Codeforces Round #598解题报告

wenzhuan

发布于 2022-08-15 12:32:50

2190

发布于 2022-08-15 12:32:50

文章被收录于专栏：你会烧尽还是结冰

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

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

A: Payment Without Change

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

#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次相邻位交换且每个位置只能交换一次使最终结果序列字典序最小输出此序列暴力莽写得有点丑一个活脱脱的>号我开始压行后就没写过这么丑的代码

#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后先让这个人一直跳尽量远

#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

#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

#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的区间可以等价为多次相邻交换将字符串换成递增的需要逆序对次如果逆序对数相同或者差为偶数（换两次等同于不变）则可以如果有一个串的字母有两个以上这就可以和这个字母不受限地交换所以也可以啊我说的啥啊

#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"); 
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度