Codeforces 1256 #Codeforces

1256C.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

void redirect_input(){freopen("./input.txt","r",stdin);}
void redirect_output(){freopen("./output.txt","w",stdout);}

const int maxn = 1200;
int n, d, m;
int b[maxn]={0};

void solve(){
    int presum = 0;
    cin >> n >> m >> d;
    for(int i=1; i<=m; i++){
        cin >> b[i];
        presum += b[i];
    }
    if(presum + (d - 1) * (m + 1) < n){
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
    int space = n - presum;
    for(int idx=1; idx<=m; idx++){
        if(space >= d - 1){
            space -= d - 1;
            for(int i=0; i<d-1; i++) cout << "0 ";
        }else{
            for(int i=0; i<space; i++) cout << "0 ";
            space = 0;
        }
        for(int i=0; i<b[idx]; i++) cout << idx << " ";
    }
    for(int i=0; i<space; i++) cout << "0 ";
    cout << endl;
}

signed main(){
    Android;
    redirect_input();
    solve();
}

1256D.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

void redirect_input(){freopen("./input.txt","r",stdin);}
void redirect_output(){freopen("./output.txt","w",stdout);}

const int maxn = 1e6 + 1000;
char buffer[maxn];

void solve(){
    ll n, k;
    cin >> n >> k;
    cin >> buffer;

    ll iter_pos = 0;
    for(int i=0; i<n; i++){
        if(buffer[i] == '1') continue;
        iter_pos = max(iter_pos, i - k);
        while(iter_pos < i && buffer[iter_pos] == '0') iter_pos++;
        swap(buffer[iter_pos], buffer[i]);
        k -= i - iter_pos;
    }
    cout << buffer << '\n';
}

signed main(){
    Android;
    int q;
    cin >> q;
    while(q--) solve();
}

1256E.cpp

 #include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

void redirect_input(){freopen("./input.txt","r",stdin);}
void redirect_output(){freopen("./output.txt","w",stdout);}

const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6 + 1000;
ll dp[maxn] = {0};

pair<int, int> players[maxn];
int mark[maxn], ans[maxn];

void solve(){
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) {
        int skill;
        cin >> skill;
        players[i] = {skill, i};
    }
    sort(players + 1, players + n + 1, greater<pair<int, int> >());
    int choose = 0;
    dp[0] = 0;
    dp[1] = dp[2] = inf;
    mark[0] = -1;
    for(int i=3; i<=n; i++){
        if(i-3 >= 0 && dp[i-3] + players[i-2].first < dp[choose] + players[choose+1].first){
            choose = i-3;
        }
        mark[i] = choose;
        dp[i] = dp[choose] + players[choose + 1].first - players[i].first;
    }
    vector<int> ptrs;
    int ptr = n;
    while(ptr != -1){
        ptrs.push_back(ptr), ptr = mark[ptr];
    }
    reverse(ptrs.begin(), ptrs.end());
    for(int i=1; i<=n; i++){
        ans[players[i].second] = lower_bound(ptrs.begin(), ptrs.end(), i) - ptrs.begin();
    }
    cout << dp[n] << " " << ptrs.size() - 1 << "\n";
    for(int i=1; i<=n; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
}

signed main(){
    Android;
    solve();
}

1256F.cpp

 #include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

void redirect_input(){freopen("./input.txt","r",stdin);}
void redirect_output(){freopen("./output.txt","w",stdout);}

const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6 + 1000;
char s1[maxn], s2[maxn];
int cnt1[26], cnt2[26];

// 冒泡排序，求要多少次交换才能够使其有序
// 即求逆序对的数目(由于len<=26，因此就不使用归并排序求解了)
// 当两串的逆序对数之和为偶数时输出"YES"，否则为"NO"
int calc(char * s, int len){
    int cnt = 0;
    for(int i=0; i<len-1; i++){
        for(int j=0; j<len-i-1; j++){
            if(s[j]>s[j+1]){
                cnt++;
                swap(s[j], s[j+1]);
            }
        }
    }
    return cnt;
}

void solve(){
    memset(cnt1, 0, sizeof cnt1);
    memset(cnt2, 0, sizeof cnt2);
    int n;
    cin >> n >> s1 >> s2;
    bool equal = true;
    for(int i=0; i<n && equal; i++) if(s1[i] != s2[i]) equal = false;
    if(equal){
        cout << "YES\n";
        return;
    }

    for(int i=0; i<n; i++) cnt1[s1[i]-'a']++;
    for(int i=0; i<n; i++) cnt2[s2[i]-'a']++;
    bool doub = false;
    equal = true;
    for(int i=0; i<26 && equal; i++) {
        if(cnt1[i] != cnt2[i]) equal = false;
        if(cnt1[i] >= 2) doub = true;
    }
    if(!equal){
        cout << "NO\n";
        return;
    }
    // 如果出现某个字符出现2次或以上
    if(doub){
        cout << "YES\n";
        return;
    }

    int c1 = calc(s1, n), c2 = calc(s2, n);
    // 若交换次数之和为偶数，那么就Yes
    if((c1 + c2) % 2){
        cout << "NO\n";
    }else{
        cout << "YES\n";
    }
}

signed main(){
    Android;
    int q;
    cin >> q;
    while(q--)
        solve();
}