91色婷婷超碰,黄色三级成年人在线,后入在线

Problem A

分兩種情況：

$d$ 本身就不在 $[l,r]$ 內(nèi)：直接輸出d
否則，輸出第一個大于r的d的倍數(shù)。也就是d * (r / d + 1)

時間復雜度為 $O(q)$

#include <cstdio>

using namespace std;

typedef long long LL;

int main()
{
    int q;
    scanf("%d", &q);
    while(q--)
    {
        LL l, r, d;
        scanf("%lld%lld%lld", &l, &r, &d);
        
        if((d < l) || (d > r))
        {
            printf("%lld\n", d);
            continue;
        }

        printf("%lld\n", d * (r / d + 1));
    }
    return 0;
}

Problem B

先去掉多余的字符。只保留[，]，:，|這四種字符。
然后找最靠左的[:（兩個字符可以不用緊鄰，下同）和最靠右的:]，然后再其中間找出所有的|，拼起來就是答案的字符串了。輸出長度即可。
注意[:]的情況，這種情況是非法的。

時間復雜度為 $O(len(s))$

#include <iostream>
#include <string>

using namespace std;

typedef long long LL;

bool CheckChr(char &c)
{
    if(c == '[')return true;
    if(c == ']')return true;
    if(c == ':')return true;
    if(c == '|')return true;
    return false;
}

int FindL(string &s)
{
    int pos = 0;
    while(pos < s.length())
    {
        if(s[pos] == '[')break;
        pos++;
    }
    while(pos < s.length())
    {
        if(s[pos] == ':')break;
        pos++;
    }
    return pos;
}

int FindR(string &s)
{
    int pos = s.length() - 1;
    while(pos >= 0)
    {
        if(s[pos] == ']')break;
        pos--;
    }
    while(pos >= 0)
    {
        if(s[pos] == ':')break;
        pos--;
    }
    return pos;
}

int GetAns(string &s, int l, int r)
{
    if(l >= r)return -1;
    int ans = 4;
    for(int i = l + 1; i < r; I++)
    {
        if(s[i] == '|')ans++;
    }
    return ans;
}

int main()
{
    string s;
    while(cin >> s)
    {
        string tmp;
        for(int i = 0; i < s.length(); I++)
        {
            if(CheckChr(s[I]))
            {
                tmp += s[I];
            }
        }
        s = tmp;

        cout << GetAns(s, FindL(s), FindR(s)) << endl;
    }
    return 0;
}

Problem C

思路的出發(fā)點類似于區(qū)間覆蓋的貪心算法。
首先，對區(qū)間按左值從小到大排序。
然后將第一個區(qū)間（也就是最左邊的區(qū)間）放入集合1，從左往右遍歷：

若當前區(qū)間與集合1相交，那么將其放入集合1中
否則說明從當前區(qū)間開始往右的區(qū)間都不會跟集合1相交，將包括當前區(qū)間在內(nèi)的剩余區(qū)間置入集合2

于是我們就可以得到一種分割方法。
當然，如果這樣掃一遍發(fā)現(xiàn)所有區(qū)間都在集合1的話，直接輸出-1。

時間復雜度為 $O(Tn{\log}n)$

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct node
{
    int pos;
    int l ,r;
    int ans;
    node(int _pos = 0, int _l = 0, int _r = 0, int _ans = 0)
    {
        pos = _pos;
        l = _l;
        r = _r;
        ans = _ans;
    }
    bool operator < (const node &p)const
    {
        if(l != p.l)
        {
            return l < p.l;
        }
        return r < p.r;
    }
};

bool cmp (const node &a, const node &b)
{
    return a.pos < b.pos;
}

vector<node> v;

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        v.clear();
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; I++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            v.push_back(node(i, a, b));
        }
        sort(v.begin(), v.end());
        
        int pos = -1;
        int r = v[0].r;

        for(int i = 1; i < n; I++)
        {
            if(v[i].l > r)
            {
                pos = I;
                break;
            }
            r = max(r, v[i].r);
        }

        if(pos == -1)
        {
            printf("-1\n");
            continue;
        }
        for(int i = 0; i < n; I++)
        {
            if(i < pos)v[i].ans = 1;
            else v[i].ans = 2;
        }
        sort(v.begin(), v.end(), cmp);
        for(int i = 0; i < n; I++)
        {
            if(i)printf(" ");
            printf("%d", v[i].ans);
        }
        printf("\n");
    }
    return 0;
}

Problem D

做完之后看了一下官方題解，官方題解貌似是樹分治肛過去的。這里提供另外一種可以卡過去的方法。
首先顯然可以得出一個結(jié)論：最長鏈上所有點的權值必定是同一個質(zhì)數(shù)的倍數(shù)。
那么問題的重心便可以放在質(zhì)數(shù)上。一個簡單的思路是，枚舉所有在 $[1,max(a[i])]$ 中的質(zhì)數(shù)，對于每個質(zhì)數(shù)而言，有些點包含這個質(zhì)數(shù)（標記為1），有些點則不包含這個質(zhì)數(shù)（標記為0）。那么問題便可以轉(zhuǎn)化為，給定一個權值只有0和1的樹，找出最長的全是1的鏈。這個問題是一個簡單的樹DP，可以在 $O(n)$ 內(nèi)解決。但由于在 $[1,max(a[i])]$ 中的質(zhì)數(shù)過多（差不多是 ${\frac {max(a[i])} {10}}$ 個），所以直接做肯定是超時的。
于是考慮縮減區(qū)間范圍。注意到當質(zhì)數(shù) $p$ 大于 ${\sqrt {max(a[i])}}$ 的時候，節(jié)點中權值為質(zhì)數(shù) $p$ 的倍數(shù)的點的權值分解質(zhì)因數(shù)之后，其最大的質(zhì)因數(shù)只可能是 $p$ 。
于是便可以將這個區(qū)間分成兩個區(qū)間來解決：

枚舉區(qū)間 $[1,{\sqrt {max(a[i])}}]$ 中的質(zhì)數(shù)，套用上述的方法。時間復雜度為 $O(n{\sqrt {max(a[i])}})$ 。
對于另外的部分：
- 枚舉區(qū)間 $[1,{\sqrt {max(a[i])}}]$ 中的質(zhì)數(shù)，對于每個質(zhì)數(shù)而言，枚舉所有點，對每個點而言除掉該質(zhì)數(shù)直到無法再整除為止。時間復雜度為 $O(n{\sqrt {max(a[i])}})$ 。
- 經(jīng)過第一步的處理之后，所有的點的權值要么是1，要么就是區(qū)間 $({\sqrt {max(a[i])}},max(a[{i}])]$ 中的質(zhì)數(shù)。我們便可以使用樹DP的方法在 $O(n)$ 的時間內(nèi)找到這顆樹上除了1以外所有權值相同的鏈，取最長即可。

總的時間復雜度為 $O(n{\sqrt {max(a[i])}})$ 。

雖然基本上是卡著時間過的就是了

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

using namespace std;

struct PrimeList
{
    bool vis[200005];
    vector<int> List;
    int maxa;

    void init(int _maxa)
    {
        maxa = _maxa;
        memset(vis, 0, sizeof(vis));
        List.clear();
        for(int i = 2; i <= maxa; i++)
        {
            if(!vis[i])
            {
                List.push_back(i);
                for(int j = 2; j * i <= maxa; j++)
                {
                    vis[j * i] = true;
                }
            }
        }
    }

    bool Find(int &a)
    {
        if(a * a <= maxa)
        {
            return false;
        }
        int l = 0, r = List.size() - 1;
        while(r > l)
        {
            int mid = (l + r) >> 1;
            if(List[mid] < a)
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
        }
        return a == List[l];
    }
}P;

struct Tree
{
    int w[200005];
    vector<int> e[200005];
    int n;

    int dp[200005];
    int ans[200005];

    bool vis[200005];

    void init(int _n)
    {
        n = _n;
        for(int i = 1; i <= n; i++)
        {
            w[i] = 0;
            e[i].clear();
        }
        memset(vis, 0, sizeof(vis));
    }

    int dfs(int g, int pos = 1, int prt = -1, bool isUni = false)
    {
        dp[pos] = 0;
        ans[pos] = 0;

        if(isUni)
        {
            if(w[pos] != g)
            {
                return dp[pos];
            }
            vis[pos] = true;
        }

        for(int i = 0; i < e[pos].size(); i++)
        {
            if(e[pos][i] == prt)
            {
                continue;
            }
            dfs(g, e[pos][i], pos, isUni);
            dp[pos] = max(dp[pos], dp[e[pos][i]]);
        }

        if(w[pos] % g == 0)
        {
            priority_queue< int, vector<int>, greater<int> > q;
            for(int i = 0; i < e[pos].size(); i++)
            {
                if(e[pos][i] == prt)
                {
                    continue;
                }
                q.push(ans[e[pos][i]]);
                if(q.size() > 2)
                {
                    q.pop();
                }
            }
            if(q.size() > 0)
            {
                ans[pos] = q.top() + 1;
                q.pop();
                if(q.size() > 0)
                {
                    dp[pos] = max(dp[pos], ans[pos] + q.top());
                    ans[pos] = q.top() + 1;
                }
                else
                {
                    dp[pos] = max(dp[pos], ans[pos]);
                }
            }
            else
            {
                ans[pos] = 1;
                dp[pos] = max(dp[pos], 1);
            }
        }
        //printf("dp[%d] = %d[%d]\n", pos, dp[pos], ans[pos]);
        return dp[pos];
    }
}T;

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        T.init(n);
        int maxa = 0;
        for(int i = 1; i <= n; i++)
        {
            int a;
            scanf("%d", &a);
            T.w[i] = a;
            maxa = max(maxa, a);
        }
        for(int i = 1; i < n; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            T.e[u].push_back(v);
            T.e[v].push_back(u);
        }
        P.init(maxa);

        int ans = 0;
        for(int i = 0; (i < P.List.size()) && (P.List[i] * P.List[i] <= maxa); i++)
        {
            //printf("%d %d\n", ans, P.List[i]);
            ans = max(ans, T.dfs(P.List[i]));
            //printf("*%d\n", ans);
            for(int j = 1; j <= n; j++)
            {
                while(T.w[j] % P.List[i] == 0)
                {
                    T.w[j] /= P.List[i];
                }
            }
        }

        for(int i = 1; i <= n; i++)
        {
            if(T.vis[i])
            {
                continue;
            }
            if(P.Find(T.w[i]))
            {
                ans = max(ans, T.dfs(T.w[i], i, -1, true));
            }
        }

        printf("%d\n", ans);
    }
    return 0;
}

Problem E

首先，不管是wallet還是bill都強制翻轉(zhuǎn)成 $x<=y$ （ $h<=w$ ）的形式。
然后，對于每個輸入，如果是bill的話就去更新 $x$ 和 $y$ 的最大值，否則就拿輸入的 $h$ 和 $w$ 分別跟當前的 $x$ 和 $y$ 的最大值比較得到答案。

時間復雜度為 $O(n)$ 。

PS：這E題活的跟道簽到題似的噗。。

#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
    int x = 0, y = 0;
    int n;
    scanf("%d", &n);
    while(n--)
    {
        char s[5];
        int px, py;
        scanf("%s%d%d", s, &px, &py);
        if(px > py)
        {
            swap(px, py);
        }
        if(s[0] == '+')
        {
            x = max(x, px);
            y = max(y, py);
        }
        else
        {
            if((x > px) || (y > py))
            {
                printf("NO\n");
            }
            else
            {
                printf("YES\n");
            }
        }
    }
    return 0;
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

【Codeforces】Educational Codeforces Round #58

【Codeforces】Educational Codeforces Round #58

Problem A

Problem B

Problem C

Problem D

Problem E

后續(xù)待補充

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

【Codeforces】Educational Codeforces Round #58

Problem A

Problem B

Problem C

Problem D

Problem E

后續(xù)待補充

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av