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

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


了解详情 >

七つの海

ひと結び、人を結んで

补题链接:Dashboard - Codeforces Round #708 (Div. 2) - Codeforces

记录

推特做题术

7_QMZFWQ_2JMS4Z46F_T9.png

虽然还是勉强保住了 ABC 选手的尊严,但是这场题目是真的偏简单…… ABC 连两千名都进不了()明明参加人数就只有两万人不到,可以说是很捞了== 赛后一看 E1 比 D 简单,C2 比 C1 简单,也真神秘(

题解

A - Meximization

看样例猜解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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();
map<int, int> cnt;
for (int i = 1; i <= n; ++ i)
++ cnt[scanner.nextInt()];
for (auto [i, ii] : cnt)
print(i, ' ');
for (auto [i, ii] : cnt)
while (-- ii) print(i, ' ');
println();
}
return 0;
}

B - M-arrays

按照 \(\mathrm{mod} \ m\) 进行分组统计答案就行:

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
const int N = 1e5 + 5;
int a[N], cnt[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(),
m = scanner.nextInt();
for (int i = 1; i <= n; ++ i)
a[i] = scanner.nextInt();
memset(cnt, 0, sizeof(int) * m);
for (int i = 1; i <= n; ++ i)
++ cnt[a[i] % m];
int ans = bool(cnt[0]), lim = m / 2;
for (int i = 1; i <= lim; ++ i)
{
auto aa = cnt[i], bb = cnt[m - i];
if (!aa && !bb) continue;
ans += max(abs(bb - aa), 1);
}
println(ans);
}
return 0;
}

C1 - k-LCM (easy version)

实际上没我代码写的那么复杂;如果是奇数的话就输出 1 k/2 k/2 就行,偶数但是不是 4 的倍数的话就是 2 k/2-1 k/2-1;再不然就是 n/2 n/4 n/4;不用看了,肯定是对的 ==

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
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(),
k = scanner.nextInt();
if (__builtin_popcount(n) == 1)
{
print(n / 2, ' ', n / 4, ' ', n / 4, '\n');
continue;
}
longs mod2 = 1;
while (!(n % 2)) n /= 2, mod2 *= 2;
int tmp = n / 2;
print(mod2, ' ', mod2 * tmp, ' ', mod2 * tmp, '\n');
}
return 0;
}

C2 - k-LCM (hard version)

这个题目就更搞了…… 因为服务器中途宕机的原因,我交的很慢,甚至还因为原想法过于花哨边界条件太多而 wa 了一发()但是实际上这个题比 C1 还要简单:

对于 n 和 k,只需要先输出 k - 31,然后再用 C1 的办法处理就行了(((

显然,C1 的办法保证得到的三个数的 LCM 满足 lcm <= (k - 3) / 2,而我们其他的数都是 1,对 lcm 没有任何贡献,所以最后的结果显然也是满足题意的(

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
void C1(int n)
{
if (n % 2) print("1 ", n / 2, ' ', n / 2);
else if (n % 4) print("2 ", n / 2 - 1, ' ', n / 2 - 1);
else print(n / 2, ' ', n / 4, ' ', n / 4);
}

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(),
k = scanner.nextInt();
int m = k - 3; C1(n - m);
while (m --) print(" 1");
println();
}
return 0;
}

就不贴我赛场上写的丑陋的甚至还 WA 了一发代码了…… 我真傻,真的(

XJQ1VOCX5_3_D_4ML2KN.png

还是不够机智==

D - Genius

\(1 \dots n\)\(n \leq 5000\) 个位置:\(i\)-th 位置有 \(tag_i\)\(c_i = 2^i\)\(s_i\) 分数;初始有 \(\mathrm{IQ} = 0\)\(S = 0\)

如果你当前在 \(i\) 点,那么仅当 \(\mathrm{IQ} < |c_i - c_j|\)\(tag_i \ne tag_j\) 同时满足时才能到达 \(j\) 点;
到达 \(j\) 点之后,你的 \(\mathrm{IQ}\) 变为 \(|c_i - c_j|\),并且获得 \(|s_i - s_j|\) 分数;

你可以任意选择起点,问你可以获得的最大分数;

特别说明内存限制 32MB

首先,定义边权 \(w_{i, j} = |c_i - c_j|\);显然所有的边的“边权”都是不同的;然后考虑动态规划:定义 \(F_i\) 表示最后停留在点 \(i\) 最大能获得的分数;显然最初情况下全部为 0;然后转换题目限制条件,进行转移:

  • \(tag_i \ne tag_j\):这个简单,如果不满足直接阻止对应的转移就行了。
  • \(\mathrm{IQ} < |c_i - c_j|\):意思就是说走的边越来越长;因此我们总是先转移短边再转移长边就行。

综上所述,我们就可以在一维 DP 内完成答案的求解;

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 = 5050;
int s[N], tag[N];
longs dp[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)
tag[i] = scanner.nextInt();
for (int i = 1; i <= n; ++ i)
s[i] = scanner.nextInt();
memset(dp, 0, sizeof(longs) * (n + 1));
for (int i = 1; i <= n; ++ i)
for (int j = i - 1; j; -- j)
if (tag[i] != tag[j])
{
auto ii = dp[i], jj = dp[j];
auto add = abs(s[i] - s[j]);
maximize(dp[i], jj + add);
maximize(dp[j], ii + add);
}
println(*max_element(dp + 1, dp + 1 + n));
}
return 0;
}

有的时候想问题还是要跳出局部纵观全体;像这个题就是做的时候视野集中在走的策略上,并且还被预处理 tag 连通块的想法所牵制,最后离正解渐行渐远(

E1 - Square-free division (easy version)

给定长度为 \(n \leq 2 \cdot 10^5\) 的数组;现在你需要将数组划分成一些连续的段,使得每个段中不包含两个数,它们的乘积为完全平方数;求满足此要求可以划分的最少的段数。

首先肯定要对数组里每个数字进行分解质因数;因为相乘就是分解质因数得到的多项式的指数相加,而完全平方数分解得到的多项式的指数均为 2;那么我们可以得到结论:如果 x 和 y 的乘积是完全平方数,那么 x 和 y 分解质因数得到的多项式中关于每一个质数的指数都是 \(\mathrm{mod} \ 2\) 相等的。

因此,我们只需要记录每个元素质因数分解之后指数 \(\mathrm{mod} \ 2\) 的情况,然后划分不包含相同 pattern 的元素即可:这样,这个问题就退化为划分不包含相等数字的段;众所周知,这个问题可以贪心的解决。

那么应该如何维持这个 pattern 呢?使用一个很大的 bitset 嘛?完全没有必要:因为 \(a_i \leq 10^7\),那么质因子指数不会超过 1 的 pattern 的乘积自然也不会超过这个限制;所以只需要将它们乘起来就可以了,即快又优雅(

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
37
38
39
40
41
42
43
44
45
46
47
const int N = 2e5 + 5, A = 1e7 + 7;
int a[N], pattern[N];

// PrimeFactorizationSieve()
namespace PFS {...}

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();
using PFS::prime, PFS::fact;
PFS::start();
while (T --)
{
int n = scanner.nextInt(),
k = scanner.nextInt();
for (int i = 1; i <= n; ++ i)
a[i] = scanner.nextInt();
fill(pattern, pattern + n + 1, 1);
for (int i = 1; i <= n; ++ i)
{
int exp = 0, base = 0, tmp = a[i];
while (tmp > 1)
{
int p = fact[tmp];
if (base == p) ++ exp;
else
{
if (exp % 2) pattern[i] *= base;
base = p, exp = 1;
} tmp /= p;
}
if (exp % 2) pattern[i] *= base;
}
int ans = 1;
set<int> unique;
for (int i = 1; i <= n; unique.insert(pattern[i ++]))
if (unique.count(pattern[i])) ++ ans, unique.clear();
println(ans);
}
return 0;
}

真就比 D 简单呗?以后打 CF 也不能盯着一个题死看了,得适当设定递归深度((

话说我的欧拉筛写成函数竟然会过不了编译(提示编译得到的文件过大),只好拆成命名空间的形式才能过,倒是挺神秘的有点==

E2 - Square-free division (hard version)

在 E1 的基础上,你获得了 \(k \leq 20\) 次的单点修改的机会:你可以将任意位置修改为任意数字不超过 \(k\) 次;

看到 k 非常的小,所以可以考虑 DP;令 DP 数组 \(F_{i, j}\) 的含义是在长度为 i 的前缀中,允许不超过 j 次的修改,可以得到的最少的分段数;那么,我们至少可以考虑到两种显然的转移:

  • \(j > 0\),那么显然可以从 \(F_{i,k} (k < j)\) 转移到 \(F_{i, j}\)
  • 若区间 \((i, k]\) 消耗了 \(x\) 次修改而得以连续,那么 \(F_{k, j + x} = F_{i, j} + 1\)

因此,如果我们可以维护一段区间维持连续而消耗的次数,就可以利用第二种转移求出最后的答案;

当然,我们不可能去维护所有的区间;将第二种转移反过来,我们只需要维护对于每一个满足 \(x \leq j\) 的修改次数,以一个确定的右端点 \(i\),可以到达的最远的左端点 \(l\) 即可。这样的转移一定是更优的。而预处理求出这个距离也并不难;我们依然可以像 E1 那样通过一次遍历就完成维护(因为 pattern 的大小是有限的,我们可以使用桶来去重而不是 set,这样时间复杂度就是线性的);维护 \(k\) 中不同的修改情况的复杂度是 \(O(nk)\) 的;

这样,我们就可以利用上面说到的两种转移方法进行转移了;时间复杂度是 \(O(nk^2)\) 的;

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
const int N = 2e5 + 5, A = 1e7 + 7;
int a[N], pattern[N], cnt[A];
int ll[N][25], f[N][25];

// PrimeFactorizationSieve()
namespace PFS { ... }

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();
using PFS::prime, PFS::fact;
PFS::start();
while (T --)
{
int n = scanner.nextInt(),
k = scanner.nextInt();
for (int i = 1; i <= n; ++ i)
a[i] = scanner.nextInt();
fill(pattern, pattern + n + 1, 1);
for (int i = 1; i <= n; ++ i)
{
int exp = 0, base = 0, tmp = a[i];
while (tmp > 1)
{
int p = fact[tmp];
if (base == p) ++ exp;
else
{
if (exp % 2) pattern[i] *= base;
base = p, exp = 1;
} tmp /= p;
}
if (exp % 2) pattern[i] *= base;
}
for (int j = 0; j <= k; ++ j)
{
int cur = n + 1, use = 0;
for (int i = n; i > 0; -- i)
{
while (cur - 1 >= 1 &&
use + !!cnt[pattern[cur - 1]] <= j)
use += !!(cnt[pattern[-- cur]] ++);
ll[i][j] = cur;
if (cnt[pattern[i]] --> 1) -- use;
}
}
for (int i = 1; i <= n; ++ i)
memset(f[i], 0x3f, sizeof(f[i]));
memset(f[0], 0, sizeof(f[0]));
for (int i = 1; i <= n; ++ i)
for (int j = 0; j <= k; ++ j)
{
if (j) minimize(f[i][j], f[i][j - 1]);
for (int l = 0; l <= j; ++ l)
minimize(f[i][j], f[ll[i][l] - 1][j - l] + 1);
}
int ans = 0x3f3f3f3f;
for (int i = 0; i <= k; ++ i)
minimize(ans, f[n][i]);
println(ans);
}
return 0;
}

后记

《就这》:比赛中:Codeforces 服务器就这?比赛后:你这通过情况就这?

服务器恢复:拿好你的 15 分钟,我们没有找到任何 unrated 的原因!半小时后:我们 unrated 了!

评论