A - Tiny Arithmetic Sequence
题目大意
给定序列\(A=(A_1,A_2,A_3)\)。能否将\(A\)重新排列，使得\(A_3-A_2=A_2-A_1\)？
\(1\le A_i\le 100\)
输入格式
\(A_1~A_2~A_3\)
输出格式
如果能将\(A\)重新排列使得\(A_3-A_2=A_2-A_1\)，输出Yes；如果不能，输出No。
样例
| \(A\) | 输出 |
|---|---|
| \((5,1,3)\) | Yes |
| \((1,4,3)\) | No |
| \((5,5,5)\) | Yes |
分析
很容易想到，如果\(A_3-A_2=A_2-A_1\)，则\(A_1\le A_2\le A_3\)或\(A_3\le A_2\le A_1\)必定成立。
因此，我们可以先把\(A\)按升序排列，再\(A_3-A_2=A_2-A_1\)是否成立即可。
代码
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int a[3];
scanf("%d%d%d", a, a + 1, a + 2);
sort(a, a + 3);
puts(a[2] - a[1] == a[1] - a[0]? "Yes": "No");
return 0;
}
B - Do you know the second highest mountain?
题目大意
有\(N\)坐山。第\(i\)坐山有一个名字\(S_i\)和高度\(T_i\)。
输出第二高的山的名字。
\(2\le N\le 1000\)
\(1\le |S_i|\le 15\)
\(1\le T_i\le 10^5\)
\(S_i\ne S_j~(i\ne j)\)
\(T_i\ne T_j~(i\ne j)\)
\(S_i\)由大小写英文字母和数字组成。
输入格式
\(N\)
\(S_1~T_1\)
\(S_2~T_2\)
\(\vdots\)
\(S_N~T_N\)
输出格式
输出第二高的山的名字。
样例
样例输入1
3
Everest 8849
K2 8611
Kangchenjunga 8586
样例输出1
K2
第二高的山是K2。
样例输入2
4
Kita 3193
Aino 3189
Fuji 3776
Okuhotaka 3190
样例输出2
Kita
第二高的山是Kita。
样例输入3
4
QCFium 2846
chokudai 2992
kyoprofriends 2432
penguinman 2390
样例输出3
QCFium
第二高的山是QCFium。
分析
这道题其实就是给定求数组\(T\)中第二大的元素的\(S_i\)。我们可以利用优先队列实现求第二大的元素。
代码
#include <iostream>
#include <queue>
#include <string>
using namespace std;
using pis = pair<int, string>;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
priority_queue<pis, vector<pis>, greater<pis> > q;
while(n--)
{
string s;
int h;
cin >> s >> h;
q.emplace(h, s);
if(q.size() > 2) q.pop();
}
cout << q.top().second << endl;
return 0;
}
C - Secret Number
题目大意
有一个四位的PIN。这个PIN由0~9组成，也可能以0开头。
有一个字符串\(S_0S_1\dots S_9\)，代表每一种数字是否在这个PIN中出现：
- 如果\(S_i=~\)
o，这个PIN肯定包含数字\(i\)； - 如果\(S_i=~\)
x，这个PIN肯定不包含数字\(i\)； - 如果\(S_i=~\)
?，这个PIN可能包含（也可能不包含）数字\(i\)。
有多少个合法的PIN？
\(S\)是一个由o、x、?组成的长度为\(10\)的字符串。
输入格式
\(S\)
输出格式
将答案输出为一个整数。
样例
| \(S\) | 答案 |
|---|---|
ooo???xxxx |
\(108\) |
o?oo?oxoxo |
\(0\) |
xxxxx?xxxo |
\(15\) |
极端测试点：\(S=~\)??????????，正确输出：\(10000\) |
分析
因为可能的PIN数量非常少（最多只有\(10000\)个），所以我们考虑暴力枚举所有可能的PIN，即尝试0000到9999之间所有的PIN。对于每个可能的PIN，我们可以在\(\mathcal O(|S|)\)的时间内判断出它是否合法。
程序的总时间复杂度为\(\mathcal O(10000|S|)\)，由于\(10000\)和\(|S|\)都是常数，所以也可以看作\(\mathcal O(1)\)。
代码
#include <cstdio>
using namespace std;
char s[15];
inline bool valid(int a, int b, int c, int d)
{
bool used[10] = {false};
used[a] = used[b] = used[c] = used[d] = true;
for(int i=0; i<10; i++)
if(s[i] == 'o')
{
if(!used[i])
return false;
}
else if(s[i] == 'x' && used[i])
return false;
return true;
}
int main()
{
scanf("%s", s);
int ans = 0;
for(int a=0; a<10; a++)
for(int b=0; b<10; b++)
for(int c=0; c<10; c++)
for(int d=0; d<10; d++)
ans += valid(a, b, c, d);
printf("%d\n", ans);
return 0;
}
D - Game in Momotetsu World
题目大意
我们有一个\(H\times W\)的棋盘，它上面每个小格子都是蓝色或红色的。棋盘上\((i,j)\)这个点的颜色取决于\(A_{i,j}\)。如果\(A_{i,j}=~\)+，则\((i,j)\)为蓝；如果\(A_{i,j}=~\)-，则\((i,j)\)为红。
在棋盘上有一颗棋子，它的初始位置在左上角，也就是\((1,1)\)。Takahashi和Aoki要用这颗棋子对战。两人一开始都有\(0\)分，他们要轮流执行如下操作，Takahashi先走：
- 将棋子往右或下移动（不能移出棋盘）。然后，如果移到的点是蓝色的，对应的玩家得一分；否则，玩家扣一分。
当棋子走到\((H,W)\)时，游戏结束。此时，如果两人得分相等，则视为平局；否则，得分多的人胜利。
当两人都按最优操作进行游戏时，求最终的游戏结果。
\(1\le H,W\le 2000\)
\(A_{i,j}\)是+或-。
输入格式
\(H~W\)
\(A_{1,1}A_{1,2}A_{1,3}\dots A_{1,W}\)
\(A_{2,1}A_{2,2}A_{2,3}\dots A_{2,W}\)
\(\vdots\)
\(A_{H,1}A_{H,2}A_{H,3}\dots A_{H,W}\)
输出格式
如果Takahashi会赢，输出Takahashi；如果Aoki，输出Aoki；否则，游戏平局，输出Draw。
样例
略，请自行前往AtCoder查看。
分析
本题可以使用动态规划的思想。
我们设\(d\)为\((\text{Takahashi目前的得分})-(\text{Aoki目前的得分})\)，则Takahashi的目标是最大化\(d\)、Aoki的目标是最小化\(d\)。我们很容易想到，对于棋子在\((i,j)\)时，如果\((i+j)\)是奇数，则Aoki走棋，如果它是偶数，则Takahashi走棋。
所以，对于棋盘上的每个点\((i,j)\)我们考虑如下\(\text{dp}\)：
- 如果\((i+j)\)是偶数：棋子在\((i,j)\)时最小的\(d\)（这是Aoki走棋）。
- 如果\((i+j)\)是奇数：棋子在\((i,j)\)时最大的\(d\)（这是Takahashi走棋）。
我们设\(add(i,j)\)为玩家把棋子走到\((i,j)\)获得的分数，则有如下\(\text{dp}\)状态：
- 如果\((i+j)\)是偶数：\(dp(i,j)=\min(dp(i+1,j)-add(i+1,j),dp(i,j+1)-add(i, j+1))\)
- 如果\((i+j)\)是奇数：\(dp(i,j)=\max(dp(i+1,j)+add(i+1,j),dp(i,j+1)+add(i, j+1))\)
所以，最终我们只需要通过\(dp(0,0)\)判断结果即可。如果\(dp(0,0)>0\)，则Takahashi胜；如果\(dp(0,0)<0\)，Aoki胜；否则，游戏平局。
程序的总时间复杂度为\(\mathcal O(NM)\)。
代码
注意：我这里的dp运用了滚动表的技巧，所以是一维的，当然也可以使用普通的二维dp。
#include <cstdio>
#include <algorithm>
#define maxn 2005
using namespace std;
int dp[maxn], add[maxn][maxn];
int main()
{
int h, w;
scanf("%d%d", &h, &w);
for(int i=0; i<h; i++)
{
char tmp[maxn];
scanf("%s", tmp);
for(int j=0; j<w; j++)
add[i][j] = tmp[j] == '+'? 1: -1;
}
dp[w - 1] = 0;
for(int j=w-2; j>=0; j--)
dp[j] = j + h & 1? dp[j + 1] + add[h - 1][j + 1]: dp[j + 1] - add[h - 1][j + 1];
for(int i=h-2; i>=0; i--)
{
dp[w - 1] = i + w & 1? dp[w - 1] + add[i + 1][w - 1]: dp[w - 1] - add[i + 1][w - 1];
for(int j=w-2; j>=0; j--)
if(i + j & 1)
dp[j] = min(dp[j] - add[i + 1][j], dp[j + 1] - add[i][j + 1]);
else dp[j] = max(dp[j] + add[i + 1][j], dp[j + 1] + add[i][j + 1]);
}
if(dp[0] > 0) puts("Takahashi");
else if(dp[0] < 0) puts("Aoki");
else puts("Draw");
return 0;
}
E - Xor Distances
题目大意
我们有一棵由\(N\)个顶点组成的加权树。第\(i\)条边双向连接着顶点\(u_i\)和\(v_i\)且有一个权值\(w_i\)。
对于一对顶点\((x,y)\)（\(x\ne y\)），我们如下定义\(\mathrm{dist}(x,y)\)：
- \(\mathrm{dist}(x,y)=x\)和\(y\)之间的最短路径经过的所有边权值的异或结果。
输出每对点\((i,j)\)的\(\mathrm{dist}(i,j)\)之和，对\((10^9+7)\)取模，即\(\sum\limits_{i=1}^{N-1}\sum\limits_{j=i+1}^N \mathrm{dist}(i,j)\bmod(10^9+7)\)。
\(1\le N\le 2\times10^5\)
\(1\le u_i < v_i\le N\)
\(0\le w_i < 2^{60}\)
输入格式
\(N\)
\(u_1~v_1~w_1\)
\(u_2~v_2~w_2\)
\(\vdots\)
\(u_{N-1}~v_{N-1}~w_{N-1}\)
输出格式
输出每对点\((i,j)\)的\(\mathrm{dist}(i,j)\)之和，对\((10^9+7)\)取模。
样例
略，请自行前往AtCoder查看
分析
首先，我们先看数据范围。
\(1\le N\le 2\times10^5\)
这样一来，最暴力的\(\mathcal O(n^3)\)解法，即枚举所有对点\(\mathcal O(n^2)\)、找最短路\(\mathcal O(n)\)就肯定不行了。
其次，我们尝试优化暴力过程，考虑异或（\(\oplus\)）的几个特征：
- \(0\oplus A = A\)
- \(A\oplus A = 0\)
- \(A\oplus B = B\oplus A\)
- \(A\oplus B\oplus B = A\)
最后一个特征（异或再异或会抵消掉）实际上就是在告诉我们，\(\mathrm{dist}(x,y)=\mathrm{dist}(n,x)\oplus\mathrm{dist}(n,y)\)，因为\((n,y)\)的最短路径中到\(n\)的多余的一部分直接被最后一次异或抵消掉了。如果不能理解上面的证明，可以用下面的方法证明（设\(k\)为\(x\)和\(y\)的最小共同祖先）：
\[\begin{aligned}\mathrm{dist}(x,y)&=\mathrm{dist}(x,k)\oplus\mathrm{dist}(y,k)\\&=\mathrm{dist}(x,k)\oplus\mathrm{dist}(y,k)\oplus(\mathrm{dist}(n,k)\oplus\mathrm{dist}(n,k))\\&=(\mathrm{dist}(x,k)\oplus\mathrm{dist}(n,k))\oplus(\mathrm{dist}(y,k)\oplus\mathrm{dist}(n,k))\\&=\mathrm{dist}(x,n)\oplus\mathrm{dist}(y,n)\end{aligned} \]这时，我们可以令\(n=1\)，并从\(n\)开始跑一遍搜索，计算出所有的\(\mathrm{dist}(n,x)\)（时间复杂度\(\mathcal O(n)\)），再对所有的\((i,j)\)求出所有的\(\mathrm{dist}(n,i)\oplus\mathrm{dist}(n,j)\)并求和（时间复杂度\(\mathcal O(n^2)\)），算出结果。这样做的总时间复杂度为\(\mathcal O(n^2)\)。可惜，这样还是过不去。
我们考虑进一步优化。我们发现，对于每个二进制位，在异或的操作下，一个\(1\)和一个\(0\)就能组成一个\(1\)。所以，我们可以统计每一位的\(0\)和\(1\)的个数，计算它们的乘积并相加即可。
代码
这里的搜索推荐\(\text{BFS}\)，因为这道题中它比\(\text{DFS}\)好写且更快，当然\(\text{DFS}\)也可以实现。
#include <cstdio>
#include <queue>
#pragma GCC optimize("Ofast")
#define maxn 200005
#define MOD 1000000007LL
using namespace std;
using LL = long long;
vector<pair<int, LL>> G[maxn];
LL d[maxn];
int main()
{
int n;
scanf("%d", &n);
for(int i=1; i<n; i++)
{
int u, v;
LL w;
scanf("%d%d%lld", &u, &v, &w);
G[--u].emplace_back(--v, w);
G[v].emplace_back(u, w);
}
queue<int> q;
q.push(0);
for(int i=1; i<n; i++) d[i] = -1;
while(!q.empty())
{
int v = q.front(); q.pop();
for(auto [u, w]: G[v])
if(d[u] == -1)
q.push(u), d[u] = d[v] ^ w;
}
LL ans = 0LL;
for(int i=0; i<60; i++)
{
int cnt = 0;
for(int j=0; j<n; j++)
if(d[j] >> i & 1LL)
cnt ++;
if((ans += (1LL << i) % MOD * cnt % MOD * (n - cnt) % MOD) > MOD)
ans -= MOD;
}
printf("%lld\n", ans);
return 0;
}