Codeforces Round #599解题报告

全绿的第一场
不好意思说是题解 就解题报告吧
(天哪稳赚终于更博了

先反思一下 B这个傻逼暴力场上没调出来 真的弟弟
这场+11 我什么时候上蓝啊555
贪心场√

A: Payment Without Change

题目链接
题意:有a个n b个1 问能不能凑到s
以为会炸int 赛后想了想好像也不会233

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define sc(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
using namespace std;
typedef long long ll;
ll a,b,n,s;
int solve(){
if(a*n+b<s) return puts("NO"),0;
int x=min(a,s/n);
if(x*n+b>=s) return puts("YES"),0;
else return puts("NO"),0;
}
int main(){
int _; sc(_); while(_--){
scl(a); scl(b); scl(n); scl(s);
solve();
}
}

B: Minimize the Permutation

题目链接
题意:给定一个1~n的排列 要操作最多n-1次相邻位交换且每个位置只能交换一次 使最终结果序列字典序最小 输出此序列
暴力莽 写得有点丑 一个活脱脱的>号
我开始压行后就没写过这么丑的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
int a[105],v[105];
int main(){
int _; sc(_); while(_--){
int n; sc(n); rep(i,1,n+1) sc(a[i]),v[i]=0;
int c(0);
rep(i,1,n+1){
rep(j,1,n+1){
if(a[j]==i){
int k=j;
while(k>1){
if(v[k]) break;
if(a[k]<a[k-1]){
swap(a[k],a[k-1]);
c++; v[k]++;
}
else break; k--;
}
break;
}
}
if(c==n) break;
}
rep(i,1,n+1) pf("%d ",a[i]);
pf("\n");
}
}

C: Platforms Jumping

题目链接
题意:一道河长n 有m个木板 第i个木板长c[i] 人一次可以跳d格 问这个人能否过河 能的话输出方案
贪心 判完YES后先让这个人一直跳尽量远

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
int a[1005],s;
int main(){
int n,m,k; sc(n); sc(m); sc(k);
rep(i,1,m+1) sc(a[i]),s+=a[i];
if(n-s>(m+1)*(k-1)) pf("NO\n");
else{
int n1=n;
pf("YES\n");
n-=s; n++;
rep(i,1,m+2){
int t=min(k,n);
rep(j,0,t-1) pf("0 ");
rep(j,0,a[i]) pf("%d ",i);
n-=t-1;
}
}
}

D: Binary String Minimizing

题目链接
题意:给定一个长度为n的01串 问交换最多k次后字典序最小的串是什么
贪心 直接for一遍 不过还是写麻烦了233
k没开ll wa了一次 qswl

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", &x)
#define scl(x) scanf("%lld", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
char s[maxn];
vector<int>v;
int main(){
int _; sc(_); while(_--){
int n; ll k; sc(n); scl(k); scs(s); v.clear();
rep(i,0,n) if(s[i]=='0') v.push_back(i);
int pos(0);
rep(i,0,n) if(s[i]=='0') pos++; else break;
rep(i,0,v.size()){
if(v[i]<pos) continue;
int t=min(1ll*v[i]-1ll*pos,k);
if(t<k) swap(s[v[i]],s[pos]);
else swap(s[v[i]],s[v[i]-k]);
k-=t; pos++;
if(k<=0) break;
}
pf("%s\n",s);
}
}

E: Yet Another Division Into Teams

题目链接
题意:n个人每个人能力为a[i] 一个队的差距指最大值减最小值 要把这些人划分成k个至少3人的队 希望每个队差异总和最小 求总和 队数 成员划分
是个dp 我看题解写的呜呜呜 没什么好说的 官方题解更好懂 wtcl

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
#define pf printf
#define INF 0x3f3f3f3f
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
const int maxn = 2e5 + 5;
pair<int,int>a[maxn];
int dp[maxn],t[maxn],r[maxn];
int main(){
int n,cnt(0); sc(n);
rep(i,0,n) sc(a[i].first),a[i].second=i;
sort(a,a+n); rep(i,1,n+1) dp[i]=INF;
rep(i,0,n) rep(j,3,6){
if(i+j>n) break;
if(dp[i+j]>dp[i]+a[i+j-1].first-a[i].first){
dp[i+j]=dp[i]+a[i+j-1].first-a[i].first;
r[i+j]=i;
}
}
int now=n;
while(now){
dep(i,now-1,r[now]) t[a[i].second]=cnt;
cnt++; now=r[now];
}
pf("%d %d\n",dp[n],cnt);
rep(i,0,n) pf("%d ",t[i]+1); pf("\n");
}

F: Equalizing Two Strings

题目链接
题意:给定串s和t 每次可以在s和t中翻转长度相同的子串 问是否有可能使s和t相同
问施老师的 11-nb!
翻转长度为len的区间可以等价为多次相邻交换 将字符串换成递增的 需要逆序对次 如果逆序对数相同或者差为偶数(换两次等同于不变)则可以 如果有一个串的字母有两个以上 这就可以和这个字母不受限地交换 所以也可以
啊我说的啥啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
const int maxn = 2e5 + 5;
int n,c[30],d[30];
char s[maxn],t[maxn];
int solve(){
int t1(0),t2(0);
rep(i,0,n){
c[s[i]-'a']++,d[t[i]-'a']++;
rep(j,s[i]-'a'+1,26) t1+=c[j];
rep(j,t[i]-'a'+1,26) t2+=d[j];
}
rep(i,0,26) if(c[i]!=d[i]) return 0;
rep(i,0,26) if(c[i]>=2||d[i]>=2) return 1;
return (t1-t2)%2==0;
}
int main(){
int _; sc(_); while(_--){
sc(n); scs(s); scs(t);
mst(c,0); mst(d,0);
if(solve()) puts("YES"); else puts("NO");
}
}