743.md (3855B)
1 Source: https://codeforces.com/blog/entry/49049 2 3 Tutorial is loading... 4 5 **Setter's code** 6 7 ``` 8 int n, a, b; 9 string s; 10 cin >> n >> a >> b >> s; 11 12 a--, b--; 13 14 cout << ((s[a] - '0') ^ (s[b] - '0')); 15 ``` 16 17 Tutorial is loading... 18 19 **Setter's code** 20 21 ``` 22 int go(ll l, ll r, ll need, int alphSize) 23 { 24 ll m = l + (r - l) / 2LL; 25 if (need < m) 26 return go(l, m - 1, need, alphSize - 1); 27 else if (need > m) 28 return go(m + 1, r, need, alphSize - 1); 29 else 30 return alphSize; 31 } 32 33 void solveABig() 34 { 35 int n; 36 ll k; 37 38 cin >> n >> k; 39 ll sz = 1; 40 for (int i = 1; i < n; i++) 41 sz = sz * 2LL + 1LL; 42 43 cout << go(1, sz, k, n); 44 } 45 ``` 46 47 Tutorial is loading... 48 49 **Setter's code** 50 51 ``` 52 int n; 53 cin >> n; 54 if (n == 1) 55 cout << -1 << endl; 56 else 57 cout << n << ' ' << n + 1 << ' ' << n * (n + 1) << endl; 58 ``` 59 60 Tutorial is loading... 61 62 **Setter's code** 63 64 ``` 65 int a[maxn]; 66 vector<int> g[maxn]; 67 68 ll sum_subTree[maxn], mx_subTree[maxn]; 69 70 void dfs1(int v, int p) { 71 sum_subTree[v] = a[v]; 72 mx_subTree[v] = -llinf; 73 for (int i = 0; i < g[v].size(); i++) { 74 int to = g[v][i]; 75 if (to == p) 76 continue; 77 dfs1(to, v); 78 sum_subTree[v] += sum_subTree[to]; 79 mx_subTree[v] = max(mx_subTree[v], mx_subTree[to]); 80 } 81 mx_subTree[v] = max(mx_subTree[v], sum_subTree[v]); 82 } 83 84 ll ans = -llinf; 85 86 void dfs2(int v, int p, ll out) { 87 if (out != -llinf) 88 ans = max(ans, sum_subTree[v] + out); 89 90 vector<pair<ll, int> > miniset; 91 for (int i = 0; i < g[v].size(); i++) { 92 int to = g[v][i]; 93 if (to == p) 94 continue; 95 miniset.pb(mp(mx_subTree[to], to)); 96 sort(miniset.rbegin(), miniset.rend()); 97 if (miniset.size() == 3) 98 miniset.pop_back(); 99 } 100 miniset.pb(mp(-llinf, -1)); 101 for (int i = 0; i < g[v].size(); i++) { 102 int to = g[v][i]; 103 if (to == p) 104 continue; 105 ll cur = miniset[0].s == to ? miniset[1].f : miniset[0].f; 106 dfs2(to, v, max(out, cur)); 107 } 108 } 109 110 int main() { 111 for (int i = 0; i + 1 < n; i++) { 112 int u, v; 113 read(u, v); 114 u--, v--; 115 g[u].pb(v); 116 g[v].pb(u); 117 } 118 119 dfs1(0, -1); 120 dfs2(0, -1, -llinf); 121 cout << ((ans == -llinf) ? ("Impossible") : to_string(ans)); 122 return 0; 123 } 124 ``` 125 126 Tutorial is loading... 127 128 **Setter's code** 129 130 ``` 131 int can(int len) { 132 for (int i = 0; i < 8; i++) 133 cur[i] = 0; 134 for (int i = 0; i <= n; i++) 135 for (int j = 0; j < (1 << 8); j++) 136 dp[i][j] = -inf; 137 dp[0][0] = 0; 138 for (int i = 0; i < n; i++) { 139 for (int j = 0; j < (1 << 8); j++) { 140 if (dp[i][j] == -inf) 141 continue; 142 for (int k = 0; k < 8; k++) { 143 if (j & (1 << k)) 144 continue; 145 int it = cur[k] + len - 1; 146 if (it >= in[k].size()) 147 continue; 148 amax(dp[in[k][it] + 1][j | (1 << k)], dp[i][j]); 149 150 it++; 151 if (it >= in[k].size()) 152 continue; 153 amax(dp[in[k][it] + 1][j | (1 << k)], dp[i][j] + 1); 154 } 155 } 156 cur[a[i]]++; 157 } 158 159 int ans = -inf; 160 for (int i = 0; i <= n; i++) 161 ans = max(ans, dp[i][(1 << 8) - 1]); 162 if (ans == -inf) 163 return -1; 164 165 return ans * (len + 1) + (8 - ans) * len; 166 } 167 168 int main() { 169 for (int i = 0; i < n; i++) { 170 in[a[i]].push_back(i); 171 } 172 173 int l = 1, r = n / 8; 174 while (r - l > 1) { 175 int m = (l + r) >> 1; 176 if (can(m) != -1) 177 l = m; 178 else 179 r = m; 180 } 181 int ans = max(can(l), can(r)); 182 if (ans == -1) { 183 ans = 0; 184 for (int i = 0; i < 8; i++) 185 if (!in[i].empty()) 186 ans++; 187 } 188 cout << ans; 189 return 0; 190 } 191 ```