调试小记1既约分数2 蛇形填数3跑步锻炼4七段码5蚂蚁感冒6地宫取宝7带分数

本文主要是介绍调试小记1既约分数2 蛇形填数3跑步锻炼4七段码5蚂蚁感冒6地宫取宝7带分数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

20省2-2- 既约分数

https://vijos.org/d/gadflycq/contest/601bf6daf413621b7b360286/1041
【问题描述】
如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。
例如， \frac{3}{4}
4
3

, \frac{5}{2}
2
5

, \frac{1}{8}
8
1

, \frac{7}{1}
1
7

(即 3/4，5/2，1/8，7/1)都是既约分数。
请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1和 2020）？

【输入】
没有输入。

【输出】
输出一个整数。
考试时的代码：
要知道什么是最大公约数：
最大公约数是两个整数共有的因子中最大的那一个，最大公约数也叫最大公因子。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。

#include <bits/stdc++.h>using namespace std;int main()
{int a,b,c,d,i,s=0,flag=0;for(a=1;a<=2020;a++)for(b=1;b<=2020;b++){c=a;d=b;for(i=2;i<=c;i++){if(d%c==0||(d%i==0&&c%i==0))//if(d%i==0&&c%i==0){flag=1;break;}else continue;}if(flag==0) s++;}printf("%d",s);return 0;
}

答案：2481215
这道题重点在判断最大公约数上，这里我们利用递归和正则表达式，实现辗转相除法求最大公约数。（也是我考试时薄弱的地方）
greatest common divisor(gcd) 最大公约数

#include <bits/stdc++.h>using namespace std;
int zdgy(int i,int j){return (!j)?i:zdgy(j,i%j);
}
int main()
{int num=2020,s=0;for(int i=1;i<=num;i++)for(int j=1;j<=num;j++){if(zdgy(i,j)==1)s++;}printf("%d",s);return 0;
}

重要内容：如下代码，递归和三目运算

#include <bits/stdc++.h>using namespace std;
int gcd(int i,int j){//zdgy(i,j)求i,j的最大公约数return (!j)?i:gcd(j,i%j);
}
int main()
{int s=gcd(3,5);//求两个数的最大公约数printf("%d",s);return 0;
}

答案：761
原始的两个数相乘再除以最大公约数就是最小公倍数。

#include <bits/stdc++.h>using namespace std;
int gcd(int i,int j){//zdgy(i,j)求i,j的最大公约数return (!j)?i:gcd(j,i%j);
}
int main()
{int s=gcd(2,4);//求两个数的最大公约数printf("最大公约数%d",s);printf("最小公倍数%d",8/gcd(2,4));return 0;
}

20省2-3- 蛇形填数

https://vijos.org/d/gadflycq/contest/601bf6daf413621b7b360286/1042
【问题描述】
如下图所示，小明用从 1 开始的正整数“蛇形”填充无限大的矩阵

1 2 6 7 15 ……
3 5 8 14 ……
4 9 13 ……
10 12 ……
11 ……
……

容易看出矩阵第二行第二列中的数是 5。请你计算矩阵中第 20 行第 20 列的数是多少？

【输入】
没有输入。

【输出】
输出一个整数。

考试时，我在尝试找对角线的规律，找了很久没找出来。
参考别的：1 5 13 25 规律是代码很快就出来了
在这里插入图片描述

#include <bits/stdc++.h>using namespace std;int main()
{int a[50];a[1]=1;for(int i=2;i<=20;i++){a[i]=a[i-1]+4*(i-1);}printf("%d",a[20]);return 0;
}

解法二暴力遍历：用二维数组模拟蛇形填数过程

#include <bits/stdc++.h>using namespace std;int main()
{int a[50][50];a[0][0]=1;int x=0,y=0,z=1;while(z<=1000){y++;while(x>=0&&y>=0){a[x][y]=++z;if(y==0) break;x++;y--;}x++;while(x>=0&&y>=0){a[x][y]=++z;if(x==0)break;x--;y++;}}printf("%d",a[19][19]);return 0;
}

20省2-4- 跑步锻炼

https://vijos.org/d/gadflycq/contest/601bf6daf413621b7b360286/1043
小蓝每天都锻炼身体。
正常情况下，小蓝每天跑 1 千米。如果某天是周一或者月初（ 1 日），为了激励自己，小蓝要跑 2 千米。如果同时是周一或月初，小蓝也是跑 2 千米。
小蓝跑步已经坚持了很长时间，从 2000 年 1 月 1 日周六（含）到 2020 年10 月 1 日周四（含）。请问这段时间小蓝总共跑步多少千米？

【输入】
没有输入。

【输出】
输出一个整数。
解法一：模拟

#include <bits/stdc++.h>using namespace std;int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int main() {int y = 2000, m = 1, d = 1, w = 6, ans = 0;while(1){ans+=1+(d==1||w==1);//注意这个和下面一行的顺序if(y==2020&&m==10&&d==1) break;d++;w=(w+1)%7;if((y%400==0||(y%4==0&&y%100!=0))&&m==2){if(d>month[m]+1) {d=1,m++;}}else if(d>month[m]){d=1,m++;}if(m==13) {y++,m=1;}}printf("%d\n", ans);return 0;
}

答案：8879
这个代码让我想起也可以这样写来计算两个日期相差的天数，代码如下：

#include <bits/stdc++.h>
using namespace std;
int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main() {int y = 2000, m = 1, d = 1,  ans = 0;while(1){//注意这个和下面一行的顺序if(y==2020&&m==10&&d==1) break;ans+=1;d++;if((y%400==0||(y%4==0&&y%100!=0))&&m==2){if(d>month[m]+1) {d=1,m++;}}else if(d>month[m]){d=1,m++;}if(m==13) {y++,m=1;}}printf("%d\n", ans);return 0;
}

运行结果和用计算器算的一样

20省2-5- 七段码

https://vijos.org/d/gadflycq/contest/601bf6daf413621b7b360286/1044
【问题描述】
小蓝要用七段码数码管来表示一种特殊的文字。

上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。

(若图片无法显示，可参考如下示意图，从顶段开始顺时针依次标记为a,b,c,d,e,f，中间的横段标记为g)

   a----

f | | b
---- → g
e | | c
----
d
Copy
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。
例如： b 发光，其他二极管不发光可以用来表达一种字符。
例如： c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如： a, b, c, d, e 发光， f, g 不发光可以用来表达一种字符。
例如： b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？

【输入】
没有输入。

【输出】
输出一个整数。
【参考思路】：
把边看成一个一个的点，相邻的边有边（无向），之后求随机选取x（x>0&&x<=7）条边，使它们构成一个连通图。
是否选择这条边用0和1来表示，所以所有情况就是1~127的二进制，
最后通过dfs来判断连通图

#include <stdio.h>
#include <string.h>int vis[10][10]={0};		//各段邻接矩阵，相邻为1，不相邻为0
int ans[10];				//每次选择哪几段，选择的段为1，未选择为0
int men[10];				//存放访问标记void dfs(int pos)
{for (int i=1;i<8;i++)if ( vis[pos][i] && ans[i] && men[i]==0 )	//如果与上一段的联通，且被选择，且未被标记过，则将其标记{men[i]=1;dfs(i);}	
}bool check()
{int sum=0;memset(men,0,sizeof(men));for (int i=1;i<8;i++)if (ans[i] && men[i]==0)	//如果存在一段被选择，且该段未被之前的深搜访问标记过，则是新的一个独立段{sum++;					//每有一个新的独立段，sum就+1		men[i]=1;dfs(i);}if (sum==1)			//如果sum等于1，就表示只有一个连通域return true;elsereturn false;
}int main()
{int i,num=0;vis[1][2]=vis[2][1]=1;		//a-g对应1-7vis[1][6]=vis[6][1]=1;vis[2][3]=vis[3][2]=1;vis[2][7]=vis[7][2]=1;vis[3][4]=vis[4][3]=1;vis[3][7]=vis[7][3]=1;vis[4][5]=vis[5][4]=1;vis[5][7]=vis[7][5]=1;vis[5][6]=vis[6][5]=1;vis[6][7]=vis[7][6]=1;for (i=1;i<128;i++)			//用7位二进制表示各段选择情况{int j=i, k=1;memset(ans,0,sizeof(ans));while(j)						//求出i的二进制的每一位，存进数组{ans[k++]=j%2;j/=2;}if (check()) num++;}printf("%d\n",num);return 0;
}

14省8-蚂蚁感冒

https://vijos.org/d/gadflycq/contest/601bf6daf413621b7b360286/5ab51f74d3d8a13712243385
思维题。。
【参考思路】：

1、蚂蚁碰撞之后掉头和不掉头穿过，从效果上来看是一样的。因为速度一样，都是从一只感染变为两只感染。
2、最终感染数量 = 位于感染源左边向右走的个数 + 位于感染源右边向左走的个数 + 1（感染源本身）
3、极端情况下感染源行进方向没有相对行进的蚂蚁，那么最终只有感染源自己被感染。
考试时写的代码，分数是75，错误原因是for循环的边界写错了。
75分代码

#include <bits/stdc++.h>using namespace std;struct mymayi{int z,id;bool zf;}m[53];
bool cmp(mymayi a,mymayi b){return a.z<b.z;}
int main()
{     int n,e,input;cin>>n;for(e=0;e<=n-1;e++){scanf("%d",&input);m[e].z=abs(input),m[e].id=e,m[e].zf=input>0?1:0;}sort(m,m+n,cmp);int tag,left=0,right=0,ans=0;//左边for(int i=0;i<=n-1;i++ ){if(m[i].id==0){tag=i;break;}if(m[i].zf) left++;//1向右走}//右边for(int i=tag;i<=n-1;i++){if(!m[i].zf) right++;//0向左走}if(m[tag].zf&&right==0||!m[tag].zf&&left==0) ans=1;else ans=left+right+1;printf("%d",ans);return 0;}

100分代码：

#include <bits/stdc++.h>using namespace std;struct mymayi{int z,id;bool zf;}m[53];
bool cmp(mymayi a,mymayi b){return a.z<b.z;}
int main()
{     int n,e,input;cin>>n;for(e=0;e<=n-1;e++){scanf("%d",&input);m[e].z=abs(input),m[e].id=e,m[e].zf=(input>0)?1:0;}sort(m,m+n,cmp);int tag,left=0,right=0,ans=0;//左边for(int i=0;i<=n-1;i++ ){if(m[i].id==0){tag=i;break;}if(m[i].zf) left++;//1向右走}//右边for(int i=n-1;i>tag;i--){if(!m[i].zf) right++;//0向左走}if((m[tag].zf&&right==0 )|| ((!m[tag].zf)&&left==0)) ans=1;else ans=left+right+1;printf("%d",ans);return 0;}

这道题思路很重要，如果当时思考感染掉头，考虑之后的情况，那就是思路死胡同了，蚂蚁碰撞之后掉头和不掉头穿过，从效果上来看是一样的，这个要看出。考试时如果思路陷入了死胡同，那很有可能你思路错了，及时改变思路！！！

14省9-地宫取宝

https://vijos.org/d/gadflycq/p/5ab5210ad3d8a1371224338b
X 国王有一个地宫宝库。是 n × m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。

输入
输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)

接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值

输出
要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。
考试时代码：
14分代码

#include <bits/stdc++.h>using namespace std;
int a[55][55];
int n,m,cnt,k;
int ans=0,price;
void dfs(int i,int j,int ma,int cnt){if(cnt>k) return ;if(i==n||j==m)  return ;price=a[i][j];if(i==n-1&&j==m-1){if(cnt==k||(cnt==k-1&&price>ma)){ans++;ans%=1000000007;}return ;}if(price>ma){dfs(i+1,j,price,cnt+1);dfs(i,j+1,price,cnt+1);}dfs(i+1,j,ma,cnt);dfs(i,j+1,ma,cnt);
}
int main()
{cin>>n>>m>>k;for(int i=0;i<=n-1;i++)for(int j=0;j<=m-1;j++){scanf("%d",&a[i][j]);}dfs(0,0,-1,0);printf("%d",ans);return 0;}

数据规格是50*50递归的话容易timeout。
在这里插入图片描述
42分代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,k,a[50][50];
long long ans=0;
void dfs(int x,int y,int ma,int cnt){int cur=a[x][y];if(x==n||y==m) return ;if(x==n-1&&y==m-1){if(cnt==k) ans++;if(cnt==k-1&&cur>ma) ans++;}if(cur>ma){//可取dfs(x+1,y,cur,cnt+1);dfs(x,y+1,cur,cnt+1);}else{dfs(x+1,y,ma,cnt);dfs(x,y+1,ma,cnt);}}
int main(){cin>>n>>m>>k;for(int i=0;i<=n-1;i++)for(int j=0;j<=m-1;j++)scanf("%d",&a[i][j]);dfs(0,0,-1,0);printf("%lld",ans);
return 0;}

超时要看能不能变成贪心；是不是可以改成动态规划，用递推方式来做；是否有重复子问题。这个是有交叉的重复子问题的，重复子问题就是dfs里面的参数相同。
这个题改成记忆性递归。

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007;
int n,m,k,a[50][50],cache[50][50][14][13];long long dfs(int x,int y,int ma,int cnt){long long ans=0;int cur=a[x][y];if(cache[x][y][ma+1][cnt]!=-1) return cache[x][y][ma+1][cnt];if(x==n||y==m||cnt>k) return 0;if(x==n-1&&y==m-1){if(cnt==k) ans++;if(cnt==k-1&&cur>ma) ans++;}if(cur>ma){//可取ans+=dfs(x+1,y,cur,cnt+1);ans+=dfs(x,y+1,cur,cnt+1);}ans+=dfs(x+1,y,ma,cnt);ans+=dfs(x,y+1,ma,cnt);cache[x][y][ma+1][cnt]=ans%mod;return ans%mod;}
int main(){cin>>n>>m>>k;for(int i=0;i<=n-1;i++)for(int j=0;j<=m-1;j++)scanf("%d",&a[i][j]);memset(cache,-1,sizeof(cache));//cache的初始化值要和ans可能的值避开,取-1可行printf("%lld",dfs(0,0,-1,0) );
return 0;}

13省9-带分数

https://vijos.org/d/gadflycq/contest/601bf6daf413621b7b360286/5a98cd10d3d8a1371223dbec
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
输入格式
从标准输入读入一个正整数N (N<1000*1000)
输出格式
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
思路：
我们可以把问题简化为下面的表达式：
num = left + up / down
我们的思想是：
先遍历left，再遍历down，两层for循环就可以解决；
找出符合条件（left、up、down为1~9不重复的9个数字组成）。
生成1~9的全排列
解法二：dfs

#include<iostream>
#include<cstring>
using namespace std;int N,ans,digit,flag,full[9];void div(int m)
{while(m){if(m%10!=0)full[m%10-1]=1;m/=10;digit++;}
}bool check(int *f)
{int j;for(j=0;j<9;j++)if(!f[j])return false;return true;
}void  DFS(int a,int b,int c)
{digit=0;flag=0;div(a);div(b);div(c);if(digit>9){memset(full,0,sizeof(full));return ;}if(check(full)){ans++;memset(full,0,sizeof(full));}else memset(full,0,sizeof(full));DFS(a,(c+1)*b/c,c+1);return ;
}int main()
{int i;while(cin>>N){ans=0;memset(full,0,sizeof(full));for(i=2;i<N-1;i++)DFS(i,N-i,1);cout<<ans<<endl;}return 0;
}