T1
Topcoder SRM 583 div1 Medium - TurnOnLamps
发现取反一条路径相当于把两个端点到根的路径分别取反。所以只要考虑到根的情况。设 \(f[i]\) 表示 \(i\) 子树内所有边都合法的最小操作次数，则每个点只要把所有儿子的 \(f\) 加过来然后看到儿子的每条边是否合法即可。
代码
#include <iostream>
using namespace std;
string ini, imp;
int head[55], nxt[105], to[105], ecnt = -1;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int f[55];
void dfs(int x, int fa) {
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa) {
dfs(v, x);
f[x] += f[v];
f[x] += ((imp[i >> 1] != '0') && (((f[v] + ini[i >> 1] - '0') & 1) == 0));
}
}
}
int main() {
int n;
cin >> n;
++n;
for (int i = 2; i <= n; i++) {
int x;
cin >> x;
add(i, x + 1);
add(x + 1, i);
}
cin >> ini >> imp;
dfs(1, 0);
cout << (f[1] >> 1) + (f[1] & 1) << "\n";
return 0;
}
T2
Topcoder SRM 590 div1 Medium - XorCards
首先找有多少种不同的异或结果在 \(m\) 之内。考虑使用线性基。先把所有线性基消成每一列至多只有一个 \(1\) 的形式，然后二分一下求第 \(k\) 小异或值。这些值都是可以被表出的。接下来考虑那些没有成功插入线性基的数，这些数一定都可以被线性基中的数表出。所以对于任意一种这些数的选择方案，一定可以通过选择线性基中对应的能够表出这些数的数来让当前的异或和不变，从而对于每一种可行的异或值与每一种选择没有成功插入线性基的数的选择方案的组合都能够找到一种可行的选择若干数的合法方案。所以只需要把两个乘一下即可。
代码
#include <iostream>
#define int long long
using namespace std;
int n, lim;
int a[56, x[56, p[56;
int cnt;
void Insert(int v) {
for (int i = 55; ~i; i--) {
if (v & (1ll << i)) {
if (x[i])
v ^= x[i];
else {
x[i] = v;
return;
}
}
}
++cnt;
}
int pcnt;
void Deal() {
for (int i = 0; i <= 55; i++) {
for (int j = i - 1; ~j; j--) {
if (x[i] & (1ll << j))
x[i] ^= x[j];
}
}
for (int i = 0; i <= 55; i++) {
if (x[i])
p[pcnt++] = x[i];
}
}
int kth(int k) {
int ret = 0;
for (int i = 0; i <= 55; i++) {
if (k & (1ll << i))
ret ^= p[i];
}
return ret;
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], Insert(a[i]);
cin >> lim;
Deal();
int l = 0, r = (1ll << pcnt) - 1, mid, ans = 0;
while (l <= r) {
mid = (l + r) >> 1;
if (kth(mid) <= lim)
ans = mid, l = mid + 1;
else
r = mid - 1;
}
cout << ((ans + 1) << cnt) << "\n";
return 0;
}
T3
Topcoder SRM 597 div1 Medium - LittleElephantAndRGB
标签：head,imp,int,ecnt,Topcoder,线性,20240407 From： https://www.cnblogs.com/forgotmyhandle/p/18119439