T1 Array Coloring
https://codeforces.com/problemset/problem/1857/A
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> #include <algorithm> #include <vector> #include <cstring> using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) { int n; cin >> n; int cnt_odd = 0; while (n --) { int x; cin >> x; if (x & 1) cnt_odd ++; } if (cnt_odd & 1) cout << "NO\n"; else cout << "YES\n"; } } |
T2 Ten Words of Wisdom
https://codeforces.com/problemset/problem/1850/B
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) { int n; cin >> n; int ans = 0; int idx = 0; for (int i = 1; i <= n; ++ i) { int l, q; cin >> l >> q; if (l <= 10 && q > ans) { ans = q; idx = i; } } cout << idx << '\n'; } } |
T3 Running Miles
https://codeforces.com/problemset/problem/1826/D
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e5 + 10; int n; int b[N], lmax[N], rmax[N]; void toMax(int &a, int b) { if (a < b) a = b; } void solve() { cin >> n; for (int i = 1; i <= n; ++ i) cin >> b[i]; lmax[1] = b[1] + 1; // 预处理最值 for (int i = 2; i <= n; ++ i) { lmax[i] = max(lmax[i - 1], b[i] + i); } rmax[n] = b[n] - n; for (int i = n - 1; i; -- i) { rmax[i] = max(rmax[i + 1], b[i] - i); } int ans = 0; for (int i = 2; i < n; ++ i) { // 枚举中间元素 toMax(ans, b[i] + lmax[i - 1] + rmax[i + 1]); } cout << ans << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) { solve(); } } |
T4 Make It Permutation
https://codeforces.com/problemset/problem/1810/C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <iostream> #include <cstring> #include <algorithm> using namespace std; using LL = long long; const int N = 1e5 + 10; int a[N], n, c, d; void toMin(LL &a, LL b) { if (a > b) a = b; } void solve() { cin >> n >> c >> d; for (int i = 1; i <= n; ++ i) cin >> a[i]; sort(a + 1, a + 1 + n); int rep = unique(a + 1, a + 1 + n) - a - 1; LL ans = (LL)n * c + d; for (int i = 1; i <= rep; ++ i) { // 枚举排列 // 补齐前[1, a[i]]; 删掉[a[i + 1], a[n]]; toMin(ans, (LL)d * (a[i] - i) + (LL)c * (n - i)); } cout << ans << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) { solve(); } } |
T5 Easy Assembly
https://codeforces.com/problemset/problem/1773/E
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<vector<int>> a; vector<int> all; for (int i = 0; i < n; ++ i) { int k; cin >> k; a.push_back(vector<int>(k)); for (int j = 0; j < k; ++ j) { cin >> a[i][j]; all.push_back(a[i][j]); } } sort(all.begin(), all.end()); auto findpos = [&](int x) -> int { return lower_bound(all.begin(), all.end(), x) - all.begin(); }; // #define Debug #ifdef Debug for (auto vx: a) { for (auto val: vx) { cout << findpos(val) << ' '; } cout << endl; } #endif int sum_block = 0; for (auto vx: a) { #ifdef Debug cout << "EEEEEEEEE\n"; #endif int siz = vx.size(), block = 1; #ifdef Debug cout << "size:" << siz << endl; #endif if (siz != 1) { // 切块 若只有一个就不用切 block = 0; for (int i = 0; i < siz; ++ i) { int j = i + 1; while (j < siz && findpos(vx[j]) == findpos(vx[j - 1]) + 1) { #ifdef Debug cout << "pos(j) " << findpos(j) << endl; cout << "pos(j - 1) " << findpos(j - 1) << endl; #endif j ++; } #ifdef Debug cout << j << endl; #endif i = j - 1; block ++; } } sum_block += block; } int split = sum_block - n, combine = sum_block - 1; cout << split << ' ' << combine << endl; } |
T6 Tavas and SaDDas
https://codeforces.com/problemset/problem/535/B
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int n, a; string s; int dfs(int pos) { if (pos == s.size() - 1) return s[pos] == '4' ? 1: 2; int ans = 0; char c = s[pos]; char now = '4'; if (now < c) ans += 1 << (n - 1 - pos); else if (now == c) ans += dfs(pos + 1); now = '7'; if (now < c) ans += 1 << (n - 1 - pos); else if (now == c) ans += dfs(pos + 1); return ans; } int main() { cin >> a; s = to_string(a); n = s.size(); int add = 0; for (int i = 1; i < n; ++ i) { add += 1 << i; } cout << dfs(0) + add << endl; } |
T7 Chessboard
https://codeforces.com/problemset/problem/961/C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int n; struct square { int a[N][N]; int stA = -1; int stB = -1; void read() { string line; for (int i = 1; i <= n; ++ i) { getline(cin, line); for (int j = 1; j <= n; ++ j) a[i][j] = line[j - 1] - '0'; } } void out() { for (int i = 1; i <= n; ++ i, cout << endl) for (int j = 1; j <= n; ++ j) cout << a[i][j] << ' '; } int step_to_A() { // i+j偶数时a[i][j]=1 (i+j a[i,j]奇偶性不同) if (stA != -1) return stA; int ans = 0; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) if (a[i][j] != ((i + j) & 1)) ans ++; return stA = ans; } int step_to_B() { // (i+j a[i,j]奇偶性相同) if (stB != -1) return stB; int ans = 0; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) if (a[i][j] == ((i + j) & 1)) ans ++; return stB = ans; } } board[4]; int order[3][4] = { {0, 1, 2, 3}, {0, 1, 3, 2}, {0, 2, 3, 1} }; /*最后形成的棋盘可能有两种 1. 1 0 0 1 2. 0 1 1 0 n为奇数所以每个角落的颜色都一样 设A为角落颜色==1 B为角落颜色==0 */ int main() { cin >> n; for (int i = 0; i < 4; ++ i) { getchar(); board[i].read(); // cout << char('A' + i) << endl; // board[i].out(); // cout << board[i].step_to_A() << ' ' << board[i].step_to_B() << endl; // cout << "EEEEEEEEEE\n"; } int ans = 2e9; for (int i = 0; i < 3; ++ i) { square &a = board[order[i][0]]; square &b = board[order[i][1]]; square &c = board[order[i][2]]; square &d = board[order[i][3]]; int now = min( a.step_to_A() + b.step_to_B() + c.step_to_B() + d.step_to_A(), a.step_to_B() + b.step_to_A() + c.step_to_A() + d.step_to_B() ); ans = min(ans, now); } cout << ans << endl; } |
T8 Dima and a Bad XOR
https://codeforces.com/problemset/problem/1151/B
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 510; int a[N][N]; int main() { cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) { cin >> a[i][j]; } vector<vector<int>> limit(n + 1, vector<int>(10, 2)); // 1表示全为1 0表示全为0 2表示都存在 vector<vector<int>> to1st_1(n + 1, vector<int>(10, -1)); // 表示找到当前行该位第一个1的位置 -1表示不存在 vector<vector<int>> to1st_0(n + 1, vector<int>(10, -1)); // 表示找到当前行该位第一个0的位置 -1表示不存在 for (int bit = 0; bit < 10; ++ bit) { for (int i = 1; i <= n; ++ i) { int mo = a[i][1] >> bit & 1; bool f = true; for (int j = 1; j <= m; ++ j) { int now = a[i][j] >> bit & 1; f = f && (now == mo); if (to1st_0[i][bit] == -1 && !now) to1st_0[i][bit] = j; if (to1st_1[i][bit] == -1 && now) to1st_1[i][bit] = j; } if (f) limit[i][bit] = mo; } } for (int bit = 0; bit < 10; ++ bit) { int f = -1; // 表示本位第一个可选的下标 -1不存在 int cnt1 = 0; // 记录本位1的个数 for (int i = 1; i <= n; ++ i) { if (limit[i][bit] == 2) { if (f == -1) f = i; } else if (limit[i][bit] == 1) { cnt1 ++; } } if (f != -1) { // 若存在可选则一定有答案 cout << "TAK\n"; if (cnt1 & 1) { // 奇数个1则选0 for (int i = 1; i <= n; ++ i) { int now = limit[i][bit]; if (now == 2) { cout << to1st_0[i][bit] << ' '; } else if (now == 1) { cout << to1st_1[i][bit] << ' '; } else { cout << to1st_0[i][bit] << ' '; } } } else { // 反之选1(只选一个) for (int i = 1; i <= n; ++ i) { int now = limit[i][bit]; if (now == 0) { cout << to1st_0[i][bit] << ' '; } else if (now == 1) { cout << to1st_1[i][bit] << ' '; } else if (i == f) { cout << to1st_1[i][bit] << ' '; } else { cout << to1st_0[i][bit] << ' '; } } } return 0; } else { if (cnt1 & 1) { cout << "TAK\n"; for (int i = 1; i <= n; ++ i) { int now = limit[i][bit]; if (now == 0) { cout << to1st_0[i][bit] << ' '; } else { cout << to1st_1[i][bit] << ' '; } } return 0; } } } cout << "NIE"; } |
T9 Two Pizzas
https://codeforces.com/problemset/problem/1185/F
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int M = 1 << 9; int prices[M + 5]; // 记录某状态下最小prices int num[M + 5]; // 表示某状态可以满足的人数 int st[M + 5]; // 表示p中某状态是否存在 int main() { cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; for (int i = 1; i <= n; ++ i) { // 读入friend状态 int x; cin >> x; int s = 0; while (x --) { int t; cin >> t; s |= 1 << (t - 1); } for (int bit = 0; bit < M; ++ bit) if (bit == (s | bit)) // 状态bit包含状态s // 即s可以满足的friend状态 num[bit] ++; } int max_sum = -1; // 最多可以满足的人数 int p1; // 第一个pizza编号 int p2; // 第二个pizza编号 int sum_price; // 总价格 for (int i = 1; i <= m; ++ i) { // 读入pizza状态 int cost; cin >> cost; int x; cin >> x; int pizza1 = 0; // pizza1状态 while (x --) { int t; cin >> t; pizza1 |= 1 << (t - 1); } for (int bit = 0; bit < M; ++ bit) { // 枚举状态或和 if (bit != (bit | pizza1)) continue; // 去除不合法情况 if (num[bit] < max_sum) continue; // 去除比当前答案小的情况 int pizza2 = bit ^ pizza1; // 计算状态二 if (!st[pizza2]) continue; // 去除不存在的状态 int now_sum = num[bit]; if (now_sum > max_sum || (now_sum == max_sum && cost + prices[pizza2] < sum_price)) { max_sum = now_sum; sum_price = cost + prices[pizza2]; p1 = st[pizza2]; p2 = i; } } for (int bit = 0; bit < M; ++ bit) { // 当前选择了pizza1对各个数据进行维护 if (pizza1 == (bit | pizza1)) { // p1可以满足bit时 if (!st[bit] || cost < prices[bit]) { // 维护最小价格与映射 st[bit] = i; prices[bit] = cost; } } } // 特别的当状态为0时记录的是所有选择中的最小值 if (!st[0] || cost < prices[0]) { st[0] = i; prices[0] = cost; } } cout << p1 << ' ' << p2; } |
T10 XOR-gun
https://codeforces.com/problemset/problem/1415/D
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e5 + 10, M = 60; int a[N]; int n; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; ++ i) cin >> a[i]; if (n > M) { cout << 1; } else { int ans = 2e9; for (int i = 1; i < n; ++ i) { int v1 = 0; for (int n1 = 1; i + n1 - 1 < n; ++ n1) { int r1 = i + n1 - 1; int l2 = i + n1; int v2 = 0; v1 ^= a[r1]; for (int n2 = 1; i + n1 + n2 - 1 <= n; ++ n2) { // [i, i+n1-1] [i+n1, i+n1+n2-1] int r2 = i + n1 + n2 - 1; v2 ^= a[r2]; if (v1 > v2) ans = min(ans, n1 + n2 - 2); } } } cout << (ans > n ? -1: ans); } } |
发表回复