Yokohama 2018

题目链接

Yokohama 2018

C - Emergency Evacuation

思路

先计算出每个人到出口的时间，肯定会有同步的，例如下列情况

10s 10
15s 10

就是10s 的时候有10个人到达出口，15s的时候有10个人到达出口，就需要排队，10s+10s+10s=30s可以全部走完，模拟一下上述过程，算出来就是答案。坑点就是数据很小，在误导你暴力QaQ

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
map<int,int>mp; 
int main(){
	int r,s,p;
	int mx=0;
	scanf("%d %d %d",&r,&s,&p);
	for(int i=0;i<p;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		
		int step;
		if(y>s){
			 step = r+1-x+y-s;
		}else{
			step = r+1-x+s-y+1;
		}
		mp[step]++;
	}
	for(auto k:mp){
		mx=max(k.first+k.second-1,mx+k.second);
	}
	printf("%d",mx);
}

G What Goes Up Must Come Down

思路

可以从最大的那个数分成两个区间，我们考虑一个数应该在做区间还是在右区间，显然，在左区间的贡献相当于左边比它大的数的个数，在右区间的贡献相当与右边比它大的个数，然后用树状数组维护一波，就可以了

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int arr[N];
int mx[N],mi[N];
int lowbit(int x){
	return x&(-x);
} 
int a[N],c[N]; //对应原数组和树状数组
void updata(int i,int k){    //在i位置加上k
    while(i < N){
        c[i] += k;
        i += lowbit(i);
    }
}
int getsum(int i){        //求A[1 - i]的和
    int res = 0;
    while(i > 0){
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&arr[i]);
		updata(arr[i],1);
		mi[i]=getsum(10001)-getsum(arr[i]);
	}
	memset(a,0,sizeof(a));
	memset(c,0,sizeof(c));
	for(int i=n-1;i>=0;i--){
		updata(arr[i],1);
		mx[i]=getsum(10001)-getsum(arr[i]);
	}
	ll ans = 0;
	for(int i=0;i<n;i++)ans+=min(mi[i],mx[i]);
	printf("%lld\n",ans);
}

K Sixth Sense

思路

很显然的一点就是我们能够预处理处最大的数目，排序后$O(nlogn)$贪心找就可以了，问题在于如何找到字典序最大，这里我们先处理出最大胜利局数$ans$。
我们枚举每一个a[i],我们可以选择获胜或者失败，当然能获胜肯定选择获胜，因为获胜的字典序肯定大于失败，所以我们就先考虑获胜的情况，从b[]数组找出中枚举出比a[i]大的数组成bb数组。
接下来考虑我们要取bb数组中的那个值能成功？因为我们知道了胜利的局数，如果这一局胜利的话，只需要剩下的牌能够使得剩下的$a[i+1]~a[n]$胜利$ans-1$局就好了。现在我们二分bb[]数组，从里面选出一个数，然后再判断能否成立，我们先给$a[i+1]~a[n]$排序$O(nlogn)$,然后再在二分中O(n)的找出最大局数就好了，这个时间复杂度是$O(n^2logn)$。
然后考虑不成功的情况，不成功的话从b数组中找出比a[i]小的数组成bb数组，然后类似刚才，一样是选最大的，但是获胜的局数就是ans了，因为这局输了。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 5e3+10;
vector<int>a,b,res;
int aa[N],bb[N];
bool check(int k,int lim){
	int res=0,j=0;
	while(res<lim&&j<lim){
		if(bb[j]>aa[res])res++;
		j++;
	}
	return res>=k;
}
int main(){
	int n,x;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&aa[i]),a.push_back(aa[i]);
	for(int i=0;i<n;i++)scanf("%d",&bb[i]),b.push_back(bb[i]);
	sort(aa,aa+n);
	sort(bb,bb+n);
	sort(b.begin(),b.end());
	int ans = 0,dn =0;
	while(ans<n&&dn<n){
		if(bb[dn]>aa[ans])ans++;
		dn++;
	}
	for(int i=0;i<n;i++){
		int pos = -1;
		int blen=upper_bound(b.begin(),b.end(),a[i])-b.begin();
		int aj=0;
		for(int j=i+1;j<n;j++)aa[aj++]=a[j];
		sort(aa,aa+aj);
		int l=blen,r=b.size()-1;
		while(l<=r){
			int mid = l+r>>1;
			int bj=0;
			for(int j=0;j<b.size();j++){if(j!=mid)bb[bj++]=b[j];}
			if(check(ans-1,bj)){
				pos=mid;
				l=mid+1;
			}else r=mid-1;
		}
		if(pos!=-1)ans--;
		else{
			l=0;
			r=blen-1;
		    while(l<=r){
			int mid = l+r>>1;
			int bj=0;
			for(int j=0;j<blen;j++)if(j!=mid)bb[bj++]=b[j];
			if(check(ans,bj)){
				pos=mid;
				l=mid+1;
			}else r=mid-1;
		}
		}
		res.push_back(b[pos]);
		b.erase(b.begin()+pos);
	}
	for(auto k : res){
		printf("%d ",k);
	}
}