Educational Codeforces Round 106
前言
个人练习中的一场，做出了 A ~ D 题，为数不多的做出 div2 的 D 题的一次，于是来写个题解。
EF 题待补。
A. Domino on Windowsill
题目
有一个 \(2 \times n\) 的网格，第一行前 \(k_1\) 个网格被涂成了白色，第二行前 \(k_2\) 个网格被涂成了白色，其余网格为黑色。
现有 \(w\) 个白色多米诺骨牌（\(1\times 2\) 的矩形，可以旋转）和 \(b\) 个黑色多米诺骨牌，只能放在对应颜色的网格上，问是否能放置所有 \(w+b\) 个多米诺骨牌。
多组数据。
样例输入 #1
2
1 0 1
1 0
1 1 1
0 0
样例输出 #1
NO
YES
题解
不难发现，最多能放白色骨牌的数量就是 \(\lfloor \frac{k_1+k_2}{2} \rfloor\) ，黑色骨牌的数量是 \(\lfloor \frac{2n-k_1-k_2}{2} \rfloor\) ，判断 \(w\) 和 \(b\) 是否不超过最多数量即可。
void solve() {
int n, k1, k2, w, b;
cin >> n >> k1 >> k2 >> w >> b;
int W = (k1 + k2) / 2, B = (2 * n - k1 - k2) / 2;
cout << (w <= W && b <= B ? "YES" : "NO") << endl;
}
B. Binary Removals
题目
给定一个长度为 \(n\ (2\leq n \leq 100)\) 的只包含 \(0\) 和 \(1\) 的字符串，问是否能移去一些不相邻的字符，使得最终字符串为升序排列（即形成先 \(k_0\ (k_0\geq 0)\) 个 \(0\) ，再 \(k_1\ (k_1\geq 0)\) 个 \(1\) 的形式)。
多组数据。
样例输入 #1
5
10101011011
0000
11111
110
1100
样例输出 #1
YES
YES
YES
YES
NO
题解
观察到 \(n\) 的范围比较小，我们可以枚举前缀的长度 \(i\) ，判断是否能将 \(s[1\cdots i]\) 全变为 \(0\) ，以及是否能将 \(s[i+1\cdots n]\) 全变为 \(1\) 即可。
以判断是否能将 \(s[1\cdots i]\) 全变为 \(0\) 为例，要使其全变为 \(0\) ，需要移去这里面所有的 \(1\) ，所以只需判断有没有相邻的 \(1\) 即可。
void solve() {
string s;
cin >> s;
int n = s.length();
bool flag = false;
rep(i, 0, n) {
// remove all '1' of index 0 ~ i-1
// remove all '0' of index i ~ n-1
bool ok = true;
rep(j, 0, i - 2) {
if(s[j] == '1' && s[j + 1] == '1') {
ok = false;
break;
}
}
rep(j, i, n - 2) {
if(s[j] == '0' && s[j + 1] == '0'){
ok = false;
break;
}
}
if(ok){
flag = true;
break;
}
}
cout << (flag ? "YES" : "NO") << endl;
}
C. Minimum Grid Path
题目
你要从 \((0,0)\) 走到 \((n,n)\) ，每次可以向上走或者向右走，只能最多转向 \(n-1\) 次。
设你转向了 \(k-1\) 次，形成了 \(k\) 条线段，现给定一个数组 \(c\) ，其中 \(c_i\) 代表第 \(i\) 条线段所需花费，最终的总花费为 \(\sum\limits_{i=1}^k c_i\times length_i\) ，其中 \(length_i\) 表示第 \(i\) 条线段的长度，求最小花费。
多组数据。
样例输入 #1
3
2
13 88
3
2 3 1
5
4 3 2 1 4
样例输出 #1
202
13
19
题解
不难发现向上走和向右走是独立的，我们规定第一步向右，那么 \(0,2,4,\cdots\) 等下标就为向右的花费，\(1,3,5,\cdots\) 等即为向上的花费。
我们枚举转弯的次数，计算不同方向上的最小花费，加起来就是当前步数对应的的花费，取最小值即可。
至于计算最小花费，如果在当前方向走了 \(x\) 条线段，那么一定是花费最小的那条线段长度为 \(n-(x-1)\) ，其余 \(x-1\) 条线段长度为 \(1\) 时该方向花费最小，花费为 \(\sum\limits_{i=1}^xc_{i}+(n-x)\times c_{min}\) ，其中 \(c_1,\cdots c_x\) 为这 \(n\) 条线段对应花费。
我们只需维护 \(c\) 的前缀和以及最小值，根据对应的 \(x\) 即可计算出当前步数对应的花费，时间复杂度 \(\mathcal{O}(n)\)。
void solve() {
int n;
cin >> n;
vector<i64> cost(n);
for(auto &c : cost) cin >> c;
int curX = 0, curY = 0;
i64 minX = INF, minY = INF, ans = INF, sumX = 0, sumY = 0;
rep(i, 0, n-1) {
if(i % 2 == 0) {
curX++;
minX = min(minX, cost[i]);
sumX += cost[i];
}
if(i % 2 == 1) {
curY++;
minY = min(minY, cost[i]);
sumY += cost[i];
}
if(i == 0) continue; // at least one turn
i64 res = sumX + (n - curX) * minX +
sumY + (n - curY) * minY;
ans = min(ans, res);
}
cout << ans << endl;
}
D. The Number of Pairs
题目
给定 \(c,d,x\ (1\leq c,d,x \leq 10^7)\)，求有多少对正整数 \((a,b)\) 满足 $$c\cdot lcm(a,b) - d\cdot gcd(a,b) = x$$
其中 \(gcd(a,b)\) 表示 \(a\) 和 \(b\) 的最大公约数，\(lcm(a,b)\) 表示 \(a\) 和 \(b\) 的最小公倍数。
多组数据，\(t\ (1\leq t \leq 10^4)\) 为数据组数。
样例输入 #1
4
1 1 3
4 2 6
3 3 7
2 7 25
样例输出 #1
4
3
0
8
题解
令 \(g=gcd(a,b)\) ，\(a=Ag\) ，\(b=Bg\)，其中 \(A\)，\(B\) 互质。原等式变为：$$c\cdot ABg-d\cdot g=x$$
我们可以提取一个 \(g\)，变为 $$g\cdot (cAB-d)=x$$
惯用套路，枚举 \(x\) 的约数 \(g\) ，可以算出 \(A\times B\) 的值为 \(\frac{x+d\cdot g}{c\cdot g}\)，令其为 \(k\) ，可以发现 \(k\) 最大为 \(2\times 10^7\)，问题转化为计算满足 \(gcd(n,m)=1\) 且 \(n\times m=k\) 的正整数数对个数。
将 \(k\) 分解质因数，可以发现 \(k\) 的每种质因子 \(p\) 只能同时全部给 \(n\) 或 \(m\) 其中一个，两种决策，乘法原理计算得答案为 \(2^{cnt}\) ，其中 \(cnt\) 是 \(k\) 的本质不同质因子个数。
发现这玩意是积性函数，所以可以线性筛，在 i % p[j] == 0 的时候会多算，减去 \(1\) 即可。
void sieve() {
rep(i, 2, 2e7) {
if(!vis[i]) p[++tot] = i, cnt[i] = 1;
for(int j = 1; j <= tot && i * p[j] <= 2e7; j++) {
vis[p[j] * i] = true;
cnt[i * p[j]] = cnt[i] + 1;
if(i % p[j] == 0) {
cnt[i * p[j]]--;
break;
}
}
}
}
void solve() {
i64 c, d, x;
cin >> c >> d >> x;
auto calc = [&](i64 k) -> i64 { // calculate the number of (n,m)
return 1 << cnt[k];
};
vector<i64> fac;
for(i64 g = 1; g <= x / g; g++) { // enumerate g
if(x % g == 0) fac.pb(g);
if(g != x / g) fac.pb(x / g);
}
i64 ans = 0;
for(auto g : fac)
if((x + d * g) % (c * g) == 0)
ans += calc((x + d * g) / (c * g));
cout << ans << endl;
}