Codeforces 1253 #Codeforces

1253A.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 = 1e5 + 100;
int a[maxn], b[maxn];

void solve() {
    int n, tag = -1, cnt = 0;
    bool fail = false;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    for (int i = 0; i < n && !fail; i++) {
        b[i] -= a[i];
        if (b[i] < 0)
            fail = true;
        if (b[i] != 0) {
            if (tag == -1) tag = b[i];
            if (tag != b[i])
                fail = true;
        }
    }

    if (b[0] != 0) cnt++;
    for (int i = 1; i < n && !fail; i++) {
        if (b[i] != b[i - 1] && b[i - 1] == 0) cnt++;
        if (cnt > 1) fail = true;
    }

    cout << (fail ? "NO\n" : "YES\n");
}

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

1253B.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 = 1e5 + 100;
int a[maxn];
set<int> entered, stay;

void solve() {
    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    vector<int> ans;
    int prev = -1;
    bool error = false;
    for(int i=0; i<n; i++){
        bool is_enter = a[i] > 0;
        int id = abs(a[i]);
        if(is_enter){
            if(entered.find(id) != entered.end()){
                error = true;
                break;
            }
            entered.insert(id);
            stay.insert(id);
        }else{
            auto ptr = stay.find(id);
            if(ptr == stay.end()){
                error = true;
                break;
            }
            stay.erase(ptr);
        }
        if(stay.size() <= 0){
            entered.clear();
            ans.push_back(i - prev);
            prev = i;
        }
    }
    if(error || stay.size() > 0){
        cout << -1 << '\n';
    }else{
        cout << ans.size() << '\n';
        for(int i=0; i<ans.size(); i++) cout << ans[i] << " ";
        cout << '\n';
    }
}

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

1253C.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 = 2e5 + 100;
ll a[maxn], b[maxn], ans[maxn];

void solve() {
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for(int i=1; i<=n; i++){
        int pre = i - m;
        b[i] = a[i];
        if(pre > 0) b[i] += b[pre];
    }
    ans[0] = 0;
    for(int i=1; i<=n; i++){
        int pre = i - m;
        ans[i] = ans[i-1] + a[i];
        if(pre > 0) ans[i] += b[i] - a[i];
    }
    for(int i=1; i<=n; i++) cout << ans[i] << " ";
    cout << "\n";
}

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

1253D.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 = 2e5 + 100;
vector<int> edge[maxn];
int vis[maxn];

int lookup(int u){
    return vis[u] == u?u:(vis[u] = lookup(vis[u]));
}

void merge(int u, int v){
    u = lookup(u), v = lookup(v);
    if(u > v) swap(u, v);
    vis[u] = v;
}

void dfs(int u){
    for(int v:edge[u]){
        if(lookup(u) != lookup(v)){
            merge(u, v);
            dfs(v);
        }
    }
}

void solve() {
    int n, m, ans = 0;
    cin >> n >> m;
    for(int i=1; i<=n; i++) vis[i] = i;

    for(int i=0; i<m; i++){
        int u, v;
        cin >> u >> v;
        edge[v].push_back(u);
        edge[u].push_back(v);
    }
    for(int i=1; i<=n; i++){
        if(vis[i] == i)
            dfs(i);
    }

    for(int i=n; i>0; i--){
        int part = lookup(i);
        for(int j=i+1; j<part;){
            int nxt = lookup(j);
            j = nxt + 1;
            if(nxt != part){
                ans ++;
                merge(part, nxt);
            }
        }
    }
    cout << ans << '\n';
}

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

1253E.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 = 100, maxm=1e5 + 1000;

int l[maxn], r[maxn];
int dp[maxm];
int n, m, a, b;

void solve() {
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> a >> b;
        l[i] = a - b;
        r[i] = a + b;
    }
    dp[m + 1] = 0;
    for(int pos=m; pos>0; pos--){
        dp[pos] = m - pos + 1;// 如果右侧没有信号塔
        for(int i=0; i<n; i++){
            if(l[i] <= pos && pos <= r[i]){
                dp[pos] = dp[pos + 1];
                break;
            }
            if(pos < l[i]){
                int cost = l[i] - pos;
                int next_pos = min(m + 1, r[i] + cost + 1);
                dp[pos] = min(dp[pos], cost + dp[next_pos]);
            }
        }
    }
    cout << dp[1] << endl;
}

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