B.Bitwise Exclusive-OR Sequence
题意:
有\(n\)个数,他们满足\(m\)组限制,每组限制给出\(u, v\),满足a[u] ^ a[v] == w
,求这\(n\)个数的最小值
思路:
对于每一组\(u,v\),按位考虑,如果\(w\)上对应位是\(0\),意味着\(a_{u},a_{v}\)这一位一样,否则不一样,这是一个二分图问题,没一位考虑一个二分图,对一开始的点取\(01\)时的值取最小值即可
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
struct way {
int to, next, w;
}edge[M << 1];
int cnt, head[N];
void add(int u, int v, int w) {
edge[++cnt].to = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt;
}
bool vis[N];
int n, m, val[N];
int f[N];
int find(int x) {
if(f[x] == x) return x;
return f[x] = find(f[x]);
}
vector<int> vec[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 1; i <= m; i++) {
int x, y, w;
cin >> x >> y >> w;
add(x, y, w);
add(y, x, w);
f[find(x)] = find(y);
}
vector<int> mul(n);
for(int i = 1; i <= n; i++) {
f[i] = mul[i - 1] = find(f[i]);
}
sort(mul.begin(), mul.end());
mul.erase(unique(mul.begin(), mul.end()), mul.end());
int maxid = -1;
for(int i = 1; i <= n; i++) {
int id = lower_bound(mul.begin(), mul.end(), f[i]) - mul.begin() + 1;
vec[id].emplace_back(i);
maxid = max(maxid, id);
}
auto getBits = [&](int x, int k) {
return (x >> k) & 1;
};
auto setBits = [&](int &x, int k, int value) {
if(value == 1) {
x |= 1 << k;
} else if(getBits(x, k)) {
x ^= 1 << k;
}
};
using dfsType = void(int, int, int);
function<dfsType> dfs = [&](int u, int value, int bits) {
setBits(val[u], bits, value);
vis[u] = true;
for(int i = head[u]; i; i = edge[i].next) {
auto [v, _, w] = edge[i];
if(vis[v]) {
if(getBits(val[u], bits) ^ getBits(val[v], bits) ^ getBits(w, bits)) {
cout << -1 << endl;
exit(0);
}
} else {
dfs(v, getBits(w, bits) ^ getBits(val[u], bits), bits);
}
}
};
ll ans = 0;
for(int i = 1; i <= maxid; i++) {
for(int j = 0; j <= 30; j++) {
dfs(vec[i][0], 0, j);
ll sum1 = 0, sum2 = 0;
for(int u : vec[i]) {
sum1 += getBits(val[u], j) << j;
sum2 += (getBits(val[u], j) ^ 1) << j;
setBits(val[u], j, 0);
vis[u] = false;
}
ans += min(sum1, sum2);
}
}
cout << ans << endl;
return 0;
}
E.Edward Gaming, the Champion
题意:
给出一个字符串,计算有多少个"edgnb"
子串
思路:
"edgnb"
规模很小,暴力找即可
#include<bits/stdc++.h>
using namespace std;
int main() {
int t = 1;
while(t--) {
string s;
cin >> s;
int ans = 0;
for(int i = 0; i + 4 < s.size(); i++) {
if(s.substr(i, 5) == "edgnb") {
ans++;
}
}
cout << ans << endl;
}
return 0;
}
F.Encoded Strings I
题意:
定义对字符串\(s\)的每个字符\(c\)的映射为
\[F_{s}(c) =chr(G(s,c)) \]其中\(chr(i)\)为第\(i + 1\)个小写字母,\(G(s, c)\)为\(s\)中\(c\)最后一次出现位置之后的所有不同字符个数
求出\(s\)的所有前缀的中的字典序最大的映射结果
思路:
由于\(n\le1000\),考虑暴力,遍历所有前缀,从后到前计算,用set
维护后面的不同字符数,取最大结果
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
char chr(int x) {
return 'a' + x;
}
string solve(string s) {
set<char> set1;
map<char, int> map1;
for(int i = (int)s.size() - 1; ~i; i--) {
if(!map1.count(s[i])) {
map1[s[i]] = set1.size();
}
set1.emplace(s[i]);
}
for(char &ch : s) {
ch = chr(map1[ch]);
}
return s;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
string s;
cin >> s >> s;
string ans;
for(int i = 0; i < s.size(); i++) {
ans = max(ans, solve(s.substr(0, i + 1)));
}
cout << ans << endl;
return 0;
}
H.Line Graph Matching
题意:
给出一幅\(n\)个点,\(m\)条带权边的图,将边看成新点,如果边有公共点,则他们的新点有一条边,新边的权值为两个边的权值之和。找出新边的一个集合,使他们里面的集合中任意两条边都没有相交的点,并且是集合的新边权值之和最大化
思路:
如果选一个新边,即是选两条相邻原边,如果新边不相交,即选的原边也不相交,那么原问题就是对每条原边找一条相邻边匹配,匹配过的边不能匹配,使他们权值和最大。
接下来考虑整幅图的边的数量,如果是偶数,那么自然可以全选,当前点的度如果是奇数,多出来的一条边可以分给相邻点取匹配,因为是连通图,最后多出来的一条边总是可以找到另一条多出来的,此时最优策略是所有边全选。
当边的数量是奇数边时,我们需要删边,考虑怎么删,我们删一条权值最小的边应该是最优的。但如果边是桥,可能会留下两个奇数边的连通分量。我们需要考虑桥的特殊性。
- 当边不是桥,删去这条边原图一定还是联通的,此时变成了偶数边的情况,可以删去
- 当边是桥
- 如果删去他留下了两个偶数的连通分量,转换成了两个偶数边的图,可以考虑删去
- 如果删他剩下两个边为奇数的联通分量,他一定不是最优,因为删去他,两个连通分量又要删去一条最优的边,既然如此,为什么不直接删去两个连通分量中最优的边呢?或者假设这样的桥可以是最优的,那两个连通分量又可以这样做,一直到所有图都被删了,这显然不对。
所以我们只需要找出所有非桥和桥且分割成两个偶数边的连通分量的边取最小值,删去这个边即可
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
int n, m, depth[N];
vector<pair<int, int>> g[N];
int tot[N], min1 = 0x7fffffff;
int dp[N];
bool vis[N];
void dfs(int u, int fa) {
for(auto &[v, w] : g[u]) {
if(v == fa) continue;
if(depth[v] == 0) {
depth[v] = depth[u] + 1;
dfs(v, u);
dp[u] += dp[v];
tot[u] += 1 + tot[v];
if(dp[v] == 0) {
if(tot[v] % 2 == 0) {
min1 = min(min1, w);
}
} else {
min1 = min(min1, w);
}
} else {
min1 = min(min1, w);
if(depth[u] < depth[v]) {
dp[u]--;
tot[u]++;
} else if(depth[u] > depth[v]) {
dp[u]++;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
ll sum = 0;
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
sum += w;
}
if(m & 1) {
depth[1] = 1;
dfs(1, 0);
cout << sum - min1 << endl;
} else {
cout << sum << endl;
}
return 0;
}
这里引入两种dfs树上求割点和桥的方法
割点
一个点是割点当且仅当他有至少一颗子树内的所有点通过回边到的所有点的深度都不低于当前点
树形dp维护这一信息:
设
dp[u]
为u子树内能到的最浅深度,遍历所有能到的点\(v\),如果\(v\)是回边到的,即深度比u更浅,那么dp[u] = min(dp[u], depth[v])
,如果是儿子,那么dp[u] = min(dp[u], dp[v])
当且仅当存在至少一个\(v\)是儿子满足
dp[v] <= depth[u]
时,\(u\)是割点桥
一条边是桥当且仅当没有回边跨越这一条边
树形dp维护这样一个信息:
设
dp[u]
是跨越(u, fa[u])
这条边的回边数那么
dp[u] = dp[v] + (u向上的回边数) - (u向下的回边数)
遇到一条回边
(u, v)
时,可以在\(u, v\)任意一个地方操作一次即可,不要操作两次,此时(u, v)
一定没有桥,不用担心准确性比如在\(u\)处找到回边,令
dp[u]++, dp[v]--
即可
J.Luggage Lock
题意:
有四位滚轮密码,每一位的范围为\([0, 9]\),每次可以上下滚一位,\(0\)与\(9\)是相邻的。给出两个密码,问最少需要多少步才可以从一个密码到另一个密码
思路:
只需要找一个基准点,比如\(0000\),从这个基准点bfs
到其他状态,设\(f[s]\)是到\(0000\)状态\(s\)的最少步数,状态\(AB\)之间的步数就是\(0000\)到他们的差状态的步数,比如\(1234 \rightarrow\ 2356\)即\(0000 \rightarrow \ 1122\),直接查询即可
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
int main() {
#ifdef stdjudge
freopen("in.txt", "r", stdin);
auto TimeFlagFirst = clock();
#endif
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
map<string, int> map1;
queue<string> q;
q.emplace("0000");
map1["0000"] = 0;
auto solve = [&](string s, int sta, int len, int del) -> string {
for(int i = sta; i < sta + len; i++) {
s[i] += del;
if(s[i] > '9') s[i] -= 10;
else if(s[i] < '0') s[i] += 10;
}
return s;
};
while(!q.empty()) {
string s = q.front();
q.pop();
for(int i = 0; i < 4; i++) {
for(int j = 1; j <= 4 - i; j++) {
for(int k : {-1, 1}) {
string res = solve(s, i, j, k);
if(!res.empty() && !map1.count(res)) {
map1[res] = map1[s] + 1;
q.emplace(res);
}
}
}
}
}
int tt = 1;
cin >> tt;
while(tt--) {
string s, t;
cin >> s >> t;
auto work = [&]() {
string ret;
for(int i = 0; i < s.size(); i++) {
if(t[i] > s[i]) {
ret += t[i] - s[i] + '0';
} else if(t[i] < s[i]) {
ret += 10 + t[i] - s[i] + '0';
} else {
ret += '0';
}
}
return ret;
};
cout << map1[work()] << endl;
}
#ifdef stdjudge
freopen("CON","r",stdin);
cout << endl << "耗时:" << clock() - TimeFlagFirst << "ms" << endl;
cout << flush;
system("pause");
#endif
return 0;
}
L.Perfect Matchings
题意:
在一副有\(2n\)个点的完全图中,有\(2n-1\)条边是不可选择的,这\(2n-1\)条边是一棵树,在剩下的边选择\(n\)条,使\(n\)条中两两都不相交,有多少种选法?
思路:
正难则反,我们反着考虑有多少情况是不合法的,也就是,在树上选择了\(i\)条边的情况有多少种?此时树上匹配了\(2i\)个点,剩下\(2n-2i\)就是完全图中匹配的情况,完全图中匹配的也是总情况,先考虑这个
- 问题等价于:有\(n\)个球,\(n\)为偶数,分成\(\frac{n}{2}\)有多少种?
先考虑dp,设f[n]
就是原问题的答案,考虑有多少种可能可以与\(n\)号匹配,有\(n-1\)种,匹配完\(n\)号,剩下\(n-2\)个球,就是子问题f[n - 2]
的答案,即有f[n] = (n - 1) * f[n - 2]
- 再考虑树中选择边的情况
考虑树形dp,设dp[u][i][0/1]
为\(u\)子树内,匹配了\(i\)条边,根节点无/有被匹配的情况数。
考虑合并子树,合并后的子树如果是没匹配的,只能从合并前没匹配的子树转移来,合并的儿子无所谓
dp[u][i + j][0] = dp[u][i][0] * (dp[v][j][0] + dp[v][j][1])
根节点先前匹配过了,同上
dp[u][i + j][1] = dp[u][i][1] * (dp[v][j][0] + dp[v][j][1])
根节点现在匹配
dp[u][i + j + 1][1] = dp[u][i][0] * dp[v][j][0];
树上选\(k\)条边的答案即(dp[1][k][0] + dp[1][k][1]) * f[2n - 2k]
,即匹配\(2k\)个树上点,剩下\(2n-2k\)个完全图中匹配
利用容斥,答案即
\[f[2n] - \sum_{i = 1}^{2n-1}(-1)^{i + 1}(dp[1][i][0]+dp[1][i][1])f[2n-2i] \]需要注意的是:树上背包要枚举原子树大小和儿子大小而不是枚举合并后子树的大小!!!否则复杂度不对!!!
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 4e3 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
namespace ModInt {
const int P = mod;
using i64 = long long;
int norm(int x) {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
template<class T>
T power(T a, int b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Z {
int x;
Z(int x = 0) : x(norm(x)) {}
int val() const {
return x;
}
Z operator-() const {
return Z(norm(P - x));
}
Z inv() const {
assert(x != 0);
return power(*this, P - 2);
}
Z &operator*=(const Z &rhs) {
x = i64(x) * rhs.x % P;
return *this;
}
Z &operator+=(const Z &rhs) {
x = norm(x + rhs.x);
return *this;
}
Z &operator-=(const Z &rhs) {
x = norm(x - rhs.x);
return *this;
}
Z &operator/=(const Z &rhs) {
return *this *= rhs.inv();
}
friend Z operator*(const Z &lhs, const Z &rhs) {
Z res = lhs;
res *= rhs;
return res;
}
friend Z operator+(const Z &lhs, const Z &rhs) {
Z res = lhs;
res += rhs;
return res;
}
friend Z operator-(const Z &lhs, const Z &rhs) {
Z res = lhs;
res -= rhs;
return res;
}
friend Z operator/(const Z &lhs, const Z &rhs) {
Z res = lhs;
res /= rhs;
return res;
}
friend std::istream &operator>>(std::istream &is, Z &a) {
i64 v;
is >> v;
v %= P;
a = Z(v);
return is;
}
friend std::ostream &operator<<(std::ostream &os, const Z &a) {
return os << a.val();
}
};
}
using mint = ModInt::Z;
mint dp[N][N][2], tmp[N][N][2], f[M];
int sum[N], n;
vector<int> g[N];
void dfs(int u, int fa) {
dp[u][0][0] = 1;
for(int v : g[u]) {
if(v == fa) {
continue;
}
dfs(v, u);
//dp[u][i][0/1] 选/不选u, 使用了i条树边, 方案数有多少
for(int i = 0; i <= sum[u] + sum[v] + 1; i++) {
for(int j = 0; j <= 1; j++) {
tmp[u][i][j] = 0;
}
}
for(int i = 0; i <= sum[u]; i++) {
for(int j = 0; j <= sum[v]; j++) {
tmp[u][i + j][0] += dp[u][i][0] * (dp[v][j][0] + dp[v][j][1]);
tmp[u][i + j + 1][1] += dp[u][i][0] * dp[v][j][0];
tmp[u][i + j][1] += dp[u][i][1] * (dp[v][j][0] + dp[v][j][1]);
}
}
sum[u] += 1 + sum[v];
for(int i = 0; i <= sum[u]; i++) {
for(int j = 0; j <= 1; j++) {
dp[u][i][j] = tmp[u][i][j];
}
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cin >> n;
for(int i = 1; i < 2 * n; i++) {
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
dfs(1, 0);
f[0] = 1;
for(int i = 2; i < M; i += 2) {
f[i] = (i - 1) * f[i - 2];
}
mint ans = f[2 * n];
for(int i = 1; i < 2 * n; i++) {
if(i & 1) ans -= f[2 * n - 2 * i] * (dp[1][i][0] + dp[1][i][1]);
else ans += f[2 * n - 2 * i] * (dp[1][i][0] + dp[1][i][1]);
}
cout << ans << endl;
return 0;
}
标签:const,int,沈阳,rhs,long,icpc,2021,return,dp
From: https://www.cnblogs.com/yawnsheep/p/17555337.html