ABC花了近1h;D想了一会跳过了;E WA,正解似乎涉及博弈论的定理;F数学期望没看。
打代码时应刻意提高手速。代码实现的经验有待丰富。
A. A-characteristic
秒 - AC
关于代码实现,给定n,可求出符合题意的所有可能的k。不需要把它们放到一个set中,或是用vh数组标记;输入只有一个k,可以在计算过程中判断其是否合法。
cin >> n >> k;
flag = false;
for (int i = 0; i <= n / 2; ++i) {
if (k == i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2) {
cout << "YES\n";
for (int j = 1; j <= i; ++j) cout << 1 << ' ';
for (int j = 1; j <= n - i; ++j) cout << -1 << ' ';
cout << "\n";
flag = true;
break;
}
}
if (!flag) cout << "NO\n";
B. Sort with Step
秒 - AC
特判在代码实现中很常见。有时还没仔细想就写了代码,写完才发现特判与一般情况的统一性。我想,此时不必把特判删掉并修改代码细节,这有点浪费时间且从结果上来看毫无用处(思考是否有疏漏;鼠标指针移动,上下左右方向键),但很多时候我会忍不住这么做。
cin >> n >> k;
cnt = 0;
for (int i = 1; i <= n; ++i) {
int tmp; cin >> tmp;
if (tmp % k != i % k) ++cnt;
}
if (cnt <= 2) cout << (cnt >> 1) << "\n";
else cout << -1 << "\n";
C. Strongly Composite
质因数分解、乘法原理 - AC
a对b的约束仅有a的所有数的积。既然涉及质数、合数、因数、乘积,当然要考虑质因数分解。
已知b的所有数的积的质因数分解形式(根据a得出)。把质因子分给尽可能多的数,使得,只需要保证每个数都是“强合数”。也就是尽量让b中每个数分得的质因子数目较少,留更多的给后面。(上面的“使得”二字放在那里似乎不通顺,但如果删除会产生歧义。我通过这两个字提示后面的内容的意义——这是个语文问题,我想不出更好的表达方法)
分析“强合数”的特征。
b
=
p
1
k
1
…
p
m
k
m
b=p_1^{k_1}\dots p_m^{k_m}
b=p1k1…pmkm,质因数个数m,合因数个数
Π
(
k
i
+
1
)
−
m
−
1
\Pi (k_i+1)-m-1
Π(ki+1)−m−1,注意1不是合数也不是质数。
强合数满足
2
m
+
1
≤
Π
(
k
i
+
1
)
2m+1\leq \Pi (k_i+1)
2m+1≤Π(ki+1).
使每个b分得的质因数个数尽可能少。
m=1时,k至少是(2).
m=2时,k至少是(2,1),与m=1相比,这是无用的。
m=3时,k至少是(1,1,1). 更大的m不会比它更优。
从数目上看,应优先使用(2)向b分配质因子。此后剩余的质因数,各自的个数都是1,优先用(1,1,1)消去。对冗余的,则用(1,1,1,1),(1,1,1,1,1). 可以将这看作把冗余的质因数合并到已有的强合数中。
cin >> tt;
set_prime(MAXA - 1);
while (tt--) {
ans = m = 0;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
int tmp = a[i];
while (tmp > 1) {
int k = p[tmp];
if (!vh[k]) vh[k] = true, ++m;
else vh[k] = false, --m, ++ans;
tmp /= prime[k];
}
}
ans += m / 3;
cout << ans << '\n';
for (int i = 1; i <= n; ++i) {
while (a[i] > 1) vh[p[a[i]]] = false, a[i] /= prime[p[a[i]]];
}
}
代码实现优化 - AC(补)
我用不熟悉的线性筛实现质因数分解,花了很多时间。实际上,使用更简单的暴力分解,复杂度为 O ( n a l o g ( n l o g a ) ) O(n\sqrt a log(nloga)) O(nalog(nloga)),不会超时。
a不超过1e7,很大。上面的代码中,vh数组如果用memset清空,会超时。就算用素数的标号为下标,1e7内的素数有约665000个,还是会超时。所以有上文麻烦的清空方法。
对每个testcase新开一个STL map,免去了对素数标号的麻烦,也无需清空。
while (tt--) {
ans = m = 0;
map<int, int> vh;
cin >> n;
for (int i = 1; i <= n; ++i) {
int tmp; cin >> tmp;
for (int j = 2; j * j <= tmp; ++j) {
while (!(tmp % j)) {
++vh[j];
tmp /= j;
}
}
if (tmp != 1) ++vh[tmp];
}
for (auto i : vh) {
ans += i.second >> 1;
m += i.second & 1;
}
ans += m / 3;
cout << ans << "\n";
}
D. Unique Palindromes
跳过
看到字符串,互不相同的回文子串个数,还是个构造题,想了一会没啥思路,跳过去做后面的题了,后面的题更做不出来。
分析 - AC(补)
考虑在t的后面加一个字符,对p(t)可能无影响;可能使+1;若+2,那么其中一个回文串是另一个回文串的后缀,因为回文,所以小回文串翻折过去,也是大回文串的前缀,也就一定已被统计过。所以在t的后面加一个字符,p(t)只可能不变或+1.
长度增加m,p(t)最多增加m,据此判断无解情况。关于构造,发现aaaaaaa
这样的串就能达到最大增量。
有趣的是,输入保证
k
≤
20
k\leq 20
k≤20,英文字母有26个,对于需要控制p值的每一段,分别用aaaa
,bbbb
,cccc
…来调节p值。剩下的空位,就用不含回文串的xyzxyzxyz
填充。
但是,单个x
本身是一个回文串。可以将字符串前三个字符初始化为xyz
.
同时要防止出现xyz|aaaax|bbbx
这样的情况,xbbbx
是回文串。
flag = false;
cin >> n >> k;
for (int i = 1; i <= k; ++i) {
cin >> x[i];
}
for (int i = 1; i <= k; ++i) {
cin >> c[i];
}
int p = 0;
ans = "xyz";
x[0] = 3, c[0] = 3;
for (int i = 1; i <= k; ++i) {
if (c[i] < c[i - 1] || c[i] - c[i - 1] > x[i] - x[i - 1]) {
flag = true;
break;
}
for (int j = 1; j <= c[i] - c[i - 1]; ++j) {
ans.push_back('a' + i - 1);
}
while (ans.size() < x[i]) {
ans.push_back('x' + p);
p = (p + 1) % 3;
}
}
if (!flag) cout << "YES\n" << ans << '\n';
else cout << "NO\n";
E. Removing Graph
博弈dp - WA
图由若干个互不连通的环组成。
我没有多想,错误地将问题简化为,每个环为一个盒子,环上的节点数为石子数,依次在几个盒子中玩游戏。但是,从环上取走一段变成链,从链上取走一段,可能分裂成两段,也就是变成两个盒子。文章来源:https://www.toymoban.com/news/detail-430288.html
从最近做的思维题、构造题中,
分析问题中的重点对象的特性和性质;从特殊到一般,转移;还想到了一些词但是忘了。文章来源地址https://www.toymoban.com/news/detail-430288.html
到了这里,关于Codeforces Round 868 (Div. 2) A~D的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!