Codeforces Round #402 (Div. 2) （A-D）

客官°小女子只卖身不卖艺 2022-07-12 15:16 188阅读 0赞

[CF \#402 div2][CF _402 div2]

A题：

数学。具体看代码吧。很容易明白的。

#include<bits/stdc++.h>
    using namespace std;
    int a[6],b[6];
    int main()
    {
        int n, x, y;
        cin>>n;
        if(n==1){
            cin>>x>>y;
            if(x==y) printf("0\n");
            else printf("-1\n");
            return 0;
        }
        int count_a=0;
    	int count_b=0;
        for(int i=0; i<n; i++){
           cin>>x;
           a[x]++;
        }
        for(int i=0; i<n; i++){
            cin>>y;
            b[y]++;
        }
        for(int i=1; i<=5; i++){
            if((a[i]+b[i])%2==0){
                if(a[i]>b[i])   count_a += (a[i]-b[i])/2;
                else if(a[i]<b[i]) count_b += (b[i]-a[i])/2;
            }
            else{
                return 0*printf("-1\n"); 
            }
        }
        cout<<count_a<<endl;    
        return 0;
    }

B题：

贪心。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int main()
    {
        string s;
        int k;
        cin>>s>>k;
        ll n=atoi(s.c_str());
        if(n % ((ll)pow(10,k))==0)return 0*printf("0");
        int count = 0;
        for(int i= 0;i < s.length(); i++)
        {
        	if(s[i]=='0')count++;
    	}
    	int ans=0;
    	if(count >= k)
    	{
    		int count_0 = 0;
    		for(int i = s.length()-1; i>=0;--i)
    		{
    			if(s[i]=='0'){
    				count_0++;
    				if(count_0 == k)
    				return 0*printf("%d\n",ans);
    			}
    			else ans++;
    		}
    	}
    	cout<<s.length()-1<<endl;
        return 0;
    }

C题：

贪心。

代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    struct Price
    {
    	int a,b,c;
    }price[200010];
    int cmp(const Price &a, const Price &b)
    {
    	return a.c < b.c;
    }
    int main()
    {
        int n,k;
        int ans=0;
        cin>>n>>k;
        for(int i=0;i<n;i++){
        	cin>>price[i].a;
    	}
    	for(int i=0;i<n;i++){
    		cin>>price[i].b;
    	}
    	for(int i=0;i<n;i++){
    		price[i].c = price[i].a - price[i].b;
    	}
    	sort(price,price+n,cmp);
    	for(int i = 0; i < k;i++){
    		ans += price[i].a;
    	}
    	for(int i = k; i < n; i++){
    		if(price[i].c < 0) ans += price[i].a;
    		else ans += price[i].b;
    	}
    	cout<<ans<<endl;
        return 0;
    }

D题：

二分。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int a[200010];
    string s,p;
    int check(int n)
    {
        string tmp=s;
        for (int i=0; i<n; i++)
        {
            tmp[a[i] - 1] = '*';
        }
        int i=0,j=0;
        while (i < s.length() && j < p.length() )
        {
            if (tmp[i] != p[j]) i++;
            else{
                i++;
                j++;
            }
        }
        if(j==p.length())return 1;
        else return 0;
    }
    
    int main()
    {
        cin>>s>>p;
        for (int i = 0; i < s.length(); i++) cin>>a[i];
       	int l=0;
    	int r=s.length()-1;
        int ans=0;
        while (l<=r)
        {
            int mid = (l+r)>>1;
            if (check(mid)){
                ans = mid;
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        cout<<ans<<endl;
        return 0;
    }

[CF _402 div2]: http://codeforces.com/contest/779