adolphshi
adolphshi
文章17
标签11
分类4
回到首页
文章归档
我的朋友
给我赞助
关于博主

文章分类

一言

文章归档

最新文章

© 2026 adolphshi Powered by Hexo & Nexmoe
萌ICP备20235011号
CF-R997记录

CF-R997记录

2025年01月19日 CF补全计划 约2.5k字 预计需要11分钟

CF2056.Codeforces Round 997 (Div. 2) solved(3/7)

好久都没写blog了，趁着集训把这些题改了。

A.Shape Perimeter

小学数学题，我们发现可以平移边然后成一个长方形，长方形边长为 m+Σxim+\Sigma x_i 和 m+Σyim+\Sigma y_i然后直接算就行了。

代码考场糖丸了，写的比较复杂。

B.Find the Permutation

题意就是对于一个数列的每一个顺序对连边，最后给你图让你还原数列。

手玩一下会发现，当两个点之间有边时，小的数排在大的数前面，否则排在大的数的后面。

然后我们就发现这好像可以用快排的方式来做，选一个基数，分两落，然后分治，于是我们就可以爆改cmp函数然后直接sort就可以了。

C.Palindromic Subsequences

题意就是构造一个数列使得最长回文子序列(不一定连续)的个数大于序列长度(也就是nn)

神奇电波题，但是我和出题人对上了可能是为了补偿我B题寄得很惨，首先我们会发现一种不是很合适的做法，由nn个不同的数构成的数列，这样的会最长回文子序列长度为一，个数为 nn 个，显然不会符合要求。

好像没什么办法了，看样例，发现第一组数据好像有个很神奇的性质，两个一在左右两端，中间放从互不相同的数，这样的话最长回文子序列长度为三，个数为 n−2n-2 个，好像更不优。

别急，我们发现在第一组数据后面放了一个 22，我们会发现，虽然中间的数列中少了一个数，但是两个二中间的又都是刚才的那个结构，这样的话就肯定大于 nn 了。吗？

我们发现它在很小的时候不成立，不过6≤n6\leq n 就更加印证了我们的构造是正确的。

D.Unique Median

止步于此死因是没有发现单调性还硬要用双指针，题意是查询中位数相同的区间的个数。长度为偶数数组的中位数有两个。注意aia_i 的取值范围。

本题有两个关键点：

  1. 发现正着统计不好统计，我们可以正难则反。（常见套路。

  2. 我们发现对于非法区间，一定会有一个数字 kk 在数组中出现，并有正好一半的数 ≤k\leq k 。这个的提示在于1≤ai≤101\leq a_i \leq \textcolor{red}{10} 告诉我们与值域有关。

当我们发现了这两个关键点之后，这题就可以做了，我们可以枚举 kk,然后找非法区间的个数。

具体怎么统计我们可以使用之前统计中位数时常用的技巧见D题思路部分怎么又是D题 依旧是将大于kk的记成-1，小于kk的记成 11 ,非法区间就是含有 kk 且和为 00 的区间。这启发我们把前缀和求出来并统计和相同的前缀的个数，遇见了kk 就将上一次到当前kk 的前缀加入统计个数中。在这儿才用双指针，想太早会误导自己。

E.Nested Segments

给你一个不交集（有包含，但不交叉），你在上边继续加线段使得它依旧是不交集，问在有多少种不同的方案数使得加的线段最多，答案对 998244353998244353 取模。

首先，不交集有一个广为人知的性质——依据区间包含关系连边（包含向被包含连边），就会形成一个森林。所以本题就是给你一个树，让你找向树上挂最多点的方案数。为了方便，我们向每一个集合中先插入[1,n][1,n] 和 [i,i][i,i]（如果没有的话）这样的话整个集合就是一棵树，并且有 nn 个叶子。

我们先从m=0m=0 开始分析， 这时给出的是一个空集。我们会发现，当这棵树为一颗二叉树的时候总点数最多。此时每一个节点都有两个或零个的儿子。那么这个东西的个数就是有2n−12n-1个节点的二叉树的个数（因为有nn个叶子），这是我们联想到卡特兰数。答案就是Cn−1C_{n-1} 其中 CC 为卡特兰数

然后发现当m≠0m \neq 0 时，此时若一个区间包含若干个区间[l1,r1],[l2,r2],⋯[l_1,r_1],[l_2,r_2],\cdots 那么我们可以在[l1,r1],[l2,r2][l_1,r_1],[l_2,r_2]之上插入[l1,r2][l_1,r_2] 这样原先的两个区间就变为了新区间的两个子区间，因此我们还可以将给出的树转变为一个二叉树，并且叶子节点个数还为nn 。那么最大的节点个数依旧不变，但方案数肯定是有变化的。

此时我们可以将一个区间所包含的区间[l1,r1],[l2,r2],⋯[l_1,r_1],[l_2,r_2],\cdots 看成一个点，那么对于上一个区间，就相当于是再统计二叉树的个数，此时对于这个区间的答案就是Ck−1C_{k-1} 其中 kk 为原区间的子区间个数（注意我们为了方便添加的[i,i][i,i]）。

最终答案就是将所有区间的答案相乘，就是 ∏Ccv−1\large{\prod C_{c_v - 1}} 其中 cvc_v 为 vv 子区间个数。

F.Xor of Median (Hard Version)

没看懂，有没有大佬来教教我啊。😭

code

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair<int,int> pii;

ci maxn=2e6+10;

int n,t,m,x,y,c;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		x=0,y=0;
		c=0;int lx=0,ly=0;
		scanf("%d%d",&x,&y);
		c+=4*m;
		_F(i,2,n)
		{
			int dx,dy;
			scanf("%d%d",&dx,&dy);
			lx=x,ly=y;
			x+=dx,y+=dy;
			c+=4*m;
			c-=2*max(lx+m-x,0)+2*max(ly+m-y,0);
		}
		printf("%d\n",c);
	}
	return 0;
}

B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair<int,int> pii;

ci maxn=2e6+10;

int n,m,t,id[1010];
char s[1010][1010];
vector<int> v[1010];
bool cmp(int x,int y)
{
	return (s[x][y]=='1'&&x<y)||(s[x][y]=='0'&&x>y);
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		_F(i,1,n)
		{
			scanf("%s",s[i]+1);
			id[i]=i;
		}
		sort(id+1,id+n+1,cmp);
		_F(i,1,n)
			printf("%d ",id[i]);
		puts("");
	}
	return 0;
}

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include 
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair pii;

ci maxn=2e6+10;

int n,t;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		printf("1 ");
		_F(i,2,n-2)
			printf("%d ",i-1);
		printf("1 2\n");
	}
	return 0;
}

D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair<int,int> pii;

ci maxn=2e6+10;

int n,m,t,a[maxn],b[maxn],cnt[maxn],s[maxn];
ll ans;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		ans=0;
		scanf("%d",&n);
		_F(i,1,n)
			scanf("%d",&a[i]);
		_F(k,1,10)
		{
			_F(i,0,n*2+1)
				cnt[i]=0;
			_F(i,1,n)
				b[i]=(a[i]>k?-1:1);
			int l=0,num=n;
			_F(i,1,n)
			{
				s[i]=num;
				num+=b[i];
			}
			num=n;
			_F(i,1,n)
			{
				if(a[i]==k)
				{
					while(l<=i)
					{
						cnt[s[l]]++;
						l++;
					}
				}
				num+=b[i];
				ans+=cnt[num];
			}
		}
		ans=1ll*n*(n+1)/2-ans;
		printf("%lld\n",ans);
	}
	return 0;
}

E

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const ll ci;
typedef pair<ll,ll> pii;

ci maxn=6e5+10,p=998244353;

ll n,t,jc[maxn],jn[maxn],inv[maxn],m,cnt[maxn],ans;
pii s[maxn];
bool v[maxn],fl=0;
ll ksm(ll x,ll y)
{
	ll res=1;
	while(y)
	{
		if(y&1) res=res*x%p;
		x=x*x%p;
		y>>=1;
	}
	return res;
}
ll c(ll x,ll y)
{
	if(y>x||y<0) return 0;
	return jc[x]*jn[y]%p*jn[x-y]%p;
}
ll cat(ll x)
{
	return c(2*x,x)*inv[x+1]%p;
}
int main()
{
	scanf("%lld",&t);
	jc[0]=1;
	_F(i,1,maxn-9)
		jc[i]=jc[i-1]*i%p;
	jn[maxn-9]=ksm(jc[maxn-9],p-2);
	F_(i,maxn-10,0)
		jn[i]=jn[i+1]*(i+1)%p;
	_F(i,1,maxn-9)
		inv[i]=jn[i]*jc[i-1]%p;
	while(t--)
	{
		fl=0;ans=1;
		scanf("%lld%lld",&n,&m);
		_F(i,1,n)
			v[i]=0;
		_F(i,1,m)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			s[i]={x,y};
			if(x==y) v[x]=1;
			if(x==1&&y==n) fl=1;
		}
		if(!fl) s[++m]={1,n};
		_F(i,1,n)
			if(!v[i]&&n!=1)
				s[++m]={i,i};
		_F(i,1,m)
			s[i].second=-s[i].second,cnt[i]=0;
		sort(s+1,s+1+m);
		_F(i,1,m)
		{
			int j=i+1;
			while(j<=m)
			{
				if(-s[i].second<s[j].first) break;
				cnt[i]++;
				j=upper_bound(s+1,s+1+m,make_pair(-s[j].second,1ll))-s;//找下一个区间
			}
		}
		_F(i,1,m)
			s[i].second=-s[i].second;
		_F(i,1,m)
		{
			if(cnt[i]>0)
			{
				ans=(ans*cat(cnt[i]-1))%p;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}
本文作者：adolphshi
本文链接：http://adolphshi.github.io/2025/01/19/cf-r997%E8%AE%B0%E5%BD%95/
版权声明：本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
×