A 2048
题意：multiset里面有许多2的幂，每次可以从multiset取出两个一样的数字，放回去两数之和，问能否出现2048.
分析：优先队列模拟操作
B knights
题意：棋子可以走日字，将n*n的棋盘用W与B填满，代表两个阵营的棋子，使得可以互相攻击的点对数量最大。
分析：大水题
解法一：
bfs，在左上角先放一个棋子，然后在可以攻击到的地方放敌对棋子，然后重复直到没有格子可以填。
解法二：
棋子与他可以攻击到的位置的曼哈顿距离为奇数，所以构造棋盘使得不存在相邻的B与W即可，就像国际象棋的棋盘。
C Perfect Team
题意：c，m，x代表coder，mathematician，和咸鱼，一只队伍必须要有一个coder和mathematician，必须要有三个人，求最多队伍数。
分析：解法一：不考虑人数配置，队伍数为（c+m+x）/3，考虑人数配置，将这个值跟c和m三个值取最小值即为答案。
解法二：比较容易想到，先组出c，m，x各一个的队伍，对于剩下来的人，二分可以组出的队伍数量，加上前面的结果就是答案。
D Make The Fence Great Again
题意：给定数组a和b，ai是第i元素的值，bi是将ai+1的代价，求最小代价，使得a中没有相邻的元素相同。
分析：首先，很容易想到对于每一个元素只需要+0，+1或+2就可以使得a满足条件。
令dp[i][j]为第i位上升j的合法情况的最小代价，如果a[i]==a[i-1]，那么dp[i][0]为第i位上升0合法的最小代价，如果ai上升0，ai-1的合法状态为上升1或者2，所以dp[i][0]可以从dp[i-1][1]和dp[i-1][2]转移，dp[i][1]可以从dp[i-1][0]和dp[i-1][2]转移。依次类推。
这道题比赛时如果用cin不关同步可以过样例，但是赛后会被hack。
#include <bits/stdc++.h> #define mp make_pair #define mst(a,n) memset(a, n, sizeof(a)) #define debug(x) cout << #x << ": " << x << endl #define pb push_back typedef long long LL; const int maxn = 3e5 + 10; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; using namespace std; LL n, q, a[maxn], b[maxn], dp[maxn][3]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> q; while (q--) { cin >> n; for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; } LL ans = 0; for (int i = 0; i < n; ++i) dp[i][0] = 0; dp[0][1] = b[0]; dp[0][2] = 2 * b[0]; for (int i = 1; i < n; ++i) { if (a[i] == a[i - 1]) { dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]); dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + b[i]; dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + b[i] * 2; } else if (a[i] == a[i - 1] + 1) { dp[i][0] = min(dp[i - 1][0], dp[i - 1][2]); dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + b[i]; dp[i][2] = min(dp[i - 1][0], min(dp[i - 1][1], dp[i - 1][2])) + b[i] * 2; } else if (a[i] == a[i - 1] - 1) { dp[i][0] = min(dp[i - 1][0], min(dp[i - 1][1], dp[i - 1][2])); dp[i][1] = min(dp[i - 1][1], dp[i - 1][2]) + b[i]; dp[i][2] = min(dp[i - 1][0], dp[i - 1][2]) + b[i] * 2; } else if (a[i] == a[i - 1] + 2) { dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]); dp[i][1] = dp[i][0] + b[i]; dp[i][2] = dp[i][0] + b[i] * 2; } else if (a[i] == a[i - 1] - 2) { dp[i][0] = min(dp[i - 1][0], min(dp[i - 1][1], dp[i - 1][2])); dp[i][1] = dp[i][0] + b[i]; dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + b[i] * 2; } else { dp[i][0] = min(dp[i - 1][0], min(dp[i - 1][1], dp[i - 1][2])); dp[i][1] = dp[i][0] + b[i]; dp[i][2] = dp[i][0] + b[i] * 2; } } cout << min(dp[n - 1][0], min(dp[n - 1][1], dp[n - 1][2])) << endl; } }