Educational Codeforces Round 43(Div. 2) 解题报告

水题......现在最后的形式中最多一个 1，其他的全是 0。注意特判原来给的就是 0 的情况就行（我居然还在这上面挂了一发）

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
int n;
string s;
int cnt[2];

inline void solve()
{
    cin >> n >> s;
    for (auto i : s)
    {
        cnt[i - '0']++;
    }
    if (cnt[1] == 0)
        return cout << 0, void();
    cout << 1;
    for (int i = 0; i < cnt[0]; ++i)
        cout << 0;
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

B - Lara Croft and the New Game

也是水题，就按照题意分成三个部分来算一下就行。第三部分算一下奇偶即可。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
ll n, m, k;

inline void solve()
{
    cin >> n >> m >> k;
    if (k < n)
        return cout << k + 1 << " 1" << endl, void();
    else if (k < n + m - 1)
        return cout << n << " " << k - n + 2, void();
    else
    {
        k -= n + m - 1;
        ll hadhang = k / (m - 1);
        ll lefthang = k
        if (hadhang & 1)
        {
            cout << n - 1 - hadhang << ' ' << lefthang + 2 << endl;
        }
        else
        {
            cout << n - 1 - hadhang << ' ' << m - lefthang << endl;
        }
    }
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

C - Nested Segments

按照 $l$ 第一关键字从小到大，$r$ 第二关键字从大到小排序即可，这样存在解的充要条件就是存在相邻两条线段，前一条包含后一条。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
int n;
struct seg
{
    int l, r, id;
    bool operator<(const seg &x) const
    {
        if (l < x.l)
            return 1;
        if (l > x.l)
            return 0;
        if (r > x.r)
            return 1;
        return id < x.id;
    }
} s[N];

inline void solve()
{
    scanf(
    for (int i = 1; i <= n; ++i)
    {
        int l, r;
        scanf(
        s[i] = {l, r, i};
    }
    sort(s + 1, s + n + 1);
    for (int i = 1; i < n; ++i)
    {
        if (s[i + 1].l >= s[i].l && s[i + 1].r <= s[i].r)
            return printf(
    }
    puts("-1 -1");
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

D - Degree Set

这个题就有意思了（
对于一个问题 $(d_1,d_2,...,d_n)$，我们可以先拿出来 $d_1$ 个点，每个点往其他所有 $n-1$ 个点连边，这样就有了 $d_1$ 个度数为 $d_n$ 的点，这些点后面就不会再参与连边了。
现在可以发现，度数为 $d_1$ 和 $d_n$ 的点都已经有了（除了这 $d_1$ 个点之外的点此时的度数都是 $d_1$，有点绕倒是），那么我们只需要构造出 $d_2,d_3,...,d_{n-1}$ 的点了。将这 $d_1$ 个点撤去之后，也就变成了 $d_2-d_1,d_3-d_2,...,d_{n-1}-d_1$，于是就变成了更小的子问题了。
对于这个子问题，只需要 $d_{n-1}-d_1+1$ 个点就行，但是上一层的问题可能还会有多的点剩下，那么这些多的点个数就是 $(d_n -d_1 + 1) -(d_{n-1} - d_1 + 1) = d_n - d_{n-1}$ 个，让这些点后续操作都不参与就是了。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
int n;
int d[1050];
vector<pii> e;

inline void solve()
{
    scanf(
    for (int i = 1; i <= n; ++i)
        scanf(
    int rt = d[n] + 1;
    int l = 1, r = n, p = 1;
    while (p < rt && l <= r)
    {
        for (int i = p; i < p + d[l]; ++i)
            for (int j = rt; j > i; --j)
                e.push_back({i, j});
        for (int i = l + 1; i <= r; ++i)
            d[i] -= d[l];
        p += d[r] - d[r - 1] + d[l];
        l++, r--;
    }
    random_shuffle(vecall(e));
    cout << e.size() << endl;
    for (auto [u, v] : e)
        printf(
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

E - Well played!

~~（这不显然比 D 简单？）~~

显然所有的 $a$ 操作只操作同一个生物就行。接下来就是枚举操作哪个生物再 $\mathcal{O}(1)$ 判断即可。
设 $w_i$ 表示第 $i$ 个生物的原贡献。对于 $h_i-d_i>0$ 前 $b$ 大的生物，其 $w_i=h_i$，剩下的就是 $w_i=d_i$。对于枚举到的这个生物，如果原本就在前 $b$ 个之内，那么就计算一下新的贡献就行；否则，将原来 $h_i-d_i$ 最小的那个踢出去换成自己即可（如果本来满足的生物数不够 $b$ 的话，就直接用一次就行）。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
int n, a, b;
ll h[N], d[N], w[N];
ll ans;
bool vis[N];
vector<int> vec;
bool cmp(const int &x, const int &y) { return h[x] - d[x] > h[y] - d[y]; }

inline void solve()
{
    scanf(
    for (int i = 1; i <= n; ++i)
    {
        scanf(
        w[i] = d[i];
        ans += d[i];
        if (h[i] > d[i])
            vec.push_back(i);
    }
    if (b == 0)
        return cout << ans << '\n', void();
    veccmpsort(vec, cmp);
    vec.resize(b);
    ll mnh = llinf;
    for (int i = 0; i < b; ++i)
    {
        vis[vec[i]] = 1;
        ans = ans - d[vec[i]] + h[vec[i]];
        w[vec[i]] = h[vec[i]];
    }
    for (int i = 1; i <= n; ++i)
        mnh = min(mnh, w[i]);
    ll res = ans;
    for (int i = 1; i <= n; ++i)
    {
        ll tmp = res;
        ll he = h[i] * st(a);
        if (he > d[i])
        {
            if (vis[i])
                tmp += (-w[i] + he);
            else if (b > 0)
                tmp += max(0ll, he - (w[vec[b - 1]] - d[vec[b - 1]]) - w[i]);
        }
        ans = max(ans, tmp);
    }
    cout << ans << '\n';
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

F - Minimal k-covering

我还想写下界最小流来着......想了想太麻烦了（
由于每个点的度数是一定的，那么实际上我们只需要决定删除最多的边即可。
设第 $i$ 个点的度数为 $d_i$，那么只需要连一条容量为 $d_i-k$ 的边即可，二分图中间的边就改成有向边，容量为 $1$，这样，有流量的边就意味着这条边被删除了。跑最大流即可。
不过本题要求所有 $k\in[0,mind_i]$ 的答案。反着过来，每次相当于给这些边的容量 +1，再增广，这样可以加快速度。
时间复杂度为 $\mathcal{O}((n+m)^2)$

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
const int MAXN = 200050, MAXM = 200050, INF = 0x3f3f3f3f;
struct dinic
{
    struct Edge
    {
        int to, nxt, flow;
    } e[MAXM];
    int head[MAXN], ecnt = -1, dis[MAXN], cur[MAXN];
    void add_edge(int u, int v, int f)
    {
        e[++ecnt] = {v, head[u], f};
        head[u] = ecnt;
        e[++ecnt] = {u, head[v], 0};
        head[v] = ecnt;
    }
    int n, m, s, t;
    bool bfs()
    {
        memset(dis, 0, sizeof(dis));
        queue<int> q;
        dis[s] = 1;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = head[u]; ~i; i = e[i].nxt)
            {
                int v = e[i].to;
                if (!dis[v] && e[i].flow > 0)
                {
                    dis[v] = dis[u] + 1;
                    q.push(v);
                }
            }
        }
        return dis[t];
    }
    int dfs(int u, int flow)
    {
        if (u == t)
            return flow;
        int nowflow = 0;
        for (int &i = cur[u]; ~i; i = e[i].nxt)
        {
            int v = e[i].to;
            if (dis[v] == dis[u] + 1 && e[i].flow > 0)
            {
                int tmp = dfs(v, min(flow, e[i].flow));
                e[i].flow -= tmp;
                e[i ^ 1].flow += tmp;
                flow -= tmp;
                nowflow += tmp;
                if (!flow)
                    break;
            }
        }
        return nowflow;
    }
    int solve(int n, int s, int t)
    {
        this->s = s, this->t = t, this->n = n;
        int ans = 0;
        while (bfs())
        {
            memcpy(cur, head, (n + 5) * sizeof(int));
            ans += dfs(s, INF);
        }
        return ans;
    }
    void init()
    {
        ecnt = -1;
        memset(head, -1, sizeof(head));
    }
} G;

int n1, n2, m, k = inf, ansflow;
int S, T, d[N];
struct edge
{
    int x, y, id;
} e[5050];
vector<vector<int>> ans;

void getans()
{
    vector<int> vec;
    for (int i = 0; i < m; ++i)
        if (G.e[i << 1].flow != 0)
            vec.push_back(i + 1);
    ans.push_back(vec);
}

inline void solve()
{
    G.init();
    scanf(
    S = n1 + n2 + 1, T = S + 1;
    for (int i = 0; i < m; ++i)
    {
        int x, y;
        scanf(
        e[i] = {x, y, i << 1};
        G.add_edge(x, n1 + y, 1);
        d[x]++, d[n1 + y]++;
    }
    for (int i = 1; i <= n1; ++i)
        k = min(k, d[i]);
    for (int i = 1; i <= n2; ++i)
        k = min(k, d[i + n1]);
    for (int i = 1; i <= n1; ++i)
        G.add_edge(S, i, d[i] - k);
    for (int i = 1; i <= n2; ++i)
        G.add_edge(i + n1, T, d[i + n1] - k);
    ansflow = G.solve(T, S, T);
    getans();
    while (k--)
    {
        for (int i = 2 * m; i < G.ecnt; i += 2)
            G.e[i].flow++;
        ansflow = G.solve(T, S, T);
        getans();
    }
    reverse(vecall(ans));
    for (auto vec : ans)
    {
        cout << vec.size() << ' ';
        for (auto i : vec)
            cout << i << ' ';
        putchar('\n');
    }
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

Educational Codeforces Round 43(Div. 2) 解题报告

Codeforces Round #704 (Div.2) 解题报告

[Codeforces Round #716 (Div. 2)] 1514E – Baby Ehab’s Hyper Apartment

Comments NOTHING

取消回复