吐槽一下，这次比赛不知道怎么的，可能是div3参加的人比较多吗，代码题解上去后全是in queue，比赛的过程中我还看了提交的，80多页几千个提交全是in queue, 我的代码等了**半个多小时才运行，然后发现time limit真的有点搞心态，思路在下一题我还要反过来去优化上一题，不过还是自己太菜了，能力够强的话直接半小时全部提交等ak了
比赛链接
Dashboard - Codeforces Round 962 (Div. 3) - Codeforces
题目A
链接:
题目大意理解:
输入一个数字n,表示总共的腿的数量
农场只有鸡和牛
输出一个数字,表示最少有多少个动物
思路:
知道腿的数量，要使动物数量最少，那就假设全是牛，剩下的就是鸡
而且要么n能整除4,要么余数是2,那么答案就是(n + 2) / 4
代码(Python):
'''
要么n能整除4,要么余数是2,那么答案就是(n + 2) // 4
'''
def func(n: int) -> int:
return (n + 2) // 4
def main():
t = II()
result = []
'''
输入一个数字n,表示总共的腿的数量
农场只有鸡和牛
输出一个数字,表示最少有多少个动物
'''
for _ in range(t):
n = II()
res = func(n)
result.append(res)
for res in result:
print(res)
if __name__ == "__main__":
main()代码(C++):
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
/*
要么n能整除4,要么余数是2,那么答案就是(n + 2) / 4
*/
int func(int n) {
return (n + 2) / 4;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
/*
输入一个数字n,表示总共的腿的数量
农场只有鸡和牛
输出一个数字,表示最少有多少个动物
*/
while (t--){
int n;
cin >> n;
int res = func(n);
cout << res << '\n';
}
}题目B
链接:
Problem - B - Codeforces
题目大意理解:
第一行输入两个数n, k表示矩阵宽度和缩减范围
下面n行输入矩阵
对于这个矩阵,缩减范围内的数字都是相同的,把缩减范围的数字变成一个
好吧，说的有点抽象，用例子理解就好了，题目中也给出了图帮助理解
比如输入
6 3
000111
000111
000111
111000
111000
111000
操作后:
01
10
输出操作后的矩阵
思路:
遍历矩阵,每次加k,遇到的数字是什么就加入新的矩阵中去即可
代码(Python):
from typing import List
def func(arr: List[List[int]], k: int) -> List[list[int]]:
n = len(arr)
res = []
for i in range(0, n, k):
#一行一行的计算
row = []
for j in range(0, n, k):
#当前数字
cur_num = arr[i][j]
row.append(cur_num)
res.append(row)
return res
def main():
t = II()
result = []
for _ in range(t):
n, k = MII()
arr = []
for _ in range(n):
#这题有点小坑(也可能是我太蠢了),这个输入的没有空格
#不能直接使用def LII():return list(MII())
row = list(input())
arr.append([int(x) for x in row])
res = func(arr, k)
result.append(res)
for res in result:
for row in res:
for num in row:
print(num, end ='')
print()
if __name__ == "__main__":
main()代码(C++):
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
vector<vector<int>> func(vector<vector<int>> arr, int k) {
int n = arr.size();
vector<vector<int>> res;
for (int i = 0; i < n; i += k){
vector<int> row;
for (int j = 0; j < n; j += k){
int curNum = arr[i][j];
row.push_back(curNum);
}
res.push_back(row);
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--){
int n, k;
cin >> n >> k;
vector<vector<int>> arr(n, vector<int>(n));
for (int i = 0; i < n; i++){
string row;
cin >> row;
for (int j = 0; j < n; j++){
arr[i][j] = row[j] - '0';
}
}
vector<vector<int>>res = func(arr, k);
for (auto row : res){
for(auto n : row){
cout << n;
}
cout << '\n';
}
}
}题目C
链接:
题目大意理解:
输入第一行两个数字n, q分别表示字符串长度和查询次数
接下来两行,输入两行字符串a, b 接下来
q行每行输入两个数l, r表示查询区间
sort[a[l...r]]表示对区间[a_l - 1, a_r - 1]中
对字符串进行排序,字典序小的在前面
一次操作:
可以选择一个在区间内一个字符变成任何一个想要的字符
经过若干次操作,使得sort[a[l...r]] == sort[b[l...r]]
输出最小操作次数
思路:
首先理解这个sort
只要字符串里面的含有的字符个数和类型都相同,排序后两个字符串就是相等的
那么现在只需要统计l, r这个区间内的字符串不同的个数即可
可以用一个长度26的数组进行统计
可以对每一次操作直接暴力统计:
#这个方法每次查询都要遍历同一个字符串某个区间,当查询次数过多会超时的
def func_time_limit(a: str, b: str, l: int, r: int) -> int:
a = a[l - 1:r]
b = b[l - 1:r]
if a == b:
return 0
cnt1 = [0] * 26
cnt2 = [0] * 26
for c in a:
cnt1[ord(c) - ord('a')] += 1
for c in b:
cnt2[ord(c) - ord('a')] += 1
#相同的个数
cnt = sum(min(cnt1[i], cnt2[i]) for i in range(26))
return len(a) - cnt这个方法每次查询都要遍历同一个字符串某个区间,当查询次数过多会超时的
得想一个新的思路，既然每次都会查询同一个字符串的每个区间，那么可以用类似前缀和的思想
写一个函数，对一个长度为n的字符串生成一个行数为n + 1列数为26二维数组，这个二维数组每一行表示字符串每个下标前面所拥有的字符串个数和类型
然后每次查询就只需要对这个二维数组进行操作即可
代码(Python):
def pre(s: str) -> List[List[int]]:
n = len(s)
cnt = [[0] * 26 for _ in range(n + 1)]
for i in range(1, n + 1):
#复制上一行,然后在这一行添加字符串s的当前字符
cnt[i] = cnt[i - 1].copy()
cnt[i][ord(s[i - 1]) - ord('a')] += 1
return cnt
def func(cnt_a: List[list[int]], cnt_b: List[List[int]], l: int, r: int):
cnt = 0
for i in range(26):
#求出a和b在这个区间的字符个数即可
a = cnt_a[r][i] - cnt_a[l - 1][i]
b = cnt_b[r][i] - cnt_b[l - 1][i]
#相同的个数就是a和b之间的最小值
cnt += min(a, b)
return r - l + 1 - cnt
def main():
t = int(input())
result = []
for _ in range(t):
n, q = map(int, input().split())
a = input()
b = input()
#生成一个二维前缀数组
cnt_a = pre(a)
cnt_b = pre(b)
for _ in range(q):
l, r = map(int, input().split())
result.append(func(cnt_a, cnt_b, l, r))
for res in result:
print(res)
if __name__ == "__main__":
main()代码(C++):
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<vector<int>> pre(string& s) {
int n = s.length();
vector<vector<int>> cnt(n + 1, vector<int>(26, 0));
for (int i = 1; i <= n; i++) {
cnt[i] = cnt[i - 1];
cnt[i][s[i - 1] - 'a']++;
}
return cnt;
}
int func(vector<vector<int>>& cnt_a, vector<vector<int>>& cnt_b, int l, int r) {
int res = 0;
for (int i = 0; i < 26; i++) {
int diff_a = cnt_a[r][i] - cnt_a[l - 1][i];
int diff_b = cnt_b[r][i] - cnt_b[l - 1][i];
res += min(diff_a, diff_b);
}
return r - l + 1 - res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
vector<int> result;
while (t--) {
int n, q;
cin >> n >> q;
string a, b;
cin >> a >> b;
vector<vector<int>> cnt_a = pre(a);
vector<vector<int>> cnt_b = pre(b);
while (q--) {
int l, r;
cin >> l >> r;
result.push_back(func(cnt_a, cnt_b, l, r));
}
}
for (int res : result) {
cout << res << '\n';
}
return 0;
}题目D
链接:
题目大意理解:
输入两个数n, x
然后找出满足条件的三元组的个数(a, b, c)
这三元组是有顺序的,比如(1,1,2)和(1,2,1)算两个
满足:ab+ac+bc≤n &&
标签：小白想,cnt,962,int,题解,vector,func,res,row From： https://blog.csdn.net/2401_83669813/article/details/140733865