EC-Final2016
Easy：ADEL
E：赌博水题，让$\sum \frac{1}{p}<1$即可，$p$为赌$1$元实际所得。坑点是要开long double，坑了好久。。
#include<bits/stdc++.h>
#define N 111
#define CL(a) memset(a,0,sizeof a)
using namespace std;
int T,ca,n,an,i;char c;
long double V,x,y,pl[N];
int main(){
scanf("%d",&T);
for(ca=1;ca<=T;ca++){
scanf("%d",&n);an=0;V=0;
for(i=1;i<=n;i++)cin>>x>>c>>y,pl[i]=x/(x+y);
sort(pl+1,pl+n+1);
for(i=1;i<=n;i++){
V+=pl[i];
if(V<1)an=i;
}
printf("Case #%d: %d\n",ca,an);
}
}
MID：BCFH
C：因为常数较小，$O(n^3)$暴枚即可通过，不用加任何优化
#include<bits/stdc++.h>
#define N 1111
#define CL(a) memset(a,0,sizeof a)
using namespace std;
int T,n,i,j,ca,an,L,R,cnt,c[N],a[N],v[N];
int main(){
scanf("%d",&T);
for(ca=1;ca<=T;ca++){
scanf("%d",&n);an=0;
for(i=1;i<=n;i++)scanf("%d",&a[i]),v[i]=a[i];
sort(v+1,v+n+1);cnt=unique(v+1,v+n+1)-v-1;
for(i=1;i<=n;i++)a[i]=lower_bound(v+1,v+cnt+1,a[i])-v;
for(i=1;i<=n;i++){
for(j=i;j<=n&&!c[a[j]];j++){
c[a[j]]++;
an=max(an,j-i+1);
for(L=j+2,R=0;L<=n;L++){
if(R<L)R=L;
for(;R<=n&&!c[a[R]];)c[a[R++]]=1;
an=max(an,j-i+1+R-L);
if(R>L)c[a[L]]=0;
}
}
for(;j>=i;j--)c[a[j]]=0;
}
printf("Case #%d: %d\n",ca,an);
}
}
H：每个格子分别考虑各自的贡献，从$[1,k]$枚举该格子的值$i$，那么它是超级格子的概率为$\frac{(i-1)^{n+m-2}}{k^{n+m-2}}$，总方案数为$k^{n*m}$，那么答案即为$k^{n*m}+n*m*k^{n*m-n-m+1}*\sum_i^k (i-1)^{n+m-2}$。
#include<bits/stdc++.h>
#define M 1000000007
#define LL long long
using namespace std;
int T,ca,n,m,k,i;
LL V,an;
LL Pw(LL a,LL b,LL p){
LL v=1;
for(;b;b>>=1,a=a*a%p)if(b&1)v=v*a%p;
return v;
}
int main(){
scanf("%d",&T);
for(ca=1;ca<=T;ca++){
scanf("%d%d%d",&n,&m,&k);V=0;
for(i=k;i;i--)V=(V+Pw(i-1,n+m-2,M))%M;
V=V*n%M*m%M*Pw(k,n*m-n-m+1,M)%M;;
printf("Case #%d: %I64d\n",ca,(V+Pw(k,n*m,M))%M);
}
}
F：将第$2-n$个串建广义后缀自动机，第$1$个串在上面跑最短不公共子串即可。将m达成n调了好久。。。
#include<bits/stdc++.h>
#define N 666666
#define CL(a) memset(a,0,sizeof a)
char s[N],A[N];
int T,ca,al,ar,n,m,i,j,x,p,np,q,nq,cnt,L,st[N],c[N][27],F[N];
void add(int x){
p=np;st[np=++cnt]=st[p]+1;
for(;p&&!c[p][x];p=F[p])c[p][x]=np;
if(!p)F[np]=1;else
if(st[p]+1==st[q=c[p][x]])F[np]=q;else{
st[nq=++cnt]=st[p]+1;memcpy(c[nq],c[q],sizeof c[q]);
F[nq]=F[q];F[q]=F[np]=nq;
for(;p&&c[p][x]==q;p=F[p])c[p][x]=nq;
}
}
void up(int ul,int ur){
if(ur-ul<ar-al)al=ul,ar=ur;else if(ur-ul==ar-al){
for(int j=0;j<=ar-al;j++)if(A[al+j]!=A[ul+j]){
if(A[ul+j]<A[al+j])al=ul,ar=ur;
return;
}
}
}
int main(){
scanf("%d",&T);
for(ca=1;ca<=T;ca++){
scanf("%d",&n);al=0;ar=1e9;
np=cnt=1;scanf("%s",A);
for(i=2;i<=n;i++){
scanf("%s",s);m=strlen(s);
for(j=0;j<m;j++)add(s[j]-'a');
add(26);
}
m=strlen(A);
for(p=1,L=i=0;i<m;i++)
if(c[p][x=A[i]-'a'])p=c[p][x],L=st[F[p]]+1;else{
for(;!c[p][x]&&p;p=F[p],L=st[F[p]]+1)up(i-L,i);
if(!p)p=1,L=0;else p=c[p][x],L=st[F[p]]+1;
}
printf("Case #%d: ",ca);
if(ar-al>m)puts("Impossible");else{
for(i=al;i<=ar;i++)printf("%c",A[i]);puts("");
}
for(i=1;i<=cnt;i++)for(F[i]=st[i]=0,j=0;j<27;j++)c[i][j]=0;
}
}
B：求长度为$n$字典序第$k$小的H回文串。H回文串：奇数位连起来是回文串或者偶数位连起来是回文串。$N\leq100000,K\leq 10^{18}$。
如果已经确定了前$i$位，可以通过容斥求出后几位的方案数，即奇数是回文串+偶数是回文串-奇数、偶数都是回文串，那么可以逐位确定得到答案。但由于$N$较大，而只用求字典序$K$小的，于是只需要确定后$2log_2(K)$位即可得到正确答案。时间复杂度$O(NlgK)$。
#include<bits/stdc++.h>
#define N 111111
#define LL long long
const LL inf=1e18;
LL k,an,pw[N];
int T,ca,n,i,v[N];
using namespace std;
LL get(int A,int B){
bool ff;int V=0;
for(int i=1,j;i<=n;i++){
j=(n&1)?n-i+1:(i&1)?n-i:n-i+2;
if(j<i)continue;
ff=(i&1)?A:B;
if((v[i]&&v[j]&&v[i]!=v[j])&&ff)return 0;
if(i==j)V=(v[i])?V:V+1;
else if(!v[i]||!v[j])V+=(!ff)+(!v[i]&&!v[j]);
}
return pw[V];
}
LL CAL(){return get(1,0)+get(0,1)-get(1,1);}
int main(){
for(pw[0]=i=1;i<N;i++)pw[i]=min(pw[i-1]*2,inf);
scanf("%d",&T);
for(ca=1;ca<=T;ca++){
printf("Case #%d: ",ca);
scanf("%d%lld",&n,&k);
an=CAL();
if(k>an){puts("NOT FOUND!");continue;}
for(i=1;i<=n-130;i++)v[i]=1;
for(i=max(1,n-129);i<=n;i++){
v[i]=1;an=CAL();
if(an<k)k-=an,v[i]=2;
}
for(i=1;i<=n;i++)printf("%d",v[i]-1),v[i]=0;
puts("");
}
}
MID-HARD：GJ
G：$N$个点$M$条边$(x,y,z)$的图，每个点有一个颜色$c_i$。在线$Q$次询问从$x$点出发经过边权不超过$z$的边到的所有点中出现次数最多的颜色，如果个数相同输出标号最小的。$N,M,Q\leq200000$。
Kruskal重构树，询问树上倍增找到管理的点，相当于在线询问子树中出现最多的数。而这个在线是假的，只要求出所有子树出现最多的数就行了，用线段树合并处理出答案，询问时直接在树上倍增找到所对应的子树即可。时间复杂度$O((N+Q)logN)$。
#include<bits/stdc++.h>
#define N 222222
#define M 4444444
#define CL(a) memset(a,0,sizeof a)
using namespace std;
int Te,ca,n,nn,m,Q,x,y,i,j,id,AN,tot,fa[N],c[N],an[N],fir[N],ne[N],la[N],F[N][18],d[N][18],T[N],L[M],R[M];
pair<int,int>mv[M];
struct P{int x,y,z;}p[N];
bool cmp(P a,P b){return a.z<b.z;}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int get(int x,int z){
for(int i=17;~i;i--)if(F[x][i]&&d[x][i]<=z)x=F[x][i];
return x;
}
void ins(int&k,int l,int r,int z){
k=++id;L[k]=R[k]=0;mv[k]=make_pair(0,0);int md=l+r>>1;
if(l==r)mv[k].first++,mv[k].second=-z;
else z<=md?ins(L[k],l,md,z):ins(R[k],md+1,r,z),mv[k]=max(mv[L[k]],mv[R[k]]);
}
int mg(int x,int y,int l,int r){
if(!x||!y)return x+y;
if(l==r)mv[x].first+=mv[y].first;else{
int md=l+r>>1;
L[x]=mg(L[x],L[y],l,md);
R[x]=mg(R[x],R[y],md+1,r);
mv[x]=max(mv[L[x]],mv[R[x]]);
}
return x;
}
void dfs(int x){
if(x<=nn)ins(T[x],1,nn,c[x]);
for(int i=fir[x];i;i=ne[i])dfs(la[i]),T[x]=mg(T[x],T[la[i]],1,nn);
an[x]=-mv[T[x]].second;
}
int main(){
scanf("%d",&Te);
for(ca=1;ca<=Te;ca++){
CL(fa);CL(T);CL(fir);tot=id=AN=0;
printf("Case #%d:\n",ca);
scanf("%d%d",&n,&m);nn=n;
for(i=1;i<=n;i++)scanf("%d",&c[i]),fa[i]=i;
for(i=1;i<=m;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
sort(p+1,p+m+1,cmp);
for(i=1;i<=m;i++){
x=gf(p[i].x);y=gf(p[i].y);
if(x!=y){
fa[x]=fa[y]=F[x][0]=F[y][0]=++n;fa[n]=n;
d[x][0]=d[y][0]=p[i].z;ins(n,x);ins(n,y);
}
}
dfs(n);
for(j=1;j<=17;j++)for(i=1;i<=n;i++)d[i][j]=max(d[i][j-1],d[F[i][j-1]][j-1]),F[i][j]=F[F[i][j-1]][j-1];
for(scanf("%d",&Q);Q--;printf("%d\n",AN))scanf("%d%d",&x,&y),x=get(x^AN,y^AN),AN=an[x];
}
}
J：$N$行$M$列的网格，4种插头，要求一些点必须有插头，而且插头要连成若干环。两个插头连接有一个价值$V_{i,j}$，现在要在使连接合法的情况下价值最大。$N,M\leq30$。
每个点$i$拆成两个点$i_1$和$i_2$，作为入点和出点。连边$(S,i_1)(i_2,T)$，如果这个点不是必选，再连$(i_1,i_2)$，两点$i,j$连边$(i_1,j_2,cost_{i,j})$，跑费用流即可。
#include<bits/stdc++.h>
#define N 2222
#define M 2222222
#define inf 1e9
#define CL(a) memset(a,0,sizeof a)
using namespace std;
struct CostFlow{
int h,t,tot,an,fl,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);tot=1;}
void add(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;
}
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]];
}
void cal(int S,int T,int n){
for(an=fl=0;spfa(S,T,n);end(S,T));
}
}G;
int n,m;
int C(int x,int y,int z){return z*n*m+x*m-m+y;}
int main(){
int S,T,Te,ca,E,i,j,x,y,z,an,v[33][33];
scanf("%d",&Te);
for(ca=1;ca<=Te;ca++){
printf("Case #%d: ",ca);
G.in();CL(v);
scanf("%d%d",&n,&m);S=n*m*2+1;T=S+1;
for(i=1;i<=n;i++)for(j=1;j<m;j++){
scanf("%d",&z);
if((i+j)&1)G.add(C(i,j,0),C(i,j+1,1),1,-z);
else G.add(C(i,j+1,0),C(i,j,1),1,-z);
}
for(i=1;i<n;i++)for(j=1;j<=m;j++){
scanf("%d",&z);
if((i+j)&1)G.add(C(i+1,j,0),C(i,j,1),1,-z);
else G.add(C(i,j,0),C(i+1,j,1),1,-z);
}
for(scanf("%d",&E);E--;)scanf("%d%d",&x,&y),v[x][y]=1;
for(i=1;i<=n;i++)for(j=1;j<=m;j++){
x=C(i,j,0);y=C(i,j,1);
G.add(S,x,1,0),G.add(y,T,1,0);
if(!v[i][j])G.add(x,y,1,0);
}
G.cal(S,T,T);
if(G.fl!=n*m)puts("Impossible");else printf("%d\n",-G.an);
}
}
HARD：IK
I：有$N$棵樱桃，每颗樱桃选择的概率都是$P$，每颗樱桃$1$元。有$M$种面值的钞票，每种钞票无限多，面值为$C_i$。最后选完樱桃后付费，多的钱不找零，问期望要多付多少钱。$N\leq 10^9,M\leq 100,C_i\leq10000$。
想法：明显可以对$C_1$取模跑一个最短路求出取得樱桃树$P$足够大时每个模数要多付多少钱，而$P$较小时可以暴力。就是求一个$\sum_{i=0}^NC(N,i)*P^i*(1-P)^{n-i}*V[i\ mod\ C_1]$。估计是个FFT吧，但不太会
K：地面上$N$个点，空间上一点$P$选一条准线，使得平面上有最多的点和$P$的连线与准线的夹角小于$\alpha$。$N\leq1000$。
想法：没有想法。退退火吧
评论 (0)
