比赛链接:
Dashboard - Codeforces Round 963 (Div. 2) - Codeforces
之后有实力了再试试后面的题目，现在要做那些题，起码要理解一个多小时
题目A:
链接:
题目大意理解:
极少数不考翻译能读懂的cf题目(bushi)
每个测试用例第一行一个n，第二行一个只含有ABCD和？的字符串，长度为4n
第二行的字符串表示答题卡上面的选项，问号表示没选
然后每个选项最多只有n个是对的
然后输出这个答题卡中最多有多少个正确答案
比如输入
5
ACADC??ACAC?DCAABC?C
一共有 6个 A, 一个B, 7个C, 2个D
由于每个选项最多只有n个是对的，此时就是5个
那么最大值就是 5 + 1 + 5 + 2 = 13
输出
13
思路:
上面示例已经写出来了，直接统计每个字母的数目，然后大于n答案就加上n，如果小于n就全部加上，注意?这个，要么在统计的时候排除，要么在遍历的时候排除
代码(C++):
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--){
int n;
cin >> n;
string s;
cin >> s;
unordered_map<int, int> map;
int res = 0;
for (auto& c : s){
map[c] += 1;
}
for (auto& [key, val] : map){
if (key != '?'){
if (val >= n){
res += n;
}else{
res += val;
}
}
}
cout << res << '\n';
}
return 0;
}代码(Python):
def main():
t = II()
res = []
for _ in range(t):
n = II()
s = I()
hash_map = defaultdict(int)
for c in s:
if c != '?':
hash_map[c] += 1
r = 0
for v in hash_map.values():
if v >= n:
r += n
else:
r += v
res.append(r)
for r in res:
print(r)题目B:
很好的一个思维题，文字描述这么少，我竟然能两次把题目意思理解错
链接:
题目大意理解:
输入一列数字，你可以选择两个奇偶性不同的数进行操作
然后两个数字中小的那个数字替换成两个数字的和
最后操作结果是保证这一列数字奇偶性相同
输出最小操作次数
思路:
注意题目条件：两个数字中小的那个数字替换成两个数字的和
一个奇数加上一个偶数肯定是变成奇数的，那么就变换偶数即可
不管奇数偶数数量怎么样，都必须把所有的偶数变成奇数
那么答案肯定大于等于偶数的数量，可以定义res = ev.size()
对偶数的集合进行排序，遍历偶数集合并且不断更新奇数中的最大值
如果出现： 此时偶数中的值大于此时奇数中的最大值
答案加上一即可(把最大的偶数替换一次即可)
代码(C++):
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--){
int n;
cin >> n;
vector<int> odd, ev;
for (int i = 0; i < n; i++){
int x;
cin >> x;
if (x % 2){
odd.push_back(x);
}else{
ev.push_back(x);
}
}
if (!odd.size() || !ev.size()){
cout << 0 << '\n';
continue;
}
long long val = 0;
int res = ev.size();
for (auto& x : odd){
val = max((long long)x, val);
}
sort(ev.begin(), ev.end());
for (auto& x : ev){
if (x > val){
res++;
break;
}
val += x;
}
cout << res << '\n';
}
return 0;
}代码(Python):
def main():
t = II()
res = []
for _ in range(t):
n = II()
arr = LII()
ev = []
odd = []
for x in arr:
if x % 2:
odd.append(x)
else:
ev.append(x)
if len(ev) == 0 or len(odd) == 0:
res.append(0)
continue
max_val = 0
for x in odd:
max_val = max(x, max_val)
r = len(ev)
ev.sort()
for x in ev:
if x > max_val:
r += 1
break
max_val += x
res.append(r)
for r in res:
print(r)题目C:
题目意思感觉还是很好理解，但是想起来就很复杂了
链接:
题目大意理解:
每个测试用例第一行输入两个数n, k，表示房间的个数和芯片的周期数
第二行有n个不同的整数，表示芯片安装的时刻
开始所有房间的灯都是熄灭的，然后依次安装芯片，周期地控制灯的开关,芯片一旦安装上去，就会先开k分钟的灯，关k分钟的灯，然后这个周期下去
求最早一个时刻，所有灯都是亮的，如果没有就输出-1
思路:
首先明确一点，当所有的芯片安装完成后，才有可能所有的灯会亮
可以求出芯片安装时刻的最大值max_val
然后就是芯片装好一瞬间就会亮，周期是2k,
现在需要考虑的就是每一个芯片安装时刻到所有装完(max_val)这一段时间是否满足在k内即可
代码(C++):
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n);
int maxVal = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
maxVal = max(maxVal, a[i]);
}
int l = 0, r = k - 1;
for (int i = 0; i < n; ++i) {
int x = (maxVal - a[i]) % (2 * k);
if (x == k) {
l = r + 1;
break;
}
if (x < k) {
r = min(r, k - x - 1);
}
if (x > k) {
l = max(l, 2 * k - x);
}
}
if (l > r){
cout << -1 << "\n";
}
else{
cout << maxVal + l << '\n';
}
}
return 0;
}代码(Python):
def main():
t = II()
res = []
for _ in range(t):
n, k = MII()
a = LII()
max_val = max(a)
l, r = 0, k - 1
for i in range(n):
x = (max_val - a[i]) % (2 * k)
if x == k:
l = r + 1
break
if x < k:
r = min(r, k - x - 1)
else:
l = max(l, 2 * k - x)
if l > r:
res.append(-1)
else:
res.append(max_val + 1)
for r in res:
print(r)