Codeforces Round 868 (Div. 2) A~D

这篇具有很好参考价值的文章主要介绍了Codeforces Round 868 (Div. 2) A~D。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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=p1k1pmkm,质因数个数m,合因数个数 Π ( k i + 1 ) − m − 1 \Pi (k_i+1)-m-1 Π(ki+1)m1注意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(na log(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 k20,英文字母有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

到了这里,关于Codeforces Round 868 (Div. 2) A~D的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Codeforces Round 920 (Div. 3)

    Codeforces Round 920 (Div. 3) 题意:随机给出正方形在平面坐标系上的四个顶点的坐标,求正方形的面积,正方形边与xy轴平行。 思路:因为正方形与坐标轴平行,所以找出相同的两x或y坐标即可找到一条边的长度,平方就是面积,注意结果返回整型。 AC code: 题意:给出两个01字符

    2024年01月17日
    浏览(68)
  • Codeforces Round 912 (Div. 2)

    大等于2依据冒泡排序即可排序,因此判断下1即可 对每一个数字找哪一位肯定为0填0其他的填1 从后往前考虑加到当前集合或新立一个集合 从最高位开始考虑能否为1,计算能否时每个数当前位为1

    2024年02月04日
    浏览(45)
  • Codeforces Round 881 (Div. 3)

    给定一个数组,给每个元素涂色。求最大的代价。 代价为每个颜色的代价和。 每个颜色的代价为涂了该颜色的元素的极差。 因为是极差,每个元素要么对答案有正的贡献,要么有负的贡献,要么无贡献。且正负贡献的个数要相同。 因为要最大值,自然就是想有正贡献的是最

    2024年02月09日
    浏览(44)
  • Codeforces Round 867 (Div. 3)

    从所有a[i]+i-1=t的选择种取个max即可 实际上就是取同符号乘积的最大值 找规律,发现结果与边长n的关系是:res = n * (n + 3) - (n - 2) ①当n为奇数时,除了1其他均无解 ②当n为偶数时,我们可以构造一个形如n,1,n - 2,3,...的数列 首先我们可以发现n必定出现在起始位置。如果n不在起

    2024年02月02日
    浏览(49)
  • Codeforces Round 874 (Div. 3)

    用最少的长度为2的字符串按一定规则拼出s。规则是:前一个字符串的尾与后一个字符串的首相同。 统计s中长度为2的不同字符串数量。 给定数组a[n]和b[n],重排b后,令任意|ai−bi|≤k成立(1≤k≤n)数据保证一定有解。 将a和b分别按从小到大的顺序匹配便是最优的,一定能满足

    2024年02月05日
    浏览(38)
  • Codeforces Round 894 (Div. 3)

    签到题 a数组里,大于等于前一个值的a[i]会被写到b里。直接遍历b,如果b[i]比前一个小就在它前面插一个相等的值 计算反过来的长度,判断是否相等就行 对于没有重复口味的集合,能选出的方案是n*(n-1)/2 (从n个里面选2个的组合数)。二分找出需要多少不同口味的冰淇淋,

    2024年02月11日
    浏览(45)
  • Codeforces Round 926 (Div. 2)

    类似于倍投法,就是在一赔一的情况下,第一次压一块钱,每输一次就押注上一次两倍的金额. 假如资金无限的话,这种方法赢的期望为无穷大.原理类似于二进制,不论你输再多次,只要赢一次总额就增加了1.比如 15 二进制1111,前3把一直输,但是只要第4把赢,就一定可以增加 1

    2024年02月20日
    浏览(45)
  • Codeforces Round 866 (Div. 2)

    给出一个仅由_或^组成的字符串,你可以在任意位置添加_或^字符,使得字符串满足: 任意字符要么属于^_^的一部分,要么属于^^的一部分。求最少添加的字符数量。 对于_我们只需处理没有组成^_^的_: ①如果_在首位置且左边没有^则添加^ ②如果_在尾位置且右边没有^则添加

    2023年04月25日
    浏览(57)
  • Codeforces Round 871 (Div. 4)

    给定n个长度为10的字符串,问其与codeforces字符串的对应下标字母不同的个数。 对于每个字符串从前往后依次和“codeforces”对应字符比较然后统计不同字母数即可 给定长度为n的数组,问连续相邻为0的最大长度 维护一个全局最大长度res,和当前连续序列的长度cnt。从前往后扫

    2024年02月03日
    浏览(53)
  • Codeforces Round 918 (Div. 4)补题

    Odd One Out(Problem - A - Codeforces) 题目大意:有三个数,其中两个相同,找出不同的那个数。 Not Quite Latin Square(Problem - B - Codeforces) 题目大意:有一个3*3的矩阵,每行每列都由1,2,3三个元素构成,且同行同列中的元素不同,先有一个地方出现空缺,要求输出空缺位置的元素

    2024年02月01日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包