1554.md (7762B)
1 Source: https://codeforces.com/blog/entry/93321 2 3 The problem names are based on my favorite characters out there. Yes, [1554E - You](/contest/1554/problem/E "Codeforces Round 735 (Div. 2)") are my most favorite character UwU. 4 5 I have tried to make the editorials as interactive as possible. Enjoy. 6 7 Tutorial is loading... 8 9 **Code(C++)** 10 11 ``` 12 #include<bits/stdc++.h> 13 using namespace std; 14 15 int32_t main() { 16 ios_base::sync_with_stdio(0); 17 cin.tie(0); 18 int t; cin >> t; 19 while (t--) { 20 int n; cin >> n; 21 vector<int> a(n); 22 for (auto &x: a) { 23 cin >> x; 24 } 25 long long ans = 0; 26 for (int i = 1; i < n; i++) { 27 ans = max(ans, 1LL * a[i] * a[i - 1]); 28 } 29 cout << ans << '\n'; 30 } 31 return 0; 32 } 33 ``` 34 35 **Code(Python)** 36 37 ``` 38 import sys 39 input = sys.stdin.buffer.readline 40 t = int(input()) 41 for _ in range(t): 42 n = int(input()) 43 a = list(map(int, input().split())) 44 ans = 0 45 for i in range(n - 1): 46 ans = max(ans, a[i] * a[i + 1]) 47 print(ans) 48 ``` 49 50 Tutorial is loading... 51 52 **Code(C++)** 53 54 ``` 55 #include<bits/stdc++.h> 56 using namespace std; 57 58 int32_t main() { 59 ios_base::sync_with_stdio(0); 60 cin.tie(0); 61 int t; cin >> t; 62 while (t--) { 63 int n, k; cin >> n >> k; 64 vector<int> a(n + 1); 65 for (int i = 1; i <= n; i++) { 66 cin >> a[i]; 67 } 68 long long ans = -1e12; 69 int l = max(1, n - 2 * k); 70 for (int i = l; i <= n; i++) { 71 for (int j = i + 1; j <= n; j++) { 72 ans = max(ans, 1LL * i * j - 1LL * k * (a[i] | a[j])); 73 } 74 } 75 cout << ans << '\n'; 76 } 77 return 0; 78 } 79 ``` 80 81 **Code(Python)** 82 83 ``` 84 import sys 85 input = sys.stdin.buffer.readline 86 t = int(input()) 87 for _ in range(t): 88 n, k = map(int, input().split()) 89 a = list(map(int, input().split())) 90 l = max(0, n - 2 * k - 1) 91 ans = -1e12 92 for i in range(l, n): 93 for j in range(i + 1, n): 94 ans = max(ans, (i + 1) * (j + 1) - k * (a[i] | a[j])) 95 print(ans) 96 ``` 97 98 Tutorial is loading... 99 100 **Code(C++)** 101 102 ``` 103 #include<bits/stdc++.h> 104 using namespace std; 105 106 int32_t main() { 107 ios_base::sync_with_stdio(0); 108 cin.tie(0); 109 int t; cin >> t; 110 while (t--) { 111 int n, m; cin >> n >> m; 112 ++m; 113 int ans = 0; 114 for (int k = 30; k >= 0 and n < m; k--) { 115 if ((n >> k & 1) == (m >> k & 1)) continue; 116 if (m >> k & 1) ans |= 1 << k, n |= 1 << k; 117 } 118 cout << ans << '\n'; 119 } 120 return 0; 121 } 122 ``` 123 124 **Code(Python)** 125 126 ``` 127 import sys 128 input = sys.stdin.buffer.readline 129 t = int(input()) 130 for _ in range(t): 131 n, m = map(int, input().split()) 132 m += 1 133 ans = 0 134 for k in range(30, -1, -1): 135 if (n >= m): break 136 if ((n >> k & 1) == (m >> k & 1)): continue 137 if (m >> k & 1): 138 ans |= 1 << k 139 n |= 1 << k 140 print(ans) 141 ``` 142 143 Tutorial is loading... 144 145 **Code(C++)** 146 147 ``` 148 #include<bits/stdc++.h> 149 using namespace std; 150 151 int32_t main() { 152 ios_base::sync_with_stdio(0); 153 cin.tie(0); 154 int t; cin >> t; 155 while (t--) { 156 int n; cin >> n; 157 if (n == 1) { 158 cout << "a\n"; 159 } 160 else { 161 cout << string(n / 2, 'a') + (n & 1 ? "bc" : "b") + string(n / 2 - 1, 'a') << '\n'; 162 } 163 } 164 return 0; 165 } 166 ``` 167 168 **Code(Python)** 169 170 ``` 171 t = int(input()) 172 for _ in range(t): 173 n = int(input()) 174 if (n == 1): 175 print('a') 176 else: 177 s = 'a' * (n // 2) 178 if (n & 1): 179 s += 'bc' 180 else: 181 s += 'b' 182 s += 'a' * (n // 2 - 1) 183 print(s) 184 ``` 185 186 If you are wondering(as you always do 。^‿^。) about the checker: 187 188 **Checker** 189 190 Write a suffix automata and check if every node occurs an odd number of times. 191 192 **Code** 193 194 ``` 195 #include<bits/stdc++.h> 196 #include "testlib.h" 197 using namespace std; 198 199 // len -> largest string length of the corresponding endpos-equivalent class 200 // link -> longest suffix that is another endpos-equivalent class. 201 // firstpos -> 1 indexed end position of the first occurrence of the largest string of that node 202 // minlen(v) -> smallest string of node v = len(link(v)) + 1 203 // terminal nodes -> store the suffixes 204 struct SuffixAutomaton { 205 struct node { 206 int len, link, firstpos; 207 map<char, int> nxt; 208 }; 209 int sz, last; 210 vector<node> t; 211 vector<int> terminal; 212 vector<int> dp; 213 vector<vector<int>> g; 214 SuffixAutomaton() {} 215 SuffixAutomaton(int n) { 216 t.resize(2 * n); terminal.resize(2 * n, 0); 217 dp.resize(2 * n, -1); sz = 1; last = 0; 218 g.resize(2 * n); 219 t[0].len = 0; t[0].link = -1; t[0].firstpos = 0; 220 } 221 void extend(char c) { 222 int p = last; 223 int cur = sz++; 224 t[cur].len = t[last].len + 1; 225 t[cur].firstpos = t[cur].len; 226 p = last; 227 while (p != -1 && !t[p].nxt.count(c)) { 228 t[p].nxt[c] = cur; 229 p = t[p].link; 230 } 231 if (p == -1) t[cur].link = 0; 232 else { 233 int q = t[p].nxt[c]; 234 if (t[p].len + 1 == t[q].len) t[cur].link = q; 235 else { 236 int clone = sz++; 237 t[clone] = t[q]; 238 t[clone].len = t[p].len + 1; 239 while (p != -1 && t[p].nxt[c] == q) { 240 t[p].nxt[c] = clone; 241 p = t[p].link; 242 } 243 t[q].link = t[cur].link = clone; 244 } 245 } 246 last = cur; 247 } 248 void build_tree() { 249 for (int i = 1; i < sz; i++) g[t[i].link].push_back(i); 250 } 251 void build(string &s) { 252 for (auto x: s) { 253 extend(x); 254 terminal[last] = 1; 255 } 256 build_tree(); 257 } 258 int cnt(int i) { // number of times i-th node occurs in the string 259 if (dp[i] != -1) return dp[i]; 260 int ret = terminal[i]; 261 for (auto &x: g[i]) ret += cnt(x); 262 return dp[i] = ret; 263 } 264 }; 265 pair<int, int> ok(string s) { 266 int n = s.size(); 267 SuffixAutomaton sa(n); 268 sa.build(s); 269 for (int i = 1; i < sa.sz; i++) { 270 if (sa.cnt(i) % 2 == 0) { 271 return {sa.t[i].firstpos - sa.t[i].len, sa.t[i].firstpos - 1}; 272 } 273 } 274 return {-1, -1}; 275 } 276 int main(int argc, char* argv[]) { 277 registerTestlibCmd(argc, argv); 278 int t = inf.readInt(); 279 inf.readEoln(); 280 for (int test = 1; test <= t; test++) { 281 setTestCase(test); 282 int n = inf.readInt(); 283 inf.readEoln(); 284 string s = ouf.readToken(); 285 if (s.size() != n) { 286 quitf(_wa, "the length of s should be exactly %d", n); 287 } 288 for (int i = 0; i < n; i++) { 289 if (!(s[i] >= 'a' and s[i] <= 'z')) { 290 quitf(_wa, "s contains %c which is not an English lowercase character", s[i]); 291 } 292 } 293 auto p = ok(s); 294 if (p.first != -1) { 295 quitf(_wa, "the substring s[%d, %d] (0-indexed) occurs even number of times in s :\"(", p.first, p.second); 296 } 297 } 298 quitf(_ok, "you are the best problem solver ever UwU"); 299 return 0; 300 } 301 ``` 302 303 Tutorial is loading... 304 305 **Code(C++)** 306 307 ``` 308 #include<bits/stdc++.h> 309 using namespace std; 310 311 const int N = 1e5 + 9, mod = 998244353; 312 313 vector<int> g[N]; 314 int dp[N], d, ok, ans[N]; 315 void dfs(int u, int p = 0) { 316 if (!ok) return; 317 for (auto v: g[u]) { 318 if (v ^ p) { 319 dfs(v, u); 320 } 321 } 322 if (dp[u] % d != 0) { 323 if (p) { 324 dp[u]++; 325 } 326 if (dp[u] % d != 0) { 327 ok = 0; 328 return; 329 } 330 } 331 else { 332 dp[p]++; 333 } 334 } 335 int32_t main() { 336 ios_base::sync_with_stdio(0); 337 cin.tie(0); 338 int t; cin >> t; 339 while (t--) { 340 int n; cin >> n; 341 for (int i = 1; i < n; i++) { 342 int u, v; cin >> u >> v; 343 g[u].push_back(v); 344 g[v].push_back(u); 345 } 346 for (int i = 1; i <= n; i++) { 347 ans[i] = 0; 348 } 349 ans[1] = 1; 350 for (int k = 1; k <= n - 1; k++) { 351 ans[1] = (ans[1] + ans[1]) % mod; 352 } 353 for (d = 2; d <= n - 1; d++) { 354 if ((n - 1) % d == 0) { 355 ok = 1; 356 dfs(1); 357 ans[d] = ok; 358 for (int i = 0; i <= n; i++) { 359 dp[i] = 0; 360 } 361 } 362 } 363 for (int i = n; i >= 1; i--) { 364 for (int j = i + i; j <= n; j += i) { 365 ans[i] = (ans[i] - ans[j] + mod) % mod; 366 } 367 } 368 for (int i = 1; i <= n; i++) { 369 if (i > 1) cout << ' '; 370 cout << ans[i]; 371 } 372 cout << '\n'; 373 for (int i = 1; i <= n; i++) { 374 g[i].clear(); 375 } 376 } 377 return 0; 378 } 379 ```