抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

七つの海

今日、海を見た。もう怖くない

补题链接:https://codeforces.com/contest/1499

记录

一开始还是挺像模像样的,快速地切掉了 ABC 三个题,然后在 D 题处一直瞎想,看着通过人数从 30 涨到 600 左右直到比赛结束……这种感觉是真的不好()到底是什么使得我变得总是做不出 D 呢…… 确实需要好好反思(

题解

A - Domino on Windowsill

不用管怎么摆放;因为只有两排,所以只需要看格子数够不够就行;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
signed main()
{
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#if 0
freopen("in.txt", "r", stdin);
#endif
int T = scanner.nextInt();
while (T --)
{
int n, k1, k2, w, b;
scanner(n, k1, k2, w, b);
int ww = (k1 + k2) / 2;
int bb = (2 * n - k1 - k2) / 2;
println(ww >= w && bb >= b ? "YES" : "NO");
}
return 0;
}

B - Binary Removals

数据规模很小;所以只需要遍历 0-1 分界点的位置,然后 \(O(n)\) 检查是否可行即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int N = 120;
char s[N];

signed main()
{
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#if 0
freopen("in.txt", "r", stdin);
#endif
int T = scanner.nextInt();
while (T --)
{
scanner(s);
int n = strlen(s);
bool ok = false;
bitset<N> del;
for (int i = 0; i <= n; ++ i)
{
del.reset();
for (int j = 0; j < i; ++ j)
if (s[j] == '1') del.set(j);
for (int j = i; j < n; ++ j)
if (s[j] == '0') del.set(j);
bool _ok = true;
for (int j = 1; j < n; ++ j)
if (del[j] && del[j - 1]) _ok = false;
if (_ok) ok = true;
}
println(ok ? "YES" : "NO");
}
return 0;
}

C - Minimum Grid Path

首先,你至少要转一次弯才能到达终点,所以你的路程段数至少是两段;因为只有两个方向,所以你每转一次弯就相当于在两种方向来回横跳;注意到题目说的是第 x 段路的费用是 \(c_x\);所以显然偶数段的路和奇数段的路方向不同,且恰好占据了两个方向——且两个方向都需要走 \(n\) 的长度;

因为转方向之后至少要在这一段路之间走 1 个单位,所以如果在某个方向走了 \(x\) 段路,其中费用最小的为 \(c_x'\),所有的这些路段的单价总和为 \(C_x\),那么这个方向上最便宜的走法一定是花费 \(C_x + (n - x)c_x'\) 的:即在花费最小的路段尽可能地走,但是之前经过的不那么优的路段只走一段;

还需要注意的就是两个方向并不是独立的:因为是连贯的折线,所以在两个方向上走的段数差不能超过 1;一种比较优雅的遍历方法就是遍历所有的段数,然后分别处理两边的最优花费,求和取最小值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const int N = 1e5 + 5;
longs c[N];

signed main()
{
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#if 0
freopen("in.txt", "r", stdin);
#endif
int T = scanner.nextInt();
while (T --)
{
int n = scanner.nextInt();
for (int i = 1; i <= n; ++ i)
c[i] = scanner.nextInt();
longs ans = c[1] * n + c[2] * n;
longs odd = c[1], even = c[2];
longs os = c[1], es = c[2];
longs on = 1, en = 1;
for (int i = 3; i <= n; ++ i)
{
++ (i % 2 ? on : en);
(i % 2 ? os : es) += c[i];
minimize((i % 2 ? odd : even), c[i]);
auto tmp = odd * (n - on) + os + even * (n - en) + es;
minimize(ans, tmp);
}
println(ans);
}
return 0;
}

D - The Number of Pairs

给定三个整数 \(c\)\(d\)\(x\);它们满足 \(1 \leq c, d, x \leq 10^7\);现给定等式: \[ c \cdot \mathrm{lcm}(a, b) - d \cdot \mathrm{gcd}(a, b) = x \]\(a, b\) 均为正整数;求出满足该等式的 \((a, b)\) 的对数。

这个等式首先一看就是要化简的:令 \(K = \mathrm{gcd}(a, b)\);那么就可以将 a 和 b 表示为 \(a = nK, \ b = mK\),其中的 n 和 m 显然满足 \(n,m \in N^+\)\(\mathrm{gcd}(n, m) = 1\);那么我们就可以进行如下的等价变换: \[ \begin{align} c \cdot \mathrm{lcm}(a, b) - d \cdot \mathrm{gcd}(a, b) &= x \\ c \cdot \frac{ab}{\mathrm{gcd}(a, b)} - d \cdot \mathrm{gcd}(a, b) &= x \\ c \cdot nmK - d \cdot K &= x \\ K &= \frac{x}{cnm - d} \end{align} \] 那么,记 \(y = cnm - d\),这个问题就变成了求满足这个等式的互质的 \((n, m)\) 的对数。具体的做法就是枚举 \(x\) 的因子 \(y\):如果满足 \(c \mid (d + y)\),那么 \(nm = \frac{d + y}{c}\);记 \(z = nm\),因为 n 和 m 互质,所以 \(z\) 的每一个不同的质因子要不全部属于 n,要不全部属于 m;用 \(P_z\) 表示 z 的不同的质因子的数量,那么对于 z,满足条件的 (n, m) 一共有 \(2^{P_z}\) 对。

实际实现时,可以先用线性筛预处理数据范围内的 \(P\) 数组,然后根据输入计算答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int A = 2e7 + 7;

namespace linear_sieve { ... }

longs fastPow(longs a, ulongs b) { ... }

signed main()
{
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#if 0
freopen("in.txt", "r", stdin);
#endif
int T = scanner.nextInt(), c, d, x;
using linear_sieve::cnt;
linear_sieve::start();
const auto calc =
[&](longs y) -> longs
{
if ((d + y) % c) return 0;
const auto z = (d + y) / c;
return fastPow(2, cnt[z]);
};
while (T --)
{
scanner(c, d, x);
longs ans = 0, y;
for (y = 1; y * y < x; ++ y)
if (!(x % y))
ans += calc(y) + calc(x / y);
if (y * y == x) ans += calc(y);
println(ans);
}
return 0;
}

需要注意的是:虽然数据范围是 1e7 的,但是 z 是有可能大于 1e7 的;所以预处理的数据范围要更广。

事后分析

虽然也确实推了式子,也至少推到了这份题解中提到的第二部;但是这实在是太像 \(\mathrm{exgcd}\) 了:如果假设 lcm 和 gcd 都为未知变量的话;但是就像刚才所推导的那样,这两个未知变量之间本就有所联系,并且这个联系的关系也是不定的(lcm 是 gcd 的倍数),求出了倍数还是要进行这样的拆分,就非常的不合理。

E - Chaotic Merge

……

F - Diameter Cuts

等待题解中……

后记

和之前的发挥不是很正常的比赛是一样的:总是感觉自己的思维非常的不稳定——不在能做出题的频道上;之前解决这种问题是静下心来仔细想想自己到底有哪些地方出了问题,也许现在也是需要这样的时候吧(

猫猫脸.png

不过我确实需要静下心来好好地想想了…… 愉快犯是不够扎实的(

评论