[考试反思]1023csp-s模拟测试83：等候

大家好，欢迎来到IT知识分享网。

分数倒是依旧那么烂，但是这个时间比较诡异。

6分49秒弄出T1，15分钟送上T2的50分暴力，不到一小时半的时候T3的30分暴力也完成了。。。

在85分钟之后一次提交也没有

前15分钟平均每分钟得10分，后三个小时每小时得10分。。。

如果这场考试只考16分钟，我绝对rank1而且能拉第二一大截。

然而这些都是我的yy，最终还不是考得什么也不是么。。。

到了后两个小时，什么也想不出来，听着别人码，看着别人拿分，自己坐以待毙，稍绝望。。。

中途OJ还死了能看到评测结果，打开评测界面挂在顶上的大概是这个东西

[考试反思]1023csp-s模拟测试83：等候

T2我想了一辈子也没想出来啊啊啊。。。

然而我要脸我没有看我的分数。赛后看，嗯，果然一分没多。。。

然而T2其实就是包装了一下的B组原题，还是我考场A掉的那个，居然就不会做了

也不知道是状态问题还是怎么的

集训过半。。。

紧张起来吧。。。

T1：最大异或和

每个节点都被拿走了。所以最后两个人得分异或起来就是所有节点的异或和。

如果总异或和上某一位是0那么两个人得分的这一位上一定相同，拉不开差距。

否则这一位就是绝胜位，谁在这一位上是1谁就赢。

然而小Q是可以自行选择节点了，选择任意一个这一位上是1的节点他就赢了。

如果没有绝胜位，即异或和为0，就是平局。

 1 #include<cstdio>
 2 int main(){
 3     int t,n,X;scanf("%d",&t);
 4     while(t--){
 5         scanf("%d",&n);X=0;
 6         for(int i=1,x;i<=n;++i)scanf("%d",&x),X^=x;
 7         for(int i=1,x,y;i<n;++i)scanf("%d%d",&x,&y);
 8         puts(X?"Q":"D");
 9     }
10 }

为何不秒切？

T2：简单的括号序列

 1 #include<cstdio>
 2 #define mod 1000000007
 3 int min(int a,int b){return a<b?a:b;}
 4 int fac[200005],inv[200005],invv[200005],n,pre[200005],suf[200005],ans;char s[200005];
 5 int C(int b,int t){return 1ll*fac[b]*inv[t]%mod*inv[b-t]%mod;}
 6 main(){
 7     scanf("%s",s+1);while(s[n+1])n++;
 8     fac[0]=fac[1]=inv[1]=inv[0]=invv[1]=1;
 9     for(int i=2;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod,invv[i]=mod-1ll*mod/i*invv[mod%i]%mod,inv[i]=1ll*inv[i-1]*invv[i]%mod;
10     for(int i=1;i<=n;++i)pre[i]=pre[i-1]+(s[i]=='(');
11     for(int i=n;i;--i)suf[i]=suf[i+1]+(s[i]==')');
12     for(int i=1;i<=n;++i)if(s[i]==')')for(int j=1;j<=min(pre[i],suf[i]);++j)
13         ans=(ans+1ll*C(pre[i],j)*C(suf[i]-1,j-1))%mod;
14     printf("%d\n",ans);
15 }

50分暴力不细说

瓶颈在于式子$\sum\limits_{i=1}^{min(pre,suf)}C_{pre}^{i} \times C_{suf-1}^{i-1}$

$=\sum\limits_{i=1}^{min(pre,suf)}C_{pre}^{pre-i} \times C_{suf-1}^{i-1}$

两枣树问题，从含义上即可理解：就是$C_{pre+suf-1}^{pre-1}$

 1 #include<cstdio>
 2 #define mod 1000000007
 3 int min(int a,int b){return a<b?a:b;}
 4 int fac[200005],inv[200005],invv[200005],n,pre[200005],suf[200005],ans;char s[200005];
 5 int C(int b,int t){return 1ll*fac[b]*inv[t]%mod*inv[b-t]%mod;}
 6 main(){
 7     scanf("%s",s+1);while(s[n+1])n++;
 8     fac[0]=fac[1]=inv[1]=inv[0]=invv[1]=1;
 9     for(int i=2;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod,invv[i]=mod-1ll*mod/i*invv[mod%i]%mod,inv[i]=1ll*inv[i-1]*invv[i]%mod;
10     for(int i=1;i<=n;++i)pre[i]=pre[i-1]+(s[i]=='(');
11     for(int i=n;i;--i)suf[i]=suf[i+1]+(s[i]==')');
12     for(int i=1;i<=n;++i)if(s[i]==')')for(int j=1;j<=min(pre[i],suf[i]);++j)
13         ans=(ans+1ll*C(pre[i],j)*C(suf[i]-1,j-1))%mod;
14     printf("%d\n",ans);
15 }

考场切的原题，现在凭什么反而想不到？

T3：旅行计划

图很密集，不难想到矩阵。

但是这次不是倍增快速幂，而是分块预处理。

100步为1块。处理矩阵p0[i][j][k]表示i步从j到k的最短距离。

p1[i][j][k]表示100i步。p2[i][j][k]表示至少i步。

注意p0和p2要处理到150而不是100，当你需要p2[99][x][y]时它的真实步数可能大于100而你没有处理然后你就WA90了。

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int min(int a,int b){return a<b?a:b;}
 5 int dp0[155][52][52],dp1[105][52][52],dp2[155][52][52],E[52][52],r[52][52],n,m,q,x,y,v;
 6 int main(){
 7     scanf("%d%d",&n,&m);
 8     memset(E,0x3f,sizeof E);memset(dp0,0x3f,sizeof dp0);
 9     memset(dp1,0x3f,sizeof dp1);memset(dp2,0x3f,sizeof dp2);
10     for(int i=1;i<=m;++i)scanf("%d%d%d",&x,&y,&v),E[x][y]=min(E[x][y],v);
11     for(int i=1;i<=n;++i)dp0[0][i][i]=dp1[0][i][i]=0;
12     for(int i=1;i<=150;++i)for(int j=1;j<=n;++j)for(int k=1;k<=n;++k)for(int l=1;l<=n;++l)
13         dp0[i][j][k]=min(dp0[i][j][k],dp0[i-1][j][l]+E[l][k]);
14     for(int i=1;i<=100;++i)for(int j=1;j<=n;++j)for(int k=1;k<=n;++k)for(int l=1;l<=n;++l)
15         dp1[i][j][k]=min(dp1[i][j][k],dp1[i-1][j][l]+dp0[100][l][k]);
16     for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)for(int k=150;~k;--k)
17         dp2[k][i][j]=min(dp2[k+1][i][j],dp0[k][i][j]);
18     scanf("%d",&q);
19     while(q--){
20         scanf("%d%d%d",&x,&y,&v);int ans=1000000000;
21         for(int i=1;i<=n;++i)ans=min(ans,dp1[v/100][x][i]+dp2[v%100][i][y]);
22         printf("%d\n",ans>900000000?-1:ans);
23     }
24 }

考场上想到矩阵没想到分块

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/33360.html

[考试反思]1023csp-s模拟测试83：等候

相关推荐

发表回复