CF1251

Posted on | Edited on | Views:

$Div.2$

A Broken Keyboard

若某段连续出现这个字符 $c$ 的次数为奇数,则字符 $c$ 一定没有坏掉.

时间复杂度 $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
//%std
#include<bits/stdc++.h>
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=512;
char buf[MAXN];
int n,t,ans[26];
void solve()
{
	scanf("%s",buf);
	n=strlen(buf);
	memset(ans,0,sizeof ans);
	for(int l=0,r;l<n;l=r+1)
	{
		r=l;
		while(r+1<n && buf[r+1]==buf[r])
			++r;
		if((r-l+1)&1)
			ans[buf[l]-'a']=1;
	}
	for(int i=0;i<26;++i)
		if(ans[i])
			putchar('a'+i);
	puts("");
}
int main()
{
	int T=read();
	while(T--)
		solve();
	return 0;
}

B Binary Palindromes

由于对交换的次数不作限制,那么任意一个 $0,1$ 个数都不变的方案,都可以得到.

于是答案只与 $0,1$ 的个数,以及每个串的长度有关.

统计出 $0,1​$ 的个数后,对于每个长度确定的字符串,依次构造.

这里可以贪心来放,若串长为偶,就任意选出 $\frac {len} {2}$ 个对子放入.

若串长为奇,此时若 $0,1$ 的个数有一个为奇,就让它去作为中心的数,否则就任意选一个填在中心.

剩下的部分仍然任意选对子放入,时间复杂度 $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
//%std
#include<bits/stdc++.h>
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=51;
int n,len[MAXN],cnt[2];
char buf[MAXN];
int solve()
{
	n=read();
	cnt[0]=cnt[1]=0;
	for(int i=1;i<=n;++i)
	{
		scanf("%s",buf);
		len[i]=strlen(buf);
		for(int j=0;j<len[i];++j)
			++cnt[buf[j]-'0'];	
	}
	for(int i=1;i<=n;++i)
	{
		if(len[i]&1)
		{
			if(cnt[0]+cnt[1]==0)
				return i-1;
			else if(cnt[0]==0)
				--cnt[1];
			else if(cnt[1]==0)
				--cnt[0];
			else if(cnt[0]&1)
				--cnt[0];
			else
				--cnt[1];
		}
		len[i]>>=1;
		if((cnt[0]>>1)>=len[i])
			cnt[0]-=len[i]<<1;
		else
		{
			len[i]-=cnt[0]>>1;
			cnt[0]&=1;
			if((cnt[1]>>1)>=len[i])
				cnt[1]-=len[i]<<1;
			else
				return i-1;
		}
	}
	return n;
}
int main()
{
	int T=read();
	while(T--)
		printf("%d\n",solve());
	return 0;
}

C Minimize The Integer

从前往后考虑每一位,根据数的比较方式,只需要贪心地让当前这一位尽可能的小.

注意到一个奇数往前换,如果它的前面还有奇数,则它一定会被挡住,不能来到当前的这位,偶数同理.

于是当前的这位就只能取剩下的第一个奇数或者第一个偶数.

这就是一个归并排序的过程,时间复杂度 $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
//%std
#include<bits/stdc++.h>
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=3e5+10;
char buf[MAXN];
int n,pos[2][MAXN],t[2];
void solve()
{
	scanf("%s",buf);
	n=strlen(buf);
	for(int i=n-1;i>=0;--i)
	{
		int x=buf[i]-'0';
		pos[x&1][++t[x&1]]=x;
	}
	while(t[0]+t[1])
	{
		if(!t[0])
			putchar(pos[1][t[1]--]+'0');
		else if(!t[1])
			putchar(pos[0][t[0]--]+'0');
		else if(pos[0][t[0]]<pos[1][t[1]])
			putchar(pos[0][t[0]--]+'0');
		else
			putchar(pos[1][t[1]--]+'0');
	}
	puts("");
}
int main()
{
	int T=read();
	while(T--)
		solve();
	return 0;
}

D Salary Changing

二分答案 $k$ ,则需要算出至少有 $\frac{n+1}{2}$ 个人的薪水 $\ge k$ 时,最小的总薪水是否 $\le s$ .

每个人的薪水区间 $[l,r]$ 要么满足 $l>k$ ,要么满足 $r<k$ ,要么满足 $l\le k\le r$ .

对于前两种区间,显然都选它们的左端点作为薪水.

若薪水 $\ge k$ 的人数还不够,则还要将一部分 $l\le k\le r$ 的区间选取的薪水从 $l$ 调整为 $k$ .

实现时,可以先将所有区间按照 $l,r$ 为两个关键字排序,从后往前扫一遍即可验证.

时间复杂度 $O(n\log n+n\log \max r)$ .

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
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll 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;
const int inf=1e9;
int n,m;
ll s;
struct Interval
{
	int l,r;
	bool operator < (const Interval &rhs) const
	{
		return l==rhs.l?r<rhs.r:l<rhs.l;
	}
}p[MAXN];
bool check(int k)
{
	ll tot=0;
	int cnt=0;
	for(int i=n;i>=1;--i)
	{
		if(cnt==m)
		{
			tot+=p[i].l;
			continue;
		}
		if(p[i].l>k)
			tot+=p[i].l,++cnt;
		else if(p[i].r>=k)
			tot+=k,++cnt;
		else
			tot+=p[i].l;
	}
	return cnt==m && tot<=s;
}
void solve()
{
	n=read(),s=read();
	m=(n+1)>>1;
	for(int i=1;i<=n;++i)
		p[i].l=read(),p[i].r=read();
	sort(p+1,p+1+n);
	int L=1,R=inf,res;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(check(mid))
			res=mid,L=mid+1;
		else
			R=mid-1;
	}
	printf("%d\n",res);
}
int main()
{
	int T=read();
	while(T--)
		solve();
	return 0;
}

E Voting

将所有人按照 $m_i$ 从小到大排序,依次考虑.

记录一个 $cnt$ ,表示当前已经投了票的人数,到第 $i$ 个人时,若 $n-i+cnt<m_i$ ,则在 $[1,i]$ 中必须有人要投票.

用一个小根堆维护还没有投票的所有人的 $p$ ,需要投票时,就弹出堆顶,更新答案和 $cnt$ .

一个人最多只会被弹出一次,时间复杂度 $O(n\log 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
//%std
#include<bits/stdc++.h>
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;
struct node
{
	int m,p;
	bool operator < (const node &rhs) const
	{
		return m>rhs.m;
	}
}a[MAXN];
priority_queue<int> q;
void solve()
{
	while(!q.empty())
		q.pop();
	n=read();
	for(int i=1;i<=n;++i)
		a[i].m=read(),a[i].p=read();
	sort(a+1,a+1+n);
	ll ans=0;
	int cnt=0;
	for(int i=1;i<=n;++i)
	{
		q.push(-a[i].p);
		while(cnt+(n-i)<a[i].m)
		{
			++cnt;
			ans-=q.top();
			q.pop();
		}
	}	
	cout<<ans<<endl;
}
int main()
{
	int T=read();
	while(T--)
		solve();
	return 0;
}

F Red-White Fence

容易得出一个图形的周长为 $2(mx+1+w)$ ,其中 $w$ 表示使用的白色板子数目.

$k$ 很小,可以直接去枚举用的红色板子的高度 $mx$ ,尝试将每个 $w$ 的方案数都算出来,加入对应贡献.

从高到低考虑每种长度的白色板子,从高度 $<mx$ 的白色板子开始计算.

若这种长度只有 $1$ 块,则只能选择不加,或者加在某一边,生成函数表示为 $(1+2x)$ .

若 $>1$ 块,则可以选择不加,或者加在某一边,或者两边都加,生成函数表示为 $(1+2x+x^2)=(x+1)^2$ .

那么这些生成函数之积就是 $(1+2x)^a\cdot (x+1)^{2b}$ 的形式,用二项式定理算出两个多项式,再用 $NTT$ 将它们乘起来.

最后利用维护的贡献 $O(1)$ 回答每个询问.

时间复杂度 $O(kn\log n+q)$ .

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
//%std
#include<bits/stdc++.h>
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,G=3;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(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=1.8e6+10;
int omega[MAXN],inv[MAXN],rev[MAXN],curn;
void NTT_init(int n)
{
	if(curn==n)
		return;
	for(int i=0;i<n;++i)
		rev[i]=(rev[i>>1]>>1)|((n>>1)*(i&1));
	for(int l=2;l<=n;l<<=1)
	{
		omega[l]=fpow(G,(P-1)/l);
		inv[l]=fpow(omega[l],P-2);
	}
	curn=n;
}
void DFT(int *a,int n,bool invflag)
{
	NTT_init(n);
	for(int i=0;i<n;++i)
		if(i<rev[i])
			swap(a[i],a[rev[i]]);
	for(int l=2;l<=n;l<<=1)
	{
		int m=(l>>1);
		int gi=omega[l];
		if(invflag)
			gi=inv[l];
		for(int *p=a;p!=a+n;p+=l)
		{
			int g=1;
			for(int i=0;i<m;++i)
			{
				int t=mul(g,p[i+m]);
				p[i+m]=add(p[i],P-t);
				p[i]=add(p[i],t);
				g=mul(g,gi);
			}
		}
	}
	if(invflag)
	{
		int invn=fpow(n,P-2);
		for(int i=0;i<n;++i)
			a[i]=mul(a[i],invn);
	}
}
int NTT_A[MAXN],NTT_B[MAXN];
void NTT(int *A,int *B,int *C,int lenA,int lenB)
{
	int lenC=lenA+lenB-1,n=1;
	while(n<lenC)
		n<<=1;
	for(int i=0;i<lenA;++i)
		NTT_A[i]=A[i];
	for(int i=lenA;i<n;++i)
		NTT_A[i]=0;
	for(int i=0;i<lenB;++i)
		NTT_B[i]=B[i];
	for(int i=lenB;i<n;++i)
		NTT_B[i]=0;
	DFT(NTT_A,n,false);
	DFT(NTT_B,n,false);
	for(int i=0;i<n;++i)
		C[i]=mul(NTT_A[i],NTT_B[i]);
	DFT(C,n,true);
}
int n,k,fac[MAXN],invfac[MAXN],pw2[MAXN];
void init()
{
	int m=n<<1;
	fac[0]=pw2[0]=1;
	for(int i=1;i<=m;++i)
	{
		fac[i]=mul(fac[i-1],i);
		pw2[i]=mul(pw2[i-1],2);
	}
	invfac[m]=fpow(fac[m],P-2);
	for(int i=m-1;i>=0;--i)
		invfac[i]=mul(invfac[i+1],i+1);
}
int binom(int M,int N)
{
	if(M<N || N<0 || M<0)
		return 0;
	return mul(fac[M],mul(invfac[N],invfac[M-N]));
}
int h[MAXN],ans[MAXN];
int A[MAXN],B[MAXN],tmp[MAXN];
void solve(int mx)
{
	int a=0,b=0;
	//(1+2x)^a \cdot (1+2x+x^2)^b
	for(int l=0,r;l<n && h[l]<mx;l=r+1)
	{
		r=l;
		while(r+1<n && h[r+1]==h[r])
			++r;
		if(l==r)
			++a;
		else
			++b;
	}
	for(int i=0;i<=a;++i)
		A[i]=mul(binom(a,i),pw2[i]);
	for(int i=0;i<=2*b;++i)
		B[i]=binom(2*b,i);
	NTT(A,B,tmp,a+1,2*b+1);
	int len=a+2*b+1;
	for(int i=0;i<len;++i)
		ans[i+1+mx]=add(ans[i+1+mx],tmp[i]);
}
int main()
{
	n=read(),k=read();
	init();
	for(int i=0;i<n;++i)
		h[i]=read();
	sort(h,h+n);
	for(int i=0;i<k;++i)
	{
		int x=read();
		solve(x);
	}	
	int q=read();
	while(q--)
		printf("%d\n",ans[read()>>1]);
	return 0;
}