“蔚来杯“2022牛客暑期多校训练营5

K.Headphones

题意：
共有n副耳机，妹妹拿了k对，问NIO至少要拿多少个才能使NIO的耳机数>妹妹。

思路：
至少要拿k+1对耳机，因此当k+1+k=2*k+1>n时，是绝对不可行的，输出-1.
否则，还剩下n-k对，最坏的情况是拿到了每一对的单只，即n-k只，要需要拿到k+1对，因此需要拿n-k+k+1=n+1只耳机。

代码：

#include 
using namespace std;
int main(){
	int n,k;
	while(scanf("%d%d",&n,&k)!=EOF){
		if(2*k+1>n) printf("-1\n");
		else printf("%d\n",n+1);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10

B.Watches

题意：
给出手表个数n及每个手表对应的价钱ai以及NIO拥有的钱m。如果NIO最后买了k只手表，那么买的第i只手表的价钱为ai+k*i（这个i为原序列中的i），问NIO最多可以买多少只手表。

思路：
可以适当进行剪枝，即先求出原序列的最小值，如果这个最小值mi>=m,因为还要加上祱，那么一个都不能买。
需要枚举k，因为之前预处理出了mi,那么可以计算出一个最大值m/mi,在n与这个值之间取最小值。
在lim-0枚举k,对应计算出每只手表的实际价钱，如果前k个手表的实际价钱之和<=m，表明这个k可行，直接输出。

代码：

#include 
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n,m,a[N];
ll b[N];

int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		scanf("%d",&a[1]);
		int mi=a[1];
		int ans=0;
		for(int i=2;i<=n;i++) {
			scanf("%d",&a[i]);
			mi=min(mi,a[i]);
		}
		if(mi>=m) {//如果当前的最小值都已经>=m了，一个都买不了 
			printf("0\n");
			continue;
		}
		int lim=min(m/mi,n);//预处理lim,之前已经预处理出了最小值，那么就取min(m/mi,n); 
		for(int k=lim;k>=0;k--){//枚举k 
			for(int i=1;i<=n;i++) b[i]=a[i]+k*i;//计算实际价值 
			sort(b+1,b+n+1);//排序 
			ll x=0;
			for(int i=1;i<=k;i++) x+=b[i];
			if(x<=m){//如果前k个的实际花费<=m，表明可以 
				ans=k;
				break;
			}
			
		} 
		printf("%d\n",ans);
	} 
	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

C.Bit Transmission

题意：
给出二进制串的长度n,进行3n次查询，每次查询位置pos(0-n-1)，回答YES表明为1，NO表明为0。当持续报错或者崩溃时需要修复bug。注意对于所有的询问，报错的次数最多为1次。如果最后能够确定唯一的二进制串，输出这个串，否则输出-1。

思路：
不能确定唯一串的情况：
（1）某个位置的字符未被查询过
（2）某个位置的YES和NO均为1
（3）某个位置的YES和NO的个数均>=2，那报错肯定超过1次了
（4）某个位置的YES个数为1同时0的个数>=2或者NO个数为1同时YES的个数>=2,此时报错次数+1,累计报错次数，当次数>1时，也不行。

具体见代码：

#include 
using namespace std;
typedef long long ll;
typedef pair PII;
#define fi first
#define se second
const int N = 1e6+10;
int n,pos;
string s;

int main(){
	while(scanf("%d",&n)!=EOF){
		vector v(n+1);
		for(int i=1;i<=3*n;i++){
			scanf("%d",&pos);
			cin>>s;
			if(s=="YES") v[pos].fi++;//1个数++ 
			else if(s=="NO") v[pos].se++;//0个数++ 
		}
		int f=1,num=0;//f为标记，num为报错的次数，当报错次数>1时，也不行 
		for(int i=0;i=2&&v[i].se>=2){//均>=2 
				f=0;
				break;
			}
			else if((v[i].fi==1&&v[i].se>=2)||(v[i].se==1&&v[i].fi>=2)){//报错的时候 
				num++;//报错次数+1 
				if(num>1) {
					f=0;
					break;
				}
			}
			
		}
		if(f==0) printf("-1\n");
		else{
			for(int i=0;iv[i].se)?1:0;
				printf("%d",ans);
			}
		}
		printf("\n");
	}
	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

G.KFC Crazy Thursday

题意：
给出一个长度为n的由小写字母组成的字符串，分别求出以k,f,c结尾的回文串的数目。

思路：
以k为例：
记录下k的位置，到后面的k时，分别与前面的k组成字符串并判断是否为回文串。
这是比赛时的做法，但是后面提交就超时了。
还是得用回文树。

代码：

#include 
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
char s[N];
ll n;
vector  ans(3);
struct PAM{
	ll tr[N][26], fail[N], len[N], cnt[N], idx, last;
	PAM(){
		fail[0] = 1, fail[1] = 1;
		len[1] = -1;
		idx = 1;
	}
	void insert(char c, ll i){
		ll p = get_fail(last, i);
		if (!tr[p][c - 'a']){
			fail[ ++ idx] = tr[get_fail(fail[p], i)][c - 'a'];
			tr[p][c - 'a'] = idx;
			len[idx] = len[p] + 2;
			cnt[idx] = cnt[fail[idx]] + 1;
		}
		last = tr[p][c - 'a'];
	}
	ll get_fail(ll u, ll i){
		while(i - len[u] - 1 < 0 || s[i - len[u] - 1] != s[i]){
			u = fail[u];
		}
		return u;
	}
}pam;

int main(){
    ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n >> s;
	for (int i = 0; i < n; i ++ ){
		pam.insert(s[i], i);
		ll num = pam.cnt[pam.last];
		if (s[i] == 'k') ans[0] += num;
		else if (s[i] == 'f') ans[1] += num;
		else if (s[i] == 'c') ans[2] += num;
	}
	for (int i = 0; i < 3; i ++ )
		cout<