Codeforces #611

前不知名算法竞赛选手被 div 3 血虐现场

div 3 其实有一个好，码量巨大小，但需要思考，适合康 复 训 练

round of greedy

A

倒计时，随便算个式子

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
int main()
{
    int t; read(t);
    while(t--)
    {
        int h, m; read(h, m);
        int sum = (24 - h - 1) * 60 + (60 - m);
        printf("%d\n", sum);
    }
}

B

分果子，一种特殊的平均规则，也是随便推推

#include <iostream>
using namespace std;
int main()
{
    int t; cin>>t;
    while(t--)
    {
        int a, b; cin>>a>>b;
        int res = a % b;
        if(res < b / 2) cout<<a<<endl;
        else cout<<a - res + b / 2<<endl;
    }
    return 0;
}

C

给1些链造环。突破口在于单个的点。
其实很久前应该做过类似的题，唉，老了。
提供1种比较容易实现的策略：把单个的点串起来，如果只有1个单的就串一个其他的后面，然后入/出度为零的点随意配对就好了。

#include <iostream>
using namespace std;
const long long maxn = 2e5 + 10;
long long f[maxn];
bool in[maxn], out[maxn];
long long in2[maxn], inc = 0, ou2[maxn], ouc = 0;
long long main()
{
    long long n; cin>>n;
    long long pre = 0, st = 0, cnt = 0;
    for(long long i = 1; i <= n; ++i) 
    {
        cin>>f[i];
        if(f[i]) in[f[i]] = true, out[i] = true;
    }
    for(long long i = 1; i <= n; ++i) if(!in[i] && !out[i]) ++cnt;
    if(cnt == 1)
    {
        for(long long i = 1; i <= n; ++i) if(!in[i] && !out[i]) pre = i;
        for(long long i = 1; i <= n; ++i) if(!in[i] && i != pre)
        {
            f[pre] = i;
            in[i] = true; out[pre] = true;
            break;
        }
    }
    else if(cnt > 1)
    {
        for(long long i = 1; i <= n; ++i) if(!in[i] && !out[i])
        {
            if(pre) in[f[i] = pre] = true, out[i] = true;
            pre = i;
        } 
    }
    for(long long i = 1; i <= n; ++i)
    {
        if(!in[i]) in2[inc++] = i;
        if(!out[i]) ou2[ouc++] = i;
    }
    for(long long i = 0; i < inc; ++i) f[ou2[i]] = in2[i];
    for(long long i = 1; i <= n; ++i)
        cout<<f[i]<<" ";
    return 0;
}

D

安排一些人到一些位置，使得离最近的树的距离总和最小。人不能重叠。
很经典的多源bfs模型，可是俺不会了，可恶。

#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;
queue<long long> q;
map<long long, long long> d;
vector<long long> v;
int main()
{
    long long n, m; cin>>n>>m;
    vector<long long> x(n);
    for(long long i = 0; i < n; ++i)
    {
        cin>>x[i];
        q.push(x[i]); d[x[i]] = 0;
    }
    long long ans = 0;
    while(!q.empty())
    {
        if(v.size() == m) break;
        long long k = q.front(); q.pop();
        if(d[k]) ans += d[k], v.push_back(k);
        if(!d.count(k - 1)) q.push(k - 1), d[k - 1] = d[k] + 1;
        if(!d.count(k + 1)) q.push(k + 1), d[k + 1] = d[k] + 1;
    }
    cout<<ans<<endl;
    for(auto iter : v) cout<<iter<<" ";
    return 0;
}

E

每个人可以当相邻房子或者不动。求最少/多占据房子树。
这是两个独立问题。被坑了，往dp想了。可恶。
最小的话，注意每连续三个位置，只要有东西必然最后可以只占一个位置。贪心就好了。
最大的话，每个连续段的人数大于段的长度的话，就可以往左或者往右扩展各最大一格。然后处理以下边界情况，具体就是往左边扩展的那个格会不会被上次盖到。

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 10;
int f[maxn][2], cnt[maxn];
int main()
{
    int n; cin>>n;
    for(int i = 0, j; i < n; ++i) cin>>j, ++cnt[j];
    int _min = 0;
    for(int i = 0; i <= n; ++i)
    {
        if(!cnt[i]) continue;
        else _min += 1, i += 2;
    }
    int _max = 0, len = 0;
    bool right = false;
    for(int i = 0; i <= n; ++i)
    {
        if(!cnt[i]){++len; continue;}
        int j = i, sum = 0;
        for(; cnt[j]; ++j) sum += cnt[j];
        _max += j - i;
        if(sum > j - i && (!right || len > 1)) --sum, ++_max;
        right = false;
        if(sum > j - i) ++_max, right = true;
        i = j;
        len = 1;
    }
    cout<<_min<<" "<<_max<<endl;
    return 0;
}

F

觉得是1道好题，不枉做这套题叻。
每个点的权是这个节点编号的2的幂。每个边的权是子树点权和。给每一条边的排名和对应他们的爸爸，求复原这棵树。
也事贪心，，，
诉诸这样一种策略：把相邻出现的两个点连起来，连不起来的话，就从大到小可以选的点里选一个。
这是正确的因为二的幂永远比比它小的二的幂的和要大。所以大的点不出现在这里的话也不能出现在其他地方。

#include <iostream>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
bool flag[maxn];
int main()
{
    int n; cin>>n;
    for(int i = 1; i < n; ++i) cin>>a[i];
    cout<<a[1]<<endl;
    int cur = n;
    for(int i = 1; i < n; ++i)
    {
        flag[a[i]] = true;
        while(flag[cur]) --cur;
        if(i == n - 1 || flag[a[i + 1]])
        {
            cout<<a[i]<<" "<<cur<<endl;
            flag[cur] = true;
        }
        else
        {
            cout<<a[i]<<" "<<a[i + 1]<<endl;
        }
    }
    return 0;
}