首页 > 其他分享 >[赛记] csp-s模拟6

[赛记] csp-s模拟6

时间：2024-10-05 11:02:05浏览次数：1  
标签：cnt 赛记 int long ++ htop include csp 模拟

一般图最小匹配 35pts

纯纯的错解35pts；

考虑将原数列排序，那么我们选的边就只能是相邻两个点的；

发现这玩意能够递推（赛时没发现），所以直接 $ DP $，设 $ f_{i, j} $ 表示当前考虑到第 $ i $ 位，有 $ j $ 条边被选的最小权值，转移时考虑第 $ i $ 个点连不连第 $ i - 1 $ 个点即可；

时间复杂度：$ \Theta(nm) $；

点击查看代码 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m;
long long a[5005];
long long f[5005][5005];
int main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);
	memset(f, 0x3f, sizeof(f));
	f[0][0] = 0;
	f[2][1] = a[2] - a[1];
	f[2][0] = 0;
	f[1][0] = 0;
	for (int i = 3; i <= n; i++) {
		for (int j = 0; j <= min(i / 2, m); j++) {
			if (j == 0) {
				f[i][j] = f[i - 1][j];
				continue;
			}
			f[i][j] = min(f[i - 1][j], f[i - 2][j - 1] + a[i] - a[i - 1]);
		}
	}
	cout << f[n][m];
	return 0;
}

重定向 95pts

少判断了一种情况，95pts；

大力分讨，对于两个数 $ a_i, a_{i + 1} $，考虑它们的四种 $ 0, 1 $ 情况，然后分别搞一搞就行；

注意多测，数组要清空；

还要注意 $ 0 $ 的时候可以把后面较小的数删掉放到这里来；

时间复杂度：$ \Theta(n \log n) $，瓶颈在二分查找 + 遍历和排序上；

点击查看代码 
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int t;
int n;
int a[2000005], b[2000005], c[2000005], mi[2000005], ans[2000005];
int main() {
	freopen("repeat.in", "r", stdin);
	freopen("repeat.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while(t--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			b[i] = a[i];
		}
		sort(b + 1, b + 1 + n);
		int csum = 0;
		for (int i = 1; i <= n; i++) {
			int o = lower_bound(b + 1, b + 1 + n, i) - b;
			if (b[o] != i) {
				c[++csum] = i;
			}
		}
		int mipos = n + 1;
		a[n + 1] = 0x3f3f3f3f;
		for (int i = n; i >= 1; i--) {
			if (a[i] == 0) mi[i] = mipos;
			else if (a[i] < a[mipos]) {
				mipos = i;
			}
		}
		int now = 1;
		int pos = 0;
		for (int i = 1; i <= n - 1; i++) {
			if (a[i] != 0 && a[i + 1] != 0) {
				if (a[i] > a[i + 1]) {
					pos = i;
					c[++csum] = a[i];
					break;
				}
			}
			if (a[i] == 0 && a[i + 1] != 0) {
				if (c[now] > a[mi[i]]) {
					if (a[mi[i]] < a[i + 1]) {
						pos = mi[i];
						c[++csum] = a[mi[i]];
						break;
					} else {
						pos = i;
						break;
					}
				} else {
					if (c[now] > a[i + 1]) {
						pos = i;
						break;
					} else {
						now++;
					}
				}
			}
			if (a[i] != 0 && a[i + 1] == 0) {
				if (a[i] > c[now]) {
					pos = i;
					c[++csum] = a[i];
					break;
				}
			}
			if (a[i] == 0 && a[i + 1] == 0) {
				if (a[mi[i]] < c[now]) {
					pos = mi[i];
					c[++csum] = a[mi[i]];
					break;
				}
				now++;
			}
		}
		sort(c + 1, c + 1 + csum);
		if (pos == 0) pos = n;
		now = 1;
		int asum = 0;
		for (int i = 1; i <= n; i++) {
			if (pos == i) continue;
			if (a[i] != 0) ans[++asum] = a[i];
			else {
				ans[++asum] = c[now];
				now++;
			}
		}
		for (int i = 1; i <= asum; i++) {
			cout << ans[i] << ' ';
		}
		cout << '\n';
		for (int i = 1; i <= n; i++) {
			a[i] = 0;
			b[i] = 0;
			c[i] = 0;
			mi[i] = 0;
			ans[i] = 0;
		}
	}
	return 0;
}

斯坦纳树 35pts

200行暴力35pts；

点击查看暴力 
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
struct sss{
	int t, ne;
	long long w;
}e[1000005];
int h[1000005], cnt;
void add(int u, int v, long long ww) {
	e[++cnt].t = v;
	e[cnt].ne = h[u];
	h[u] = cnt;
	e[cnt].w = ww;
}
struct sas{
	int f, t;
	long long w;
	bool operator <(const sas &A) const {
		return w < A.w;
	}
}ed[1000005];
int f[500005];
int find(int x) {
	if (x != f[x]) f[x] = find(f[x]);
	return f[x];
}
int ecnt;
int fa[500005], dep[500005], siz[500005], dfn[500005], nfd[500005], hson[500005], htop[500005], dcnt;
long long a[500005];
int b[500005], bcnt;
bool vis[500005];
bool cmp(int x, int y) {
	return dfn[x] < dfn[y];
}
namespace SEG{
	inline int ls(int x) {
		return x << 1;
	}
	inline int rs(int x) {
		return x << 1 | 1;
	}
	struct sss{
		int l, r;
		long long sum;
	}tr[3000005];
	inline void push_up(int id) {
		tr[id].sum = tr[ls(id)].sum + tr[rs(id)].sum;
	}
	void bt(int id, int l, int r) {
		tr[id].l = l;
		tr[id].r = r;
		if (l == r) {
			tr[id].sum = a[nfd[l]];
			return;
		}
		int mid = (l + r) >> 1;
		bt(ls(id), l, mid);
		bt(rs(id), mid + 1, r);
		push_up(id);
	}
	long long ask(int id, int l, int r) {
		if (tr[id].l >= l && tr[id].r <= r) {
			return tr[id].sum;
		}
		int mid = (tr[id].l + tr[id].r) >> 1;
		if (r <= mid) return ask(ls(id), l, r);
		else if (l > mid) return ask(rs(id), l, r);
		else return ask(ls(id), l, mid) + ask(rs(id), mid + 1, r);
	}
}
namespace TCS{
	void dfs1(int x, int f) {
		fa[x] = f;
		dep[x] = dep[f] + 1;
		hson[x] = -1;
		for (int i = h[x]; i; i = e[i].ne) {
			int u = e[i].t;
			if (u == f) continue;
			dfs1(u, x);
			siz[x] += siz[u];
			if (hson[x] == -1 || siz[hson[x]] < siz[u]) hson[x] = u;
		}
	}
	void dfs(int x) {
		for (int i = h[x]; i; i = e[i].ne) {
			int u = e[i].t;
			if (u == fa[x]) continue;
			a[u] = e[i].w;
			dfs(u);
		}
	}
	void dfs2(int x, int t) {
		htop[x] = t;
		dfn[x] = ++dcnt;
		nfd[dcnt] = x;
		if (hson[x] == -1) return;
		dfs2(hson[x], t);
		for (int i = h[x]; i; i = e[i].ne) {
			int u = e[i].t;
			if (u == fa[x] || u == hson[x]) continue;
			dfs2(u, u);
		}
	}
	int lca(int x, int y) {
		while(htop[x] != htop[y]) {
			if (dep[htop[x]] < dep[htop[y]]) swap(x, y);
			x = fa[htop[x]];
		}
		if (dfn[x] > dfn[y]) swap(x, y);
		return x;
	}
	long long ask(int x, int y) {
		long long ans = 0;
		while(htop[x] != htop[y]) {
			if (dep[htop[x]] < dep[htop[y]]) swap(x, y);
			ans += SEG::ask(1, dfn[htop[x]], dfn[x]);
			x = fa[htop[x]];
		}
		if (x == y) return ans;
		if (dfn[x] > dfn[y]) swap(x, y);
		ans += SEG::ask(1, dfn[x] + 1, dfn[y]);
		return ans;
	}
}
long long Kru() {
	long long ans = 0;
	for (int i = 1; i <= bcnt; i++) {
		for (int j = i + 1; j <= bcnt; j++) {
			ed[++ecnt] = {b[i], b[j], TCS::ask(b[i], b[j])};
		}
	}
	sort(ed + 1, ed + 1 + ecnt);
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	int tot = 0;
	for (int i = 1; i <= ecnt; i++) {
		if (tot == bcnt - 1) break;
		int x = find(ed[i].f);
		int y = find(ed[i].t);
		if (x != y) {
			f[x] = y;
			ans += ed[i].w;
		}
	}
	return ans;
}
int main() {
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int x, y;
	long long w;
	for (int i = 1; i <= n - 1; i++) {
		cin >> x >> y;
		cin >> w;
		add(x, y, w);
		add(y, x, w);
	}
	TCS::dfs1(1, 0);
	TCS::dfs(1);
	TCS::dfs2(1, 1);
	SEG::bt(1, 1, dcnt);
	if (n <= 500) {
		for (int i = 1; i <= n; i++) {
			cin >> x;
			b[++bcnt] = x;
			if (i == 1) {
				cout << 1;
				continue;
			}
			sort(b + 1, b + 1 + bcnt, cmp);
			for (int j = 1; j <= n; j++) vis[j] = false;
			long long ans = 0;
			int lc = b[1];
			for (int j = 2; j <= bcnt; j++) {
				lc = TCS::lca(lc, b[j]);
			}
			for (int j = 1; j <= bcnt; j++) {
				int x = b[j];
				while(x != lc) {
					if (!vis[x]) {
						vis[x] = true;
						ans += a[x];
					}
					x = fa[x];
				}
			}
			ecnt = 0;
			long long sum = Kru();
			if (sum == ans) cout << 1;
			else cout << 0;
		}
		return 0;
	}
	for (int i = 1; i <= n; i++) cout << 1;
	return 0;
}

其实正解也很暴力，考虑其正确当且仅当所有出现过的点的 $ lca $ 也出现过（即没有一个在出现过的点构成的虚树中没有出现过的点的度数 $ \geq 3 $）；

但是有边权为 $ 0 $ 的情况，我们将其缩成一个点即可；

那么我们可以钦定 $ b_1 $ 为根（有些人类智慧），然后每次遍历到一个新的 $ b_i $ 时就往上跳并把路径上经过的点标记一下，看第一个到达的被标记过的点在不在已经有的点中，若全都在则满足要求；

发现每个点最多只会被遍历一次，保证了时间复杂度；

对于不在的点的维护，我用的 set（主要是因为 erase empty insert 好用），所以时间复杂度为 $ \Theta(n \log n) $；

点击查看代码 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int n;
struct sss{
	int t, ne;
	long long w;
}e[1000005];
int h[1000005], cnt;
void add(int u, int v, int ww) {
	e[++cnt].t = v;
	e[cnt].ne = h[u];
	h[u] = cnt;
	e[cnt].w = ww;
}
int b[500005];
int belog[500005], sum;
void dfs(int x, int fa) {
	belog[x] = sum;
	for (int i = h[x]; i; i = e[i].ne) {
		int u = e[i].t;
		if (u == fa || belog[u]) continue;
		if (e[i].w == 0) dfs(u, x);
	}
}
int x[500005], y[500005];
long long w[500005];
vector<int> v[500005];
int fa[500005];
bool vis[500005], vi[500005];
void afs(int x, int f) {
	fa[x] = f;
	for (int i = 0; i < v[x].size(); i++) {
		int u = v[x][i];
		if (u == f) continue;
		afs(u, x);
	}
}
set<int> s;
int main() {
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {
		cin >> x[i] >> y[i];
		cin >> w[i];
		add(x[i], y[i], w[i]);
		add(y[i], x[i], w[i]);
	}
	sum = 0;
	for (int i = 1; i <= n; i++) {
		if (!belog[i]) {
			sum++;
			dfs(i, 0);
		}
	}
	for (int i = 1; i <= n - 1; i++) {
		if (belog[x[i]] != belog[y[i]]) {
			v[belog[x[i]]].push_back(belog[y[i]]);
			v[belog[y[i]]].push_back(belog[x[i]]);
		}
	}
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
	}
	afs(belog[b[1]], 0);
	cout << 1;
	vis[belog[b[1]]] = true;
	vi[belog[b[1]]] = true;
	for (int i = 2; i <= n; i++) {
		int x = belog[b[i]];
		while(!vis[x]) {
			vis[x] = true;
			x = fa[x];
		}
		vi[belog[b[i]]] = true;
		if (!vi[x]) {
			s.insert(x);
		}
		s.erase(belog[b[i]]);
		if (s.empty()) {
			cout << 1;
		} else {
			cout << 0;
		}
	}
	return 0;
}

标签：cnt,赛记,int,long,++,htop,include,csp,模拟
From： https://www.cnblogs.com/PeppaEvenPig/p/18447686

相关文章

  • 冲刺 CSP 联训模拟2
    题面温馨提示代码中的变量名可能与题意、题解不同。代码不删缺省源，可以直接拿来对拍。T1挤压Solution众所周知，异或是一种按位运算，不好进行十进制的数间合并。我们考虑将每个数拆分为二进制的形式进行处理。此时，对于每一种情况，假设表示\(2^i\)二进制位的值为\(b_i\)，我......
  • 冲刺 CSP 联训模拟 2
    T1挤压概率期望，二进制拆位看到异或想到拆位算贡献\[\begin{aligned}ans&=\sum_xx^2P(x)\\&=\sum_x(b_1+b_2+...+b_{30})^2P(x)\\\(b_i表示\x\二进制下\i\位的值)\\&=\sum_x(b_1b_1+b_1b_2+...b_{30}b_{29}+b_{30}b_{30})P(x)\\&=\sum_i^{30}\sum_j^{30......
  • 代码源CSP-S模拟赛Day7-9赛后总结
    代码源CSP-S模拟赛Day7-9赛后总结Day7赛时先扫一遍题，T1显然数位dp，感觉放在T1应该不难，而且题面有一种很亲切的感觉，感觉很可做。T2简单思考一下发现最终合成的数就是\(a_1\)，\(a_2\)，\(a_3\)……，\(a_n\)这n个数填正负号再加上一个k的倍数，估计会有一些比较智慧的手法，感觉很......
  • CSP-S 模拟赛34
    CSP-S模拟赛34T1考虑对原序列将\(k\)的左右分成两个序列。simple的想法是分别从\(1\)开始跑前缀和，每一次总跑到下一个小于它的点，然后依次类推。发现这样做碰到序列最小值之后难以继续。然而我们发现这样跑点的过程从前往后和从后往前是等价的。这样考虑的原因是发现这样......
  • CSP-S 模拟赛 32
    CSP-S模拟赛32rnk25，\(0+0+9+0=9\)。T1[CF1578K]KingdomofIslands还没改出来。T2[CF1578L]Labyrinth警钟嚼烂：改代码改干净。首先考虑如果从\(a\)走到\(b\)，人最胖是多少。毫无疑问，这是一个最大生成树问题。在这个基础上考虑原问题，我们发现由于人会越来越胖，一定有边......
  • 比赛记录（51~60）
    51CSP-S模拟赛321得分题目T1T2T3T4总分得分\(4\)\(20\)\(11\)\(27\)\(62\)排名：rank\(9\)。真正炸裂的一集。2题解T1考虑到边数较少，于是考虑能不能枚举边相关信息。通过部分分可以有如下讨论：\(c_u\nec_v\)时，意味着原先两点间有的边没了，那么两......
  • CSP-S模拟赛20241004
    A你考虑可以把这个数组当中的每个数表示成另一种形式：\(a_i=k_i\timesx+b\)(其中\(x\)是模数，\(b\)为余数)。对于求两个数是否对于某个余数同余，显然你要判断他们两个的差，即\(a_i-a_j\)，那么我们用上面那种形式表示其实就是\(a_i-a_j=(k_i-k_j)\timesx\),所以你要判断整个数......
  • CSP-JS多省分数线分析！复赛如何准备？（附复赛流程视频）
    截止目前已经有多个省份CSP-JS的分数线已经出了，很多省份比去年提升了不少，像河南等地都提升了20多分，不过也有一些省份，天津比去年提升分数却不是很多。还有很多省份分数线没出，各位家长想要预估是否能够晋级的，以下是已出分数线省份表格统计：目前已出分数线省份省份入门组......
  • [CSP-J 2023] 小苹果（apple）-----------用数组
    1#include<iostream>2usingnamespacestd;3intmain(){4intn,m;5cin>>n>>m;6intg=n,t=0,li,s[n+1],b;7for(inti=1;i<=n;i++){8s[i]=i;9}10while(g){11t+=1,b=0,li=0,g-=(g+......
  • CSP小苹果详细解法
    #include<bits/stdc++.h>usingnamespacestd;intmain(){intn,ant=0,t,j;cin>>n;cout<<"小苞的桌上一共放了"<<n<<"个苹果。"<<endl;inta[n+5],b[n+5];for(inti=1;i<=n;i++){a[i......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99