A.Grass Field

原题链接

水题，分类讨论。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>

using namespace std;

int t,a,b,c,d;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>a>>b>>c>>d;
        if(!(a|b|c|d))cout<<0<<'\n';
        else if(a&b&c&d)cout<<2<<'\n';
        else cout<<1<<'\n';
    }
}

B.Permutation

原题链接

显然 d 为 $ 2 $ ，时花费最大，接下来按这来排即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int N=2e5+10;
int t,n;
bool v[N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        memset(v,0,sizeof v);
        cin>>n;
        cout<<2<<'\n';
        for(int i=1;i<=n;i++){
            if(v[i]) continue;
            for(int j=i;j<=n;j<<=1){
                if(v[j]) continue;
                cout<<j<<' ';
                v[j]=1;
            }
        }
        cout<<'\n';
    }
}

C.Schedule Management

原题链接

二分答案。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=2e5+10;

int t,n,m,x;

int a[N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        memset(a,0,sizeof a);
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            cin>>x;
            a[x]++;
        }
        int l=0,r=m*2;
        while(l<r){
            int mid=(l+r)>>1;
            long long sum=0;
            for(int i=1;i<=n;i++){
                if(a[i]>mid){
                    sum+=a[i]-mid;
                }
                else{
                    sum-=(mid-a[i])/2;
                }
            }
            if(sum>0) l=mid+1;
            else r=mid;
        }
        cout<<l<<'\n';
    }
}

D. Permutation Restoration

一个还算得上简单的贪心，至少我是能想到的。

#include <bits/stdc++.h>
#define PII pair<int,int>

using namespace std;
int t,n;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n;
		vector<int> a(n),b(n);
		vector<PII> v(n);
		set<PII> s;
		for(int i=0;i<n;i++){
			cin>>a[i];
			v[i]={(i+1)/(a[i]+1)+1,i};
		}
		sort(v.begin(),v.end());
		int j=0;
		for(int i=0;i<n;i++){
			while(j<n&&v[j].first==i+1){
				int id=v[j++].second;
				s.insert({a[id]?(id+1)/a[id]:n,id});
			}
			b[s.begin()->second]=i+1;
			s.erase(s.begin());
		}
		for(int i=0;i<n;i++){
			cout<<b[i]<<' ';
		}
		cout<<'\n';
	}
}