首页 > 其他分享 >2021沈阳icpc

2021沈阳icpc

时间：2023-07-14 23:33:50浏览次数：42  
标签：const int 沈阳 rhs long icpc 2021 return dp

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

相关文章

  • 2022ICPC杭州站 A （裴蜀 + 扩欧）
    题目链接：A题意：给定一个序列\(a\)，让序列加上一个等差序列，求出总和%$m$的最小值以及等差序列的\(s\)和公差\(d\)。思路：定义\(a\)序列总和为sum。则求解的答案为\((sum+n∗s+n∗(n+1)2∗d)\)%m的最小值。根据裴蜀定理得到原式等于\(sum+x∗gcd(n,n∗(n+1)/2)+y......
  • 2021 robocom 世界机器人开发者大赛-本科组（初赛）
    7-1懂得都懂题目描述：7-1懂的都懂众所周知，在互联网上有很多话是不好直接说出来的，不过一些模糊的图片仍然能让网友看懂你在说什么。然而对这种言论依然一定要出重拳，所以请你实现一个简单的匹配算法。现在我们采集了原图的一些特征数据，由N个小于255的非负整数组成，假设对于......
  • NOI2021 题解
    [NOI2021]轻重边转化一下题意：每次给一条链染色，查一条链从\(x\)到\(y\)有几条边两端颜色相同。那这个随便树剖线段树就好了。也可以LCT，码量可能要小点。#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>usingnamespace......
  • 洛谷 P6892 [ICPC2014 WF] Baggage
    洛谷传送门感觉这题递归的思想挺值得借鉴的。特判\(n=3\)。首先根据样例不难猜测最小次数为\(n\)。事实上最小次数下界为\(n\)，因为设\(x\)为当前相邻元素相同对数，不难发现除第一次操作外\(x\)最多增加\(2\)，而终态中\(x=2n-2\)。我们尝试构造能达到下界的方案。......
  • CMU15-445Project_2021Fall
    本文为CMU15-445(2021Fall)的lab记录。推荐博客：https://blog.csdn.net/twentyonepilots/article/details/120868216，逻辑写得比较清楚CMU-15445官方网页https://15445.courses.cs.cmu.edu/fall2021/assignments.htmlProject#1-BufferPoolTASK#1-LRU剔除策略可以先......
  • 记录Unity2021接入穿山甲SDK的几个问题
    Unity2021接入穿山甲SDK，打包一直有报错，费了不少心力，查了N多帖子（绝大部分没什么用），特别感谢ChatGPT提供的线索，最终打包成功，记录几个遇到的问题1、导入最新版本的ExternalDependencyManager，在Github下载源码：https://github.com/googlesamples/unity-jar-resolver；2、ExternalDepend......
  • Springcloud2021+Nacos2.2+Dubbo3+Seata1.6实现分布式事务
    示例代码地址：https://gitee.com/gtnotgod/Springcloud-alibaba.git更详细参考Gitee完整的项目：https://gitee.com/gtnotgod/Springcloud-alibaba.git官网下载Nacoshttps://nacos.io/zh-cn/index.html压缩包解压：配置Nacos：**/nacos/conf/application.properties#********......
  • 盘点2021年Apache年报中出现的国产项目
    盘点2021年Apache年报中出现的国产项目：ShardingSphere,IoTDB,CarbonData,Eagle,Kylin,Apisix,DolphinSchedulerandEcharts1、引言2021年8月31日，Apache软件基金会发布2021财年（2020年5月1日-2021年4月30日）年度报告，报告内容由Apache软件基金会概览、......
  • P7561[JOISC 2021 Day2] 道路の建設案 (Road Construction) 题解
    P7561[JOISC2021Day2]道路の建設案(RoadConstruction)题解题目描述JOI国是一个\(x\timesy\)的二维平面，王国里有\(n\)个城镇，分别编号为\(1,2,\cdots,n\in[1,2.5\times10^5]\)，其中第\(i\)个城镇的坐标为\((x_i,y_i)\)。在JOI国，正计划修建连接两座城......
  • 2021年电赛题目基于互联网的摄像测量系统（D题）
    基于互联网的摄像测量系统设计报告2021年全国大学生电子设计竞赛试题<10cmO拍摄方向θ1mx1m拍摄方向BA边长为1米的正方形测试区域l互联网参赛注意事项(1)11月4日8:00竞赛正式开始。本科组参赛队只能在【本科组】题目中任选一题；高职高专组参赛队在【高职高专组】题目中任......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99