CF Round #600 (Div 2) 解题报告（A~E）

A:Single Push

采用差分的思想，让(b-a=c)，然后观察(c)序列是不是一个满足要求的序列

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int T, n;
int a[maxn], b[maxn];
int c[maxn];
int main()
{
    cin >> T;
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) c[i] = 0;
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
        int flag = 1;
        for(int i = 1; i <= n; i++)
        {
            c[i] = b[i] - a[i];
            if(c[i] < 0)
            {
                puts("NO"); flag = 0;
                break;
            }
        }
        if(!flag) continue;

        for(int i = 1; i <= n; i++)
        {
            if(c[i] == 0) continue;
            for(int j = i; j <= n; j++)
            {
                if(c[i] == c[j])
                {
                    i = j;
                    continue;
                }
                else
                {
                    if(c[j] != 0)
                    {
                        flag = 0;
                        break;
                    }
                    if(c[j] == 0)
                    {
                        for(int k = j; k <= n; k++)
                        {
                            if(c[k] != 0)
                            {
                                flag = 0;
                                i = k;
                                j = k;
                                break;
                            }
                        }
                    }
                }
                if(!flag) break;
            }
            if(!flag) break;
        }
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

这份代码真是又丑又长...
看了一下CF上学了一下这个写法。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], n, T, cnt;
bool flag;
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n); cnt = 0; flag = 1;
        for(int i = 1; i <= n; i++) 
            scanf("%d", &a[i]);
        for(int i = 1, x; i <= n; i++)
        {
            scanf("%d", &x); a[i] = x - a[i];
            if(a[i] < 0) flag = 0;
            if(a[i] != a[i-1]) cnt++;
        }
        if(cnt > 2 || (cnt == 2 && a[n] != 0)) flag = 0;
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

相比我写的简洁明了了很多。

B:Silly Mistake

暴力模拟就行

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], n;
int vis[1000000+10];
int cnt, c[maxn];
int isv[1000000+10];
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    if(n % 2 == 1)
    {
        puts("-1");
        return 0;
    }

    int tot = 0, num = 0;
    vector<int> d;
    for(int i = 1, x; i <= n; i++)
    {
        x = a[i];
        if(x > 0)
        {
            if(vis[x] == 0 && isv[x] == 0)
            {
                vis[x] = 1; isv[x] = 1;
                d.push_back(x); num++;
            }

            else {
                puts("-1");
                return 0;
            }
        }


        else if(x < 0)
        {
            if(vis[abs(x)] == 1)
            {
                vis[abs(x)] = 0;
                tot += 2;
                num -= 1;
            }
            else if(vis[abs(x)] == 0)
            {
                puts("-1");
                return 0;
            }
        }
        
        if(num == 0)
        {
            c[++cnt] = tot;
            tot = 0;
            while(d.size())
            {
                int xx = d.back();
                isv[xx] = 0;
                d.pop_back();
            }
        }
    }
    if(num != 0)
    {
        puts("-1");
        return 0;
    }

    cout << cnt << endl;
    for(int i = 1; i <= cnt; i++)
        printf("%d ", c[i]);
    puts("");

    return 0;
}

C:Sweet Eating

排序+贪心+前缀和
假如说现在考虑一共吃(i)颗糖，那么首先肯定的一点是，每天吃(m)颗糖，我要尽可能的打满这(m)，很显然的贪心。
对于吃(k)颗糖，如果不考虑天数要乘上一个数，那么其实就是前缀和。
对于开启了新的一天，实际上是要把糖度高的放到第一天，然后把前面吃(i-m)颗糖的糖度加上。
这么说可能不太好理解，结合样例来看。
- 目前糖度是(2,3,4,4)，(m=2)。
- 吃(1/2)颗糖结果显然是在第一天都吃完，答案为(2,5)。
- 吃(3)颗糖的情况就需要我们开启新的一天，那么就是将(3,4)放到第一天，(2)放到第二天。
- 也就是说(2)被翻倍了。(ans(3)=sum(3)+ans(1))
- 吃(4)颗糖的情况，那其实就是要把(2,3)放到第二天，(4,4)放到第一天。(ans(4)=sum(4)+ans(2))。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int a[maxn], n, m;
ll c[maxn];
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(a+1, a+1+n);
    ll sum = 0;
    for(int i = 1; i <= n; i++)
    {
        sum += a[i]; c[i] = sum;
        if(i >= m) c[i] += c[i-m];
    }
    for(int i = 1; i <= n; i++)
        printf("%lld ", c[i]); puts("");
    return 0;
}

D: Harmonious Graph

并查集
考虑所有连通块，记录每个连通块中最大的数字。
然后枚举(i)，当(i)所在的连通块内最大的数字大于(i)时，判断(i)和(i+1)是否在一个连通块中，如果是，则跳过，否则连接(i)和(i+1)并让(ans++)。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
int n, m;

int fa[maxn], mx[maxn];
int get_fa(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = get_fa(fa[x]);
}

bool merge_dis(int x, int y)
{
    x = get_fa(x), y = get_fa(y);
    if(x == y) return false;
    fa[y] = x;
    mx[x] = max(mx[x], mx[y]);
    return true;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) fa[i] = mx[i] = i;
    for(int i = 1, x, y; i <= m; i++)
    {
        cin >> x >> y;
        merge_dis(x, y);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(mx[get_fa(i)] > i)
        {
            if(merge_dis(i, i + 1)) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

E：Antenna Coverage

(dp)，参考: https://www.cnblogs.com/Willems/p/11876315.html
考虑(f(i))表示覆盖(i)~(m)的最小花费。初态(f(m+1)=0)，最后答案为(f(1))。
倒序枚举。
当前枚举到点(i)，如果(i)已经被覆盖了，那么有(f(i)=f(i+1))。
如果(i)没有被覆盖，枚举(n)个天线，考虑左端点大于(i)的那个天线。
设(dis=x-s-i)，即覆盖到区间左端点到(i)的距离。
因为同时左右扩展，所以也向右边延伸到了(dis)。
那么有(f(i)=min{dis+f(x+s+dis)})。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 80 + 10;
const int maxm = 1e5 + 10;
int n, m, f[maxm];

struct Node{
    int l, r;
    bool operator < (Node a){
        if(a.l == l) return r < a.r;
        return l < a.l;
    }
}h[maxn];

int main()
{
    scanf("%d%d", &n, &m);
    memset(f, 0x3f, sizeof f);
    for(int i = 1, p, s; i <= n; i++)
    {
        scanf("%d%d", &p, &s);
        h[i] = {max(p-s, 1), min(p+s, m)};
    }

    sort(h+1, h+1+n);

    //for(int i=1; i<=n;i++) cout << h[i].l << " " << h[i].r << endl;

    f[m+1] = 0;
    for(int i = m; i > h[n].r; i--)
        f[i] = m - i + 1;
    for(int i = 1; i <= n; i++)
        for(int j = h[i].l; j <= h[i].r; j++)
            f[j] = 0;

    for(int i = m; i >= 1; i--)
    {
        if(!f[i]) f[i] = f[i+1];
        else
        {
            for(int j = 1; j <= n; j++)
            {
                if(h[j].l > i)
                {
                    int d = h[j].l - i;
                    int num = min(h[j].r+d, m);
                    f[i] = min(f[i], d + f[num+1]);
                }
            }
        }
    }

    cout << f[1] << endl;
    return 0;
}