第1题 —— 门牌制作 （5分）
- 枚举1到2020，判断有多少个字符2。
- 答案624
#include<bits/stdc++.h>
using namespace std;
int main(){
int cnt = 0;
for(int i = 1; i <= 2020; i++){
int x = i;
while(x){
if(x%10==2)cnt++;
x /= 10;
}
}
cout<<cnt<<"\n";
return 0;
}
第2题 —— 既约分数 （5分）
- 双层循环枚举1到2020，gcd分子分母=1的累加
- 答案为2481215
#include<bits/stdc++.h>
using namespace std;
int main(){
int cnt = 0;
for(int i = 1; i <= 2020; i++){
for(int j = 1; j <= 2020; j++){
if(__gcd(i,j)==1)cnt++;
}
}
cout<<cnt<<"\n";
return 0;
}
第3题 —— 蛇形填数 （10分）
- 发现每次对角线值的差是4的倍数，可以通过递推的方式计算
- 答案761
#include<bits/stdc++.h>
using namespace std;
int main(){
int x = 1;
//+4->2,+8->3,+19->20
for(int i = 1; i <= 19; i++){
x += i*4;
}
cout<<x;
return 0;
}
第4题 —— 跑步锻炼 （10分）
- 暴力遍历每一天，算出每一天的是星期几并累加跑多少，注意判断闰年
- 答案8879
#include<bits/stdc++.h>
using namespace std;
int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int main(){
int sum = 0, week = 6;
for(int year=2000; year <= 2020; year++){
if((year%400==0) || (year%4==0&&year%100!=0))a[2] = 29;
else a[2] = 28;
for(int month = 1; month <= 12; month++){
for(int day = 1; day<=a[month]; day++){
if(day==1 || week==1)sum += 2;
else sum += 1;
week = (week+1)%7;
if(year==2020 && month==10 && day==1){
cout<<sum<<'\n';
return 0;
}
}
}
}
return 0;
}
第5题 —— 七段码 （15分）
- 必须要相邻才能发光，也就是所有开着的灯必须是连通的，求合法的方案数。
- 建图后dfs选边，选完判断连通性统计答案。
- 答案80。
#include<bits/stdc++.h>
using namespace std;
int fa[10];
int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }
int e[10][10], ans;
int vis[10];
void dfs(int cur){
if(cur == 8){
for(int i = 1; i <= 7; i++)fa[i] = i;
for(int i = 1; i <= 7; i++){
for(int j = 1; j <= 7; j++){
if(e[i][j] && vis[i] && vis[j]){
int x = find(i), y = find(j);
if(x != y){
fa[x] = y;
}
}
}
}
int cnt = 0;
for(int i = 1; i <= 7; i++){
if(vis[i] && i==fa[i])cnt++;
}
if(cnt == 1)ans++;
}else{
vis[cur] = 1;
dfs(cur+1);
vis[cur] = 0;
dfs(cur+1);
}
}
int main(){
//连边建图
//a b c d e f g
//1 2 3 4 5 6 7
e[1][2] = e[1][6] = 1;
e[2][1] = e[2][7] = e[2][3] = 1;
e[3][2] = e[3][4] = e[3][7] = 1;
e[4][3] = e[4][5] = 1;
e[5][4] = e[5][6] = e[5][7] = 1;
e[6][1] = e[6][5] = e[6][7] = 1;
dfs(1);
cout<<ans<<"\n";
return 0;
}
第6题 —— 成绩统计 （15分）
- 计算及格率和优秀率，四舍五入输出。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin>>n;
int a = 0, b = 0;
for(int i = 1; i <= n; i++){
int x; cin>>x;
if(x>=60)a++;
if(x>=85)b++;
}
printf("%.0lf%%\n%.0lf%%", round(a*100.0/n), round(b*100.0/n));
return 0;
}
第7题 —— 回文日期 （20分）
- 逐个枚举判断八位数是不是回文是会超时的。
- 我们可以枚举1000到8999前四位，然后直接构造回文串，根据输入二分查询。
- 注意闰年和abab格式
//AC
#include<bits/stdc++.h>
using namespace std;
string to_string(int x){
string res;
stringstream ss;
ss<<x;
ss>>res;
return res;
}
int stoi(string x){
int res;
stringstream ss;
ss<<x;
ss>>res;
return res;
}
int a[13] = { 0, 31,28,31,30,31,30,31,31,30,31,30,31 };
int main(){
vector<int>vc, vc2; //存起来
for(int i = 1000; i <= 9999; i++){//枚举年
string s = to_string(i);
for(int j = 3; j >= 0; j--)s+=s[j];//构造abab
int yy = i;
int mm = (s[4]-'0')*10+(s[5]-'0');
int dd = (s[6]-'0')*10+(s[7]-'0');
int ok;//确保日期合法
if(mm >= 1 && mm <= 12){
if((yy%400==0) || (yy%4 == 0 && yy %100!=0))a[2] = 29;
else a[2] = 28;
if(a[mm]>=dd)ok = 1;
else ok = 0;
}else{
ok = 0;
}
//确保日期是回文
if(ok){
vc.push_back(stoi(s));
}
//确保日期是abab
if(s[0]==s[2] && s[1]== s[3]);
else ok = 0;
if(ok){
vc2.push_back(stoi(s));
}
}
int x; cin>>x;
int p1 = upper_bound(vc.begin(),vc.end(), x)-vc.begin();
int p2 = upper_bound(vc2.begin(),vc2.end(), x)-vc2.begin();
cout<<vc[p1]<<"\n";
cout<<vc2[p2]<<"\n";
return 0;
}
第8题 —— 子串分值和 （20分）
- 暴力不难想到双循环枚举起点和长度，每次计算，50分。
- 考虑每个字符的贡献，仅在与上一个与之相同的字符中间处产生贡献，直接统计。
#include<bits/stdc++.h>
using namespace std;
int main(){
string s; cin>>s;
int z[50] = {0}; long long ans = 0;
for(int i = 0; i < s.size(); i++){
z[s[i]-'a'] = i+1;
for(int i = 0; i < 27; i++){
ans += z[i];
}
}
cout<<ans<<'\n';
return 0;
}
第9题 —— 平面切分 （25分）
- 直线相交产生平面个数，是个结论。即第n条直线与前n-1条相交时，如果产生了n-1个交点，那么会多出来n个平面。
- 开个set维护直线集合，每次暴力枚举求交点，+1累积即可。
#include<bits/stdc++.h>
using namespace std;
set<pair<double, double> >se;//存直线
int calc(double c, double d){//求新产生的交点个数
set<pair<double, double> >pp;//存交点
set<pair<double, double> >::iterator i;
for(i = se.begin(); i != se.end(); i++){
double a = i->first, b = i->second;
if(a!=c){
pair<double, double> t;//求交点
t.first = (d-b)/(a-c);
t.second = c*t.first+d;
pp.insert(t);
}
}
return pp.size();
}
int main(){
int n; cin>>n;
int res = 1;
for(int i = 1; i <= n; i++){
int a, b; cin>>a>>b;
pair<double, double>t;
t.first = a; t.second = b;
if(!se.count(t)){//没有重复
res++;
res += calc(a,b);
}
se.insert(t);
}
cout<<res<<'\n';
return 0;
}
第10题 —— 字串排序 （25分）
- 冒泡排序的交换次数——序列中逆序对的个数。
在满足交换次数V的前提下，要求最短的序列。 - 可以按照字典序暴力枚举字符串，然后每次求逆序对判断>=V。