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

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


了解详情 >

七つの海

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

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

记录

很捞,ABC 选手都没有当成,属是不是很行(

a.jpg

补了题之后发现这场甚至还算比较简单的,肺都气炸(

题解

A - Anti-knapsack

给定 \(n\)\(k\),要求选出最大的子集 \(S \subset [1, n]\),使得不存在集合 \(T \subseteq S\) 满足 \(\sum_{i \in T}i = k\)

明明是个签到题但是我却白给一发;最开始写的是由前缀和小于 k 的数字构成小于 k 的部分,但是仔细想想就会发现这个数字集合显然不如 k / 2 大==

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, k;
$$ n, k;
int ans = n - k + k / 2;
println(ans);
for (int i = (k + 1) / 2; i < k; ++ i)
print(i, ' ');
for (int i = k + 1; i <= n; ++ i)
print(i, ' ');
println();
}
return 0;
}

日常脑瘫操作(

B - Planet Lapituletti

纯暴力就行

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
70
struct fast_read
{
template<class name>
fast_read operator, (name &x)
{scanner(x); return fast_read{};}
} fastRead;
#define $$ fastRead,

char trans[] = {'0', '1', '5', '-', '-', '2', '-', '-', '8', '-'};

void mirror(const char *s, char *t)
{
for (int i = 0; i < 5; ++ i)
if (s[i] == ':') t[4 - i] = ':';
else t[4 - i] = trans[s[i] - '0'];
t[5] = 0;
}

auto turn(const char *s)
{
int H = (s[0] - '0') * 10 + s[1] - '0',
M = (s[3] - '0') * 10 + s[4] - '0';
return make_pair(H, M);
}

void make(int H, int M, char *s)
{
s[0] = H / 10 % 10 + '0';
s[1] = H % 10 + '0';
s[3] = M / 10 % 10 + '0';
s[4] = M % 10 + '0';
s[2] = ':', s[5] = 0;
}

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(), h, m;
const auto validator =
[&](const char *s)
{
for (int i = 0; i < 5; ++ i)
if (s[i] == '-') return false;
auto [H, M] = turn(s);
return H >= 0 && H < h && M >= 0 && M < m;
};
const auto tik =
[&](char *s)
{
auto [H, M] = turn(s);
++ M; H = (H + M / m) % h;
M %= m;
make(H, M, s);
};
while (T --)
{
char s[6], t[6];
$$ h, m, s;
mirror(s, t);
while (!validator(t))
tik(s), mirror(s, t);
println(s);
}
return 0;
}

但是代码有点花里胡哨

C - K-beautiful Strings

定义K-美丽的字符串:字符串中所有出现的字符的出现次数都是 k 的整数倍;

现在给 \(n \leq 10^5\)\(k \leq n\),问可以得到的字典序最小但是字典序大于等于原串的的K-美丽的字符串;如果这样的字符串不存在,输出 -1

怎么说呢,首先需要明确以下几点:

  • 只有字符串长度为 K 的倍数的字符串才有可能成为题目要求的字符串
  • 因为满足要求的字符串字典序要比原串大,所以尽可能小的唯一方法是尽可能地保留前缀
  • 同上,保留前缀后的第一位的字符一定要大于等于原串对应位置的字符

综上所述,我们可以得到一种优雅并且正确的写法:

  • 如果原串已经是一个 K - 美丽的字符串了,就直接输出
  • 倒序遍历可能维护的前缀长度,并维护前缀不同字符的出现次数
  • 尝试将前缀后的第一个字符修改为任何大于原串的字符
  • 判断除去该字符的后缀能否和前面的已确定字符组成 K - 美丽字符串

然后就可以写出这个题的代码:

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
70
71
72
struct fast_read
{
template<class name>
fast_read operator, (name &x)
{scanner(x); return fast_read{};}
} fastRead;
#define $$ fastRead,

const int N = 1e5 + 5;
int cnt[30];
char s[N], app[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(), n, k, need;
const auto stillNeed =
[&](int x) {return (k - x % k) % k;};
const auto alter =
[&](char ch, int delta)
{
need -= stillNeed(cnt[ch - 'a']);
cnt[ch - 'a'] += delta;
need += stillNeed(cnt[ch - 'a']);
};
while (T --)
{
$$ n, k;
if (n % k) {println(-1); continue;}
memset(cnt, 0, sizeof cnt);
$$ s;
for (int i = 0; i < n; ++ i)
++ cnt[s[i] - 'a'];
for (int i = need = 0; i < 26; ++ i)
need += stillNeed(cnt[i]);
if (!need) {println(s); continue;}
for (int i = n - 1; i >= 0; -- i)
{
alter(s[i], -1);
for (auto alt = s[i] + 1; alt <= 'z'; ++ alt)
{
alter(alt, +1);
if (i + need < n)
{
for (int j = 0; j < i; ++ j)
print(s[j]);
print((char)alt);
int cur = 0, res = n - i - 1;
for (char ch = 'a'; ch <= 'z'; ++ ch)
{
int m = stillNeed(cnt[ch - 'a']);
res -= m;
while (m --) app[cur ++] = ch;
}
while (res --) app[cur ++] = 'a';
app[cur] = 0;
sort(app, app + cur);
println(app);
goto complete;
}
alter(alt, -1);
}
}
complete: continue;
}
return 0;
}

实际上也没有那么多需要注意的地方,关键就在于最开始写代码的思路是否正确)如果抓着修改字符来看的话,代码会难想而且难写许多,浪费比赛时间。

D - GCD of an Array

给一个长度为 \(n \leq 2 \cdot 10^5\) 的数组 \(a\),满足 \(a_i \leq 2 \cdot 10^5\)

然后对这个数组进行 \(q \leq 2 \cdot 10^5\) 次操作:单点修改为原来的 \(x\) 倍,且 \(x \leq 2 \cdot 10^5\)

在每次操作后,要求输出现在数组的 gcd 对于 1e9 + 7 的模数。

STL 嗯做题:首先要意识到将所有的 \(a_i\) 分解成 \(\prod p_j^{k_i}\) 的形式,那么 GCD 可以表示为 \(\prod p_j^{\textrm{min}k_i}\);又因为修改只有单点倍增,GCD 只会有增无减;所以可以考虑用 STL 维护每个数组成员的分解结果,以及整个数组每个质因子的分解结果集合,需要支持查询最小值;

这样,每当进行单点修改时,我们就可以通过更新分解结果,然后更新数组质因子的维护结果,并借此更新答案

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#define $$ fastRead,

template <int n> auto &EulerSieve()
{
static vector<int> prime;
static array<int, n + 1> vis;
for (int i = 2; i <= n; ++ i)
{
if (!vis[i])
prime.push_back(i), vis[i] = i;
for (auto & pp : prime)
{
if ((longs)i * pp > n) break;
vis[i * pp] = pp;
if (i % pp == 0) break;
}
}
return vis;
}

const int N = 2e5 + 5;
const int mod = 1e9 + 7;

longs fastPow(longs a, ulongs b)
{
longs ans = 1;
while(b)
{
if (b & 1u) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1u;
}
return ans % mod;
}

signed main()
{
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#if 0
freopen("in.txt", "r", stdin);
#endif
int n, q, a;
longs ans = 1;
auto pp = EulerSieve<N>();
vector<unordered_map<int, int>> part;
unordered_map<int, multiset<int>> maintain;
const auto update =
[&](int div, int last)
{
if (maintain[div].size() != n) return;
int now = *maintain[div].begin();
ans = ans * fastPow(div, now - last) % mod;
};
const auto alter =
[&](int i, int x)
{
while (1 != x)
{
auto div = pp[x], cnt = 0;
while (div == pp[x])
++ cnt, x /= div;
auto old = part[i][div];
part[i][div] += cnt;
int last = 0;
if (maintain[div].size() == n)
last = *maintain[div].begin();
if (old)
{
auto it = maintain[div].find(old);
maintain[div].erase(it);
}
maintain[div].insert(old + cnt);
update(div, last);
}
};
$$ n, q, part.resize(n + 1);
for (int i = 1; i <= n; ++ i) $$ a, alter(i, a);
int i, x;
while (q --) $$ i, x, alter(i, x), println(ans);
return 0;
}

E - Enormous XOR

对于两个大整数 \(l\)\(r\)\(l \leq r\)),定义函数: \(G_{l, r} = \bigoplus_{i=l}^ri\)\(F _ {l, r} = \mathrm{max} _ {l \leq x \leq y \leq r} G _ {x, y}\)

现在给定 \(l\)\(r\) 的二进制表示形式(\(l \leq r < 2^{10^6}\));要求求出 \(F_{l, r}\) 的值。

抖机灵题:令 \(l\)\(r\) 的最高位分别为 \(H_l\)\(H_r\)

如果 \(H_l \ne H_r\),那么显然有 \(F_{l, r} = 2^{H_r + 1} - 1\):因为 \(2^{H_r},\ 2^{H_r} - 1 \in [l, r]\) 显然成立,而 \(2^{H_r} \oplus (2^{H_r} - 1) = 2^{H_r + 1} - 1\);否则,答案至少有最大值 \(r\);考虑选出答案的区间:为了保持可能存在的最高位存在,得到答案的区间 \([x, y]\) 的大小必定是奇数;且不难想到其中 \(y = r\)

我们考虑 \(r\) 的奇偶性:

  • 如果 \(r\) 为奇数,因此除了最大的一个数字之后,最大的数字是 \(r - 1\)——除了奇数位之外和 \(r\) 完全一致;不难发现区间中的数字是成对出现的,因此 \(r\) 能确定保留的位只有奇数位,不如 \(r\) 优;
  • 如果 \(r\) 为偶数,同理,显然最低位(奇偶位)必然为 1,所以异或值为 \(r + 1\),更优;

但是以上操作都要建立在区间 \([l, r]\) 允许的情况下;如果允许区间小于 3,则无法进行上述操作,答案为 \(r\)

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
#define $$ fastRead,

const int N = 1e6 + 5;
char l[N], r[N], ans[N], tmp[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 n = scanner.nextInt();
$$ l, r;
int hl = 0, hr = 0;
while (l[hl] != '1') ++ hl;
while (r[hr] != '1') ++ hr;
if (hl != hr)
{
for (int i = min(hl, hr); i < n; ++ i)
ans[i] = '1';
for (int i = 0; i < min(hl, hr); ++ i)
ans[i] = '0';
ans[n] = '\0';
}
else if (r[n - 1] == '1')
memcpy(ans, r, sizeof ans);
else
{
memcpy(tmp, r, sizeof tmp);
for (int i = n - 2; i >= 0; -- i)
if (tmp[i] == '1')
{tmp[i] = '0'; break;}
else tmp[i] = '1';
memcpy(ans, r, sizeof ans);
if (strcmp(tmp, l) >= 0) ans[n - 1] = '1';
}
println(ans);
return 0;
}

F - Enchanted Matrix

这是一个交互题;有一个 \(n \times m\) 的矩阵,求合法的 \((x, y)\) 的数对个数:

合法的 \((x, y)\) 数对的定义:可以将原矩阵完整的划分为一些 \(x \times y\) 的子矩阵,这些子矩阵相等。

最多可以询问 \(3 \cdot \lfloor \textrm{log}_2(n + m) \rfloor\) 次两个不相交的子矩阵是否相等。

分析

首先可以意识到这个问题中行列是互相独立的问题:显然有 [x, y] === [x, m] && [n, y]

然后再一个显然的就是要求出这个数对,必须要先求出行列方向上的最短循环节,再由循环节凑出其他的答案——这是一个很常见的套路:串的分多段全等的问题可以转化为找它的最短循环节。


如何在单维(也就是一个串)中寻找最短的循环节呢?我们首先利用筛预处理出范围内整数的质因数分解,然后以每一个质因数作为本次分段数,在上一次分割后的循环节上进行尝试;最后剩下的没有被除去的质因数的乘积就是最短循环节的长度。


那么如何判断分出的段在当前串中是否是循环节呢?

首先,如果不考虑重叠的限制条件,对于任何串的候选循环节;我们先令该串包含了 \(L\) 个候选循环节,候选循环节的长度为 \(x\):这样,我们只需要比较原串长度为 \((L - 1)x\) 的前缀和长度为 \((L - 1)x\) 的后缀是否相等即可;也就是前 \(L - 1\) 节和后 \(L - 1\) 节是否相等;这也是很容易证明的;

但是题目限制了不允许询问重叠的区间,所以上述做法在这并不可行;但是我们还是可以基于这种思路,采用迂回的办法来完成询问;因为我们每次都是对于一个串(原串或者已经被分割后的),使用它长度的质因数来作为划分段数;令划分的段数为 \(L\),这里的段显然和上面说的候选循环节由相同的意义。

因为 \(L\) 是质因数,所以只有可能是两种情况:

  • \(L = 2\),此时直接询问两段是否相等即可;
  • \(L > 2\),此时 \(L\) 必定是奇数;令 \(l = \lfloor \frac{L}2 \rfloor\)
    • 我们选取前 \(l\) 段作为中转,那么还剩下连续的 \(l + 1\)
    • 剩下的 \(l + 1\) 段也是奇数,可以使用最初说的方法进行判断
    • 但是我们不直接比较重叠的两段,而是让它们分别于前面选出的中转段进行比较
  • 这样就可以在 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
70
const int N = 1005;

int ask(int h, int w, int x1, int y1, int x2, int y2)
{
cout << "? " << h << ' ' << w << ' ' << x1 << ' '
<< y1 << ' ' << x2 << ' ' << y2 << endl;
int tmp; cin >> tmp; return tmp;
}

template <int n> auto &sieve()
{
static vector<int> prime;
static array<int, n + 1> vis;
for (int i = 2; i <= n; ++ i)
{
if (!vis[i])
prime.push_back(i), vis[i] = i;
for (auto & pp : prime)
{
if ((longs)i * pp > n) break;
vis[i * pp] = pp;
if (i % pp == 0) break;
}
}
return vis;
}

signed main()
{
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#if 0
freopen("in.txt", "r", stdin);
#endif
int n, m;
auto p = sieve<N>();
const auto askM =
[&](int len, int time) -> bool
{
const auto h = n, w = time / 2 * len;
if (time == 2)
return ask(h, w, 1, 1, 1, w + 1);
else return
ask(h, w, 1, 1, 1, w + 1) &&
ask(h, w, 1, 1, 1, w + len + 1);
};
const auto askN =
[&](int len, int time) -> bool
{
const auto h = time / 2 * len, w = m;
if (time == 2)
return ask(h, w, h + 1, 1, 1, 1);
else return
ask(h, w, h + 1, 1, 1, 1) &&
ask(h, w, h + len + 1, 1, 1, 1);
};
cin >> n >> m;
auto [nn, mm] = make_pair(n, m);
for (int i = nn; i > 1; i /= p[i])
if (askN(nn / p[i], p[i])) nn /= p[i];
for (int i = mm; i > 1; i /= p[i])
if (askM(mm / p[i], p[i])) mm /= p[i];
const auto nt = n / nn, mt = m / mm;
longs np = 0, mp = 0;
for (int i = 1; i <= nt; ++ i) np += !(nt % i);
for (int i = 1; i <= mt; ++ i) mp += !(mt % i);
cout << "! " << np * mp << endl;
return 0;
}

最后不能直接输出 nt * mt

后记

参考资料

评论