【Codeforces】Codeforces Round #53

作者: Caproner | 来源:发表于2019-01-25 20:49 被阅读0次

Problem A

分三种情况：

$l_1=l_2$ 并且 $l_1=r_2$ ，由于必定有解，所以 $r_1$ 必定不会跟 $l_1$ 相等。所以直接输出 $r_1$ 和 $l_1$ 即可。
除此之外，如果 $l_1=l_2$ ，那么输出 $l_1$ 和 $r_2$ 即可。
否则，直接输出 $l_1$ 和 $l_2$ 即可。

时间复杂度为 $O(q)$

#include <iostream>

using namespace std;

int main()
{
    int q;
    cin >> q;
    while(q--)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if((l1 == l2) && (l1 == r2))
        {
            cout << r1 << " " << l1 << endl;
        }
        else if(l1 == l2)
        {
            cout << l1 << " " << r2 << endl;
        }
        else
        {
            cout << l1 << " " << l2 << endl;
        }
    }
    return 0;
}

Problem B

由于必定有解，于是对数组做两次如下操作：

选出数组中最大的数字，记为 $ans$
将数组中所有 $ans$ 的因数去掉一份（去掉一份你的意思是，假设数组里有两个1，那么只去掉一个）。

数组用map统计每个数的个数来存储，找因数使用根号试除法，则时间复杂度为 $O(n{\sqrt d}{\log n})$

#include <iostream>
#include <map>

using namespace std;

int getAns(map<int, int> &mp)
{
    auto it = mp.end();
    it--;
    int ret = it->first;
    for(int i = 1; i * i <= ret; i++)
    {
        if(ret % i)continue;
        mp[i]--;
        if(mp[i] == 0)
        {
            mp.erase(i);
        }
        if(ret / i != i)
        {
            mp[ret / i]--;
            if(mp[ret / i] == 0)
            {
                mp.erase(ret / i);
            }
        }
    }
    return ret;
}

int main()
{
    int n;
    while(cin >> n)
    {
        map<int, int> mp;
        for(int i = 0; i < n; i++)
        {
            int p;
            cin >> p;
            mp[p]++;
        }
        cout << getAns(mp) << " ";
        cout << getAns(mp) << endl;
    }
    return 0;
}

Problem C

根据题意显然可以得知，符合题目要求的字符串必定是以3为周期重复的。
所以只需要枚举前三个字母，然后构造跟输入的字符串s等长的字符串，再比较其字母不同的个数，最后从这些值中取最小值即可。

时间复杂度为 $O(n)$

#include <iostream>
#include <string>
#include <map>

using namespace std;

const string AlphaList = "RGB";

int getAns(string &c, string &s)
{
    int ret = 0;
    for(int i = 0; i < s.length(); i++)
    {
        if(s[i] != c[i % 3])
        {
            ret++;
        }
    }
    return ret;
}

int main()
{
    int n;
    while(cin >> n)
    {
        string s;
        cin >> s;
        int ans = s.length() + 5;
        string c;
        for(int i = 0; i < 3; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                if(i == j)continue;
                for(int k = 0; k < 3; k++)
                {
                    if(i == k)continue;
                    if(j == k)continue;
                    string pc;
                    pc += AlphaList[i];
                    pc += AlphaList[j];
                    pc += AlphaList[k];
                    int pans = getAns(pc, s);
                    if(ans > pans)
                    {
                        ans = pans;
                        c = pc;
                    }
                }
            }
        }
        cout << ans << endl;
        for(int i = 0; i < s.length(); i++)
        {
            cout << c[i % 3];
        }
        cout << endl;
    }
    return 0;
}

Problem D

设 $dp[i][j]$ 为字符串为原串的子串 $[0,i]$ 的情况下，且最后一个字符强制改为 $j$ 的情况下的最小修改数。然后另设一个数组 $prt$ 用于记录dp过程中的选择，然后直接dp过去就行了。

时间复杂度为 $O(n)$

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const string AlphaList = "RGB";

int dp[200005][4];
int prt[200005][4];

void Solve(string &s)
{
    for(int i = 0; i < 3; i++)
    {
        if(s[0] == AlphaList[i])
        {
            dp[0][i] = 0;
        }
        else
        {
            dp[0][i] = 1;
        }
    }
    
    for(int i = 1; i < s.length(); i++)
    {
        for(int j = 0; j < 3; j++)
        {
            dp[i][j] = s.length() + 5;
            for(int k = 0; k < 3; k++)
            {
                if(j == k)continue;
                if(dp[i][j] > dp[i-1][k])
                {
                    dp[i][j] = dp[i-1][k];
                    prt[i][j] = k;
                }
            }
            if(s[i] != AlphaList[j])
            {
                dp[i][j]++;
            }
        }
    }

    int ans = 0;
    if(dp[s.length() - 1][1] < dp[s.length() - 1][ans])
    {
        ans = 1;
    }
    if(dp[s.length() - 1][2] < dp[s.length() - 1][ans])
    {
        ans = 2;
    }

    cout << dp[s.length() - 1][ans] << endl;
    string ansstr;
    for(int i = s.length() - 1; i >= 0; i--)
    {
        ansstr += AlphaList[ans];
        ans = prt[i][ans];
    }
    reverse(ansstr.begin(), ansstr.end());
    cout << ansstr << endl;
}

int main()
{
    int n;
    while(cin >> n)
    {
        string s;
        cin >> s;
        Solve(s);
    }
}

Problem E (E1 + E2)

首先显然需要建立两颗支持区间更新的线段树，分别维护数组的最小值和最大值。
能够想到的一个思路是枚举数组中的每个数，令其尽可能小，除它以外的数尽可能大（只需要只选取所有包含当前数的区间就可以达到这个目的来），然后得到此时的极差，并取所有极差的最大值。
对于每个枚举的值计算极差的时间复杂度是 $O(m{\log n})$ ，于是总的时间复杂度是 $O(nm{\log n})$ 。这显然爆炸。
换个思路，考虑到相邻两次枚举的时候选取的区间是有相交的部分的。由此可以考虑使用尺取法来维护所选的区间。
于是我们需要复制两个原来的区间序列，分别以按 $l$ 升序和按 $r$ 升序来排序（分别记为数列 $v_l$ 和数列 $v_r$ ）。那么每次我们枚举完第 $i$ 个数之后，我们便需要根据 $v_r$ 去掉所有右值小于 $i$ 的区间，再根据 $v_l$ 加入所有左值等于 $i+1$ 开头的区间。这样我们就可以从所有只覆盖到 $i$ 的区间推出所有只覆盖 $i+1$ 的区间。

使用尺取法之后的总时间复杂度为 $O(n+m{\log (m+n)})$ 。不知道会不会算错不过如果按这个算法的话貌似比标程要优一点（标程是 $O(nm)$ ）？感觉十分的慌啊总觉得要么就是时间复杂度算错了要么就是有可以叉掉我的case。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

const int INF = 1e8;

struct SegTree
{
    int a[400005];
    int b[400005];
    int lazy[400005];
    
    void init()
    {
        memset(lazy, 0, sizeof(lazy));
        for(int i = 0; i < 400005; i++)
        {
            a[i] = INF;
            b[i] = -1 * INF;
        }
    }

    void SetElem(int pos, int elem, int l, int r, int p)
    {
        if(l == r)
        {
            a[p] = elem;
            b[p] = elem;
            return;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid)
        {
            SetElem(pos, elem, l, mid, p << 1);
        }
        else
        {
            SetElem(pos, elem, mid + 1, r, (p << 1) + 1);
        }
        a[p] = min(a[p << 1], a[(p << 1) + 1]);
        b[p] = max(b[p << 1], b[(p << 1) + 1]);
    }

    void SetSeg(int pl, int pr, int elem, int l, int r, int p)
    {
        if((pl == l) && (pr == r))
        {
            lazy[p] += elem;
            return;
        }
        int mid = (l + r) >> 1;
        if(pr <= mid)
        {
            SetSeg(pl, pr, elem, l, mid, p << 1);
        }
        else if(pl > mid)
        {
            SetSeg(pl, pr, elem, mid + 1, r, (p << 1) + 1);
        }
        else
        {
            SetSeg(pl, mid, elem, l, mid, p << 1);
            SetSeg(mid + 1, pr, elem, mid + 1, r, (p << 1) + 1);
        }

        a[p] = min(a[p << 1] + lazy[p << 1], a[(p << 1) + 1] + lazy[(p << 1) + 1]);
        b[p] = max(b[p << 1] + lazy[p << 1], b[(p << 1) + 1] + lazy[(p << 1) + 1]);
    }

    int GetMin()
    {
        return a[1] + lazy[1];
    }

    int GetMax()
    {
        return b[1] + lazy[1];
    }

    int GetMinPos(int l, int r, int p)
    {
        if(l == r)
        {
            return l;
        }
        int mid = (l + r) >> 1;
        if(a[p] + lazy[p] == a[p << 1] + lazy[p << 1])
        {
            return GetMinPos(l, mid, p << 1);
        }
        else
        {
            return GetMinPos(mid + 1, r, (p << 1) + 1);
        }
    }
}S;

struct node
{
    int l, r;
    int pos;
    node(int _l = 0, int _r = 0, int _pos = 0)
    {
        l = _l;
        r = _r;
        pos = _pos;
    }
};

bool cmp_l(const node &a, const node &b)
{
    if(a.l != b.l)
    {
        return a.l < b.l;
    }
    return a.r < b.r;
}
bool cmp_r(const node &a, const node &b)
{
    if(a.r != b.r)
    {
        return a.r < b.r;
    }
    return a.l < b.l;
}
vector<node> vl, vr;

int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        S.init();
        vl.clear();
        vr.clear();
        for(int i = 1; i <= n; i++)
        {
            int a;
            scanf("%d", &a);
            S.SetElem(i, a, 1, n, 1);
        }
        for(int i = 0; i < m; i++)
        {
            int l, r;
            scanf("%d%d", &l, &r);
            vl.push_back(node(l, r, i + 1));
            vr.push_back(node(l, r, i + 1));
        }
        sort(vl.begin(), vl.end(), cmp_l);
        sort(vr.begin(), vr.end(), cmp_r);

        int pos_l = 0;
        int pos_r = 0;
        int ans = -1;
        int ans_pos;
        for(int i = 1; i <= n; i++)
        {
            while((pos_r < m) && (vr[pos_r].r < i))
            {
                S.SetSeg(vr[pos_r].l, vr[pos_r].r, 1, 1, n, 1);
                pos_r++;
            }
            while((pos_l < m) && (vl[pos_l].l == i))
            {
                S.SetSeg(vl[pos_l].l, vl[pos_l].r, -1, 1, n, 1);
                pos_l++;
            }
            if(ans < S.GetMax() - S.GetMin())
            {
                ans = S.GetMax() - S.GetMin();
                ans_pos = i;
            }
        }

        while(pos_l < m)
        {
            S.SetSeg(vl[pos_l].l, vl[pos_l].r, -1, 1, n, 1);
            pos_l++;
        }
        while(pos_r < m)
        {
            S.SetSeg(vr[pos_r].l, vr[pos_r].r, 1, 1, n, 1);
            pos_r++;
        }

        vector<int> ans_v;
        for(int i = 0; i < m; i++)
        {
            if((ans_pos <= vl[i].r) && (ans_pos >= vl[i].l))
            {
                ans_v.push_back(vl[i].pos);
            }
        }

        printf("%d\n%d\n", ans, (int)ans_v.size());
        for(int i = 0; i < ans_v.size(); i++)
        {
            if(i)printf(" ");
            printf("%d", ans_v[i]);
        }
        printf("\n");

    }
    return 0;
}

Problem F

一个十分显然的想法是，对图建最小生成树。然后对于剩下的边 $<u,v,w>$ 而言，只要查询最小生成树上从 $u$ 到 $v$ 的路径的最大值是否等于 $w$ 即可。如果是则意味着当前最小生成树中从 $u$ 到 $v$ 的路径上有一条边的权值跟当前边 $<u,v,w>$ 相等，即表明可以用边 $<u,v,w>$ 替换之使其依旧为最小生成树。那么这显然是需要加权值的边，于是答案+1。
对于上述查询的话可以使用树链剖分维护最小生成树来实现，总时间复杂度为 $O(m({\log m})^2)$ 。但是事实上有更加简单且高效的解法。
我们可以把边按权值归类，并让这些分类按权值从小到大排序。那么对于每一类边而言，其权值就是相等的。那么我们便可以按权值从小到大枚举每一类边。对于每一类边而言，用这些边做Kruskal的过程。如果出现会构成环且不是自环的边，那么表明这条边肯定跟同一类边冲突了，那么答案加一。然后再每次对一类边做完Kruskal之后，按照当前Kruskal的并查集对当前图缩点。
思路很简洁，但是缩点这个过程时耗很长（如果每次都去缩点的话，时间复杂度是 $O(n)$ 的）。所以需要考虑如何对缩点这个过程进行优化。
于是考虑不直接缩点，而是将上一个类Kruskal之后的并查集存下来用于当前类Kruskal过程的查询。于是就可以这么做：维护两个并查集D1和D2，其中D1记录的就是上一个类遍历完之后的并查集。然后从小到大遍历每一类边。对于每一类边而言做两遍Kruskal：

第一遍针对D2，如果出现无法插入D2的边，则先去D1检查一下两个点是否已经并起来了。如果已经并起来了的话说明当前边在现在这个缩完点的图中是一条自环边，直接舍弃。否则则表明该边是一条冲突边，答案加一
第二遍针对D1，加就完事了，仅仅是用于将D2的并查集同步到D1。

分类使用map维护，总的时间复杂度为 $O(m{\log m})$ 。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int MAXN = 200005;

struct DSU
{
    int prt[MAXN];
    int n;

    void init(int _n)
    {
        n = _n;
        for(int i = 1; i <= n; i++)
        {
            prt[i] = i;
        }
    }

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

    bool unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if(x == y)return false;
        if(x > y)swap(x, y);
        prt[y] = x;
        return true;
    }
};

struct Kruskal
{
    map< int, vector< pair<int, int> > > mp;
    int n;

    DSU D1, D2;
    
    void init(int _n)
    {
        n = _n;
        mp.clear();
        D1.init(n);
        D2.init(n);
    }

    void push_back(int _u, int _v, int _w)
    {
        mp[_w].push_back(make_pair(_u, _v));
    }

    int Solve()
    {
        int ret = 0;
        for(auto it = mp.begin(); it != mp.end(); it++)
        {
            vector< pair<int, int> > &v = it->second;
            for(int i = 0; i < v.size(); i++)
            {
                if(!D2.unite(v[i].first, v[i].second))
                {
                    if(D1.find(v[i].first) == D1.find(v[i].second))
                    {
                        continue;
                    }
                    ret++;
                }
            }
            for(int i = 0; i < v.size(); i++)
            {
                D1.unite(v[i].first, v[i].second);
            }
        }
        return ret;
    }
}K;

int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        K.init(n);
        for(int i = 0; i < m; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            K.push_back(u, v, w);
        }
        printf("%d\n", K.Solve());
    }
}

【Codeforces】Codeforces Round #53

Problem A

Problem B

Problem C

Problem D

Problem E (E1 + E2)

Problem F

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读