Educational Codeforces Round 64 (Rated for Div. 2)题解

题目链接

A. Inscribed Figures

水题，但是坑了很多人。需要注意以下就是正方形、圆以及三角形的情况，它们在上面的顶点是重合的。

其余的参照样例判断一下就好了了。具体证明我也不会

代码如下：

Code

```cpp
#include
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n;
int a[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0) ;
cin >> n;
for(int i = 1; i > a[i] ;
int ans = 0;
int flag = 0;
for(int i = 2; i

B. Ugly Pairs

这场我真的被教育惨了。。B题都没写出来。

题目就是给你一个字符串，现在你可以对其顺序进行重排，问最后是否存在一种方案，使得任意相邻的两个字符不在字母表中相邻。如果存在方案就输出。

这个题我看到大佬随机1w次给过了，牛逼。

其实这个题构造的时候考虑奇偶性就行了。因为在字母表中位于奇数位的数相差肯定大于1，位于偶数位也同理。

之后判断一下首位是否可以拼接起来就行了。可以证明如果四种拼接方式都不成立，那么最后是肯定不存在合法方案的。yy一下就好了。

代码如下：

Code

```cpp
#include
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int N = 105;
int T;
char s[N];
bool ch(char a, char b) {
return abs(a - b) != 1;
}
int main() {
cin >> T;
while(T--) {
scanf("%s", s) ;
vector v(2) ;
int n = strlen(s);
sort(s, s + n);
for(int i = 0; i

C. Match Points

这里很显然的贪心策略是错的。正确的做法应该是二分（当然也可以乱搞贪心过。

首先顺序是不影响结果的，所以我们可以对数从小到大排序。然后二分答案来判断可行性，很显然答案是具有单调性的。

具体的check方法为，假设当前二分的答案为\(x\),那么就拿前\(x\)个和后\(x\)个对应来匹配。

这里可以证明，如果答案\(x\)合法，那么这样的匹配是一定可行的。如果存在其它方案，也可以“收敛”为这个方案。

代码如下:

Code

```cpp
#include
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n, z;
int a[N];
bool check(int x) {
if(2 * x > n) return false ;
for(int i = 1; i > n >> z;
for(int i = 1; i > a[i];
sort(a + 1, a + n + 1) ;
int l = 0, r = n + 1, mid;
while(l > 1;
if(check(mid)) l = mid + 1;
else r = mid;
}
cout

D. 0-1-Tree

简单说下题意吧。就是给你一颗树，边权为0或1。

现在问多少个有向点对\((x,y)\)，满足从\(x\)到\(y\)的简单路径在经过1边权的边后，不会经过边权为0的边。当然，如果先经过边权为0的边，后面是可以经过边权为1的边的。

这个题有两种方法的，我都说一下吧。

对于每个点进行统计

这个我们用并查集来做。首先添加边权为1的边，并且记录每个点所在连通块点的个数；同理这样记录边权为0时的个数。

之后我们枚举每个点，\(ans+=cnt1*cnt0\)就行了。

注意一下最后要减去n，因为之前算的时候算了自身与自身的点对的。

这样做的正确性应该就是不存在两个点，同时在相同的两个边权集合中。所以这样枚举会覆盖所有的情况。

代码如下：

Code

```cpp
#include
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n;
int f[N], f2[N];
ll cnta[N], cntb[N];
int find(int x) {
return f[x] == x ? f[x] : f[x] = find(f[x]) ;
}
int find2(int x) {
return f2[x] == x ? f2[x] : f2[x] = find2(f2[x]) ;
}
void Union(int a, int b) {
int fa = find(a), fb = find(b) ;
if(fa != fb) f[fa] = fb;
}
void Union2(int a, int b) {
int fa = find2(a), fb = find2(b) ;
if(fa != fb) f2[fa] = fb;
}
int main() {
cin >> n;
for(int i = 1; i

dp思想，考虑以每个点为中转站的方案数。

因为如果一个点为中转站，那么就有两种方向。

我们就用两个数组维护连接当前点边权为0/1并且方向为上/下的边数。之后在树dp回溯的时候进行更新就行了。

细节见代码吧:

Code

```cpp
#include
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n;
ll up[N][2], dw[N][2];
struct Edge{
int v, next, w;
}e[N > n;
memset(head, -1, sizeof(head)) ;
for(int i = 1; i

E. Special Segments of Permutation

单调栈找出两边第一个比当前数小的位置，然后类似于启发式合并的思想暴力就行了。

这样为什么是对的，可能要了解一下笛卡尔树。可以发现构造出笛卡尔树后，我们的暴力就相当于树上的启发式合并，复杂度是\(O(nlogn)\)的。（应该是这样来想的。

代码如下：

Code

```cpp
#include
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n;
int a[N], b[N];
int r[N], l[N], sz[N] ;
int top;
int sta[N];
int main() {
scanf("%d", &n) ;
for(int i = 1; i 0 && a[sta[top]] l[i]) ans++;
}
}
}
cout

F. Card Bag

简单说下题意吧：

给出\(n\)张卡片，每张卡片上面有个数字。现在每一回合你从中抽取一张卡片，假设卡片上面的数字为\(x\)，并且你上一次抽取的卡片数字为\(y\)。如果\(x=y\)，你就获得胜利；如果\(x>y\)游戏继续下一轮；如果\(x<y\)，你就输了这场游戏。

最后如果要赢的话，将所有抽取的卡片一次展开，就会发现是先单增，后面两个数值是相等的。

考虑将所有卡片排序，并且计算出\(dp(i,j)\)，表示前\(i\)个卡片中选出\(j\)张不同的卡片的情况总数。

然后考虑枚举最终赢的时候的数值，统计一下所有赢的情况和就行了。

代码如下：

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5005, MOD = 998244353 ;

int n;

ll dp[N][N];

ll fac[N], c[N], a[N];

ll qp(ll A, ll b) {

	ll ans = 1;

	while(b) {

		if(b & 1) ans = ans * A % MOD;

		A = A * A % MOD;

		b >>= 1;

	}

	return ans ;

}

int main() {

	fac[0] = 1;

	for(int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % MOD;

	scanf("%d", &n);

	for(int i = 1; i <= n; i++) scanf("%d", &a[i]), c[a[i]]++;

	int num = n;

	/*for(int i = 1; i < N; i++) {

		if(c[i]) {

			num++;

			c[num] = c[i] ;

		}

	}*/

	dp[0][0] = 1;

	for(int i = 1; i <= num; i++) {

		for(int j = 0; j <= i; j++) {

			if(j == 0) dp[i][j] = dp[i - 1][j];

			else dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * c[i] % MOD ) % MOD;

		}

	}

	ll ans = 0;

	for(int i = 1; i <= num; i++) {

		if(c[i] >= 2)

		for(int j = 1; j <= i; j++) {

			ans = (ans + dp[i - 1][j - 1] * c[i] % MOD * (c[i] - 1) % MOD * fac[n - j - 1] % MOD) % MOD;

		}

	}

	ans = ans * qp(fac[n], MOD - 2) % MOD ;

	cout << ans ;

	return 0 ;

}

Educational Codeforces Round 64 (Rated for Div. 2)题解

Educational Codeforces Round 64 (Rated for Div. 2)题解

A. Inscribed Figures

B. Ugly Pairs

C. Match Points

D. 0-1-Tree

E. Special Segments of Permutation

F. Card Bag