CF1478A

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ "] on line " << __LINE__ << endl
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

vector<int> a;
map<int, int> maps;
void solve() {
    int n = rd();
    a.resize(n + 1);
    maps.clear();
    for(int i = 1; i <= n; i++) a[i] = rd(), maps[a[i]]++;
    int ans = 0;
    for(auto it : maps) {
        ans = max(ans, it.second);
    }
    cout << ans << endl;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}

CF1478B

非常玄学的做法。首先我们发现，对于 100 以上的数字，无论 d 是多少，均可表示。

100 以内刷表法即可。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

int f[210];

void add(int x) {
    for(int i = 0; i <= 100; i++) {
        if(f[i] && i + x <= 100) f[i + x] = 1;
    }
}

void solve() {
    int q = rd(), d = rd();
    ms(f); f[0] = 1;
    for(int i = 0; i <= 9; i++) {
        add(i * 10 + d);
        add(d * 10 + i);
    }
    for(int i = 1; i <= q; i++) {
        int n = rd();
        if(n >= 100) puts("YES");
        else puts(f[n] ? "YES" : "NO");
    }
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}

CF1478C

更加玄学的做法。

|a+b|+|a-b|=2\max(|a|, |b|)

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ "] on line " << __LINE__ << endl
using namespace std;
#define int long long
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

vector<int> a, ans;
void solve() {
    int n = rd();
    a.resize(2 * n);
    ans.resize(n);
    for(int i = 0; i < 2 * n; i++) {
        a[i] = rd();
    }
    sort(a.begin(), a.end(), greater<int> () );
    a.erase(unique(a.begin(), a.end()), a.end());
    if(a.size() != n) return puts("NO"), void();
    int minus = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] - minus <= 0) return puts("NO"), void();
        if((a[i] - minus) % (2 * (n - i))) return puts("NO"), void();
        ans[i] = ((a[i] - minus) / (2 * (n - i)));
        minus += 2 * ans[i];
    }

//  for(int i = 0; i < n; i++) {
//      cout << ans[i] << " ";
//  }
//  cout << endl;

    sort(ans.begin(), ans.end(), greater<int> () );
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    for(auto it : ans) {
        if(it == 0) return puts("NO"), void();
    }
    puts(ans.size() == n ? "YES" : "NO");
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}

P3402 可持久化并查集

按秩合并。套路性地用主席树维护 fa 和 sz 即可。

路径压缩可能导致 MLE。

按秩合并和按 sz 合并都可以保证树高是 O(logn) 级别。

随机合并可能被一条链卡到 O(n) （存疑）

P1947 猜数

奇怪的交互入门题。

值得注意的是警惕本不需要多次调用的函数被多次调用。。。

extern "C" int Seniorious(int);

extern "C" int Chtholly(int n, int c) {
    int l = 1, r = n, ans = 0;
    while(l <= r) {
        int mid = (l + r) >> 1;
        int res = Seniorious(mid);
        if(res == 0) return mid;
        else if(res < 0) 
            l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}

P3641 [APIO2016]最大差分

对我来说谜一样的边界条件 QAQ。

Subtask1：每次询问最大最小值，询问 \frac{n + 1}{2} 次即可得知原序列。暴力即可。

Subtask2：同样获得全局最大最小值。我们发现，即使答案最劣，不过是按照等差数列排布。故答案最劣不会低于 \lceil\frac{a_n - a_1}{n-1}\rceil。

进一步地，将 a_1 至 a_n 的序列分块，块大小为 \lceil\frac{a_n - a_1}{n-1}\rceil。这样每次可能的答案一定是一个块的最小值减去这个块之前的第一个有值的最大值。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define d(x) cerr << #x << " => " << x << endl
extern "C" void MinMax(long long,long long,long long*,long long*);

const int Maxn = 0x7f7f7f7f7f7f7f7f;

vector<int> vec;

extern "C" int findGap(int T, int n) {
    if(T == 1) {
        int on = n;
        int l = 0, r = Maxn;
        vec.resize(n + 1);
        int ti = 0;
        while(n > 0) {
            ++ti;
            int mx, mn;
            MinMax(l, r, &mn, &mx);
            vec[ti] = mn; vec[on - ti + 1] = mx;
            l = mn + 1, r = mx - 1;
            if(l > r) break;
            n -= 2; 
        }

        int res = 0;
        for(int i = 2; i <= on; i++) {
            res = max(res, vec[i] - vec[i - 1]);
        }
        return res;
    } else if(T == 2) {
        int maxx, minx, mx, mn;
        MinMax(0, Maxn, &minx, &maxx);
        int sz = (maxx - minx) / (n - 1);
        if((maxx - minx) % (n - 1)) ++sz;
        int lst = minx, ans = 0;
        for(int i = minx + 1; i < maxx; i += sz) {
            int r = min(i + sz - 1, maxx - 1);
            MinMax(i, r, &mn, &mx);
            ans = max(ans, mn - lst);
            if(mx != -1) lst = mx;
        }
        ans = max(ans, maxx - lst);
        return ans;
    }
}

营业日志 1.28