1324.md (4296B)
1 Source: https://codeforces.com/blog/entry/74714 2 3 Suddendly, all ideas of this contest are mine. And I'm very sorry about one missing small test in the problem B. This is the biggest mistake I made during the preparation of this round. 4 5 [1324A - Yet Another Tetris Problem](/contest/1324/problem/A "Codeforces Round 627 (Div. 3)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 for i in range(int(input())): 15 n = int(input()) 16 cnto = sum(list(map(lambda x: int(x) % 2, input().split()))) 17 print('YES' if cnto == 0 or cnto == n else 'NO') 18 ``` 19 20 [1324B - Yet Another Palindrome Problem](/contest/1324/problem/B "Codeforces Round 627 (Div. 3)") 21 22 **Tutorial** 23 24 Tutorial is loading... 25 26 **Solution** 27 28 ``` 29 for i in range(int(input())): 30 n = int(input()) 31 s = list(map(int, input().split())) 32 ok = False 33 for i in range(n): 34 for j in range(i + 2, n): 35 if s[i] == s[j]: ok = True 36 print('YES' if ok else 'NO') 37 ``` 38 39 [1324C - Frog Jumps](/contest/1324/problem/C "Codeforces Round 627 (Div. 3)") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution** 46 47 ``` 48 #include <bits/stdc++.h> 49 50 using namespace std; 51 52 int main() { 53 #ifdef _DEBUG 54 freopen("input.txt", "r", stdin); 55 // freopen("output.txt", "w", stdout); 56 #endif 57 58 int t; 59 cin >> t; 60 while (t--) { 61 string s; 62 cin >> s; 63 vector<int> pos; 64 pos.push_back(0); 65 for (int i = 0; i < int(s.size()); ++i) { 66 if (s[i] == 'R') pos.push_back(i + 1); 67 } 68 pos.push_back(s.size() + 1); 69 int ans = 0; 70 for (int i = 0; i < int(pos.size()) - 1; ++i) { 71 ans = max(ans, pos[i + 1] - pos[i]); 72 } 73 cout << ans << endl; 74 } 75 76 return 0; 77 } 78 ``` 79 80 [1324D - Pair of Topics](/contest/1324/problem/D "Codeforces Round 627 (Div. 3)") 81 82 **Tutorial** 83 84 Tutorial is loading... 85 86 **Solution** 87 88 ``` 89 #include <bits/stdc++.h> 90 91 using namespace std; 92 93 int main() { 94 #ifdef _DEBUG 95 freopen("input.txt", "r", stdin); 96 // freopen("output.txt", "w", stdout); 97 #endif 98 99 int n; 100 cin >> n; 101 vector<int> a(n), b(n); 102 for (auto &it : a) cin >> it; 103 for (auto &it : b) cin >> it; 104 vector<int> c(n); 105 for (int i = 0; i < n; ++i) { 106 c[i] = a[i] - b[i]; 107 } 108 sort(c.begin(), c.end()); 109 110 long long ans = 0; 111 for (int i = 0; i < n; ++i) { 112 if (c[i] <= 0) continue; 113 int pos = lower_bound(c.begin(), c.end(), -c[i] + 1) - c.begin(); 114 ans += i - pos; 115 } 116 117 cout << ans << endl; 118 119 return 0; 120 } 121 ``` 122 123 [1324E - Sleeping Schedule](/contest/1324/problem/E "Codeforces Round 627 (Div. 3)") 124 125 **Tutorial** 126 127 Tutorial is loading... 128 129 **Solution** 130 131 ``` 132 #include <bits/stdc++.h> 133 134 using namespace std; 135 136 bool in(int x, int l, int r) { 137 return l <= x && x <= r; 138 } 139 140 int main() { 141 #ifdef _DEBUG 142 freopen("input.txt", "r", stdin); 143 // freopen("output.txt", "w", stdout); 144 #endif 145 146 int n, h, l, r; 147 cin >> n >> h >> l >> r; 148 vector<int> a(n); 149 for (auto &it : a) cin >> it; 150 vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MIN)); 151 dp[0][0] = 0; 152 int sum = 0; 153 for (int i = 0; i < n; ++i) { 154 sum += a[i]; 155 for (int j = 0; j <= n; ++j) { 156 dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + in((sum - j) % h, l, r)); 157 if (j < n) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + in((sum - j - 1) % h, l, r)); 158 } 159 } 160 161 cout << *max_element(dp[n].begin(), dp[n].end()) << endl; 162 163 return 0; 164 } 165 ``` 166 167 [1324F - Maximum White Subtree](/contest/1324/problem/F "Codeforces Round 627 (Div. 3)") 168 169 **Tutorial** 170 171 Tutorial is loading... 172 173 **Solution** 174 175 ``` 176 #include <bits/stdc++.h> 177 178 using namespace std; 179 180 vector<int> a; 181 vector<int> dp; 182 vector<int> ans; 183 vector<vector<int>> g; 184 185 void dfs(int v, int p = -1) { 186 dp[v] = a[v]; 187 for (auto to : g[v]) { 188 if (to == p) continue; 189 dfs(to, v); 190 dp[v] += max(dp[to], 0); 191 } 192 } 193 194 void dfs2(int v, int p = -1) { 195 ans[v] = dp[v]; 196 for (auto to : g[v]) { 197 if (to == p) continue; 198 dp[v] -= max(0, dp[to]); 199 dp[to] += max(0, dp[v]); 200 dfs2(to, v); 201 dp[to] -= max(0, dp[v]); 202 dp[v] += max(0, dp[to]); 203 } 204 } 205 206 int main() { 207 #ifdef _DEBUG 208 freopen("input.txt", "r", stdin); 209 // freopen("output.txt", "w", stdout); 210 #endif 211 212 int n; 213 cin >> n; 214 a = dp = ans = vector<int>(n); 215 g = vector<vector<int>>(n); 216 for (int i = 0; i < n; ++i) { 217 cin >> a[i]; 218 if (a[i] == 0) a[i] = -1; 219 } 220 for (int i = 0; i < n - 1; ++i) { 221 int x, y; 222 cin >> x >> y; 223 --x, --y; 224 g[x].push_back(y); 225 g[y].push_back(x); 226 } 227 228 dfs(0); 229 dfs2(0); 230 for (auto it : ans) cout << it << " "; 231 cout << endl; 232 233 return 0; 234 } 235 ```