ICPC2016北京
EASY：DEFK
MID：CHI
I：给定$s[i]$，求$f[i]=\sum (\sum_j^i s[j])^k$，$n\leq50000,k\leq100$。
令$S[i]=\sum_j^i s[j]$，将公式拆开得$f[i]=\sum (S[i]-S[j-1])^k=C(k,0)*S[i]^k-C(k,1)*S[i]^{k-1}*S[j-1]+...+(-1)^k*C(k,k)*S[j-1]^k$，再记一次幂次前缀和就行了
#include<bits/stdc++.h>
#define N 55555
#define W 111
#define M 1000000007
using namespace std;
int T,i,j,n,k,o,V,an,S[N][W],SS[N][W],c[W][W];
char s[N];
int main(){
for(i=0;i<=100;i++)for(c[i][0]=j=1;j<=i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%M;
for(scanf("%d",&T);T--;){
scanf("%d%d%s",&n,&k,s+1);an=0;SS[0][0]=1;
for(i=1;i<=n;i++)S[i][0]=1,S[i][1]=S[i-1][1]+s[i]-'0';
for(i=1;i<=n;i++)for(j=2;j<=k;j++)S[i][j]=1ll*S[i][j-1]*S[i][1]%M;
for(i=1;i<=n;i++)for(j=0;j<=k;j++)SS[i][j]=(SS[i-1][j]+S[i][j])%M;
for(i=1;i<=n;i++){
for(an=j=0;j<=k;j++){
V=1ll*S[i][k-j]*SS[i-1][j]%M*c[k][j]%M;
if(j&1)an=(an+M-V)%M;else an=(an+V)%M;
}
printf("%d%c",an,i==n?'\n':' ');
}
}
}
C：一个$n*n$的棋盘上每个格子是黑或白，要求第$i$行的黑棋数在$[Li_i,Ri_i]$之间，第$j$行的黑棋数在$[Lj_j,Rj_j]$之间。现在有$\frac{n*n}{2}$对交换$(X1,Y1)(X2,Y2)$，表示可以交换$(X1,Y1)(X2,Y2)$的棋子，满足$X1=X2$或$Y1=Y2$，问是否满足所有限制以及满足所有限制的最小交换数。
网络流建图，将行和列拆成点，源向行、列连本来的黑棋数，行、列向汇连限制范围，行、列之间交换棋子加费用，跑有源汇最小费用最大流。
#include<bits/stdc++.h>
#define N 111
#define M 22222
#define inf 1e9
#define CL(a) memset(a,0,sizeof a)
using namespace std;
int n,S,T,SS,TT,a[N][N],Vi[N],Vj[N],Li[N],Ri[N],Lj[N],Rj[N];
struct CostFlow{
int m,h,t,tot,an,fl,SUM,du[N],fir[N],va[M],la[M],ne[M],q[N],d[N],fa[N],pre[N],co[M];bool v[N];
void in(){CL(fir);CL(pre);CL(fa);CL(du);tot=1;SUM=0;}
void ins(int x,int y,int fl,int z){
la[++tot]=y;ne[tot]=fir[x];va[tot]=fl;co[tot]=z;fir[x]=tot;
la[++tot]=x;ne[tot]=fir[y];va[tot]=0;co[tot]=-z;fir[y]=tot;
}
void add(int x,int y,int L,int R,int c){
du[x]-=L;du[y]+=L;
ins(x,y,R-L,c);
}
void prepare(){
for(int i=1;i<=n;i++){
if(du[i]>0)ins(SS,i,du[i],0),SUM+=du[i];
if(du[i]<0)ins(i,TT,-du[i],0);
}
ins(T,S,inf,0);
}
bool spfa(int S,int T,int n){
int i,x,y;
for(i=1;i<=n;i++)d[i]=inf;
for(CL(v),d[S]=h=0,v[q[t=1]=S]=1;h^t;)
for(i=fir[x=q[h=h%n+1]],v[x]=0;i;i=ne[i])
if(d[x]+co[i]<d[y=la[i]]&&va[i]){
d[y]=d[fa[y]=x]+co[pre[y]=i];
if(!v[y])v[q[t=t%n+1]=y]=1;
}
return d[T]<inf;
}
void end(int S,int T){
int i,p=inf;
for(i=T;i!=S;i=fa[i])p=min(p,va[pre[i]]);fl+=p;
for(i=T;i!=S;i=fa[i])va[pre[i]]-=p,va[pre[i]^1]+=p,an+=p*co[pre[i]];
}
int cal(int S,int T,int n){
for(an=fl=0;spfa(S,T,n);end(S,T));
return an;
}
int work(){
cal(SS,TT,n+2);
if(fl!=SUM)return -1;else return an;
}
}G;
int main(){
int i,j,X1,Y1,X2,Y2;
for(;~scanf("%d",&n);){
CL(Vi);CL(Vj);G.in();S=n+n+1;T=S+1;SS=T+1;TT=T+2;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(scanf("%d",&a[i][j]),a[i][j])Vi[i]++,Vj[j]++;
for(i=1;i<=n;i++){
scanf("%d%d",&Li[i],&Ri[i]);
G.add(S,i,Vi[i],Vi[i],0);
G.add(i,T,Li[i],Ri[i],0);
}
for(j=1;j<=n;j++){
scanf("%d%d",&Lj[j],&Rj[j]);
G.add(S,n+j,Vj[j],Vj[j],0);
G.add(n+j,T,Lj[j],Rj[j],0);
}
for(i=1;i<=n*n/2;i++){
scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
if(a[X1][Y1]!=a[X2][Y2]){
if(!a[X1][Y1])swap(X1,X2),swap(Y1,Y2);
if(X1==X2)G.add(Y1+n,Y2+n,0,1,1);
if(Y1==Y2)G.add(X1,X2,0,1,1);
}
}
n=T;G.prepare();
printf("%d\n",G.work());
}
}
H：二分答案，K次圆并裸题
#include<bits/stdc++.h>
#define N 1111
#define CL(a) memset(a,0,sizeof a)
#define eps 1e-8
#define pi acos(-1)
using namespace std;
int sgn(double x){return x<-eps?-1:x>eps;}//x>0-->1 x=0-->0 x<0-->-1
int cmp(double x,double y){return sgn(x-y);}//x>y-->1 x=0-->0 x<y-->-1
double sqr(double x){return x*x;}
struct P{//一个点或者一个向量
double x,y;
P(double x=0,double y=0):x(x),y(y){}
void in(){scanf("%lf%lf",&x,&y);}
void out(){printf("%.7f %.7f\n",x,y);}
double norm(){return sqrt(x*x+y*y);}//模长
double norm2(){return x*x+y*y;}
P unit(){//单位向量
double l=norm();
return P(x/l,y/l);
}
P rot90(){return P(-y,x);}
double angle(){return atan2(y,x);}//角度
};
bool operator==(P a,P b){return !cmp(a.x,b.x)&&!cmp(a.y,b.y);}
bool operator!=(P a,P b){return !(a==b);}
bool operator<(P a,P b){return cmp(a.x,b.x)==0?cmp(a.y,b.y)<0:cmp(a.x,b.x)<0;}
P operator-(P a){return P(-a.x,-a.y);}
P operator+(P a,P b){return P(a.x+b.x,a.y+b.y);}
P operator-(P a,P b){return P(a.x-b.x,a.y-b.y);}
P operator*(P a,double b){return P(a.x*b,a.y*b);}
P operator/(P a,double b){return P(a.x/b,a.y/b);}
double dis(P a,P b){return (a-b).norm();}//距离
struct C{//圆类
P c;double r;
explicit C(P c=P(),double r=0):c(c),r(r){}
void in(){c.in();scanf("%lf",&r);}
};
bool operator==(C a,C b){
return a.c==b.c&&cmp(a.r,b.r)==0;
}
bool operator!=(C a,C b){return !(a==b);}
bool in_circle(P a,C b){//点是否再圆内
return cmp(dis(a,b.c),b.r)<=0;
}
int circle_relationship(C a,C b){//两圆关系
if(a==b)return 0;//相同
double d=dis(a.c,b.c),r1=a.r+b.r,r2=fabs(a.r-b.r);
if(sgn(d-r1)==1)return 5;//相离
if(sgn(d-r1)==0)return 4;//外切
if(sgn(d-r2)==1)return 3;//相交
if(sgn(d-r2)==0)return 2;//内切
return 1;//相含
}
C make_circle(P a,P b){//以两点为直径做圆
return C((a+b)/2,dis(a,b)/2);
}
P __circle_intersect(C a,C b){
P r=(b.c-a.c).unit();
double d=dis(a.c,b.c);
double x=0.5*((sqr(a.r)-sqr(b.r))/d+d);
double h=sqrt(sqr(a.r)-sqr(x));
return a.c+r*x+r.rot90()*h;
}
void circle_intersect(C a,C b,P&p1,P&p2){//两圆的交点
p1=__circle_intersect(b,a);
p2=__circle_intersect(a,b);
}
double an[N];bool vs[N];
pair<double,int>q[N];
double cal(C o,double l,double r){
return o.r*.5*(o.r*(r-l)+(o.c.x*(sin(r)-sin(l))-o.c.y*(cos(r)-cos(l))));
}
int n,K;double W,S;double X[N],Y[N],Z[N];
bool ok(double H){
int V,i,j,k,t,cnt;C p[N];P p1,p2;double v1,v2,Rv;
for(i=1;i<=n;i++)p[i-1]=C(P(X[i],Y[i]),W/sqrt(sqr(X[i])+sqr(Y[i])+H*H)/Z[i]),an[i]=0;
for(i=0;i<n;i++)vs[i]=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)if(i!=j&&sgn(p[j].r-p[i].r)>=0&&!vs[j])
if(circle_relationship(p[i],p[j])==0)vs[i]=1;
for(i=0;i<n;i++)if(!vs[i]){
for(k=j=0;j<n;j++)if(sgn(p[j].r-p[i].r)>=0&&circle_relationship(p[i],p[j])<=2)k++;
for(t=j=0;j<n;j++)if(!vs[j]&&i!=j&&circle_relationship(p[i],p[j])==3){
circle_intersect(p[i],p[j],p1,p2);
v1=(p1-p[i].c).angle(),v2=(p2-p[i].c).angle();
if(sgn(v1)<0)v1+=pi*2;if(sgn(v2)<0)v2+=pi*2;
if(sgn(v2-v1)>=0)q[++t]=make_pair(v1,1),q[++t]=make_pair(v2,-1);
else q[++t]=make_pair(0,1),q[++t]=make_pair(v2,-1),q[++t]=make_pair(v1,1),q[++t]=make_pair(pi*2,-1);
}
sort(q+1,q+t+1);Rv=0;
for(j=1;j<=t;j++){
an[V+k]+=cal(p[i],q[j-1].first,q[j].first);
V+=q[j].second;Rv=q[j].first;
}
an[V+k]+=cal(p[i],Rv,pi*2);
}
return sgn(an[K]-S)>=0;
}
int main(){
int T,i;double L,R,MD;
for(scanf("%d",&T);T--;){
scanf("%d%lf%d%lf",&n,&W,&K,&S);
for(i=1;i<=n;i++)scanf("%lf%lf%lf",&X[i],&Y[i],&Z[i]);
if(ok(500)||!K){puts("Oops!");continue;}
if(!ok(0)){puts("No solution!");continue;}
for(L=0,R=500;R-L>eps;)if(ok(MD=(L+R)*.5))L=MD;else R=MD;
printf("%.4lf\n",L);
}
}
HARD：
A：一个01矩阵是合法的要满足对于所有的$1\leq i\leq N,1\leq j\leq M$，有$v[i][j]\ xor\ v[i-1][j]\ xor\ v[i+1][j]\ xor\ v[i][j-1]\ xor\ v[i][j+1]=0$，现在给定$N$行$M$列矩阵，$Q$次询问字典序第$k$小的矩阵的$v[x][y]$是$0$还是$1$。$N,M,Q\leq 800,K\leq 2^{800}$
暂时不会做
评论 (0)
