首页 > 其他分享 >Codeforces 4 A-D

Codeforces 4 A-D

时间:2024-10-30 16:20:50浏览次数:1  
标签:le 5005 NO int text sum Codeforces

题面

A B C D
难度:红 橙 橙 黄

题解

A

题目大意:

判断一个正整数 \(w\) 能否表示成两个正偶数之和。

解题思路:
考虑分类讨论 \(w\)。

对于 \(1\) 和 \(2\),显然为 NO

对于 \(w \ge 3\),考虑将其表示为 \(x + 2\)。根据题意,若 \(x\) 为偶数,则答案显然必为 YES;否则必然为 NO。因为 \(2\) 是偶数,所以 \(w\) 与 \(x\) 同奇偶。结论的证明留作思考题。

综上,若 \(w \ge 3\) 且 \(w\) 为偶数则答案为 YES,否则为 NO

#include <bits/stdc++.h>
using namespace std;
int main() {
    int w;
    scanf("%d", &w);
    if (w % 2 == 0 && w != 2) puts("YES");
    else puts("NO");
    return 0;
}

B

题目大意:

构造一个数组 \(a\),使得 \(\text {minTime}_i \le a_i \le \text{maxTime}_i(1 \le i \le d)\),且 \(\sum _{i=1} ^ d a_i = \text{sumTime}\),或输出 NO 表示不存在这样的数组。

解题思路:

先求出 \(x = \sum _{i=1} ^ d \text{minTime}_i\) 和 \(y = \sum _{i=1} ^ d \text{maxTime}_i\)。若满足 \(x \le d \le y\),则存在这样的数组,否则不存在。下面是一种构造思路:

接下来,考虑先设 \(a_i = \text{minTime}_i\),然后求 \(z = \text{sumTime} - x\)。接下来,考虑从 \(1 \le i \le d\),将 \(a_i\) 的值设为 \(\text{maxTime}_i\),并将 \(z\) 减去 \(\text{maxTime}_i - \text{minTime}_i\),直到 \(z \le 0\)。此时令 \(a_i \leftarrow a_i + z\),即为答案。证明过程略。

#include <bits/stdc++.h>
using namespace std;
int sum, d, x, y, z;
int a[100010], b[100010], c[100010];
int main() {
	scanf("%d%d", &d, &sum);
	for (int i = 1; i <= d; i++) scanf("%d%d", &b[i], &c[i]), x += b[i], y += c[i];
	if (x <= sum && sum <= y) {
		puts("YES");
		if (x == sum) {
			for (int i = 1; i <= d; i++) printf("%d ", b[i]);
			putchar('\n');
		} else if (y == sum) {
			for (int i = 1; i <= d; i++) printf("%d ", c[i]);
			putchar('\n');
		} else {
			for (int i = 1; i <= d; i++) a[i] = b[i];
			z = sum - x;
			for (int i = 1; i <= d; i++) {
				int tmp = c[i] - b[i];
				if (z > tmp) {
					z -= tmp;
					a[i] += tmp;
				} else {
					a[i] += z;
					break;
				}
			}
			for (int i = 1; i <= d; i++) printf("%d ", a[i]);
			putchar('\n');
		}
	} else {
		puts("NO");
	}
	return 0;
}

C

题目大意:

给定 \(n\) 次操作,每次向集合中加入一个字符串(当集合中没有这个字符串时),或加入【该字符串,连接,最小能使其不重复的正整数】的字符串。

解题思路:
这道题可以用 STL 中的 map 解决。使用 map 统计字符串出现的次数即可。

#include <bits/stdc++.h>
using namespace std;
int n;
map<string, int> mp;
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        if (!mp[s]) {
            mp[s] = 1;
            cout << "OK\n";
        } else {
            cout << s << mp[s] << '\n';
            mp[s]++;
        }
    }
    return 0;
}

D

题目大意:

求去除一些元素之后,严格二维上升子排列。

解题思路:
注意到 \(O(n^2)\) 可过。记忆化搜索即可。

可以使用链表存储序列。

#include <bits/stdc++.h>
using namespace std;
int n, d, w, a[5005], b[5005], f[5005], nxt[5005];
bool nok[5005];
int dfs(int x) {
	if (f[x]) return f[x];
	f[x] = 1;
	for (int i = 1; i <= n; i++) {
		if (nok[i]) continue;
		if (a[i] > a[x] && b[i] > b[x] && f[x] < dfs(i) + 1) {
			f[x] = dfs(i) + 1;
			nxt[x] = i;
		}
	}
	return f[x];
}
int main() {
	scanf("%d%d%d", &n, &d, &w);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &a[i], &b[i]);
		if (a[i] <= d || b[i] <= w) nok[i] = 1;
	}
	printf("%d\n", dfs(0) - 1);
	int pos = nxt[0];
	while (pos) {
		printf("%d ", pos);
		pos = nxt[pos];
	}
	return 0;
}

标签:le,5005,NO,int,text,sum,Codeforces
From: https://www.cnblogs.com/chenaknoip/p/18515850

相关文章

  • [CodeForces] CF628 题解
    A.TennisTournamentLink-CFLink-Luogu【题目大意】\(n\)个选手进行若干场比赛,胜者保留,败者淘汰。每场比赛为两人。每场比赛每个人需要\(b\)瓶水,裁判需要\(1\)瓶水。每个人参加这些比赛总共需要\(p\)条毛巾。注意:洛谷题面翻译有误!建议看英文版。【解题思路】每场比......
  • Educational Codeforces Round 171 (Rated for Div. 2) 10.28 ABCD题解
    EducationalCodeforcesRound171(RatedforDiv.2)10.28(ABCD)题解A.PerpendicularSegments数学(math)计算几何(geometry)题意:给定一个\(X,Y,K\)。需要求解出二维坐标系中的四个点\(A,B,C,D\),满足:\(0\leqA_x,B_x,C_x,D_x\leqX\),\(0\leqA_y,B_y,C_y,D_y\leqY\)。并......
  • Educational Codeforces Round 171 (Div. 2)
    EducationalCodeforcesRound171(Div.2)A猜结论,两条边的最小值最大时,两条边相等。所以取\(min(x,y)\)为边长的正方形,对角线就是所求。#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>usingnamespacestd;intx,y,k;voidsolve(){......
  • Codeforces Global Round 27
    CodeforcesGlobalRound27总结A将红色的位置\((r,c)\)移走,分为三块来考虑,蓝色的块移动\(m-c\),黄色的块移动\(m*(n-r)\),绿色的块移动\((m-1)*(n-r)\)。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#in......
  • 2024.10.14 Codeforces Round 978 (Div. 2)
    比赛链接Solved:4/7Upsolved:5/7Rank:447(rated343)D2.Asesino(HardVersion)题意:有n个人,除了一个卧底以外,其他人或者只会说真话,或者只会说谎,且他们知道彼此的身份。卧底只会说谎,但其他人都认为他只会说真话。现在你可以进行若干次询问,每次询问形如问第i个人第j个人是什么......
  • Educational Codeforces Round 171 (Rated for Div. 2) 题解(A-C)
    EducationalCodeforcesRound171(RatedforDiv.2)题解(A-C)这场ABC全都犯病了(悲伤)目录EducationalCodeforcesRound171(RatedforDiv.2)题解(A-C)目录A.PerpendicularSegmentsB.BlackCellsC.ActionFiguresA.PerpendicularSegments大意给你一个......
  • [CodeForces] CF520 题解
    A.Pangram【题目大意】给定一个字符串,询问是否所有英文字符(a到z)都在这个字符串中出现过,不区分大小写。【解题思路】开个桶记录字符是否出现过,最后遍历桶,如果发现有一个没出现就输出NO,否则就输出YES。注意不区分大小写!B.TwoButtons【题目大意】给定两个正整数\(n\)......
  • Educational Codeforces Round 163 (Rated for Div. 2) - VP记录
    Preface这次难度感觉挺平均的,前面的题不水,后面的题也不毒瘤(可能是因为我做的不够后面)A.SpecialCharacters开局构造题。因为特殊字符一定是成对出现的(包括两边的,可以分类讨论思考一下),所以只有\(n\)为偶数的时候才有解。然后直接以AABBAABB...的格式输够\(n\)个就行了......
  • CodeForces
    CodeForces做题记录CodeforcesGlobalRound27ASliding当\((r,c)\)被取走时:\(\foralli\in[r+1,n],(i,1)\)会移动到\([i-1,m]\),曼哈顿距离为\(m\)。\(\foralli\in[r+1,n],j\in[2,m],(i,j)\)会移动到\((i,j-1)\),曼哈顿距离为\(1\)。\(......
  • Educational Codeforces Round 171 (Rated for Div. 2)题解记录
    比赛链接:https://codeforces.com/contest/2026A.PerpendicularSegments题目说了必定有答案,直接对角线即可#include<iostream>#include<queue>#include<map>#include<set>#include<vector>#include<algorithm>#include<deque>#include<......