时间戳

首页 > 技术文章 > Educational Codeforces Round 109 (Rated for Div. 2)

Educational Codeforces Round 109 (Rated for Div. 2)

DreamW1ngs 2021-05-22 00:07 原文

比赛地址

A（水题）

题目链接
⭐

题目：
每次可以倒入1份药剂/水，请问最少多少

解析：
直接对浓度进行进行最简约分，输出分母即可

#include<bits/stdc++.h>
using namespace std;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {
	int T, n;
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		printf("%d\n", 100 / gcd(100, n));
	}
}

 

B（水题）

题目链接
⭐

题目：
给出\(1\sim n\)的排序，每次可以对子连续序列进行排序吗，问最多进行多少次操作以后可以使得数列有序

解析：
考虑到每次对\(n-1\)个序列进行排序的情况下（假设是对前\(n-1\)个数进行排序），如果\(1\)不在第\(n\)个位置，则下一次对后\(n-1\)个元素进行排序即可，同理如果\(n\)不在第1个位置，对后\(n-1\)个序列也可以达到相同的目的。但是当1在第\(n\)个位置且\(n\)在第\(1\)个位置时，必须先将\(1\)或\(n\)先置换出来，再进行如上步骤

#include<bits/stdc++.h>
using namespace std;

const int maxn = 55;
int dat[maxn];

int main() {
	int T, n;
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		bool ok = true;
		for (int i = 0; i < n; ++i) {
			scanf("%d", &dat[i]);
			if (i && dat[i] < dat[i - 1]) ok = false;
		}
		if (ok) printf("0\n");
		else {
			if (dat[0] == n && dat[n - 1] == 1) printf("3\n");
			else if (dat[0] == 1 || dat[n - 1] == n) printf("1\n");
			else printf("2\n");
		}
	}
}

 

C（思维+栈）

题目链接
⭐⭐⭐

题目：
在一个X轴区间[0,m]上，给出\(n\)个机器人的初始朝向以及位置，机器人在整数点相遇时会碰撞，两机器人均会消失，已知机器人每个单位时间行进一个单位长度，碰到区间端点时会反向前行，求出每个机器人撞毁的时间

解析：

  1. 不难发现，奇数位上的机器人一定不会与偶数位上的机器人相撞，这样就可以把机器人分成奇偶两类
  2. 对于任意一类机器人，可以考虑将向右走的机器人不断入栈，向左走的机器人与栈顶机器人相撞，时间很明显是二者之差除以二
  3. 但在栈空的情况下，向左走的机器人相当于从\(-x\)的位置向右移动，因此可以将\(-x\)入栈
  4. 同样思考如果扫描到最后栈内元素有多时，可以将向右走的机器人同样视为从\(2\times m-x\)的位置向左移，与次栈顶的元素相撞
  5. 如果最后栈内元素剩\(1\)，则代表此机器人永远无法被撞毁，赋予\(-1\)
#include<bits/stdc++.h>

using namespace std;


struct TT {
	int pos, id;
	bool dir;
};
stack<TT> s;
vector<TT> v[2];
const int maxn = 3e5 + 5;
int pos[maxn], n, m;

void solve(vector<TT>& v) {
	sort(v.begin(), v.end(), [](TT i, TT j) {return i.pos < j.pos; });
	for (auto& i : v) {
		if (i.dir)
			s.push(i);
		else {
			if (!s.empty()) {
				auto t = s.top(); s.pop();
				pos[i.id] = pos[t.id] = (i.pos - t.pos) / 2;
			}
			else s.push(TT{ -i.pos,i.id,1 });
		}
	}
	while (s.size() > 1) {
		auto t1 = s.top(); s.pop();
		auto t2 = s.top(); s.pop();
		pos[t1.id] = pos[t2.id] = (2 * m - t1.pos - t2.pos) / 2;
	}
	if (!s.empty()) {
		pos[s.top().id] = -1;
		s.pop();
	}
}

int main() {
	int T;
	char ch;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		v[0].clear(), v[1].clear();
		for (int i = 0; i < n; ++i)
			scanf("%d", &pos[i]);
		for (int i = 0; i < n; ++i) {
			scanf(" %c", &ch);
			v[pos[i] & 1].push_back(TT{ pos[i],i, ch == 'R' });
		}
		solve(v[1]), solve(v[0]);
		for (int i = 0; i < n; ++i)
			printf("%d ", pos[i]);
		printf("\n");
	}
}

 

D（dp）

题目链接
⭐⭐⭐

题目：
假设\(n\)个位置上至多有\(\lfloor\frac{n}{2}\rfloor\)上坐了人，用\(1\)表示，空座位用\(0\)表示，第\(i\)个人如果想要移动到第\(j\)个位置，则需要付出\(\mid i-j\mid\)的代价，现需另所有人不在原被占有位的最小代价

解析：

  1. 首先想到的做法是最小费用流，但是边大概有\(10^7\)条，会无情TLE，因此考虑DP的做法。
  2. 首先证明一个引理——如果要满足最小代价，则第\(i\)个空位置一定坐的\(1\sim i\)号人。假如第\(j_{mx}(j_{mx}>i)\)号人坐上了第\(i\)号位置，那么必然存在一个\(j_{mn}\)坐上了某个大于\(i\)的位置\(k\)，此时代价为\((j_{mx}-i)+(k-j_{mn})\)，但是如果二者位置互换，则代价为\((i-j_{mn})+(j_{mx}-k)\)，二者进行比较，不难发现左边恒大于右边，故引理成立
  3. 那么考虑用状态\(dp[i][j]\)代表前\(j\)个人坐在前\(i\)个空位时的最小代价，考虑第\(j\)个人是否坐第\(i\)个空位，不难得到状态转移方程

\[dp[i][j]=\max(dp[i][j-1],dp[i-1][j-1]+|p_{empty}[j]-p_{occupied}[i]|) \]

注意：
引理的作用主要用于进行迭代更新\(dp\)数组时，对于第\(i\)个空位只需要迭代\(\min(人的个数，i)\)
如果缺少引理，对结果其实没有影响，但是状态的定义会变得较为复杂与难以理解，较难寻找到正确的状态转移方程

#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e3 + 5;
int p[maxn];
vector<int> n1(1), n2(1);
int dp[maxn][maxn];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &p[i]);
		if (p[i]) n2.push_back(i);
		else n1.push_back(i);
	}
	for (int i = 0; i < n1.size(); ++i)
		for (int j = i + 1; j < n2.size(); ++j)
			dp[i][j] = 0x3f3f3f3f;
	for (int i = 1; i < n1.size(); ++i)
		for (int j = 1; j <= min(int(n2.size() - 1), i); ++j)
			dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1] + abs(n1[i] - n2[j]));
	printf("%d", n2.size() == 1 ? 0 : dp[n1.size() - 1][n2.size() - 1]);
}

 

E（思维+期望+组合数学）

题目链接
⭐⭐⭐⭐

题目：
给出\(n\)个城市以及\(m\)块区域，以及每座城市距离每块区域之间的距离，可以在第\(i(1\sim n)\)轮在某个城市内安插一个控制装置，能够掌控距离该城市距离在\(i\)以内的城池，问掌控城池的期望，答案模取\(998244353\)

解析：

  1. 对于答案——掌握城池和的期望，可以转化为每个城池被掌握的期望和，也就相当于每个城池被掌握的概率和
  2. 考虑第\(i\)个城市被掌握的概率，正向思考由于可能出现城市重叠控制区域的情况，难以轻松获得结果，因此可以反向思考，用\(1-区域不被控制的概率\)
  3. 而对于\(n!\)种安插控制装置的顺序下，可以反向迭代统计城市不被掌握时，安插控制装置的顺序。对于第\(i\)轮，可以选择所有距离大于\(i\)的城市中的一个。这个城市的数量可以进行动态的维护
#include<bits/stdc++.h>
using namespace std;

int d[25][50005];
typedef long long ll;
const ll mod = 998244353;

int cnt[25];

ll q_pow(ll x, ll n) {
	ll ans = 1;
	while (n) {
		if (n & 1) ans = ans * x % mod;
		n >>= 1;
		x = x * x % mod;
	}
	return ans;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			scanf("%d", &d[i][j]);
	ll inv = 1;
	for (int i = 2; i <= n; ++i)
		inv = inv * i % mod;
	inv = q_pow(inv, mod - 2);
	ll ans = 0;
	for (int j = 0; j < m; ++j) {
		memset(cnt, 0, sizeof(cnt));
		for (int i = 0; i < n; ++i)
			++cnt[d[i][j]];
		ll ret = 1, now = 0;
		for (int i = n; i >= 1; --i) {
			now += cnt[i + 1];
			ret = ret * now % mod;
			if (now-- == 0) break;
		}
		ans = ((ans + 1 - ret * inv % mod) % mod + mod) % mod;
	}
	printf("%lld", ans);
}

 

推荐阅读