A
请问在 1 到 2020 中，有多少个数与 2020 互质，即有多少个数与 2020 的最大公约数为 1。
答案
800
最大公约数（gcd），可以自己敲模板代码，也可以用库里的函数
#include<iostream>
using namespace std;
int gcd(int a,int b){
if(b) return gcd(b,a%b);
return a;
}
int main(){
int res=0;
for(int i=1;i<=2020;i++){
if(gcd(i,2020)==1) res++;
}
cout<<res<<endl;
return 0;
}
B
ASCII 码将每个字符对应到一个数值（编码），用于信息的表示和传输。在 ASCII 码中，英文字母是按从小到大的顺序依次编码的，例如：字母 A 编码是 65, 字母 B 编码是 66，字母 C 编码是 67，请问字母 Q 编码是多少？
答案
81
int main(){
int res;
res='Q';
cout<<res<<endl;
return 0;
}
C
有一棵二叉树，一个由2021个结点，其中有1000个结点有两个子结点，其他的结点有一个或者0个子结点。
请问，这棵二叉树有多少个叶结点？
答案
1001
二叉树的特性
D
对于整数 v 和 p，定义 Pierce 序列为：
a[1] = v
a[i] = p % a[i-1]
例如，当 v = 8, p = 21 时，对应的 Pierce 序列为
a[1] = 8
a[2] = 5
a[3] = 1
再往后计算，值变为 0，不在我们考虑的范围内。因此当 v = 8, p = 21 时， Pierce 序列的长度为 3。
当 p 一定时，对于不同的 v 值，Pierce 序列的长度可能不同。当 p = 8 时，若 1<=v<p，最长的 Pierce 序列出现在 v=13时，为(13, 8, 5, 1)，长度为 4。
当 p=2021 时，最长的 Pierce 序列出现在 v=1160 时，请问这个序列有多长？
答案
12
题目好像有一些问题，_当 p = 8 时，若 1<=v<p，最长的 Pierce 序列出现在 v=13时，为(13, 8, 5, 1)，长度为 4。_这里，不知道是我理解的问题，还是题目的问题
#include<iostream>
using namespace std;
int main(){
int res=0,a,b;
a=2021,b=1160;
while(b!=0){
b=a%b;
res++;
}
cout<<res<<endl;
return 0;
}
E
在 Excel 中，第 1 列到第 26 列的列名依次为 A 到 Z，从第 27 列开始，列名有两个字母组成，第 27 列到第 702 列的列名依次为 AA 到 ZZ。
之后的列再用 3 个字母、4 个字母表示。
请问，第 2021 列的列名是什么？
答案
BYS
和第十届那个问题如出一辙，模拟就可以了
#include<iostream>
using namespace std;
int main(){
char a='A'-1,b='A'-1,c='A'-1;
for(int i=1;i<=2021;i++){
a++;
if(a>'Z'){
a='A';
b++;
if(b>'Z'){
b='A';
c++;
}
}
}
cout<<c<<' '<<b<<' '<<a<<endl;
return 0;
}
F
在书写一个较大的整数时，为了方便看清数位，通常会在数位之间加上逗号来分割数位，具体的，从右向左，每三位分成一段，相邻的段之间加一个逗号。
例如，1234567 写成 1,234,567。
例如，17179869184 写成 17,179,869,184。
给定一个整数，请将这个整数增加分割符后输出。
输入格式
输入一行包含一个整数 v。
输出格式
输出增加分割符后的整数。
样例
输入
1234567
17179869184
输出
1,234,567
17,179,869,184
数据范围
对于 50% 的评测用例，$0 <= v < 10^9$。
对于所有评测用例，$0 <= v < 10^{18} $。
思路
用的STL里字符串相关的操作
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
int t=s.length(),m=0;
for(int i=t-1;i>0;i--){
m++;
if(m%3==0){
s.insert(i,",");
m=0;
}
}
cout<<s<<endl;
return 0;
}
G
斐波那契数列是这样一个数列：它的第一项和第二项都是1，从第三项开始每一项都是前两项的和。
根据以上定义，我们容易计算出斐波那契数列的前几项依次是：1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ……
现在请你计算斐波那契数列第N项是奇数还是偶数？
输入格式
输入的包含一个整数N。
输出格式
如果是奇数输出1，是偶数输出0。
样例
输入
10
输出
1
数据规模和约定
对于所有评测用例，$1 <= N <= 1000000000$。
提示
找规律。
思路
首先输出一部分偶数项的的下标，找一下规律
int main(){
f[1]=f[2]=1;
for(int i=3;i<=100;i++){
f[i]=f[i-1]+f[i-2];
if(f[i]>=100) f[i]%=100;
if(f[i]%2==0)cout<<i<<endl;
}
return 0;
}
输出
3
6
9
12
15
18
...
可以看出偶数项从第3项开始，相隔3，故而只需要看N是否是3的倍数就可以了。
C++ 代码
int main(){
long long int n=0;
cin>>n;
if(n%3==0) cout<<0<<endl;
else cout<<1<<endl;
return 0;
}
H
给定一个矩阵 M，由 n 行 m 列组成，第 i 行第 j 列值为 M[i][j]。
定义矩阵 M 的重量为矩阵中所有元素的和，即为weight(M)
请找到矩阵左上角的一个子矩阵S（矩阵的前 r 行中的前 c 列组成），使得这个子矩阵的重量的两倍最接近矩阵 M 重量。即 |2 weight(S)-weight(M)| 最小。
如果有多个子矩阵满足条件，请找出面积 r * c 最小的一个。
如果仍然有多个子矩阵满足条件，请找出其中 r 最小的一个。
输入格式
输入第一行包含两个整数 n, m，表示矩阵的大小。
接下来 n 行，每行 m 个整数，表示给定的矩阵M。
输出格式
输出一行，包含两个整数 r, c，表示子矩阵为矩阵 M 的前 r 行中的前 c 列。
样例
输入：
3 4
3 0 1 1
1 0 1 1
1 1 -2 4
输出
2 3
数据范围
对于 30% 的评测用例，$1 <= n, m <= 20, -10 <= M[i][j] <= 10$。
对于 50% 的评测用例，$1 <= n, m <= 100, -100 <= M[i][j] <= 100$。
对于所有评测用例，$1 <= n, m <= 1000, -1000 <= M[i][j] <= 1000$。
思路
二维前缀和
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int s[N][N];
int main(){
int n,m,sum=0,r=-1,c=-1,t=0x3f3f3f3f;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>s[i][j];
sum+=s[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
int a=abs(s[i][j]*2-sum);
if(a<=t){
if(a<t){
t=a;
r=i,c=j;
}
else{
if(i*j<r*c)r=i,c=j;
else if(i*j==r*c||i<r)r=i,c=j;
}
}
}
}
cout<<r<<' '<<c<<endl;
return 0;
}
I
杂货铺老板一共有N件物品，每件物品具有ABC三种属性中的一种或多种。从杂货铺老板处购得一件物品需要支付相应的代价。
现在你需要计算出如何购买物品，可以使得ABC三种属性中的每一种都在至少一件购买的物品中出现，并且支付的总代价最小。
输入格式
输入第一行包含一个整数N。
以下N行，每行包含一个整数C和一个只包含”ABC”的字符串，代表购得该物品的代价和其具有的属性。
输出格式
输出一个整数，代表最小的代价。如果无论如何凑不齐ABC三种属性，输出-1。
样例
输入
5
10 A
9 BC
11 CA
4 A
5 B
输出
13
数据范围
对于50%的评测用例，$1 <= N <= 20$
对于所有评测用例，$1 <= N <= 1000， 1 <= C <= 100000$。
思路
有一个问题是，题目中没有说输入属性的时候是按照顺序输入的，我是默认它是按照顺序输入进行做的。如果不是的话就要凉了，但是也可以在输入的地方做手脚，使得它是按照顺序进行存储的。
有看到用全排列做的朋友，也可以尝试一下。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int> mp;
string str[7]={"A","B","C","AB","BC","CA","ABC"};
int main(){
int n;
cin>>n;
for(int i=0;i<7;i++){
mp[str[i]]=0x3f3f3f3f;
}
while(n--){
int t;
string s;
cin>>t>>s;
if(mp[s]>t)mp[s]=t;
}
int res=mp["ABC"],t=0;
for(int i=0;i<3;i++){
t+=mp[str[i]];
}
if(t<res) res=t;
if(mp["A"]+mp["BC"]<res) res=mp["A"]+mp["BC"];
if(mp["B"]+mp["CA"]<res) res=mp["B"]+mp["CA"];
if(mp["C"]+mp["AB"]<res) res=mp["C"]+mp["AB"];
if(res>0x3f3f3f3f/2) cout<<-1<<endl;
else cout<<res<<endl;
return 0;
}
J
给定一个序列 $(a_1, a_2, …, a_n)$, 它的一个上升子序列是指从序列中取出一些元素，按照原来的顺序排列后，是单调递增的序列。
例如，对于序列 (3, 2, 7, 6, 7)，取出下标为 2, 4, 5 的元素$ a_2, a_4, a_5$，即 2, 6, 7，是一个上升子序列。
在这个序列中，有 7 个长度为 2 的上升子序列，例如
1. 下标 1, 3 对应的 3, 7；
2. 下标 1, 4 对应的 3, 6；
3. 下标 1, 5 对应的 3, 7；
4. 下标 2, 3 对应的 2, 7；
5. 下标 2, 4 对应的 2, 6；
6. 下标 2, 5 对应的 2, 7；
7. 下标 4, 5 对应的 6, 7。
注意，可能有下标不同但对应数值相同的上升子序列，他们应当算成不同的上升子序列。
给定序列，请问序列中一共有多少个长度为 k 的上升子序列。
输入格式
输入第一行包含两个整数 n, k，表示序列的长度和上升子序列的长度。
第二行包含 n 个整数$ a_1, a_2, …, a_n $，表示给定的序列。
输出格式
输出一行，包含一个整数，表示长度为 k 的上升子序列的数量，答案可能很大，请输出答案除以 1000007 的余数。
样例
输入
5 2
3 2 7 6 7
输出
7
数据范围
对于 30% 的评测用例，$1 <= n <= 20, 0 <= a_i <= 100$。
对于 50% 的评测用例，$1 <= n <= 100, 0 <= a_i <= 1000$。
对于所有评测用例，$1 <= n <= 1000, 1 <= k <= 10, 0 <= a_i <= 10000$。
思路
线性DP，注意题目中说数字可能很大，要求模。
不过不知道数据太大的时候时间复杂度过不过得去。应该是可以优化掉一重循环的，不过我还没想明白，就先这样吧。
C++ 代码
线性DP
推导过程不难，有一点像最短上升子序列那道模板题
#include<iostream>
using namespace std;
int f[1010][20],a[1010];
const int mod=100007;
int main(){
int n,k,res;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
f[i][1]=1;
}
for(int i=1;i<=n;i++){
for(int j=2;j<=k;j++){
for(int m=1;m<i;m++){
if(a[m]<a[i]) f[i][j]+=f[m][j-1]%mod;
}
f[i][j]%=mod;
}
}
for(int i=1;i<=n;i++){
res+=f[i][k];
}
cout<<res%mod<<endl;
}
