专栏文章

【RS十周年】比赛题解

hhxydz
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio3fc7u
此快照首次捕获于
2025/12/02 12:43
3 个月前
此快照最后确认于
2025/12/02 12:43
3 个月前
查看原文

Successful person

优先用大盒：先看 n 能否被 5 整除，若能，用 5 颗装盒子数最少，结果为 n / 5。
混合装尝试：若不能被 5 整除，看余数能否被 3 整除，能则用 5 颗装和 3 颗装组合。
逐步减 3 尝试：若上述都不满足，不断从 n 中减 3，每减一次检查剩余数量能否被 5 整除，能则计算总盒数。
若整个过程都没找到方案，输出 wwyytsn!，否则输出最少盒子数。
CPP
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int result = -1;
    if (n % 5 == 0) {
        result = n / 5;
    } else if ((n % 5) % 3 == 0) {
        result = n / 5 + (n % 5) / 3;
    } else {
        int temp = n;
        while (temp >= 3) {
            temp -= 3;
            if (temp % 5 == 0) {
                result = temp / 5 + (n - temp) / 3;
                break;
            }
        }
    }
    if (result == -1) {
        cout << "wwyytsn!";
    } else {
        cout << result;
    }
    return 0;
}

迷魂阵

（本来有个更难的小模拟的，但是后面题有点爆了，所以这题想着节省一点时间的）
每个棋子走到对面需要 n−1n - 1 步数，所以至少需要 2n(n−1)2n(n - 1) 步。如果某一列的黑子和白子同时向他们的正方向移动，那么会相撞。不妨让黑子在原来的列，白子进行交错。考虑第 ii 列的白子最后走到了第 pip_i 列，那么m多出来步数为
∑i=1n ∣i−pi∣\sum_{i = 1}^{n} \ {|i - p_i|}
由于 pi≠ip_i ≠ i，该和式存在下界⌈1x⌉⌈\frac{1}{x}⌉可以对相邻的两列 pi=i+1p_i = i + 1，p(i+1)=ip_(i+1) = i,当 nn 是偶数时这样直 接可以取到下界，而 nn 是奇数时，只需要前三列 p1=3,p2=1,p3=2p_1 = 3, p_2 = 1, p_3 = 2 即可，刚好满足下界。

代码1

CPP
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n;
    cin >> n;
    long long ans = n * (2 * n - 1);
	if (n & 1) cout << ans + 1 << endl;
	else cout << ans << endl;
    return 0;
}

代码2

CPP
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL n;
int main() {
    cin >> n;
    cout << 2 * n * (n - 1) + n + (n % 2);
    return 0;
}

地心历险

算法一

注意到图是三部图，如果令 si≡coli(mod3)s_i ≡ col_i(mod 3) 就复合条件了。图的性质不太好，先研究树的情况。
对于一个非根节点，显然可以通过父亲边调整权值。设 m=(coolroot−sroot)m = (cool_{root} - s_{root}) modmod 33 ，那么如果我们可以找到包含根的一个奇环，我们不断在上面 −m,+m-m, +m ，与根相连的两条边都是 −m-m ，这样相当于 +m+ m modmod 33。而其他点都不变，也就满足了条件。于是当这个图不是二分图时，找一个奇环上的点做根 即可。
接下来考虑二分图的情况，重新给图染色（只用 0101）。不妨令根的颜色为 00，这样只有当最后算出情况 是 11 的时候才会出错。可我们发现 22 这种点权还没用，这时我们不妨选两条边给其加 11，容易发现这时 并没有什么问题。可以选择度数大于 22 的点当根。

算法二

上述算法中直接构造只有根可能出错，故当根不合法时，重新随机选择根和 dfs 生成树。注意到题目只要求值不同而不是上面提到的模 33 与 coolicool_i 相同，故随意调整几次即可满足条件。
CPP
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define mp make_pair
using namespace std;
template <typename T>
void read(T &x) {
	T flag = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') flag = -1;
	for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	x *= flag;
}
const int maxn = 200005;
struct e{
	int u, v, val;
}ans[maxn];
int n, m;
char s[maxn];
int col[maxn], f[maxn], val[maxn], d[maxn];
vector<pair<int, int>> vec[maxn], t[maxn];
bool vis[maxn];
int tmp[maxn];
int flag, End;
int pre[maxn], num[maxn];
void dfs(int x, int fa, int id) {
	f[x] = fa;
	if (fa) t[x].pb(mp(fa, id));
	for (int i = 0; i < (int)vec[x].size(); i++) {
		int y = vec[x][i].first;
		if (f[y] > 0 || y == flag) continue;
		t[x].pb(mp(y, vec[x][i].second));
		dfs(y, x, vec[x][i].second);
	}
}
void get_ans(int x) {
	for (int i = 0; i < (int)t[x].size(); i++) {
		int y = t[x][i].first;
		if (y == f[x]) continue;
		get_ans(y);
		int m = col[y] - d[y];
		ans[t[x][i].second].val = m;
		d[y] = d[y] + m;
		d[x] = d[x] + m; 
	}
}
void get_ans2(int x) {
	for (int i = 0; i < (int)t[x].size(); i++) {
		int y = t[x][i].first;
		if (y == f[x]) continue;
		get_ans2(y);
		int m = tmp[y] - d[y];
		ans[t[x][i].second].val = m;
		d[y] = d[y] + m;
		d[x] = d[x] + m;
	}
}
void check(int x) {
	for (int i = 0; i < (int)vec[x].size(); i++) {
		int y = vec[x][i].first;
		if (tmp[y] == -1) tmp[y] = tmp[x] ^ 1, check(y);
		else {
			if (tmp[y] == tmp[x]) {
				flag = x;// 不是二分图 
			}
		}
	}
}
void yyy(int x) {
	for (int i =0; i < (int)vec[x].size(); i++) {
		int y = vec[x][i].first;
		if (tmp[y] != -1) continue;
		tmp[y] = tmp[x] ^ 1;
		yyy(y);
	}
}
int cnt[maxn];
void output() {
	for (int i = 1; i <= m; i++) {
		ans[i].val = (ans[i].val % 3 + 3) % 3;
		if (ans[i].val == 0) ans[i].val = 3;
		printf("%d\n", ans[i].val);
		cnt[ans[i].u] += ans[i].val;
		cnt[ans[i].v] += ans[i].val;
	}
}
void jjj(int x) {
	for (int i = 0; i < (int)vec[x].size(); i++) {
		int y = vec[x][i].first;
		if (tmp[y] == -1) tmp[y] = tmp[x] ^ 1, pre[y] = x, num[y] = vec[x][i].second, jjj(y);
		else {
			if (y == flag && tmp[x] == tmp[flag]) {
				End = x;
			}
		}
	}
}
void work() {
	tmp[1] = 0;
	check(1);
	if (flag) {// 不是二分图  
		dfs(flag, 0, 0);
		get_ans(flag);
		int m = (col[flag] - d[flag]);
		memset(tmp, -1, sizeof(tmp));
		tmp[flag] = 0;
		jjj(flag);
		for (int i = End; i != flag; i = pre[i]) {
			ans[num[i]].val += m;
			m = -m;
		}
		for (int i = 0; i < (int)vec[End].size(); i++) {
			if (vec[End][i].first == flag) ans[vec[End][i].second].val += m << 1;
		}
		output();
	} else {
		flag = 1;
		memset(tmp, -1, sizeof(tmp));
		tmp[1] = 0;
		
		yyy(flag);
		dfs(flag, 0, 0);
		get_ans2(flag);
		if ((d[1] % 3 + 3) % 3 == 1 && vec[1].size() > 1) {
			ans[vec[1][1].second].val++; ans[vec[1][2].second].val++;
		}
		output();
	}
}
int main() {
	memset(tmp, -1, sizeof(tmp));
	read(n); read(m);
	for (int i = 1; i <= n; i++) {
		read(col[i]); 
	}
	for (int i = 1; i <= m; i++) {
		int u, v;
		read(u); read(v);
		ans[i].u = u; ans[i].v = v;
		vec[u].pb(mp(v, i));
		vec[v].pb(mp(u, i));
	}
	for (int i = 1; i <= n; i++) reverse(vec[i].begin(), vec[i].end());
	work();
	return 0;
}

魔法屋

发现 aia_i −- (ai(a_i modmod j)j) 并不会改变
ailcm(1,2,...,k)\frac {a_i}{lcm(1,2,...,k)}
的值。记 L=lcm(1,2,...,k−1)L = lcm(1,2,...,k-1) ,于是可以分成两个部分，⌊ai/L⌋⌊a_i/L⌋ 和 aia_i modmod LL , 前者在操作的过程中不会变，总共会对答案有 ×nk−1×k×n^{k-1}×k 的贡献，后者较小，考虑动态规划。
记 fi,jf_{i,j} 代表值为 ii 的数，第 jj 次操作开始，后面对答案的总贡献。转移分成两部分，如果当前选中这个数，则从 fi−imodj,j+1f_{i-imodj,j+1} 转移，否则以 n−1n-1 系数从 fi,j+1f_{i,j+1} 转移。即
fi,j=fi−imodj,j+1+if_{i,j}=f_{i-imodj,j+1} + i ×× gi−imodj,j+1+(n−1)g_{i-imodj,j+1} + (n-1) ×× f(i,j+1)f_(i,j+1)
其中 gi,jg_{i,j} 代表方案数，是辅助数组。转移即为 gi,j=gi−imodj,j+1+(n−1)gi,j+1。g_{i,j} = g_{i-imodj,j+1}+(n-1)g_{i,j+1}。
而答案即为 ∑i=1n faimodL,1\sum_{i = 1}^{n} \ {f_{a_i} mod L,1}。注意到修改只是修改一个位置，那么其对答案的贡献可以 O(1)O(1) 表示，那么就做到了 O(1)O(1) 修改。有一些 dp 的做法可能无法做到 O(1)O(1) 修改，可惜hxydz太懒了脑子不够用了。
CPP
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 5, mod = 1e9 + 7;
template <typename T>
void read(T &x) {
	T sgn = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
	for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	x *= sgn;
}
int n, a[maxn], x, y, k, m, ans, cnt[maxn];
int f[20][720721], g[20][720721], pw[20], q;
int qmod(int x) { return x >= mod ? x - mod : x; }
int ksm(int a, int b = mod - 2) { int ret = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ret = 1ll * ret * a % mod; return ret; }
int main() {
	int lcm = 1;
	for (int i = 1; i <= 16; i++) lcm = lcm * i / __gcd(lcm, i);
	read(n); read(k);
	for (int i = 1; i <= n; i++) read(a[i]);
	pw[0] = 1;
	for (int i = 1; i <= k; i++) pw[i] = 1ll * pw[i - 1] * n % mod; 
	for (int i = 1; i <= n; i++)
		cnt[a[i] % lcm]++, ans = qmod(ans + 1ll * (a[i] / lcm * lcm) * pw[k - 1] % mod * k % mod);
	for (int i = 0; i < lcm; i++) g[k + 1][i] = 1;
	for (int i = k; i; i--)
	{
		for (int j = 0; j < lcm; j++)
		{
			f[i][j] = qmod(1ll * (n - 1) * f[i + 1][j] % mod + f[i][j]);
			f[i][j] = qmod(qmod(1ll * j * g[i + 1][j - j % i] % mod + f[i + 1][j - j % i]) + f[i][j]);
			g[i][j] = qmod(1ll * (n - 1) * g[i + 1][j] % mod + g[i + 1][j - j % i]);
		}
	}
	for (int i = 0; i < lcm; i++) ans = qmod(ans + 1ll * cnt[i] * f[1][i] % mod);
	printf("%d\n", ans);
	read(q);
	while (q--) {
		int x, y;
		read(x); read(y);
		ans = qmod(ans - 1ll * (a[x] / lcm * lcm) * pw[k - 1] % mod * k % mod + mod);
		ans = qmod(ans - f[1][a[x] % lcm] + mod);
		a[x] = y;
		ans = qmod(ans + 1ll * (a[x] / lcm * lcm) * pw[k - 1] % mod * k % mod);
		ans = qmod(ans + f[1][a[x] % lcm]);
		printf("%d\n", ans);
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...