[关闭]
@CQUPTacm 2018-11-18T08:04:37.000000Z 字数 9010 阅读 2003

重庆市第九届大学生程序设计大赛重邮赛区决赛 题解

题解

题解的顺序按照难度(出题人心中的)排列

G 双倍的快乐

    这道题看起来虽然(不)像一道博弈论，但是实际上它(确实)不是博弈论。一共N*M个落子的地方，全下完才结束，所以其实谁赢之和N*M的奇偶性有关。除非N和M都是奇数，不然N*M一定是偶数。所以只需要判断N和M各自的奇偶性，这只需要判断N和M的最后一位的奇偶性就行了，所以N和M的数据范围只是吓唬人的。
    时间复杂度o(T*logN)，空间复杂度o(logN)。

代码

  1. //C++
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. char s1[105],s2[105];
  6. int main()
  7. {
  8.     int t,l1,l2;
  9.     scanf("%d",&t);
  10.     while(t--)
  11.     {
  12.         scanf("%s%s",s1,s2);
  13.         l1=strlen(s1);
  14.         l2=strlen(s2);
  15.         if(((s1[l1-1]-'0')%2)==1 &&((s2[l2-1]-'0')%2)==1)
  16.             printf("Qm win\n");
  17.         else
  18.             printf("Oqm win\n");
  19.     }
  20.     return 0;
  21. }

E 节奏大师

    根据题目的意思，对于每个音符，在二维数组中把对应那一列的起始行到结束行标记为'X'即可。最后输出整个二维数组。
    时间复杂度o(N*L)，空间复杂度o(10*L)。

代码

  1. //C++
  2. #include<cstdio>
  3. using namespace std;
  4. char ans[105][10];
  5. char c[6];
  6. int main()
  7. {
  8.     int l,n,s,e;
  9.     scanf("%d%d",&l,&n);
  10.     for(int i=1;i<=l;i++)
  11.         for(int j=1;j<=7;j++)
  12.             ans[i][j]='X';
  13.     for(int i=1;i<=n;i++)
  14.     {
  15.         scanf("%s",c);
  16.         scanf("%d%d",&s,&e);
  17.         for(int j=s;j<=e;j++)
  18.             ans[j][c[0]-'A'+1]='O';
  19.     }
  20.     for(int i=1;i<=l;i++)
  21.     {
  22.         for(int j=1;j<=7;j++)
  23.             printf("%c",ans[i][j]);
  24.         printf("\n");
  25.     }
  26.     return 0;
  27. }

B PUBG PARACHUTE SIMULATOR

    第一道英文题，其实还是挺简单的。
    题目比较短，题意我就不翻译了。
    本质上其实就是问N个点出现在以God jian为起点的多少种射线上。枚举点，判断从起点到当前点的射线上是否之前已经有点了，如果没有答案就加一并且标记一下这条射线。一条射线其实可以用这条射线方向上的单位向量来表示，但是单位向量可能是由两个小数组成的。。。所以我们不妨将从起点到当前点的向量看成一个分数，同过约分来保证射线表示的唯一性。注意向量平行某个坐标轴的特殊情况即可。这样我们通过两个整数来表示一条射线，就可以用二维数组记录每条射线上之前有没有点。
    注意：起点到某个敌人的向量，可能由-2000~2000范围的数组成，而下标又不能为负的，所以我们开数组要开4000*4000的。
    时间复杂度o(N)，空间复杂度o(4000^2)。

代码

  1. //C++
  2. #include<cstdio>
  3. #include<cstdlib>
  4. using namespace std;
  5. bool used[4005][4005];
  6. int gcd(int a,int b)
  7. {
  8.     if(b==0)
  9.         return a;
  10.     if(a%b==0)
  11.         return b;
  12.     else
  13.         return gcd(b,a%b);
  14. }
  15. int main()
  16. {
  17.     int x,y,xi,yi,n;
  18.     int ans=0;
  19.     int g;
  20.     scanf("%d%d%d",&x,&y,&n);
  21.     for(int i=1;i<=n;i++)
  22.     {
  23.         scanf("%d%d",&xi,&yi);
  24.         xi=xi-x;
  25.         yi=yi-y;
  26.         g=gcd(abs(xi),abs(yi));
  27.         xi=xi/g;
  28.         yi=yi/g;
  29.         if(used[xi+2001][yi+2001]!=1)
  30.         {
  31.             used[xi+2001][yi+2001]=1;
  32.             ans++;
  33.         }
  34.     }
  35.     printf("%d\n",ans);
  36.     return 0;
  37. }

A 榜单

    相信通过这道题，各位对于ACM的比赛规则有了更深刻的理解(滑稽)。
    先扫一遍提交记录，确定每个队伍每道题第一次AC的时间。再扫第二遍提交记录，把每个队伍每道题第一次AC前的罚时计算出来。然后计算出每个队的正确题数和罚时，最后根据题数和罚时对队伍进行排名并从前到后输出题数大于等于1的有效队伍。排序的部分其实用N^2的排序也可以(大概)。
    时间复杂度o(T*(M*N*logN))，空间复杂度o(M+N)。

代码

  1. //C++
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. struct Node
  6. {
  7.     int no,nums,penalty;
  8.     bool friend operator <(Node x1,Node x2)
  9.     {
  10.         if(x1.nums==x2.nums)
  11.             return x1.penalty<x2.penalty;
  12.         else
  13.             return x1.nums>x2.nums;
  14.     }
  15. }teams[305];
  16. int last[305][10],pen[305][10];
  17. char s[20];
  18. int problem[20005],team[20005],tm[20005];
  19. bool statu[20005];
  20. int main()
  21. {
  22.     int t,n,m;
  23.     scanf("%d",&t);
  24.     while(t--)
  25.     {
  26.         scanf("%d%d",&n,&m);
  27.         for(int i=1;i<=n;i++)
  28.         {
  29.             for(int j=0;j<8;j++)
  30.             {
  31.                 last[i][j]=241;
  32.                 pen[i][j]=0;
  33.             }
  34.         }
  35.         for(int i=1;i<=m;i++)
  36.         {
  37.             scanf("%s",s);
  38.             problem[i]=s[0]-'A';
  39.             scanf("%d",&team[i]);
  40.             scanf("%s",s);
  41.             if(s[0]=='A')
  42.                 statu[i]=1;
  43.             else
  44.             {
  45.                 statu[i]=0;
  46.                 scanf("%s",s);
  47.                 if(s[0]=='L')
  48.                     scanf("%s",s);
  49.             }
  50.             scanf("%d",&tm[i]);
  51.             if(statu[i]==1)
  52.                 last[team[i]][problem[i]]=min(last[team[i]][problem[i]],tm[i]);
  53.         }
  54.         for(int i=1;i<=m;i++)
  55.         {
  56.             if(statu[i]==0 && last[team[i]][problem[i]]!=241 && tm[i]<last[team[i]][problem[i]])
  57.                 pen[team[i]][problem[i]]+=20;
  58.         }
  59.         for(int i=1;i<=n;i++)
  60.         {
  61.             teams[i].no=i;
  62.             teams[i].nums=0;
  63.             teams[i].penalty=0;
  64.             for(int j=0;j<8;j++)
  65.             {
  66.                 if(last[i][j]!=241)
  67.                 {
  68.                     teams[i].nums++;
  69.                     teams[i].penalty+=last[i][j]+pen[i][j];
  70.                 }
  71.             }
  72.         }
  73.         sort(teams+1,teams+1+n);
  74.         for(int i=1;i<=n;i++)
  75.         {
  76.             if(teams[i].nums!=0)
  77.                 printf("%d %d %d\n",teams[i].no,teams[i].nums,teams[i].penalty);
  78.         }
  79.     }
  80.     return 0;
  81. }

D 天选之人

    本题目改编自现实生活。欧吃矛！
    这道题是一个比较典型的动态规划。dp[i][j]表示抽了i次之后抽出j张SSR的概率，状态转移方程:
    dp[i][j]=dp[i-1][j-1]*(y-j+1)/(x-j+1)+dp[i-1][j]*(x-y)/(x-j)
    分别表示前i-1次抽卡只抽到了j-1张SSR，这次抽卡又抽到了一张；和前i-1次已经抽到了j张SSR，这次抽卡凉了。
    特殊处理j为0的情况。j为0相当于i次抽卡全部凉了的情况(非酋附体)。
    注意：一次十连等于十次抽卡！所以抽卡次数要乘10。
    时间复杂度o(10*N*X)，空间复杂度o(10*N*X)。

代码

  1. //C++
  2. #include<cstdio>
  3. using namespace std;
  4. double dp[1005][1005];
  5. int main()
  6. {
  7.     int n,x,y;
  8.     double ans=0;
  9.     scanf("%d%d%d",&x,&y,&n);
  10.     n=n*10;
  11.     dp[0][0]=1;
  12.     for(int i=1;i<=n;i++)
  13.     {
  14.         dp[i][0]=(dp[i-1][0]*(x-y))/x;
  15.         for(int j=1;j<=y;j++)
  16.             dp[i][j]=(dp[i-1][j-1]*(y-j+1))/(x-j+1)+(dp[i-1][j]*(x-y))/(x-j);
  17.     }
  18.     for(int i=1;i<=y;i++)
  19.         ans+=i*dp[n][i];
  20.     printf("%.6f\n",ans);
  21.     return 0;
  22. }

C Family of Magic Pandas

    从这题开始终于有一些难度了。
    简单抽象之后，题目其实是这样的：给一颗以1为根的有N个点的树，有M个操作，每个操作让某个点的值加x，并且在他的子树中根据距离递减地加上x-1、x-2、...
    一个点的能力值之和两个因素有关：他从父节点继承的能力值和他自身觉醒的新能力的能力值。而他从父节点那里继承多少能力值又和两个因素有关：父节点的总能力值和父节点的能力数量。因为每拥有一种能力，继承的时候就要少一点能力值。
    于是我们的目标就是将操作处理成每个节点自己会觉醒多少能力值以及每个点拥有多少项能力。前者很好维护，后者我们可以用类似差分处理区间加法的思路，当一个点觉醒一种能力时，他的子树都拥有这种能力，除了距离太远的孙子的孙子的孙子的孙子...我们找到这种能力会在多少代的时候消失，然后打上标记，处理到这一代的时候做出相应的处理即可。为了保证这些变动只对子树内的点起作用，在退出当前节点的时候要把所有的影响都恢复，这个过程要注意顺序。
    注意：能力值可能非常大，所以可能会有能力传到最后都不会消失。
    时间复杂度o(N+M)，空间复杂度o(N+M)。

代码

  1. //C++
  2. #include<cstdio>
  3. #include<vector>
  4. using namespace std;
  5. int dis[200005];
  6. vector <int> vec[200005];
  7. vector <int> del[200005];
  8. int nowdel[200005],n,nownum;
  9. long long add[200005];
  10. long long nowans;
  11. long long ans[200005];
  12. void dfs1(int x,int y)
  13. {
  14.     dis[x]=y;
  15.     for(int i=0;i<vec[x].size();i++)
  16.     {
  17.         if(dis[vec[x][i]]==0)
  18.             dfs1(vec[x][i],y+1);
  19.     }
  20. }
  21. void dfs2(int x)
  22. {
  23.     nowans-=nownum;
  24.     nownum-=nowdel[dis[x]];
  25.     nowans+=add[x];
  26.     nownum+=del[x].size();
  27.     ans[x]=nowans;
  28.     for(int i=0;i<del[x].size();i++)
  29.     {
  30.         if(del[x][i]<=n)
  31.             nowdel[del[x][i]]++;
  32.     }
  33.     for(int i=0;i<vec[x].size();i++)
  34.     {
  35.         if(dis[vec[x][i]]>dis[x])
  36.             dfs2(vec[x][i]);
  37.     }
  38.     for(int i=0;i<del[x].size();i++)
  39.     {
  40.         if(del[x][i]<=n)
  41.             nowdel[del[x][i]]--;
  42.     }
  43.     nownum-=del[x].size();
  44.     nowans-=add[x];
  45.     nownum+=nowdel[dis[x]];
  46.     nowans+=nownum;
  47. }
  48. int main()
  49. {
  50.     int m,u,v;
  51.     int a,x;
  52.     scanf("%d%d",&n,&m);
  53.     for(int i=1;i<n;i++)
  54.     {
  55.         scanf("%d%d",&u,&v);
  56.         vec[u].push_back(v);
  57.         vec[v].push_back(u);
  58.     }
  59.     dfs1(1,1);
  60.     while(m--)
  61.     {
  62.         scanf("%d%d",&a,&x);
  63.         add[a]+=x;
  64.         del[a].push_back(dis[a]+x);
  65.     }
  66.     nowans=0;
  67.     nownum=0;
  68.     dfs2(1);
  69.     for(int i=1;i<n;i++)
  70.         printf("%lld ",ans[i]);
  71.     printf("%lld\n",ans[n]);
  72.     return 0;
  73. }

H 键王之键

    键王之键：想当年我也是cf的div1E，没想到现在连防ak都不是了。。。
    这题据说正解是WQS二分优化的动态规划，但是出题人不会，而且据说正解跑的没有这个std快。。。
    这里提供的是一种最大费用最大流的解法。建图如下：源点到卫宫星宇连一条容量为A费用为0的边，源点到桐谷蜀清连一条容量为B费用为0的边，卫宫星宇到第i把子键连一条容量为1费用为Pi的边，桐谷蜀清到第i把子键连一条容量为1费用为Qi的边，第i把子键到汇点连一条容量为1费用为0的边，第i把子键再连一条容量为1费用为-Pi*Qi的边。
    跑出的最大费用就是答案。
    本题其实更推荐把小数都转成整数来完成。
    本题原始数据范围N和A、B都是2000的，但是学校的老爷机跑不动，就砍成1000了。。。
    时间复杂度o(能过)，空间复杂度o(N)。

代码

  1. //C++
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<queue>
  6. #include<cstring>
  7. using namespace std;
  8. typedef double LD;
  9. const int MAXN=2010,MAXM=20010;
  10. const LD inf=1e15,eps=1e-8;
  11. struct edge
  12. {
  13.     int adj,flow,next;
  14.     LD cost;
  15. }e[MAXM];
  16. int n,st,ed,a,b,tot,head[MAXN],mark[MAXN],vis[MAXN];
  17. double p[MAXN],q[MAXN];
  18. LD dist[MAXN];
  19. queue<int> que;
  20. inline void add_edge(int u,int v,int f,LD c)
  21. {
  22.     e[tot].adj=v,e[tot].flow=f,e[tot].cost=c,e[tot].next=head[u];
  23.     head[u]=tot++;
  24.     e[tot].adj=u,e[tot].flow=0,e[tot].cost=-c,e[tot].next=head[v];
  25.     head[v]=tot++;
  26. }
  27. inline bool SPFA()
  28. {
  29.     fill(dist,dist+n,-inf);
  30.     que.push(st),dist[st]=0,vis[st]=true,mark[st]=-1;
  31.     while(!que.empty())
  32.     {
  33.         int u=que.front();
  34.         que.pop();
  35.         vis[u]=false;
  36.         for(int i=head[u];~i;i=e[i].next)
  37.         {
  38.             int &v=e[i].adj;
  39.             if(e[i].flow&&dist[u]+e[i].cost>dist[v]+eps)
  40.             {
  41.                 dist[v]=dist[u]+e[i].cost,mark[v]=i;
  42.                 if(!vis[v])que.push(v),vis[v]=true;
  43.             }
  44.         }
  45.     }
  46.     return dist[ed]>-inf;
  47. }
  48. inline double solve()
  49. {
  50.     LD ret=0;
  51.     while(SPFA())
  52.     {
  53.         int delta=~0u>>1;
  54.         for(int i=mark[ed];~i;i=mark[e[i^1].adj])delta=min(delta,e[i].flow);
  55.         for(int i=mark[ed];~i;i=mark[e[i^1].adj])
  56.         {
  57.             ret+=delta*e[i].cost;
  58.             e[i].flow-=delta,e[i^1].flow+=delta;
  59.         }
  60.     }
  61.     return ret;
  62. }
  63. inline void init()
  64. {
  65.     memset(head,-1,sizeof(head));
  66.     scanf("%d%d%d",&n,&a,&b);
  67.     for(int i=1;i<=n;i++)scanf("%lf",&p[i]);
  68.     for(int i=1;i<=n;i++)scanf("%lf",&q[i]);
  69.     st=0,ed=n+1;
  70.     add_edge(st,n+2,a,0);
  71.     add_edge(st,n+3,b,0);
  72.     for(int i=1;i<=n;i++)
  73.     {
  74.         add_edge(n+2,i,1,p[i]);
  75.         add_edge(n+3,i,1,q[i]);
  76.         add_edge(i,ed,1,0);
  77.         add_edge(i,ed,1,-p[i]*q[i]);
  78.     }
  79.     n+=4;
  80. }
  81. int main()
  82. {
  83.     init();
  84.     printf("%.6f\n",solve());
  85.     return 0;
  86. }

F 为CC打call

    我也没想到一道笔试题被我改成了防ak。。。
    先让拿颜色一的n1名粉丝站好不动，他们把这一排分割成n1+1个部分，中间的n1-1个部分必须填充其他两种颜色的粉丝，两边的两个部分可以填充其他颜色粉丝也可以不填充。
    一个部分有三种情况：颜色二比颜色三多一、颜色三比颜色二多一、颜色二和颜色三一样多。枚举有i个部分颜色二比颜色三多一，可以计算出有n3-(n2-i)个部分颜色三比颜色二多一。再枚举左右两边的是否放置刚才说的两种情况的部分，剩下的部分从n1-1个部分中选。之后，可以得到至少有l个部分需要放置，至多有r个部分还能放置，可以证明l和r的差距至多为2，即最多三种情况。枚举这三种情况，各填上一个颜色二+颜色三的最小组合，此时组合有两种顺序。剩下的组合可以随意放入刚才有放置东西的任何一个部分，用隔板法可以计算方案数。
    过程中需要用到的2的幂对1000000007取模和组合数对1000000007取模可以预处理，其中组合数的部分通过把组合数公式中三阶乘的部分分子预处理分母求逆元再相乘来得到。
    标程写的十分暴力，用了很多取模，你们可以试试黑科技优化。
    时间复杂度o(N*log(mod)+T*N)，空间复杂度o(N)。

代码

  1. //C++
  2. #include<cstdio>
  3. #include<iostream>
  4. using namespace std;
  5. #define mod 1000000007
  6. long long jc[600005],ni[600005],mi2[300005];
  7. long long ksm(long long x,long long y)
  8. {
  9.     long long now=1;
  10.     while(y)
  11.     {
  12.         if(y%2)
  13.             now=(now*x)%mod;
  14.         x=(x*x)%mod;
  15.         y>>=1;
  16.     }
  17.     return now;
  18. }
  19. long long c(int x,int y)
  20. {
  21.     return (((jc[x]*ni[y])%mod)*ni[x-y])%mod;
  22. }
  23. long long ask(int x,int y,int l,int r)
  24. {
  25.     if(x==0)
  26.     {
  27.         if(l==0)
  28.             return 1;
  29.         else
  30.             return 0;
  31.     }
  32.     long long now=0;
  33.     for(int i=l;i<=r;i++)
  34.     {
  35.         if(i+y<1 || i>x)
  36.             continue;
  37.         now=(now+((c(r-l,i-l)*mi2[i])%mod)*c(x+y-1,x-i))%mod;
  38.     }
  39.     return now;
  40. }
  41. int main()
  42. {
  43.     jc[0]=ni[0]=1;
  44.     for(int i=1;i<=600000;i++)
  45.     {
  46.         jc[i]=(jc[i-1]*i)%mod;
  47.         ni[i]=ksm(jc[i],mod-2);
  48.     }
  49.     mi2[0]=1;
  50.     for(int i=1;i<=300000;i++)
  51.         mi2[i]=(mi2[i-1]*2)%mod;
  52.     int t;
  53.     int n1,n2,n3;
  54.     long long ans,temp1,temp2;
  55.     scanf("%d",&t);
  56.     while(t--)
  57.     {
  58.         scanf("%d%d%d",&n1,&n2,&n3);
  59.         ans=0;
  60.         for(int i=0;i<=n2;i++)
  61.         {
  62.             int j=n3-(n2-i);
  63.             if(i+j>n1+1 || j<0)
  64.                 continue;
  65.             if(i>=2)
  66.             {
  67.                 temp1=(c(n1-1,j)*c(n1-1-j,i-2))%mod;
  68.                 temp2=ask(n2-i,i+j,n1+1-i-j,n1+1-i-j);
  69.                 ans=(ans+temp2*temp1)%mod;
  70.             }
  71.             if(j>=2)
  72.             {
  73.                 temp1=(c(n1-1,i)*c(n1-1-i,j-2))%mod;
  74.                 temp2=ask(n2-i,i+j,n1+1-i-j,n1+1-i-j);
  75.                 ans=(ans+temp2*temp1)%mod;
  76.             }
  77.             if(i>=1 && j>=1)
  78.             {
  79.                 temp1=(c(n1-1,j-1)*c(n1-j,i-1)*2)%mod;
  80.                 temp2=ask(n2-i,i+j,n1+1-i-j,n1+1-i-j);
  81.                 ans=(ans+temp2*temp1)%mod;
  82.             }
  83.             if(i>=1 && i+j<=n1)
  84.             {
  85.                 temp1=(c(n1-1,j)*c(n1-1-j,i-1)*2)%mod;
  86.                 temp2=ask(n2-i,i+j,n1-i-j,n1+1-i-j);
  87.                 ans=(ans+temp2*temp1)%mod;
  88.             }
  89.             if(j>=1 && i+j<=n1)
  90.             {
  91.                 temp1=(c(n1-1,i)*c(n1-1-i,j-1)*2)%mod;
  92.                 temp2=ask(n2-i,i+j,n1-i-j,n1+1-i-j);
  93.                 ans=(ans+temp2*temp1)%mod;
  94.             }
  95.             if(i+j<=n1-1)
  96.             {
  97.                 temp1=(c(n1-1,i)*c(n1-1-i,j))%mod;
  98.                 temp2=ask(n2-i,i+j,n1-1-i-j,n1+1-i-j);
  99.                 ans=(ans+temp2*temp1)%mod;
  100.             }
  101.         }
  102.         printf("%lld\n",ans);
  103.     }
  104.     return 0;
  105. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注