A. 2048 Game
乱搞即可。
<details> <summary>Code</summary></details>1#include <bits/stdc++.h> 2#define MP make_pair 3#define fi first 4#define se second 5#define sz(x) (int)(x).size() 6//#define Local 7using namespace std; 8typedef long long ll; 9typedef pair<int, int> pii; 10const int N = 1e5 + 5; 11 12int n; 13int a[N]; 14 15void run() { 16 cin >> n; 17 int cnt = 0, cnt1 = 0; 18 for(int i = 1; i <= n; i++) { 19 cin >> a[i]; 20 if(a[i] > 2048) continue; 21 if(a[i] == 1) ++cnt1; 22 else { 23 cnt += a[i] / 2; 24 } 25 } 26 cnt += cnt1 / 2; 27 if(cnt >= 1024) cout << "YES" << '\n'; 28 else cout << "NO" << '\n'; 29} 30 31int main() { 32 ios::sync_with_stdio(false); 33 cin.tie(0); cout.tie(0); 34 cout << fixed << setprecision(20); 35#ifdef Local 36 freopen("../input.in", "r", stdin); 37 freopen("../output.out", "w", stdout); 38#endif 39 int q; cin >> q; 40 while(q--) run(); 41 return 0; 42}
B. Knights
直接按奇偶分类其实就行，但我写了个$dfs$...
<details> <summary>Code</summary></details>1#include <bits/stdc++.h> 2#define MP make_pair 3#define fi first 4#define se second 5#define sz(x) (int)(x).size() 6//#define Local 7using namespace std; 8typedef long long ll; 9typedef pair<int, int> pii; 10const int N = 105; 11 12int n; 13int a[N][N]; 14int dx[8] = {-2, -2, -1, -1, 2, 2, 1, 1}; 15int dy[8] = {-1, 1, -2, 2, -1, 1, -2, 2}; 16bool chk(int x, int y) { 17 return x <= n && x >= 1 && y >= 1 && y <= n && a[x][y] == 0; 18} 19 20void dfs(int x, int y, int c) { 21 a[x][y] = c; 22 for(int i = 0; i < 8; i++) { 23 int nowx = x + dx[i], nowy = y + dy[i]; 24 if(chk(nowx, nowy)) dfs(nowx, nowy, 3 - c); 25 } 26} 27 28void run() { 29 memset(a, 0, sizeof(a)); 30 dfs(1, 1, 1); 31 for(int i = 1; i <= n; i++) { 32 for(int j = 1; j <= n; j++) { 33 if(a[i][j] == 1) cout << 'W'; 34 else cout << 'B'; 35 } 36 cout << '\n'; 37 } 38} 39 40int main() { 41 ios::sync_with_stdio(false); 42 cin.tie(0); cout.tie(0); 43 cout << fixed << setprecision(20); 44#ifdef Local 45 freopen("../input.in", "r", stdin); 46 freopen("../output.out", "w", stdout); 47#endif 48 while(cin >> n) run(); 49 return 0; 50}
C. Perfect Team
直接输出就行，但我写了个二分...
<details> <summary>Code</summary></details>1#include <bits/stdc++.h> 2#define MP make_pair 3#define fi first 4#define se second 5#define sz(x) (int)(x).size() 6//#define Local 7using namespace std; 8typedef long long ll; 9typedef pair<int, int> pii; 10const int N = 1e5 + 5; 11 12int c, m, x; 13 14bool chk(int q) { 15 int nc = c - q, nm = m - q; 16 return nc >= 0 && nm >= 0 && nc + nm + x >= q; 17} 18 19void run() { 20 cin >> c >> m >> x; 21 int ans = min(c, m); 22 if(x >= ans) { 23 cout << ans << '\n'; return; 24 } 25 int l = 0, r = 100000002, mid; 26 while(l < r) { 27 mid = (l + r) >> 1; 28 if(chk(mid)) l = mid + 1; 29 else r = mid; 30 } 31 cout << r - 1 << '\n'; 32} 33 34int main() { 35 ios::sync_with_stdio(false); 36 cin.tie(0); cout.tie(0); 37 cout << fixed << setprecision(20); 38#ifdef Local 39 freopen("../input.in", "r", stdin); 40 freopen("../output.out", "w", stdout); 41#endif 42 int q; cin >> q; 43 while(q--) run(); 44 return 0; 45}
D. Make The Fence Great Again
题意： 给出$n$个数，现在定义一个好的序列为：对于任意相邻的$i,j$，满足$a_i\not ={a_j}$。 现在你可以每次将一个数增加$1$，代价为$b_i$。 问将给出的序列变成好的序列的最小代价为多少。
思路：
- 注意到一个数最多增加两次，因为如果增加的次数大于$2$的话，就会有空隙，填补那个空隙就行了。
- 那么定义$dp[i,j]$表示考虑了前$i$个数，最后一个数增加了$j$次的最小代价，直接枚举转移即可。
代码如下：
<details> <summary>Code</summary></details>1#include <bits/stdc++.h> 2#define INF 2000000000000000000 3#define MP make_pair 4#define fi first 5#define se second 6#define sz(x) (int)(x).size() 7//#define Local 8using namespace std; 9typedef long long ll; 10typedef pair<int, int> pii; 11const int N = 3e5 + 5; 12 13ll dp[N][5]; 14int n; 15int a[N], b[N]; 16 17void run() { 18 cin >> n; 19 for(int i = 1; i <= n; i++) cin >> a[i] >> b[i]; 20 for(int i = 0; i <= n; i++) for(int j = 0; j < 5; j++) dp[i][j] = INF; 21 for(int i = 0; i < 5; i++) dp[0][i] = 0; 22 for(int i = 1; i <= n; i++) { 23 for(int j = 0; j < 4; j++) { 24 for(int k = 0; k < 4; k++) { 25 if(i == 1 || a[i - 1] + k != a[i] + j) { 26 dp[i][j] = min(dp[i - 1][k] + 1ll * j * b[i], dp[i][j]); 27 } 28 } 29 } 30 } 31 ll ans = INF; 32 for(int i = 0; i < 4; i++) ans = min(ans, dp[n][i]); 33 cout << ans << '\n'; 34} 35 36int main() { 37 ios::sync_with_stdio(false); 38 cin.tie(0); cout.tie(0); 39 cout << fixed << setprecision(20); 40#ifdef Local 41 freopen("../input.in", "r", stdin); 42 freopen("../output.out", "w", stdout); 43#endif 44 int q; cin >> q; 45 while(q--) run(); 46 return 0; 47}
E. Game With String
题意： 给出一个$01$序列，两个人来玩博弈游戏，博弈规则如下：
- $A$为先手，$B$为后手，给出$a,b,b<a$，$A$能够将$a$个连续的$a$个$0$变为$1$；$B$能够将连续的$b$个$0$变为$1$。
- 当有一个人无法操作时，则输掉这场游戏。
现给出长度不超过$10^5$的序列，问谁胜谁负。
思路： 感觉很有意思的一道博弈题，跟平时遇到的博弈题不一样。感觉不一样就在于游戏规则对于双方来说都不一样，好像是非平衡博弈？ 首先有一个很重要的观察：
- 如果存在一段连续的$0$的长度$x$满足：$b\leq x<a$，那么$B$必胜。
$B$会比$A$多一次机会。 $A$能搞的$B$也能搞；若出现一个局面，$B$必须用掉这一次机会，那么说明其它位置肯定不存在一段长度大于等于$b$了，自然之后$A$不能再搞了。
</details>那么现在考虑，在什么样的局面下，$B$能够构造出上述观察。 思考可以发现，当存在两段连续$0$的个数都大于等于$2b$时，$B$必然可以构造出这样一段，当然原来就有这么一段就不说了。 发现剩下的情况个数很少，我们直接分类讨论：
- 当不存在任何一个段长度大于等于$2b$时，显然此时所有合法段的长度都是不小于$a$的（前面的情况已经排除）。那么此时的胜负就根据合法段的奇偶个数。
- 当仅存在一个时，既然只有一段，直接枚举$A$在该段上的所有选择，看看存不存在必胜状态就行啦。$A$开始必然在这段区间上面选，不然$B$可以随便构造出满足“观察”的段。
代码如下：
<details> <summary>Code</summary></details>1#include <bits/stdc++.h> 2#define MP make_pair 3#define fi first 4#define se second 5#define sz(x) (int)(x).size() 6#define all(x) (x).begin(), (x).end() 7//#define Local 8using namespace std; 9typedef long long ll; 10typedef pair<int, int> pii; 11const int N = 3e5 + 5; 12 13char s[N]; 14int a, b; 15 16void A() { 17 cout << "YES" << '\n'; 18} 19 20void B() { 21 cout << "NO" << '\n'; 22} 23 24void run() { 25 vector <int> v; 26 cin >> a >> b; 27 cin >> s + 1; 28 int n = strlen(s + 1); 29 int cnt = 0; 30 for(int i = 1; i <= n; i++) { 31 if(s[i] == '.') ++cnt; 32 else { 33 if(cnt) { 34 v.push_back(cnt); 35 cnt = 0; 36 } 37 } 38 } 39 if(cnt) v.push_back(cnt); cnt = 0; 40 int f = 0; 41 for(auto it : v) { 42 if(it >= 2 * b) ++cnt; 43 if(it >= b && it < a) f = 1; 44 } 45 if(f || cnt >= 2) { 46 B(); return; 47 } 48 if(cnt == 0) { 49 for(auto it : v) { 50 if(it >= a) ++cnt; 51 } 52 if(cnt & 1) A(); 53 else B(); 54 return ; 55 } 56 int mx = *max_element(all(v)); 57 cnt = 0; 58 for(auto it : v) { 59 if(it != mx && it >= a) ++cnt; 60 } 61 for(int l = 1; l + a - 1 <= mx; l++) { 62 int r = l + a - 1; 63 int left = l - 1, right = mx - r; 64 if(left >= 2 * b || right >= 2 * b) continue; 65 if((left >= b && left < a) || (right >= b && right < a)) continue; 66 int tmp = cnt + (left >= a) + (right >= a); 67 if(tmp % 2 == 0) { 68 A(); return; 69 } 70 } 71 B(); 72} 73 74int main() { 75 ios::sync_with_stdio(false); 76 cin.tie(0); cout.tie(0); 77 cout << fixed << setprecision(20); 78#ifdef Local 79 freopen("../input.in", "r", stdin); 80 freopen("../output.out", "w", stdout); 81#endif 82 int q; cin >> q; 83 while(q--) run(); 84 return 0; 85}
F. Choose a Square
题意： 二维平面上给出$n$个点，每个点都有个权值。现在要求选择一个正方形，满足其中一根对角线的两顶点在$y=x$这条直线上。 问所选正方形包含了的点的权值和减去边长的最大值。 类似于这样： 
答案为$4$。
思路：
-
因为正方形具有对称性，所以我们可以考虑将$y=x$这条直线下方的点对称过去处理，那么我们现在就相当于选择一个等腰直角三角形的区域，类似于这样：
-
注意到最终三角形的边上一定存在至少一个点，那么也就是说有用的横纵坐标就为这些点的坐标。
-
直接枚举$x,y$显然复杂度不能承受，考虑当我们枚举$x$时，选择一个最大的$y$，就类似于维护一个区间最大值。
-
对于一个位置$x=x_0$，显然随着$y$增大包含的点越多，并且对于一个$y=y_0$而言，与$y=x$这条直线所形成的三角形区域是必选的。类似于这样：
-
所以线段树的做法就很显然了，横坐标直接从后往前枚举，依次加点并且不断在线段树中插入点的信息并更新区间信息，查询的时候就直接查询最大值以及纵坐标即可。
-
为什么是更新区间最大值？
-
因为每插入一个点，它会影响在它右上方的点，当选择右上方的点时，它也必然被包含，类似于这样：（所以直接更新在其上方的区间信息即可）
-
注意一个细节，因为最后还要减去正方形的边长，对于一个点$(x,y)$而言，正方形边长就为$y-x$，减去就是加上$x-y$。因为我们是按照$y$值建立线段树的，初始答案就为$-y$，最后加上枚举的$x$就行了。
最后还要注意特判一下答案为负的情况，可能答案不包含任何点。 详见代码：
<details> <summary>Code</summary></details>1#include <bits/stdc++.h> 2#define MP make_pair 3#define fi first 4#define se second 5#define sz(x) (int)(x).size() 6#define all(x) (x).begin(), (x).end() 7//#define Local 8using namespace std; 9typedef long long ll; 10typedef pair<ll, ll> pll; 11const int N = 5e5 + 5; 12 13int n; 14vector <int> v; 15pll tr[N << 2]; 16ll add[N << 2]; 17 18struct node{ 19 int x, y, c; 20 bool operator < (const node &A) const{ 21 return x < A.x; 22 } 23}p[N]; 24 25void push_up(int o) { 26 tr[o] = max(tr[o << 1], tr[o << 1|1]); 27} 28 29void push_down(int o, int l, int r) { 30 if(add[o]) { 31 tr[o << 1].fi += add[o]; 32 tr[o << 1|1].fi += add[o]; 33 add[o << 1] += add[o]; 34 add[o << 1|1] += add[o]; 35 add[o] = 0; 36 } 37} 38 39void build(int o, int l, int r) { 40 add[o] = 0; 41 if(l == r) { 42 tr[o] = MP(-v[l], v[l]); 43 return; 44 } 45 int mid = (l + r) >> 1; 46 build(o << 1, l, mid); build(o << 1|1, mid + 1, r); 47 push_up(o); 48} 49 50void update(int o, int l, int r, int x, int c) { 51 if(x <= v[l]) { 52 tr[o].fi += c; 53 add[o] += c; 54 return; 55 } 56 push_down(o, l, r); 57 int mid = (l + r) >> 1; 58 if(x <= v[mid]) update(o << 1, l, mid, x, c); 59 update(o << 1|1, mid + 1, r, x, c); 60 push_up(o); 61} 62 63pll query(int o, int l, int r, int L) { 64 if(L > v[r]) return MP(-1000000009, 0); 65 if(L <= v[l]) return tr[o]; 66 push_down(o, l, r); 67 int mid = (l + r) >> 1; 68 pll ret = max(query(o << 1, l, mid, L), query(o << 1|1, mid + 1, r, L)); 69 return ret; 70} 71 72void run() { 73 v.clear(); 74 for(int i = 1; i <= n; i++) { 75 int x, y, c; cin >> x >> y >> c; 76 if(x > y) swap(x, y); 77 p[i] = {x, y, c}; 78 v.push_back(y); 79 } 80 sort(all(v)); 81 v.erase(unique(all(v)), v.end()); 82 build(1, 0, sz(v) - 1); 83 sort(p + 1, p + n + 1); 84 p[0].x = -1; 85 pll ans = MP(-1000000009, 0); 86 int ansx; 87 for(int i = n; i >= 1; i--) { 88 update(1, 0, sz(v) - 1, p[i].y, p[i].c); 89 if(p[i - 1].x != p[i].x) { 90 pll ret = query(1, 0, sz(v) - 1, p[i].x); 91 ret.fi += p[i].x; 92 if(ret > ans) { 93 ans = ret; 94 ansx = p[i].x; 95 } 96 } 97 } 98 if(ans.fi < 0) { 99 ans = MP(0, 1000000001), ansx = 1000000001; 100 } 101 cout << ans.fi << ' ' << ansx << ' ' << ansx << ' ' << ans.se << ' ' << ans.se << '\n'; 102} 103 104int main() { 105 ios::sync_with_stdio(false); 106 cin.tie(0); cout.tie(0); 107 cout << fixed << setprecision(20); 108#ifdef Local 109 freopen("../input.in", "r", stdin); 110 freopen("../output.out", "w", stdout); 111#endif 112 while(cin >> n) run(); 113 return 0; 114}