目录
试题 A: 门牌制作
>>624
暴力计数
#include<iostream>
using namespace std;
int main()
{
int cnt = 0;
for(int i = 1; i <= 2020; i ++)
{
int n = i;
while(n){
if(n%10==2) cnt++;
n /= 10;
}
}
cout << cnt;
return 0;
}试题 B: 既约分
>>2481214
#include<iostream>
using namespace std;
int a[2021];
int gcd(int a, int b){
return b==0? a:gcd(b,a%b);
}
int main()
{
int cnt=0;
for(int i = 1; i <= 2020; i ++)
for(int j = 1; j <= 2020; j ++)
if(j!=i && gcd(i,j)==1) cnt++;
cout<<cnt; //2481214
return 0;
}试题 C: 蛇形填数
>>761
简单推一下规律就行
试题 D:跑步锻炼(代码明天补上)
>>>8879
模拟日期累计即可
代码明天补上
试题 E: 七段码
方法1: 二进制枚举+并查集
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10;
int mp[N][N], f[N], vis[N];
int find(int x){ //路径压缩
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
int solve()
{
int res = 0;
for(int st = 1; st < 1<<7; st ++){
memset(vis,0,sizeof vis);
for(int i = 0;i < 7;i ++) f[i] = i;
for(int i = 0;i < 7;i ++)
{
if(st & (1<<i))
{
vis[i] = true;
for(int j = 0; j < 7; j ++)
{
if(mp[i][j] && vis[j]){
int fi = find(i), fj = find(j);
f[fi] = fj;
}
}
}
}
// 连通块数
int cnt = 0;
for(int i = 0;i < 7;i ++){
if(vis[i] && i == f[i]){
cnt ++;
if(cnt > 1) break;
}
}
if(cnt == 1) res ++;
}
return res;
}
int main()
{
//初始化图
mp[0][1]=mp[1][0]=1;
mp[0][5]=mp[5][0]=1;
mp[1][2]=mp[2][1]=1;
mp[1][6]=mp[6][1]=1;
mp[2][6]=mp[6][2]=1;
mp[2][3]=mp[3][2]=1;
mp[3][4]=mp[4][3]=1;
mp[4][6]=mp[6][4]=1;
mp[4][5]=mp[5][4]=1;
mp[5][6]=mp[6][5]=1;
//枚举从1开始的所有状态
cout << solve();
return 0;
}
方法2: DFS+并查集
#include<iostream>
using namespace std;
const int N = 10;
int res;
int vis[N], mp[N][N], f[N];
int find(int x){
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
}
void dfs(int n) {
if(n==7) {
for(int i = 0; i < 7; i++)
if(vis[i])
for(int j = 0; j < 7; j ++)
if(mp[i][j] && vis[j])
f[find(i)] = find(j);
int t = -1, m = 0;
for( ; m < 7; m ++) {
if(vis[m] && t==-1) t = find(m);
if(vis[m] && find(m)!=t) break;
}
if(m==7 && t!=-1) res++;
for(int i = 0; i < 7; i ++) f[i] = i;
return;
}
//灭 or 亮
vis[n]=0;
dfs(n+1);
vis[n]=1;
dfs(n+1);
}
int main()
{
//初始化图
mp[0][1]=mp[1][0]=1;
mp[0][5]=mp[5][0]=1;
mp[1][2]=mp[2][1]=1;
mp[1][6]=mp[6][1]=1;
mp[2][6]=mp[6][2]=1;
mp[2][3]=mp[3][2]=1;
mp[3][4]=mp[4][3]=1;
mp[4][6]=mp[6][4]=1;
mp[4][5]=mp[5][4]=1;
mp[5][6]=mp[6][5]=1;
for(int i = 0; i < 7; i ++) f[i] = i;
dfs(0);
cout << res;
return 0;
}
试题 F: 成绩统计
略,签到题
试题 H: 子串分值和
模拟
需要记住每个字母上次出现的位置来计算权值,再与其后的串长相乘
和之前做过的这道有异曲同工之妙
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
char s[N];
ll last[26];
int main()
{
scanf("%s", s + 1);
int n = strlen(s + 1);
ll ans = 0;
for (int i = 1; i <= n; i++)
{
int x = s[i] - 'a';
ans += (i - last[x]) * (n - i + 1);
last[x] = i;
}
cout << ans << endl;
return 0;
}
试题 I: 平面切分
直线分平面公式
#include<iostream>
#include<set>
using namespace std;
const int N = 10010;
int A[N], B[N];
typedef pair<double, double> PII;
set<PII> s, p; //线集合,点集合
int main()
{
int n, a, b;
cin >> n;
for(int i = 0; i < n; i ++)
{
scanf("%d%d",&a, &b);
s.insert({a, b});
}
int m = 0;
for(auto t : s)
{
A[m] = t.first, B[m++] = t.second;
}
int res = 2;
for(int i = 1; i < m; i ++)
{
for(int j = i-1; j >= 0; j --)
{
double a1 = A[i], a2 = A[j], b1 = B[i], b2 = B[j];
double x, y; //交点
x = (b2-b1)/(a1-a2);
y = a1*(b2-b1)/(a1-a2)+b1;
p.insert({x, y});
}
res += p.size()+1; //与之前直线交点的和再加一,表示新增的平面数
}
cout << res ;
return 0;
}