感想：
三个人一开始都是正向看题，导致8分钟之后看榜才发现最后一题是签到。然后就陷入了跟榜做题的被动局面。
这场我一直在隔壁当嘴巴选手，虽然喂的题意给的算法都是对的，包括数独也有了现成的板子，但就是不太想写(然而最后还是想写H还写挂了，没想到有很弱智的写法，总想着要用什么数据结构，完全思维江化)。
最后2小时三个人各开了FHK三题，都没做出来(其实这三道题都非常简单，然而三个人状态都不好)，最后遗憾4题。
赛后队友非常自闭，其实我们就差推出F和写完K了。当时想到K字符串hash的做法但不知道为啥不敢写，听完题解之后后悔死了。
题目链接： https://ac.nowcoder.com/acm/contest/625#question
A：没做出来，正解是爆搜
B：神仙题
C：题意很裸的贪心，但是要注意比较两端相同的情况时要往里走，不是很好写(队友居然写了200行+把我惊到了，肯定不用这么多)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 // compare all in sta. 6 int calc(deque <char> a, deque <char> b, int sta) 7 { 8 while (1) 9 { 10 if ((sta & 1) && (sta & 2) && !(sta & 4) && !(sta & 8) && a.empty()) 11 { 12 if (sta & 1) 13 { 14 return 1; 15 } 16 else if (sta & 2) 17 { 18 return 2; 19 } 20 } 21 if (!(sta & 1) && !(sta & 2) && (sta & 4) && (sta & 8) && b.empty()) 22 { 23 if (sta & 4) 24 { 25 return 4; 26 } 27 else if (sta & 8) 28 { 29 return 8; 30 } 31 } 32 if (a.empty() && b.empty()) 33 { 34 if (sta & 1) 35 { 36 return 1; 37 } 38 else if (sta & 2) 39 { 40 return 2; 41 } 42 else if (sta & 4) 43 { 44 return 4; 45 } 46 else if (sta & 8) 47 { 48 return 8; 49 } 50 } 51 char sc = 0; 52 53 if (sta == 1 || sta == 2 || sta == 4 || sta == 8) 54 { 55 return sta; 56 } 57 58 if (sta & 1) 59 { 60 char tmp; 61 if (a.size()) 62 { 63 tmp = a.front(); 64 a.pop_front(); 65 a.push_front(tmp); 66 } 67 else 68 { 69 tmp = 1; 70 } 71 if (tmp > sc) 72 { 73 sc = tmp; 74 } 75 } 76 77 if (sta & 2) 78 { 79 char tmp; 80 if (a.size()) 81 { 82 tmp = a.back(); 83 a.pop_back(); 84 a.push_back(tmp); 85 } 86 else 87 { 88 tmp = 1; 89 } 90 if (tmp > sc) 91 { 92 sc = tmp; 93 } 94 } 95 96 if (sta & 4) 97 { 98 char tmp; 99 if (b.size()) 100 { 101 tmp = b.front(); 102 b.pop_front(); 103 b.push_front(tmp); 104 } 105 else 106 { 107 tmp = 1; 108 } 109 if (tmp > sc) 110 { 111 sc = tmp; 112 } 113 } 114 115 if (sta & 8) 116 { 117 char tmp; 118 if (b.size()) 119 { 120 tmp = b.back(); 121 b.pop_back(); 122 b.push_back(tmp); 123 } 124 else 125 { 126 tmp = 1; 127 } 128 if (tmp > sc) 129 { 130 sc = tmp; 131 } 132 } 133 134 int sel = 0; 135 136 char s1 = 0, s2 = 0, s3 = 0, s4 = 0; 137 138 if (sta & 1) 139 { 140 char tmp; 141 if (a.size()) 142 { 143 tmp = a.front(); 144 a.pop_front(); 145 s1 = tmp; 146 } 147 else 148 { 149 tmp = 1; 150 } 151 if (tmp == sc) 152 { 153 sel |= 1; 154 } 155 } 156 157 if (sta & 2) 158 { 159 char tmp; 160 if (a.size()) 161 { 162 tmp = a.back(); 163 a.pop_back(); 164 s2 = tmp; 165 } 166 else 167 { 168 tmp = 1; 169 } 170 if (tmp == sc) 171 { 172 sel |= 2; 173 } 174 } 175 176 if (sta & 4) 177 { 178 char tmp; 179 if (b.size()) 180 { 181 tmp = b.front(); 182 b.pop_front(); 183 s3 = tmp; 184 } 185 else 186 { 187 tmp = 1; 188 } 189 if (tmp == sc) 190 { 191 sel |= 4; 192 } 193 } 194 195 if (sta & 8) 196 { 197 char tmp; 198 if (b.size()) 199 { 200 tmp = b.back(); 201 b.pop_back(); 202 s4 = tmp; 203 } 204 else 205 { 206 tmp = 1; 207 } 208 if (tmp == sc) 209 { 210 sel |= 8; 211 } 212 } 213 sta = sel; 214 } 215 } 216 217 int main() 218 { 219 int T; 220 cin >> T; 221 for (int c = 1; c <= T; c++) 222 { 223 string A, B; 224 cin >> A >> B; 225 cout << "Case #" << c << ": "; 226 deque <char> a, b; 227 for (auto i : A) 228 { 229 a.push_back(i); 230 } 231 for (auto i : B) 232 { 233 b.push_back(i); 234 } 235 while (a.size() || b.size()) 236 { 237 char mx = 0; 238 int sta = 0; 239 if (a.size()) 240 { 241 if (a.front() > mx) 242 { 243 mx = a.front(); 244 } 245 if (a.back() > mx) 246 { 247 mx = a.back(); 248 } 249 } 250 if (b.size()) 251 { 252 if (b.front() > mx) 253 { 254 mx = b.front(); 255 } 256 if (b.back() > mx) 257 { 258 mx = b.back(); 259 } 260 } 261 262 if (a.size()) 263 { 264 if (a.front() == mx) 265 { 266 sta |= 1; 267 } 268 if (a.back() == mx) 269 { 270 sta |= 2; 271 } 272 } 273 if (b.size()) 274 { 275 if (b.front() == mx) 276 { 277 sta |= 4; 278 } 279 if (b.back() == mx) 280 { 281 sta |= 8; 282 } 283 } 284 285 sta = calc(a, b, sta); 286 287 switch (sta) 288 { 289 case 1: 290 cout << a.front(); 291 a.pop_front(); 292 break; 293 case 2: 294 cout << a.back(); 295 a.pop_back(); 296 break; 297 case 4: 298 cout << b.front(); 299 b.pop_front(); 300 break; 301 case 8: 302 cout << b.back(); 303 b.pop_back(); 304 break; 305 } 306 } 307 cout << endl; 308 } 309 return 0; 310 }
D：神仙图论题，点分治+NTT
E：数独，Dancing Links秒杀
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int N = 9; 6 const int MaxN = N * N * N + 10; 7 const int MaxM = N * N * 4 + 10; 8 const int maxnode = MaxN * 4 + MaxM + 10; 9 char g[MaxN]; 10 struct DLX{ 11 int n, m, size; 12 int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode]; 13 int H[MaxN], S[MaxN]; 14 int ansd, ans[MaxN]; 15 void init(int _n, int _m) { 16 n = _n; 17 m = _m; 18 for (int i = 0; i <= m; i++) { 19 S[i] = 0; 20 U[i] = D[i] = i; 21 L[i] = i - 1; 22 R[i] = i + 1; 23 } 24 R[m] = 0; 25 L[0] = m; 26 size = m; 27 for (int i = 1; i <= n; i++) { 28 H[i] = -1; 29 } 30 } 31 32 void Link(int r, int c) { 33 ++S[Col[++size] = c]; 34 Row[size] = r; 35 D[size] = D[c]; 36 U[D[c]] = size; 37 U[size] = c; 38 D[c] = size; 39 if (H[r] < 0) H[r] = L[size] = R[size] = size; 40 else { 41 R[size] = R[H[r]]; 42 L[R[H[r]]] = size; 43 L[size] = H[r]; 44 R[H[r]] = size; 45 } 46 } 47 void Remove(int c) { 48 L[R[c]] = L[c]; 49 R[L[c]] = R[c]; 50 for (int i = D[c]; i != c; i = D[i]) 51 for (int j = R[i]; j != i; j = R[j]) { 52 U[D[j]] = U[j]; 53 D[U[j]] = D[j]; 54 --S[Col[j]]; 55 } 56 } 57 void resume(int c){ 58 for (int i = U[c]; i != c; i = U[i]) { 59 for (int j = L[i]; j != i; j = L[j]) { 60 ++S[Col[U[D[j]] = D[U[j]] = j]]; 61 } 62 } 63 L[R[c]] = R[L[c]] = c; 64 } 65 bool Dance(int d) { 66 if (R[0] == 0) { 67 for (int i = 0; i < d; i++) { 68 g[(ans[i] - 1) / 9] = (ans[i] - 1) % 9 + ‘1‘; 69 } 70 for (int i = 0; i < N; i ++) { 71 for (int j = 0; j < N; j++) { 72 printf(j ? " %c" : "%c", g[i*N+j]); 73 } 74 printf("\n"); 75 } 76 return true; 77 } 78 int c = R[0]; 79 for (int i = R[0]; i != 0; i = R[i]) { 80 if (S[i] < S[c]) { 81 c = i; 82 } 83 } 84 Remove(c); 85 for (int i = D[c]; i != c; i = D[i]) { 86 ans[d] = Row[i]; 87 for (int j = R[i]; j != i; j = R[j]) Remove(Col[j]); 88 if (Dance(d + 1)) return true; 89 for (int j = L[i]; j != i; j = L[j]) resume(Col[j]); 90 } 91 resume(c); 92 return false; 93 } 94 }; 95 96 void place (int &r, int &c1, int &c2, int &c3, int &c4, int i, int j, int k) { 97 r = (i * N + j) * N + k; 98 c1 = i * N + j + 1; 99 c2 = N * N + i * N + k; 100 c3 = N * N * 2 + j * N + k; 101 c4 = N * N * 3 + ((i / 3) * 3 + (j / 3)) * N + k; 102 } 103 104 DLX dlx; 105 106 int main(void) { 107 for (int i = 0; i < 9; i++) { 108 for (int j = 0; j < 9; j++) { 109 int tmp; 110 scanf("%d", &tmp); 111 if (tmp == 0) { 112 g[i * N + j] = ‘.‘; 113 } else { 114 g[i * N + j] = ‘0‘ + tmp; 115 } 116 } 117 } 118 dlx.init(N * N * N, N * N * 4); 119 int r, c1, c2, c3, c4; 120 for(int i = 0; i < N; i++) 121 for (int j = 0; j < N; j++) 122 for (int k = 1; k <= N; k++) 123 if (g[i * N + j] == ‘.‘ || g[i * N + j] == ‘0‘ + k) { 124 place (r, c1, c2, c3, c4, i, j, k); 125 dlx.Link(r, c1); 126 dlx.Link(r, c2); 127 dlx.Link(r, c3); 128 dlx.Link(r, c4); 129 } 130 dlx.Dance(0); 131 return 0; 132 }
F：概率dp，但是可以通过算出n=3的情况来蒙出答案是2n-1 (队友到最后都没推出来，难受)
G：很迷的神仙题
H：rmq，也可以直接暴力算
1 /* basic header */ 2 #include <iostream> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <string> 6 #include <cstring> 7 #include <cmath> 8 #include <cstdint> 9 #include <climits> 10 #include <float.h> 11 /* STL */ 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <queue> 16 #include <stack> 17 #include <algorithm> 18 #include <array> 19 #include <iterator> 20 /* define */ 21 #define ll long long 22 #define dou double 23 #define pb emplace_back 24 #define mp make_pair 25 #define fir first 26 #define sec second 27 #define init(a,b) fill(begin(a),end(a),b) 28 #define sot(a,b) sort(a+1,a+1+b) 29 #define rep1(i,a,b) for(int i=a;i<=b;++i) 30 #define rep0(i,a,b) for(int i=a;i<b;++i) 31 #define repa(i,a) for(auto &i:a) 32 #define eps 1e-8 33 #define int_inf 0x3f3f3f3f 34 #define ll_inf 0x7f7f7f7f7f7f7f7f 35 #define lson curPos<<1 36 #define rson curPos<<1|1 37 /* namespace */ 38 using namespace std; 39 /* header end */ 40 41 const int maxn = 5e5 + 10; 42 const int mod = 1e9 + 7; 43 ll ans = 0, a[maxn], comGcd = 0; 44 int n; 45 46 int main() 47 { 48 scanf("%d", &n); 49 rep1(i, 1, n) 50 { 51 scanf("%lld", &a[i]); 52 comGcd = i == 1 ? a[i] : __gcd(comGcd, a[i]); 53 } 54 rep1(i, 1, n) 55 { 56 ll currGcd = a[i]; 57 rep1(j, i, n) 58 { 59 currGcd = __gcd(currGcd, a[j]); 60 ans = (ans + currGcd) % mod; 61 if (currGcd == comGcd) 62 { 63 ans = ((n - j) * comGcd + ans) % mod; 64 break; 65 } 66 } 67 } 68 printf("%lld\n", ans); 69 return 0; 70 }
I：很简单的O(n)贪心，队友不知道为啥wa了好几发
1 #include<iostream> 2 #include<cstdio> 3 4 using namespace std; 5 const int maxn = 2000000; 6 int A[maxn]; 7 typedef long long ll; 8 int main() 9 { 10 int n; 11 scanf("%d",&n); 12 for(int i = 1;i <= n;i++){ 13 scanf("%d",&A[i]); 14 } 15 A[n+1] = A[n]-1; 16 int mx,mn; 17 mx = mn= A[1]; 18 ll ans = 0; 19 20 for(int i = 1;i <= n;i++){ 21 if(A[i] >= A[i-1]&&A[i] > A[i+1]){ 22 mx = max(mx,A[i]); 23 ans += mx - mn; 24 mx = mn = A[i+1]; 25 continue; 26 } 27 if(A[i] > A[i-1]){ 28 mx = max(A[i],mx); 29 } 30 if(A[i] <= A[i-1]&&A[i] <= A[i+1]){ 31 mx = mn = A[i]; 32 } 33 } 34 printf("%lld\n",ans); 35 return 0; 36 }
J：化简行列式之后原题就变成了斜率优化dp了
K：字符串hash，最后没写完，很可惜
L：温暖的签到题(然而我们过了8分钟才发现)
原文：https://www.cnblogs.com/JHSeng/p/10704639.html
