2021牛客寒假算法基础集训营5【解题报告】
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 桥
咕咕咕
投递美团等公司10个岗位 >