阅读 169

Codeforces Round #723 (Div. 2) 部分题解

Codeforces Round #723 (Div. 2) 部分题解

一发过了 D ,nice

A

思维题,注意到排序后,将 an+ian+i 插入到 aiai 前即可。

#pragma GCC optimize("O3")#include<bits/stdc++.h>using namespace std;#define endl '\n'#define debug(x) cerr << #x << ": " << x << endl#define pb(a) push_back(a)#define set0(a) memset(a,0,sizeof(a))#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define dwn(i,a,b) for(int i=(a);i>=(b);i--)#define ceil(a,b) (a+(b-1))/b#define INF 0x3f3f3f3f#define ll_INF 0x7f7f7f7f7f7f7f7ftypedef long long ll;typedef pair<int,int> PII;typedef pair<double,double> PDD;inline int read(){	int x=0,y=1;char c=getchar();	while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();	return x*y;
}int a[30];int main(){	int T; cin>>T;	while(T--){		int n; cin>>n;
		rep(i,1,2*n) cin>>a[i];
		
		sort(a+1, a+1+2*n);
		
		rep(i,1,n) cout<<a[i]<<' '<<a[i+n]<<' ';		cout<<endl;
	}    return 0;
}

B

分析:数学题,推推柿子即可

#pragma GCC optimize("O3")#include<bits/stdc++.h>using namespace std;#define endl '\n'#define debug(x) cerr << #x << ": " << x << endl#define pb(a) push_back(a)#define set0(a) memset(a,0,sizeof(a))#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define dwn(i,a,b) for(int i=(a);i>=(b);i--)#define ceil(a,b) (a+(b-1))/b#define INF 0x3f3f3f3f#define ll_INF 0x7f7f7f7f7f7f7f7ftypedef long long ll;typedef pair<int,int> PII;typedef pair<double,double> PDD;inline int read(){	int x=0,y=1;char c=getchar();	while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();	return x*y;
}int main(){	int T; cin>>T;	while(T--){		int x; cin>>x;		int r=x%11;		if(!r) puts("YES");		else{
			x-=r*111;			if(x<0) puts("NO");			else if(x==0) puts("YES");			else{				if(x%11==0) puts("YES");				else puts("NO");
			}
		}
	}    return 0;
}

C

反悔贪心
细节见代码:

#pragma GCC optimize("O3")#include<bits/stdc++.h>using namespace std;#define endl '\n'#define debug(x) cerr << #x << ": " << x << endl#define pb(a) push_back(a)#define set0(a) memset(a,0,sizeof(a))#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define dwn(i,a,b) for(int i=(a);i>=(b);i--)#define ceil(a,b) (a+(b-1))/b#define INF 0x3f3f3f3f#define ll_INF 0x7f7f7f7f7f7f7f7ftypedef long long ll;typedef pair<int,int> PII;typedef pair<double,double> PDD;inline void read(int &x) {    int s=0;x=1;    char ch=getchar();    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}int main(){	int n; cin>>n;	priority_queue<ll, vector<ll>, greater<ll>> pq;
	
	ll cur=0;
	rep(i,1,n){
		ll x; cin>>x;
		pq.push(x), cur+=x;		
		while(cur<0 && pq.size()){
			cur-=pq.top();
			pq.pop();
		}
	}	cout<<pq.size()<<endl;	
    return 0;
}

D

发现相同的字母总是连在一起能得到最优解,所以暴力 4!4! 枚举排列,然后统计逆序对即可。

#pragma GCC optimize("O3")#include<bits/stdc++.h>using namespace std;#define endl '\n'#define debug(x) cerr << #x << ": " << x << endl#define pb(a) push_back(a)#define set0(a) memset(a,0,sizeof(a))#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define dwn(i,a,b) for(int i=(a);i>=(b);i--)#define ceil(a,b) (a+(b-1))/b#define INF 0x3f3f3f3f#define ll_INF 0x7f7f7f7f7f7f7f7ftypedef long long ll;typedef pair<int,int> PII;typedef pair<double,double> PDD;inline void read(int &x) {    int s=0;x=1;    char ch=getchar();    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}const int N=2e5+5;int a[5], cnt[5];int w[N], tmp[N];

ll d;void cdq(int l, int r){	if(l>=r) return;	int mid=l+r>>1;
	cdq(l, mid), cdq(mid+1, r);
	
	ll sum=0;	for(int j=l, i=mid+1, k=l;k<=r;k++)		if(i>r || j<=mid && w[i]>w[j]) sum++, tmp[k]=w[j++]; // 如果说右区间的指针已经走到边界,或者左区间的b值比较小。
		else d+=sum, tmp[k]=w[i++];	
	for(int k=l;k<=r;k++) w[k]=tmp[k];  // 完成排序,复制}int main(){	int T; cin>>T;	while(T--){
		set0(cnt);		string s; cin>>s;		for(auto i: s)			if(i=='A') cnt[1]++;			else if(i=='T') cnt[2]++;			else if(i=='N') cnt[3]++;			else if(i=='O') cnt[4]++;
			
		rep(i,1,4) a[i]=i;		
		int k=0;
		ll dis=1e18;		int kt;		do{
			k++;			string cur;			
			vector<int> va, vt, vn, vo;
			rep(i,0,s.size()-1)				if(s[i]=='A') va.pb(i);				else if(s[i]=='T') vt.pb(i);				else if(s[i]=='N') vn.pb(i);				else if(s[i]=='O') vo.pb(i);
		
			d=0;			int tot=0;
			rep(i,1,4)				if(a[i]==1){					for(auto o: va) w[++tot]=o;
				}				else if(a[i]==2){					for(auto o: vt) w[++tot]=o;
				}				else if(a[i]==3){					for(auto o: vn) w[++tot]=o;
				}				else if(a[i]==4){					for(auto o: vo) w[++tot]=o;
				}
			
			cdq(1, s.size());			if(d<dis) dis=d, kt=k;
		}while(next_permutation(a+1, a+1+4));		
		// debug(kt);
		rep(i,1,4) a[i]=i;		
		int kth=0;		do{
			kth++;			if(kth==kt){				// output ans
				string cur;
				rep(i,1,4) rep(j,1,cnt[a[i]]){					if(a[i]==1) cur+='A';					else if(a[i]==2) cur+='T';					else if(a[i]==3) cur+='N';					else if(a[i]==4) cur+='O';
				}				cout<<cur<<endl;				break;
			}
		}while(next_permutation(a+1, a+1+4));
	}    return 0;
}


__EOF__

本文作者HinanawiTenshi
本文链接:https://www.cnblogs.com/Tenshi/p/14826002.html


文章分类
后端
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐