今年题目难度有较大提升，总体与往年类似，数学题居多。以下为我通过的部分题解。
赛题链接：http://acm.xidian.edu.cn/contest.php?cid=1053
A - 上帝视角
我也没去过澳门赌场，不熟悉什么筹码之类。看完题有点懵，但毕竟是签到题。
题目大概是隐含了总筹码数量相同这一条件，然后每个人开始的筹码都是一样的。给你一组每个人手上筹码的局面，然后有q组询问，让你判断现在局面是否合法，其中一个人赢了还是输了。
比较简单，废话不多说直接上代码：
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll; ll arr[], qi[];
int main()
{
int n, m, q;
ll total = ;
cin>>n;
for(int i=;i<n;i++)
cin>>arr[i], total += arr[i];
cin>>q; for(int i=;i<q;i++)
cin>>qi[i]; if(total%n)
cout<<"you ren chu qian?\n";
else {
total /= n;
for(int i=;i<q;i++)
if(arr[qi[i]-]>total) cout<<"jian hao jiu shou!\n";
else if(arr[qi[i]-]<total) cout<<"ji shi zhi sun!\n";
else cout<<"wei shi bu wan!\n";
}
return ;
}
B - Shocking! Two Acmer Doing This In The Lab!
感觉太复杂了，一直没做，AC了再来更新吧。大概就是一个思维题。
C - XY之说走就走的旅行
简单的BFS，开始题目看错了，以为求min(disA+disB)，交上去WA了一发，再看题发现是求min(max(disA, disB));
因为偷懒用一个数组存（i,j)到两地的最大距离，不明不白WA了半天。。。思考问题一定要考虑周全啊！！！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std; int n, m;
char mp[][];
int s1x, s1y, s2x, s2y, k;
bool vis[][];
int dis[][];
const int dx[]={, , , -};
const int dy[]={, -, , };
struct node{
int x, y;
int step;
node(int xx=, int yy=, int s=):x(xx), y(yy), step(s){}
} sta[];
void bfs(int t, int x, int y)
{
vis[x][y] = ;
queue<node> q;
q.push(node(x, y, ));
while(q.size()) {
node now = q.front(); q.pop();
for(int i=;i<;i++) {
int nx = now.x+dx[i];
int ny = now.y+dy[i];
if(nx>= && nx<n && ny>= && ny<m && !vis[nx][ny] && mp[nx][ny]!='#') {
vis[nx][ny] = ;
if(mp[nx][ny]=='P') {
if(t==) dis[nx][ny] = now.step+;
else if(dis[nx][ny])
dis[nx][ny] = max(now.step+, dis[nx][ny]);
}
q.push(node(nx, ny, now.step+));
} }
}
}
int main()
{
while(cin>>n>>m)
{
k = ;
getchar();
for(int i=;i<n;i++) {
scanf("%s", mp[i]);
for(int j=;mp[i][j];j++)
if(mp[i][j]=='P') sta[k].x = i, sta[k++].y=j;
else if(mp[i][j]=='X') s1x = i, s1y = j;
else if(mp[i][j]=='Y') s2x = i, s2y = j;
}
memset(dis, , sizeof(dis));
memset(vis, , sizeof(vis));
bfs(, s1x, s1y);
memset(vis, , sizeof(vis));
bfs(, s2x, s2y); int x, ans = ;
for(int i=;i<k;i++)
if(dis[sta[i].x][sta[i].y] && dis[sta[i].x][sta[i].y]<ans)
x = i, ans = dis[sta[x].x][sta[x].y];
cout<<sta[x].x+<<' '<<sta[x].y+<<endl;
} return ;
}
D - 武举考试安排表
这题难点在于读懂题目，然后就是要打表找规律。直白说比赛安排表类似一个数独，添上一行123...N的表头代表队员编号的话，那么整个表就有N行N列。我们要使每行每列都有1~N，并且要找到一个字典序最小的方案。
第一天我很天真地以为，简单把123...N的排列每次循环左移就能得到字典序最小的安排表。WA了三次后，在纸上排一遍发现还能有更优的排法，排表过程中要用到dfs，复杂度O(22N），就扔到一边没管了。
过了两天根据Wu找的规律几分钟写了代码就直接AC了，哈哈哈。预处理n=10的安排表，查询O(1)，总的时间复杂度O(220+T)。
#include<iostream>
#include<cstdio>
using namespace std;
int ans[][];
const int num[] = {, , , , , , , , , , , };
void pre()
{
ans[][] = ans[][] = ;
ans[][] = ans[][] = ; int s = ;
while(s<) {
for(int i=s;i<*s;i++)
for(int j=;j<s;j++)
ans[i][j] = s+ans[i-s][j]; for(int i=;i<s;i++)
for(int j=s;j<*s;j++)
ans[i][j] = s+ans[i][j-s]; for(int i=s;i<*s;i++)
for(int j=s;j<*s;j++)
ans[i][j] = ans[i-s][j-s];
s *= ;
}
}
int main()
{
pre();
for(int i=;i<;i++) {
for(int j=;j<;j++)
printf("%2d ", ans[i][j]);
cout<<endl;
}
int T; cin>>T;
int n, m, x;
while(T--)
{
scanf("%d %d %d", &n, &m, &x);
if(m<||m>num[n]||x<||x>num[n]-)
cout<<"Wrong Query!\n";
else {
cout<<ans[x][m-]<<endl;
} }
return ;
}
E - 最后一个
一眼扫去这不就是Nim博弈吗？然后就快速写了个Nim和，交上去就WA了。再细看发现结束的规则不一样，取走最后的石子者为败家。想了半天还是不太会博弈，既然状态有限，就写了记忆化搜索，调试好样例交上就AC了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int s[][][][][][]; // s=0 败 s=1 胜
int solve(int a, int b, int c, int d, int e, int f)
{
if(a+b+c+d+e+f==) return ;
if(s[a][b][c][d][e][f]!=-)
return s[a][b][c][d][e][f]; for(int i=;i<=a;i++)
if(solve(a-i, b, c, d, e, f)==) return s[a][b][c][d][e][f]=;
for(int i=;i<=b;i++)
if(solve(a, b-i, c, d, e, f)==) return s[a][b][c][d][e][f]=;
for(int i=;i<=c;i++)
if(solve(a, b, c-i, d, e, f)==) return s[a][b][c][d][e][f]=;
for(int i=;i<=d;i++)
if(solve(a, b, c, d-i, e, f)==) return s[a][b][c][d][e][f]=;
for(int i=;i<=e;i++)
if(solve(a, b, c, d, e-i, f)==) return s[a][b][c][d][e][f]=;
for(int i=;i<=f;i++)
if(solve(a, b, c, d, e, f-i)==) return s[a][b][c][d][e][f]=; return s[a][b][c][d][e][f]=; }
int arr[];
int main()
{
memset(s, -, sizeof(s));
s[][][][][][] = ;
int n;
while(scanf("%d", &n)!=EOF) {
memset(arr, , sizeof(arr));
for(int i=;i<n;i++)
scanf("%d", &arr[i]); printf("%s\n", solve(arr[],arr[],arr[],arr[],arr[],arr[])?"orzwym6912":"orzwang9897");
}
return ;
}
网上查阅了相关的题，理解了这个规则其实同样可以用Nim和来解决，只需要特殊判断全部堆都是1的情况。因为在Nim博弈中，最后一步要取走全部石子，那么本题对于必胜者也可以少取走一颗石子，那么也是必胜。但是如果每堆只有一颗石子，就无法按照Nim博弈的进行最优取法。显然有偶数个为1的堆为必胜态，那么问题就解决了。
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int n;
while(scanf("%d", &n)!=EOF) {
int ans = , k;
bool flag = ; int cnt = ;
while(n--) {
scanf("%d", &k);
if(k==) continue; if(k!=) flag = ;
else cnt++;
ans ^= k;
}
if(!flag)
printf("%s\n", ans==?"orzwang9897":"orzwym6912");
else
printf("%s\n", cnt&?"orzwang9897":"orzwym6912");
}
return ;
}
F - 背包弹夹平底锅
通过找规律+oeis.org归纳出公式，最后发现了这题主要是得到第二类斯特林数。结果就是s(n, i)*i!/n^m。
那么怎么求s(n, i)呢？查阅资料得知这个跟组合数有相似的递推性质，可以在O(n2)时间内求出s(n, i)。此题n,m<100000,显然不行。
翻了好多篇博客，都提到要用快速傅里叶变换，然后就自闭了。
（待补。。。）
G - 小鸟的修路计划
这题就是求有n个不同节点的连通图的种类。
开始自己手算了递推式，样例都算不对，只好百度借鉴了别人的公式。
写好快速幂+组合数WA了好多次，debug很久，一度怀疑幂运算取模出错了，要用那啥费马小定理。最后比对别人的输出才突然注意到三个ll相乘会溢出的重大bug。。。
先预处理，T次查询直接输出结果，时间复杂度O(m2+T)。
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll; const ll mod=;
ll C[][], f[];
ll pow_mod(ll a, ll x)
{
ll res = ;
while(x) {
if(x&) res = (res*a)%mod;
a = (a*a)%mod;
x >>= ;
}
return res;
}
ll Cn2(int n)
{
return (ll)n*(n-)/;
}
void solve()
{
for(int i=;i<;i++)
C[i][i] = C[i][] = ; for(int i=;i<;i++)
for(int j=;j<=i;j++) {
C[i][j] = (C[i-][j] + C[i-][j-])%mod;
} f[] = f[] = ;
// f[3] = 4;
for(int n=;n<;n++) {
for(int i=;i<n;i++)
f[n] = (f[n] + ((C[n-][i-]*f[i])%mod * pow_mod(, Cn2(n-i))%mod))%mod; f[n] = ((pow_mod(, Cn2(n))-f[n])%mod+mod)%mod;
}
} int main()
{
int T; cin>>T;
solve();
while(T--) {
int m; scanf("%d", &m);
printf("%lld\n", f[m]);
}
return ;
}
// 2的C(n,2)次方我为什么要用组合数。。。
H - 超长递增序列
一个简单技巧题被我硬生生用二分法暴力求解，一直TLE到怀疑人生。（虽说复杂度O(T*2n*logn)很勉强的样子）
由于a1 + a2 + ... + ai <= a(i+1)，那么对于K，我们从后往前查找，如果a(i+1)<=K，不取a(i+1)的话就无法选择前i项使总和为K，所以a(i+1)必选。因此不断往前贪心即可。
时间复杂度O(T*n)
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
ll arr[], K; ll pow2(ll a, int x)
{
ll res = ;
while(x) {
if(x&) res *= a;
a *= a;
x >>= ;
}
return res;
} int main()
{
int T, n; scanf("%d", &T);
while(T--) {
scanf("%d %lld", &n, &K);
for(int i=;i<=n;i++)
scanf("%lld", &arr[i]); int i=n;
ll res = ;
while(K>) {
while(i>= && arr[i]>K) i--;
if(i<) break;
else
K -= arr[i], res += pow2(, i);
}
if(K==)
printf("%lld\n", res);
else
printf("-1\n");
}
return ;
}
I - 两数和
题意：给了n个数两两之间C(n,2)组和，求出原数列，如有多组，输出字典序最小的解。
假设有a1<=a2<=a3<=... <=an，可以得到最小和一定是a1+a2，次小和一定是a1+a3。（仔细想想是不是）
那么如果我们假设第三小的和是a2+a3的话，前三个数就确定了。显然接下来最小的和就是a1+a4，求出a4，删去a2+a4,a3+a4，那么最小的就是a1+a5，依次类推，a5，a6，... ，都能计算出来。
但问题没这么简单。
我们其实无法确定a1+a4,a1+a5,..., a1+an与a2+a3的大小顺序。可以肯定的是，a2+a3的值一定在这n-3+1=n-2组最小值之中。
所以采用穷举并检验后续能否全部算出，时间复杂度O(T*n3)，可行。
PS. 注意n=2的特殊处理。
// 考虑到每次检验失败都要重新传入n*(n-1)/2组值，感觉会拖慢时间，自作聪明将multiset<ll>传引用，结果WA了半天还不知道哪出错了。。。
// 对于要在函数内进行修改且不需要返回更新值的变量，还是不要想当然传引用了。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
typedef multiset<ll>::iterator msPt;
int n;
ll ai, a[];
bool solve(ll c1, ll c2, ll c3, multiset<ll> S)
{
if((c1+c2+c3)%)
return ; if(c1+c3<=c2||c1+c2<=c3)
return ; a[] = (c1+c2-c3)/;
a[] = (c1+c3-c2)/;
a[] = (c2+c3-c1)/; for(int i=;i<=n;i++) {
a[i] = *S.begin()-a[]; S.erase(S.begin()); for(int j=;j<i;j++) {
if(S.find(a[j]+a[i])==S.end())
return ;
else
S.erase(S.find(a[j]+a[i]));
}
} for(int i=;i<=n;i++)
printf("%lld%c", a[i], n==i?'\n':' ');
return ;
} int main()
{
int T; cin>>T;
while(T--) {
scanf("%d", &n);
if(n==) {
scanf("%lld", &ai);
if(ai>)
printf("1 %lld\n", ai-);
else
printf("Impossible\n"); continue;
} multiset<ll> S;
for(int i=;i<n*(n-)/;i++) {
scanf("%lld", &ai);
S.insert(ai);
}
ll c1 = *S.begin(); S.erase(S.begin());
ll c2 = *S.begin(); S.erase(S.begin());
// ll c3 = *S.begin(); S.erase(S.begin()); vector<ll> C3;
for(msPt it = S.begin(); C3.size()<n-&& it!=S.end();it++)
if(C3.size() && *it==C3[C3.size()-]) continue;
else
C3.push_back(*it); bool flag = ;
for(int i=;i<C3.size();i++) {
S.erase(S.find(C3[i]));
if(!solve(c1, c2, C3[i], S)) {
S.insert(C3[i]);
} else {
flag = ;
}
}
if(!flag)
printf("Impossible\n"); }
return ;
}
J - 垒箱子
哈哈不会，据说需要各种暴力+建图。我还是好好掌握prim啊、dijkstra啊这种再来吧。。。
K - 签到
到了传说中的签到题，好几天都一直没人做。读完题发现就是求解三个球面的交点问题，可以直接联立方程求解。
为了体现出它不是一个数学问题，我尝试用计算几何的思维，二分两平面的交线。WA了十来次才发现连输出要求都没注意。改过后仍然WA。。。
最后还是用数学方法解方程通过的。赛后题解提供了五六种思路，我尝试了两种二分都失败了，改日再研究计算几何。。。