Codeforces 1234 #Codeforces

1234B2.cpp

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

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int n, k;
queue<int> que;
unordered_set<int, custom_hash> st;
void solve(){
    int v;
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> v;
        if(st.count(v)) continue;
        if(que.size() >= k){
            int ot = que.front();
            que.pop();
            st.erase(ot);
        }
        que.push(v), st.insert(v);
    }
    vector<int> ans;
    while(!que.empty()){
        ans.push_back(que.front());
        que.pop();
    }
    reverse(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for(int a:ans){
        cout << a << ' ';
    }
    cout << endl;
}

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

1234D.cpp

// 这题完全可以用set 的 binary_search (lower_bound) 做
#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
//cuz i am not using ios
using namespace std;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll inf=0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5 + 1000;
int n;
// 应该叫 Fenwick Tree 或 Binary Indexed Tree
struct tree_arr{
    int arr[maxn];
    void clear(){
        for(int i=0;i<=n;i++) arr[i] = 0;
    }
    void modify(int pos, int delta){
        for(int i=pos;i<=n;i+=(-i)&i) arr[i] += delta;
    }
    int query(int pos){
        int ret = 0;
        for(int i=pos;i>0;i-=(-i)&i) ret += arr[i];
        return ret;
    }
}ta[26];
char buffer[maxn];

void solve(){
    cin >> (buffer + 1);
    n = strlen(buffer + 1);
    for(int i=1;i<=n;i++)
        ta[buffer[i]-'a'].modify(i, 1);
    int q, a, b, c;
    char ch;
    cin >> q;
    for(int i=0;i<q;i++){
        cin >> a;
        if(a == 2){
            cin >> b >> c;
            int ans = 0;
            for(int i=0;i<26;i++){
                ans += (ta[i].query(c) - ta[i].query(b - 1) > 0);
            }
            cout << ans << '\n';
        }else{
            cin >> b >> ch;
            ta[buffer[b] - 'a'].modify(b, -1);
            ta[ch - 'a'].modify(b, 1);
            buffer[b] = ch;
        }
    }
}

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

1234E.cpp

/*
    另一做法更好理解
    https://codeforces.com/blog/entry/70233?#comment-547256
    https://codeforces.com/contest/1234/submission/61676673
*/
#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
//cuz i am not using ios
using namespace std;

const int maxn = 2e5 + 1000;
ll x[maxn], ans[maxn];
vector<int> nearby[maxn];
int pref[maxn] = {0};

void solve(){
    int n, m;
    cin >> n >> m;
    for(int i=0;i<m;i++) cin >> x[i];
    for(int i=0;i<m-1;i++){
        if(x[i] != x[i+1]){ //如果相等，那么就是0
            nearby[x[i]].push_back(x[i+1]);
            nearby[x[i+1]].push_back(x[i]);
        }
        
        if(abs(x[i] - x[i+1]) >= 2){
            pref[min(x[i], x[i+1]) + 1]++;
            pref[max(x[i], x[i+1])]--;
        }
    }
    for(int i=1;i<=n;i++) pref[i] += pref[i-1];
    ans[1] = 0;
    for(int i=0;i<m-1;i++){
        ans[1] += abs(x[i] - x[i+1]);
    }

    for(int i=2;i<=n;i++){
        ans[i] = ans[1] - pref[i];
        for(int j:nearby[i]){
            ans[i] -= abs(i - j);
            ans[i] += j - 1 + (j <= i);
        }
    }

    for(int i=1;i<=n;i++){
        cout << ans[i] << ' ';
    }
    cout << endl;

}

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

1234F.cpp

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

const int maxn = 1 << 20, mask = (1 << 20) - 1;
bool is_appeared[30];
char str[maxn];
int len, rec[maxn + 10];

void solve(){
    memset(is_appeared, 0, sizeof is_appeared);
    memset(rec, 0, sizeof rec);
    cin >> str;
    len = strlen(str);
    int l = 0, r = 0, stat = 0;
    for(;r < len;r++){
        int idx = str[r] - 'a';
        while(is_appeared[idx]){
            is_appeared[str[l] - 'a'] = false;
            stat ^= 1 << (str[l] - 'a');
            l++;
        }
        is_appeared[idx] = true;
        stat |= 1 << idx;
        rec[stat] = max(rec[stat], r - l + 1);

        int tmp_stat = stat;
        for(int i=l; i<r; i++){
            tmp_stat ^= (1 << (str[i] - 'a'));
            rec[tmp_stat] = max(rec[tmp_stat], r - i);
        }
    }
    
    for(int i=0;i<mask;i++){
        if(rec[i] == 0) continue;
        for(int j=0;j<20;j++){
            if((i & (1 << j)) == 0)
                rec[i | (1 << j)] = max(rec[i], rec[i | (1 << j)]);
        }
    }

    int ans = 0;
    for(int i=mask;i>0;i--){
        if(rec[i] == 0) continue;
        ans = max(ans, rec[i] + rec[mask ^ i]);
    }
    cout << ans << '\n';
}

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