Codeforces Round #746 (Div. 2) A-E

这场貌似是因为贪玩就没打了。

vp了一下发现正好是我薄弱的部分，没打有点可惜。

A (+1)

　　WA2:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f; ///1061109567
const int maxn = 2e6 + 10;

int n, m, k;
int a[maxn];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++ i) {
            scanf("%d", &a[i]);
        }
        sort(a+1, a+1+n, greater<int>());
        int base = m / (a[1] + a[2]) ;
        m -= (a[1] + a[2]) * base;
        base *= 2;
        while (m) {
            m -= a[1];
            base ++;
            if (m <= 0) break;

            m -= a[2]; ///主要是忽略了这里-a[2]会让 m < 0 之后 while (m)其实会把负数再次进入导致答案多1
            base ++;
        }
        cout << base << endl;
    }
    return 0;
}

View Code

　　AC:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f; ///1061109567
const int maxn = 2e6 + 10;

int n, m, k;
int a[maxn];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++ i) {
            scanf("%d", &a[i]);
        }
        sort(a+1, a+1+n, greater<int>());
        int base = m / (a[1] + a[2]) ;
        
        m -= (a[1] + a[2]) * base;
        
        base *= 2;
        
        if (m > 0) {
            m -= a[1];
            base ++;
        }
        if (m > 0) {
            m -= a[2];
            base ++;
        }
        cout << base << endl;
    }
    return 0;
}

B (+3)

主要这题看上去我一点感觉都没有，还是脑子不大够吧。

假设n = 5。

不如先假设x = 1吧，意味着所有数字都可以和其他位置任意一个数进行交换。

之后再假设x = 2，发现第一个数字可以和3 到 5位置上的数字进行交换，之后又发现第二个位置可以和4到5位置进行交换。

这两个位置可以合并，就相当于第一个位置可以和2-5进行交换(2可以先换到4或者5，之后1跟4或者5进行交换就可以获得2的位置了)

之后其他位置同理，我们发现x = 2的时候也是可以全部交换的。

之后我们在考虑x = 3，发现第三个数字无论如何都不能被交换(3-3 < 1, 3+3 > 5)。

于是我们得到了一个想法，即只要不能交换的位置跟目的数组是相同的，那么我们就可以操作成功。否则就会失败。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f; ///1061109567
const int maxn = 2e6 + 10;

int n, x;
int a[maxn], b[maxn];
int vis[maxn];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &x);
        for (int i = 1; i <= n; ++ i) {
            scanf("%d", &a[i]);
            b[i] = a[i];
            vis[i] = 0;
        }
        sort(b+1, b+1+n);
        for (int i = 1+x; i <= n; ++ i) {
            vis[i] = vis[i-x] = 1;
        }
        int flag = 0;
        for (int i = 1; i <= n; ++ i) {
            if (vis[i] == 0 && a[i] != b[i]) flag = 1;
        }
        if (flag == 1) puts("NO");
        else puts("YES");
    }
    return 0;
}

这道题在vp的时候并没有做出来。

我已经到了如果所有数的xorsum为0的话怎么YES，

如果不为0的话，需要找到三个部分使得这三个部分的xorsum都为整个数组的xorsum。

被卡在如何找到三个部分。之后看了眼别人的题解，其实并不是很难。主要还是没想到吧。

其实我觉得我应该算式想到一点点了。我的想法是从叶子节点出发，一直向上xor，如果找到xorsum为目标的话，那么就cnt++；

但是这样其实是有一个问题的，就是说叶子节点一直向上的话，如果走到了分岔路，你不知道应该要往哪里走。这样的话有可能走完整棵树才会找到目标值。

于是我就觉得这个想法非常的难实现，或者说就是错的。

题解的做法其实就是一个树形dp。思想是根节点出发，先到底部（叶子节点），向上异或，一旦找到值就向上返回0，相当于是吧下面的这个连通块给截断了。之后cnt++，最后统计cnt的值是否大于2就好了。

并不是特别难写，主要还是有一点思维在里面的。你要想到，如果一个树被分成很多个部分的话，这些部分一定会分别有一条或者多条从叶子节点出发的链。这样的话就保证这个树形DP是正确的了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f; ///1061109567
const int maxn = 2e6 + 10;


int a[maxn];

int xorsum;
int cnt = 0;
vector<int> G[maxn];

int DFS(int u, int fa, int sum) {
    //cout << u << " " << fa << endl;
    int tsum = sum;
    for (auto v : G[u]) {
        if (v == fa) continue;
        sum ^= DFS(v, u, tsum);
    }
    sum ^= a[u];
    if (sum == xorsum) {
        cnt ++;
        return 0;
    }
    return sum;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, k; scanf("%d%d", &n, &k);
        xorsum = cnt = 0;
        for (int i = 1; i <= n; ++ i) {
            scanf("%d", &a[i]);
            G[i].clear();
            xorsum ^= a[i];
        }
        for (int i = 1; i <= n-1; ++ i) {
            int u, v; scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }

        if (xorsum == 0) {
            puts("YES");
        }
        else if (k > 2) {
            DFS(1, 0, 0);
            if (cnt > 2) {
                puts("YES");
            }
            else puts("NO");
        }
        else puts("NO");
    }
    return 0;
}

是一个比较有趣的交互题。最后还是看了题解。

不过还是记录一下自己的思考过程吧。

一定会询问一次所有的点来找到最大值（废话）

首先我发现如果是求点对经过边的gcd最大，那么其实就是求树上最大的边权是哪条。

之后很容易想到一个O(n)的询问，即询问每一条边。

之后我一直在想如何优化这个询问的过程。

先考虑为什么是求gcd呢？假设问的是瓶颈路呢？路径的gcd是否有什么关键的性质？（最后发现唯一的性质就是让我知道题目其实是求树上最大边权）

之后想了一个假算法，大概就是每次以根节点出发，每次查询一般的子树，如果不在这一半里就在另一半里，之后继续二分下去，知道找到那一条边。

为啥我觉得他是假的呢，因为最后求的其实是两个点，但是这个算法吧求的其实是一条路径，之后这条边只是在这条路径上，而且这个算法的询问次数大概是高度 * log（n/高度）我觉得肯定过不去。

看了题解发现其实只是需要一个工具而已，欧拉序（其实之前就用过这个东西了，但是一直不知道他叫这个）

我们把每个节点入栈的时间与出栈的时间都记录下来，并排成一个序列，我们发现每棵子树的序列都是连续的。如果我们二分这个区间，那么我们就相当于是二分每一个子树，所以我们一定能求得这条边。

注意欧拉序中节点是会被重复加入的。所以我们需要询问的时候去重。

（话说这个二分其实我也不是很会写。好菜啊，之前我写的二分大多都是懒人版的二分，就是单点查询，但是现在需要的其实是一个长度为2的区间，于是我的懒人版二分就失效了，主要还是自己对二分的理解不大够吧，打算之后看看课好好再学一次二分）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f; ///1061109567
const int maxn = 2e6 + 10;

int n, vis[maxn];
vector<int> G[maxn];
int euler[maxn], tot;

void DFS(int u, int fa) {
    euler[++tot] = u;
    for (auto v : G[u]) {
        if (v == fa) continue;
        DFS(v, u);
        euler[++tot] = u;
    }
}

int query(int L, int R) {
    vector<int> out;
    for (int i = L; i <= R; ++ i) {
        if (vis[euler[i]] == 0) {
            out.push_back(euler[i]);
            vis[euler[i]] = 1;
        }
    }
    cout << "? " << out.size();
    for (auto u : out) {
        cout << " " << u;
        vis[u] = 0;
    }
    cout << endl;
    int get; cin >> get;
    return get;
}

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n-1; ++ i) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    DFS(1, 0);
    int L = 1, R = tot, rec
    int maxx = query(1, tot);
    while (L < R-1) {
        int mid = L + R >> 1;
        if (query(L, mid) == maxx) {
            R = mid;
        }
        else {
            L = mid;
        }
    }
    cout << "! " << euler[L] << " " << euler[R] << endl;
    return 0;
}

一开始我一直在往a ^ b = a + b - (a&b << 1)上去想，即异或等于非进位加法。

于是这道题就卡死了。其实就是异或操作的奇偶性，我们发现每一位上如果是偶数个一那么就是0，奇数个1就是1。

那么如果这个区间长度为奇数，那么就不可能能满足题目要求。因为最高位个数都是1，然后又是奇数个，所以左右两边都是会有最高位。

其他位也是同理。

于是我们从奇偶性出发。

首先我们考虑a & b > a ^ b，假设最高位为k，当且仅当a,b在k位都有1，并且a^b在比k大的数位上没有1。

于是我们考虑从高到低枚举每一位的贡献。并且记录前k位的前缀异或和，当前缀异或和为0的时候，找到最小的位置，检查最小的位置到当前位置是否全部都是1即可，有点类似双指针的思想。

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef pair<int, int> pii;
    const int inf = 0x3f3f3f3f; ///1061109567
    const int maxn = 2e6 + 10;
     
    int n;
    int a[maxn], cnt[maxn], sum[maxn], pos[maxn], vis[maxn];
     
    int main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++ i) {
            scanf("%d", &a[i]);
        }
        int ans = 0;
        for (int j = 20; j >= 0; j --) {
            for (int i = 1; i <= n; ++ i) {
                cnt[i] = cnt[i-1] + ((a[i] >> j) & 1);
                sum[i] = sum[i-1] ^ (a[i] >> j);
            }
            memset(vis, -1, sizeof vis);
            vis[0] = 0;
            for (int i = 1; i <= n; ++ i) {
                if (vis[sum[i]] != -1) {
                    if (cnt[i] - cnt[vis[sum[i]]] == i - vis[sum[i]]) {
                        ans = max(ans, i - vis[sum[i]]);
                    }
                    else vis[sum[i]] = i;
                }
                else vis[sum[i]] = i;
            }
        }
        printf("%d
", ans);
     
        return 0;
    }