题解 | "蔚来杯"2022牛客暑期多校训练营5

~~论为什么出题人这么喜欢多组数据~~

~~论为什么本场比赛这么多签到题~~

B - Watches

二分答案加上贪心。每次二分可以取多少个就可以计算出每件商品此时对应的价格，之后排序，从小到大取即可。

C - Bit Transmission

题目大意是给你对于长度 $n$ 的二进制数每一位是否为 $1$ 的 $3\times n$ 个信息，其中最多有一个是错误的，求是否有对应的且唯一的二进制数满足这些信息。

考虑开一个数组，统计给定信息中第 $i$ 位为 $1$ 的次数和为 $0$ 的次数。接下来是唯一解的情况。我们用 $cnt_{i,1}$ 和 $cnt_{i,0}$ 分别表示第 $i$ 位为 $1$ 的次数和为 $0$ 的次数。

$cnt_{i,0} = cnt_{i,1}$ 。这显然是没有唯一解的，因为你不知道 $0$ 和 $1$ 到底应该填哪一个到 $i$ 这一位上
$cnt_{i,0} \ge 2$ 且 $cnt_{i,1}\ge 2$ 。这违反了题目 最多只有一条假信息 的条件。
$cnt_{i,0} \not=0$ 且 $cnt_{i,1}\not=0$ 且 $cnt_{j,0} \not=0$ 且 $cnt_{j,1}\not=0,(i\not=j)$ 。这同样违反了题目 最多只有一条假信息 的条件。

如果上述条件全部满足，那么对于第 $i$ 位来说，取次数较多的那一个就好。具体来说，若 $cnt_{i,1}\ge cnt_{i,0}$ ，则第 $i$ 位填 $1$ ；反之，填 $0$ 。

注意多组数据

#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
int n, cnt_opp;
int cnt[MAXN][2];
bool truth[MAXN];
int main(){
    while(~scanf("%d",&n)){
        cnt_opp = 0; bool flag = true;
        memset(cnt, 0, sizeof(cnt));
        memset(truth, 0, sizeof(truth));
        for(int i = 1; i <= n * 3; i++){
            int id; char op[10];
            scanf("%d %s", &id, op+1); id++;
            if(op[1] == 'Y'){
                cnt[id][1]++;
            }else{
                cnt[id][0]++;
            }
        }
        for(int i = 1; i <= n; i++){
            if(cnt[i][0] && cnt[i][1]) cnt_opp++;
            if((cnt[i][0] == 1 && cnt[i][1] == 1) || (cnt[i][0] > 1 && cnt[i][1] > 1) || (cnt[i][0] == 0 && cnt[i][1] == 0)){
                flag = false;
                break;
            }else{
                if(cnt[i][0] > cnt[i][1]) truth[i] = 0;
                else if(cnt[i][1] > cnt[i][0]) truth[i] = 1;
            }
        }
        if(!flag || cnt_opp >= 2){
            printf("-1\n");
            continue;
        }
        for(int i = n; i >= 1; i--) printf("%d",truth[i]);
        printf("\n");
    }
    return 0;
}

G - KFC Crazy Thursday

~~标题不错 QWQ~~

~~所以为什么比赛会有模板题~~

回文自动机模板题，直接上板子。

#include<bits/stdc++.h>
#define MAXN 500010
using namespace std;
int n, tot = 1, last, cur, pos;
int len[MAXN], num[MAXN], fail[MAXN], trie[MAXN][26], ans[4];
char s[MAXN];
int getfail(int now,int i){
	while(i - len[now] - 1 < 0 || s[i-len[now]-1] != s[i]) now = fail[now];
	return now;
}
int main(){
	while(~scanf("%d%s", &n, s)){
		memset(ans, 0, sizeof(ans));
		memset(num, 0, sizeof(num));
		memset(len, 0, sizeof(len));
		memset(trie, 0, sizeof(trie));
		memset(fail, 0, sizeof(fail));
		tot = 1; last = 0; cur = 0; pos = 0;
		fail[0] = 1; len[1] = -1;
		for(int i = 0; i <= n - 1; i++){
			pos = getfail(cur,i);
			if(!trie[pos][s[i]-'a']){
				fail[++tot] = trie[getfail(fail[pos],i)][s[i]-'a'];
				trie[pos][s[i]-'a'] = tot;
				len[tot] = len[pos] + 2;
				num[tot] = num[fail[tot]] + 1;
			}
			cur = trie[pos][s[i]-'a'];
			last = num[cur];
			if(s[i] == 'k') ans[1] += last;
			else if(s[i] == 'f') ans[2] += last;
			else if(s[i] == 'c') ans[3] += last;
		}
		printf("%d %d %d\n", ans[1], ans[2], ans[3]);
	}
	return 0;
}

H - Cutting Papers

~~因为样例出锅导致不敢交错过 1 小时的某人~~

其实可以按照题目意思自己画一个图

这里给直接放出图来

观察到，不论 $n$ 取多少，最后出来的形状都是这种形状的。

那面积其实非常好算。这样的话，就是小学平面几何了。

~~虽然我觉得不用代码~~

#include<bits/stdc++.h>
#define pi acos(-1)
using namespace std;
typedef double lf;
int n;
lf cir, pol, dit, r;
int main(){
    while(~scanf("%d",&n)){
        r = n / 2.0;
        cir = pi * r * r;
        pol = r * r * 3;
        dit = r * r + cir / 2;
        printf("%.9lf\n",cir + pol - dit);
    }
    return 0;
}

K - Headphones

~~同样是小学数学，不是吗~~

直接上代码就好

#include<bits/stdc++.h>
using namespace std;
int n, k;
int main(){
    while(~scanf("%d%d",&n,&k)){
        if(2 * k + 1 > n) printf("-1\n");
        else printf("%d\n",n + 1);
    }
    return 0;
}