GMPCP 粤澳正式赛

小灰灰 2023-03-12 12:12 6阅读 0赞

# 总共20题 #

# 官方题解 #

## A题：[Alice的秘密][Alice] ##

**AC代码**

#include<bits/stdc++.h>
    using namespace std;
    
    int isDate(int year, int month, int day)
    { 
    	if(year>2020 || year<1900) return 0;
    	if(month>12 || month<1) return 0;
    	if(month==1||month==3||month==5||month==7||month==8||month==10||month==12){ 
    		return (day>=1&&day<=31);
    	}
    	if(month==4||month==6||month==9||month==11) { 
    		return (day>=1&&day<=30);
    	}
    	if((year%4==0&&year%100!=0)||(year%400==0)){ 
    		return (day>=1&&day<=29);
    	}
    	return day>=1&&day<=28;
    }
    
    int getK(char *date)
    { 
    	if(strlen(date)!=8) return 0;
    	int d[8];
    	for(int i=0; i<8; i++){ 
    		if(date[i]>'9'||date[i]<'0') return 0;
    		d[i] = date[i]-'0';
    	}
    	int year = d[0]*1000 + d[1]*100 + d[2]*10 + d[3];
    	int month = d[4]*10 + d[5];
    	int day = d[6]*10 + d[7];
    	if(!isDate(year, month, day)) return 0;
    	int k=0;
    	for(int i=0; i<8; i++){ 
    		k += d[i];
    	}
    	while(k>9){ 
    		int sum = k;
    		k = 0;
    		while(sum>0){ 
    			k+=sum%10;
    			sum/=10;
    		}
    	}
    	return k;
    }
    
    int isMsg(char *msg)
    { 
    	int i=0;
    	while(msg[i]!='\0'){ 
    		if(!((msg[i]==' ') || (msg[i]<='z'&&msg[i]>='a') || (msg[i]<='Z'&&msg[i]>='A')))
    			return 0;
    		i++;
    	}
    	return 1;
    }
    
    void printMsg(char *msg, int k)
    { 
    	int i=0;
    	while(msg[i]!='\0'){ 
    		if(msg[i]==' ') printf("#");
    		else{ 
    			if(msg[i]>='a'&&msg[i]<='z')
    			printf("%c", (msg[i]+k-'a')%26+'a');
    			else printf("%c", (msg[i]+k-'A')%26+'A');
    		}
    		i++;
    	}
    	printf("\n");
    }
    
    int main()
    { 
    	char date[10];
    	char msg[132];
    	while(gets(date)!=NULL){ 
    		gets(msg)!=NULL;
    		int k = getK(date);
    		if(k==0 || !isMsg(msg)) printf("none\n");
    		else{ 
    			printMsg(msg, k);
    		}
    	}
    	return 0;
    }

全 C 语言代码，学到了合法日期的表达方法，还有题目还要判断信息合法性

## B题：[今天星期几][Link 1] ##

**AC代码**

#include<stdio.h>
    
    int isLeap(int year){ 
    	return (year%4==0&&year%100!=0)||(year%400==0);
    }
    
    int daysInMonth(int year, int month){ 
    	switch(month){ 
    		case 1: return 31;
    		case 2: if(isLeap(year)) return 29;
    		else return 28;
    		case 3: return 31;
    		case 4: return 30;
    		case 5: return 31;
    		case 6: return 30;
    		case 7: return 31;
    		case 8: return 31;
    		case 9: return 30;
    		case 10: return 31;
    		case 11: return 30;
    		case 12: return 31;
    	}
    }
    
    int main(){ 
    	int year, month, day, sum=0;
    	while(~scanf("%d %d %d", &year, &month, &day)){ 
    		sum = 0;
    		for(int y=2000; y<year; y++){ 
    			if(isLeap(y)) sum+=366;
    			else sum+=365;
    		}
    		for(int m=1; m<month; m++){ 
    			sum += daysInMonth(year, m);
    		}
    		for(int d=1; d<day; d++){ 
    			sum++;
    		}
    		printf("%d %d\n", sum/4+1, sum%4+1);   //表达第几天的方式是: 模4加1
    	}
    	return 0;
    }

加天数的函数有用到 switch 很秀，学到了

## C题：[小明的英文作业][Link 2] ##

**AC代码**

#include<stdio.h>
    #include<string.h>
    #include<string>
    #include<map>
    using namespace std;
    int main(){ 
    	char *cp, line[2200], word[24];
    	while(gets(line)){ 
    		int sum = 0;
    		if(line[0] == '#') break;
    		else{ 
    			map<string, int> m;
    			cp = line;
    			while(*cp!='\0'){ 
    				int i = 0;
    				while(*cp !=' '&& *cp!='\0'){ 
    					word[i] = *cp;
    					i++;
    					cp++;
    				}
    				if (*cp==' ') cp++;
    				word[i] = '\0';
    				m[word]++;  //map还可以这样用 
    				sum++;
    			}
    			int count = 0;
    			map<string,int> ::iterator it;
    			for(it=m.begin(); it!=m.end(); it++){ 
    				if(it->second==1) count++;  //只出现1次的单词不能少于全部单词的一半 
    			}
    			if(count*2>=sum) printf("yes\n");
    			else printf("no\n");
    		}
    	}
    	return 0;
    }

指针 cp 代替数组下标判断字符的用法很秀，学到了

## D题：[分三排][Link 3] ##

**简单题，略**

## E题：[击中目标][Link 4] ##

**变态题，略**

## F题：[序列计数][Link 5] ##

**变态题，略**

## G题：[强迫症][Link 6] ##

**AC代码**

#include <iostream >
    using namespace std;
    int main()
    { 
    	int n = 0;
    	int a;
    	cin >> n;
    	cin >> a;
    	int repeat_element = a;
    	int count = 1;
    	for(int i = 1; i < n; i++)
    	{ 
    		cin >> a;
    		if(count == 0)
    		{ 
    			repeat_element = a;
    		}
    		if( repeat_element == a)
    			count ++;
    		else
    			count --;
    	}
    	cout << repeat_element ;
    	return 0;
    }

重复元素大于一半，可以采用投票法，不需要排序，很强的方法

## H题：[新型冠状爱情病毒][Link 7] ##

**变态题，略**

## I题：[期末表彰][Link 8] ##

**简单题，略**

## J题：[最小特征][Link 9] ##

**AC代码**

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    char c[10];
    ll ans,ans1,ans2,ans3;
    ll lg[10];
    
    ll pd(){ 
        ll x=0;
        for(int k=1;k<=8;k++){ 
            x+= ( (c[9]-'0')^(c[k]-'0') )*lg[8-k];
        }
        return x;
    }
    
    int main(){ 
        ll n; cin>>n;
        lg[0]=1;
        for(int i=1;i<=10;i++) lg[i]=lg[i-1]*2;  //以这种方式存储 2的次方会快一点 
        while(n--){ 
            ans=ans1=ans2=ans3=0;
            cin>>c[1]>>c[2]>>c[3]>>c[8]>>c[9]>>c[4]>>c[7]>>c[6]>>c[5];
            ans=pd();
            swap(c[3],c[5]); swap(c[3],c[7]); swap(c[1],c[3]);
            swap(c[2],c[4]); swap(c[2],c[6]); swap(c[2],c[8]);
            ans1=pd();
            swap(c[3],c[5]); swap(c[3],c[7]); swap(c[1],c[3]);
            swap(c[2],c[4]); swap(c[2],c[6]); swap(c[2],c[8]);
            ans2=pd();
            swap(c[3],c[5]); swap(c[3],c[7]); swap(c[1],c[3]);
            swap(c[2],c[4]); swap(c[2],c[6]); swap(c[2],c[8]);
            ans3=pd();
            ans=min(ans,ans1); ans=min(ans,ans2); ans=min(ans,ans3);
            cout<<ans<<endl;
        }
        return 0;
    }

## K题：[项目管理][Link 10] ##

**AC代码：**

#include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int manx=1e6+5;
    struct node{ 
        ll x,y;
    }a[manx];
    bool cmp(node a,node b){ 
        return a.y>b.y;
    }
    
    int main(){ 
        ll n; cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i].x>>a[i].y;
        ll ans=0,cnt=0;
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++){ 
            cnt+=a[i].x;
            ans=max(ans,cnt+a[i].y);  //学生同时执行他们项目的最长时间 
        }
        cout<<"Project "<<n<<": "<<ans<<endl;
        return 0;
    }

贪心，把用时间长的安排在前面，这样在他在工作的时间可以去给其他人安排

## L题：[捕鱼达人][Link 11] ##

**提升题，略**

## M题：[排除危险][Link 12] ##

**AC代码**

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll cnt;
    map<ll,ll>vis;
    
    int main(){ 
        ll x,y; ll ans=0,res=0,n=0;
        while(cin>>x){ 
            if(x==-1) break;
            cin>>y;
            n++;
            res=0;
            if(vis[x]==0) res++; vis[x]++;
            if(vis[y]==0) res++; vis[y]++;
            ans++; cnt+=res;
            if(ans==cnt){ 
                ans--; cnt-=res;
                vis[x]--; vis[y]--;
            }
         // cout<<ans<<" "<<cnt<<endl<<endl;
        }
        cout<<n-ans<<endl;
        return 0;
    }

根据题意模拟就可以，让化学物品ans！=元素种类cnt

## N题：[图像编码问题][Link 13] ##

**AC代码**

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int manx=1e6+5;
    
    struct node{ 
        ll x,val;
    }a[manx];
    ll k=0;
    bool cmp(node a,node b){ 
        return a.val<b.val;
    }
    
    void pd(ll l,ll r){ 
        string sl="",sr="";
        do{ 
            if(l&1) sl+="1";
            else sl+="0";
            l>>=1;
        }while(l);
        do{ 
            if(r&1) sr+="1";
            else sr+="0";
            r>>=1;
        }while(r);
        while(sl.size()<sr.size()) sl+="0";
        while(sr.size()<sl.size()) sr+="0";
        reverse(sl.begin(),sl.end());
        reverse(sr.begin(),sr.end());
        string s="";
        for(int i=0;i<sl.size();i++)
            s+=sl[i],s+=sr[i];
        s.erase(0,s.find_first_not_of('0'));
        ll x=1,ans=0;
        if(s.size()==0){ 
             a[k].val=ans;
             return;
        }
        for(int i=s.size()-1;i>=0;i--){ 
            if(s[i]=='1') ans+=x;
            x*=2;
        }
        a[k].val=ans;
    }
    
    int main(){ 
        ll n; cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){ 
                cin>>a[++k].x;
                pd(i-1,j-1);
            }
        sort(a+1,a+1+k,cmp);
        for(int i=1;i<=k;i++){ 
            ll cnt=1,p=i+1;
            while(p<=k&&a[i].x==a[p].x) cnt++,p++;  //这种写法还挺常见的
            if(p!=k+1&&i!=k) cout<<a[i].x<<","<<cnt<<" ";
            else  cout<<a[i].x<<","<<cnt;
            i=i+cnt-1;
        }
        return 0;
    }

## O题：[军训值日生][Link 14] ##

**提升题，略**

## P题：[今天图书馆开了没？][Link 15] ##

**AC代码**

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int manx=1e6+5;
    ll a[manx][5],dp[manx][5];
    int main(){ 
        ll n; cin>>n;
        for(int i=1;i<=n;i++){ 
           for(int j=1;j<=4;j++) cin>>a[i][j];
        }
        for(int j=1;j<=4;j++) dp[1][j]=a[1][j];
        for(int i=2;i<=n;i++){ 
            for(int j=1;j<=4;j++){ 
                if(a[i][j])
                    for(int k=1;k<=4;k++){ 
                        if(j==k&&a[i-1][j]) dp[i][j]=max(dp[i][j],dp[i-1][k]);
                        else dp[i][j]=max(dp[i][j],dp[i-1][k]+1);
                    }
                else
    				for(int k=1;k<=4;k++)
    					dp[i][j]=max(dp[i][j],dp[i-1][k]);
            }
        }
        ll ans=0;
        for(int i=1;i<=4;i++)
            ans=max(ans,dp[n][i]);
        cout<<ans<<endl;
        return 0;
    }

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

## Q题：[小明的体育课][Link 16] ##

**简单题，略**

## R题：[孤独的字符串][Link 17] ##

**提升题，略**

## S题：[鲍勃的输入法][Link 18] ##

**变态题，略**

## T题：[一起做课件][Link 19] ##

**变态题，略**

[Alice]: https://oj.bnuz.edu.cn/contest/22/problems/145/content
[Link 1]: https://oj.bnuz.edu.cn/contest/22/problems/143/content
[Link 2]: https://oj.bnuz.edu.cn/contest/22/problems/154/content
[Link 3]: https://oj.bnuz.edu.cn/contest/22/problems/135/content
[Link 4]: https://oj.bnuz.edu.cn/contest/22/problems/141/content
[Link 5]: https://oj.bnuz.edu.cn/contest/22/problems/147/content
[Link 6]: https://oj.bnuz.edu.cn/contest/22/problems/136/content
[Link 7]: https://oj.bnuz.edu.cn/contest/22/problems/152/content
[Link 8]: https://oj.bnuz.edu.cn/contest/22/problems/137/content
[Link 9]: https://oj.bnuz.edu.cn/contest/22/problems/140/content
[Link 10]: https://oj.bnuz.edu.cn/contest/22/problems/138/content
[Link 11]: https://oj.bnuz.edu.cn/contest/22/problems/151/content
[Link 12]: https://oj.bnuz.edu.cn/contest/22/problems/139/content
[Link 13]: https://oj.bnuz.edu.cn/contest/22/problems/142/content
[Link 14]: https://oj.bnuz.edu.cn/contest/22/problems/144/content
[Link 15]: https://oj.bnuz.edu.cn/contest/22/problems/149/content
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70]: /images/20230312/594c816710b740fcaabc8e16abaf7852.png
[Link 16]: https://oj.bnuz.edu.cn/contest/22/problems/153/content
[Link 17]: https://oj.bnuz.edu.cn/contest/22/problems/148/content
[Link 18]: https://oj.bnuz.edu.cn/contest/22/problems/150/content
[Link 19]: https://oj.bnuz.edu.cn/contest/22/problems/146/content