2033.md (7849B)
1 Source: https://codeforces.com/blog/entry/135520 2 3 [2033A - Sakurako and Kosuke](/contest/2033/problem/A "Codeforces Round 981 (Div. 3)") 4 5 Idea: [FBI](/profile/FBI "Master FBI") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 def solve(): 15 n = int(input()) 16 x = 0 17 c = 1 18 while -n <= x <= n: 19 if c % 2 == 1: 20 x -= 2 * c - 1 21 else: 22 x += 2 * c - 1 23 c += 1 24 if c % 2 == 0: 25 print("Sakurako") 26 else: 27 print("Kosuke") 28 29 for tc in range(int(input())): 30 solve() 31 ``` 32 33 [2033B - Sakurako and Water](/contest/2033/problem/B "Codeforces Round 981 (Div. 3)") 34 35 Idea: [FBI](/profile/FBI "Master FBI") 36 37 **Tutorial** 38 39 Tutorial is loading... 40 41 **Solution** 42 43 ``` 44 def solve(): 45 n = int(input()) 46 mn = dict() 47 for i in range(n): 48 a = [int(x) for x in input().split()] 49 for j in range(n): 50 mn[i - j] = min(a[j], mn.get(i - j, 0)) 51 ans = 0 52 for value in mn.values(): 53 ans -= value 54 print(ans) 55 56 t = int(input()) 57 for _ in range(t): 58 solve() 59 ``` 60 61 [2033C - Sakurako's Field Trip](/contest/2033/problem/C "Codeforces Round 981 (Div. 3)") 62 63 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") 64 65 **Tutorial** 66 67 Tutorial is loading... 68 69 **Solution** 70 71 ``` 72 #include <bits/stdc++.h> 73 using namespace std; 74 int main(){ 75 int t; 76 cin>>t; 77 while(t--){ 78 int n; 79 cin>>n; 80 int a[n+1]; 81 for(int i=1;i<=n;i++){ 82 cin>>a[i]; 83 } 84 for(int i=n/2-1;i>=1;i--){ 85 if(a[i]==a[i+1] || a[n-i+1]==a[n-i]){ 86 swap(a[i],a[n-i+1]); 87 } 88 } 89 int re=0; 90 for(int i=1;i<n;i++){ 91 re+=(a[i]==a[i+1]); 92 } 93 cout<<re<<endl; 94 } 95 } 96 ``` 97 98 [2033D - Kousuke's Assignment](/contest/2033/problem/D "Codeforces Round 981 (Div. 3)") 99 100 Idea: [FBI](/profile/FBI "Master FBI") 101 102 **Tutorial** 103 104 Tutorial is loading... 105 106 **Solution** 107 108 ``` 109 #include <bits/stdc++.h> 110 using namespace std; 111 int main(){ 112 int t; 113 cin>>t; 114 while(t--){ 115 int n; 116 cin>>n; 117 int a[n+1]; 118 map<int,int>mp; 119 for(int i=1;i<=n;i++){ 120 cin>>a[i]; 121 } 122 int p_su[n+1]; 123 p_su[0]=0; 124 int lst[n+1]; 125 mp[0]=0; 126 for(int i=1;i<=n;i++){ 127 p_su[i]=p_su[i-1]+a[i]; 128 if(mp.find(p_su[i])==mp.end()){ 129 lst[i]=-1; 130 } 131 else{ 132 lst[i]=mp[p_su[i]]; 133 } 134 mp[p_su[i]]=i; 135 } 136 int dp[n+1]; 137 memset(dp,0,sizeof dp); 138 for(int i=1;i<=n;i++){ 139 dp[i]=max(dp[i],dp[i-1]); 140 if(lst[i]!=-1){ 141 dp[i]=max(dp[i],dp[lst[i]]+1); 142 } 143 } 144 cout<<*max_element(dp,dp+n+1)<<endl; 145 } 146 } 147 ``` 148 149 [2033E - Sakurako, Kosuke, and the Permutation](/contest/2033/problem/E "Codeforces Round 981 (Div. 3)") 150 151 Idea: [FBI](/profile/FBI "Master FBI") 152 153 **Tutorial** 154 155 Tutorial is loading... 156 157 **Solution** 158 159 ``` 160 #include<bits/stdc++.h> 161 using namespace std; 162 int main(){ 163 int t; 164 ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr); 165 cin>>t; 166 while(t--){ 167 int n; 168 cin>>n; 169 int p[n+1]; 170 for(int i=1;i<=n;i++){ 171 cin>>p[i]; 172 } 173 bool us[n+1]; 174 memset(us,0,sizeof us); 175 int re=0; 176 for(int i=1;i<=n;i++){ 177 if(!us[i]){ 178 int cu=i; 179 int le=0; 180 while(us[cu]==0){ 181 le++; 182 us[cu]=1; 183 cu=p[cu]; 184 } 185 re+=(le-1)/2; 186 } 187 } 188 cout<<re<<'\n'; 189 } 190 } 191 ``` 192 193 [2033F - Kosuke's Sloth](/contest/2033/problem/F "Codeforces Round 981 (Div. 3)") 194 195 Idea: [FBI](/profile/FBI "Master FBI") 196 197 **Tutorial** 198 199 Tutorial is loading... 200 201 **Solution** 202 203 ``` 204 #include <bits/stdc++.h> 205 206 using namespace std; 207 using LL = long long; 208 #define ssize(x) (int)(x.size()) 209 #define ALL(x) (x).begin(), (x).end() 210 211 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 212 213 int rd(int l, int r) { 214 return uniform_int_distribution<int>(l, r)(rng); 215 } 216 const LL MOD = 1e9 + 7; 217 int bp(int a, int n) { 218 if (n == 0) 219 return 1; 220 if (n % 2 == 0) 221 return bp(1LL * a * a % MOD, n / 2); 222 else 223 return 1LL * bp(a, n - 1) * a % MOD; 224 } 225 int inv(int a) { 226 return bp(a, MOD - 2); 227 } 228 void solve() { 229 LL n, k; 230 cin >> n >> k; 231 n %= MOD; 232 if (k == 1) { 233 cout << n << "\n"; 234 return; 235 } 236 vector<int> fib(3); 237 fib[0] = fib[1] = 1; 238 int cnt = 0; 239 for (int i = 2; i <= 10 * k; i++) { 240 fib[i % 3] = (fib[(i + 2) % 3] + fib[(i + 1) % 3]) % k; 241 if (fib[i % 3] == 0) 242 cnt++; 243 if (fib[i % 3] == 1 && fib[(i + 2) % 3] == 0) { 244 cout << 1LL * i * n % MOD * inv(cnt) % MOD << "\n"; 245 return; 246 } 247 } 248 } 249 int main() { 250 ios_base::sync_with_stdio(0); 251 cin.tie(0); 252 cout.tie(0); 253 int t = 1; 254 cin >> t; 255 while (t--) { 256 solve(); 257 } 258 } 259 ``` 260 261 [2033G - Sakurako and Chefir](/contest/2033/problem/G "Codeforces Round 981 (Div. 3)") 262 263 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") 264 265 **Tutorial** 266 267 Tutorial is loading... 268 269 **Solution** 270 271 ``` 272 #include <bits/stdc++.h> 273 274 //#define int long long 275 #define pb emplace_back 276 #define mp make_pair 277 #define x first 278 #define y second 279 #define all(a) a.begin(), a.end() 280 #define rall(a) a.rbegin(), a.rend() 281 282 typedef long double ld; 283 typedef long long ll; 284 285 using namespace std; 286 287 mt19937 rnd(time(nullptr)); 288 289 const int inf = 1e9; 290 const int M = 1e9 + 7; 291 const ld pi = atan2(0, -1); 292 const ld eps = 1e-6; 293 294 void precalc(int v, int p, vector<vector<int>> &sl, vector<pair<int, int>> &maxd, vector<int> &h){ 295 maxd[v] = {0, 0}; 296 if (v != p) h[v] = h[p] + 1; 297 for(int u: sl[v]){ 298 if (u == p) continue; 299 precalc(u, v, sl, maxd, h); 300 if (maxd[v].y < maxd[u].x + 1) { 301 maxd[v].y = maxd[u].x + 1; 302 } 303 if (maxd[v].y > maxd[v].x) { 304 swap(maxd[v].x, maxd[v].y); 305 } 306 } 307 } 308 309 void calc_binups(int v, int p, vector<vector<int>> &sl, vector<vector<pair<int, int>>> &binup, vector<pair<int, int>> &maxd, vector<int> &h){ 310 binup[v][0] = {maxd[p].x, p}; 311 if (maxd[p].x == maxd[v].x + 1) { 312 binup[v][0].x = maxd[p].y; 313 } 314 binup[v][0].x -= h[p]; 315 for(int i = 1; i < 20; ++i){ 316 binup[v][i].y = binup[binup[v][i - 1].y][i - 1].y; 317 binup[v][i].x = max(binup[v][i - 1].x, binup[binup[v][i - 1].y][i - 1].x); 318 } 319 320 for(int u: sl[v]){ 321 if (u == p) continue; 322 calc_binups(u, v, sl, binup, maxd, h); 323 } 324 } 325 326 int get_ans(int v, int k, vector<vector<pair<int, int>>> &binup, vector<pair<int, int>> &maxd, vector<int> &h){ 327 k = min(k, h[v]); 328 int res = maxd[v].x - h[v]; 329 int ini = h[v]; 330 for(int i = 19; i >= 0; --i){ 331 if ((1 << i) <= k) { 332 res = max(res, binup[v][i].x); 333 v = binup[v][i].y; 334 k -= (1 << i); 335 } 336 } 337 return res + ini; 338 } 339 340 void solve(int tc){ 341 int n; 342 cin >> n; 343 vector<vector<int>> sl(n); 344 for(int i = 1; i < n; ++i){ 345 int u, v; 346 cin >> u >> v; 347 sl[--u].emplace_back(--v); 348 sl[v].emplace_back(u); 349 } 350 vector<pair<int, int>> maxd(n); 351 vector<int> h(n); 352 precalc(0, 0, sl, maxd, h); 353 vector<vector<pair<int, int>>> binup(n, vector<pair<int, int>>(20)); 354 calc_binups(0, 0, sl, binup, maxd, h); 355 int q; 356 cin >> q; 357 for(int _ = 0; _ < q; ++_){ 358 int v, k; 359 cin >> v >> k; 360 cout << get_ans(v - 1, k, binup, maxd, h) << " "; 361 } 362 } 363 364 bool multi = true; 365 366 signed main() { 367 int t = 1; 368 if (multi)cin >> t; 369 for (int i = 1; i <= t; ++i) { 370 solve(i); 371 cout << "\n"; 372 } 373 return 0; 374 } 375 ```