1722.md (8046B)
1 Source: https://codeforces.com/blog/entry/106478 2 3 Thanks for participating! 4 5 [1722A - Проверка правописания](/contest/1722/problem/A "Codeforces Round 817 (Div. 4)") 6 7 Idea: [mesanu](/profile/mesanu "Эксперт mesanu"), [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 8 9 **Tutorial** 10 11 ### [1722A - Проверка правописания](/contest/1722/problem/A "Codeforces Round 817 (Div. 4)") 12 13 Check if the string has length 5 and if it has the characters $\texttt{T}, \texttt{i}, \texttt{m}, \texttt{u}, \texttt{r}$. The complexity is $\mathcal{O}(n)$. 14 15 You can also sort the string, and check if it is $\texttt{Timur}$ when sorted (which is $\texttt{Timru}$). 16 17 **Solution** 18 19 ``` 20 #include <bits/stdc++.h> 21 22 using namespace std; 23 24 #define forn(i, n) for (int i = 0; i < int(n); i++) 25 26 int main() { 27 string name = "Timur"; 28 sort(name.begin(), name.end()); 29 30 int n; 31 cin >> n; 32 forn(i, n) { 33 int m; 34 cin >> m; 35 string s; 36 cin >> s; 37 sort(s.begin(), s.end()); 38 cout << (s == name ? "YES" : "NO") << endl; 39 } 40 } 41 ``` 42 43 [1722B - Дальтонизм](/contest/1722/problem/B "Codeforces Round 817 (Div. 4)") 44 45 Idea: [flamestorm](/profile/flamestorm "Эксперт flamestorm") 46 47 **Tutorial** 48 49 Tutorial is loading... 50 51 **Solution** 52 53 ``` 54 #include <bits/stdc++.h> 55 56 using namespace std; 57 58 const int MAX = 200007; 59 const int MOD = 1000000007; 60 61 void solve() { 62 int n; 63 cin >> n; 64 string s, t; 65 cin >> s >> t; 66 for (int i = 0; i < n; i++) { 67 if (s[i] == 'R') { 68 if (t[i] != 'R') {cout << "NO\n"; return;} 69 } 70 else { 71 if (t[i] == 'R') {cout << "NO\n"; return;} 72 } 73 } 74 cout << "YES\n"; 75 } 76 77 int main() { 78 ios::sync_with_stdio(false); 79 cin.tie(nullptr); 80 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 81 // solve(); 82 } 83 ``` 84 85 [1722C - Игра в слова](/contest/1722/problem/C "Codeforces Round 817 (Div. 4)") 86 87 Idea: [flamestorm](/profile/flamestorm "Эксперт flamestorm") 88 89 **Tutorial** 90 91 Tutorial is loading... 92 93 **Solution** 94 95 ``` 96 #include <bits/stdc++.h> 97 98 using namespace std; 99 100 const int MAX = 200007; 101 const int MOD = 1000000007; 102 103 void solve() { 104 int n; 105 cin >> n; 106 map<string, int> mp; 107 string a[3][n]; 108 for (int i = 0; i < 3; i++) { 109 for (int j = 0; j < n; j++) { 110 cin >> a[i][j]; 111 mp[a[i][j]]++; 112 } 113 } 114 for (int i = 0; i < 3; i++) { 115 int tot = 0; 116 for (int j = 0; j < n; j++) { 117 if (mp[a[i][j]] == 1) {tot += 3;} 118 else if (mp[a[i][j]] == 2) {tot++;} 119 } 120 cout << tot << ' '; 121 } 122 cout << '\n'; 123 } 124 125 int main() { 126 ios::sync_with_stdio(false); 127 cin.tie(nullptr); 128 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 129 // solve(); 130 } 131 ``` 132 133 [1722D - Ряд](/contest/1722/problem/D "Codeforces Round 817 (Div. 4)") 134 135 Idea: [flamestorm](/profile/flamestorm "Эксперт flamestorm") 136 137 **Tutorial** 138 139 Tutorial is loading... 140 141 **Solution** 142 143 ``` 144 #include <bits/stdc++.h> 145 146 using namespace std; 147 148 const int MAX = 200007; 149 const int MOD = 1000000007; 150 151 void solve() { 152 int n; 153 cin >> n; 154 string s; 155 cin >> s; 156 long long tot = 0; 157 vector<long long> v; 158 for (int i = 0; i < n; i++) { 159 if (s[i] == 'L') { 160 v.push_back((n - 1 - i) - i); 161 tot += i; 162 } 163 else { 164 v.push_back(i - (n - 1 - i)); 165 tot += n - 1 - i; 166 } 167 } 168 sort(v.begin(), v.end(), greater<int>()); 169 for (int i = 0; i < n; i++) { 170 if (v[i] > 0) {tot += v[i];} 171 cout << tot << ' '; 172 } 173 cout << '\n'; 174 } 175 176 int main() { 177 ios::sync_with_stdio(false); 178 cin.tie(nullptr); 179 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 180 // solve(); 181 } 182 ``` 183 184 [1722E - Считаем прямоугольники](/contest/1722/problem/E "Codeforces Round 817 (Div. 4)") 185 186 Idea: [mesanu](/profile/mesanu "Эксперт mesanu") 187 188 **Tutorial** 189 190 Tutorial is loading... 191 192 You can read about [2D prefix sums](https://usaco.guide/silver/more-prefix-sums?lang=cpp#2d-prefix-sums) if you haven't heard of them before. 193 194 **Solution** 195 196 ``` 197 #include <bits/stdc++.h> 198 199 using namespace std; 200 201 long long a[1005][1005]; 202 long long pref[1005][1005]; 203 204 void solve() 205 { 206 long long n, q; 207 cin >> n >> q; 208 for(int i = 0; i <= 1001; i++) 209 { 210 for(int j = 0; j <= 1001; j++) 211 { 212 a[i][j] = pref[i][j] = 0; 213 } 214 } 215 for(int i = 0; i < n; i++) 216 { 217 long long h, w; 218 cin >> h >> w; 219 a[h][w]+=h*w; 220 } 221 for(int i = 1; i <= 1000; i++) 222 { 223 for(int j = 1; j <= 1000; j++) 224 { 225 pref[i][j] = pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j]; 226 } 227 } 228 for(int i = 0; i < q; i++) 229 { 230 long long hs, ws, hb, wb; 231 cin >> hs >> ws >> hb >> wb; 232 cout << pref[hb-1][wb-1]-pref[hb-1][ws]-pref[hs][wb-1]+pref[hs][ws] << endl; 233 } 234 } 235 236 int main() { 237 int t = 1; 238 cin >> t; 239 while(t--) 240 { 241 solve(); 242 } 243 } 244 ``` 245 246 [1722F - L-фигуры](/contest/1722/problem/F "Codeforces Round 817 (Div. 4)") 247 248 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 249 250 **Tutorial** 251 252 Tutorial is loading... 253 254 **Solution** 255 256 ``` 257 #include <bits/stdc++.h> 258 259 using namespace std; 260 261 const int MAX = 200007; 262 const int MOD = 1000000007; 263 264 const int dx[3] = {-1, 0, 1}, dy[3] = {-1, 0, 1}; 265 266 void solve() { 267 int n, m; 268 cin >> n >> m; 269 char g[n][m]; 270 int id[n][m]; 271 for (int i = 0; i < n; i++) { 272 for (int j = 0; j < m; j++) { 273 cin >> g[i][j]; 274 id[i][j] = 0; 275 } 276 } 277 int curr = 1; 278 for (int i = 0; i < n; i++) { 279 for (int j = 0; j < m; j++) { 280 if (g[i][j] == '*') { 281 vector<pair<int, int>> adjh, adjv; 282 if (i > 0 && g[i - 1][j] == '*') { 283 adjh.emplace_back(i - 1, j); 284 } 285 if (i < n - 1 && g[i + 1][j] == '*') { 286 adjh.emplace_back(i + 1, j); 287 } 288 if (j > 0 && g[i][j - 1] == '*') { 289 adjv.emplace_back(i, j - 1); 290 } 291 if (j < m - 1 && g[i][j + 1] == '*') { 292 adjv.emplace_back(i, j + 1); 293 } 294 if (adjh.size() == 1 && adjv.size() == 1) { 295 if (id[i][j] == 0) {id[i][j] = curr;} 296 else {cout << "NO\n"; return;} 297 if (id[adjh[0].first][adjh[0].second] == 0) {id[adjh[0].first][adjh[0].second] = curr;} 298 else {cout << "NO\n"; return;} 299 if (id[adjv[0].first][adjv[0].second] == 0) {id[adjv[0].first][adjv[0].second] = curr;} 300 else {cout << "NO\n"; return;} 301 curr++; 302 } 303 else if (adjh.size() > 1 || adjv.size() > 1) { 304 cout << "NO\n"; return; 305 } 306 } 307 } 308 } 309 for (int i = 0; i < n; i++) { 310 for (int j = 0; j < m; j++) { 311 if (g[i][j] == '*') { 312 if (id[i][j] == 0) {cout << "NO\n"; return;} 313 else { 314 for (int x = 0; x < 3; x++) { 315 for (int y = 0; y < 3; y++) { 316 if (0 <= i + dx[x] && i + dx[x] < n) { 317 if (0 <= j + dy[y] && j + dy[y] < m) { 318 if (id[i + dx[x]][j + dy[y]] != id[i][j] && id[i + dx[x]][j + dy[y]] != 0) { 319 cout << "NO\n"; return; 320 } 321 } 322 } 323 } 324 } 325 } 326 } 327 } 328 } 329 cout << "YES\n"; 330 } 331 332 int main() { 333 ios::sync_with_stdio(false); 334 cin.tie(nullptr); 335 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 336 // solve(); 337 } 338 ``` 339 340 [1722G - Чётный-нечётный XOR](/contest/1722/problem/G "Codeforces Round 817 (Div. 4)") 341 342 Idea: [mesanu](/profile/mesanu "Эксперт mesanu") 343 344 **Tutorial** 345 346 Tutorial is loading... 347 348 **Alternate Tutorial Sketch** 349 350 Output the integers from $1$ to $n-3$, then $2^{29}$, $2^{30}$, and the XOR of those $n-1$ numbers. Why does it work? 351 352 **Solution** 353 354 ``` 355 #include <bits/stdc++.h> 356 357 using namespace std; 358 359 void solve() 360 { 361 int n; 362 cin >> n; 363 int case1 = 0; 364 int case2 = 0; 365 for(int i = 0; i < n-2; i++) 366 { 367 case1^=i; 368 case2^=(i+1); 369 } 370 long long addLast = ((long long)1<<31)-1; 371 if(case1 != 0) 372 { 373 for(int i = 0; i < n-2; i++) 374 { 375 cout << i << " "; 376 } 377 case1^=addLast; 378 cout << addLast << " " << case1 << endl; 379 } 380 else 381 { 382 for(int i = 1; i <= n-2; i++) 383 { 384 cout << i << " "; 385 } 386 case2^=addLast; 387 cout << addLast << " " << case2 << endl; 388 } 389 } 390 391 int main() 392 { 393 int t = 1; 394 cin >> t; 395 while(t--) 396 { 397 solve(); 398 } 399 } 400 ```