Codeforces 1120 简要题解_codeforces1120a

传送门

A题

传送门
题意简述：给你一个$m$个数的数列，现在规定把一个数列的$1,2,...,k$分成第一组，把$k+1,k+2,...,2k$分成第二组,…,这样把前$n\ast k$个数分成$n$组，现在给你$s$个数，你可以删去至多$m-n\ast k$个数使得新数列按照上述方式分组可以分出来至少一个组满足$s$个数都在里面出现（如果$s$个数中$a$出现$b$次则分出来满足条件的组中$a$出现至少$b$次），求任意方案。

---

思路：
我们用双指针统计一下就行了，注意细节。
代码：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
   
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
const int N=5e5+5;
int cnt[N],tot[N],lim[N],a[N],okcnt=0,m,n,k,s,det=0;
bool in[N];
inline void check(int l,int r){
   
	int blo=l==l/k*k?(l/k-1)*k+1:l/k*k+1;
	if(r-blo+1-k>(n-m*k))return;
	if(r-blo+1-k<=0)puts("0"),exit(0);
	int ccnt=0;
	for(ri i=blo;i<=r;++i)ccnt+=in[i];
	cout<<r-blo+1-k<<'\n';
	for(ri i=blo,j=1;i<=r&&j<=r-blo+1-k;++i){
   
		if(lim[a[i]]&&tot[a[i]]<lim[a[i]]){
   
			++tot[a[i]];
			continue;
		}
		cout<<i<<' ',++j;
	}
	exit(0);
}
int main(){
   
	n=read(),k=read(),m=read(),s=read();
	for(ri i=1;i<=n;++i)a[i]=read();
	for(ri i=1,v;i<=s;++i){
   
		++lim[v=read()];
		if(lim[v]>1)++det;
	}
	for(ri l=1,r=0;;){
   
		while(r<n&&okcnt!=s-det){
   
			++r,++cnt[a[r]];
			if(cnt[a[r]]==lim[a[r]])++okcnt;
			if(cnt[a[r]]<=lim[a[r]])in[r]=1;
		}
		if(okcnt!=s-det)break;
		while(okcnt==s-det){
   
			if(cnt[a[l]]==lim[a[l]])check(l,r),--okcnt;
			if(cnt[a[l]]<=lim[a[l]])in[l]=0;
			--cnt[a[l]];
			++l;
		}
	}
	puts("-1");
	return 0;
}
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

---

B题

传送门
题意简述：给你两个等长的数字串$a,b$，你可以把$a$中的任意相邻两个数同时$+1/-1$，问能否把$a$变成$b$以及输出操作方案数和具体方案。

---

思路：
一道比较显然的贪心吧。
直接一位一位匹配就行了，如果$a_i$比$b_i$小就给$a_i,a_{i+1}$同时加上$b_i-a_i$；如果 a i a_i