调式小记第2次测训赛 20模2-Cc3-最大公约数20省1-3- 合并检测20省1-5- 矩阵17省7-日期问题 17省8-包子凑数

﹏ヽ暗。殇╰゛Y 2022-10-25 04:57 17阅读 0赞

\*\**1、20模2-Cc3-最大公约数*  
https://vijos.org/d/gadflycq/p/1035

考试时，做错了，错误原因：①70044写成7044,②找的是最大公约数，要找的是最大那个；  
提交时错误的代码：

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        
        int a=7044,b=113148;
        for(int i=b;i>=2;i--){
        
            if(b%i==0&&a%i==0){
        
                cout<<i;
                break;
            }
        }
        return 0;
    }

修改后正确的代码一：

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        
        int a=70044,b=113148;
        for(int i=a;i>=2;i--){
        
            if(b%i==0&&a%i==0){
        
                cout<<i;
                break;
            }
        }
        return 0;
    }

修改后正确的代码二：

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main() {
        
    	int m=0;
    	for(int i=1;i<=70044;i++){
        
    		if(113148%i==0&&70044%i==0){
        
    			m=i;
    		}
    	}
    	cout<<m;
    	
    	
    	return 0;
    }

\*\****2、20省1-3- 合并检测***  
https://vijos.org/d/gadflycq/p/1038  
【问题描述】  
新冠疫情由新冠病毒引起，最近在 A 国蔓延，为了尽快控制疫情， A 国准备给大量民众进病毒核酸检测。  
然而，用于检测的试剂盒紧缺。  
为了解决这一困难，科学家想了一个办法：合并检测。即将从多个人（ k个）采集的标本放到同一个试剂盒中进行检测。如果结果为阴性，则说明这 k个人都是阴性，用一个试剂盒完成了 k 个人的检测。如果结果为阳性，则说明至少有一个人为阳性，需要将这 k 个人的样本全部重新独立检测（从理论上看，如果检测前 k − 1 个人都是阴性可以推断出第 k 个人是阳性，但是在实际操作中不会利用此推断，而是将 k 个人独立检测），加上最开始的合并检测，一共使用了 k + 1 个试剂盒完成了 k 个人的检测。  
A 国估计被测的民众的感染率大概是 1%，呈均匀分布。请问 k 取多少能最节省试剂盒？

【输入】  
没有输入。

【输出】  
输出一个整数。  
考试时错误，是因为复制代码时，多了个注释新号；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70 1]  
\*\****3、20省1-5- 矩阵***  
https://vijos.org/d/gadflycq/p/1039  
【问题描述】  
把 1 ∼ 2020 放在 2 × 1010 的矩阵里。要求同一行中右边的比左边大，同一列中下边的比上边的大。一共有多少种方案？  
答案很大，你只需要给出方案数除以 2020 的余数即可。

【输入】  
没有输入。

【输出】  
输出一个整数。

【提示】  
把答案放在输出语句中输出，例如C/C++语言可以用printf或cout。  
注意：需要输出的是一个整数，不要输出任何多余内容。

首先是对题目意思的理解，2\*1010是2行1010列。我们从 2020 个数里选 1010 个放入第一行，那么为了满足同一行中右边的比左边大，只能升序排列。同理剩下的 1010 个放入第二行的也要升序排列，那么只要对于任意 i∈\[1,1010\] 都满足第二行第 i 个大于第一行第 i 个就是一种合法方案。从前往后枚举，用dp\[i\]\[j\] 表示当前枚举了 i 个数，其中 j 个放入第一行的合法方案数。  
我提交的错误的代码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70 2]  
还有数组下标越界啦，开到dp\[2020\]\[2020\]以上才得行，dp\[2020\]\[1010\]不得行的哦。  
修改后的代码一：

#include<bits/stdc++.h>
    using namespace std;
    long long dp[2050][2050];//dp[i][j]表示前i个数放前j到第一行的方案数;
    int main()
    {
           long long int i,j;
        memset(dp,0,sizeof(dp));
        dp[1][1]=1;//dp[2][1]=1;
        for( i=2;i<=2020;i++){
        
            for(j=1;j<=i;j++){
        
                    dp[i][j]=(dp[i][j]+dp[i-1][j-1])%2020;
                    if(i-j<=j)//数 行数   行数
                    {
        dp[i][j]=(dp[i][j]+dp[i-1][j])%2020;}
    
            }
        }
        printf("%lld\n",dp[2020][1010]);
    
    return 0;
     }

参考别的代码：

#include<bits/stdc++.h>
    using namespace std;
    int N = 2020, mod = 2020;
    long long dp[N][N];
    int main() {
        
       long long cnt = 0;
        dp[1][1] = 1;// 1必然放在第一行
        for (int i = 1; i <= 2020; ++i) {
        
            for (int j = 1; j <= i; ++j) {
        
                dp[i][j] += dp[i - 1][j - 1];// 将第i个数放第一行
                if (i - j <= j)
                    /*
                        因为是正向枚举，后面的数只会越来越大
                        要随时保持第一行的个数不能比第二行的少
                        否则必然出现这一列第二行比第一行小的情况
                    */
                    dp[i][j] += dp[i - 1][j];
                dp[i][j] %= mod;
            }
            
        }
        cout << dp[2020][1010];
    }

\*\****4、17省7-日期问题***  
https://vijos.org/d/gadflycq/p/5aaba0b8d3d8a13712240a9c  
小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。

比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。

给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？

输入  
一个日期，格式是"AA/BB/CC"。 (0 <= A, B, C <= 9)

输出  
输出若干个不相同的日期，每个日期一行，格式是"yyyy-MM-dd"。多个日期按从早到晚排列。

样例  
输入  
02/03/04

输出  
2002-03-04  
2004-02-03  
2004-03-02

错误代码：

#include <bits/stdc++.h>
    
    using namespace std;
    
    typedef struct{
        
        int year, month, day;
    }date;
    
    bool isyn(int y){
        
        return (y % 4 == 0) || (y % 100 && y % 400 == 0);//ture false
    }
    
    void print(const date &d){
        
        printf("%02d-%02d-%02d\n", d.year, d.month, d.day);//
    }
    
    bool compare(const date &d1, const date &d2){
        
        if(d1.year != d2.year){
        
            return d1.year < d2.year;
        }
        if(d1.month != d2.month){
        
            return d1.month < d2.month;
        }
        return d1.day < d2.day;
    }
    
    bool check(const date &d){
        
        static int month_days[] = {
        0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};//12月
        if(isyn(d.year)){
        //闰年
            month_days[2] = 29;
        }else{
        
            month_days[2] = 28;
        }
    
        if(d.year < 1960 || d.year > 2059){
        
            return false;
        }
        if(d.month < 1 || d.month > 12){
        
            return false;
        }
        if(d.day < 1 || d.day > month_days[d.month]){
        
            return false;
        }
    }
    
    int main()
    {
        
        int a, b, c;
        scanf("%d/%d/%d", &a, &b, &c);
        date d[6] = {
        
            {
        2000 + a, b, c},
            {
        1900 + a, b, c},
            {
        2000 + c, a, b},
            {
        1900 + c, a, b},
            {
        2000 + c, b, a},
            {
        1900 + c, b, a}
        };
        sort(d, d + 6, compare);//自定义排序规则
        for(int i = 0; i < 6; ++ i){
        
            if(check(d[i])){
        
                print(d[i]);
            }
        }
        return 0;
    }

错误情况  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70 3]  
醒醒，改Bug啦！！

关键字：闰年判断，枚举，输入

#include<bits/stdc++.h>
    using namespace std;
    int check(int year,int mon,int day){
        
    	
    	if(year%400==0||(year%100!=0&&year%4==0))  {
        
    		if(mon==2&&day>29) return 0;
    		
    	}
    	else
            {
        if(mon==2&&day>28) return 0;
    	
    	
    	    else return 1;
    		}
    	return 1;	
    	
    }
    void shuchu(int fi,int se,int th){
        
    	int year,mon,day;
    	for(year=1960;year<=2059;year++)
    		for(mon=1;mon<=12;mon++)
    			for(day=1;day<=31;day++){
        //有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。
    				//年月日 
    				if(year%100==fi&&mon==se&&day==th){
        
    					if(check(year,mon,day))
    					printf("%d-%02d-%02d\n",year,mon,day);	
    					
    				}
    				 
    				if(mon==fi&&day==se&&year%100==th&&fi!=th)
    				printf("%d-%02d-%02d\n",year,mon,day);	
    				
    				//ri  year mon
    				if(day==fi&&mon==se&&year%100==th&&fi!=se)
    				printf("%d-%02d-%02d\n",year,mon,day);	
    				
    			}
    		
    	
    	
    }
    int main(){
        
    	int fi,se,th;
        int xg1,xg2;
    	//scanf("%d/%d/%d",&fi,&se,&th);
    	scanf("%d%c%d%c%d",&fi,&xg1,&se,&xg2,&th);
    	shuchu(fi,se,th);	
    	return 0;
    }

\*\****5，17省8-包子凑数***

https://vijos.org/d/gadflycq/contest/60135eeef413621b7335de73/5aabd01bd3d8a13712240ba7

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入  
第一行包含一个整数N。(1 <= N <= 100)  
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)

输出  
一个整数代表答案。如果凑不出的数目有无限多个，输出INF。  
输入：  
2  
4  
5

程序应该输出：  
6

再例如，  
输入：  
2  
4  
6

程序应该输出：  
INF

考试时提交是runerro!!凸(艹皿艹 )我输入数组那里没&。。。。第一次犯这种低级错误，必须是最后一次！！

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70 4]

考试时候，没写&。。。的代码

#include <bits/stdc++.h>
    using namespace std;
    int n;
    int a[102];
    int f[10020];
    int gcd(int x,int y)
    {
        
        return x%y==0? y:gcd(y,x%y);
    }
    int main ()
    {
        
        cin>>n;
        for(int i=1;i<=n;i++)
            scanf("%d",a[i]);
        memset(f,0,sizeof(f));
            f[0]=1;
        int num=a[1];
        for(int i=2;i<=n;i++)
            num=gcd(num,a[i]);
        if(num!=1)
            cout<<"INF";
        else{
        
            for(int i=1;i<=n;i++)
            for(int j=0;j+a[i]<=10000;j++)
            if(f[j])
            f[j+a[i]]=1;
            int ans=0;
            for(int i=1;i<=10000;i++)
            if(f[i]==0)
            ans++;
            cout<<ans;}
        return 0;
    }

#include <bits/stdc++.h>
    using namespace std;
    int n;
    int a[102];
    int f[10020];
    int gcd(int x,int y)
    {
        
        return x%y==0? y:gcd(y,x%y);
    }
    int main ()
    {
        
        cin>>n;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(f,0,sizeof(f));
            f[0]=1;
        int num=a[1];
        for(int i=2;i<=n;i++)
            num=gcd(num,a[i]);
        if(num!=1)
            cout<<"INF";
        else{
        
            for(int i=1;i<=n;i++)
            for(int j=0;j+a[i]<=10000;j++)
            if(f[j])
            f[j+a[i]]=1;
            int ans=0;
            for(int i=1;i<=10000;i++)
            if(f[i]==0)
            ans++;
            cout<<ans;}
        return 0;
    }

\*\****6，基础训练—数的读法***

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70]: /images/20221024/3bfbfb2b63854dc29346d69c385628c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70 1]: /images/20221024/ef1ae2b7714a4cc19c86bd97867ffae1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70 2]: /images/20221024/8b169c2a204d47378b642d047e23c096.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70 3]: /images/20221024/47ec3f431335428699b876397a16917e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70 4]: /images/20221024/6b8514ea91aa48ebb5bdad488761519f.png