4
12
2016
0

[BZOJ4514] [Sdoi2016]数字配对

用二分图建图再跑最大费用最大流就可以了

考场上建图写炸了。。。sad

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
 
const long long INF=1000000000000000ll;
 
int n,en,S,T,h[10005],flag[10005],Back[10005],Tag,tab[100005],cnt,X[10005],Y[10005],xs=0,ys=0;
long long A[2005],B[2005],C[2005],D[10005],Cost=0;
queue<int> Q;
 
struct Edge{
int b,back,next;
long long f,c;
}e[2000005];
 
void AddEdge(int sa,int sb,long long sc,long long sd){
e[++en].b=sb;
e[en].back=en+1;
e[en].f=sc;
e[en].c=sd;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].back=en-1;
e[en].f=0;
e[en].c=-sd;
e[en].next=h[sa];
h[sa]=en;
}
 
bool SPFA(){
memset(D,-80,sizeof(D));
memset(flag,0,sizeof(flag));
memset(Back,0,sizeof(Back));
D[S]=0;
Q.push(S);
flag[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    flag[u]=0;
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(D[u]+e[i].c>D[v] && e[i].f){
            D[v]=D[u]+e[i].c;
            Back[v]=i;
            if(!flag[v]){
                flag[v]=1;
                Q.push(v);
            }
        }
    }
}
return D[T]>-INF;
}
 
long long Flow(){
long long ans=INF,Co=0;
int Tx=Back[T];
while(Tx){
    ans=min(ans,e[Tx].f);
    Co+=e[Tx].c;
    Tx=Back[e[e[Tx].back].b];
}
while(Cost+ans*Co<0)ans--;if(ans<=0){Tag=1;return 0;}
Tx=Back[T];
while(Tx){
    e[Tx].f-=ans;
    e[e[Tx].back].f+=ans;
    Cost+=ans*e[Tx].c;
    Tx=Back[e[e[Tx].back].b];
}
return ans;
}
 
long long MaxCost(){
long long ans=0;
while(SPFA()){
    ans+=Flow();
    if(Tag)break;
}
return ans;
}
 
bool Test(int x){
if(x==1 || x==0)return 0;
for(int i=2;i*i<=x;i++){
    if(x%i==0)return 0;
}
return 1;
}
 
bool Testx(long long x){
if(x==1 || x==0)return 0;
for(int i=1;tab[i]*tab[i]<=x && i<=cnt;i++){
    if(x%tab[i]==0)return 0;
}
return 1;
}
 
void Prime(){
for(int i=2;i<=40000;i++){
    if(Test(i)){tab[++cnt]=i;}
}
}
 
int Count(long long x){
int px=0;
for(int i=1;tab[i]*tab[i]<=x && i<=cnt;i++){
    while(x%tab[i]==0){px++;x/=tab[i];}
}
if(x>1)px++;
return px;
}
 
int main(){
freopen("4514.in","r",stdin);
freopen("4514.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&A[i]);
for(int i=1;i<=n;i++)scanf("%lld",&B[i]);
for(int i=1;i<=n;i++)scanf("%lld",&C[i]);
Prime();
S=n+1;T=n+2;
for(int i=1;i<=n;i++){if(Count(A[i])&1)X[++xs]=i;else Y[++ys]=i;}
for(int i=1;i<=xs;i++)AddEdge(S,X[i],B[X[i]],0);
for(int i=1;i<=ys;i++)AddEdge(Y[i],T,B[Y[i]],0);
for(int i=1;i<=xs;i++){
    for(int j=1;j<=ys;j++){
        if(A[X[i]]%A[Y[j]]==0 && Testx(A[X[i]]/A[Y[j]])){AddEdge(X[i],Y[j],INF,C[X[i]]*C[Y[j]]);}
        if(A[Y[j]]%A[X[i]]==0 && Testx(A[Y[j]]/A[X[i]])){AddEdge(X[i],Y[j],INF,C[X[i]]*C[Y[j]]);}
    }
}
printf("%lld\n",MaxCost());
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
11
2016
0

[BZOJ4318] OSU!

一道简单的期望DP题。。但是我这种题还要看别人的题解。。毕竟DP能力太差

考虑我们已经确定好了前k-1位的期望得分,那么当前第k位有两种情况:

1.操作成功为1,这么做的贡献就等于前面连续1的个数加上1后再三次方的得分然后减去前面的得分期望

2.操作失败为0,那么贡献为0

然后我们需要维护x,x2两个量,然后因为期望的线性性,我们每一次直接加上就好了

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;

int n;
double a[100005],x[100005],x2[100005],dp[100005];

int main(){
freopen("4318.in","r",stdin);
freopen("4318.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
for(int i=1;i<=n;i++){
	x[i]=(x[i-1]+1)*a[i];
	x2[i]=(x2[i-1]+2*x[i-1]+1)*a[i];
	dp[i]=dp[i-1]+(3*x2[i-1]+3*x[i-1]+1)*a[i];
}
printf("%.1lf\n",dp[n]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
11
2016
0

[BZOJ3993] [SDOI2015]星际战争

二分时间,跑实数网络流就可以了

貌似速度还很快- -

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;

const int INF=2100000000;
const double eps=1e-6;

int n,m,level[5005],h[5005],cur[5005],S,T,en,Mt[55][55];
double A[55],B[55],Sum;
queue<int> Q;

struct Edge{
int b,back,next;
double f;
}e[100005];

double Abs(double x){return x>0?x:-x;}

void AddEdge(int sa,int sb,double sc){
e[++en].b=sb;
e[en].f=sc;
e[en].next=h[sa];
e[en].back=en+1;
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].next=h[sa];
e[en].back=en-1;
h[sa]=en;
}

int BFS(){
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
        if(e[i].f<eps || level[v])continue;
        level[v]=level[u]+1;
        Q.push(v);
	}
}
return level[T];
}

double DFS(int u,double flow){
if(u==T)return flow;
double f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b;
    double fl;
    if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))>eps){
		f-=fl;
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		if(f<eps)return flow;
    }
}
return flow-f;
}

double Dinic(){
double ans=0;
while(BFS()){for(int i=1;i<=T;i++)cur[i]=h[i];ans+=DFS(S,(double)INF);}
return ans;
}

bool Test(double Ts){
memset(h,0,sizeof(h));
en=0;
S=n+m+1;
T=n+m+2;
for(int i=1;i<=m;i++)AddEdge(S,i,Ts*B[i]);
for(int i=1;i<=n;i++)AddEdge(i+m,T,A[i]);
for(int i=1;i<=m;i++){
	for(int j=1;j<=n;j++){
		if(Mt[i][j])AddEdge(i,j+m,INF);
	}
}
return Abs(Dinic()-Sum)<eps;
}

double Div(){
double l=0,r=100000000,ans;
while(r-l>eps){
	double mid=l/2+r/2;
	if(Test(mid)){ans=mid;r=mid;}
	else l=mid;
}
return ans;
}

int main(){
freopen("3993.in","r",stdin);
freopen("3993.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){scanf("%lf",&A[i]);Sum+=A[i];}
for(int i=1;i<=m;i++){scanf("%lf",&B[i]);}
for(int i=1;i<=m;i++){
	for(int j=1;j<=n;j++){
		scanf("%d",&Mt[i][j]);
	}
}
printf("%lf\n",Div());
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
11
2016
0

[BZOJ4407] 于神之怒加强版

一道反演的好题

首先我们需要推一下式子(写在纸上发现不太好写在电脑上)

拍照太烦了……其实就是Claris博客上的公式

然后倒数第二行那个式子的前缀和我不太会。。本来想问Claris的后来自己推了一下就会了

网上题解都好玄学啊

首先对于这么一个式子(用画图画的请见谅……我不会LateX)

我们把这个式子的值用一个函数F(D)表示

然后我们可以发现:对于D为质数,那么d只有两个值:一个是1,一个是D

那么我们可以暴力快速幂乘起来就可以了

如果D不是质数,为了简化我们假设这个D可以由两个质数相乘

那么d的取值可以是:1,第一个质数,第二个质数,两个质数之积

那么我们设f[i]=i是质数则为ik,否则为0

g[i]=这个和数会由哪些质数组成

我们就可得到F[i*pri[j]]=F[pri[j]]*F[i],因为这个F[i*pri[j]]会由F[i]和F[i*pri[j]]组成,那么两个sigma相乘自然就是这个值了

对于两个质数以上的乘积我觉得和上面一样的。。主要分g[i]是否等于i(i是质数)和g[i]不等于i两种情况考虑,就可以了

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int N=5000000,Mod=1000000007;

int T,n,m,k,pri[N/5+1],mu[N+5],tab[N+5],g[N+5],sum[N+5],F[N+5],f[N+5],cnt;

int Pow(int x,int y){
int base=x,ans=1;
while(y){
	if(y&1)ans=1ll*ans*base%Mod;
	base=1ll*base*base%Mod;
	y>>=1;
}
return ans;
}

void Prepare(){
mu[1]=1;
F[1]=1;
for(int i=2;i<=N;i++){
	if(!tab[i]){pri[++cnt]=i;mu[i]=-1;f[i]=Pow(i,k);F[i]=f[i]-1;g[i]=i;}
	for(int j=1;j<=cnt && i*pri[j]<=N;j++){
		tab[pri[j]*i]=1;
		if(i%pri[j]){
			mu[i*pri[j]]=-mu[i];
			g[i*pri[j]]=pri[j];
			F[i*pri[j]]=1ll*F[pri[j]]*F[i]%Mod;
		}
		else{
			mu[i*pri[j]]=0;
			g[i*pri[j]]=g[i]*pri[j];
            F[i*pri[j]]=g[i]!=i?1ll*F[i/g[i]]*F[g[i]*pri[j]]%Mod:1ll*F[i]*f[pri[j]]%Mod;
			break;
		}
	}
}
for(int i=2;i<=N;i++)F[i]=(F[i-1]+F[i])%Mod;
}

int Solve(){
int ans=0,j;
for(int i=1;i<=n && i<=m;i=j+1){
	j=min(n/(n/i),m/(m/i));
    ans=(ans+1ll*(F[j]-F[i-1]+Mod)*(n/i)%Mod*(m/i)%Mod)%Mod;
}
return ans;
}

int main(){
freopen("4407.in","r",stdin);
freopen("4407.out","w",stdout);
scanf("%d %d",&T,&k);
Prepare();
while(T--){
	scanf("%d %d",&n,&m);
    printf("%d\n",Solve());
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
10
2016
0

[BZOJ2809] [Apio2012]dispatching

首先我们确定了领导者和派遣出去的忍着数目就确定了答案

那么我们枚举领导者,每次一定派遣薪水最少的忍者们

然后先DFS,然后每次超过m我们就在可并堆中pop掉薪水最多的忍着

因为薪水是正数,所以这样做是对的

#include<cstdio>
#include<algorithm>
using namespace std;

int n,h[100005],en,siz[100005],root[100005],cnt;
long long m,ans,sum[100005];

struct Ninja{
int b;
long long c,l;
}ninja[100005];

struct Edge{
int b,next;
}e[1000005];

struct Heap{
int l,r,dis;
long long v;
}heap[100005];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

int Newheap(long long x){
heap[++cnt].v=x;
heap[cnt].l=heap[cnt].r=heap[cnt].dis=0;
return cnt;
}

int Merge(int A,int B){
if(!A)return B;
if(!B)return A;
if(heap[A].v<heap[B].v)swap(A,B);
heap[A].r=Merge(heap[A].r,B);
if(heap[heap[A].l].dis<heap[heap[A].r].dis)swap(heap[A].l,heap[A].r);
heap[A].dis=heap[heap[A].r].dis+1;
return A;
}

long long Top(int x){return heap[x].v;}
void Pop(int &x){x=Merge(heap[x].l,heap[x].r);}

void dfs(int u){
root[u]=Newheap(ninja[u].c);
siz[u]=1;
sum[u]=ninja[u].c;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	dfs(v);
	sum[u]+=sum[v];
	siz[u]+=siz[v];
	root[u]=Merge(root[u],root[v]);
}
while(sum[u]>m){
	sum[u]-=Top(root[u]);
	Pop(root[u]);
	siz[u]--;
}
ans=max(ans,siz[u]*ninja[u].l);
}

int main(){
freopen("2809.in","r",stdin);
freopen("2809.out","w",stdout);
scanf("%d %lld",&n,&m);
heap[0].dis=-1;
for(int i=1;i<=n;i++){
	scanf("%d %lld %lld",&ninja[i].b,&ninja[i].c,&ninja[i].l);
    AddEdge(ninja[i].b,i);
}
dfs(1);
printf("%lld\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
10
2016
0

[BZOJ2733] [HNOI2012]永无乡

首先连通块我们用并查集维护,而查询k大我们用权值线段树维护

建边就是合并两个线段树

查询直接在权值线段树查询就好了

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,q,a[100005],f[100005],v[100005],root[100005],cnt;

struct SegTree{
int nl,nr,sum;
}tree[2000005];

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}

void Insert(int &rt,int l,int r,int pos){
if(!rt)rt=++cnt;
if(l==r){tree[rt].sum=1;return;}
int mid=l+r>>1;
if(pos<=mid)Insert(tree[rt].nl,l,mid,pos);
else Insert(tree[rt].nr,mid+1,r,pos);
tree[rt].sum=tree[tree[rt].nl].sum+tree[tree[rt].nr].sum;
}

int Query(int rt,int l,int r,int k){
if(l==r)return l;
int mid=l+r>>1;
if(tree[tree[rt].nl].sum>=k)return Query(tree[rt].nl,l,mid,k);
return Query(tree[rt].nr,mid+1,r,k-tree[tree[rt].nl].sum);
}

int Merge(int l,int r){
if(!l)return r;
if(!r)return l;
tree[l].nl=Merge(tree[l].nl,tree[r].nl);
tree[l].nr=Merge(tree[l].nr,tree[r].nr);
tree[l].sum=tree[tree[l].nl].sum+tree[tree[l].nr].sum;
return l;
}

int main(){
freopen("2733.in","r",stdin);
freopen("2733.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);f[i]=i;}
for(int i=1;i<=m;i++){
	int tp,tq;
	scanf("%d %d",&tp,&tq);
	tp=Find(tp);tq=Find(tq);f[tp]=tq;
}
for(int i=1;i<=n;i++){Insert(root[Find(i)],1,n,a[i]);v[a[i]]=i;}
scanf("%d",&q);
while(q--){
	char s[5];
	int x,y;
	scanf("%s %d %d",s,&x,&y);
	if(s[0]=='B'){x=Find(x);y=Find(y);if(x!=y){f[x]=y;root[y]=Merge(root[x],root[y]);}}
	if(s[0]=='Q'){x=Find(x);if(tree[root[x]].sum>=y)printf("%d\n",v[Query(root[x],1,n,y)]);else puts("-1");}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
10
2016
0

[BZOJ4444] [Scoi2015]国旗计划

树上倍增

首先剖环成2倍长的链

对于每一个士兵求他的下一个士兵应该选哪一个,记录进Next数组

注意此时Next数组形成了一棵树,然后树上倍增就可以了

#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
 
int n,m,Next[400005],cnt,ans[200005],fa[400005][20];
 
struct Soldier{
long long l,r;
int id;
friend bool operator<(Soldier A,Soldier B){return A.l<B.l;}
}sol[400005];
 
int main(){
freopen("4444.in","r",stdin);
freopen("4444.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    int xl,xr;
    scanf("%d %d",&xl,&xr);
    if(xl<xr){
        sol[++cnt].l=xl;sol[cnt].r=xr;
        sol[cnt].id=i;
        sol[++cnt].l=xl+m;sol[cnt].r=xr+m;
    }
    else {
        sol[++cnt].l=xl;sol[cnt].r=xr+m;
        sol[cnt].id=i;
        sol[++cnt].l=xl+m;sol[cnt].r=xr+m+m;
    }
}
sol[0].r=21000000000000000ll;
sort(sol+1,sol+cnt+1);
int j=0;
for(int i=1;i<=cnt;i++){
    while(j<=cnt && sol[j].l<=sol[i].r)j++;
    Next[i]=j-1;
}
for(int i=cnt-1;i>=1;i--){
    fa[i][0]=Next[i];
    for(j=1;j<=19;j++)fa[i][j]=fa[fa[i][j-1]][j-1];
    if(sol[i].id){
        int tp=i;
        for(j=19;j>=0;j--){if(sol[fa[tp][j]].r-sol[i].l<m){ans[sol[i].id]+=1<<j;tp=fa[tp][j];}}
        ans[sol[i].id]+=2;
    }
}
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
3
2016
0

[BZOJ2179] FFT快速傅立叶

FFT模版题

话说网上对FFT讲的神乎其神,以后我来搞一份小学生都能看懂的FFT入门吧

最好没有公式和严谨的证明,搞一些非常通俗的就比较好

因为我自己也只会模版。。。

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

const int SIZE=300005;
const double Pi=acos(-1);

int An,Bn,Cn,n,Step,Rev[SIZE],Ans[SIZE];
char s[SIZE];

struct Complex{
double a,b;
Complex(double sa=0.0,double sb=0.0){a=sa;b=sb;}
friend Complex operator+(Complex a,Complex b){return Complex(a.a+b.a,a.b+b.b);}
friend Complex operator-(Complex a,Complex b){return Complex(a.a-b.a,a.b-b.b);}
friend Complex operator*(Complex a,Complex b){return Complex(a.a*b.a-a.b*b.b,b.a*a.b+a.a*b.b);}
}A[SIZE],B[SIZE],C[SIZE];

void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
	Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
	for(int i=0;i<n;i+=k<<1){
		Complex wkj=Complex(1.0,0.0);
		for(int j=0;j<k;j++){
			Complex a=x[i+j],b=x[i+j+k]*wkj;
			x[i+j]=a+b;
			x[i+j+k]=a-b;
			wkj=wkj*wk;
		}
	}
}
if(flag==-1)for(int i=0;i<n;i++)x[i].a/=n;
}

void Init_Solve_Out(){
scanf("%d",&An);
Bn=An;Cn=An+Bn-1;
scanf("%s",s);
for(int i=0;i<An;i++)A[i]=Complex(s[i]-'0');
scanf("%s",s);
for(int i=0;i<Bn;i++)B[i]=Complex(s[i]-'0');
for(n=1,Step=0;n<Cn;n<<=1,Step++);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);FFT(B,1);
for(int i=0;i<n;i++)C[i]=A[i]*B[i];
FFT(C,-1);
for(int i=0;i<Cn;i++)Ans[Cn-i]=(int)(C[i].a+0.5);
for(int i=1;i<=Cn;i++)Ans[i+1]+=Ans[i]/10,Ans[i]%=10;
if(Ans[Cn+1])Cn++;
for(int i=Cn;i>=1;i--)printf("%d",Ans[i]);
}

int main(){
freopen("2179.in","r",stdin);
freopen("2179.out","w",stdout);
Init_Solve_Out();
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
30
2016
0

[BZOJ3343] 教主的魔法

分块

每个块维护两个数组,一个是按位置排序,另一个按大小排序

修改暴力做两块,中间搞个tag

询问两块暴力,中间二分

#include<cstdio>
#include<algorithm>
using namespace std;

int n,q,cnt;
const int block_size=1000,block_num=1000;

struct Block{
int block1[block_size+5],block2[block_size+5];
int n,tag;
}block[block_num+5];

void Add(int l,int r,int v){
int first_block=(l-1)/block_size+1,last_block=(r-1)/block_size+1,first_pos=(l-1)%block_size+1,last_pos=(r-1)%block_size+1;
if(first_block==last_block){
    for(int i=first_pos;i<=last_pos;i++)block[first_block].block1[i]+=v;
    for(int i=1;i<=block[first_block].n;i++)block[first_block].block2[i]=block[first_block].block1[i];
    sort(block[first_block].block2+1,block[first_block].block2+block[first_block].n+1);
	return;
}
for(int i=first_block+1;i<last_block;i++)block[i].tag+=v;
for(int i=first_pos;i<=block[first_block].n;i++)block[first_block].block1[i]+=v;
for(int i=1;i<=block[first_block].n;i++)block[first_block].block2[i]=block[first_block].block1[i];
sort(block[first_block].block2+1,block[first_block].block2+block[first_block].n+1);
for(int i=1;i<=last_pos;i++)block[last_block].block1[i]+=v;
for(int i=1;i<=block[last_block].n;i++)block[last_block].block2[i]=block[last_block].block1[i];
sort(block[last_block].block2+1,block[last_block].block2+block[last_block].n+1);
}

int Div(int id,int k){
int l=1,r=block[id].n,ans=0;
while(l<=r){
	int mid=l+r>>1;
	if(block[id].block2[mid]+block[id].tag<k){l=mid+1;ans=mid;}
	else {r=mid-1;}
}
return block[id].n-ans;
}

int Query(int l,int r,int k){
int first_block=(l-1)/block_size+1,last_block=(r-1)/block_size+1,first_pos=(l-1)%block_size+1,last_pos=(r-1)%block_size+1,ans=0;
if(first_block==last_block){
    for(int i=first_pos;i<=last_pos;i++)ans+=(k<=(block[first_block].block1[i]+block[first_block].tag));
	return ans;
}
for(int i=first_block+1;i<last_block;i++)ans+=Div(i,k);
for(int i=first_pos;i<=block[first_block].n;i++)ans+=(k<=(block[first_block].block1[i]+block[first_block].tag));
for(int i=1;i<=last_pos;i++)ans+=(k<=(block[last_block].block1[i]+block[last_block].tag));
return ans;
}

int main(){
freopen("3343.in","r",stdin);
freopen("3343.out","w",stdout);
scanf("%d %d",&n,&q);
cnt=(n-1)/block_size+1;
for(int i=1;i<cnt;i++)block[i].n=block_size;
block[cnt].n=(n-1)%block_size+1;
for(int i=1;i<=n;i++){
	int pos_block=(i-1)/block_size+1,pos=(i-1)%block_size+1;
	scanf("%d",&block[pos_block].block1[pos]);
}
for(int i=1;i<=cnt;i++){
	for(int j=1;j<=block[i].n;j++)block[i].block2[j]=block[i].block1[j];
	sort(block[i].block2+1,block[i].block2+block[i].n+1);
}
for(int i=1;i<=q;i++){
	int l,r,v;
	char s[5];
    scanf("%s %d %d %d",s,&l,&r,&v);
    if(s[0]=='M')Add(l,r,v);
    if(s[0]=='A')printf("%d\n",Query(l,r,v));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
29
2016
0

[BZOJ1468] Tree

一模一样的点分治……

为了凑博客数又复制了一遍

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
  
int n,k,h[40005],en,mx[40005],siz[40005],ans,root,val,vis[40005],temp[40005],cnt;
  
struct Edge{
int b,v,next;
}e[80005];
  
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
  
void DfsSiz(int u,int fa){
siz[u]=1;
mx[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v]){
        DfsSiz(v,u);
        siz[u]+=siz[v];
        mx[u]=max(mx[u],siz[v]);
    }
}
}
  
void DfsRoot(int point,int u,int fa){
mx[u]=max(mx[u],siz[point]-siz[u]);
if(val>mx[u]){val=mx[u];root=u;}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v])DfsRoot(point,v,u);
}
}
  
void GetDist(int u,int fa,int val){
temp[++cnt]=val;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v])GetDist(v,u,val+e[i].v);
}
}
  
int Cal(int u,int val){
cnt=0;
int now=0;
GetDist(u,u,val);
sort(temp+1,temp+cnt+1);
//for(int i=1;i<=cnt;i++)printf("Temp:%d\n",temp[i]);
int i=1,j=cnt;
while(i<j){
    while(temp[i]+temp[j]>k && i<j)j--;
    now+=j-i;
    i++;
}
//printf("Now:%d\n",now);
return now;
}
  
void Dfs(int u){
val=2100000000;
DfsSiz(u,u);
DfsRoot(u,u,0);
ans+=Cal(root,0);
//printf("Ans:%d\n",ans);
vis[root]=1;
for(int i=h[root];i;i=e[i].next){
    int v=e[i].b;
    if(!vis[v]){
        ans-=Cal(v,e[i].v);
        Dfs(v);
    }
}
}
  
int main(){
freopen("1468.in","r",stdin);
freopen("1468.out","w",stdout);
scanf("%d",&n);
//memset(h,0,sizeof(h));
//memset(vis,0,sizeof(vis));
//ans=en=0;
for(int i=1;i<n;i++){
    int sa,sb,sc;
    scanf("%d %d %d",&sa,&sb,&sc);
    AddEdge(sa,sb,sc);
    AddEdge(sb,sa,sc);
}
scanf("%d",&k);
Dfs(1);
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com