傳送門
?
A 2048
題意：multiset里面有許多2的冪，每次可以從multiset取出兩個一樣的數字，放回去兩數之和，問能否出現2048.
code1083、分析：優先隊列模擬操作
B knights
題意：棋子可以走日字，將n*n的棋盤用W與B填滿，代表兩個陣營的棋子，使得可以互相攻擊的點對數量最大。
分析：大水題
解法一：
B0D？ bfs，在左上角先放一個棋子，然后在可以攻擊到的地方放敵對棋子，然后重復直到沒有格子可以填。
解法二：
棋子與他可以攻擊到的位置的曼哈頓距離為奇數，所以構造棋盤使得不存在相鄰的B與W即可，就像國際象棋的棋盤。
C?Perfect Team
題意：c，m，x代表coder，mathematician，和咸魚，一只隊伍必須要有一個coder和mathematician，必須要有三個人，求最多隊伍數。
分析：解法一：不考慮人數配置，隊伍數為（c+m+x）/3，考慮人數配置，將這個值跟c和m三個值取最小值即為答案。
A B C D E F，解法二：比較容易想到，先組出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]轉移。依次類推。
A B C D游戲怎么玩、這道題比賽時如果用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;} }
?
