1393.md (8738B)
1 Source: https://codeforces.com/blog/entry/81161 2 3 [1393A - Rainbow Dash, Fluttershy and Chess Coloring](/contest/1393/problem/A "Codeforces Round 662 (Div. 2)") 4 5 Idea: [AlFlen](/profile/AlFlen "Master AlFlen") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (74TrAkToR)** 12 13 ``` 14 #include<bits/stdc++.h> 15 16 using namespace std; 17 18 main() { 19 ios_base::sync_with_stdio(0); 20 cin.tie(0); 21 cout.tie(0); 22 int t, n; 23 cin >> t; 24 while (t--) { 25 cin >> n; 26 cout << n / 2 + 1 << '\n'; 27 } 28 return 0; 29 } 30 ``` 31 32 [1393B - Applejack and Storages](/contest/1393/problem/B "Codeforces Round 662 (Div. 2)") 33 34 Idea: [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR") 35 36 **Tutorial** 37 38 Tutorial is loading... 39 40 **Solution (74TrAkToR)** 41 42 ``` 43 #include<bits/stdc++.h> 44 45 using namespace std; 46 47 int const MAXN = 1e5 + 5; 48 int cnt[MAXN]; 49 50 main() { 51 ios_base::sync_with_stdio(0); 52 cin.tie(0); 53 cout.tie(0); 54 55 int n, q, x, cnt2 = 0, cnt4 = 0; 56 char type; 57 cin >> n; 58 59 for (int i = 1; i <= n; ++i) { 60 cin >> x; 61 62 cnt2 -= cnt[x] / 2; 63 cnt4 -= cnt[x] / 4; 64 cnt[x]++; 65 cnt2 += cnt[x] / 2; 66 cnt4 += cnt[x] / 4; 67 } 68 69 cin >> q; 70 71 for (int i = 1; i <= q; ++i) { 72 cin >> type >> x; 73 cnt2 -= cnt[x] / 2; 74 cnt4 -= cnt[x] / 4; 75 76 if (type == '+') cnt[x]++; 77 else cnt[x]--; 78 79 cnt2 += cnt[x] / 2; 80 cnt4 += cnt[x] / 4; 81 82 if (cnt4 >= 1 && cnt2 >= 4) cout << "YES" << '\n'; 83 else cout << "NO" << '\n'; 84 } 85 86 return 0; 87 } 88 ``` 89 90 [1393C - Pinkie Pie Eats Patty-cakes](/contest/1393/problem/C "Codeforces Round 662 (Div. 2)") 91 92 Idea: [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR") и [lapochka_queen](/profile/lapochka_queen "Unrated, lapochka_queen") 93 94 **Tutorial** 95 96 Tutorial is loading... 97 98 **Solution (AlFlen)** 99 100 ``` 101 #include <bits/stdc++.h> 102 103 using namespace std; 104 105 const int MAXN = 100009; 106 int cnt[MAXN]; 107 vector<int> a; 108 int n; 109 110 bool check(int x) { 111 for (int i = 1; i <= n; i ++) cnt[i] = 0; 112 for (int i = 0; i < n; i ++) cnt[a[i]]++; 113 114 set<pair<int, int>, greater<pair<int, int>>> ss; //use greater comparator to sort set in descending order 115 for (int i = 1; i <= n; i ++) { 116 if (cnt[i] > 0) ss.insert({cnt[i], i}); 117 } 118 119 vector<int> b; 120 for (int i = 0; i < n; i ++) { 121 if (i >= x && cnt[b[i - x]]) { 122 ss.insert({cnt[b[i - x]], b[i - x]}); 123 } 124 125 if (ss.empty()) return 0; 126 b.push_back(ss.begin()->second); 127 ss.erase(ss.begin()); 128 cnt[b.back()]--; 129 } 130 131 return 1; 132 } 133 134 signed main() { 135 ios :: sync_with_stdio(0); 136 cin.tie(0); 137 138 int ttt; 139 cin >> ttt; 140 141 while (ttt--) { 142 cin >> n; 143 144 a.resize(n); 145 for (int i = 0; i < n; i ++) { 146 cin >> a[i]; 147 } 148 149 int l = 0, r = n; 150 while (r - l > 1) { 151 int m = (r + l) / 2; 152 if (check(m)) { 153 l = m; 154 } 155 156 else { 157 r = m; 158 } 159 } 160 161 cout << l - 1 << "\n"; 162 } 163 164 return 0; 165 } 166 ``` 167 168 [1393D - Rarity and New Dress](/contest/1393/problem/D "Codeforces Round 662 (Div. 2)") 169 170 Idea: [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR") 171 172 **Tutorial** 173 174 Tutorial is loading... 175 176 **Solution (74TrAkToR)** 177 178 ``` 179 #include<bits/stdc++.h> 180 181 using namespace std; 182 183 typedef long long ll; 184 int const maxn = 2005; 185 char a[maxn][maxn]; 186 int cnt_up[maxn][maxn], cnt_down[maxn][maxn], L[maxn], R[maxn]; 187 188 main() { 189 ios_base::sync_with_stdio(0); 190 cin.tie(0); 191 cout.tie(0); 192 int n, m; 193 cin >> n >> m; 194 for (int i = 1; i <= n; ++i) { 195 for (int j = 1; j <= m; ++j) cin >> a[i][j]; 196 } 197 ll ans = 0; 198 for (int i = 1; i <= n; ++i) { 199 for (int j = 1; j <= m; ++j) { 200 if (i != 1 && a[i][j] == a[i - 1][j]) cnt_up[i][j] = cnt_up[i - 1][j] + 1; 201 else cnt_up[i][j] = 0; 202 } 203 } 204 for (int i = n; i >= 1; --i) { 205 for (int j = 1; j <= m; ++j) { 206 if (i != n && a[i][j] == a[i + 1][j]) cnt_down[i][j] = cnt_down[i + 1][j] + 1; 207 else cnt_down[i][j] = 0; 208 } 209 } 210 for (int i = 1; i <= n; ++i) { 211 for (int j = 1; j <= m; ++j) { 212 int go = j; 213 while (go <= m && a[i][j] == a[i][go]) go++; 214 go--; 215 for (int pos = j; pos <= go; ++pos) { 216 if (pos == j) L[pos] = pos; 217 else { 218 L[pos] = max(L[pos - 1], pos - min(cnt_up[i][pos], cnt_down[i][pos])); 219 } 220 } 221 j = go; 222 } 223 for (int j = m; j >= 1; --j) { 224 int go = j; 225 while (go >= 1 && a[i][j] == a[i][go]) go--; 226 go++; 227 for (int pos = j; pos >= go; --pos) { 228 if (pos == j) R[pos] = pos; 229 else { 230 R[pos] = min(R[pos + 1], pos + min(cnt_up[i][pos], cnt_down[i][pos])); 231 } 232 } 233 j = go; 234 } 235 for (int j = 1; j <= m; ++j) { 236 ans += (ll)min(j - L[j] + 1, R[j] - j + 1); 237 } 238 } 239 cout << ans << '\n'; 240 return 0; 241 } 242 ``` 243 244 [1393E2 - Twilight and Ancient Scroll (harder version)](/contest/1393/problem/E2 "Codeforces Round 662 (Div. 2)") 245 246 Idea: [AlFlen](/profile/AlFlen "Master AlFlen") 247 248 **Tutorial** 249 250 Tutorial is loading... 251 252 **Solution (74TrAkToR)** 253 254 ``` 255 #include<bits/stdc++.h> 256 257 using namespace std; 258 259 typedef long long ll; 260 int const maxn = 1e5 + 5, maxc = 1e6 + 5; 261 ll mod[2], P[2], p[2][maxc], rev_P[2]; 262 vector < ll > h[2][maxn]; 263 vector < int > sorted[maxn]; 264 string s[maxn]; 265 int nxt[maxc]; 266 int a[maxc], dp[2][maxc], inf = 1e9 + 7; 267 int MOD = 1e9 + 7; 268 269 ll st(ll x, int y, int ok) { 270 if (y == 0) return 1; 271 if (y % 2 == 0) { 272 ll d = st(x, y / 2, ok); 273 return d * d % mod[ok]; 274 } 275 return x * st(x, y - 1, ok) % mod[ok]; 276 } 277 278 inline char get_c(int i, int x, int numb) { 279 if (numb < x) return s[i][numb]; 280 if (numb + 1 < (int)s[i].size()) return s[i][numb + 1]; 281 return ' '; 282 } 283 284 inline ll get_hash(int t, int i, int x, int len) { 285 if (len < x) return h[t][i][len]; 286 return (h[t][i][x] + (h[t][i][len + 1] - h[t][i][x + 1] + mod[t]) * rev_P[t]) % mod[t]; 287 } 288 289 inline pair < ll, ll > get_h(int i, int x, int len) { 290 return {get_hash(0, i, x, len), get_hash(1, i, x, len)}; 291 } 292 293 inline int check(int i, int x, int j, int y) { 294 int len1 = (int)s[i].size(), len2 = (int)s[j].size(); 295 if (x != len1) len1--; 296 if (y != len2) len2--; 297 int lef = 0, righ = min(len1, len2) + 1; 298 while (righ - lef > 1) { 299 int mid = (righ + lef) / 2; 300 if (get_h(i, x, mid) == get_h(j, y, mid)) lef = mid; 301 else righ = mid; 302 } 303 return get_c(i, x, lef) >= get_c(j, y, lef); 304 } 305 306 main() { 307 ios_base::sync_with_stdio(0); 308 cin.tie(0); 309 cout.tie(0); 310 mod[0] = 1e9 + 7, mod[1] = 1e9 + 9, P[0] = 29, P[1] = 31, rev_P[0] = st(P[0], mod[0] - 2, 0), rev_P[1] = st(P[1], mod[1] - 2, 1); 311 p[0][0] = 1, p[1][0] = 1; 312 for (int i = 1; i < maxc; ++i) { 313 for (int j = 0; j <= 1; ++j) p[j][i] = p[j][i - 1] * P[j] % mod[j]; 314 } 315 int n; 316 cin >> n; 317 for (int i = 1; i <= n; ++i) { 318 cin >> s[i]; 319 for (int j = 0; j <= 1; ++j) { 320 h[j][i].push_back(0); 321 for (int pos = 0; pos < (int)s[i].size(); ++pos) { 322 h[j][i].push_back((h[j][i][pos] + p[j][pos] * (s[i][pos] - 'a' + 1)) % mod[j]); 323 } 324 } 325 nxt[(int)s[i].size() - 1] = (int)s[i].size() - 1; 326 for (int pos = (int)s[i].size() - 2; pos >= 0; --pos) { 327 if (s[i][pos] != s[i][pos + 1]) nxt[pos] = pos + 1; 328 else nxt[pos] = nxt[pos + 1]; 329 } 330 int l = 0, r = (int)s[i].size() - 1; 331 for (int j = 0; j < (int)s[i].size(); ++j) { 332 if (s[i][nxt[j]] <= s[i][j]) a[l++] = j; 333 else a[r--] = j; 334 } 335 for (int j = 0; j < (int)s[i].size(); ++j) { 336 sorted[i].push_back(a[j]); 337 if (a[j] == (int)s[i].size() - 1) sorted[i].push_back((int)s[i].size()); 338 } 339 } 340 for (int i = 0; i <= (int)s[1].size(); ++i) { 341 dp[0][i] = 1; 342 } 343 for (int i = 2; i <= n; ++i) { 344 int oks = (i - 1) % 2, ptr = 0, sum = 0, cur = -1; 345 for (auto key : sorted[i]) { 346 cur++; 347 while (ptr < (int)sorted[i - 1].size() && check(i, key, i - 1, sorted[i - 1][ptr])) { 348 sum += dp[(1^oks)][ptr]; 349 if (sum >= MOD) sum -= MOD; 350 ptr++; 351 } 352 dp[oks][cur] = sum; 353 } 354 } 355 int ans = 0; 356 for (int i = 0; i <= (int)s[n].size(); ++i) { 357 ans += dp[(n - 1) % 2][i]; 358 if (ans >= MOD) ans -= MOD; 359 } 360 cout << ans << '\n'; 361 return 0; 362 } 363 ```