2020-2021 ICPC Southeastern European Regional Programming Contest (SEERC 2020)解题报告

B. Reverse Game

大致题意

给出一段01序列，Alice和Bob可以依次轮流对10，110，100，1010进行反转，使其变成01，011，001，0101。Alice先开始操作，谁先无法操作则对手赢得游戏

解题思路

可以注意到，所有4种可以反转的字串，都是将1向串的右侧移动，所以结束时，所有的0都在1的左侧。继续观察操作序列，可以发现每一次操作，都可以使整个串的01逆序对（我们将0在1左侧定义为正序）数量减少1或2。所以只要我们统计所有的逆序对，这道题就变成了一个巴什博奕，将逆序对mod 3即可得到答案

E. Divisible by 3

大致题意

给出一个长度为\(n\)的数组，定义一段子数组的重量为其中两两乘积和。例如有数组\(b\)，对于\(l\)到\(r\)的子数组，其重量为对于所有\(l \le i < j \le r\)，\(b_ib_j\)的乘积。

求给出数组中重量能被3整除的子数组数量

\(n\)的范围：\(1 \le n \le 5\cdot 10^5\)

解题思路

对于\(10^5\)的数据范围，暴力枚举肯定不行。

定义数组为\(a\),子数组前缀和为\(sum_i\),子数组的重量为\(p_i\)

考虑使用dp的思路。对于任意一个子数组，如果在其之后添加一个新的\(a_i\),那么变化后的重量等于\((p_{i-1} + sum_{i-1} * a[i])\),所以其实只要知道\(p_{i-1}\)和\(sum_{i-1}\),我们就可以进行转移。而且因为这道题只要求我们求被3整除的数量，所以就可以在过程中进行对3取模，然后在每一位上\(0 - 3\)枚举\(p_{i-1}\)和\(sum_{i-1}\),一共9个状态进行转移

L. Neo-Robin Hood

大致题意

有\(n\)个人，对第\(i\)个人有\(m_i\)的财富，但他还需要\(p_i\)的财富来达到目标，你可以从任意的人手里抢走\(m_i\)并用来帮助其他人使其完成目标，你抢的人不能超过你所帮助完成目标了的人，求问你能抢的最多的人。

解题思路

?参考的优秀博客

在选择时，在选择（抢）的人数不变时，我们肯定想要抢到手里的钱尽可能多，这样才能帮助更多的人，来抢更多的钱。对于任意两人\(x,y\)，如果抢\(x\)帮助\(y\)，对手中的钱的贡献为\(m_x - p_y\)，如果抢\(y\)帮助\(x\)，那么对手中钱的贡献为\(m_y - p_x\)，当\(m_y - p_x > m_x - p_y\)时，我们就要反转策略，来获得最多的钱。

通过移项，我们将上式变为\(m_y + p_y > m_x + p_x\)，我们将每一个人按\(m_i + p_i\)进行降序排序，来获得最大贡献。

根据上述性质，我们可以确定，排序后在答案中，帮助的人都排在抢劫的人的后面。我们这时候统计对于每一个分界点，在这个点前面选\(k\)个数，能否大于这个点后面选\(k\)个数

由于选取的人数\(k\)满足单调（可以抢\(k\)个人，那抢\(k-1\)当人也没问题），所以\(k\)的值可以使用二分来查找

在check函数中

用优先队列来维护对于位置\(i\)，在其前面选\(k\)个数能抢到的最多的钱。反方向同样用一个优先队列维护帮助\(k\)个人要花的最少的钱。各用一个循环即可得到所有的位置的值。

如果对于任意一个位置\(i\)满足前面的值大于后面的值，说面对当前\(k\)有可行解，返回true，否则返回false

最终就可以得到最大的\(k\)

M. Mistake

大致题意

给定\(n,k,m\)

给出\(m\)组依赖关系，要求将给出的\(n * k\)个数分为\(k\)组，使每组内的先后顺序都满足前文依赖关系下的拓扑序。

解题思路

遍历\(n * k\)个数，对于遇到的每一个数，如果这个数此前没有出现过，那就把他放到第一组，如果出现过，那就放到第 出现的次数 + 1 组里。

有一个简单的证明

对于每一个数，如果它所依赖的数出现过，那么它依赖的数同样依次被放进了\(1,2,...,k\)中，所以这样的方法可以必定满足依赖方法。（所以本题中的依赖方案其实没什么用）

代码部分

B

#include
using namespace std;
using ll = long long;
void solve() {
	string s;
	cin >> s;
	int n = s.length();
	s = " " + s;
	ll sum = 0;
	ll cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (s[i] == '1') {
			cnt++;
		}
		else {
			sum += cnt;
		}
	}
	if (sum % 3 == 0)
		cout << "Bob\n";
	else
		cout << "Alice\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

E

#include
using namespace std;
using ll = long long;
const ll maxn = 5e5;
ll dp[maxn+10][3][3];
ll ans = 0;
void solve() {
	ll n;
	cin >> n;
	vector a(n + 1);
	for (ll i = 1; i <= n; i++) {
		cin >> a[i];
		dp[i][0][a[i] % 3]++;
	}

	for (ll i = 1; i <= n; i++) {
		for (ll j = 0; j < 3; j++) {
			for (ll k = 0; k < 3; k++) {
				dp[i][(j + (a[i] * k)) % 3][(k + a[i]) % 3] += dp[i - 1][j][k];
			}
		}
	}
	for (ll i = 1; i <= n; i++) {
		for (ll j = 0; j < 3; j++)
			ans += dp[i][0][j];
	}
	cout << ans << "\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

K

#include
using namespace std;
using ll = long long;
const ll maxn = 1e5;
struct pol {
	ll m, p;
}ps[maxn + 10];

bool cmp(pol a, pol b) {
	return a.m + a.p > b.m + b.p;
}
ll n;
bool check(ll k) {
	priority_queue, greater> p1;
	priority_queue, less> p2;
	vector pre(n + 10);
	vector suf(n + 10);
	ll t = 0;
	for (ll i = 1; i <= n; i++) {
		if (p1.size() < k)
			p1.push(ps[i].m), t += ps[i].m;
		else if (p1.top() < ps[i].m) {
			t += ps[i].m - p1.top();
			p1.pop();
			p1.push(ps[i].m);
		}
		pre[i] = t;
	}

	t = 0;
	for (ll i = n; i >= 1; i--) {
		if (p2.size() < k)
			p2.push(ps[i].p), t += ps[i].p;
		else if (p2.top() > ps[i].p) {
			t += ps[i].p - p2.top();
			p2.pop();
			p2.push(ps[i].p);
		}
		suf[i] = t;
	}

	for (ll i = k; i <= n - k; i++) {
		if (pre[i] - suf[i + 1] >= 0)
			return true;
	}
	return false;
}

void solve() {
	cin >> n;
	for (ll i = 1; i <= n; i++) {
		cin >> ps[i].m;
	}
	for (ll i = 1; i <= n; i++) {
		cin >> ps[i].p;
	}

	sort(ps + 1, ps + 1 + n, cmp);

	ll l = 1, r = n / 2;
	ll res = 0;

	while (l <= r) {
		ll mid = (l + r) / 2;
		if (check(mid)) {
			res = mid;
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	cout << res << "\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

M

#include
using namespace std;
const int maxn = 5e5;
set st[maxn + 10];
void solve() {
	int n, k, m;
	cin >> n >> k >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
	}
	for (int i = 1; i <= n * k; i++) {
		int t;
		cin >> t;
		if (st[t].empty()) {
			cout << 1 << " ";
			st[t].insert(1);
		}
		else{
			int tt = *prev(st[t].end()) + 1;
			cout << tt << " ";
			st[t].insert(tt);
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}