A. Tree Orientation
树形DP,$f[i][j][k]$表示$i$的子树中有$j$个汇点,$i$往父亲的树边方向为$k$的方案数。
转移则需要另一个DP:$g[i][j][k]$表示考虑前$i$个儿子,子树中有$j$个汇点,$i$的出边个数是否是$0$的方案数。
时间复杂度$O(n^2)$。
#includeconst int N=1010,P=1000000007;int n,m,i,x,y,g[N],v[N<<1],nxt[N<<1],ed;int f[N][N][2];int size[N];int pre[N][2],now[N][2];inline void add(int x,int y){ v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}inline void up(int&a,int b){a=(a+b)%P;}void dfs(int x,int y){ for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs(v[i],x); size[x]=1; for(int i=0;i<=1;i++)for(int j=0;j<2;j++)pre[i][j]=0; pre[0][0]=1; for(int i=g[x];i;i=nxt[i]){ int u=v[i]; if(u==y)continue; for(int j=0;j<=size[x]+size[u];j++)for(int k=0;k<2;k++)now[j][k]=0; for(int j=0;j<=size[x];j++)for(int k=0;k<2;k++)if(pre[j][k]) for(int a=0;a<=size[u];a++)for(int b=0;b<2;b++)if(f[u][a][b]){ up(now[j+a][k||b],1LL*pre[j][k]*f[u][a][b]%P); } size[x]+=size[u]; for(int j=0;j<=size[x];j++)for(int k=0;k<2;k++)pre[j][k]=now[j][k]; } for(int j=0;j<=size[x];j++)for(int k=0;k<2;k++){ for(int o=0;o<2;o++){ if(x==1&&!o)continue; up(f[x][j+(!(k||!o))][o],pre[j][k]); } }}int main(){ scanf("%d%d",&n,&m); for(i=1;i
B. A Masterpiece
行列交换不影响答案,根据这一条构造即可。
#include#include #include #include #include #include #include #include
C. Auction
从$n$开始倒推出哪些数字是必胜/必败态,每次数字集合都可以压缩成一个区间,且最多推$O(\log n)$步。
#include#include #include #include #include #include #include #include
D. Deck Building
将过程倒过来,那么可以看作按$k$从大到小选取若干点,要求$s$是波浪形,且相邻两段$i\rightarrow j$的代价为$j$前面$s_i$到$s_j$之间的点数。
设$f[i][j]$表示考虑前$i$个点且第$i$个点必选,与上一个点的大小关系为$j$的方案数,$g[][]$表示代价之和,则转移可以用线段树打标记优化。
时间复杂度$O(n\log n)$。
#include#include using namespace std;typedef long long ll;const int N=100010,M=262150,P=1000000007;int n,m,i,j,k,x,b[N],f[N][2],g[N][2],ans,ma,mi;int bit[N];struct E{int s,k;}a[N];inline bool cmp(const E&a,const E&b){return a.k>b.k;}inline void modify(int x){for(;x<=n;x+=x&-x)bit[x]++;}inline int getpre(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}struct DS{int f[M],g[M],tag[M],v[M];inline void tag1(int x,int p){ tag[x]=(tag[x]+p)%P; v[x]=(v[x]+1LL*p*f[x])%P;}inline void pb(int x){ if(tag[x]){ tag1(x<<1,tag[x]); tag1(x<<1|1,tag[x]); tag[x]=0; }}inline void up(int x){ f[x]=(f[x<<1]+f[x<<1|1])%P; g[x]=(g[x<<1]+g[x<<1|1])%P; v[x]=(v[x<<1]+v[x<<1|1])%P;}void change(int x,int a,int b,int c,int d,int p){ if(c<=a&&b<=d){ tag1(x,p); return; } pb(x); int mid=(a+b)>>1; if(c<=mid)change(x<<1,a,mid,c,d,p); if(d>mid)change(x<<1|1,mid+1,b,c,d,p); up(x);}void addf(int x,int a,int b,int c,int p){ if(a==b){ f[x]=(f[x]+p)%P; v[x]=(v[x]+1LL*tag[x]*p)%P; return; } pb(x); int mid=(a+b)>>1; if(c<=mid)addf(x<<1,a,mid,c,p); else addf(x<<1|1,mid+1,b,c,p); up(x);}void addg(int x,int a,int b,int c,int p){ if(a==b){ g[x]=(g[x]+p)%P; v[x]=(v[x]+p)%P; return; } pb(x); int mid=(a+b)>>1; if(c<=mid)addg(x<<1,a,mid,c,p); else addg(x<<1|1,mid+1,b,c,p); up(x);}int askf(int x,int a,int b,int c,int d){ if(c<=a&&b<=d)return f[x]; pb(x); int mid=(a+b)>>1,t=0; if(c<=mid)t=askf(x<<1,a,mid,c,d); if(d>mid)t+=askf(x<<1|1,mid+1,b,c,d); return t%P;}int askv(int x,int a,int b,int c,int d){ if(c<=a&&b<=d)return v[x]; pb(x); int mid=(a+b)>>1,t=0; if(c<=mid)t=askv(x<<1,a,mid,c,d); if(d>mid)t+=askv(x<<1|1,mid+1,b,c,d); return t%P;}}g0,g1;int main(){ scanf("%d",&n);m=n+1; for(i=1;i<=n;i++)scanf("%d%d",&a[i].s,&a[i].k),b[i]=a[i].s; sort(a+1,a+n+1,cmp); sort(b+1,b+n+1); for(i=1;i<=n;i++)a[i].s=lower_bound(b+1,b+n+1,a[i].s)-b; ma=-N,mi=N; for(i=1;i<=n;i=j){ for(j=i;j<=n&&a[i].k==a[j].k;j++){ x=a[j].s; if(ma<=x)f[j][0]=1; if(mi>=x)f[j][1]=1; int cnt=g1.askf(1,0,m,x+1,m);//sum f (f[j][0]+=cnt)%=P; (g[j][0]+=g1.askv(1,0,m,x+1,m))%=P;//sum g+f*w g[j][0]=(g[j][0]-1LL*getpre(x)*cnt)%P; cnt=g0.askf(1,0,m,0,x-1);//sum f (f[j][1]+=cnt)%=P; (g[j][1]+=g0.askv(1,0,m,0,x-1))%=P;//sum g+f*w g[j][1]=(g[j][1]+1LL*getpre(x-1)*cnt)%P; } for(k=i;k
E. The secret of betting
$f[i][S]$表示考虑前$i$个人,$i$往前往后$k$个人的位置确定情况为$S$的方案数,只有恰好$k$个$1$的状态是有效的。
当$n$比较小时暴力转移,否则矩阵快速幂加速。
#include#include #include #include #include #include #include #include
F. Financial Reports
设$f[i][j][x][y]$表示考虑前$i$个位置,目前选取区间的状态为$j$(即未选,正在选,已选),区间外选取了$x$个数,区间内丢弃了$y$个数时,区间和的最大值。
注意输出方案时要特判交换不导致答案变优的情况。
时间复杂度$O(n)$。
#include#include using namespace std;typedef long long ll;typedef pair P;typedef pair W;typedef pair PI;const int N=100010;const ll inf=1LL<<60;int n,i,j,x,y;ll a[N];PI f[N][3][2][2],ans;//how many in and how many outinline void up(PI&t,ll a,int b,int c,int d,int e){ t=max(t,PI(a,W(P(b,c),P(d,e))));}int main(){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%lld",&a[i]); for(i=0;i<=n;i++)for(j=0;j<3;j++)for(x=0;x<2;x++)for(y=0;y<2;y++)f[i][j][x][y]=PI(-inf,W(P(0,0),P(0,0))); f[0][0][0][0]=PI(0,W(P(0,0),P(0,0))); for(i=1;i<=n;i++)for(x=0;x<2;x++)for(y=0;y<2;y++){ //consider i PI t=f[i-1][0][x][y]; int A=t.second.first.first; int B=t.second.first.second; int C=t.second.second.first; int D=t.second.second.second; if(t.first>-inf){ //still the stage up(f[i][0][x][y],t.first,A,B,C,D); //swap in if(!x)up(f[i][0][1][y],t.first+a[i],i,B,C,D); //new stage up(f[i][1][x][y],t.first+a[i],A,B,i,D); //swap out if(!y)up(f[i][1][x][1],t.first,A,i,i,D); } t=f[i-1][1][x][y]; A=t.second.first.first; B=t.second.first.second; C=t.second.second.first; D=t.second.second.second; if(t.first>-inf){ //still the stage up(f[i][1][x][y],t.first+a[i],A,B,C,i); //swap out if(!y)up(f[i][1][x][1],t.first,A,i,C,i); //new stage up(f[i][2][x][y],t.first,A,B,C,D); //swap in if(!x)up(f[i][2][1][y],t.first+a[i],i,B,C,D); } t=f[i-1][2][x][y]; A=t.second.first.first; B=t.second.first.second; C=t.second.second.first; D=t.second.second.second; if(t.first>-inf){ //still the stage up(f[i][2][x][y],t.first,A,B,C,D); //swap in if(!x)up(f[i][2][1][y],t.first+a[i],i,B,C,D); } } ans=max(f[n][1][1][1],f[n][2][1][1]); ans=max(ans,f[n][1][0][0]); ans=max(ans,f[n][2][0][0]); int A=ans.second.first.first; int B=ans.second.first.second; int C=ans.second.second.first; int D=ans.second.second.second; if(!A){ A=C,B=D; if(A==B){ if(B==1)B=2; else B=1; } } if(A>B)swap(A,B); printf("%lld\n%d %d",ans.first,A,B);}
G. Moore’s Law
从$n-1$的答案开始往最高位补$1$或者$2$,必然有解。
#include#include using namespace std;typedef long long ll;int n,i,len,f[1111111];ll m;bool check(){ ll t=0; for(int i=len;i;i--)t=(t*10+f[i])%m; return t==0;}int main(){ scanf("%d",&n); m=1LL<
H. Plagiarism
$f[i][j][x][y]$表示考虑$a$长度为$i$的前缀以及$b$长度为$j$的前缀,$a$和$b$正在匹配的部分长度分别为$x$和$y$时的最小串长。
时间复杂度$O(n^4)$。
#include#include #include using namespace std;const int N=110,inf=10000000;int K,n,m,o,i,j,k,x,y,t,f[2][N][N][N],ans;char a[N],b[N];inline void up(int&x,int y){ x>y?(x=y):0;}int main(){ scanf("%d%s%s",&K,a+1,b+1); n=strlen(a+1); m=strlen(b+1); for(j=0;j<=m;j++)for(x=0;x<=n;x++)for(y=0;y<=m;y++)f[0][j][x][y]=inf; f[0][0][0][0]=0; for(i=o=0;i<=n;i++,o^=1){ for(j=0;j<=m;j++)for(x=0;x<=n;x++)for(y=0;y<=m;y++)f[o^1][j][x][y]=inf; for(j=0;j<=m;j++)for(x=n;~x;x--)for(y=m;~y;y--)if(f[o][j][x][y] =K)up(f[o][j][0][y],t); if(y>=K)up(f[o][j][x][0],t); if(x>=K&&y>=K)up(f[o][j][0][0],t); t++; if(i
I. Number builder
将$1$和$2$交替放是最优的。
#include#include #include #include #include #include #include #include
J. Find a triangle
首先二分出三角形的包围盒,然后确定哪个顶点是三角形的顶点,之后二分即可。