week4

2021-08-01

第四周

Cherry（cf）

链接：

https://codeforces.com/contest/1554/problem/A

思路：

刚开始又大又小的没看明白，但其实结果就是输出一个连续子数组里最大值和最小值的乘积最大值，其实没那么麻烦，只需要保证子数组长度为2，那么一定有一个最大和一个最小值，从头到尾遍历一遍即可

俺是一坨垃圾代码QWQ:

int main()
{
    fast;
    int t;
    cin >> t;
    while(t--)
    {
        ll n;
        cin >> n;
        vector<ll> v(n);
        ll mx = 0;
        for (int i = 0;i<n;i++)
        {
            cin >> v[i];
        }
        for (int i = 1; i < n - 1;i++)
        {
            mx = max(mx, v[i - 1] * v[i]);
            mx = max(mx, v[i +1] * v[i]);
        }
        if(n==2)
            cout << v[0] * v[1] << endl;
        else
            cout << mx << endl;
    }
    return 0;
}

Cobb（cf）

链接：

https://codeforces.com/contest/1554/problem/B

思路：

他给了一个公式，要求输出整个数组中能够通过这个公式输出的最大值。观察这个公式，我们不难发现有四个分为两组的变量，一组是i*j,另一组是k*(ai|aj)，我们需要前一组的值尽量大，后一组的值尽量小。前面一组，我们尽量保持i，j相间，这样能尽可能保证结果最大，而后面那一组，暴力就完了，n^2跑一下就妥了

俺是一坨垃圾代码QWQ:

int main()
{
    fast;
    int t;
    cin >> t;
    while(t--)
    {
        ll n,k;
        cin >> n>>k;
        vector<ll> v(n+1);
        ll mx = -MAX;
        for (int i = 1;i<=n;i++)
        {
            cin >> v[i];
        }
        for (ll i = n; i >= 2;i--)
        {
            for (ll j = i - 1; j >= 1;j--)
            {
                if(mx<=i*j)
                    mx = max(mx, i * j - k * (v[i] | v[j]));
                else
                    break;
            }
        }
        cout << mx << endl;
    }
    return 0;
}

PizzaForces（cf）

链接：

https://codeforces.com/contest/1555/problem/A

思路：

最小也得切6块，所以6块以下都需要15分钟，设分别需要小中大号披萨各a b c个，则可以得出一共需要6a+8b+10c=2(3a+4b+5c)块披萨,需要15a+20b+25c=5(3a+4b+5c)minutes，而需要的披萨数>=朋友数时才行，所以如果朋友是奇数的话还要多加一个黛苏珂来凑数，这样就能够刚好用最少的分钟数做出刚刚好的披萨，需要的分钟数自然就是x/2*5了！

int main()
{
    int t;
    cin>>t;
    ll x;
    while(t--)
    {
        cin >> x;
        if(x<=6)
            cout << 15 << endl;
        else
        {
            if(x%2)
            {
                x ++;
            }
            cout << x / 2 * 5 << endl;
        }
    }
}

Two Tables（cf）

链接：

https://codeforces.com/contest/1555/problem/B

思路：

分类讨论到极致，差点把自己整吐了，以后遇到这种题千万不要用脑子硬想，一定要动笔。大概说说思路，剩下的长度和宽度均不够的情况，肯定是不行的，输出-1，在剩下的高度或宽度够第二个矩形时，不需要移动。接下来分两种情况，如果宽度够，和宽度不够。宽度够的话，需不需要移动，需要移动宽的话，那不移动时的高度够不够……不说了，就这么疯狂分类讨论，别漏了就行，看代码。

int main()
{
    //fast;
    int t;
    cin>>t;
    while(t--)
    {
        int W, H, x1, y1, x2, y2, w, h,w1,w2,h1,h2;
        cin >> W >> H >> x1 >> y1 >> x2 >> y2 >> w >> h;
        if(W-(x2-x1)<w&&H-(y2-y1)<h)
            cout << -1 << endl;
        else
        {
            int res = MAX;
            w1 = x1;
            w2 = W - x2;
            h1 = y1;
            h2 = H - y2;
            if(W-(x2-x1)>=w)
                if(x1>=w||W-x2>=w)
                    res = 0;
                else
                {
                    res = min(res, w - x1);
                    res = min(res, w - w2);
                    if(H-(y2-y1)>=h)
                        if(y1>=h||H-y2>=h)
                        res = 0;
                        /*else
                        {
                            res = min(res, h - y1);
                            res = min(res, h - h2);
                        }*/
                    else
                    {
                    res = min(res, h - y1);
                    res = min(res, h - h2);
                    }
                }
            else//chang bu gou
            {
                if(H-(y2-y1)>=h)
                    if(y1>=h||H-y2>=h)
                        res = 0;
                        else
                        {
                            res = min(res, h - y1);
                            res = min(res, h - h2);
                        }
            }
            printf("%.9lf\n", (double)res);
        }
 
    }
}

Coin Rows（cf）

链接：

https://codeforces.com/contest/1555/problem/C

思路：

这应该是本场里最简单的题，竟然放在c的位置，可坑死我了，最后40s内才AC,不多说了，就一暴力前缀和贪心，因为是二维的，所以先手一定会有一个拐点，会把两条路线分为左下和右上两个部分，求他们两个的最大值，在求这些最大值里最小的，就是答案（代码不建议参考，刚开始想错了，最后一分钟紧急修改，因为是前缀和，所以根本不需要a,b数组，找最小值也不需要弄set里这么麻烦）

int main()
{
    //fast;
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<int> a(n+1),a1(n+1),b1(n+1), b(n+1);
        for (int i = 1;i<=n;i++)
            {
                cin >> a[i];
                a1[i] += a1[i - 1]+a[i];
            }
        for (int i = 1; i <= n;i++)
            {
                cin >> b[i];
                b1[i] += b1[i - 1]+b[i];
            }
        int mx=0;
        queue<int> q;
        for (int i = 1; i <= n;i++)
        {
            if(a[i]+b[i]>mx)
            {
                mx = a[i] + b[i];
            }
        }
        for (int i = 1; i <= n;i++)
        {
                q.push(i);
        }
        set<int>lly;
        while(!q.empty())
        {
            lly.insert(max(b1[q.front() - 1], a1[n] - a1[q.front()]));
            q.pop();
        }
        cout << *lly.begin() << endl;
    }
}

Gregor and Cryptography（cf）

链接：

https://codeforces.com/contest/1549/problem/A

思路：

对于所有的质数，对2除余一定等于1，对自己本身-1除余也一定等于一

int main()
{
    fast;
    int t;
    cin >> t;
    while(t--)
    {
        int x;
        cin >> x;
        cout << 2 << " " <<x - 1 << endl;
    }
}

Gregor and the Pawn Game（cf）

链接：

https://codeforces.com/contest/1549/problem/B

思路：

根据题目模拟，注意斜着走后的棋子的标记

int main()
{
    fast;
    int t;
    cin >> t;
    while(t--)
    {
        int x;
        cin >> x;
        string a, b,c;
        cin >> a >> b;
        c = a;
        int cnt = 0;
        for (int i = 0; i < x;i++)
        {
            if(b[i]=='1')
            {
                if(a[i]=='0')
                {
                    a[i] = '2';
                    b[i] = '0';
                    cnt++;
                }
                else if(a[i]=='1')
                {
                    if(i>0&&a[i-1]=='1'&&c[i-1]!='2')
                    {
                        cnt++;
                        c[i-1] ='2';
                        b[i] = '0';
                    }
                    else if (i<x-1&&a[i + 1] == '1'&&c[i+1]!='2')
                    {
                        cnt++;
                        c[i + 1] = '2';
                        b[i] = '0';
                    }
                }
            }
        }
        cout << cnt<<endl;
    }
}

Gregor and the Pawn Game（cf）

链接：

https://codeforces.com/contest/1549/problem/B

思路：

根据题目模拟，注意斜着走后的棋子的标记

int main()
{
    fast;
    int t;
    cin >> t;
    while(t--)
    {
        int x;
        cin >> x;
        string a, b,c;
        cin >> a >> b;
        c = a;
        int cnt = 0;
        for (int i = 0; i < x;i++)
        {
            if(b[i]=='1')
            {
                if(a[i]=='0')
                {
                    a[i] = '2';
                    b[i] = '0';
                    cnt++;
                }
                else if(a[i]=='1')
                {
                    if(i>0&&a[i-1]=='1'&&c[i-1]!='2')
                    {
                        cnt++;
                        c[i-1] ='2';
                        b[i] = '0';
                    }
                    else if (i<x-1&&a[i + 1] == '1'&&c[i+1]!='2')
                    {
                        cnt++;
                        c[i + 1] = '2';
                        b[i] = '0';
                    }
                }
            }
        }
        cout << cnt<<endl;
    }
}

Web of Lies（cf）

链接：

https://codeforces.com/contest/1549/problem/C

思路：

在每次查询后，朋友是会复活的，所以增删边是不对结果有影响的。通过题意可以看出，在一次查询过后，场上不再会有朋友关系，一定会留下来最大的。所以只需要维护一个数组，在建边时较小的那个之后一定会死，标记上。总的减去标记的就是答案

int main()
{
    fast;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m;i++){
        int x, y;
        cin >> x >> y;
        solve(x, y);
    }
    int q;
    cin >> q;
    while (q--)
    {
        int t;
        cin >> t;
        if(t==3){
            cout << n - killed << endl;
        }
        else if(t==1){
            int x, y;
            cin >> x >> y;
            solve(x, y);
        }
        else{
            int x, y;
            cin >> x >> y;
            if(x<y){
                vis[x]--;
                if(vis[x]==0)
                    killed--;
            }
            else{
                vis[y]--;
                if(vis[y]==0)
                    killed--;
            }
        }
    }
    
    return 0;
}