B Bitwise Exclusive-OR Sequence
Description
给定 \(n\) 个数和 \(m\) 个限制：\(a_u\ a_v\ w\)，要求 \(a_u\bigoplus a_v=w\)
求这 \(n\) 个数的和的最小值。
Solution
最初的想法：
由于限制了\(0\leq w\leq 2^{30}\) ，所以考虑按位做。
对于第 \(i\) 位： 遍历所有的限制条件 \(a_u\ a_v\ w\)，如果 \(w\) 的第 \(i\) 位为 \(1\)（\((w>>i)\&1==1\)），则说明 \(a_u\) 和 \(a_v\) 的第\(i\) 位必须不同，给它俩连双向边。建完图之后对所有连通块染色，保证有边相连的两个点不同色，求出该位为 \(1\) 的最少数目 \(cnt\)，将 \((1<<i)*cnt\) 累加进答案。
以上有一个很严重的错误（大错特错（）：对于一个限制条件 \(a_u\ a_v\ w\)，它不仅限制了 \(a_u\) 和 \(a_v\) 在 \(w\) 为 \(1\) 的位上不同，也限制了 \(a_u\) 和 \(a_v\) 在 \(w\) 为 \(0\) 的位上相同。而上述思路不能保证其他位相同这个条件。考虑将限制该位相同的两数用并查集维护，将一个并查集内的点视作整体再考虑该位不同的限制，连边建图染色。
改进后：
对于第 \(i\) 位： 第一遍遍历所有的限制条件 \(a_u\ a_v\ w\)，如果 \(w\) 的第 \(i\) 位为 \(0\) ，则合并 \(a_u\ a_v\) 的并查集。第二遍遍历所有的限制条件 \(a_u\ a_v\ w\)，如果 \(w\) 的第 \(i\) 位为 \(1\)，则给二者所在的连通块之间连双向边。建完图之后进行黑白染色，累计答案。
Code
#include<iostream>
#include<vector>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
vector<int>to[N];
int n, m, fa[N], siz[N], col[N], tot1, tot0;
ll ans;
struct edge {
int u, v, w;
}a[N << 1];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int read()
{
int x = 0, y = 1;char c = getchar();
while (c < '0' || c>'9') { if (c == '-')y = -1;c = getchar(); }
while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + c - '0';c = getchar(); }
return x * y;
}
void init() {
for (int i = 1;i <= n;++i)
fa[i] = i, to[i].clear(), siz[i] = 0, col[i] = -1;
}
bool dfs(int u, int color) {
if (col[u] != -1) {
if (col[u] == color)
return 1;
return 0;
}
col[u] = color;
if (color)
tot1 += siz[u];
else tot0 += siz [u];
for (int i = 0;i < to[u].size();++i) {
int v = to[u][i];
if (!dfs(v, color ^ 1)) {
return 0;
}
}
return 1;
}
int main() {
n = read(), m = read();
for (int i = 1;i <= m;++i)
a[i] = { read(),read(),read() };
for (int i = 0;i < 30;++i){
init();
//STEP1:将限制该位相同的点合并并查集
for (int j = 1;j <= m;++j)
if ((a[j].w >> i) & 1 ^ 1) {
fa[find(a[j].u)] = find(a[j].v);
}
for (int i = 1;i <= n;++i)
++siz[find(i)]; //计算所有连通块的大小
//STEP2:给限制该位不同的点所在的并查集连边
for (int j = 1;j <= m;++j)
if ((a[j].w >> i) & 1) {
int u = a[j].u, v = a[j].v;
if (find(u) == find(v)) {
printf("-1\n"); //如果二者在同一个并查集内，则不合法
return 0;
}
u = find(u), v = find(v);
to[u].push_back(v);
to[v].push_back(u);
}
//STEP3:进行黑白染色
for (int j = 1;j <= n;++j)
if (j == fa[j] && col[j] == -1 && to[j].size()) {
tot1 = 0;
tot0 = 0;
if (!dfs(j, 0)){
printf("-1"); //不合法
return 0;
}
ans += (1ll << i) * min(tot0, tot1);
}
}
printf("%lld\n", ans);
return 0;
}
E Edward Gaming, the Champion
Description
给定一个字符串\(S\ (|S|\leq200000)\)，求其中 \(edgnb\) 出现的次数。
Solution
主要是进行一个\(string\)函数的复习（？）
\(st.find(s,x)\) 会返回 \(st\) 字符串从下标 \(x\) 开始第一个出现的 \(s\) 字符串的首字符下标；
若找不到，则返回\(st.npos\)。
Code
#include<iostream>
using namespace std;
int main() {
string s;
cin >> s;
int ind = 0, ans = 0;
while ((ind = s.find("edgnb", ind)) != s.npos) { //注意这里的括号
++ans;
++ind;
}
cout << ans << endl;
return 0;
}
F Encoded Strings I
Sol
范围很小，直接暴力枚举模拟计算即可。
Code
#include<iostream>
using namespace std;
int n, num[25];
string ori_s, s, ans = "";
void calc() {
int types = 0;
for (int i = 0;i < 20;++i)
num[i] = -1;
for (int i = s.length() - 1;i >= 0;--i){
int ind = s[i] - 'a';
if (num[ind] == -1)
num[ind] = types++;
}
for (int i = 0;i < s.length();++i)
s[i] = num[s[i] - 'a'] + 'a';
if (s > ans)
ans = s;
}
int main() {
cin >> n >> ori_s;
for (int i = 1;i <= n;++i) {
s = ori_s.substr(0, i);
calc();
}
cout << ans << endl;
return 0;
}
J Luggage Lock
Description
有一个四位密码锁，每一位取值范围为\([0,9]\)。
给定密码锁的初始状态 \(a_1a_2a_3a_4\) 和目标状态 \(b_1b_2b_3b_4\) 。
将对密码锁实施一步操作定义为：向上或向下同时转动连续的几位。（如 \(0000\) 可通过一步操作得到 \(0111\) 或 \(0990\) ，但无法得到 \(1001\)）。
求从初始状态转到目标状态的最小操作次数。
Solution
首先，将 \(b_1b_2b_3b_4\) 减去 \(a_1a_2a_3a_4\) 得到 \(c_1c_2c_3c_4\) ，题目等价于将 \(c_1c_2c_3c_4\) 转到 \(0000\)。
注意到，对于每一位，只会朝一个方向转到指定数字，不存在先向上转几位再向下转几位得到目标数字的情况。
所以可以枚举每一位的旋转方向，对于每种情况计算最少步数。
我设定：负数只能一直做加法直到\(0\)，正数只能一直做减法直到\(0\)。策略是：对于尽可能长连续的一段正数，共同减去这些数的最小值 \(x\) 并在答案累加上 \(x\) ，对于尽可能长连续的一段正数，共同加上这些数的最小的绝对值 \(x\)，同样在答案上累加\(x\)。
注意对于\(0\)的处理！！有三种情况：一直不动；向上转\(10\)次；向下转\(10\)次。认为不转一定比转优的想法是错误的，比如\(-5\ 0\ -6\ -2\)，若将 \(0\) 设定为 \(-10\)，则答案为 \(10\) ；若对 \(0\) 不做任何操作，则答案为 \(11\)。
#include<iostream>
#define inf 2e9
using namespace std;
int read()
{
int x = 0, y = 1;char c = getchar();
while (c < '0' || c>'9') { if (c == '-')y = -1;c = getchar(); }
while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + c - '0';c = getchar(); }
return x * y;
}
int ori[4], cur[4], tmp[4], ans = inf;
int tot;
int calc(int l, int r) {
if (l > r)
return 0;
if (l == r)
return abs(cur[l]);
for (int i = l;i <= r;++i)
if (cur[i] == 0)
return calc(l, i - 1) + calc(i + 1, r);
for (int i = l + 1;i <= r;++i)
if (cur[i] * cur[i - 1] < 0)
return calc(l, i - 1) + calc(i, r);
int x = inf;
for (int i = l;i <= r;++i)
x = min(x, abs(cur[i]));
for (int i = l;i <= r;++i) {
if (cur[i] < 0)
cur[i] += x;
else
cur[i] -= x;
}
return x + calc(l, r);
}
void dfs(int ind, bool type) {
if (ind == 4) {
for (int i = 0;i < 4;++i)
tmp[i] = cur[i];
ans = min(ans, calc(0, 3));
for (int i = 0;i < 4;++i)
cur[i] = tmp[i];
return;
}
if (type)
cur[ind] = ori[ind];
else {
if (ori[ind] < 0)
cur[ind] = ori[ind] + 10;
else if (ori[ind] > 0)
cur[ind] = ori[ind] - 10;
else { //这里！！不要漏掉不讨论！！
cur[ind] = 10;
dfs(ind + 1, 0);
dfs(ind + 1, 1);
cur[ind] = -10;
dfs(ind + 1, 0);
dfs(ind + 1, 1);
}
}
if (type || ori[ind] != 0) {
dfs(ind + 1, 0);
dfs(ind + 1, 1);
}
}
int main() {
int T = read();
while (T--) {
int x = read(), y = read();
for (int i = 0;i < 4;++i) {
int p1 = x % 10, p2 = y % 10;
x /= 10, y /= 10;
ori[i] = p2 - p1;
}
ans = inf;
dfs(0, 1);
dfs(0, 0);
printf("%d\n", ans);
}
return 0;
}
/*
2
1389 3874
6086 0883
*/