A 美丽的路径

题目描述

叶妹妹非常喜欢图论题,这天她出了一个图论题,有一个nn个点mm条边的无向图,其中第ii个点的点权为 ,她定义一条点数为 路径: ,..., ;其中点 与点 通过一条边直接相连 ,所以路径中可以出现重复的点。她将一条路径的美丽值定义为:假设这条路径的点数为 ,那么这条路径的美丽值就是此路径上的所有点的点权中第 小的点权。现在她会询问你是否存在起点为 号点并且终点为 号点的路径,如果存在则先输出 ,再输出存在的所有路径中的最大的美丽值;否则直接输出

输入描述:

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

对于每组样例,第一行先输入四个数 ,保证

第二行输入 个数,其中第 个数为 ,表示第 个点的点权

接下来输入 行,第 行输入两个数 ,表示点 与点 之间有一条无向边,保证
【数据规模与约定】

输出描述:

如果存在起点为 号点并且终点为 号点的路径,则第一行输出 ,第二行输出存在的所有的路径中的最大的美丽值;否则直接输出

分析:

首先,如果不存在从 的路径,则直接输出 .

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

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

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

代码实现:

#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,定义一种序列,构造方法如下:

中任意选择 次,得到了 个整数(显然数字可能相同);

将选出的 个数字排序之后得到一个序列

定义一个序列的贡献为 ,求所有本质不同的序列的贡献和。

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

(对于两个序列长度为m的序列 A、B,若 ,则序列 A、B 本质不同)

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

现在,这个重任就交给你啦!

输入描述:

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

输出描述:

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

分析:

计算每个数的贡献.

作为最大值时,有 种方案.

作为最小值时,有 种方案.

因此答案为 .

代码实现:

#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,若 ,则序列 A、B 本质不同)

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

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

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

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

现在,这个重任就交给你啦!

输入描述:

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

【数据规模与约定】

1 <= n <= 10^5, n < p < 10^9+7,保证 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 石子游戏

题目描述

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

输入描述:

第一行输入样例组数

对于每组样例来说,第一行输入两个数

第二行输入 个数,其中第 个数为

【数据规模与约定】

输出描述:

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

分析:

记差分数组 .

让每堆石子数目相同就等价于 .

随之对应的,每次操作就相当于让 .

因此只需要从前往后扫一遍 .

若当前 ,则给 这段区间加上 ,前提是 .

若当前 ,则给 这段区间加上 ,前提是 .

代码实现:

#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 树上博弈

题目描述

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

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

操作如下:

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

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

输入描述:

第一行输入一个整数 ,表示样例的组数

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

第二行输入 个整数,第 个数为 ,表示第 个点的点权为

接下来输入 行,每行输入两个整数 ,表示树上有一条从点 到点 的无向边

保证输入一定是一棵树

【数据规模与约定】

输出描述:

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

分析:

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

图片说明

改成递推就快很多了.

图片说明

代码实现:

#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 我的心是冰冰的

题目描述

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

输入描述:

第一行输入一个整数 ,表示样例的组数

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

接下来输入 行,每行输入两个整数 ,表示树上有一条从点 到点 的无向边

保证输入一定是一棵树

【数据规模与约定】

输出描述:

输出 行,每行输出一个整数 表示至少需要的颜色种类数

分析:

,则答案为 .

否则,答案为 .

代码实现:

#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 模仿游戏

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

输入描述:

第一行输入一个数 ,表示样例组数

对于每组样例,第一行先输入一个数

接下来输入 行,每行输入两个数 表示第 个怪兽出现的时间, 表示第 个怪兽的权值

【数据规模与约定】

输出描述:

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

分析:

维护优先队列 和 队列 .

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

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

每回合,尽量让泽哥哥去打 的怪兽.

详见代码.

代码实现:

#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 正十字

题目描述

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

输入描述:

第一行输入 个数,

接下来 行,每行输入 个数,第 行第 个数为 ,表示网格中第 行第 列的格子的权值为

接下来 行,每行输入四个数, ,表示询问的两个格子的坐标

【数据规模与约定】

输出描述:

输出总共 行,每行输出一个数 ,如果无法到达 ,否则表示以 为起点并且能通过平移到达 的正十字的最大边长

分析:

处理出 ,表示点 所能承受的最大正十字大小.

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

代码实现:

#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 桥

咕咕咕