省队十连测

严厉谴责为了增加题目难度专门卡常的题！！！

真是气死人不偿命啊……

 

bzoj5215

非常明显的前部分直接背包，后部分算组合数。

你竟然卡常？！！

 

bzoj5216

线段树维护最小生成树，时限20s，我跑了19.7s，真开心呀。

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=2e5+7;
int n,m,Q,f[maxn];

char cc;ll ff;
template<typename T>void read(T& aa) {
	aa=0;ff=1; cc=getchar();
	while(cc!='-'&&(cc<'0'||cc>'9')) cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

int find(int x) {return x==f[x]? x:f[x]=find(f[x]);}
void reset() {For(i,1,n) f[i]=i;}

struct Node{
	int x,y,c;
	Node(){}
	Node(int x,int y,int c):x(x),y(y),c(c){}
}node[maxn];

struct T{
	vector<int> road;
	int sum;
	T(){road.clear(); sum=0;}
	bool insert(int p) const{
		if(find(node[p].x)==find(node[p].y)) return 0;
		f[find(node[p].x)]=find(node[p].y);
		return 1;
	}
	T operator + (const T& b) const{
		reset(); T o;
		int x=0,y=0,xx,yy,N=road.size(),M=b.road.size();
		while(x<N||y<M) {
			if(x<N) xx=road[x]; if(y<M) yy=b.road[y];
			if(y>=M||(x<N&&node[xx].c<=node[yy].c)) {
				if(o.insert(xx)) {
					o.sum+=node[xx].c;
					o.road.push_back(xx);
				}
				x++;
			}
			else {
				if(o.insert(yy)) {
					o.sum+=node[yy].c;
					o.road.push_back(yy);
				}
				y++;
			}
		}
		return o;
	}
}seg[4*maxn];
int ql,qr;

void bld(int pos,int l,int r) {
	if(l==r) {
		seg[pos].insert(l);
		seg[pos].road.push_back(l);
		seg[pos].sum=node[l].c;
		return;
	}
	int mid=(l+r)>>1;
	bld(pos<<1,l,mid);
	bld(pos<<1|1,mid+1,r);
	seg[pos]=seg[pos<<1]+seg[pos<<1|1];
}

T q(int pos,int l,int r) {
	if(l>=ql&&r<=qr) return seg[pos];
	int mid=(l+r)>>1; 
	if(ql<=mid&&qr<=mid) return q(pos<<1,l,mid);
	if(ql>mid&&qr>mid) return q(pos<<1|1,mid+1,r);
	return q(pos<<1,l,mid)+q(pos<<1|1,mid+1,r);
}

int main() {
	read(n); read(m); read(Q);
	int x,y,c;
	For(i,1,m) {
		read(x); read(y); read(c);
		node[i]=Node(x,y,c);
	}
	bld(1,1,m);
	For(i,1,Q) {
		read(ql); read(qr);
		printf("%d
",q(1,1,m).sum);
	}
	return 0;
}

 

bzoj5217

把二维拉成一维，FFT。

注意不要sb如我上NTT结果T得连妈都不认识了……

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=2e6+7,maxt=700+7,INF=701,tx[4]={1,-1,0,0},ty[4]={0,0,1,-1};
const db PI=acos(-1);
ll n,m,ans;
char s[maxt][maxt];
bool vis[maxt][maxt];

char cc;ll ff;
template<typename T>void read(T& aa) {
	aa=0;ff=1; cc=getchar();
	while(cc!='-'&&(cc<'0'||cc>'9')) cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

struct Virt{
    db r,i;
    Virt(db r=0.0,db i=0.0) {this->r=r;this->i=i;}
    Virt operator + (const Virt& x) {return Virt(r+x.r,i+x.i);}
    Virt operator - (const Virt& x) {return Virt(r-x.r,i-x.i);}
    Virt operator * (const Virt& x) {return Virt(r*x.r-i*x.i,r*x.i+i*x.r);}
}a[maxn],b[maxn];
 
void Rader(Virt F[],ll len) {
	for(int i=1,j=len>>1,k;i<len-1;++i) {
		if(i<j) swap(F[i],F[j]);
		k=len>>1;
		while(j>=k) {j-=k;k>>=1;}
		if(j<k) j+=k;
	}
}
 
void FFT(Virt F[],int len,int on) {
    Rader(F,len);
    for(int h=2;h<=len;h<<=1) {
        Virt wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
        for(int j=0;j<len;j+=h) {
            Virt w(1,0);
            for(int k=j;k<j+h/2;++k) {
                Virt u=F[k],t=w*F[k+h/2];
                F[k]=u+t;
                F[k+h/2]=u-t;
                w=w*wn;
            }
        }
    }
    if(on==-1) for(int i=0;i<len;++i) F[i].r/=len;
}

int zz[maxn];
void bfs(int sx,int sy) {
	int s=1,t=0,x,y,xx,yy;
	zz[++t]=sx*1000+sy;vis[sx][sy]=0;
	while(s<=t) {
		x=y=zz[s++]; x/=1000; y%=1000;
		a[(x-1)*m+y-1]=Virt(1,0);
		For(i,0,3) {
			xx=x+tx[i]; yy=y+ty[i];
			if(vis[xx][yy]) zz[++t]=xx*1000+yy,vis[xx][yy]=0;
		}
	}
}		

int main() {
	read(n); read(m);
	For(i,1,n) scanf("%s",s[i]+1);
	int l1=INF,l2=INF,r1=0,r2=0;
	For(i,1,n) For(j,1,m) {
		if(s[i][j]=='o') {
			l1=min(l1,i); l2=min(l2,j);
			r1=max(r1,i); r2=max(r2,j);
		}
		else if(s[i][j]=='#') a[n*m-(i-1)*m-j]=Virt(1,0);
	}
	For(i,1,n) For(j,1,m) if(s[i][j]=='o') b[(i-l1)*m+j-l2]=Virt(1,0);
	int len=1; for(;len<=((n*m)<<1);len<<=1);
	FFT(a,len,1); FFT(b,len,1);
	For(i,0,len) a[i]=a[i]*b[i];
	FFT(a,len,-1);
	For(i,1,n-(r1-l1)) For(j,1,m-(r2-l2))
		if(a[n*m-(i-1)*m-j].r<0.5) vis[i][j]=1;
	memset(a,0,sizeof(a));
	bfs(l1,l2);
	FFT(a,len,1);
	For(i,0,len) a[i]=a[i]*b[i];
	FFT(a,len,-1);
	For(i,0,n*m) if(a[i].r>0.5) ans++;
	printf("%lld
",ans);
	return 0;
}