题目列表
- 七段码（二进制枚举+并查集）
- 跑步锻炼（日期模拟）
- 跑步训练（模拟）
- 纪念日（日期）
- 分配口罩（dfs）
- 蛇形填数 （模拟）
- 既约分数 （最大公约数，gcd模板）
- 星期一（日期模拟）
- 测试次数（dp）
- 迷宫（bfs）
七段码
题目描述
小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。
例如：b 发光，其他二极管不发光可以用来表达一种字符。
例如：c 发光，其他二极管不发光可以用来表达一种字符。
这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。
例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。
本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
参考文献
https://blog.csdn.net/weixin_46239370/article/details/109580869
核心
二进制枚举所有状态，并查集判断连通块
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=10;
int p[N];
int e[N][N];
int ans;
bool state[N];
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void init(){
e[1][2] = e[1][6] = 1;
e[2][1] = e[2][7] = e[2][3] = 1;
e[3][2] = e[3][7] = e[3][4] = 1;
e[4][3] = e[4][5] = 1;
e[5][4] = e[5][7] = e[5][6] = 1;
e[6][1] = e[6][7] = e[6][5] = 1;
e[7][2] = e[7][3] = e[7][5] = e[7][6] = 1;
}
int main(){
init();
for(int st=1;st<(1<<7);st++){
memset(state,false,sizeof state);
for(int i=1;i<=7;i++)
p[i]=i;
for(int i=0;i<7;i++){
if(st>>i &1){
state[i+1]=true;
}
}
for(int i=1;i<=7;i++){
for(int j=1;j<=7;j++)
if(state[i]&&state[j] && e[i][j]==1){
p[find(i)]=find(j);
}
}
int cnt=0;
for(int i=1;i<=7;i++){
if(state[i]&&p[i]==i)
cnt++;
}
if(cnt==1) ans++;
}
cout<<ans;
return 0;
}
答案：80
跑步锻炼
题目描述
核心：日期模拟，注意：边界条件
代码
#include<iostream>
using namespace std;
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int x){
int year = x/10000;
int months = x%10000/100;
int days =x%100;
if(!months|| months>12|| !days) return false;
if(months!=2 && days>month[months]) return false;
if(months==2){
bool leap = (year%4==0&& year%100)||year%400==0;
if(days>28+leap) return false;
}
return true;
}
int main(){
int cnt=0,t=0;
int st=20000101;
//0-6表示周一到周日
for(int i=st;i<=20201001;i++){
if(check(i)){
// cout<<i<<endl;
t++;
// cout<<(cnt+5)%7<<endl;
if(i%100==1||(cnt+5)%7==0){
t++;
// if(i==20000101)
// cout<<i<<t<<endl;
}
cnt++;
}
}
cout<<t<<endl;
return 0;
}
答案：8879
跑步训练
题目描述
核心：模拟
#include<iostream>
using namespace std;
int main(){
int n=10000;
int t=0,temp;
while(n!=0){
t++;
if(t&1){
if(n>600)
n-=600;
else{
t--;
temp=n/10;
break;
}
}else{
n+=300;
}
// if(n==0) break;
}
cout<<t*60+temp;
return 0;
}
答案：3880
纪念日
题目描述
请问从 1921 年 7 月 23 日中午 12 时到 2020 年 7 月 1 日中午 12 时一共包含多少分钟？
核心：日期模拟
代码
#include<iostream>
using namespace std;
int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int x){
int year = x/10000;
int month =x%10000/100;
int day = x%100;
if(!month || month>12 || !day) return false;
if(month!=2 && day>months[month]) return false;
if(month==2){
bool leap = (year%4==0 && year%100) || year%400==0;
if(day > 28+leap)
return false;
}
return true;
}
int main(){
int st = 19210723;
int day=0;
for(int i=st;i<20200701;i++){
if(check(i)){
day++;
}
}
cout<<day*24*60;
return 0;
}
答案：52038720
约数个数
题目描述
对于一个整数，能整除这个整数的数称为这个数的约数。
例如：1, 2, 3, 6 都是 6 的约数。
请问 78120 有多少个约数。
代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int divide(int x){
vector<int> q;
for(int i=1;i<=x/i;i++){
if(x%i==0){
q.push_back(i);
if(i!=x/i) q.push_back(x/i);
}
}
return q.size();
}
int main(){
int n=78120;
int a=divide(n);
cout<<a;
return 0;
}
答案：96
分配口罩
题目描述
核心：模拟，暴力枚举
代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int num[15]={9090400 ,8499400 ,5926800 ,8547000 ,4958200 ,4422600 ,5751200 ,4175600 ,6309600 ,5865200 ,6604400 ,4635000 ,10663400 ,8087200 ,4554000};
bool st[15];
int res=1e18;
void dfs(int n){
int ans1=0,ans2=0;
if(n==15) {
for(int i=0;i<15;i++){
if(st[i])
ans1+=num[i];
else
ans2+=num[i];
res=min(res,abs(ans1-ans2));
}
return;
}
st[n]=true;
dfs(n+1);
st[n]=false;
dfs(n+1);
return ;
}
int main(){
int ans=-1e5;
dfs(0);
cout<<res;
return 0;
}
答案：2400
蛇形填数
题目描述
如下图所示，小明用从 1 开始的正整数 “蛇形” 填充无限大的矩阵。
核心：找规律，发现对角线为1，5，13.......
代码
#include<iostream>
using namespace std;
int main(){
int ans=1;
for(int i=1;i<=20;i++){
int k=(i-1)*4;
ans=ans+k;
}
cout<<ans<<endl;
}
答案761
既约分数
题目描述
如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。
例如，3/4，5/2，1/8，7/1都是既约分数。
请问，有多少个既约分数，分子和分母都是1到2020之间的整数（包括 1
和 2020）？
核心：gcd板子
代码
#include<iostream>
using namespace std;
int gcd(int a,int b){
return b? gcd(b,a%b) : a;
}
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;
}
答案: 2481215
星期一
题目描述
整个20世纪（1901年1月1日 至 2000年12月31日 之间），一共有多少个星期一？
(不要告诉我你不知道今天是星期几)
核心：日期模拟
代码
#include<iostream>
using namespace std;
int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int x){
int year = x/10000;
int month = x%10000/100;
int day = x%100;
if(!month || month>12 || !day) return false;
if(month!=2 && months[month]<day) return false;
if(month==2){
bool leap = (year%4==0 && year%100)||year%400==0 ;
if(day>28+leap) return false;
}
return true;
}
int main(){
//0-6表示周一到周日
int ans=0,cnt=0;
for(int i=19010101;i<=20001231;i++){
if(check(i)){
if((cnt+1)%7==0){
ans++;
}
cnt++;
}
}
cout<<ans<<endl;
return 0;
}
答案 5217
测试次数
题目描述
x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。
x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。
塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。
如果手机从第 7 层扔下去没摔坏，但第 8 层摔坏了，则手机耐摔指数 = 7。
特别地，如果手机从第 1 层扔下去就坏了，则耐摔指数 = 0。
如果到了塔的最高层第 n 层扔没摔坏，则耐摔指数 = n
为了减少测试次数，从每个厂家抽样3部手机参加测试。
某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？
请填写这个最多测试次数。
核心：动态规划
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int f[4][1010];
int main(){
// memset(f,0x3f,sizeof f);
for(int i=1;i<=3;i++)
for(int j=1;j<=1000;j++)
f[i][j]=j;
for(int i=2;i<=3;i++)
for(int j=1;j<=1000;j++)
for(int k=1;k<j;k++)
f[i][j]=min(f[i][j],max(f[i-1][k-1],f[i][j-k])+1);
cout<<f[3][1000];
}
答案：19
迷宫
题目描述
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可 以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫，一共 10 步。
其中 D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫（30 行 50 列），
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
核心：bfs+路径记录
代码
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
char g[50][55];
int dist[35][55];
int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
char dir[] = {'U', 'L', 'R', 'D'};
string ans;
int bfs(){
queue<pii> q;
q.push({29,49});
memset(dist,-1,sizeof dist);
dist[29][49]=0;
while(q.size()){
auto t = q.front();
q.pop();
int x = t.first;
int y = t.second;
for(int i=0;i<4;i++){
int x1=x+dx[i],y1=y+dy[i];
if(x1>=0 && y1>=0 && x1<30 && y1<50 && dist[x1][y1]==-1 && g[x1][y1]=='0'){
// cout<<dx[i]<<' '<<dy[i]<<endl;
q.push({x1,y1});
dist[x1][y1]=dist[x][y]+1;
// ans+=dir[i];
}
}
}
return dist[0][0];
}
int main(){
for(int i=0;i<30;i++)
scanf("%s",g[i]);
// for(int i=0;i<30;i++)
// printf("%s\n",g[i]);
cout<<bfs();
int x=0,y=0;
while(x != 29 || y != 49)
{
for (int i = 0; i < 4; i ++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= 30 || b < 0 || b >= 50) continue;
if(g[a][b] == '1') continue;
if(dist[x][y] == dist[a][b] + 1)
{
ans += dir[i];
x = a, y = b;
break;
}
}
}
cout << ans << endl;
return 0;
}
希望明天省赛好运~
跑步锻炼已修改