A 门牌号
题意：统计 ([1,2020]) 所有整数中，数码 (2) 出现的次数
分析：直接暴力枚举即可：
inline int f(int n){
int ans=0;
while(n) ans+=(n%10==2),n/=10;
return ans;
}
...
int ans=0;
for(int i=1;i<=2020;i++) ans+=f(i);
输出为 (624)
B 既约分数
题意：对于满足 (displaystyle a,bin Z，{aover b}) 为最简分数的分数称为既约分数，求 (1leq a,bleq 2020) 的既约分数个数
分析：暴力枚举 (a,b) ，用 gcd 判是否互质
int ans=0;
for(int a=1;a<=2020;a++)
for(int b=1;b<=2020;b++)
ans+=(__gcd(i,j)==1);
输出为 (2481215)
C 蛇形矩阵
题意：给出如下矩阵，求第 (20) 行 (20) 列
1 2 6 7 ...
3 5 8 ...
4 9 ...
10 ...
...
分析：考虑令 (f_n) 为第 (n) 行 (n) 列的值
不难看出，(f_n) 转移至 (f_{n+1}) 需要自己所在斜线走一半+下一条斜线走完+(f_{n+1}) 所在斜线走一半
根据各斜线的长度，不难列出转移方程 (f_{n+1}=f_n+n-1+2n+n+1=f_n+4n) ，可解出 (displaystyle f_n=4sum_{i=1}^{n-1}i+f_1=2n(n-1)+1)
代入 (n=20) 得到 (f_{20}=761)
D 七段码
题意：求多少种不同的七段码表示方法，各个亮起的灯管互相连接，且至少有一个灯管亮起
分析：用数组储存灯管间的连接情况，枚举 (2^7) 种情况，用 bfs 检查是否满足，统计答案即可
#include<bits/stdc++.h>
using namespace std;
bool connect[7][7]={
{0,1,0,0,0,1,0},
{1,0,1,0,0,0,1},
{0,1,0,1,0,0,1},
{0,0,1,0,1,0,0},
{0,0,0,1,0,1,1},
{1,0,0,0,1,0,1},
{0,1,1,0,1,1,0}
};
inline int isconnect(int S){
int que[16],Head=0,Tail=0,NS=0;
bool vis[16]={0};
for(int i=0;i<7;i++) if( (S>>i)&1 ){
que[++Tail]=i;
vis[i]=1;
break;
}
while(Head<Tail){
int now=que[++Head];
NS|=1<<now;
for(int i=0;i<7;i++)
if( ((S>>i)&1)&&connect[now][i]&&!vis[i] ){
que[++Tail]=i;
vis[i]=1;
}
}
return NS==S;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int Ans=0;
for(int i=1;!(i>>7);i++) Ans+=isconnect(i);
cout<<Ans;
cout.flush();
return 0;
}
输出为 (80)
E 直线与圆
题意：用 (20) 条直线与 (20) 个圆，求最多能将平面分为几个部分
分析：任意线（包括直线与曲线）之间，不交于同一点，则能将平面分为尽可能多的部分
根据欧拉定理 (V-E+F-T=1,T=0) ，求解出 (F=1+E-V) ，只需求解出点数 (V) 与边数 (V) 即可求解
根据我们的分析，任意两直线即可有一交点，个数为 (displaystyle (^{20}_2)) ；任意两圆之间有两个交点，个数为 (displaystyle 2cdot (^{20}_2)) ；任意圆与直线之间有两个交点，个数为 (20 imes 20 imes 2)
故 (displaystyle V=(^{20}_2)+2cdot (^{20}_2)+20 imes 20 imes 2=1370)
同样根据我们的分析，一条直线被剩余的 (19) 条直线各交于一点，被 (20) 个圆各交于两点，故线上有 (19+20 imes 2=59) 个点，一条直线被分为 (60) 条边；一个圆被剩余的 (19) 个圆、 (20) 条直线各交于两点，共 ((19+20) imes 2=78) 个点，一个圆被分为 (78) 条边
故 (displaystyle E=60 imes 20+78 imes 20=2760)
因此得到答案： (displaystyle F=1+2760-1370=1391)
F 成绩分析
题意：给出 (n) 个学生的成绩，求最高分、最低分与平均值
分析：直接在输入的时候储存最大值、最小值和分数和，最后分数和除去人数得到平均分
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N,S,MinS,MaxS,SumS;
cin>>N>>S;
MinS=MaxS=SumS=S;
for(int i=2;i<=N;i++)
cin>>S,MinS=min(MinS,S),MaxS=max(MaxS,S),SumS+=S;
cout<<MaxS<<'
'<<MinS<<'
'<<fixed<<setprecision(2)<<SumS*1.0/N;
cout.flush();
return 0;
}
G 回文年份
题意：输入一个日期，输出严格后于日期的第一个 ABCDDCBA 型日期，和第一个 ABABBABA 型日期。保证有解。
分析：第一种日期，直接枚举对应月份的对应日期，进行翻转，储存好 (366) 个日期后排序，查找第一个比输入大的即可（数据量太小，懒得写二分了）。第二种日期，由于月份和日期相同，直接枚举月份，进行翻转，储存好 (12) 个日期后和第一个储存方法相同。
#include<iostream>
#include<algorithm>
using namespace std;
int Day1[512],Day2[512];
inline int built(int month,int day){
return ((day%10*10+day/10)*100+(month%10*10+month/10))*10000+month*100+day;
}
inline void pre(){
int cntday[]={0,31,29,31,30,31,30,31,31,30,31,30,31},CntDay1=0;
for(int month=1;month<=12;month++)
for(int day=1;day<=cntday[month];day++)
Day1[++CntDay1]=built(month,day);
sort(Day1+1,Day1+367);
for(int month=1;month<=12;month++)
Day2[month]=built(month,month);
sort(Day2+1,Day2+13);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
pre();
int N;
cin>>N;
for(int i=1;i<=366;i++) if(Day1[i]>N) {
cout<<Day1[i]<<'
';
break;
}
for(int i=1;i<=12;i++) if(Day2[i]>N) {
cout<<Day2[i]<<'
';
break;
}
cout.flush();
return 0;
}
H 子串序列
题意：求一个字符串 (S) 的所有子串中，每个子串出现仅一次的字符个数和
分析：对于每一个字符单独考虑：对于第 (i) 个字符 (c) ，设其前面第一个与之相同的字符出现的位置为 (pre_i) （没有则为 (0)），后面第一个为 (nxt_i) （没有则为 (n+1)）
则对于满足 (lin(pre_i,i],rin [i,nxt_i)) 的所有区间 ([l,r]) ，仅出现一个字符 (c) ，故对每个区间都产生 (1) 的贡献，总贡献即为 ((i-pre_i)cdot (nxt_i-i)) ，每个统计起来即可
#include<iostream>
#include<string>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
string s;
int Pre[MAXN],Nxt[MAXN],PreIndex[26];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
getline(cin,s);
for(int i=0;i<s.size();i++){
if(PreIndex[s[i]-'a']) Nxt[ PreIndex[s[i]-'a'] ]=i+1;
Pre[i+1]=PreIndex[s[i]-'a'];
Nxt[i+1]=s.size()+1;
PreIndex[s[i]-'a']=i+1;
}
ll Ans=0;
for(int i=1;i<=s.size();i++) Ans+=1ll*(i-Pre[i])*(Nxt[i]-i);
cout<<Ans;
cout.flush();
return 0;
}
I 荒岛探测
题意：给定一个三角形荒岛，在荒岛上的某个人距离两给定点的距离之和不得超过给定值 (L) ，问其可覆盖的面积大小
分析：（口胡算法，现场未实现）
动点到两顶点距离之和不超过某定值，图形为一椭圆。问题等价于给定椭圆与给定三角形的交集图形大小。
在椭圆上逆时针顺序取 (10^6) 个点，按序连接，构成 (10^6) 个向量。将这些向量与三角形的三个向量求解半平面交，若有交集，则输出大小；否则输出 (0)
J 字串排序
题意：求解一字符串，满足条件：按照冒泡排序算法，需要交换的次数为给定次数 (V) ；若有多解，输出最短的；若仍有多杰，输出字典序最小的
分析：待补