[关闭]
@ysner 2018-04-12T14:06:45.000000Z 字数 8870 阅读 1497

CJ考试题集锦

考试


4.9T2()

给一颗有负边的树,询问在经过k次割边与任意连上边权为0的边后,链上边权最大和。

此题甚火,正解不敢想象,于是yy一波部分分

10pts算法()

树的直径

20pts算法()

枚举割哪条边,分别给割后产生的两颗树算直径,加起来即可
送分结束

35pts算法()

看来是分类讨论啊,然而并不知道应如何讨论(请求大佬的指教QAQ)

60pts算法()

分类讨论到此为止啦,显然只有树形DP才做的动。。。
任意连上边权为0的边???这是什么操作???这边有意义吗???
看来没有啊,那就把它忽略掉吧。
于是,问题就变成了最大化条不相交的链的链上边权总和
经典树形DP。
设状态表示以u为根的子树(且u的度数为)中,选k条链的最优解。
顺便加个大前提:强制每个点对应其父边
我们可以列出几个状态转移方程式:()()

答案就是

  1. il void dfs(re int u,re int fa)
  2. {
  3. f[0][u][0]=f[1][u][0]=f[2][u][0]=0;
  4. for(re int i=h[u];i+1;i=e[i].next)
  5. {
  6. re int v=e[i].to;
  7. if(v==fa) continue;
  8. dfs(v,u);
  9. fq(j,k,1)
  10. {
  11. f[1][u][j]=max(f[1][u][j],f[0][u][j]+f[1][v][0]+e[i].w);
  12. fq(o,j-1,0)
  13. {
  14. f[0][u][j]=max(f[0][u][j],f[0][u][o]+f[0][v][j-o]);
  15. f[1][u][j]=max(f[1][u][j],max(f[0][u][o]+f[1][v][j-o]+e[i].w,f[1][u][o]+f[0][v][j-o]));
  16. f[2][u][j]=max(f[2][u][j],max(f[1][u][o]+f[1][v][j-o-1]+e[i].w,f[2][u][o]+f[0][v][j-o]));
  17. }
  18. }
  19. f[1][u][0]=max(f[1][u][0],f[1][v][0]+e[i].w);
  20. }
  21. f[0][u][1]=max(0,f[0][u][1]);
  22. fp(i,1,k) f[0][u][i]=max(f[0][u][i],max(f[1][u][i-1],f[2][u][i]));
  23. }
  24. int main()
  25. {
  26. memset(h,-1,sizeof(h));
  27. n=gi();k=gi();
  28. fp(i,1,n-1)
  29. {
  30. re int u=gi(),v=gi(),w=gi();
  31. add(u,v,w);add(v,u,w);
  32. }
  33. memset(f,-63,sizeof(f));
  34. k++;dfs(1,0);
  35. printf("%d\n",f[0][1][k]);
  36. return 0;
  37. }

100pts算法()

辛辛苦苦想出的树形DP废了。。。
假如你是个秒出60pts的巨佬,即将AK之时闲来无事输出选了k条链的最优解,你就会发现:最优解数组是一个上凸函数!!!
这个函数以k的值为x轴,以最优解为y轴。
我们想找到的点,就是
于是考虑用一条直线去切这个函数,由此我们可以枚举一个斜率,用60分的DP来算出切点。(这好像是个套路?)
算出切点后,我们可以根据切点在k的左右,来缩小斜率范围。
二分?于是复杂度降到,皆大欢喜。

  1. struct dat
  2. {
  3. ll x,y;
  4. il bool operator < (const dat &o) const {return x==o.x? y>o.y : x<o.x;}
  5. il dat operator + (const dat &o) const {return (dat){x+o.x,y+o.y};}
  6. il dat operator + (re int o) {return (dat){x+o,y};}
  7. }dp[3][N];
  8. il dat upd(dat o){return (dat){o.x-mid,o.y+1};}
  9. il void dfs(re int u,re int fa)
  10. {
  11. dp[2][u]=max(dp[2][u],(dat){-mid,1});
  12. for(re int i=h[u];i+1;i=e[i].next)
  13. {
  14. re int v=e[i].to;
  15. if(v==fa) continue;
  16. dfs(v,u);
  17. dp[2][u]=max(dp[2][u]+dp[0][v],upd(dp[1][u]+dp[1][v]+e[i].w));
  18. dp[1][u]=max(dp[1][u]+dp[0][v],dp[0][u]+dp[1][v]+e[i].w);
  19. dp[0][u]=dp[0][u]+dp[0][v];
  20. }
  21. dp[0][u]=max(dp[0][u],max(upd(dp[1][u]),dp[2][u]));
  22. }
  23. int main()
  24. {
  25. memset(h,-1,sizeof(h));
  26. n=gi();k=gi();++k;
  27. fp(i,1,n-1)
  28. {
  29. re int u=gi(),v=gi(),w=gi();tot+=abs(w);
  30. add(u,v,w);add(v,u,w);
  31. }
  32. l=-tot,r=tot;
  33. while(l<=r)
  34. {
  35. mid=l+r>>1;
  36. memset(dp,0,sizeof(dp));
  37. dfs(1,0);
  38. if(dp[0][1].y<=k) r=mid-1;
  39. else l=mid+1;
  40. }
  41. memset(dp,0,sizeof(dp));
  42. mid=l;dfs(1,0);
  43. printf("%lld\n",l*k+dp[0][1].x);
  44. return 0;
  45. }

4.7T2()

一个 n ∗ m 的网格中,任意相邻两格点之间有 p 的概率没有边,1 − p 的概率有一条边。询问(1, 1) 与 (n, m) 连通的概率。
  1. struct Data{
  2. int x, y;
  3. double p;
  4. IL int operator <(RG Data B) const{
  5. if(x != B.x) return x < B.x;
  6. if(y != B.y) return y < B.y;
  7. return p < B.p;
  8. }
  9. };
  10. map <Data, double> mp;
  11. IL int Find(RG int x){
  12. return fa[x] == x ? x : Find(fa[x]);
  13. }
  14. IL void Dfs(RG int x, RG double s){
  15. if(Find(num) == Find(1)){
  16. ans += s;
  17. return;
  18. }
  19. if(x > cnt) return;
  20. RG int fx = Find(edge[x].u), fy = Find(edge[x].v), tmp = fa[fx];
  21. if(fx != fy) fa[fx] = fy;
  22. Dfs(x + 1, s * (1.0 - p));
  23. if(fx != fy) fa[fx] = tmp;
  24. Dfs(x + 1, s * p);
  25. }
  26. int main(RG int argc, RG char *argv[]){
  27. File("socialman");
  28. for(Input(T); T; --T){
  29. Input(n), Input(m), scanf("%lf", &p);
  30. ans = mp[(Data){n, m, p}], cnt = num = 0;
  31. if(ans != 0){
  32. printf("%.10lf\n", ans - 1);
  33. continue;
  34. }
  35. for(RG int i = 1; i <= n; ++i)
  36. for(RG int j = 1; j <= m; ++j)
  37. id[i][j] = ++num;
  38. for(RG int i = 1; i <= n; ++i)
  39. for(RG int j = 1; j <= m; ++j){
  40. if(i < n) edge[++cnt] = (Edge){id[i][j], id[i + 1][j]};
  41. if(j < m) edge[++cnt] = (Edge){id[i][j], id[i][j + 1]};
  42. }
  43. for(RG int i = 1; i <= num; ++i) fa[i] = i;
  44. Dfs(1, 1);
  45. mp[(Data){n, m, p}] = ans + 1;
  46. printf("%.10lf\n", ans);
  47. }
  48. return 0;
  49. }

4.11T1(括号序列再战猪猪侠)

题面

已知一个长度为的括号序列,给了你个信息,第个信息形如, ,表示 个左括号对应的右括号个左括号对应的右括号的前面,要你还原这个序列。(给出的限制不一定合法

解析

考虑区间DP。
我们可以设表示为将这一段区间构成合法括号序列的方案数。
其中表示第个左括号,同理。

如何转移?

看看括号序列的定义(均代表一个合法的括号序列)

如何快速判断限制条件?

可以用表示限制条件。
然后像处理矩阵一样维护二维前缀和。
这样就可以查询限制条件了。
举个栗子,要查询中有没有要求在前面的点,只需要查询一下左上角为,右下角为中的矩阵有没有值即可。
横坐标代表在前面那个区间,纵坐标代表在后面那个区间(就像你一开始赋值时的意义一样)。
于是,把两维交换一下就可以表示XX在XX后面。

如何处理不合法条件?

两种情况:

  1. il int check(re int A,re int B,re int C,re int D)
  2. {
  3. return a[C][D]-a[A-1][D]-a[C][B-1]+a[A-1][B-1];
  4. }
  5. il ll DP()
  6. {
  7. fp(i,1,n)
  8. if(check(i,i,i,i)) return 0;
  9. memset(dp,0,sizeof(dp));
  10. fq(i,n,1)
  11. {
  12. dp[i][i]=1;
  13. fp(j,i+1,n)
  14. {
  15. if(!check(i,i+1,i,j)) (dp[i][j]+=dp[i+1][j])%=mod;
  16. if(!check(i+1,i,j,i)) (dp[i][j]+=dp[i+1][j])%=mod;
  17. fp(k,i+1,j-1)
  18. if(!check(i,i+1,i,k)&&!check(k+1,i,j,i)&&!check(k+1,i+1,j,k))
  19. (dp[i][j]+=dp[i+1][k]*dp[k+1][j]%mod)%=mod;
  20. }
  21. }
  22. return dp[1][n];
  23. }
  24. int main()
  25. {
  26. T=gi();
  27. while(T--)
  28. {
  29. memset(a,0,sizeof(a));
  30. n=gi();m=gi();
  31. fp(i,1,m)
  32. {
  33. re int u=gi(),v=gi();
  34. a[u][v]=1;
  35. }
  36. fp(i,1,n)
  37. fp(j,1,n)
  38. a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
  39. DP();
  40. printf("%lld\n",DP());
  41. }
  42. fclose(stdin);
  43. fclose(stdout);
  44. return 0;
  45. }

4.11T3

题面

你要用个积木拼成一个塔,第个积木长度是
给定,积木能搭在积木上面,当且仅当
求合法的搭积木方案数。

解析

45pts算法

直接状压DP,状态为表示状态下最底下为第个积木的方案数。

100pts算法

我们都把题目想复杂了
需要一个很显然的性质:假设一个塔合法,去掉他的最长的积木后还是合法的。
于是,我们设表示选前块积木搭塔的方案数。
sort一边,从枚到,看他能加到以哪些积木结尾的塔中。

  1. int main()
  2. {
  3. n=gi();d=gi();
  4. fp(i,1,n) a[i]=gi();
  5. sort(a+1,a+1+n);
  6. dp[1]=1;
  7. for(re int i=2,pos=1;i<=n;i++)
  8. {
  9. while(pos<i&&a[i]-a[pos]>d) ++pos;
  10. dp[i]=dp[i-1]*(i-pos+1)%mod;
  11. }
  12. printf("%lld\n",dp[n]);
  13. return 0;
  14. }

4.11T2

题面

个人来参加比赛,要求进行恰好轮,要你规划比赛方式。
允许出现轮后有多人胜利的情况,即我们并不需要决出冠军。
一轮比赛可以这么理解:假设当前还剩个人,我们把个人分成若
干份(强制连续分组),但不允许某一份只有一个人(因为不能不战而胜),然后每一份的人
就会进行比赛,最后只会留下一个人晋级。
那么给定,,要你求合法的比赛过程的方案数。

解析

40pts算法

预处理表示个人分为组的方案数,枚举当前分为几组,直接暴搜即可。

  1. cf[0]=1;
  2. fp(i,1,n) cf[i]=(cf[i-1]<<1)%mod;
  3. fp(i,2,n) a[i][1]=1;
  4. fp(i,4,n) a[i][2]=i-3;
  5. fp(i,3,n/2)
  6. fp(j,4,n)
  7. fp(k,2,j-2)
  8. (a[j][i]+=a[j-k][i-1])%=mod;

Update:
我原来打的是的预处理,现在来普及一下
实际表示将拆分为个大于等于的整数的方案数。
转移考虑其是 与前面的合并 还是新建一组

70pts算法

加个记忆化
不过我要吐槽一下,我连暴搜都不会
某智障原来考场爆零写法

  1. il ll dfs(re ll n,re ll k,re ll tot)
  2. {
  3. if(n<cf[k]) return 0;
  4. if(!k||n==cf[k]) return tot;
  5. if(dp[n][k]) return dp[n][k];
  6. re ll res=0;
  7. fp(i,1,n/2)
  8. (res+=dfs(i,k-1,tot*a[n][i]%mod))%=mod;
  9. return dp[n][k]=res;
  10. }

递归的本质是将当前问题化为更小的子问题,返回的也是子问题结果。
结果我在最小的子问题返回tot???
如dfs返回值,我们应该在最小问题下返回,然后只在对应大问题层面乘上值,为了合并答案。
如不返回,才可以一直乘到底,为了统计答案。

  1. il ll dfs(re ll n,re ll k)
  2. {
  3. if(n<cf[k]) return 0;
  4. if(!k||n==cf[k]) return 1;
  5. if(dp[n][k]) return dp[n][k];
  6. re ll res=0;
  7. fp(i,1,n/2)
  8. (res+=a[n][i]*dfs(i,k-1)%mod)%=mod;
  9. return dp[n][k]=res;
  10. }

100pts算法

发现很大,很小,因此,我们考虑n递增,进行矩阵加速。
假设当前加入人,对于之前的个人
考虑第个人参加的每组比赛,假设已经超过了两个人则将这组比赛设为,否则则是
那么,第个人添加到这组序列中,它能够改变一些比赛的状态
可以添加到从第一轮开始,连续的超过两个人对决中的任意一个,此时相当于后面的若干轮的状态不变
也可以新开一组,使得最低那轮的0可以变成1
这样子我们发现状态是的,可以矩阵快速幂转移。
我还是很懵逼啊

  1. struct Matrix
  2. {
  3. int s[100][100];
  4. void clear(){memset(s,0,sizeof(s));}
  5. int * operator [](int x){return a[x];}
  6. void init(){clear();for(int i=0;i<=N;++i)s[i][i]=1;}
  7. }A,B;
  8. Matrix operator*(Matrix a,Matrix b)
  9. {
  10. Matrix c;c.clear();
  11. for(int i=0;i<=N;++i)
  12. for(int j=0;j<=N;++j)
  13. for(int k=0;k<=N;++k)
  14. c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%MOD;
  15. return c;
  16. }
  17. Matrix fpow(Matrix a,ll b)
  18. {
  19. Matrix s;s.init();
  20. while(b){if(b&1)s=s*a;a=a*a;b>>=1ll;}
  21. return s;
  22. }
  23. int main()
  24. {
  25. cin>>n>>m;N=1<<m;--N;
  26. A.s[0][0]=1;
  27. for(int i=0;i<=N;++i)
  28. for(int j=0;j<m;++j)
  29. {
  30. int x=i|(1<<j);x^=(1<<j)-1;
  31. B.s[i][x]++;
  32. if(!(i&(1<<j)))break;
  33. }
  34. B.s[N][0]+=1;
  35. B=fpow(B,n-1);A=A*B;
  36. printf("%d\n",A.s[0][N]);
  37. return 0;
  38. }

4.7T1贪婪人

题面

列的网络中,每个格子有权值。要从最左上角的格子走到最右下角的格子,每次只能向下或者向右行走。一条合法路径的权值为路过所有格子的权值之和。
每次会选择权值较大的格子走过去。如果右侧与下侧格子权值相同,则会向右走。如果已经走到了网络的下边界或者右边界,则会向终点方向行走。
已知网络左上角格子权值为,其他格子的权值范围在中,都为整数。求有多少种不同的网络,走过的路径权值恰好为

解析

考场直接爆零,我果然好菜啊

如何设状态

表示在的网格中路径权值为的方案数

边界

如何转移

  1. il ll dfs(re int x,re int y,re int z)
  2. {
  3. if(~f[x][y][z]) return f[x][y][z];re ll res=0;
  4. if(x==n)
  5. {
  6. fp(i,z,S)
  7. (res+=dfs(x,y+1,i)*c[n-1])%=mod;
  8. return f[x][y][z]=res;
  9. }
  10. if(y==m)
  11. {
  12. fp(i,z,S)
  13. (res+=dfs(x+1,y,i)*c[m-1])%=mod;
  14. return f[x][y][z]=res;
  15. }
  16. fp(i,z,S)
  17. (res+=dfs(x,y+1,i)*c[x-1]%mod*(i-z+1)%mod*c[mod-2]%mod)%=mod;
  18. fp(i,z+1,S)
  19. (res+=dfs(x+1,y,i)*c[y-1]%mod*(i-z)%mod*c[mod-2]%mod)%=mod;
  20. return f[x][y][z]=res;
  21. }
  22. int main()
  23. {
  24. n=gi();m=gi();S=gi();
  25. c[0]=1;fp(i,1,mod) c[i]=c[i-1]*(S+1)%mod;
  26. memset(f,-1,sizeof(f));
  27. memset(f[n][m],0,sizeof(f[n][m]));
  28. f[n][m][S]=1;
  29. printf("%lld\n",dfs(1,1,0));
  30. return 0;
  31. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注