1467.md (6889B)
1 Source: https://codeforces.com/blog/entry/86566 2 3 Many thanks to [infinitepro](/profile/infinitepro "Expert infinitepro"), [BledDest](/profile/BledDest "International Grandmaster BledDest") and [alimq](/profile/alimq "Candidate Master alimq") for helping me write the editorials. 4 5 Tutorial is loading... 6 7 **Solution** 8 9 ``` 10 #include <bits/stdc++.h> 11 using namespace std; 12 #define int long long 13 14 int solveTestCase() { 15 int n; 16 cin >> n; 17 18 string s = "989"; 19 if (n <= 3) 20 return cout << s.substr(0, n) << "\n", 0; 21 22 cout << s; 23 for (int i = 3; i < n; i++) 24 cout << (i - 3) % 10; 25 cout << "\n"; 26 } 27 28 signed main() { 29 ios::sync_with_stdio(false); 30 cin.tie(nullptr); 31 cout.tie(nullptr); 32 33 int t = 1; 34 cin >> t; 35 while (t--) 36 solveTestCase(); 37 38 } 39 ``` 40 41 Tutorial is loading... 42 43 **Solution** 44 45 ``` 46 #include <bits/stdc++.h> 47 using namespace std; 48 #define int long long 49 50 const int N = 3e5; 51 int a[N], n; 52 53 int isValley(int i) { 54 return (i > 0 && i < n - 1 && a[i] < a[i - 1] && a[i] < a[i + 1]); 55 } 56 57 int isHill(int i) { 58 return (i > 0 && i < n - 1 && a[i] > a[i - 1] && a[i] > a[i + 1]); 59 } 60 61 int solveTestCase() { 62 cin >> n; 63 for (int i = 0; i < n; i++) 64 cin >> a[i]; 65 66 int is[n] = {}; 67 int s = 0; 68 for (int i = 1; i < n - 1; i++) { 69 if (isHill(i) || isValley(i)) 70 is[i] = 1, s++; 71 } 72 73 int ans = s; 74 for (int i = 1; i < n - 1; i++) { 75 int temp = a[i]; 76 a[i] = a[i - 1]; 77 ans = min(ans, s - is[i - 1] - is[i] - is[i + 1] + isHill(i - 1) + isValley(i - 1) + isHill(i) + isValley(i) + isHill(i + 1) + isValley(i + 1)); 78 a[i] = a[i + 1]; 79 ans = min(ans, s - is[i - 1] - is[i] - is[i + 1] + isHill(i - 1) + isValley(i - 1) + isHill(i) + isValley(i) + isHill(i + 1) + isValley(i + 1)); 80 a[i] = temp; 81 } 82 83 cout << ans << "\n"; 84 } 85 86 signed main() { 87 ios::sync_with_stdio(false); 88 cin.tie(nullptr); 89 cout.tie(nullptr); 90 91 int t = 1; 92 cin >> t; 93 while (t--) 94 solveTestCase(); 95 } 96 ``` 97 98 Tutorial is loading... 99 100 **Solution** 101 102 ``` 103 #include <bits/stdc++.h> 104 using namespace std; 105 #define int long long 106 107 const int N = 3e5; 108 vector<vector<int>> a(3, vector<int>()); 109 vector<int> n(3, 0); 110 111 int calc() { 112 int ans = 0, m1 = a[1][0], m2 = a[2][0], s1 = 0, s2 = 0; 113 for (int i : a[0]) ans += i; 114 for (int i = 1; i < n[1]; i++) s1 += a[1][i]; 115 for (int i = 1; i < n[2]; i++) s2 += a[2][i]; 116 117 ans += max({s2 - m1 + s1 - m2, m2 + s2 - m1 - s1, m1 + s1 - m2 - s2}); 118 return ans; 119 } 120 121 int solveTestCase() { 122 cin >> n[0] >> n[1] >> n[2]; 123 a[0].resize(n[0]); 124 a[1].resize(n[1]); 125 a[2].resize(n[2]); 126 127 for (int i = 0; i < 3; i++) { 128 for (int j = 0; j < n[i]; j++) 129 cin >> a[i][j]; 130 sort(a[i].begin(), a[i].end()); 131 } 132 133 int ans = -1e18; 134 ans = max(ans, calc()); 135 136 swap(a[0], a[1]), swap(n[0], n[1]); 137 ans = max(ans, calc()); 138 139 swap(a[0], a[2]), swap(n[0], n[2]); 140 ans = max(ans, calc()); 141 142 cout << ans; 143 } 144 145 signed main() { 146 ios::sync_with_stdio(false); 147 cin.tie(nullptr); 148 cout.tie(nullptr); 149 150 int t = 1; 151 //cin >> t; 152 while (t--) 153 solveTestCase(); 154 } 155 ``` 156 157 Tutorial is loading... 158 159 **Solution** 160 161 ``` 162 #include <bits/stdc++.h> 163 using namespace std; 164 #define int long long 165 166 const int N = 5005, mod = 1e9 + 7; 167 int dp[N][N], cnt[N], a[N], q, n, k; 168 169 void pre() { 170 for (int i = 0; i < n; i++) 171 dp[i][0] = 1; 172 173 for (int j = 1; j < N; j++) { 174 dp[0][j] = dp[1][j - 1]; 175 for (int i = 1; i < n - 1; i++) 176 dp[i][j] = (dp[i - 1][j - 1] + dp[i + 1][j - 1]) % mod; 177 dp[n - 1][j] = dp[n - 2][j - 1]; 178 } 179 180 for (int i = 0; i < n; i++) { 181 for (int j = 0; j <= k; j++) 182 cnt[i] += dp[i][j] * dp[i][k - j], cnt[i] %= mod; 183 } 184 } 185 186 void solveTestCase() { 187 int ans = 0; 188 for (int i = 0; i < n; i++) 189 cin >> a[i], ans += a[i] * cnt[i], ans %= mod; 190 191 while (q--) { 192 int i, x; 193 cin >> i >> x; 194 i--; 195 196 ans -= (a[i] * cnt[i]) % mod, ans += mod, ans %= mod; 197 198 a[i] = x; 199 ans += (a[i] * cnt[i]), ans %= mod; 200 cout << ans << "\n"; 201 } 202 } 203 204 signed main() { 205 ios::sync_with_stdio(false); 206 cin.tie(nullptr); 207 cout.tie(nullptr); 208 209 cin >> n >> k >> q; 210 pre(); 211 212 int t = 1; 213 //cin >> t; 214 while (t--) 215 solveTestCase(); 216 } 217 ``` 218 219 Tutorial is loading... 220 221 **Solution** 222 223 ``` 224 #include <bits/stdc++.h> 225 using namespace std; 226 #define int long long 227 228 const int N = 5e5; 229 vector<int> adj[N]; 230 int a[N], par[N], n; 231 232 map<int, vector<int>> v, times; 233 int euler[N * 2 - 1], tin[N], tout[N], c = 0; 234 235 set<pair<int, int>> g; 236 int dp[N], ans; 237 238 void dfs(int v, int p = -1) { 239 par[v] = p; 240 tin[v] = c; 241 euler[c++] = v; 242 243 for (int i : adj[v]) { 244 if (i == p) 245 continue; 246 dfs(i, v); 247 euler[c++] = v; 248 } 249 250 tout[v] = c - 1; 251 } 252 253 void examine(int v) { 254 int sum = 0; 255 256 for (int i : adj[v]) { 257 if (i == par[v]) 258 continue; 259 260 int count = upper_bound(times[a[v]].begin(), times[a[v]].end(), tout[i]) - lower_bound(times[a[v]].begin(), times[a[v]].end(), tin[i]); 261 if (count > 0) 262 g.insert({v, i}); 263 sum += count; 264 } 265 266 sum = times[a[v]].size() - sum - 1; 267 if (sum) 268 g.insert({v, par[v]}); 269 } 270 271 int setup(int v) { 272 for (int i : adj[v]) { 273 if (i != par[v]) 274 dp[v] += setup(i); 275 } 276 return dp[v] + g.count({v, par[v]}); 277 } 278 279 void reroot(int v) { 280 if (dp[v] == g.size()) 281 ans++; 282 283 for (int i : adj[v]) { 284 if (i == par[v]) 285 continue; 286 287 dp[v] -= dp[i]; 288 dp[v] -= g.count({i, v}); 289 dp[i] += dp[v]; 290 dp[i] += g.count({v, i}); 291 292 reroot(i); 293 294 dp[i] -= g.count({v, i}); 295 dp[i] -= dp[v]; 296 dp[v] += g.count({i, v}); 297 dp[v] += dp[i]; 298 } 299 } 300 301 int solveTestCase() { 302 cin >> n; 303 for (int i = 0; i < n; i++) 304 cin >> a[i]; 305 306 for (int i = 0; i < n - 1; i++) { 307 int u, v; 308 cin >> u >> v; 309 u--, v--; 310 adj[u].push_back(v); 311 adj[v].push_back(u); 312 } 313 314 dfs(0); 315 for (int i = 0; i < n; i++) 316 v[a[i]].push_back(i); 317 318 for (auto i : v) { 319 if (i.second.size() == 1) 320 continue; 321 322 for (int j : i.second) 323 times[i.first].push_back(tin[j]); 324 sort(times[i.first].begin(), times[i.first].end()); 325 for (int j : i.second) 326 examine(j); 327 } 328 329 setup(0); 330 reroot(0); 331 332 cout << ans; 333 } 334 335 signed main() { 336 ios::sync_with_stdio(false); 337 cin.tie(nullptr); 338 cout.tie(nullptr); 339 340 int t = 1; 341 //cin >> t; 342 while (t--) 343 solveTestCase(); 344 } 345 ``` 346 347 UPD: Also, have a look at [this](https://codeforces.com/blog/entry/86566?#comment-746573) comment for an explanation of the sample test case of C.