【Codeforces】Codeforces Round #535

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$ 即可梧兼。

時間復(fù)雜度為 $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

由于必定有解放吩，于是對數(shù)組做兩次如下操作：

選出數(shù)組中最大的數(shù)字，記為 $ans$
將數(shù)組中所有 $ans$ 的因數(shù)去掉一份（去掉一份你的意思是羽杰，假設(shè)數(shù)組里有兩個1渡紫，那么只去掉一個）到推。

數(shù)組用map統(tǒng)計每個數(shù)的個數(shù)來存儲，找因數(shù)使用根號試除法惕澎，則時間復(fù)雜度為 $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

根據(jù)題意顯然可以得知莉测，符合題目要求的字符串必定是以3為周期重復(fù)的。
所以只需要枚舉前三個字母集灌，然后構(gòu)造跟輸入的字符串s等長的字符串，再比較其字母不同的個數(shù)复哆，最后從這些值中取最小值即可欣喧。

時間復(fù)雜度為 $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

設(shè) $dp[i][j]$ 為字符串為原串的子串 $[0,i]$ 的情況下，且最后一個字符強(qiáng)制改為 $j$ 的情況下的最小修改數(shù)梯找。然后另設(shè)一個數(shù)組 $prt$ 用于記錄dp過程中的選擇唆阿，然后直接dp過去就行了。

時間復(fù)雜度為 $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)

首先顯然需要建立兩顆支持區(qū)間更新的線段樹锈锤，分別維護(hù)數(shù)組的最小值和最大值驯鳖。
能夠想到的一個思路是枚舉數(shù)組中的每個數(shù)，令其盡可能小久免，除它以外的數(shù)盡可能大（只需要只選取所有包含當(dāng)前數(shù)的區(qū)間就可以達(dá)到這個目的來）浅辙，然后得到此時的極差，并取所有極差的最大值阎姥。
對于每個枚舉的值計算極差的時間復(fù)雜度是 $O(m{\log n})$ 记舆，于是總的時間復(fù)雜度是 $O(nm{\log n})$ 。這顯然爆炸呼巴。
換個思路泽腮，考慮到相鄰兩次枚舉的時候選取的區(qū)間是有相交的部分的。由此可以考慮使用尺取法來維護(hù)所選的區(qū)間衣赶。
于是我們需要復(fù)制兩個原來的區(qū)間序列诊赊，分別以按 $l$ 升序和按 $r$ 升序來排序（分別記為數(shù)列 $v_l$ 和數(shù)列 $v_r$ ）。那么每次我們枚舉完第 $i$ 個數(shù)之后府瞄，我們便需要根據(jù) $v_r$ 去掉所有右值小于 $i$ 的區(qū)間碧磅，再根據(jù) $v_l$ 加入所有左值等于 $i+1$ 開頭的區(qū)間。這樣我們就可以從所有只覆蓋到 $i$ 的區(qū)間推出所有只覆蓋 $i+1$ 的區(qū)間遵馆。

使用尺取法之后的總時間復(fù)雜度為 $O(n+m{\log (m+n)})$ 续崖。不知道會不會算錯不過如果按這個算法的話貌似比標(biāo)程要優(yōu)一點(diǎn)（標(biāo)程是 $O(nm)$ ）？感覺十分的慌啊總覺得要么就是時間復(fù)雜度算錯了要么就是有可以叉掉我的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$ 即可像吻。如果是則意味著當(dāng)前最小生成樹中從 $u$ 到 $v$ 的路徑上有一條邊的權(quán)值跟當(dāng)前邊 $<u,v,w>$ 相等峻黍，即表明可以用邊 $<u,v,w>$ 替換之使其依舊為最小生成樹。那么這顯然是需要加權(quán)值的邊拨匆，于是答案+1姆涩。
對于上述查詢的話可以使用樹鏈剖分維護(hù)最小生成樹來實(shí)現(xiàn)，總時間復(fù)雜度為 $O(m({\log m})^2)$ 惭每。但是事實(shí)上有更加簡單且高效的解法骨饿。
我們可以把邊按權(quán)值歸類，并讓這些分類按權(quán)值從小到大排序台腥。那么對于每一類邊而言宏赘，其權(quán)值就是相等的。那么我們便可以按權(quán)值從小到大枚舉每一類邊黎侈。對于每一類邊而言察署，用這些邊做Kruskal的過程。如果出現(xiàn)會構(gòu)成環(huán)且不是自環(huán)的邊峻汉，那么表明這條邊肯定跟同一類邊沖突了贴汪，那么答案加一。然后再每次對一類邊做完Kruskal之后休吠，按照當(dāng)前Kruskal的并查集對當(dāng)前圖縮點(diǎn)扳埂。
思路很簡潔，但是縮點(diǎn)這個過程時耗很長（如果每次都去縮點(diǎn)的話瘤礁，時間復(fù)雜度是 $O(n)$ 的）聂喇。所以需要考慮如何對縮點(diǎn)這個過程進(jìn)行優(yōu)化。
于是考慮不直接縮點(diǎn)蔚携，而是將上一個類Kruskal之后的并查集存下來用于當(dāng)前類Kruskal過程的查詢希太。于是就可以這么做：維護(hù)兩個并查集D1和D2，其中D1記錄的就是上一個類遍歷完之后的并查集酝蜒。然后從小到大遍歷每一類邊誊辉。對于每一類邊而言做兩遍Kruskal：

第一遍針對D2，如果出現(xiàn)無法插入D2的邊亡脑，則先去D1檢查一下兩個點(diǎn)是否已經(jīng)并起來了堕澄。如果已經(jīng)并起來了的話說明當(dāng)前邊在現(xiàn)在這個縮完點(diǎn)的圖中是一條自環(huán)邊，直接舍棄霉咨。否則則表明該邊是一條沖突邊蛙紫，答案加一
第二遍針對D1，加就完事了途戒，僅僅是用于將D2的并查集同步到D1坑傅。

分類使用map維護(hù)，總的時間復(fù)雜度為 $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());
    }
}

最后編輯于：2019.01.27 19:07:55

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末唁毒，一起剝皮案震驚了整個濱河市蒜茴，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌浆西，老刑警劉巖粉私，帶你破解...
沈念sama閱讀 211,743評論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異近零，居然都是意外死亡诺核，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,296評論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門久信，熙熙樓的掌柜王于貴愁眉苦臉地迎上來窖杀，“玉大人，你說我怎么就攤上這事入篮〕率荩” “怎么了幌甘？”我有些...
開封第一講書人閱讀 157,285評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵潮售，是天一觀的道長锅风。經(jīng)常有香客問我酥诽，道長，這世上最難降的妖魔是什么肮帐？我笑而不...
開封第一講書人閱讀 56,485評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮边器，結(jié)果婚禮上训枢，老公的妹妹穿的比我還像新娘。我一直安慰自己忘巧，他們只是感情好恒界，可當(dāng)我...
茶點(diǎn)故事閱讀 65,581評論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著砚嘴，像睡著了一般十酣。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上际长，一...
開封第一講書人閱讀 49,821評論 1贊 290
城市分裂傳說
那天耸采，我揣著相機(jī)與錄音，去河邊找鬼工育。笑死虾宇，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的如绸。我是一名探鬼主播文留，決...
沈念sama閱讀 38,960評論 3贊 408
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼好唯，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了燥翅？” 一聲冷哼從身側(cè)響起骑篙，我...
開封第一講書人閱讀 37,719評論 0贊 266
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎森书，沒想到半個月后靶端，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,186評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡凛膏，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,516評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年杨名，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片猖毫。...
茶點(diǎn)故事閱讀 38,650評論 1贊 340
活死人
序言：一個原本活蹦亂跳的男人離奇死亡台谍，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出吁断，到底是詐尸還是另有隱情趁蕊，我是刑警寧澤，帶...
沈念sama閱讀 34,329評論 4贊 330
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布仔役，位于F島的核電站掷伙，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏又兵。R本人自食惡果不足惜任柜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,936評論 3贊 313
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望沛厨。院中可真熱鬧宙地，春花似錦、人聲如沸逆皮。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,757評論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽页屠。三九已至粹胯，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間辰企，已是汗流浹背风纠。一陣腳步聲響...
開封第一講書人閱讀 31,991評論 1贊 266
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留牢贸，地道東北人竹观。一個月前我還...
沈念sama閱讀 46,370評論 2贊 360
代替公主和親
正文我出身青樓，卻偏偏與公主長得像，于是被迫代替她去往敵國和親臭增。傳聞我的和親對象是個殘疾皇子懂酱，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,527評論 2贊 349