【Gym 100712B】Rock-Paper-Scissors
【Gym 100712B】Rock-Paper-Scissors
饶文津
发布于 2020-06-02 11:39:55
发布于 2020-06-02 11:39:55
题意
对给定的对手的出拳顺序，如果只能按几个R，然后几个P，再几个S的顺序出拳（几个也可以是0个），那么求赢的方法有多少种。
分析
我原来想枚举P开始的位置和S开始的位置然后算得分，但是超时了o(╯□╰)o。。因为时间复杂度T（n^3）最大规模是500，而这里n≤1000。
用前缀和思想，s[i][0到2]储存前i个里有几个R、S、P，然后再枚举P、S开始位置为i、j；
0到i-1是R的时候，对方是S，我得分，可以得到s[i-1][1]分，对方是P，我失分，失去s[i-1][2]分，同理最后可以得到一个公式。
得分p=2*s[i-1][2]-s[i-1][1]+2*s[j-1][0]-s[i-1][0]-s[j-1][2]-s[n][0]+s[n][1]-s[j-1][1];得分大于0就是赢了。
这样时间复杂度是T（n^2）。
代码
AC代码
#include<stdio.h>
#include<cstring>
char c;
int t,n,ans,p,s[1005][3];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d ",&n);
memset(s,0,sizeof(s));
for(int i=1; i<=n; i++){
c=getchar();
for(int j=0;j<3;j++)s[i][j]=s[i-1][j];
if(c=='R')s[i][0]++;
if(c=='P')s[i][1]++;
if(c=='S')s[i][2]++;
}
ans=0;
for(int i=1; i<=n+1; i++)
for(int j=i; j<=n+1; j++)
{
p=2*s[i-1][2]-s[i-1][1]+2*s[j-1][0]-s[i-1][0]-s[j-1][2]-s[n][0]+s[n][1]-s[j-1][1];
if(p>0)ans++;
}
printf("%d\n",ans);
}
return 0;
}超时代码
#include<stdio.h>
char s[1005];
int t,n,ans,p;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d ",&n);
scanf("%s",s);
ans=0;
for(int i=0; i<=n; i++)
for(int j=i; j<=n; j++)
{
p=0;
for(int k=0; k<n; k++)
switch(s[k])
{
case 'R':
if(k>=i&&k<j) p++;
else if(k>=j) p--;
break;
case 'P':
if(k<i) p--;
else if(k>=j) p++;
break;
case 'S':
if(k<i) p++;
else if(k>=i&&k<j) p--;
break;
}
if(p>0)ans++;
}
printf("%d\n",ans);
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-02-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录