Codeforces Round #723 (Div. 2) 部分题解
Codeforces Round #723 (Div. 2) 部分题解
一发过了 D ，nice
A
思维题，注意到排序后，将 an+i 插入到 ai 前即可。
#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! 枚举排列，然后统计逆序对即可。
#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