没有参加,但是之后几天打了哦,第三场AK的CF比赛。
CF大扫荡计划正在稳步进行。
【A】Olympiad
题意:
给\(n\)个人颁奖,要满足:
至少有一个人拿奖。
如果得分为\(x\)的有奖,那么任意得分大于\(x\)必须拿奖。
得分为\(0\)的人不能拿奖。
每个人的得分\(0\le x\le 600\),问有多少种颁奖方式?
题解:
本质上,问题可以转化为有多少种不同的得分。于是开一个桶做。
#includeint n,x,cnt[601],ans;int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&x), cnt[x]++; for(int i=1;i<=600;++i) if(cnt[i]) ++ans; printf("%d",ans); return 0;}
【B】Vile Grasshoppers
题意:
松树上共有\(y\)根树枝,从低到高第\(2\)到第\(p\)个树枝都有一只蚱蜢,已知在树枝\(x\)的蚱蜢可以跳到\(2x,3x,4x,\cdots\)树枝上。
你要选取最高的树枝,使得没有蚱蜢能跳到这根树枝上。输出树枝编号。
题解:
本质上是\([1,y]\)中最大的不能被\([2,p]\)范围整除的数,倒序遍历,每一个暴力\(\sqrt{x}\)check,因为质数很多,所以很快。
#includeint p,y;int main(){ scanf("%d%d",&p,&y); for(int i=y;i>p;--i){ for(int j=2;j<=p&&j*j<=i;++j) if(i%j==0) goto no; printf("%d",i); return 0; no: continue; } puts("-1"); return 0;}
【C】Save Energy!
题意:
Julia要煮一只鸡。她厨房的炉子为了节能,开启后\(k\)分钟就会关掉。
Julia每\(d\)分钟会去厨房一次,如果炉子关了,她会把它打开。
如果炉子开着,需要\(t\)分钟煮好,关着则需要\(2t\)分钟。
问几分钟煮好?
题解:
算出周期,直接算答案,做一点数学,不难。
[详细解释] 炉子开着,每分钟煮\(\frac{1}{t}\),关着则煮\(\frac{1}{2t}\)。
那么令总进度为\(2t\),开着每分钟进度\(+2\),关着则\(+1\)。
一个周期必定是开始炉子开着,然后炉子关上,周期长度显然是\(\left\lceil\frac{k}{d}\right\rceil\cdot d\)。
这么一算,一除,一分类讨论,就差不多了。
#includelong long k,d,t,lp,t1,t2;double ans;int main(){ scanf("%lld%lld%lld",&k,&d,&t); t<<=1; lp=(k-1)/d*d+d; t1=k<<1, t2=lp-k; ans=t/(t1+t2)*lp; t%=t1+t2; if(t<=t1) ans+=(double)t/t1*k; else ans+=k+(double)(t-t1)/t2*(lp-k); printf("%lf",ans); return 0;}
【D】Sleepy Game
题意:
俩人玩博弈游戏,可是这不是博弈题,因为其中一个人睡着了。
那么身为另一个人,他可以代替另一个人以达到对自己的最优结果。
总之,在一个有\(n\)个点,\(m\)条边的有向图中,从一个初始位置\(s\)沿着边走到其他点,无法移动者输掉游戏。
问能否能赢,如果能,输出方案,如果不能,判断能否至少平局(在任意多步后都无法结束游戏)。
题解:
本质上,赢的条件是存在从\(s\)到任意一个出度为\(0\)的点的路径长度为偶数,可以重复走。
而平局则是从\(s\)能走到一个环,都不行则输了。
这题坑了我很久,接下来解释一下做法。
①判断能否赢:从\(s\)开始DFS,每个点存储能否从\(s\)到它有偶数或奇数的路径(有可能既有偶数也有奇数)。
DFS函数需要两个参数\(DFS(u,c)\),\(c\)相当于起点到它的步数的奇偶性。这样如果能到一个出度为\(0\)的点并且\(c=0\),则有解。
②判环:直接Tarjan版判环。
可以巧妙地把2个DFS合到一起。
#includeusing namespace std;int n,m,x,y,o,v[2][100001],k[2][100001],t[2][100001];vector h[100005];bool D(int u,bool c){ if(~k[c][u]) return k[c][u]; if(!h[u].size()) return k[c][u]=c; v[c][u]=1; for(int i:h[u]) {if(v[c][i]||v[!c][i]) o=1; if(!v[!c][i]&&D(i,!c)) return t[c][u]=i, v[c][u]=0, k[c][u]=1;} return v[c][u]=0, k[c][u]=0;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i){ scanf("%d",&x); while(x--) scanf("%d",&y), h[i].push_back(y); } scanf("%d",&x); memset(k,-1,sizeof k); if(D(x,0)){ puts("Win"); y=1; while(x) printf("%d ",x), x=t[y=!y][x]; return 0; } puts(o?"Draw":"Lose"); return 0;}
【E】Lock Puzzle
题意:
对于一个字符串\(\alpha\beta\),你可以通过一次操作把它变成\(\beta^R\alpha\),这里的\(x^R\)表示字符串\(x\)的倒序。
这里的\(\beta\)的长度可以任意选择。
给定一个长为\(n\)的字符串\(s\),和等长的字符串\(t\)。
问如何在\(3n+100\)的操作内把\(s\)变成\(t\)。无解输出\(-1\)。
题解:
如果\(s\)和\(t\)中有一个字母的出现次数不同,则显然无解。
而其他情况都能在\(3n\)步内完成,如下:
假设已有一个字符串\(\alpha\)的前缀是\(t\)的后缀,而紧跟着\(\alpha\)是一个需要放到\(\alpha\)前面的字符,那么我们经过3步可以把\(x\)放到\(\alpha\)前面:
\(\underline{\alpha x\beta}\\\beta^Rx\underline{\alpha^R}\\\alpha\beta^R\underline{x}\\x\alpha\beta^R\)
其中下划线是操作的\(\beta\)字符串。
那么做\(n\)遍这个操作,可以在\(3n\)步之内完成。
#include#define F(i,a,b) for(int i=a;i<=(b);++i)#define dF(i,a,b) for(int i=a;i>=(b);--i)using namespace std;int n;char str1[2005],str2[2005],str3[2005],str4[2005];int main(){ scanf("%d%s%s",&n,str1+1,str2+1); memcpy(str3+1,str1+1,n); memcpy(str4+1,str2+1,n); sort(str3+1,str3+n+1); sort(str4+1,str4+n+1); if(memcmp(str3+1,str4+1,n)) {puts("-1"); return 0;} printf("%d\n",n*3); dF(i,n,1){ int p; F(j,n-i+1,n) if(str1[j]==str2[i]) {p=j; break;} printf("%d %d 1 ",n,p-1); reverse(str1+p+1,str1+n+1); memcpy(str1+2,str1+1,p-1); str1[1]=str2[i]; } return 0;}