The 19th Zhejiang University Programming Contest Sponsored by TuSimple(浙大校赛)

柔情只为你懂 2022-04-24 03:22 136阅读 0赞

这次团队总共出了A,E,G,J这四道题，有种打CF的感觉。

## [A .Thanks, TuSimple!][A .Thanks_ TuSimple] ##

**题意：**有n位男士，m位女士，他们要去参加舞会，选择舞伴时，他们各自都有自己的要求，1表示倾向于找比自己高的舞伴，0表示倾向于找比自己矮的舞伴。问：最多有多少对舞伴可以组队成功？

**思路：**一开始我就想，这不就二分图匹配嘛？！ 和队友商量了下，队友感觉也像二分图匹配，然后我就拿着自己的小模板往上抄，抄着发现，时间复杂度是不是炸了。啊~不管了，没有其他思路，继续抄。弄完，输入样例，结果正确。造几组样例，通过。提交，TL,QWQ。之后，队友提出了一种新的想法，就是讲0,1单独讨论。也就是一个绅士要想选比自己矮点的舞伴，选择成功的话，选择的女性肯定是想选择比自己高点的舞伴。这个时候就可以让想选比自己矮点舞伴的绅士从矮到高站一排，让想选比自己高点舞伴的女士从矮到高站一排。（假如主动权在绅士手中）然后第一个绅士从第一个女性开始选择，判断是不是比自己矮，不是的话，换下一个女性选择，如果比自己矮，那就选她。下一个绅士从上一个绅士选的女士的下一个位置开始选择，步骤如上，如果找到最后一个女士也没有找到合适的，那么选择结束。最多也就只能选择这么多。

#include <bits/stdc++.h>
    
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+10;
    int n,m,p[maxn],q[maxn];
    ll a[maxn],b[maxn],a1[maxn],a0[maxn],b1[maxn],b0[maxn];
    
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&m);
            int ra0=0,ra1=0,rb0=0,rb1=0;
            for(int i=1;i<=n;i++){
                scanf("%lld",&a[i]);
            }
            for(int i=1;i<=m;i++){
                scanf("%lld",&b[i]);
            }
            for(int i=1;i<=n;i++){
                scanf("%d",&p[i]);
                if(p[i]==1) a1[ra1++]=a[i];
                else a0[ra0++]=a[i];
            }
            for(int i=1;i<=m;i++){
                scanf("%d",&q[i]);
                if(q[i]==1) b1[rb1++]=b[i];
                else b0[rb0++]=b[i];
            }
            
            int cnt=0,r;
            sort(a1,a1+ra1);
            sort(b0,b0+rb0);
            r=0;
            for(int i=0;i<ra1;i++){
            	while(r<rb0&&a1[i]>=b0[r]){
            		r++;
    			}
    			if(r>=rb0) break;
    			cnt++;
    			r++;
    		}
        
    		sort(b1,b1+rb1);
            sort(a0,a0+ra0);
            r=0;
            for(int i=0;i<rb1;i++){
            	while(r<ra0&&b1[i]>=a0[r]){
            		r++;
    			}
    			if(r>=ra0) break;
    			cnt++;
    			r++;
    		}
            printf("%d\n",cnt);
        }
        return 0;
    }

## [E.Potion][] ##

倒着推就成。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=110;
    typedef long long ll;
    ll a[maxn],b[maxn];
    
    ll sum;
    
    
    int main(){
        int t;
        scanf("%d",&t);
        while(t--){
            int n;
            scanf("%d",&n);
            for(int i=0;i<n;i++){
                scanf("%lld",&a[i]);
            }
            for(int i=0;i<n;i++){
                scanf("%lld",&b[i]);
            }
            bool flag=true;
            for(int i=n-1;i>=0;i--){
                    //printf("b[%d]=%lld,a[%d]=%lld\n",i,b[i],i,a[i]);
                if(b[i]>=a[i]){
                    if(i!=0) b[i-1]+=b[i]-a[i];
    
                }else{
                    flag=false;
                    break;
                }
            }
            if(flag) printf("Yes\n");
            else printf("No\n");
        }
    
        return 0;
    }

## [ G.Postman][G.Postman] ##

思路：保证离原点最远的点最后去送，去远的地方尽可能拿多点，顺便带给较远的地方，下次就不用跑这么远了。

下图，送快递的一个轨迹

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3Mjc1Njgw_size_16_color_FFFFFF_t_70][]

#include <bits/stdc++.h>
    
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+10;
    int a[maxn],b[maxn],c[maxn];
    int n,k;
    
    
    int main()
    {
    	
        int t;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&k);
            int lb=0,lc=0;
            for(int i=0;i<n;i++){
                scanf("%d",&a[i]);
                if(a[i]>0) b[lb++]=a[i];
                else c[lc++]=a[i]*(-1);
            }
            ll res=0;
        	sort(b,b+lb);
        	sort(c,c+lc);
    		for(int i=lc-1;i>=0;i-=k){
        		res+=2*c[i];
    		}
    		for(int i=lb-1;i>=0;i-=k){
        		res+=2*b[i];
    		}
        	if(b[lb-1]>c[lc-1]){
    			res-=b[lb-1];
    		}else{
    			res-=c[lc-1];
    		}
            
            printf("%lld\n",res);
        }
        return 0;
    }

## [J.Extended Twin Composite Number][] ##

题意:输入一个n，让你任意输出两个合数x,y,使得x+n=y.

思路：一开始我们就想输出2\*n,3\*n，起码x是3的倍数，y是4的倍数。然而n等于1不行，2和3都是素数。然后我们就改成输出9\*n，10\*n，9和10都是合数，也不怕n取1了。当然直接把1拎出来单独讨论也可。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    int main(){
    	int t;
    	ll n;
    	scanf("%d",&t);
    	while(t--){
    		scanf("%lld",&n);
    		printf("%lld %lld\n",9*n,10*n);
    	}
    	return 0;
    }

[A .Thanks_ TuSimple]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5979
[E.Potion]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5983
[G.Postman]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4096
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3Mjc1Njgw_size_16_color_FFFFFF_t_70]: /images/20220220/fccd15a1a30b4d12991d62e517f0bb36.png
[J.Extended Twin Composite Number]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5988