1787.md (6613B)
1 Source: https://codeforces.com/blog/entry/112009 2 3 [1787A - Exponential Equation](/contest/1787/problem/A) 4 5 Idea & Solution: [rsj](/profile/rsj "Master rsj") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 [1787B - Number Factorization](/contest/1787/problem/B) 12 13 Idea & Solution: [rsj](/profile/rsj "Master rsj") 14 15 **Tutorial** 16 17 Tutorial is loading... 18 19 **Solution** 20 21 ``` 22 #include <bits/stdc++.h> 23 using namespace std; 24 #define mp make_pair 25 pair<int, int> s[110]; 26 int d[110]; 27 void get() { 28 int n, l = 0, i, c; 29 cin >> n; 30 for (i = 2; i * i <= n; i++) { 31 if (n % i == 0) { 32 c = 0; 33 while (n % i == 0) c++, n /= i; 34 s[++l] = make_pair(c, i); 35 } 36 } 37 if (n != 1) s[++l] = make_pair(1, n); 38 sort(s + 1, s + l + 1), d[l + 1] = 1; 39 for (i = l; i >= 1; i--) d[i] = d[i + 1] * s[i].second; 40 int ans = 0; 41 for (i = 1; i <= l; i++) if (s[i].first != s[i - 1].first) ans += d[i] * (s[i].first - s[i - 1].first); 42 cout << ans << endl; 43 } 44 signed main() { 45 ios::sync_with_stdio(0); 46 cin.tie(0); 47 int T; 48 cin >> T; 49 while (T--) get(); 50 return 0; 51 } 52 ``` 53 54 [1787C - Remove the Bracket](/contest/1787/problem/C) 55 56 Idea & Solution: [rsj](/profile/rsj "Master rsj") 57 58 **Fact** 59 60 This is the reason why the problem was named as *Remove the Bracket*. 61 62 $ \begin{aligned} \text{Product} &= a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n = \\ &= a_1 \cdot (x_2+y_2) \cdot (x_3+y_3) \cdot \ldots \cdot (x_{n-1}+y_{n-1}) \cdot a_n = \\ &\overset{\text{?}}{=} a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot \ldots \cdot x_{n-1}+y_{n-1} \cdot a_n. \end{aligned} $ 63 64 However, We discussed to remove it on 28th Jan in the statement. Really sorry for inconvenience of the statement! 65 66 **Tutorial** 67 68 Tutorial is loading... 69 70 **Solution** 71 72 ``` 73 #include <bits/stdc++.h> 74 using namespace std; 75 const int N = 200005; 76 long long f[N][2],x[N],y[N]; 77 void get() { 78 int i,n,s,j; 79 cin>>n>>s; 80 for(i=1; i<=n; i++) { 81 cin>>j; 82 if(i==1||i==n) x[i]=y[i]=j; 83 else if(j<=s) x[i]=0,y[i]=j; 84 else x[i]=s,y[i]=j-s; 85 } 86 f[1][0]=f[1][1]=0; 87 for(i=2; i<=n; i++) { 88 f[i][0]=min(f[i-1][0]+y[i-1]*x[i],f[i-1][1]+x[i-1]*x[i]); 89 f[i][1]=min(f[i-1][0]+y[i-1]*y[i],f[i-1][1]+x[i-1]*y[i]); 90 } 91 cout<<f[n][0]<<endl; 92 } 93 int main() { 94 ios::sync_with_stdio(0); 95 cin.tie(0); 96 int T; cin>>T; 97 while(T--) get(); 98 return 0; 99 } 100 ``` 101 102 [1787D - Game on Axis](/contest/1787/problem/D) 103 104 Idea & Solution: [jiangtaizhe001](/profile/jiangtaizhe001 "Candidate Master jiangtaizhe001") 105 106 **Tutorial** 107 108 Tutorial is loading... 109 110 **Solution** 111 112 ``` 113 #include <bits/stdc++.h> 114 using namespace std; 115 const int N = 200005; 116 int a[N]; 117 int v[N]; //= 1 -> in the tree with the end node 118 int s[N]; //subtree size 119 struct E { 120 int to; 121 E *nex; 122 } *h[N]; 123 void add(int u, int v) { 124 E *cur = new E; 125 cur->to = v, cur->nex = h[u], h[u] = cur; 126 } 127 void dfs(int u) { 128 s[u] = v[u] = 1; 129 for (E *cur = h[u]; cur; cur = cur->nex) 130 dfs(cur->to), s[u] += s[cur->to]; 131 } 132 void get() { 133 int i, j, n; 134 cin >> n; 135 for (i = 1; i <= n + 1; i++) 136 s[i] = v[i] = 0, h[i] = 0; 137 for (i = 1; i <= n; i++) { 138 cin >> a[i], a[i] = min(i + a[i], n + 1); 139 if (a[i] <= 0) a[i] = n + 1; 140 add(a[i], i); 141 } 142 dfs(n + 1); //start with the end point, dfs the tree 143 long long ans = 0; 144 if (v[1] == 1) { 145 j = 1; do { ans -= s[j] + (n - s[n + 1] + 1), j = a[j]; } 146 while (j != n + 1); 147 ans += 1ll * n * (2 * n + 1); 148 } else { 149 j = 1; do { ans += (n + s[n + 1]), v[j] = 2, j = a[j]; } 150 while (v[j] != 2); 151 } 152 cout << ans << endl; 153 } 154 int main() { 155 ios::sync_with_stdio(0); 156 cin.tie(0); 157 int T; 158 cin >> T; 159 while (T--) get(); 160 return 0; 161 } 162 ``` 163 164 [1787E - The Harmonization of XOR](/contest/1787/problem/E) 165 166 Idea & Solution: [jiangtaizhe001](/profile/jiangtaizhe001 "Candidate Master jiangtaizhe001"), [rsj](/profile/rsj "Master rsj") 167 168 **Tutorial** 169 170 Tutorial is loading... 171 172 **Bonus Problem** 173 174 **Bonus Problem:** What if $x=0$? 175 176 [1787F - Inverse Transformation](/contest/1787/problem/F) 177 178 Idea & Solution: [qzhwlzy](/profile/qzhwlzy "Specialist qzhwlzy"), [rsj](/profile/rsj "Master rsj") 179 180 **Tutorial** 181 182 Tutorial is loading... 183 184 **Solution** 185 186 ``` 187 #include <bits/stdc++.h> 188 using namespace std; 189 const int N = 200005; 190 int dest[N], visit[N], ans[N], mp[N], ansinv[N], sp; 191 int pow2(int y, int M) { 192 long long x = 2, ans = 1; 193 while (y) { 194 if (y & 1) ans = ans * x % M; 195 x = x * x % M, y >>= 1; 196 } 197 return ans % M; 198 } 199 vector<int> cyc[N]; 200 void get() { 201 sp = 0; 202 int n, i, j, m, z, o; 203 cin >> n >> m; 204 for (i = 1; i <= n; i++) cyc[i].clear(); 205 for (i = 1; i <= n; i++) visit[i] = 0, cin >> dest[i]; 206 for (i = 1; i <= n; i++) { 207 if (visit[i]) continue; 208 j = i, z = 0; do { ++z, visit[j] = 1, j = dest[j]; } while (j != i); 209 cyc[z].push_back(i); 210 } 211 int lim = pow2(min(m, 20), 1e9), s = 0, d, t, num, cp; 212 for (i = 1; i <= n; i++) { 213 if (!cyc[i].size()) continue; 214 int siz = cyc[i].size(); 215 if (i % 2 == 0 && siz % lim) { 216 cout << "NO" << endl; return; 217 } else { 218 cp = -1; 219 for (j = lim; j > 0; j /= 2) { 220 while (siz >= j) { 221 siz -= j, d = s + j * i, t = j; 222 while (t--) { 223 ++s, ++cp, num = s, o = cyc[i][cp]; 224 do { 225 ans[num] = o, num += pow2(m, i * j); 226 if (num > d) num -= j * i; 227 o = dest[o]; 228 } while (o != cyc[i][cp]); 229 } 230 for (int k = sp + 1; k < sp + j * i; k++) mp[k] = k + 1; 231 mp[sp + j * i] = sp + 1, sp += j * i, s = d; 232 } 233 } 234 } 235 } 236 cout << "YES" << endl; 237 for (i = 1; i <= n; i++) ansinv[ans[i]] = i; 238 for (i = 1; i <= n; i++) cout << ans[mp[ansinv[i]]] << " \n"[i == n]; 239 } 240 int main() { 241 ios::sync_with_stdio(0), cin.tie(0); 242 int T; 243 cin >> T; 244 while (T--) get(); 245 return 0; 246 } 247 ``` 248 249 [1787G - Colorful Tree Again](/contest/1787/problem/G) 250 251 Idea & Solution: [rsj](/profile/rsj "Master rsj"), [275307894a](/profile/275307894a "Grandmaster 275307894a") 252 253 **Tutorial** 254 255 Tutorial is loading... 256 257 **UPD:** An alternative implementation using segment tree [comment link](https://codeforces.com/blog/entry/112009?#comment-998516). 258 259 [1787H - Codeforces Scoreboard](/contest/1787/problem/H) 260 261 Idea & Solution: [jiangtaizhe001](/profile/jiangtaizhe001 "Candidate Master jiangtaizhe001"), [rsj](/profile/rsj "Master rsj") 262 263 **Something To Say** 264 265 Have to declare that we built up Problem H from zero. ;) 266 267 **Tutorial** 268 269 Tutorial is loading... 270 271 [1787I - Treasure Hunt](/contest/1787/problem/I) 272 273 Idea & Solution: [275307894a](/profile/275307894a "Grandmaster 275307894a") 274 275 **Tutorial** 276 277 Tutorial is loading... 278 279 I'm really sorry for the unsatisfactory problems and the tough 3 hours ;) 280 281 However, I still hope you can enjoy the problems after the contest. The editorial hasn't been fully checked, so feel free to comment if there're errors, typos or you have questions about them. We'll check them out tomorrow. Thanks!