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;
else
return false;
}
int main()
{
int i,num=0;
vis[1][2]=vis[2][1]=1; //a-g对应1-7
vis[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
标签： 2bf5a二极管2bf5a