P14053 [SDCPC 2019] Median 题解

P14053 [SDCPC 2019] Median 题解

一道水题。

观察题意，很快我们可以发现，对于元素 \(i\)，其合不合法取决于一定大于 \(i\) 的数的个数与一定小于 \(i\) 的数的个数。

这时，我们只需要统计有多少数大于 \(i\)，与多少数小于 \(i\) 即可。

只要大于 \(i\) 的数的个数与一定小于 \(i\) 的数的个数均小于等于比中位数大或小的个数即可，也就是 \((n + 1) / 1 - 1\)。

接下来取出核心算法。

floyd 传递闭包。

首先我们发现，对于每对关系 \([a_i,b_i]\) 都一定有 \(a_i > b_i\)。

那么如果有 \(a > b\)、\(b > c\)，那么一定有 \(a > c\)。

这种关系是可以传递的！

那么我们考虑如何将这种关系下放。

观察数据范围，发现 \(n \leq 100\)，这说明本题可能需要 \(O(n ^ 3)\) 及以上的时间复杂度。

所以我们自然而然地想到floyd传递闭包。

所谓floyd传递闭包，就是用floyd将可传递的关系传递。

核心代码:

	for(int k = 1;k <= n;k ++) // 枚举中间值（即 a > b,b > c 中的 b ）{for(int i = 1;i <= n;i ++) //枚举关系的两端{for(int j = 1;j <= n;j ++){a[i][j] |= a[i][k] & a[k][j]; // 如果 i > k 并且 k > j 则 i > j}}}

然后对于每个 \(i\) 我们知道了所有比它大的关系数，同理可以求出比它小的关系数。

然后直接判断是否可行即可。

判无解只需要判断是否有不合法关系即可，即 \(a > b\) 并且 \(b > a\)。

下面放上完整代码。

#include<bits/stdc++.h>
#define int long long 
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define Blue_Archive return 0
using namespace std;
constexpr int N = 100 + 3;
constexpr char me[] = "終末なにしてますか？忙しいですか？救ってもらっていいですか？";int T;
int n;
int m;
int a[N][N]; // a[i][j] 表示 i > j
int b[N][N]; // b[i][j] 表示 i < jinline int read() // 快读
{int k = 0,f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();}while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + c - '0',c = getchar_unlocked();return k * f;
}inline void write(int x) // 快写
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline void clear() // 多测清空
{for(int i = 1;i <= n;i ++) {for(int j = 1;j <= n;j ++){a[i][j] = b[i][j] = 0;}}
}signed main()
{// freopen("data.in","r",stdin);freopen("data.out","w",stdout);T = read();while(T --){clear();n = read();m = read();bool flag = 1; // 记录是否合法for(int i = 1,x,y;i <= m;i ++){x = read();y = read();a[x][y] = 1;b[y][x] = 1;}for(int k = 1;k <= n;k ++) // floyd 传递闭包{for(int i = 1;i <= n;i ++){for(int j = 1;j <= n;j ++){a[i][j] |= a[i][k] & a[k][j];b[i][j] |= b[i][k] & b[k][j];}}}for(int i = 1;i <= n;i ++) // 判无解{for(int j = 1;j <= n;j ++){if(a[i][j] && a[j][i]) flag = 0;}}if(flag == 0) {for(int i = 1;i <= n;i ++) putchar_unlocked('0');ent;continue;}int op = (n + 1) / 2 - 1;for(int i = 1,mx,mn;i <= n;i ++){if(a[i][i]) {putchar_unlocked('0');continue;}mx = mn = 0;bool can = 1;for(int j = 1;j <= n;j ++) // 记录比 i 大的数，与比 i 小的数{if(a[i][j] && b[i][j]) {can = 0;break;}if(a[i][j]) mn ++;if(b[i][j]) mx ++;}if(!can) putchar_unlocked('0');else if(mn <= op && mx <= op) putchar_unlocked('1');else putchar_unlocked('0');}ent;}Blue_Archive;
}

## P14053 [SDCPC 2019] Median 题解一道水题。观察题意，很快我们可以发现，对于元素 $i$，其合不合法取决于一定大于 $i$ 的数的个数与一定小于 $i$ 的数的个数。这时，我们只需要统计有多少数大于 $i$，与多少数小于 $i$ 即可。只要大于 $i$ 的数的个数与一定小于 $i$ 的数的个数均小于等于比中位数大或小的个数即可，也就是 $(n + 1) / 1 - 1$。接下来取出核心算法。# floyd 传递闭包。首先我们发现，对于每对关系 $[a_i,b_i]$ 都一定有 $a_i > b_i$。那么如果有 $a > b$、$b > c$，那么一定有 $a > c$。这种关系是可以传递的！那么我们考虑如何将这种关系下放。观察数据范围，发现 $n \leq 100$，这说明本题可能需要 $O(n ^ 3)$ 及以上的时间复杂度。所以我们自然而然地想到floyd传递闭包。所谓floyd传递闭包，就是用floyd将可传递的关系传递。核心代码:```cppfor(int k = 1;k <= n;k ++) // 枚举中间值（即 a > b,b > c 中的 b ）{for(int i = 1;i <= n;i ++) //枚举关系的两端{for(int j = 1;j <= n;j ++){a[i][j] |= a[i][k] & a[k][j]; // 如果 i > k 并且 k > j 则 i > j}}}

然后对于每个 \(i\) 我们知道了所有比它大的关系数，同理可以求出比它小的关系数。

然后直接判断是否可行即可。

判无解只需要判断是否有不合法关系即可，即 \(a > b\) 并且 \(b > a\)。

下面放上完整代码。

#include<bits/stdc++.h>
#define int long long 
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define Blue_Archive return 0
using namespace std;
constexpr int N = 100 + 3;
constexpr char me[] = "終末なにしてますか？忙しいですか？救ってもらっていいですか？";int T;
int n;
int m;
int a[N][N]; // a[i][j] 表示 i > j
int b[N][N]; // b[i][j] 表示 i < jinline int read() // 快读
{int k = 0,f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();}while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + c - '0',c = getchar_unlocked();return k * f;
}inline void write(int x) // 快写
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline void clear() // 多测清空
{for(int i = 1;i <= n;i ++) {for(int j = 1;j <= n;j ++){a[i][j] = b[i][j] = 0;}}
}signed main()
{// freopen("data.in","r",stdin);freopen("data.out","w",stdout);T = read();while(T --){clear();n = read();m = read();bool flag = 1; // 记录是否合法for(int i = 1,x,y;i <= m;i ++){x = read();y = read();a[x][y] = 1;b[y][x] = 1;}for(int k = 1;k <= n;k ++) // floyd 传递闭包{for(int i = 1;i <= n;i ++){for(int j = 1;j <= n;j ++){a[i][j] |= a[i][k] & a[k][j];b[i][j] |= b[i][k] & b[k][j];}}}for(int i = 1;i <= n;i ++) // 判无解{for(int j = 1;j <= n;j ++){if(a[i][j] && a[j][i]) flag = 0;}}if(flag == 0) {for(int i = 1;i <= n;i ++) putchar_unlocked('0');ent;continue;}int op = (n + 1) / 2 - 1;for(int i = 1,mx,mn;i <= n;i ++){if(a[i][i]) {putchar_unlocked('0');continue;}mx = mn = 0;bool can = 1;for(int j = 1;j <= n;j ++) // 记录比 i 大的数，与比 i 小的数{if(a[i][j] && b[i][j]) {can = 0;break;}if(a[i][j]) mn ++;if(b[i][j]) mx ++;}if(!can) putchar_unlocked('0');else if(mn <= op && mx <= op) putchar_unlocked('1');else putchar_unlocked('0');}ent;}Blue_Archive;
}