CF1261

Posted on | Edited on | Views:

$Div.1$

A Messy

容易发现在不改变左括号,右括号个数的情况下,把这个序列变成任意一个序列都是可以的.

考虑把括号序列搞成 $()()()()\dots()((()))$ ,即前面放了 $k-1$ 对括号,剩下的括号全部嵌起来,显然是合法的.

对于每个位置 $i$ ,找到从 $i$ 往后第一个需要的括号的位置 $x$ ,把 $[i,x]$ 这一段翻一下就可以了.

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
93
94
95
96
97
98
99
100
101
102
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e3+10;
char s[MAXN];
int n,k,val[MAXN],tmp[MAXN];
set<int> lp,rp;
void rev(int L,int R)
{
	for(int i=L;i<=R;++i)
	{
		tmp[i]=val[i];
		if(val[i]==1)
			lp.erase(i);
		else
			rp.erase(i);
	}	
	for(int i=L;i<=R;++i)
	{
		val[i]=tmp[R+L-i];
		if(val[i]==1)
			lp.insert(i);
		else
			rp.insert(i);
	}
}
void fl(int i)
{
	while(1)
	{
		int x=*lp.begin();
		if(x<i)
			lp.erase(x);
		else
			break;
	}
	int x=*lp.begin();
	printf("%d %d\n",i,x);
	rev(i,x);
}
void fr(int i)
{
	while(1)
	{
		int x=*rp.begin();
		if(x<i)
			rp.erase(x);
		else
			break;
	}
	int x=*rp.begin();
	printf("%d %d\n",i,x);
	rev(i,x);
}
void solve()
{
	n=read(),k=read();
	lp.clear(),rp.clear();
	scanf("%s",s+1);
	for(int i=1; i<=n; ++i)
	{
		if(s[i]=='(')
			val[i]=1,lp.insert(i);
		else
			val[i]=-1,rp.insert(i);
	}
	printf("%d\n",n);
	for(int i=1; i<=2*(k-1); ++i)
	{
		if(i&1)
			fl(i);
		else
			fr(i);
	}
	int L=2*(k-1)+1,R=n;
	int mid=(L+R)>>1;
	for(int i=L;i<=mid;++i)
		fl(i);
	for(int i=mid+1;i<=R;++i)
		fr(i);
}
int main()
{
	int T=read();
	while(T--)
		solve();
	return 0;
}

B Optimal Subsequences

对于每个数定义一个优先度,数字越大,优先度越高,若数字相同,则位置靠前的优先度更高.

那么长度为 $k$ 的最优子序列就是由优先度最大的 $k$ 个数字构成的.

把所有询问离线下来,按照优先度从高到低加入每个数,加入了 $k$ 个数时,就回答所有 $k_i=k$ 的询问.

需要用一颗平衡树,或者权值线段树,来支持插入和求第 $pos$ 个数字.

比赛时没离线询问,写了主席树.

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
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10;
int n,m,k,pos,a[MAXN];
struct info
{
	int val,pos;
	bool operator < (const info &rhs) const
	{
		if(val!=rhs.val)
			return val>rhs.val;
		return pos<rhs.pos;
	}
}p[MAXN];
struct node
{
	int ls,rs,siz;
	node()
	{
		ls=rs=siz=0;
	}
}Tree[MAXN*20];
int idx=0,rt[MAXN];
#define root Tree[o]
#define lson Tree[root.ls]
#define rson Tree[root.rs]
void upd(int &o,int pre,int l,int r,int pos)
{
	o=++idx;
	root=Tree[pre];
	++root.siz;
	if(l==r)
		return;
	int mid=(l+r)>>1;
	if(pos<=mid)
		upd(root.ls,Tree[pre].ls,l,mid,pos);
	else
		upd(root.rs,Tree[pre].rs,mid+1,r,pos);
}
int query(int o,int l,int r,int k)
{
	if(l==r)
		return a[l];
	int mid=(l+r)>>1;
	if(lson.siz>=k)
		return query(root.ls,l,mid,k);
	else
		return query(root.rs,mid+1,r,k-lson.siz);
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		p[i].val=a[i];
		p[i].pos=i;
	}
	sort(p+1,p+1+n);
	for(int i=1;i<=n;++i)
		upd(rt[i],rt[i-1],1,n,p[i].pos);
	m=read();
	for(int i=1;i<=m;++i)
	{
		k=read(),pos=read();
		printf("%d\n",query(rt[k],1,n,pos));
	}
	return 0;
}

C Arson In Berland Forest

需要先观察到,每个初始起火的点,最后会形成一个以它为中心,每条边上有 $2T+1$ 个点的正方形.

因为这些正方形可以重叠,所以答案显然是可以二分的.

预处理一个二维前缀和,二分答案后检查是否能用这样的正方形覆盖住所有着火点.

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
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e6+10;
char buf[MAXN];
vector<int> a[MAXN],s[MAXN],tmp[MAXN],ans[MAXN];
int n,m;
bool check(int x)
{
	x=x*2+1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			ans[i][j]=tmp[i][j]=0;
	for(int i=1;i+x-1<=n;++i)
		for(int j=1;j+x-1<=m;++j)
		{
			int tot=s[i+x-1][j+x-1]-s[i-1][j+x-1]-s[i+x-1][j-1]+s[i-1][j-1];
			if(tot==x*x)
				ans[i][j]=1;
		}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			tmp[i][j]=tmp[i-1][j]+tmp[i][j-1]-tmp[i-1][j-1]+ans[i][j];
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(a[i][j]) // 判断这个点是否被覆盖 
			{
				int tot=tmp[i][j];
				if(i>x)
					tot-=tmp[i-x][j];
				if(j>x)
					tot-=tmp[i][j-x];
				if(i>x && j>x)
					tot+=tmp[i-x][j-x];
				if(!tot)
					return false;				
			}
	return true;
}
int main()
{
	n=read(),m=read();
	s[0].resize(m+1),tmp[0].resize(m+1);
	for(int i=1;i<=n;++i)
	{
		a[i].resize(m+1);
		s[i].resize(m+1);
		tmp[i].resize(m+1);
		ans[i].resize(m+1);
		scanf("%s",buf+1);
		for(int j=1;j<=m;++j)
		{
			a[i][j]=(buf[j]=='X');
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
		}
	}
	int L=0,R=(min(n,m)-1)>>1,res;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(check(mid))
			res=mid,L=mid+1;
		else
			R=mid-1;
	}
	check(res);
	printf("%d\n",res);
	for(int i=1;i<=n;++i,puts(""))
		for(int j=1;j<=m;++j)
			if(i-res>0 && j-res>0 && ans[i-res][j-res])
				putchar('X');
			else
				putchar('.');
	return 0;
}

D Wrong Answer on test 233

考虑利用生成函数,将 “变换后的答案与变换前的答案之差” 看做 $x$ 的次数.

若位置 $i​$ 与位置 $(i\bmod n)+1​$ 上的数相同,则无论怎样取,这个差都不会变,记这样的位置有 $a​$ 个.

若位置 $i$ 与位置 $(i\bmod n)+1$ 上的数不同,则各有 $1$ 种选法让差 $+1,-1$ ,其余的不变,记这样的位置有 ​$b$ 个.

记 $p=k-2$ ,则这个生成函数为 $k^a\cdot (x+x^{-1}+p)^b$ ,只有次数 $>0​$ 的项的系数会被计入答案.

把后面的式子乘上 $x^b$ ,后面就变成了 $(x^2+px+1)^b$ ,只有次数 $>b$ 的项的系数会被计入答案.

直接用多项式快速幂乘出来,常数太大,不可取.

枚举 $px$ 选了 $i$ 个,则
$$
k^a\cdot (x^2+px+1)^b=k^a\cdot \sum_{i=0}^b {b\choose i}p^{b-i}x^{b-i}\cdot \sum_{j=0}^i {i\choose j}x^{2j}
$$
由于只算次数 $>b$ 的项的系数和,对于后面那个 $\sum$ ,只有 $2j>i$ 的 $i\choose j$ 会产生贡献.

当 $i$ 为奇数时,这个贡献是 $2^{i-1}$ ,当 $i$ 为偶数时,这个贡献是 $\frac{2^i-{i\choose i/2}}{2}$ .

时间复杂度 $O(n)$ .

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
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353,inv2=(P+1)>>1;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
void inc(int &a,int b)
{
	a=add(a,b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int MAXN=2e5+10;
int fac[MAXN],invfac[MAXN],pw2[MAXN],pw[MAXN];
int binom(int M,int N)
{
	return mul(fac[M],mul(invfac[N],invfac[M-N]));
}
int n,k,p,a=0,b=0,val[MAXN];
int main()
{
	n=read(),k=read();
	p=k-2;
	for(int i=1;i<=n;++i)
		val[i]=read();
	for(int i=1;i<=n;++i)
		if(val[i]==val[i%n+1])
			++a;
		else
			++b;
	fac[0]=pw2[0]=pw[0]=1;
	for(int i=1;i<=b;++i)
	{
		fac[i]=mul(fac[i-1],i);
		pw2[i]=mul(pw2[i-1],2);
		pw[i]=mul(pw[i-1],p);
	}
	invfac[b]=fpow(fac[b],P-2);
	for(int i=b-1;i>=0;--i)
		invfac[i]=mul(invfac[i+1],i+1);
	int ans=0;
	for(int i=0;i<=b;++i)
	{
		int tmp=mul(binom(b,i),pw[b-i]);
		if(i&1)
			tmp=mul(tmp,pw2[i-1]);
		else
			tmp=mul(tmp,mul(inv2,add(pw2[i],P-binom(i,i>>1))));
		inc(ans,tmp);
	}
	ans=mul(ans,fpow(k,a));
	cout<<ans<<endl;
	return 0;
}

E Not Same

先把所有元素从小到大排序,考虑一列一列地去构造出这个解.

这里的 $n$ 指还需要构造的元素的数目.

  • 如果最大的元素 $x<n$ ,则可以从前往后递归构造解.

    即,先求出后 $n-1$ 个元素的解,记第一个元素为 $y$ ,再将前 $y$ 个操作加上第一个元素.

  • 如果最大的元素 $=n$ ,这样做时,最后一步就会出现问题.

    此时应该构造出一个解,有 $n$ 次操作都包含了最后那个元素,最多有 $1$ 次操作没有包含.

    • 如果次大的元素也 $=n$ ,就将所有除了最后一个元素的 $=n$ 的元素减去 $1$ ,递归构造前 $n-1$ 个元素的解.

      次大元素现在是 $n-1$ ,所以前面只可能构造出 $n-1$ 或者 $n$ 个操作.

      将这些操作全部加上最后一个元素,若操作数是 $n-1$ ,则还需要加上一个只包含最后一个元素的操作.

    • 如果次大的元素 $<n$ ,记它为 $x$ ,则可以先将开头的 $n-x-1$ 个数全部操作 $1$ 次,.

      然后递归构造前 $n-1$ 个元素的解,这样也会得到 $n-1$ 或者 $n$ 个操作.

      将这些操作全部加上最后一个元素,若操作数是 $n-1$ ,则还需要加上一个只包含最后一个元素的操作.

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
93
94
95
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
typedef pair<int,int> pii;
#define val first
#define pos second
void solve(vector<pii> A,vector<vector<int>> &ops)
{
	int n=A.size();
	if(n==1)
	{
		if(A[0].val)
			ops.push_back({A[0].pos});
		return;
	}
	if(A[n-1].val<n)
	{
		auto B=A;
		B.erase(B.begin());
		solve(B,ops);
		for(int i=0;i<A[0].val;++i)
			ops[i].push_back(A[0].pos);
		return;
	}
	else
	{
		auto B=A;
		B.pop_back();
		if(A[n-2].val==n)
		{
			vector<int> op;
			for(int i=0;i<n-1;++i)
				if(B[i].val==n)
				{
					B[i].val--;
					op.push_back(B[i].pos);
				}
			solve(B,ops);
			for(int i=0;i<ops.size();++i)
				ops[i].push_back(A[n-1].pos);
			if(ops.size()<n)
				ops.push_back({A[n-1].pos});
			ops.push_back(op);
		}
		else
		{
			int x=A[n-2].val;
			for(int i=0;i<n-x-1;++i)
				B[i].val--;
			solve(B,ops);
			for(int i=0;i<n-x-1;++i)
				ops.push_back({A[i].pos});
			for(int i=0;i<ops.size();++i)
				ops[i].push_back(A[n-1].pos);
			if(ops.size()<n)
				ops.push_back({A[n-1].pos});
		}
	}
}
int main()
{
	int n=read();
	vector<pii> A(n);
	for(int i=0;i<n;++i)
	{
		A[i].val=read();
		A[i].pos=i;
	}
	sort(A.begin(),A.end());
	vector<vector<int>> ops;
	solve(A,ops);
	cout<<ops.size()<<endl;
	for(int i=0;i<ops.size();++i)
	{
		string ans(n,'0');
		for(int x:ops[i])
			ans[x]='1';
		cout<<ans<<endl;
	}
	return 0;
}

F Xor-Set

考虑建出一颗管辖区间 $[0,2^{60}-1]$ 的线段树,把 $A,B$ 集合的线段各自在这棵线段树上划分出来.

那么这个线段树上一个深度为 $x$ 的节点,代表前 $x$ 位固定后,后面的 $60-x​$ 位任意取,这样的数集合中都有.

那么 $A$ 集合中的一个线段树节点与 $B$ 集合中的一个线段树节点异或,贡献是容易计算的.

由于 $C$ 是集合,所以相同的数只会被算一次,那么把两者固定的长度(红色部分)取个 $\min$ ,贡献不变.

即把黑色部分也看成可以任意取.

在线段树上的意义就是,把深度较深的那个节点向上跳,跳到两者深度相同,贡献不变.

于是可以对集合 $A$ ,只给划分出来的线段树节点打标记,对集合 $B$ ,给划分出来的线段树节点的所有祖先打上标记.

利用线段树的性质可以证明,$A,B$ 各自标记的线段数目不会超过 $4n$ .

枚举每个深度,只计算深度相同的,有标记的节点之间产生的贡献,时间复杂度 $O(n^2\log 10^{18})​$ .