记一下第一次AK codeforces吧(虽然是div. 3，小声)

作者： 作者的头像   cup-pyy ,  2022-01-11 03:11:33 ,  所有人可见 ,  阅读 582

9


2

题目链接

A题

题解

水题，判断最大值与最小值差即可

代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        int maxv = 0, minv = 1e9 + 1;
        for(int i = 1; i <= n; i++){
            int x;
            cin >> x;
            maxv = max(maxv, x);
            minv = min(minv, x);
        }
        cout << maxv - minv << '\n';
    }

}

B题

题解

水题，分别判断操作三个数能否成功即可

代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int a, b, c;
        cin >> a >> b >> c;
        if (2 * b - a > 0 && (2 * b - a) % c == 0) cout << "YES" << '\n';
        else if (2 * b - c > 0 && (2 * b - c) % a == 0) cout << "YES" << '\n';
        else if ((a + c) % 2 == 0 && (a + c) / 2 % b == 0) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }

}

C题

题解

二分图匹配，输入的每个数字用$log2(10^9)$复杂度可以预处理出这个数字可以变成哪些小于$n$的数字，能变成的数字连一条边，用匈牙利算法计算最大匹配数目是否等于$n$即可

代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn = 105, maxm = 2500;
int h[maxn], e[maxm], ne[maxm], idx;
int match[maxn];
bool v[maxn];
int a[55];

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool find(int u){
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if (!v[j]){
            v[j] = 1;
            if (!match[j] || find(match[j])){
                match[j] = u;
                return true;
            }
        }
    }
    return false;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        memset(h, -1, sizeof h);
        memset(match, 0, sizeof match);
        idx = 0;
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++){
            int x;
            cin >> x;
            while(x){
                if (x <= n) add(i, n + x);
                x /= 2;
            }
        }
        int cnt = 0;
        for(int i = 1; i <= n; i++){
            memset(v, 0, sizeof v);
            if (find(i)) cnt++;
        }
        cout << (cnt == n ? "YES" : "NO") << '\n';
    }

}

D题

题解

水题，计算总数目为奇数的字母的数量为$cnt$，这些字母都删掉一个的话剩下的字母一定都是成对的，一定可以凑成回文串，因此数目为$(n - cnt) / k$，此外，奇数长度的回文串里可以出现一个不成对的字母，因此还需要特判一下。

代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 5, INF = 0x3f3f3f3f;
char s[maxn];
int c[26];

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        memset(c, 0, sizeof c);
        int n, k;
        cin >> n >> k >> s + 1;
        for(int i = 1; i <= n; i++) c[s[i] - 'a']++;
        int cnt = 0;
        for(int i = 0; i < 26; i++) cnt += (c[i] & 1);
        int len = (n - cnt) / k;
        if (len % 2 == 0 && n - len * k >= k) len++;
        cout << len << '\n';
    }

}

E题

题解

这题是最后才做出来的，其实很简单。
首先预处理字符串里所有长度为2和3的子串保存把他们的位置存下来，这样的串其实很少只有$1000 + 100$个，其他长度的串都可以由长度2和3的串组合出来(有点类似GoodBye2021里的D题)。
这样之后其实判断目标串能否达到就成了一个背包问题，可以在$O(n)$复杂度内解决并且记录下方案(详细看代码)。

代码

#include<iostream>
#include<cstring>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e3 + 5, INF = 0x3f3f3f3f;
struct Node{
    int l, r, i;
};
char s[maxn];
Node mp[2][1000];
bool f[maxn];
int pre[maxn];

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        memset(mp, 0, sizeof mp);
        int n, m;
        cin >> n >> m;
        for(int i = 1; i <= n; i++){
            cin >> s + 1;
            for(int j = 1; j <= m - 1; j++){
                int v = (s[j] - '0') * 10 + (s[j + 1] - '0');
                mp[0][v] = {j, j + 1, i};
            }
            for(int j = 1; j <= m - 2; j++){
                int v = (s[j] - '0') * 100 + (s[j + 1] - '0') * 10 + (s[j + 2] - '0');
                mp[1][v] = {j, j + 2, i};
            }
        }
        cin >> s + 1;
        for(int i = 1; i <= m; i++) f[i] = 0;
        f[0] = 1;
        for(int i = 2; i <= m; i++){
            int v1 = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if (f[i - 2] && mp[0][v1].l){
                f[i] = 1;
                pre[i] = 2;
            }
            if (i >= 3){
                int v2 = (s[i - 2] - '0') * 100 + (s[i - 1] - '0') * 10 + (s[i] - '0');
                if (f[i - 3] && mp[1][v2].l){
                    f[i] = 1;
                    pre[i] = 3;
                }
            }

        }
        if (f[m]){
            vector<Node> ans;
            for(int i = m; i; i -= pre[i]){
                if (pre[i] == 2){
                    int v = (s[i - 1] - '0') * 10 + (s[i] - '0');
                    ans.push_back(mp[0][v]);
                }
                else{
                    int v = (s[i - 2] - '0') * 100 + (s[i - 1] - '0') * 10 + (s[i] - '0');
                    ans.push_back(mp[1][v]);
                }
            }
            reverse(ans.begin(), ans.end());
            cout << ans.size() << '\n';
            for(auto &[l, r, i] : ans)
                cout << l << ' ' << r << ' ' << i << '\n';
        }
        else cout << -1 << '\n';

    }

}

F题

题解

从要求询问的次数不超过10次不难看出来需要二分，但是这题二分的左右边界是不断在变动的，所以就显得有点奇怪。
为了保证复杂度，限制询问的次数必须保证每次必须把区间都缩小一半。
一开始数的范围是$[1, n - 1]$，后来每次的区间范围假设是$[l, r]$。那么我们每次要加上的数字必须要使区间前一半数字除以$n$向下取整的的数字不变，而区间后一半数字除以$n$向下取整的的数字加1，这样我们就比较方便确定操作的数字了。

代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;

int ask(int x){
    cout << "+ " << x << endl;
    int t;
    cin >> t;
    return t;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;
    int t = ask(n / 2);
    int l, r;
    if (t) l = n, r = n - 1 + n / 2;
    else l = n / 2 + 1, r = n - 1;
    while(l < r){
        int m = l + r + 1 >> 1;
        int ll = l % n, rr = r % n;
        int mid = n - ((ll + rr + 1) >> 1);
        int tmp = ask(mid);
        if (tmp > t) l = m + mid, r += mid;
        else l += mid, r = m + mid - 1;
        t = tmp;
    }
    cout << "! " << r << endl;

}

G题

题解

感觉并不难，这题做出来的人数也多于$E$和$F$题，核心是贪心。
从最高位开始枚举，每次只用一位用$Kruskal$来做最小生成树，很显然只要有生成树中有一条边这一位为$1$，那么我们无论怎么取边，最终这一位都不可能为$0$，那我们就在总答案里加上这一位；如果这一位可以为$0$，因为是从高位往低位枚举的，不取这一位的结果一定更好，那么说明生成树中不会出现这一位为$1$的边，我们就给这些边做个标记，再往下做最小生成树的时候就不能再使用这些边。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 5, INF = 0x3f3f3f3f;

int p[maxn], w[maxn];
bool v[maxn];
struct Edge{
    int a, b, w, bit, id;
    bool operator<(const Edge &t) const {
        return bit < t.bit;
    }
}e[maxn];
int n, m;

int find(int x){
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

int kruskal(int bit){
    for(int i = 0; i < m; i++) e[i].bit = (e[i].w >> bit & 1);
    sort(e, e + m);
    int res = 0;
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 0; i < m; i++){
        if (v[e[i].id]) continue;
        int x = find(e[i].a), y = find(e[i].b);
        if (x != y){
            p[x] = y;
            res |= e[i].bit;
        }
        if (res) return 1;
    }
    if (res == 0)
        for(int i = 0; i < m; i++)
            if ((e[i].w >> bit) & 1)
                v[e[i].id] = 1;
    return 0;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        cin >> n >> m;
        for(int i = 0; i < m; i++) v[i] = 0;
        for(int i = 0; i < m; i++) cin >> e[i].a >> e[i].b >> e[i].w, e[i].id = i;
        int res = 0;
        for(int i = 30; i >= 0; i--)
            res += kruskal(i) << i;
        cout << res << '\n';
    }

}

5 评论

用户头像
标准的零分   2022-01-11 19:25         踩      回复

请问d题最后的n-len*k>=k是什么意思Orz

用户头像
cup-pyy   2022-01-11 23:54         踩      回复

len是保证可以成对出现的点能组成的长度，一共有k种颜色，n - len * k就是把这些成对的字母都用完之后剩下的不能成对的字母的数量，如果len是偶数的话可以在中间插入任何一个不成对的字母，只要剩下的这些字母数量大于等于k说明可以给所有串都加上一个字母

用户头像
标准的零分   2022-01-12 08:21    回复了 cup-pyy 的评论         踩      回复

懂了, 谢谢大佬Orz

用户头像
har   2022-01-11 14:59         踩      回复

G题这样做如何保证最后是一颗生成树啊QAQ没想明白

用户头像
cup-pyy   2022-01-11 15:22         踩      回复

因为前面是保证剩下的边能够使图联通才会去删边，所以最后的图一定联通，所以一定存在生成树