1095.md (4812B)
1 Source: https://codeforces.com/blog/entry/64130 2 3 [1095A - Repeating Cipher](/contest/1095/problem/A "Codeforces Round 529 (Div. 3)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 int n; 18 cin >> n; 19 string s; 20 cin >> s; 21 int index = 0; 22 int gap = 1; 23 while (index < n) 24 cout << s[index], index += gap, gap++; 25 } 26 ``` 27 28 [1095B - Array Stabilization](/contest/1095/problem/B "Codeforces Round 529 (Div. 3)") 29 30 **Tutorial** 31 32 Tutorial is loading... 33 34 **Solution** 35 36 ``` 37 #include <bits/stdc++.h> 38 39 using namespace std; 40 41 int main() { 42 #ifdef _DEBUG 43 freopen("input.txt", "r", stdin); 44 // freopen("output.txt", "w", stdout); 45 #endif 46 47 int n; 48 cin >> n; 49 vector<int> a(n); 50 for (int i = 0; i < n; ++i) { 51 cin >> a[i]; 52 } 53 sort(a.begin(), a.end()); 54 55 cout << min(a[n - 2] - a[0], a[n - 1] - a[1]) << endl; 56 57 return 0; 58 } 59 ``` 60 61 [1095C - Powers Of Two](/contest/1095/problem/C "Codeforces Round 529 (Div. 3)") 62 63 **Tutorial** 64 65 Tutorial is loading... 66 67 **Solution** 68 69 ``` 70 #include<bits/stdc++.h> 71 72 using namespace std; 73 74 int main() 75 { 76 int n, k; 77 cin >> n >> k; 78 map<int, int> ans; 79 queue<int> q; 80 for(int i = 0; i <= 30; i++) 81 if(n & (1 << i)) 82 { 83 if(i > 0) q.push(1 << i); 84 ans[1 << i]++; 85 } 86 if(int(ans.size()) > k) 87 { 88 puts("NO"); 89 return 0; 90 } 91 int cnt = ans.size(); 92 while(cnt < k && !q.empty()) 93 { 94 int z = q.front(); 95 q.pop(); 96 ans[z]--; 97 ans[z / 2] += 2; 98 if(z / 2 > 1) 99 { 100 q.push(z / 2); 101 q.push(z / 2); 102 } 103 cnt++; 104 } 105 if(cnt < k) 106 { 107 puts("NO"); 108 return 0; 109 } 110 puts("YES"); 111 for(auto x : ans) 112 for(int i = 0; i < x.second; i++) 113 printf("%d ", x.first); 114 puts(""); 115 return 0; 116 } 117 ``` 118 119 [1095D - Circular Dance](/contest/1095/problem/D "Codeforces Round 529 (Div. 3)") 120 121 **Tutorial** 122 123 Tutorial is loading... 124 125 **Solution** 126 127 ``` 128 #include <bits/stdc++.h> 129 130 using namespace std; 131 132 int n; 133 vector<vector<int>> a; 134 135 void check(int l, int r) { 136 vector<int> ans; 137 for (int i = 0; i < n; ++i) { 138 int nxt = -1; 139 if (a[l][0] == r) { 140 nxt = a[l][1]; 141 } else if (a[l][1] == r) { 142 nxt = a[l][0]; 143 } else { 144 return; 145 } 146 ans.push_back(nxt); 147 l = r; 148 r = nxt; 149 } 150 for (auto it : ans) { 151 cout << it + 1 << " "; 152 } 153 cout << endl; 154 exit(0); 155 } 156 157 int main() { 158 #ifdef _DEBUG 159 freopen("input.txt", "r", stdin); 160 // freopen("output.txt", "w", stdout); 161 #endif 162 163 cin >> n; 164 a = vector<vector<int>> (n, vector<int>(2)); 165 for (int i = 0; i < n; ++i) { 166 cin >> a[i][0] >> a[i][1]; 167 --a[i][0]; 168 --a[i][1]; 169 } 170 171 check(0, a[0][0]); 172 check(0, a[0][1]); 173 174 assert(false); 175 176 return 0; 177 } 178 ``` 179 180 [1095E - Almost Regular Bracket Sequence](/contest/1095/problem/E "Codeforces Round 529 (Div. 3)") 181 182 **Tutorial** 183 184 Tutorial is loading... 185 186 **Solution** 187 188 ``` 189 #include <bits/stdc++.h> 190 191 using namespace std; 192 193 int main() { 194 #ifdef _DEBUG 195 freopen("input.txt", "r", stdin); 196 // freopen("output.txt", "w", stdout); 197 #endif 198 199 int n; 200 string s; 201 cin >> n >> s; 202 203 string rs(s.rbegin(), s.rend()); 204 for (int i = 0; i < n; ++i) { 205 if (rs[i] == '(') { 206 rs[i] = ')'; 207 } else { 208 rs[i] = '('; 209 } 210 } 211 212 vector<int> pref(n + 1), suf(n + 1); 213 vector<bool> okp(n + 1), oks(n + 1); 214 okp[0] = oks[n] = true; 215 for (int i = 0; i < n; ++i) { 216 pref[i + 1] = pref[i] + (s[i] == '(' ? +1 : -1); 217 okp[i + 1] = okp[i] & (pref[i + 1] >= 0); 218 suf[n - i - 1] = suf[n - i] + (rs[i] == '(' ? +1 : -1); 219 oks[n - i - 1] = oks[n - i] & (suf[n - i - 1] >= 0); 220 } 221 222 int ans = 0; 223 for (int i = 0; i < n; ++i) { 224 if (!okp[i] || !oks[i + 1]) { 225 continue; 226 } 227 if (s[i] == '(') { 228 if (pref[i] > 0 && pref[i] - 1 - suf[i + 1] == 0) { 229 ++ans; 230 } 231 } else { 232 if (pref[i] + 1 - suf[i + 1] == 0) { 233 ++ans; 234 } 235 } 236 } 237 238 cout << ans << endl; 239 240 return 0; 241 } 242 ``` 243 244 [1095F - Make It Connected](/contest/1095/problem/F "Codeforces Round 529 (Div. 3)") 245 246 **Tutorial** 247 248 Tutorial is loading... 249 250 **Solution** 251 252 ``` 253 #include<bits/stdc++.h> 254 255 using namespace std; 256 257 #define x first 258 #define y second 259 #define mp make_pair 260 261 typedef pair<long long, pair<int, int> > edge; 262 263 const int N = 200043; 264 265 int p[N]; 266 long long a[N]; 267 268 int get_leader(int x) 269 { 270 return (x == p[x] ? x : (p[x] = get_leader(p[x]))); 271 } 272 273 bool merge(int x, int y) 274 { 275 x = get_leader(x); 276 y = get_leader(y); 277 if(x == y) return false; 278 p[x] = y; 279 return true; 280 } 281 282 int main() 283 { 284 int n, m; 285 scanf("%d %d", &n, &m); 286 for(int i = 0; i < n; i++) 287 scanf("%lld", &a[i]); 288 vector<edge> es(m); 289 for(int i = 0; i < m; i++) 290 { 291 scanf("%d %d %lld", &es[i].y.x, &es[i].y.y, &es[i].x); 292 es[i].y.x--; 293 es[i].y.y--; 294 } 295 int z = min_element(a, a + n) - a; 296 for(int i = 0; i < n; i++) 297 if(i != z) 298 es.push_back(mp(a[i] + a[z], mp(i, z))); 299 sort(es.begin(), es.end()); 300 long long ans = 0; 301 for(int i = 0; i < n; i++) 302 p[i] = i; 303 for(auto e : es) 304 if(merge(e.y.x, e.y.y)) 305 ans += e.x; 306 printf("%lld\n", ans); 307 return 0; 308 } 309 ```