Codeforces 1278 #Codeforces

1278A.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)

using namespace std;

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

const int inf = 0x3f3f3f3f;
const int maxn = 100 + 100;
char key[maxn], hesh[maxn];
int cnt[27], temp[27];

void solve() {
    cin >> key >> hesh;
    int hlen = strlen(hesh);
    int klen = strlen(key);
    F(i, 27) cnt[i] = 0;
    F(i, klen) cnt[key[i]-'a']++;
    F(i, hlen-klen+1){
        F(j, 27) temp[j] = cnt[j];
        int remain = klen;
        for(int j=i; j<hlen && remain > 0; j++) {
            if(temp[hesh[j]-'a'] <= 0) break;
            temp[hesh[j] - 'a']--;
            remain--;
        }

        if(remain == 0){
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

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

1278B.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)

using namespace std;

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

const int inf = 0x3f3f3f3f;
const int maxn = 100 + 100;

void solve() {
    int a, b;
    cin >> a >> b;
    if(a < b) swap(a, b);
    int diff = a - b, p = 0;
    ll sum = 0;
    while(true){
        sum += p;
        if ((diff + sum) % 2 == 0){
            if(sum >= diff) {
                cout << p << '\n';
                return;
            }
        }
        p++;
    }
}

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

1278C.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)

using namespace std;

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

const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 100;
int le[maxn], ri[maxn];

void solve() {
    int n, ab_sum=0;
    cin >> n;
    F(i, n) cin >> le[i], ab_sum += (le[i]==1?1:-1);
    F(i, n) cin >> ri[i], ab_sum += (ri[i]==1?1:-1);
    if(ab_sum == 0){
        cout << "0\n";
        return;
    }
    map<int, int> dict;
    dict[0] = 0;
    int sum = 0;
    for(int i=0; i<n; i++){
        sum += (ri[i]==1)?-1:1;
        if(dict.find(sum) == dict.end()){
            dict[sum] = i + 1;
        }
    }
    int ans = inf;
    if(dict.find(-ab_sum) != dict.end()){
        ans = dict[-ab_sum];
    }
    for(int i=n-1; i>=0; i--){
        ab_sum += (le[i]==1)?-1:1;
        auto counter = dict.find(-ab_sum);
        if(counter != dict.end()){
            ans = min(ans, n-i + (*counter).second);
        }
    }
    cout << ans << '\n';
}

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

1278D.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)

using namespace std;

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

const int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 100;
int in[maxn], out[maxn];
int mark[maxn], vis[maxn]={0}, vis_cnt=0;
vector<pair<int, int> > seg;
vector<int> G[maxn];

void dfs(int u){
    vis[u] = 1;
    vis_cnt++;
    for(int v:G[u]) if(!vis[v]) dfs(v);
}

void solve() {
    int n, edge_cnt=0;
    cin >> n;
    F(i, n) mark[i] = i;
    F(i, n){
        cin >> in[i] >> out[i];
        seg.push_back({in[i], i});
        seg.push_back({out[i], i});
    }
    sort(seg.begin(), seg.end());
    set<pair<int, int> > end_points;
    for(pair<int, int> pii:seg){
        auto ptr = end_points.find(pii);
        if(ptr != end_points.end()){
            end_points.erase(ptr);
        }else{
            for(pair<int, int> ii:end_points){
                if(ii.first > out[pii.second]) break; // 这样才不会TLE
                G[ii.second].push_back(pii.second);
                G[pii.second].push_back(ii.second);
                edge_cnt++;
                if(edge_cnt >= n) break; // 没有这个会MLE
            }
            end_points.insert({out[pii.second], pii.second});
        }
        if(edge_cnt >= n) break; // 没有这个会MLE
    }
    dfs(0);
    cout << ((edge_cnt==n-1 && vis_cnt==n)?"YES\n":"NO\n");
}

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

1278E.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)
#define print(s) std::cout << s << std::endl

using namespace std;

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

const int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 100;
vector<int> tree[maxn];
vector<int> ans;

// shamelessly 'copy' from https://codeforces.com/contest/1278/submission/67222501

void dfs(int u, int p){
    for(int v:tree[u]){
        if(v == p) continue;
        ans.push_back(v);
    }
    ans.push_back(-u); // 保证孙节点的线段不会与父节点的线段相交
    reverse(tree[u].begin(), tree[u].end()); // 让子节点嵌入下一个子节点
    for(int v:tree[u]){
        if(v == p) continue;
        dfs(v, u);
    }
}

void solve() {
    int n;
    cin >> n;
    for(int i=1; i<n; i++){
        int l, r;
        cin >> l >> r;
        tree[l].push_back(r);
        tree[r].push_back(l);
    }
    ans.push_back(1);
    dfs(1, 0);
    vector<pair<int, int> > trans(n);
    F(i, ans.size()){
        int v = ans[i];
        if(v < 0){
            trans[-v].second = i+1;
        }else{
            trans[v].first = i+1;
        }
    }
    for(int i=1; i<=n; i++){
        cout << trans[i].first << " " << trans[i].second << '\n';
    }
    cout << flush;
}

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