Codeforces Round 345 (Div. 1&2)

概述

除了 Div2 的两道题，其他题都挺好的，建议做（）

Div2 A

Description

有两个游戏机，当前电量分别为 $a,b$，你每秒可以给游戏机充 $1\%$ 电，另一个游戏机会损失 $2\%$ 电，问两个游戏机能同时工作的最长时间。

Solution

选择电量较小的充电然后模拟。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

int a, b;

int main()
{
    cin >> a >> b;
    if (a == 1 && b == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    int ans = 0;
    while (a > 0 && b > 0)
    {
        if (a >= b)
            b += 1, a -= 2;
        else
            a += 1, b -= 2;
        ans++;
    }
    cout << ans << endl;
}

Div2 B

Description

有 $n$ 幅画，每幅画有一个美丽值 $a_i$，你可以任意排列这些画。当一个人从一幅画走到一幅美丽值更高的画时，他的心情会增加 $1$。

求这个人从 $1$ 到 $n$ 依次经过这些画能得到的最高心情。

Solution

我们贪心地找还没选过的美丽值最小的画，然后再选比它美丽值大的美丽值最小的画。用 multiset 实现。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <set>
#include <queue>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 1e5 + 10;

std::multiset<int> S;

int n, a[maxn];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i], S.insert(a[i]);
    int cnt = 0;
    while (S.size())
    {
        int now = *S.begin();
        S.erase(S.find(now));
        auto pos = S.lower_bound(now + 1);
        while (pos != S.end())
        {
            cnt++, S.erase(pos);
            now = *pos;
            pos = S.lower_bound(now + 1);
        }
    }
    cout << cnt << endl;
}

A

Description

给出 $n$ 对坐标 $(x_i,y_i)$。求问曼哈顿距离和欧氏距离相等的坐标组 $(i,j)$（$1\leq i<j\leq n$）有多少对？$1\leq n\leq 2\times 10^5,|x_i|,|y_i|\leq 10^9$。

Solution

不难发现两个点满足题目条件当且仅当两个点横坐标相同或纵坐标相同。

容斥一下，答案等于横坐标相同的方案数 + 纵坐标相同的方案数 - 横纵坐标都相同的方案数。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <utility>
#include <map>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

typedef std::pair<int, int> pii;

std::map<int, int> mpx, mpy;
std::map<pii, int> mp;
int n;

int main()
{
    cin >> n;
    for (int i = 0, x, y; i < n; i++)
        cin >> x >> y, mpx[x]++, mpy[y]++, mp[pii(x, y)]++;
    long long ans = 0;
    for (auto k : mpx)
        ans += 1ll * k.second * (k.second - 1) / 2;
    for (auto k : mpy)
        ans += 1ll * k.second * (k.second - 1) / 2;
    for (auto k : mp)
        ans -= 1ll * k.second * (k.second - 1) / 2;
    cout << ans << endl;
}

B

Description

从第一张照片开始看，可以向左翻或者向右翻，第 $1$ 张左边是第 $n$ 张，第 $n$ 张右边是第一张，翻一次要 $a$ 时间，照片有 w 和 h 两种摆放，w 的照片要耗费 $b$ 时间翻转，看一张照片要 $1$ 个单位时间，一共有 $T$ 个单位时间，问最多可以看多少张照片？

建议看原题面。

Solution

把环变成链，然后双指针就行。

从 $l=2,r=n+1$ 开始移动指针。

判断是否合法就是长度不超过 $n$，且当前区域看照片的时间加上移动的保底时间（$r-l-1$）和折返的时间。

建议多手玩。。。。

说起来轻巧，但细节真多啊啊啊啊啊。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 1e6 + 10;

int n, a, b, t, p[maxn], ans;
char s[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> a >> b >> t >> (s + 1);
    for (int i = 1; i <= n; i++)
        p[i] = 1 + (s[i] == 'w' ? b : 0), p[i + n] = p[i];
    int l = 2, r = n + 1, sum = 0;
    for (int i = 2; i <= n + 0; i++)
        sum += p[i];
    //for (int i = 1; i <= 2 * n; i++)
    //    cout << p[i] << endl;
    while (l <= n + 1 && r <= 2 * n) 
    {
        sum += p[r], r++;
        while (r - l > n || sum + a * (std::min(r - n - 2, n - l + 1) + r - l - 1) > t)
            sum -= p[l], l++;
        ans = std::max(ans, r - l);
        //cout << l << " " << r << " " << sum << endl;
    }
    cout << ans << endl;
}

C

Description

给定一 $N\times M$ 的表格 $a$，让你对其进行压缩，使得：

每一行与每一列相对大小不变，即若 $a_{i,j}<a_{i,k}$，则压缩后的 $a_{i,j}<a_{i,k}$，对于小于及等于的情况和同列不同行的情况同理。
压缩后表格中的最大值尽量小。

输出压缩后的表格。

$1\leq n,m$ 且 $nm\leq10^6$，$a_{i,j}\leq10^9$。

Solution

发现题目唯一限制就是大小关系，很容易想到差分约束，我们对每一行和每一列，从小的连向大的，最后求一下最长路。

对于相同的数，我们用一个并查集缩成一个点。

能发现这个图是一个 DAG，我们直接 BFS 求最长路就行。

可以建一个超级源点。

Code

#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 1e6 + 10;

int n, m;

inline int id(int x, int y) { return (x - 1) * m + y; }

struct node
{
    int id, val;
    bool operator<(const node &b) const { return val < b.val; }
};

std::vector<int> e[maxn];
std::vector<node> line[maxn], row[maxn];
inline void add(int x, int y) { e[x].push_back(y); }

int father[maxn], rd[maxn], f[maxn];
int find(int x) { return x == father[x] ? x : father[x] = find(father[x]); }
inline void uni(int x, int y) { father[find(x)] = find(y); }

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1, x; j <= m; j++)
        {
            cin >> x;
            father[id(i, j)] = id(i, j);
            line[i].push_back({id(i, j), x});
            row[j].push_back({id(i, j), x});
        }
    for (int i = 1; i <= n; i++)
    {
        std::sort(line[i].begin(), line[i].end());
        for (int j = 0; j < m - 1; j++)
            if (line[i][j].val == line[i][j + 1].val)
                uni(line[i][j].id, line[i][j + 1].id);
    }
    for (int i = 1; i <= m; i++)
    {
        std::sort(row[i].begin(), row[i].end());
        for (int j = 0; j < n - 1; j++)
            if (row[i][j].val == row[i][j + 1].val)
                uni(row[i][j].id, row[i][j + 1].id);
    }
    for (int i = 1; i <= n * m; i++)
        if (find(i) == i)
            add(0, i), rd[i]++;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < m - 1; j++)
            if (line[i][j].val != line[i][j + 1].val)
                add(find(line[i][j].id), find(line[i][j + 1].id)), rd[find(line[i][j + 1].id)]++;
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < n - 1; j++)
            if (row[i][j].val != row[i][j + 1].val)
                add(find(row[i][j].id), find(row[i][j + 1].id)), rd[find(row[i][j + 1].id)]++;
    std::queue<int> q;
    q.push(0);
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int v : e[now])
        {
            f[v] = std::max(f[v], f[now] + 1);
            rd[v]--;
            if (rd[v] == 0)
                q.push(v);
        }
    }
    for (int i = 1; i <= n; i++, cout << endl)
        for (int j = 1; j <= m; j++)
            cout << f[find(id(i, j))] << " ";
}

D

Description

给定一个长度为 $n$ 的序列以及 $m$ 个操作，每个操作形如 $a_i~b_i$，表示将序列中第 $a_i$ 个数改为 $b_i$。

对于每个操作，求出序列的最长严格上升子序列长度。

注意：每个操作之间彼此独立。（即每次操作未进行时的序列是输入时的原序列，而不是上一次操作后得到的序列）

$1\leq n,m\leq4\times10^5$

Solution

下文称“最长严格上升子序列”为 LIS。

询问每次独立。求出原序列的答案之后，可以发现，每次修改之后 LIS 的变化只有以下三种：

修改之后就没法选了，LIS 长度减小 $1$，这时原 LIS 必定包括这个数；
原来 LIS 不包括这个数，改完之后就能包括了，LIS 长度增加 $1$；
其他，LIS 不变。

问题转化为修改一个数之后怎么快速求出包含这个数的 LIS 长度。

设 $f_i$ 为以 $i$ 结尾的 LIS 长度，$g_i$ 表示以 $i$ 开头的 LIS 长度。

首先求原序列，这个离散化之后用树状数组直接正着求 $f$，倒着求 $g$ 就可以。

原序列的答案就是 $ans=\max\{f_i+g_i-1\}$。

设把一个数 $i$ 修改后新的 $f_i,g_i$ 为 $f_i’,g_i’$ 。我们可以把以上的三种情况合并成 $2$ 种：

原 LIS 包括这个数，新答案为 $\max(ans-1,f_i’+g_i’-1)$。
不包括，新答案为 $\max(ans,f_i’+g_i’-1)$。

所有询问的 $f_i’,g_i’$ 可以离线之后用一样的方法求出来。（想在线可以用主席树）

现在只剩一个问题了，怎么判断一个数是否在 LIS 中？

我们对 $f_i+g_i-1=ans$ 的 $f_i$ 都存起来，如果唯一就说明一定选了这个数。

Code

有点重工业。重复的事情干很多次。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 8e5 + 10;

int n, m, tot;

int pool[maxn], a[maxn];
int f[maxn], g[maxn], cnt[maxn];
int ans = 0;

struct Q
{
    int id, val, x;
    int f, g, ans;
    bool operator<(const Q &b) const { return x == b.x ? val < b.val : x < b.x; }
} q[maxn];
bool cmpid(const Q &a, const Q &b) { return a.id < b.id; }

inline int lowbit(int x) { return x & -x; }
int t[maxn];
void modify(int x, int v)
{
    for (; x <= tot; x += lowbit(x))
        t[x] = std::max(t[x], v);
}
int query(int x)
{
    int res = 0;
    for (; x; x -= lowbit(x))
        res = std::max(res, t[x]);
    return res;
}

void init()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i], pool[++tot] = a[i];
    for (int i = 1; i <= m; i++)
        cin >> q[i].x >> q[i].val, q[i].id = i, pool[++tot] = q[i].val;
    std::sort(pool + 1, pool + 1 + tot);
    tot = std::unique(pool + 1, pool + 1 + tot) - pool - 1;
    for (int i = 1; i <= n; i++)
        a[i] = std::lower_bound(pool + 1, pool + 1 + tot, a[i]) - pool;
    for (int i = 1; i <= m; i++)
        q[i].val = std::lower_bound(pool + 1, pool + 1 + tot, q[i].val) - pool;
    for (int i = 1; i <= n; i++)
        f[i] = query(a[i] - 1) + 1, modify(a[i], f[i]);
    memset(t, 0, sizeof(t));
    for (int i = n; i >= 1; i--)
        g[i] = query(tot - a[i]) + 1, modify(tot - a[i] + 1, g[i]);
    for (int i = 1; i <= n; i++)
        ans = std::max(ans, f[i] + g[i] - 1);
    for (int i = 1; i <= n; i++)
        if (f[i] + g[i] - 1 == ans)
            cnt[f[i]]++;
} 

int main()
{
    init();
    std::sort(q + 1, q + 1 + m);
    int now = 1;
    memset(t, 0, sizeof(t));
    for (int i = 1; i <= m; i++)
    {
        while (now < q[i].x)
            modify(a[now], f[now]), now++;
        q[i].f = query(q[i].val - 1) + 1;
    }
    now = n;
    memset(t, 0, sizeof(t));
    for (int i = m; i >= 1; i--)
    {
        while (now > q[i].x)
            modify(tot - a[now] + 1, g[now]), now--;
        q[i].g = query(tot - q[i].val) + 1;
    }
    //for (int i = 1; i <= m; i++)
     //   cout << q[i].x << " " << q[i].val << " " << q[i].f << " " << q[i].g << endl;
    for (int i = 1; i <= m; i++)
    {
        if (f[q[i].x] + g[q[i].x] - 1 == ans && cnt[f[q[i].x]] == 1)
            q[i].ans = std::max(ans - 1, q[i].f + q[i].g - 1);
        else
            q[i].ans = std::max(ans, q[i].f + q[i].g - 1);
    }
    std::sort(q + 1, q + 1 + m, cmpid);
    for (int i = 1; i <= m; i++)
        cout << q[i].ans << endl;
}

E

Description

给出两棵 $n$ 个节点的树，每次操作可以把第一棵树的一条边删掉然后连两个点，且必须满足每次操作完之后仍是一棵树。

问最少需要多少步操作才能把第一棵树变成第二棵树（是完全相同，并不是同构），并输出方案。

$n \leq 5\times 10^5$。

Solution

同为 $3000+$ 分，这个题比前几天抄的一个重工业数学题CF1190F 小清新多了。

显然原来就相同的边不会被删掉，这样就得到了答案的下界。

我们尝试构造一组达到下界的解。

先 DFS 两棵树。

用并查集把这些不用修改的边缩成一个点，每个集合代表元素就是这个集合在新树中深度最小的点。

然后从原树从底向上进行操作，找到不在同一个集合的两个点，断开原来的边，连上深度大的点在新树的父亲。

因为我们是从下到上操作，相当于每次操作时都是断开原树中叶子和它父亲的边，就能保证操作是合法的。

Code

#include <iostream>
#include <set>
#include <utility>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <cctype>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 5e5 + 10;
typedef std::pair<int, int> pii;

struct Graph
{
    std::vector<int> e[maxn];
    inline void add(int x, int y) { e[x].push_back(y), e[y].push_back(x); }
    int father[maxn];
    void dfs(int x, int fa)
    {
        father[x] = fa;
        for (int v : e[x])
            if (v != fa)
                dfs(v, x);
    }
    int h[maxn], tot, vis[maxn];
    void bfs()
    {
        std::queue<int> q;
        q.push(1);
        h[++tot] = 1;
        while (!q.empty())
        {
            int x = q.front();
            vis[x] = 1, h[++tot] = x;
            q.pop();
            for (int v : e[x])
               if (!vis[v])
                   q.push(v);
        }
    }
} g1, g2;

int n;

int father[maxn];
int find(int x) { return x == father[x] ? x : father[x] = find(father[x]); }
void uni(int x, int y) { father[find(x)] = find(y); }
bool ask(int x, int y) { return find(x) == find(y); }

void solve(int x, int fa)
{
    for (int v : g1.e[x])
    {
        if (v == fa)
            continue;
        solve(v, x);
        if (!ask(v, x))
            cout << v << " " << x << " " << find(v) << " " << g2.father[find(v)] << endl;
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1, x, y; i < n; i++)
        cin >> x >> y, g1.add(x, y);
    for (int i = 1, x, y; i < n; i++)
        cin >> x >> y, g2.add(x, y);
    g1.dfs(1, 0), g2.dfs(1, 0);
    father[1] = 1;
    int ans = n - 1;
    for (int i = 2; i <= n; i++)
    {
        int f = g2.father[i];
        if (g1.father[i] == f || g1.father[f] == i)
            father[i] = f, ans--;
        else
            father[i] = i;
    }
    cout << ans << endl;
    solve(1, 0);
}

概述¶

Div2 A¶

Description¶

Solution¶

Code¶

Div2 B¶

Description¶

Solution¶

Code¶

A¶

Description¶

Solution¶

Code¶

B¶

Description¶

Solution¶

Code¶

C¶

Description¶

Solution¶

Code¶

D¶

Description¶

Solution¶

Code¶

E¶

Description¶

Solution¶

Code¶

概述

Div2 A

Description

Solution

Code

Div2 B

Description

Solution

Code

A

Description

Solution

Code

B

Description

Solution

Code

C

Description

Solution

Code

D

Description

Solution

Code

E

Description

Solution

Code