2021“MINIEYE杯”中国大学生算法设计超级联赛

2021“MINIEYE杯”中国大学生算法设计超级联赛

1006

• Given a sequence of integers of length n, find the shortest consecutive subsequence witch XOR sum not less than k.

  If there are multiple consecutive subsequences of the same length, print the consecutive subsequence with the smallest left end point.

  If there are no consecutive subsequence witch XOR sum not less than k, just print “-1”.

【这道题可以说是完全给了自己一道警钟，早早的就写过trie的01树的题目，写这题的时候不仅没想到，百度知道要01trie做之后都没有思路，明明写过求最大异或的题目，害。】

​ 首先这题使用了异或前缀和的01字典树，我们可以边遍历边补充建树，遍历右端点，那么现在已有的树便是所有有可能存在左端点的一颗前缀树，每次从最高位开始找，找是否可能异或为1的点，然后维护一个到当前位置的异或值,如果大于k,则我们维护一个返回的值，而v[p]越大则区间长度越小。

解释

else
        {
            p = son[p][x];
            //if (res >= k)
              //  ans = max(ans, v[p]);
        }

因为如果p = son[p] [x]，值是不会变大的，而不会变的点其实都是之前的点，是肯定会长度更长的。（每次建树每个点都是存的最后一个位置)

int n, k;
int son[30 * maxn][2], idx;
int v[30 * maxn],a[maxn];

void creat(int u,int pos)
{
    int p = 0;

    pre(i, 29, 0)
    {
        int x = u >> i & 1;
        if (son[p][x] == 0) son[p][x] = ++idx;
        p = son[p][x];
        v[p] = pos;
    }

    return;
}

int ser(int u)
{
    int ans = -1;
    int res = 0;
    int p = 0;
    pre(i, 29, 0)
    {
        int x = u >> i & 1;
        if (son[p][!x])
        {
            p = son[p][!x];
            res = res + (1 << i);
            if (res >= k)
                ans = max(ans, v[p]);
        }
        else
        {
            p = son[p][x];
            //if (res >= k)
              //  ans = max(ans, v[p]);
        }
    }

    return ans;
}

signed main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0),cout.tie(0);

    int t = read();
    while (t--)
    {
        n = read(), k = read();

        rep(i, 0, 30 * n) 
            son[i][0] = son[i][1] = 0;
        idx = 0;

        rep(i, 1, n) a[i] = read();

        int sum = 0;
        int l = -1, r = -1;
        int res = 0,minn = inf;

        rep(i, 1, n)
        {
            sum = sum ^ a[i];
            if ((res = ser(sum)) != -1)
            {
                if (minn > (i - res))
                {
                    //see1(i);
                    minn = i - res;
                    l = res + 1;
                    r = i;
                }
            }
            creat(sum, i);
        }

        if (~l)
        {
            printf("%d %d\n", l, r);
        }
        else out(-1);
    }

    return 0;
}

1009

• Let’s call a weighted connected undirected graph of n vertices and m edges KD-Graph, if the
  following conditions fulfill:

  * n vertices are strictly divided into K groups, each group contains at least one vertice

  * if vertices p and q ( p ≠ q ) are in the same group, there must be at least one path between p and q meet the max value in this path is less than or equal to D.

  * if vertices p and q ( p ≠ q ) are in different groups, there can’t be any path between p and q meet the max value in this path is less than or equal to D.

  You are given a weighted connected undirected graph G of n vertices and m edges and an integer K.

  Your task is find the minimum non-negative D which can make there is a way to divide the n vertices into K groups makes G satisfy the definition of KD-Graph.Or −1 if there is no such D exist.

  老毛病了二分之前不想是不是满足单调性不过脑子。

首先最暴力的方法就是从1尝试到inf (X) 从0试到inf（√）但是显然会超时。

那么我们怎么样才能减小找D的次数呢，如果一个d是可行的话，那么d有可能夹在2个权值之间，而如果d可行的话，小于d的那个权值也可行，因为<=d的在一个组里面，所以其实答案就在m个权值中，如果从小到大排序，就只需要遍历1e5次了。

而每次比较都需要在某一阶段合并完成后，再去看是否满足k。

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

struct nod
{
    int a, b, c;

    bool operator < (const nod& b) const&
    {
        return c < b.c;
    }

}mp[5*maxn];

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

void solve()
{
    rep(i, 1, n) fa[i] = i;

    sort(mp + 1, mp + 1 + m);

    int now = n,ans = 0;

    rep(i, 1, m)  
    {
        if (mp[i].c > ans)  // 在将某一阶段合并完成后，再去比较 
        {
            if (now == k)
            {
                out(ans);
                return;
            }
        }

        if ( find(mp[i].a) == find(mp[i].b) ) continue;

        now--; // 现在有的集合数减少
        fa[find(mp[i].a)] = find(mp[i].b);
        ans = mp[i].c;

    }
    printf("%d\n", now == k ? ans : -1); //最后有一次是没有判断的
    return ;
}

signed main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0),cout.tie(0);

    int t = read();
    while (t--)
    {
        n = read(), m = read(), k = read();

        rep(i, 1, m)
        {
            int x = read(), y = read(), z = read();
            mp[i] = { x,y,z };
        }

        solve();
    }
    return 0;
}