A. Picking&Dancing
有一列n个石子，两人交替取石子，每次只能取连续的两个，取走后，剩下的石子仍然排成1列。问最后剩下的石子数量是奇数还是偶数。
读懂题意就没什么好说的。
#include<stdio.h>
int n;
int main()
{
scanf("%d",&n);
if(n%2)
puts("Xiaoyu_Chen");
else
puts("Yitong_Qin");
return 0;
}
B. string
首先我们可以倒着贪心。因为比如aabd，这个d 合并不合并到b 和之前的字符串无关。
然后我们写出伪代码：
ans :=1;
for i:= n-1 downto 1 do
if(s[i]<> s[i+1])
then ans :=1;
else inc(ans);
然后我们发现，答案就是开头连续相同的字母数。
#include<bits/stdc++.h>
using namespace std;
long long i,ans,l;
char ch;
string s;
int main() {
cin>>s;
l = s.length();
ch = s[0];
i = 1;
ans = 1;
while (s[i] == ch && i < l) {
ans++;
i++;
}
cout<<ans;
}
C. How To Get Twenty-four?
题意：给定一个数n，问你能否用n个"7"仅仅通过加减乘除(可添加括号)这几种运算得到24点。
手推一下n比较小的情况，容易发现，n<=5时都是无解的。
n=6的情况在样例中给出 ：
(7*7*7-7)/(7+7)=24
n=7时：
#include<stdio.h>
int n;
int main()
{
scanf("%d",&n);
if(n<=5)
puts("NO");
else
puts("YES");
return 0;
}
D. Passing the Ball
结论题：
若M为奇数，则答案为((N-1)^M-N+1)/N
若M为偶数，则答案为((N-1)^M+N-1)/N
证明一：
设F[k]为球最后传给第k个人的情况数
显然球最后传给第2到第N个人的概率相同，即F[2]=F[3]=...=F[N]
F[1]+F[2]+F[3]+...+F[N]=(N-1)^M
F[1]+(N-1)*F[2]=(N-1)^M
而球一旦传给第3到第N个人，则球最后传给前两个人的概率相同
即在球曾传给第3到第N个人的情况中，最后传给前两个人的情况数相同
而在球没有传给第3到N个人的情况中，即前两个人互传的情况，有：
若M为奇数，则最后传给第2个人
若M为偶数，则最后传给第1个人
即F[2]=F[1]+1(M为奇数)
F[2]=F[1]-1(M为偶数)
综上所述，F[1]=((N-1)^M-N+1)/N(M为奇数)
F[1]=((N-1)^M+N-1)/N(M为偶数)
证明二:
设F[k]为k次传球后传给第1个人的情况数
则F[k]=(N-1)^(k-1)-F[k-1]，且F[1]=0
故若M为奇数，则F[m]=(N-1)^(M-1)-(N-1)^(M-2)+...-(N-1)^1
=(1-N)*((1-N)^(M-1)-1)/(1-N-1)
=((N-1)^M-N+1)/N
若M为偶数，则F[m]=(N-1)^(M-1)-(N-1)^(M-2)+...+(N-1)^1
=(N-1)((N-1)^(M-2)-(N-1)^(M-3)+...-(N-1)^1+1)
=(N-1)(((N-1)^(M-1)-N+1)/N+1)
=((N-1)^M+N-1)/N
Hint：由于数据范围进行过弱化，因此本应无法通过的直接递推的做法也可以AC了。
#include <cstdio>
#include <iostream>
using namespace std;
long long n,m;
int main(){
scanf("%lld%lld",&n,&m);
long long ans=1;
for(int i=1;i<=m;++i)ans*=n-1;
if(m&1)ans=(ans-n+1)/n;
else ans=(ans+n-1)/n;
printf("%lld",ans);
}
E. Homura's Game
题意：给定一个体积为a*b*c的长方体（由a*b*c个1*1*1的小立方体房间构成），最开始有一个石子在坐标为(1,1,1)的房间里，两人交替移动石子到一个相邻的房间，但是不能移动到曾经访问过的房间。不能移动了算输。问是否存在先手必胜策略？
考虑二维的情况，若一个a*b的棋盘恰好有偶数个格子，那么它一定可以被1*2大小的长方形卡片恰好完全覆盖。于是先手的玩家每次只需从当前卡片的一端移动到另一端即可，而后手的玩家却需要把石子移动到一个新的卡片上。于是，只要后手的玩家可以移动卡片，先手的玩家就必然可以移动卡片，于是先手必胜。
若这个棋盘恰好有奇数个格子呢？显然，除了左上角的一个格子以外，其他的所有格子可以被1*2大小的长方形卡片恰好完全覆盖。于是先手的玩家第一步必须把石子移动到一个新的卡片上。于是先手必败。
考虑三维的情况，我们容易发现，结论仍然成立。
于是只需判断a*b*c的奇偶性。偶数输出YES，奇数输出NO。
容易发现，当且仅当a,b,c均为奇数时，a*b*c才为奇数，否则为偶数。
Source：二维的情况，BZOJ2463 [中山市选2009]谁能赢呢?
#include<stdio.h>
int n;
int main()
{
int a,b,c,i;
scanf("%d%d%d",&a,&b,&c);
if(a%2==1 && b%2==1 && c%2==1)
puts("NO");
else
puts("YES");
return 0;
}
UESTC第八届ACM趣味程序设计竞赛到此就全部结束了！祝贺得奖的大家！没有得奖的选手也不要气馁，只要努力，ACM系列程序设计竞赛一直会欢迎你们的！
在此也感谢各位命题人的工作。