B - Bitwise Exclusive-OR Sequence
题意
\(n\)个数，\(m\)个关系，每个关系形如 \(a_u⊕a_v=w\)，表示第\(u\)个数与第\(v\)数的异或运算结果为\(w\)。求是否有这样的\(n\)个数满足所有关系要求，如果没有输出\(-1\)，如果有输出所有满足要求的方案中，所有数字的和的最小值。
思路
建图，处理每个连通块，选取源点赋值为\(0\)(因为要求最小)，途中出现矛盾直接输出\(-1\)，否则从低位到高位统计每一位上\(0\)和\(1\)的出现次数，最后相加计算最小值。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 1e6 + 5;
int n, m, idx;
int to[mxn], nxt[mxn], head[mxn], edge[mxn], point[mxn], pre[mxn], sz[mxn];
void add(int u, int v, int w)
{
to[++idx] = v;
edge[idx] = w;
nxt[idx] = head[u];
head[u] = idx;
}
void init()
{
fill(point, point + n, -1);
fill(sz, sz + n, 1);
iota(pre, pre + n, 0);
}
int find(int x)
{
return (x == pre[x] ? x : pre[x] = find(pre[x]));
}
void join(int u, int v)
{
int fu = find(u);
int fv = find(v);
if (fu != fv)
{
pre[fu] = fv;
sz[fv] += sz[fu];
}
}
void solve()
{
cin >> n >> m;
init();
if (!m)
{
cout << 0 << endl;
return;
}
for (int i = 0; i < m; i++)
{
int u, v, w;
cin >> u >> v >> w;
u--, v--;
add(u, v, w);
add(v, u, w);
join(u, v);
}
int ans = 0;
for (int i = 0; i < n; i++)
{
if (find(i) != i)
{
continue;
}
vector<int> cnt(30);
queue<int> q;
q.push(i);
point[i] = 0;
while (q.size())
{
int u = q.front();
q.pop();
for (int j = head[u]; j; j = nxt[j])
{
int v = to[j];
if (point[v] == -1)
{
point[v] = (point[u] ^ edge[j]);
q.push(v);
for (int k = 0; k < 30; k++)
{
cnt[k] += ((point[v] >> k) & 1); // 统计1的个数
}
}
else
{
if ((point[u] ^ point[v]) != edge[j]) // 前后矛盾
{
cout << -1 << endl;
return;
}
}
}
}
for (int j = 0; j < 30; j++)
{
ans += (1LL << j) * min(cnt[j], sz[i] - cnt[j]); // 二进制加法，cnt是1的个数，sz-cnt是0的个数，min(cnt[j], sz[i] - cnt[j])其实是当前连通快中第j位的贡献
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
E - Edward Gaming, the Champion
题意
给个字符串，找有几个"edgnb"。
思路
模拟。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
string s;
cin >> s;
if (s.size() < 5)
{
cout << 0 << endl;
return;
}
int ans = 0;
for (int i = 0; i <= s.size() - 5; i++)
{
if (s[i] == 'e' && s[i + 1] == 'd' && s[i + 2] == 'g' && s[i + 3] == 'n' && s[i + 4] == 'b')
{
ans++;
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
F - Encoded Strings I
题意
给定一个长度为\(n(n≤1000)\)的字符串\(s\)，定义函数\(Fs:Fs(c)=chr(G(c, S))\)，表示将\(S\)中的每个字符\(c\)转换为\(chr(G(c, S))\)，其中\(G(c, S)\)表示\(S\)中最后一次出现\(c\)之后的后缀中不同的字符个数，\(chr(i)\)表示第\(i\)个字符(第个\(0\)字符是 \(a\)，第\(1\)个是\(b\)…)。要求你对\(s\)的每个非空前缀代入到函数中，得到\(n\)个字符串，输出按照字典序排序的最大字符串。
思路
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 1e3 + 5;
unordered_map<char, int> cnt[mxn];
void solve()
{
int n;
string s;
cin >> n >> s;
for (int i = n; i >= 1; i--)
{
int cntt = 0;
unordered_set<char> vis;
for (int j = i - 1; j >= 0; j--)
{
if (!vis.count(s[j]))
{
vis.insert(s[j]);
cnt[i][s[j]] = cntt++;
}
}
}
set<string, greater<string>> ans;
for (int i = n; i >= 1; i--)
{
string t = s.substr(0, i);
for (int j = i - 1; j >= 0; j--)
{
t[j] = cnt[i][t[j]] + 'a';
}
ans.insert(t);
}
cout << *ans.begin() << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
J - Luggage Lock
题意
四位密码锁，每次能把一位或连续的几位向上或向下转动一个单位。现给两个密码\(A\)和\(B\)，求从\(A\)到\(B\)的最少操作数。
思路
\(T\)挺大，一个个来铁超时，直接从\(0000\)开始用\(bfs\)打表，查的时候就可以等价于查\(0000\)\(A\)和\(B\)之间的差值，即查\(1234\)到\(4689\)相当于查\(0000\)到\(3455\)。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<string, int> pii;
map<string, int> ans;
set<string> vis;
string cmd[] = { "1000","0100", "0010", "0001", "1100", "0110", "0011", "1110","0111", "1111", "2000","0200", "0020", "0002", "2200", "0220", "0022", "2220", "0222", "2222" }; // 1代表+，2代表-
string change(string s, int idx)
{
string res = s;
for (int i = 0; i < 4; i++)
{
if (cmd[idx][i] == '1')
{
res[i]++;
if (res[i] > '9')
{
res[i] = '0';
}
}
else if (cmd[idx][i] == '2')
{
res[i]--;
if (res[i] < '0')
{
res[i] = '9';
}
}
}
return res;
}
void bfs()
{
queue<pii> q;
q.push({ "0000", 0 });
vis.insert("0000");
while (q.size())
{
string cur = q.front().first;
int cnt = q.front().second;
q.pop();
for (int i = 0; i < 20; i++) // 把cur的全部情况都存了
{
string t = change(cur, i);
if (!vis.count(t))
{
vis.insert(t);
ans[t] = cnt + 1;
q.push({ t, cnt + 1 });
}
}
}
}
void solve()
{
string a, b;
cin >> a >> b;
if (a == b)
{
cout << 0 << endl;
return;
}
string t = "";
for (int i = 0; i < 4; i++)
{
t.push_back((b[i] - a[i] + 10) % 10 + '0');
}
cout << ans[t] << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
bfs();
while (T--)
{
solve();
}
return 0;
}