1029.md (5800B)
1 Source: https://codeforces.com/blog/entry/61439 2 3 [1029A - Many Equal Substrings](/contest/1029/problem/A "Codeforces Round 506 (Div. 3)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (Vovuh, O(n^2))** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 #define sz(a) int((a).size()) 17 18 int main() { 19 #ifdef _DEBUG 20 freopen("input.txt", "r", stdin); 21 // freopen("output.txt", "w", stdout); 22 #endif 23 24 int n, k; 25 string t; 26 cin >> n >> k >> t; 27 28 int cnt = 1; 29 int pos = 1; 30 string ans = t; 31 while (cnt < k) { 32 if (pos >= sz(ans)) { 33 ans += t; 34 ++cnt; 35 } else { 36 bool ok = true; 37 int len = 0; 38 for (int i = 0; i < sz(t); ++i) { 39 if (pos + i >= sz(ans)) break; 40 ++len; 41 if (ans[pos + i] != t[i]) ok = false; 42 } 43 if (ok) { 44 ans += t.substr(len); 45 ++cnt; 46 } 47 } 48 ++pos; 49 } 50 51 cout << ans << endl; 52 53 return 0; 54 } 55 ``` 56 57 **Solution (Vovuh, prefix-function)** 58 59 ``` 60 #include <bits/stdc++.h> 61 62 using namespace std; 63 64 #define sz(a) int((a).size()) 65 66 int main() { 67 #ifdef _DEBUG 68 freopen("input.txt", "r", stdin); 69 // freopen("output.txt", "w", stdout); 70 #endif 71 72 int n, k; 73 string t; 74 cin >> n >> k >> t; 75 76 vector<int> p(n); 77 for (int i = 1; i < sz(t); ++i) { 78 int j = p[i - 1]; 79 while (j > 0 && t[j] != t[i]) 80 j = p[j - 1]; 81 if (t[i] == t[j]) 82 ++j; 83 p[i] = j; 84 } 85 86 int len = sz(t) - p[n - 1]; 87 88 for (int i = 0; i < k - 1; ++i) 89 cout << t.substr(0, len); 90 cout << t << endl; 91 92 return 0; 93 } 94 ``` 95 96 [1029B - Creating the Contest](/contest/1029/problem/B "Codeforces Round 506 (Div. 3)") 97 98 **Tutorial** 99 100 Tutorial is loading... 101 102 **Solution (Vovuh)** 103 104 ``` 105 #include <bits/stdc++.h> 106 107 using namespace std; 108 109 int main() { 110 #ifdef _DEBUG 111 freopen("input.txt", "r", stdin); 112 #endif 113 114 int n; 115 scanf("%d", &n); 116 vector<int> a(n); 117 for (int i = 0; i < n; ++i) 118 scanf("%d", &a[i]); 119 120 int ans = 0; 121 for (int i = 0; i < n; ++i) { 122 int j = i; 123 while (j + 1 < n && a[j + 1] <= a[j] * 2) 124 ++j; 125 ans = max(ans, j - i + 1); 126 i = j; 127 } 128 129 printf("%d\n", ans); 130 } 131 ``` 132 133 [1029C - Maximal Intersection](/contest/1029/problem/C "Codeforces Round 506 (Div. 3)") 134 135 **Tutorial** 136 137 Tutorial is loading... 138 139 **Solution (PikMike)** 140 141 ``` 142 #include <bits/stdc++.h> 143 144 #define forn(i, n) for (int i = 0; i < int(n); i++) 145 146 using namespace std; 147 148 const int N = 300 * 1000 + 13; 149 const int INF = int(1e9); 150 151 int n; 152 int prl[N], prr[N], sul[N], sur[N]; 153 int l[N], r[N]; 154 155 int main() { 156 scanf("%d", &n); 157 forn(i, n) 158 scanf("%d%d", &l[i], &r[i]); 159 160 prl[0] = sul[n] = 0; 161 prr[0] = sur[n] = INF; 162 163 forn(i, n){ 164 prl[i + 1] = max(prl[i], l[i]); 165 prr[i + 1] = min(prr[i], r[i]); 166 } 167 168 for (int i = n - 1; i >= 0; --i){ 169 sul[i] = max(sul[i + 1], l[i]); 170 sur[i] = min(sur[i + 1], r[i]); 171 } 172 173 int ans = 0; 174 forn(i, n) 175 ans = max(ans, min(prr[i], sur[i + 1]) - max(prl[i], sul[i + 1])); 176 printf("%d\n", ans); 177 return 0; 178 } 179 ``` 180 181 [1029D - Concatenated Multiples](/contest/1029/problem/D "Codeforces Round 506 (Div. 3)") 182 183 **Tutorial** 184 185 Tutorial is loading... 186 187 **Solution (PikMike)** 188 189 ``` 190 #include <bits/stdc++.h> 191 192 #define forn(i, n) for (int i = 0; i < int(n); i++) 193 194 typedef long long li; 195 196 using namespace std; 197 198 const int N = 200 * 1000 + 13; 199 const int LOGN = 11; 200 201 int n, k; 202 int a[N]; 203 int len[N]; 204 vector<int> rems[LOGN]; 205 int pw[LOGN]; 206 207 int main() { 208 scanf("%d%d", &n, &k); 209 forn(i, n) scanf("%d", &a[i]); 210 211 pw[0] = 1; 212 forn(i, LOGN - 1) 213 pw[i + 1] = pw[i] * 10 % k; 214 215 forn(i, n){ 216 int x = a[i]; 217 while (x > 0){ 218 ++len[i]; 219 x /= 10; 220 } 221 rems[len[i]].push_back(a[i] % k); 222 } 223 224 forn(i, LOGN) 225 sort(rems[i].begin(), rems[i].end()); 226 227 li ans = 0; 228 forn(i, n){ 229 for (int j = 1; j < LOGN; ++j){ 230 int rem = (a[i] * li(pw[j])) % k; 231 int xrem = (k - rem) % k; 232 auto l = lower_bound(rems[j].begin(), rems[j].end(), xrem); 233 auto r = upper_bound(rems[j].begin(), rems[j].end(), xrem); 234 ans += (r - l); 235 if (len[i] == j && (rem + a[i] % k) % k == 0) 236 --ans; 237 } 238 } 239 240 printf("%lld\n", ans); 241 return 0; 242 } 243 ``` 244 245 [1029E - Tree with Small Distances](/contest/1029/problem/E "Codeforces Round 506 (Div. 3)") 246 247 **Tutorial** 248 249 Tutorial is loading... 250 251 **Solution (Vovuh)** 252 253 ``` 254 #include <bits/stdc++.h> 255 256 using namespace std; 257 258 const int N = 200 * 1000 + 11; 259 260 int p[N]; 261 int d[N]; 262 vector<int> g[N]; 263 264 void dfs(int v, int pr = -1, int dst = 0) { 265 d[v] = dst; 266 p[v] = pr; 267 for (auto to : g[v]) { 268 if (to != pr) { 269 dfs(to, v, dst + 1); 270 } 271 } 272 } 273 274 int main() { 275 #ifdef _DEBUG 276 freopen("input.txt", "r", stdin); 277 #endif 278 279 int n; 280 scanf("%d", &n); 281 for (int i = 0; i < n - 1; ++i) { 282 int x, y; 283 scanf("%d %d", &x, &y); 284 --x, --y; 285 g[x].push_back(y); 286 g[y].push_back(x); 287 } 288 289 dfs(0); 290 set<pair<int, int>> st; 291 for (int i = 0; i < n; ++i) { 292 if (d[i] > 2) { 293 st.insert(make_pair(-d[i], i)); 294 } 295 } 296 297 int ans = 0; 298 while (!st.empty()) { 299 int v = st.begin()->second; 300 v = p[v]; 301 ++ans; 302 auto it = st.find(make_pair(-d[v], v)); 303 if (it != st.end()) { 304 st.erase(it); 305 } 306 for (auto to : g[v]) { 307 auto it = st.find(make_pair(-d[to], to)); 308 if (it != st.end()) { 309 st.erase(it); 310 } 311 } 312 } 313 314 printf("%d\n", ans); 315 } 316 ``` 317 318 [1029F - Multicolored Markers](/contest/1029/problem/F "Codeforces Round 506 (Div. 3)") 319 320 **Tutorial** 321 322 Tutorial is loading... 323 324 **Solution (PikMike)** 325 326 ``` 327 #include <bits/stdc++.h> 328 329 #define forn(i, n) for (int i = 0; i < int(n); i++) 330 331 typedef long long li; 332 333 using namespace std; 334 335 const int N = 1000 * 1000; 336 337 int lens[N]; 338 int k; 339 340 li solve(li a, li b){ 341 k = 0; 342 for (li i = 1; i * i <= b; ++i) 343 if (b % i == 0) 344 lens[k++] = i; 345 346 li ans = 2 * (a + b) + 2; 347 li x = a + b; 348 int l = 0; 349 for (li i = 1; i * i <= x; ++i){ 350 if (x % i == 0){ 351 while (l + 1 < k && lens[l + 1] <= i) 352 ++l; 353 if (b / lens[l] <= x / i) 354 ans = min(ans, (i + x / i) * 2); 355 } 356 } 357 358 return ans; 359 } 360 361 int main() { 362 li a, b; 363 scanf("%lld%lld", &a, &b); 364 printf("%lld\n", min(solve(a, b), solve(b, a))); 365 return 0; 366 } 367 ```