进攻
排序贪心
ll a[N];
PLL b[N];
int main() {
IOS; cin >> n >> m;
rep (i, 1, n) cin >> a[i];
rep (i, 1, m) cin >> b[i].se;
rep (i, 1, m) cin >> b[i].fi;
sort(b + 1, b + 1 + m, greater<PLL>());
sort(a + 1, a + 1 + n, greater<ll>());
ll ans = 0;
for (int i = 1, j = 1; i <= n && j <= m; ++i) {
while (j <= m && b[j].se >= a[i]) ++j;
if (j > m) break;
if (b[j].fi > 0) ans += b[j].fi;
else break;
}
cout << ans;
return 0;
}
二进制
拆位处理, 计算当前输入的数 第 i 位(二进制) 为 1/0 输出是什么
然后判断什么样的操作会使答案一样, 比如对于 第i为
与 x = (1<<20) - 1, 这样不会影响答案及 a & x = a
或 y = 0, 及 a | y = a
异或 z = 0, 及 a ^ z = 0
1/0 -> 1/1 必定是 x ^= 1 << i
1/0 -> 1/0 没改变
1/0 -> 0/1 z ^= 1 << i
1/0 -> 0/0 x ^= 1 << i
三次运算即可, 及 &x, |y, ^z
int main() {
IOS; cin >> n;
int a = (1 << 20) - 1, b = 0;
rep (i, 1, n) {
int op, x; cin >> op >> x;
if (op == 1) a &= x, b &= x;
else if (op == 2) a |= x, b |= x;
else a ^= x, b ^= x;
}
int x = (1 << 20) - 1, y = 0, z = 0;
rep (i, 0, 19)
if (!(a >> i & 1))
if (b >> i & 1) z ^= 1 << i;
else x ^= 1 << i;
else if (b >> i & 1) y ^= 1 << i;
cout << "3
3 " << z << "
1 " << x << "
2 " << y << '
';
return 0;
}
种树
往下遍历就行
ll w[N], c[N], dep[N], ans;
PII a[N];
void dfs(int x) {
if (a[x].fi) dep[a[x].fi] = dep[x] + 1, dfs(a[x].fi);
if (a[x].se) dep[a[x].se] = dep[x] + 1, dfs(a[x].se);
if (a[x].fi == 0 && a[x].se == 0 && dep[x] <= m) umax(ans, w[x]);
}
int main() {
IOS; cin >> n; m = ((n - 1) / 2 + 1) / 2;
rep (i, 1, n) cin >> a[i].fi >> a[i].se;
rep (i, 1, n) cin >> w[i];
ans = -2e9;
dfs(1); cout << ans;
return 0;
}
积木
构造吧, 就是四个同色拼成一个大的正方形就行
int main() {
IOS; cin >> n;
if (n & 1) { cout << -1; return 0; }
int f = 1;
for (int i = 1; i <= n; i += 2) {
for (int j = 1, g = f; j <= n; j += 2, g ^= 1)
a[i][j] = a[i][j + 1] = a[i + 1][j] = a[i + 1][j + 1] = g;
f ^= 1;
}
f = 0;
rep (k, 1, n) {
rep (i, 1, n) {
rep (j, 1, n) cout << (a[i][j] ^ f) << ' ';
cout << '
';
}
f ^= 1;
}
return 0;
}
考试
贪心
int main() {
IOS; cin >> n >> k;
rep (i, 1, n) cin >> a[i];
rep (i, 1, n) {
cin >> _;
if (_ == a[i]) ++m;
else if (k) --k, ++m;
}
m -= k; cout << m;
return 0;
}
项链
链表而已
int ne[N][2];
int main() {
IOS; cin >> n >> m;
rep (i, 1, n + 1) ne[i - 1][k ^ 1] = i, ne[i][k] = i - 1;
rep (i, 1, m) {
int op; cin >> op;
if (op == 1) {
int x, y; cin >> x >> y;
ne[ne[x][k]][k ^ 1] = ne[x][k ^ 1];
ne[ne[x][k ^ 1]][k] = ne[x][k];
ne[x][k] = y; ne[x][k ^ 1] = ne[y][k ^ 1];
ne[ne[y][k ^ 1]][k] = x;
ne[y][k ^ 1] = x;
} else if (op == 2) {
int x, y; cin >> x >> y;
ne[ne[x][k]][k ^ 1] = ne[x][k ^ 1];
ne[ne[x][k ^ 1]][k] = ne[x][k];
ne[x][k] = ne[y][k]; ne[x][k ^ 1] = y;
ne[ne[y][k]][k ^ 1] = x;
ne[y][k] = x;
}
else if (op == 3) k ^= 1;
else {
int i = 1;
for (i = 1; i != n + 1 && i; i = ne[i][k ^ 1]) cout << i << ' ';
for (i = (i ? ne[0][k ^ 1] : ne[n + 1][k ^ 1]); i != 1; i = ne[i][k ^ 1]) cout << i << ' ';
cout << '
';
}
}
return 0;
}
涂色
签到
int main() {
IOS; cin >> n;
cout << n + 1;
return 0;
}
园
签到
int main() {
IOS;
for (cin >> _; _; --_) {
cin >> x >> y >> r >> a >> b >> c;
if (r < c) swap(x, a), swap(y, b), swap(r, c);
ll d = sqr(x - a) + sqr(y - b);
long double dd = sqrt(d);
if (dd + c < r) cout << "NO
";
else if (dd + c == r) cout << "YES
";
else if (d > sqr(r + c)) cout << "NO
";
else cout << "YES
";
}
return 0;
}
修改
给你的序列a是任意的, 我们就人为添加一个 点(n+1) 且 a[n+1] = 0
每次操作 l, r, 可以使得 a[l] 和 a[r + 1] 变得相同
最终目标是所有点都可以和 a[n+1] 相同变成 0
这不就是最小生成树吗?
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
int main() {
IOS; cin >> n >> m; ++n;
rep (i, 1, n) f[i] = i;
rep (i ,1, m) cin >> a[i].se.fi >> a[i].se.se >> a[i].fi, ++a[i].se.se;
sort(a + 1, a + 1 + m);
ll ans = 0, cnt = 0;
rep (i, 1, m) {
int x = find(a[i].se.fi), y = find(a[i].se.se);
if (x != y) f[x] = y, ans += a[i].fi, ++cnt;
}
cout << (cnt == n - 1 ? ans : -1);
return 0;
}
克隆
发现是连通图， 剩下的不用说了吧
VI h[N];
int st[N << 1], top;
bool v[N];
void dfs(int x) {
v[x] = 1; st[++top] = x;
for (auto y : h[x]) if (!v[y]) dfs(y), st[++top] = x;
}
int main() {
IOS; cin >> n >> m >> k;
rep (i, 1, m) {
int u, v; cin >> u >> v;
h[u].pb(v); h[v].pb(u);
}
int a = ((n << 1) - 1) / k + 1;
dfs(1); cout << "YES
"; --top;
for (int c = 1; c <= top; --k) {
int d = min(a, top - c + 1);
cout << d << ' ';
rep (i, 1, d) cout << st[c++] << ' ';
cout << '
';
}
while (k--) cout << "0
";
return 0;
}