2021牛客寒假算法基础集训营5【解题报告】

A 美丽的路径

题目描述

叶妹妹非常喜欢图论题，这天她出了一个图论题，有一个nn个点mm条边的无向图，其中第ii个点的点权为 $a_i$ ，她定义一条点数为 $k$ 路径： $b_1$ ， $b_2$ ，...， $b_k$ ；其中点 $b_{i-1}$ 与点 $b_i$ 通过一条边直接相连 $(2\le i\le k)$ ，所以路径中可以出现重复的点。她将一条路径的美丽值定义为：假设这条路径的点数为 $k$ ，那么这条路径的美丽值就是此路径上的所有点的点权中第 $\lfloor k/2+1 \rfloor$ 小的点权。现在她会询问你是否存在起点为 $s$ 号点并且终点为 $t$ 号点的路径，如果存在则先输出 $YES$ ，再输出存在的所有路径中的最大的美丽值；否则直接输出 $NO$ 。

输入描述:

有多组样例，第一行输入一个数TT，表述样例组数

对于每组样例，第一行先输入四个数 $n，m，s，t$ ，保证 $1\le s\le n，1\le t\le n$

第二行输入 $n$ 个数，其中第 $i$ 个数为 $a_i$ ，表示第 $i$ 个点的点权

接下来输入 $m$ 行，第 $i$ 行输入两个数 $x_i$ 和 $y_i$ ，表示点 $x_i$ 与点 $y_i$ 之间有一条无向边，保证 $1\le x_i\le n，1\le y_i\le n$
【数据规模与约定】

$1\le T\le10，1\le n\le 2*10^5，0\le m\le2*10^5，1\le a_i\le10^9$

输出描述:

如果存在起点为 $s$ 号点并且终点为 $t$ 号点的路径，则第一行输出 $YES$ ，第二行输出存在的所有的路径中的最大的美丽值；否则直接输出 $NO$

分析：

首先，如果不存在从 $s$ 到 $t$ 的路径，则直接输出 $NO$ .

否则，二分最大美丽值，问题就变成了询问是否存在从 $s$ 到 $t$ 的路径，且这条路径点权的中位数大于等于 $mid$ .

在 $s$ 到 $t$ 的路径中，如果存在两个相邻的点且他们的点权都大于等于 $mid$ ，那么我们可以在这两个点之间来回走，使得最终路径的中位数大于等于 $mid$ .

在 $s$ 到 $t$ 的路径中，如果不存在两个相邻的点且他们的点权都大于等于 $mid$ ，那为了使得路径美丽值大于等于 $mid$ ，最终路径一定是 “点权大于等于 $mid$ 的点” 与 “点权小于 $mid$ 的点” 交替走，且起点终点的点权不能同时小于 $mid$ .

代码实现：

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

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)2e5;
const int N = (int)2e2;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

int n, m, s, t;
int cnt, head[M + 5];
struct enode
{
    int v, nx;
} Edge[M * 2 + 5];

int a[M + 5];
bool vis[M + 5];
bool vis2[M + 5];

void init()
{
    cnt = 0;
    for(int i = 1; i <= n; ++i)
    {
        head[i] = -1;
        vis[i] = 0;
    }
}

void add(int u, int v)
{
    Edge[cnt].v = v;
    Edge[cnt].nx = head[u];
    head[u] = cnt++;
}

void dfs1(int u)
{
    for(int i = head[u]; ~i; i = Edge[i].nx)
    {
        int v = Edge[i].v;
        if(vis[v]) continue;
        vis[v] = 1;
        dfs1(v);
    }
}

void dfs2(int u, int mid)
{
    for(int i = head[u]; ~i; i = Edge[i].nx)
    {
        int v = Edge[i].v;
        if(vis2[v]) continue;
        if(a[u] >= mid && a[v] < mid || a[u] < mid && a[v] >= mid)
        {
            vis2[v] = 1;
            dfs2(v, mid);
        }
    }
}

bool check(int mid)
{
    for(int i = 1; i <= n; ++i)
    {
        if(vis[i] && a[i] >= mid)
        {
            for(int j = head[i]; ~j; j = Edge[j].nx)
            {
                if(a[Edge[j].v] >= mid) return 1;
            }
        }
    }

    if(a[s] < mid && a[t] < mid) return 0;
    for(int i = 1; i <= n; ++i) vis2[i] = 0;
    vis2[s] = 1; dfs2(s, mid);
    return vis2[t];
}

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void work()
{
    n = read(); m = read(); s = read(); t = read(); init();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1, u, v; i <= m; ++i)
    {
        u = read(); v = read();
        add(u, v), add(v, u);
    }
    vis[s] = 1; dfs1(s);
    if(!vis[t]) {printf("NO\n"); return;}
    int l = 1, r = (int)1e9, mid;
    while(l < r)
    {
        mid = (l + r + 1) >> 1;
        if(check(mid))  l = mid;
        else            r = mid - 1;
    }
    printf("YES\n%d\n", r);
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int T; scanf("%d", &T);
    while(T--) work();
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

B 比武招亲（上）

题目描述

众所周知，天姐姐只喜欢天下最聪明的人，为了找到这样的人，她决定比武招亲！

只见天姐姐在榜上留下了这样一道问题，谁做出来了就可以俘获她的芳心！

爱慕天姐姐已久的泽鸽鸽问询赶来，只见榜上写着：

给定 n,mn,mn,m，定义一种序列，构造方法如下：

$1.$ 在 $[1,n]$ 中任意选择 $m$ 次，得到了 $m$ 个整数（显然数字可能相同）;

$2.$ 将选出的 $m$ 个数字排序之后得到一个序列 ${a_1,a_2,...,a_m}$ 。

定义一个序列的贡献为 $max\{a_1,a_2,...,a_m\}−min\{a_1,a_2,...,a_m\}$ ，求所有本质不同的序列的贡献和。

为了防止结果过大，将答案为 $998244353$ 取模后输出。

（对于两个序列长度为m的序列 A、B，若 $∃i∈[1,m]，A_i≠B_i$ ，则序列 A、B 本质不同）

泽鸽鸽心有余而力不足，而你作为他最好的基友决定帮助泽鸽鸽俘获美人心！

现在，这个重任就交给你啦！

输入描述:

一行输入两个正整数 n，m
【数据规模与约定】
1 <= n, m <= 5*10^5

输出描述:

一行一个整数，为答案对 998244353 取模后的结果。

分析：

计算每个数的贡献.

当 $i$ 作为最大值时，有 $\binom{i + m -2 }{i - 1}$ 种方案.

当 $i$ 作为最小值时，有 $\binom{n - i + m - 1}{n - i}$ 种方案.

因此答案为 $\sum_{i=1}^{n}{i\left[\binom{i + m -2 }{i - 1} - \binom{n - i + m - 1}{n - i}\right]}$ .

代码实现：

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

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)5e5;
const int N = (int)1e6;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

int n, m;
int a[M + 5];
ll fac[N + 5];

ll quick(ll a, ll b, ll p = mod)
{
    ll s = 1;
    while(b)
    {
        if(b & 1) s = s * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return s;
}

ll inv(ll n, ll p = mod)
{
    return quick(n, p - 2, p);
}

ll C(int n, int m)
{
    return fac[n] * inv(fac[m]) % mod * inv(fac[n - m]) % mod;
}

ll S(int k, int r)
{
    return C(k + r - 1, k - 1);
}

void work()
{
    scanf("%d %d", &n, &m);
    ll ans = 0;
    for(int i = 1; i <= n; ++i) ans = (ans + 1ll * i * S(i, m - 1)) % mod;
    for(int i = 1; i <= n; ++i) ans = (ans - 1ll * i * S(n - i + 1, m - 1)) % mod;
    ans = (ans % mod + mod) % mod;
    printf("%lld\n", ans);
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; scanf("%d", &T);
//    while(T--) work();
    fac[0] = 1; for(int i = 1; i <= N; ++i) fac[i] = fac[i - 1] * i % mod;
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

C 比武招亲（下）

题目描述

泽鸽鸽在你的帮助下成功做出了天姐姐出的第一个问题，只见天姐姐又问道：

序列长度为n，我们要按顺序填数，能填的数的范围在 [1,m]，
一个序列的贡献为序列中元素的最大值，求所有本质不同的序列的贡献和对一个质数p取模后的值。
（对于两个序列 A、B，若 ${\exists}i∈[1,n]，A_i≠B_i$ ，则序列 A、B 本质不同）

泽鸽鸽灵光一现！花了1s 就秒掉了这题。

只见天姐姐也灵光一现！突然又冒出了一个神奇的想法：

令 $m=n^{n^{n^{…}}}(无限个n)$

天姐姐说如果能做出这道题，她就愿意和泽鸽鸽在一起！

这可苦恼了泽鸽鸽，而你作为他最好的基友决定帮助泽鸽鸽俘获美人心！

现在，这个重任就交给你啦！

输入描述:

一行输入两个正整数 n, p

【数据规模与约定】

1 <= n <= 10^5, n < p < 10^9+7，保证 p 为质数

输出描述:
一行一个数表示答案

分析：

先考虑题目给的第一个问题

答案为 $\sum_{i=1}^{m}{i \left[ i^n - (i - 1)^n \right]} \% p$ ， $n$ 次多项式的前缀和为 $n + 1$ 次多项式.

记 $f(x) = \sum_{i=1}^{x}{i \left[ i^n - (i - 1)^n \right]} \% p$ ，题目即求 $f(m)$ .

于是 $f(x) = f(x + p)$ .

因此只需要求 $f(m \% p)$ ，其中 $m \% p$ 可以使用欧拉降幂求得.

之后我们可以求出 $f(1), f(2), \cdots, f(n + 2)$ ，再预处理出阶乘和逆元可以通过拉格朗日差值 $O(n)$ 得到 $f(m \% p)$ .

代码实现：

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

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)1e5;
const int N = (int)2e2;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

int n, p;
int f[M + 5];
int pre[M + 5];
int suf[M + 5];
int fac[M + 5];
int invfac[M + 5];

inline int Mod1(ll n, const int& p)
{
    return n % p;
}

inline int Mod2(ll n, const int& p)
{
    return (n % p + p) % p;
}

inline int Mod3(ll n, const int& p)
{
    return n < p ? n : n % p + p;
}

int quick1(int a, int b, int p)
{
    int s = 1;
    while(b)
    {
        if(b & 1) s = Mod1(1ll * s * a, p);
        a = Mod1(1ll * a * a, p);
        b >>= 1;
    }
    return s;
}

int quick3(int a, int b, int p)
{
    int s = 1;
    while(b)
    {
        if(b & 1) s = Mod3(1ll * s * a, p);
        a = Mod3(1ll * a * a, p);
        b >>= 1;
    }
    return s;
}

int inv(int n, int p)
{
    return quick1(n, p - 2, p);
}

int phi(int n)
{
    int ans = n;
    for(int i = 2; i * i <= n; ++i)
    {
        if(n % i == 0)
        {
            ans = ans / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    }
    if(n > 1) ans = ans / n * (n - 1);
    return ans;
}

int calc(int n, int p)
{
    if(p == 1) return Mod3(n, p);
    return quick3(n, calc(n, phi(p)), p);
}

int lang(int m)
{
    for(int i = 1; i <= n + 2; ++i)
    {
        f[i] = Mod2(f[i - 1] + 1ll * i * (quick1(i, n, p) - quick1(i - 1, n, p)), p);
    }
    if(m <= n + 2)  return Mod1(f[m], p);
    pre[1] = 1; fac[0] = invfac[0] = 1; fac[1] = 1;
    for(int i = 2; i <= n + 2; ++i)
    {
        pre[i] = Mod1(1ll * pre[i - 1] * (m - i + 1), p);
        fac[i] = Mod1(1ll * fac[i - 1] * i, p);
    }
    suf[n + 2] = 1; invfac[n + 2] = inv(fac[n + 2], p);
    for(int i = n + 1; i >= 1; --i)
    {
        suf[i] = Mod1(1ll * suf[i + 1] * (m - i - 1), p);
        invfac[i] = Mod1(1ll * invfac[i + 1] * (i + 1), p);
    }
    int ans = 0, up, dn;
    for(int i = 1; i <= n + 2; ++i)
    {
        up = Mod1(1ll * Mod1(1ll * pre[i] * suf[i], p) * f[i], p);
        dn = Mod1(((n + 2 - i) & 1 ? -1ll : 1ll) * invfac[i - 1] * invfac[n + 2 - i], p);
        ans = Mod1(1ll * ans + Mod1(1ll * up * dn, p), p);
    }
    ans = Mod2(ans, p);
    return ans;
}

void work()
{
    scanf("%d %d", &n, &p);
    int m = calc(n, p) % p;
    printf("%d\n", lang(m));
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; scanf("%d", &T);
//    while(T--) work();
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

D 石子游戏

题目描述

叶妹妹很喜欢玩石头，于是这天泽鸽鸽给她出了一道石子游戏，规则是这样的：有 $n$ 堆石子排成一行，其中第 $i$ 堆石子有 $a_i$ 个，叶妹妹可以选择做无数次这种操作：每次操作把连续相邻的 $k$ 个石子堆中的每堆石子数目加一，请问叶妹妹能否让每堆石子的数目都相同呢？叶妹妹觉得这题太简单了，于是丢给了聪明的你，快来解决这个问题吧！

输入描述:

第一行输入样例组数 $T$

对于每组样例来说，第一行输入两个数 $n$ 和 $k$

第二行输入 $n$ 个数，其中第 $i$ 个数为 $a_i$

【数据规模与约定】

$1\le T\le 10，1\le n\le10^5，1\le k\le n，0\le a_i\le 10^9$

输出描述:

输出总共 $T$ 行，对于每组样例来说，如果能使每堆石子的数目都相同则输出一个整数 $x$ ， $x$ 表示达到相同时的最少的操作数；否则输出 $-1$

分析：

记差分数组 $b[i] = a[i] - a[i - 1] \; (i \geq 2)$ .

让每堆石子数目相同就等价于 $b[i] \; (i \geq 2)$ 全 $0$ .

随之对应的，每次操作就相当于让 $b[i] \leftarrow b[i] + 1,\; b[i + k] \leftarrow b[i + k] - 1 \; (2 \leq i \leq n - k + 1)$ .

因此只需要从前往后扫一遍 $b[i] \; (i \geq 2)$ .

若当前 $b[i] < 0$ ，则给 $[i, i + k - 1]$ 这段区间加上 $|b[i]|$ ，前提是 $i + k - 1 \leq n$ .

若当前 $b[i] > 0$ ，则给 $[1, i - 1]$ 这段区间加上 $|b[i]|$ ，前提是 $i \% k == 1$ .

代码实现：

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

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)1e5;
const int N = (int)1e6;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

int n, k;
int a[M + 5];
ll b[M + 5];

/**
2
5 3
1 2 1 2 3
5 1
2 1 1 2 3

**/

void work()
{
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 2; i <= n; ++i) b[i] = a[i] - a[i - 1];
    ll ans = 0;
    for(int i = 2; i <= n; ++i)
    {
        if(b[i] < 0)
        {
            if(i + k > n + 1)
            {
                printf("-1\n");
                return;
            }
            ans -= b[i];
            b[i + k] += b[i];
            b[i] = 0;
        }
        else if(b[i] > 0)
        {
            if((i - 1) % k)
            {
                printf("-1\n");
                return;
            }
            ans += (i - 1) / k * b[i];
            b[i] = 0;
        }
    }
    printf("%lld\n", ans);
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int T; scanf("%d", &T);
    while(T--) work();
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

E 树上博弈

题目描述

叶妹妹非常喜欢在树上玩博弈游戏，这天叶妹妹和泽鸽鸽遇到了一个有趣的树上博弈游戏。

游戏规则是：给定一颗有 $n$ 个点的无根树，第 $i$ 个点的权值为 $a_i$ ，叶妹妹与泽鸽鸽轮流执行操作。

操作如下：

选择一个度数为11的节点(即叶子节点)，自己的得分加上该点的权值
删去这个节点以及该节点的所有邻接的边

当树上没有点了则表示游戏结束，现在规定由叶妹妹先执行操作，双方都想让自己得分与对方得分的差值尽可能大(即尽可能让自己多得分，并且尽可能让对方少得分)，假设叶妹妹和泽鸽鸽都以最优的策略玩这个游戏，求游戏结束时叶妹妹与泽鸽鸽分数的差值是多少？

输入描述:

第一行输入一个整数 $T$ ，表示样例的组数

每组样例的第一行输入一个整数 $n$

第二行输入 $n$ 个整数，第 $i$ 个数为 $a_i$ ，表示第 $i$ 个点的点权为 $a_i$

接下来输入 $n-1$ 行，每行输入两个整数 $u$ ， $v$ ，表示树上有一条从点 $u$ 到点 $v$ 的无向边 $(1\le u\le n，1\le v\le n)$

保证输入一定是一棵树

【数据规模与约定】

$1 \le T \le 50，1 \le n \le 20，-10^9\le a_i\le 10^9$

输出描述:

输出 $T$ 行，每行输出一个数字 $x$ ， $x$ 表示游戏结束叶妹妹与泽鸽鸽分数的差值

分析：

赛时用记忆化搜索 + 卡常艹过去了.

图片说明

改成递推就快很多了.

图片说明

代码实现：

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

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)20;
const int N = (int)1e6;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

int n, m;
int a[M];
int con[M];
int cnt[1<<M];
int one[1<<M][M], oneLen[1<<M];
ll f[1<<M];

inline bool valid(const int& i)
{
    int c = 2 * cnt[i];
    for(int j = 0; j < oneLen[i] && one[i][j] < n; ++j)
    {
        c -= cnt[i & con[one[i][j]]];
    }
    return c == 2;
}

void work()
{
    scanf("%d", &n); m = (1<<n);
    for(int i = 0; i < n; ++i) scanf("%d", &a[i]), con[i] = 0;
    for(int i = 2, u, v; i <= n; ++i)
    {
        scanf("%d %d", &u, &v);
        --u, --v;
        con[u] |= (1<<v), con[v] |= (1<<u);
    }
    f[0] = 0;
    for(int i = 1; i < m; ++i)
    {
        if(!valid(i)) continue;
        if(n - cnt[i] & 1)  //泽哥哥
        {
            f[i] = inf;
            for(int j = 0, p, k; j < oneLen[i]; ++j)
            {
                p = one[i][j], k = (i&con[p]);
                if(!(k & k-1))
                {
                    f[i] = min(f[i], f[i^(1<<p)] - a[p]);
                }
            }
        }
        else
        {
            f[i] = -inf;
            for(int j = 0, p, k; j < oneLen[i]; ++j)
            {
                p = one[i][j], k = (i&con[p]);
                if(!(k & k-1))    f[i] = max(f[i], f[i^(1<<p)] + a[p]);
            }
        }
    }
    printf("%lld\n", f[m - 1]);
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    for(int i = 1; i < (1<<M); ++i)
    {
        cnt[i] = cnt[i&(i - 1)] + 1;
        for(int j = 0; j < M; ++j)
        {
            if(i>>j&1)      one[i][oneLen[i]++] = j;
        }
    }
    int T; scanf("%d", &T);
    while(T--) work();
//    work();
    return 0;
}

F 我的心是冰冰的

题目描述

泽鸽鸽很喜欢王冰冰，为了证明他是否配得上冰冰，叶妹妹出了一道题来考他：给定了一棵有 $n$ 个点的树，你需要对树的每个点进行染色，且要求每两个相邻(即有边相连)的点颜色不同，叶妹妹想知道至少需要拥有多少种不同的颜色才能完成这种染色？泽鸽鸽觉得这题太简单了，于是聪明的你快来解答吧！

输入描述:

第一行输入一个整数 $T$ ，表示样例的组数

每组样例的第一行输入一个整数 $n$

接下来输入 $n-1$ 行，每行输入两个整数 $u$ 和 $v$ ，表示树上有一条从点 $u$ 到点 $v$ 的无向边 $(1\le u\le n，1\le v\le n)$

保证输入一定是一棵树

【数据规模与约定】

$1 \le T \le 50，1 \le n \le 10^5$

输出描述:

输出 $T$ 行，每行输出一个整数 $x$ ， $x$ 表示至少需要的颜色种类数

分析：

若 $n = 1$ ，则答案为 $1$ .

否则，答案为 $2$ .

代码实现：

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

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)1e5;
const int N = (int)5e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;

int n;
int out[M + 5];

void work()
{
    scanf("%d", &n);
    for(int i = 1; i <= n - 1; ++i) scanf("%*d %*d");
    if(n == 1)  printf("1\n");
    else        printf("2\n");
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int T; scanf("%d", &T);
    while(T--) work();
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

G 模仿游戏

题目描述
有一天叶妹妹和泽鸽鸽他们一起参加一个模仿游戏，这个游戏主要任务是打怪兽，每个怪兽都有一个权值，如果两个怪兽的权值相同，那么表示这两个怪兽是同一类型的怪兽。对于任何一个怪兽，只能由一个人去打败它，并且一个人无法同时打两只及两只以上的怪兽。泽鸽鸽和叶妹妹打败任何一个怪兽都只需要花费一分钟，并且他们只能在整数分钟去打怪兽，不能出现小数分钟。由于这是模仿游戏，因此叶妹妹只能模仿泽鸽鸽去打败怪兽。比如，当泽鸽鸽在之前已经打败了权值为 $x$ 的怪兽后，叶妹妹才能去打权值为 $x$ 的怪兽（即相同类型的怪兽）。现在给出每个怪兽的出现时间和权值，请你设计一个最优的顺序使得所有怪兽都被打败后的时间最早！

输入描述:

第一行输入一个数 $T$ ，表示样例组数

对于每组样例，第一行先输入一个数 $n$

接下来输入 $n$ 行，每行输入两个数 $a_i$ 和 $b_i$ 表示第 $i$ 个怪兽出现的时间， $b_i$ 表示第 $i$ 个怪兽的权值

【数据规模与约定】

$1\le T\le 20，1\le n\le 10^5，1\le a_i\le 10^5，1\le b_i\le n$

输出描述:

输出 $T$ 行，每行输出一个数 $x$ ，表示最优顺序下所有怪兽都被打败后的最早时间

分析：

维护优先队列 $q1$ 和队列 $q2$ .

$q1$ 存的是只能被泽哥哥打的怪兽，按照下一只同类怪兽的出现时间排序.

$q2$ 存的是可以被叶妹妹打的怪兽.

每回合，尽量让泽哥哥去打 $q1$ 的怪兽.

详见代码.

代码实现：

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

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)1e5;
const int N = (int)2e2;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int n;
struct node
{
    int a, b;
    bool operator<(const node& b)const
    {
        return a < b.a;
    }
} s[M + 5];

int nx[M + 5];
int cnt[M + 5];
bool vis[M + 5];

struct qnode
{
    int b, nx;
    qnode(int _b = 0, int _nx = 0): b(_b), nx(_nx){}
    bool operator<(const qnode& b)const
    {
        return nx > b.nx;
    }
};

priority_queue<qnode> q1;
queue<qnode> q2;

void work()
{
    n = read();
    for(int i = 1; i <= n; ++i) s[i].a = read(), s[i].b = read();
    sort(s + 1, s + n + 1);
    memset(nx, -1, sizeof(nx));
    memset(cnt, 0, sizeof(cnt));
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; ++i)
    {
        if(nx[s[i].b] == -1)         nx[s[i].b] = M + 1;
        else if(nx[s[i].b] == M + 1) nx[s[i].b] = s[i].a;
    }
    for(int i = 1, p = 1; i <= 2 * M; ++i)
    {
        while(p <= n && s[p].a <= i)
        {
            if(vis[s[p].b]) q2.push(qnode());
            else
            {
                if(!cnt[s[p].b]) q1.push(qnode(s[p].b, nx[s[p].b]));
                ++cnt[s[p].b];
            }
            ++p;
        }

        if(!q2.empty()) q2.pop();
        if(!q1.empty())
        {
            int b = q1.top().b; q1.pop();
            vis[b] = 1;
            while(--cnt[b]) q2.push(qnode());
        }
        else if(!q2.empty()) q2.pop();

        if(p == n + 1 && q1.empty() && q2.empty())
        {
            printf("%d\n", i);
            return;
        }
    }
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int T; scanf("%d", &T);
    while(T--) work();
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

H 白色长方形

咕咕咕

I 正十字

题目描述

叶妹妹最近遇到了一个简单题，在一个 $n*m$ 的网格中，每个格子的权值要么是 $0$ ，要么是 $1$ 。 $0$ 表示这个格子为空，可以停留或者经过这个格子； $1$ 表示这个格子有障碍物，无法停留也无法经过这个格子。现在定义一个边长为 $k$ 的正十字是以一个格子为中心，然后这个格子连续向上，向下，向左，向右都连续拓展 $k$ 个格子，这 $4*k+1$ 格子都属于这个边长为 $k$ 的正十字，并且正十字里面的所有格子权值都必须为 $0$ 。我们规定正十字能经过一个点，表示这个正十字的中心能经过这个点。在不越界和不遇到障碍物的情况下，正十字可以通过上下左右四个方向进行平移。现在有 $Q$ 个询问，每次给你两个格子的坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$ ，请问以 $(x_1,y_1)$ 为起点并且能通过平移到达 $(x_2,y_2)$ 的正十字的边长最大是多少呢？如果无法到达则输出 $-1$ （正十字一定要经过起点， $1\le x_1\le n，1\le x_2\le n，1\le y_1\le m，1\le y_2\le m$

输入描述:

第一行输入 $3$ 个数， $n$ ， $m$ ， $Q$

接下来 $n$ 行，每行输入 $m$ 个数，第 $i$ 行第 $j$ 个数为 $a[i][j]$ ，表示网格中第 $i$ 行第 $j$ 列的格子的权值为 $a[i][j]$

接下来 $Q$ 行，每行输入四个数， $x_1,y_1,x_2,y_2$ ，表示询问的两个格子的坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$

【数据规模与约定】

$1\le n\le 1000，1\le m\le 1000，1\le Q\le 10^5$

输出描述:

输出总共 $Q$ 行，每行输出一个数 $x$ ，如果无法到达 $x=-1$ ，否则 $x$ 表示以 $(x_1,y_1)$ 为起点并且能通过平移到达 $(x_2,y_2)$ 的正十字的最大边长

分析：

处理出 $f[i][j]$ ，表示点 $(i,j)$ 所能承受的最大正十字大小.

之后倒序枚举最大正十字大小，再枚举询问，用并查集维护连通性.

代码实现：

#include <cstdio>
#include <vector>
#include <ctype.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const int M = (int)1e3;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)998244353;

int n, m, q;
int s[M + 5][M + 5];
vector< pair<int, int> > v[M + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int x1[N + 5], y1[N + 5];
int x2[N + 5], y2[N + 5];
int fa[M * M + 5];
int ans[N + 5];
bool vis[M + 5][M + 5];

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void print(int n)
{
    if(n < 0)
    {
        putchar('-');
        print(-n);
    }
    else
    {
        if(n > 9) print(n / 10);
        putchar(n % 10 + '0');
    }
}

inline int getS(const int& x1, const int& y1, const int& x2, const int& y2)
{
    return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}

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

int calc(const int& x1, const int& y1, const int& d)
{
    int l = 0, r = M, mid, x2, y2, mix, miy, mxx, mxy;
    while(l < r)
    {
        mid = (l + r + 1) >> 1;
        x2 = x1 + mid * dx[d], y2 = y1 + mid * dy[d];
        mix = min(x1, x2), miy = min(y1, y2);
        mxx = max(x1, x2), mxy = max(y1, y2);
        if(x2 < 1 || x2 > n || y2 < 1 || y2 > m || getS(mix, miy, mxx, mxy)) r = mid - 1;
        else                                                                 l = mid;
    }
    return r;
}

int tofind(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = tofind(fa[x]);
}

void work()
{
    n = read(); m = read(); q = read();
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            fa[id(i, j)] = id(i, j);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + read();
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if(getS(i, j, i, j) == 1) continue;
            int mi = inf;
            for(int k = 0; k < 4; ++k) mi = min(mi, calc(i, j, k));
            v[mi].push_back(make_pair(i, j));
        }
    }
    for(int i = 1; i <= q; ++i)
    {
        ans[i] = -1;
        x1[i] = read(); y1[i] = read();
        x2[i] = read(); y2[i] = read();
    }
    for(int i = M; i >= 0; --i)
    {
        for(auto& p: v[i])
        {
            vis[p.first][p.second] = 1;
            for(int k = 0; k < 4; ++k)
            {
                int x = p.first + dx[k], y = p.second + dy[k];
                if(x < 1 || x > n || y < 1 || y > m || !vis[x][y])    continue;
                int u = tofind(id(p.first, p.second)), v = tofind(id(x, y));
                if(u != v) fa[u] = v;
            }
        }
        for(int j = 1; j <= q; ++j)
        {
            if(~ans[j]) continue;
            if(vis[x1[j]][y1[j]] && vis[x2[j]][y2[j]]
               && tofind(id(x1[j], y1[j])) == tofind(id(x2[j], y2[j]))) ans[j] = i;
        }
    }
    for(int i = 1; i <= q; ++i) print(ans[i]), putchar('\n');
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; scanf("%d", &T);
//    while(T--) work();
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

J 桥

咕咕咕