Codeforces CodeTON Round 1

有没有一种可能,我其实是一个伞兵,离了队友啥都不会,但我的队友离了我反而更猛了?


E

队长给的做法是先随便找一个非叶子结点作为根,然后假设整棵树的和是 $s$,深度为 $1$ 的结点子树和是 $t$,那么就能推出除了根节点之外偶数深度的子树和都是 $s – t$,奇数深度的都是 $t$,进而推出每个点的点权和 $s, t$ 的关系。然后进一步发现令 $s = 1$ 或者 $t = 1$ 都是有解的。

题解的做法比较神奇,是黑白染色之后白点权值设为度数,黑点权值设为负的度数。不难证明这样搞之后每次划分的若干子树和都是 $1$ 或者 $-1$。

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 100005;

vector<int> G[maxn];
int pr[maxn];
int a[maxn], b[maxn];
int d[maxn];

void dfs(int x) {
	if (pr[x])
		d[x] = d[pr[x]] + 1;
	
	for (int y : G[x])
		if (y != pr[x]) {
			pr[y] = x;
			dfs(y);
		}

	int cnt = (int)G[x].size() - (bool)pr[x];

	// odd 1
	// even s - 1

	if (!(d[x] & 1)) {
		a[x] = 1;
		b[x] = -1 - cnt;

		if (!pr[x])
			b[x]++;
	}
	else {
		a[x] = -cnt;
		b[x] = 1 + cnt;
	}
}

int main() {

	ios::sync_with_stdio(false);

	int t;
	cin >> t;

	while (t--) {
		int n;
		cin >> n;

		for (int i = 1; i < n; i++) {
			int x, y;
			cin >> x >> y;
			G[x].push_back(y);
			G[y].push_back(x);
		}

		int r = 0;
		for (int i = 1; i <= n; i++)
			if ((int)G[i].size() > 1) {
				r = i;
				break;
			}
		
		dfs(r);
		
		set<int> st;
		for (int i = -n; i <= n; i++)
			st.insert(i);
		
		for (int i = 1; i <= n; i++) {
			int u = a[i], v = b[i];
			
			if (u) {
				if (abs(v) % abs(u) == 0)
					st.erase((-v) / u);
				
				if (u > 0) {
					while ((long long)u * *st.begin() + v < -100000)
						st.erase(*st.begin());
					
					while ((long long)u * *st.rbegin() + v > 100000)
						st.erase(*st.rbegin());
				}
				else {
					while ((long long)u * *st.begin() + v > 100000)
						st.erase(*st.begin());
					
					while ((long long)u * *st.rbegin() + v < -100000)
						st.erase(*st.rbegin());
				}
			}
		}

		int x = *st.begin();

		for (int i = 1; i <= n; i++) {
			cout << a[i] * x + b[i];

			if (i < n)
				cout << ' ';
			else
				cout << '\n';
		}

		for (int i = 1; i <= n; i++) {
			G[i].clear();
			pr[i] = 0;
			d[i] = 0;
			a[i] = b[i] = 0;
		}
	}

	return 0;
}

F

$a_i a_j + t(a_i + a_j)$ 对 $a_j$ 的偏导是 $a_i + t$,换言之是线性的,所以如果固定 $a_j$,显然 $a_i$ 依 $a_i + t$ 的正负不同只有可能连接 $a_i$ 最小的或者最大的。而两个最值中间肯定也有一条连边,所以直接就构造出了最小生成树。

把 $a_i$ 排个序之后发现直接按顺序扫就行了,只有当 $t = -a_i$ 的时候最小生成树才会变动一条边。维护一下 $f(t) = kt + b$ 即可,判一下 $t = -a_n$ 和 $t = -a_1$ 时的斜率即可区分出无界的情况。

(这题也太伞兵了,为什么我会连直接构造最小生成树都想不到啊。。)

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 200005;

int a[maxn];

int main() {

	ios::sync_with_stdio(false);

	int T;
	cin >> T;

	while (T--) {
		int n;
		cin >> n;

		for (int i = 1; i <= n; i++)
			cin >> a[i];
		
		sort(a + 1, a + n + 1);

		long long k = 0, b = 0;

		for (int i = 1; i < n; i++) {
			k += a[i] + a[n];
			b += (long long)a[i] * a[n];
		}

		bool inf = k < 0;

		long long ans = k * a[1] + b;

		for (int i = n - 1; i > 1; i--) {
			k -= a[n];
			k += a[1];
			b -= (long long)a[i] * a[n];
			b += (long long)a[i] * a[1];

			ans = max(ans, k * -a[i] + b);
		}

		inf |= k > 0;

		if (inf)
			cout << "INF\n";
		else
			cout << ans << '\n';
	}

	return 0;
}

G

挺妙的一个构造,思想实际上就是先构造出有多个环的排列,然后利用回文 $i$ 和 $n – i + 1$ 位置相等的性质把所有环进行合并。题解的做法是一次全部合并,不过我猜测两两合并也是可行的。(也许这个可以解释为什么最后一步合并和其他步骤不太一样。)

不过还没有完全理解,有空要再看看题解。

CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) Editorial – Codeforces

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 200005;

int ufs[maxn];

int findufs(int x) {
	return x == ufs[x] ? x : (ufs[x] = findufs(ufs[x]));
}

void link(int x, int y) {
	ufs[findufs(x)] = findufs(y);
}

vector<int> v[maxn];
int a[maxn], p[maxn], c[maxn];

int main() {

	int T;
	scanf("%d", &T);

	while (T--) {
		int n;
		scanf("%d", &n);

		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			v[a[i]].push_back(i);
		}

		bool bad = (count_if(v + 1, v + n + 1, [] (const auto &v) {return (bool)(v.size() & 1);}) > n % 2);

		if (n & 1)
			bad |= ((int)v[a[n / 2 + 1]].size() == 1);

		if (bad) {
			for (int i = 1; i <= n; i++)
				v[i].clear();
			
			printf("NO\n");
			continue;
		}
		
		if (n & 1) {
			int k = 0;
			for (int i = 1; i <= n; i++)
				if ((int)v[i].size() & 1) {
					k = i;
					break;
				}
			
			if (v[k].back() == n / 2 + 1)
				swap(v[k].back(), v[k][(int)v[k].size() - 2]);
			
			p[n / 2 + 1] = v[k].back();
			v[k].pop_back();
		}

		for (int i = 1, k = 1; i <= n / 2; i++) {
			while (v[k].empty())
				k++;
			
			p[i] = v[k].back();
			v[k].pop_back();

			p[n - i + 1] = v[k].back();
			v[k].pop_back();
		}

		for (int i = 1; i <= n; i++)
			ufs[i] = i;
		
		for (int i = 1; i <= n; i++)
			link(i, p[i]);
		
		for (int i = 1; i <= n / 2; i++)
			if (findufs(i) != findufs(n - i + 1)) {
				swap(p[i], p[n - i + 1]);
				link(i, n - i + 1);
			}
		
		for (int i = 1; i <= n; i++) {
			if (n % 2 && i == n / 2 + 1)
				continue;
			
			if (!c[findufs(i)])
				c[ufs[i]] = i;
		}
		
		int cnt = 0;
		for (int i = 1; i <= n; i++)
			cnt += (i == findufs(i));
		
		if (true || cnt > 1) {
			pair<int, int> pr;
			int k = 0;

			for (int i = 1; i <= n; i++)
				if (c[i]) {
					pair<int, int> t(p[c[i]], p[n - c[i] + 1]);
					if (k) {
						p[c[i]] = pr.second;
						p[n - c[i] + 1] = pr.first;
					}
					k = c[i];
					pr = t;
				}
			
			for (int i = 1; i <= n; i++)
				if (c[i]) {
					p[c[i]] = pr.first;
					p[n - c[i] + 1] = pr.second;
					break;
				}
		}
		
		printf("YES\n");
		for (int i = 1; i <= n; i++)
			printf("%d%c", p[i], i < n ? ' ' : '\n');

		for (int i = 1; i <= n; i++) {
			v[i].clear();
			c[i] = 0;
			p[i] = 0;
			ufs[i] = 0;
		}
	}

	return 0;
}

评论

  1. desprado2
    Windows Chrome
    2月前
    2022-3-28 19:33:46

    不是说多刷刷cf的题吗,这是怎么会事呢

    • 博主
      desprado2
      Windows Edge
      2月前
      2022-4-01 1:00:54

      因为有鸽子,甚至鸽了一天才看博客(

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇