2022.8.1 "蔚来杯"2022牛客暑期多校训练营5 赛后总结

比赛成绩

AC：5

RANK：598

试题订正

B.Watches

难度：easy

发现答案具有单调性，考虑二分答案。

每次二分按 $a_i+i \times k$ 从小到大排序，看前 $k$ 个之和是否小于等于 $m$ 即可。

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pa;
const int MAXN=1e5+5;
pa a[MAXN];
int n,m,k;
bool cmp(pa x,pa y)
{
    return x.first+k*x.second<y.first+k*y.second;
}
bool check(int mid)
{
    k=mid;
    sort(a+1,a+n+1,cmp);
    int sum=0;
    for(int i=1;i<=mid;++i)
    {
        sum+=a[i].first+k*a[i].second;
        if(sum>m) return 0;
    }
    return 1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i) scanf("%d",&a[i].first),a[i].second=i;
    int l=1,r=n,ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}

C.Bit Transmission

难度：easy

先根据机器人的回答统计出 $c n t 0 [i], c n t 1 [i]$ 。

用 $s u m$ 统计 $cnt0[i]>0\ \&\&\ cnt1[i]>0$ 的次数。

若出现：

$1.\ cnt0[i]==0\ \&\&\ cnt1[i]==0$

$2.\ cnt0[i]==1\ \&\&\ cnt1[i]==1$

$3.\ cnt0[i]>1\ \&\&\ cnt1[i]>1$

$4.\ sum>1$

则输出 $- 1$ 。

否则输出当前位 $c n t$ 更大的那个即可。

#include<bits/stdc++.h>
using namespace std;

const int MAXN=2e6+5;
int cnt0[MAXN],cnt1[MAXN];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(cnt0,0,sizeof(cnt0));
        memset(cnt1,0,sizeof(cnt1));
        int x;
        char opt[5];
        for(int i=1;i<=n*3;++i)
        {
            scanf("%d %s",&x,opt);
            if(opt[0]=='Y') ++cnt1[x];
            else ++cnt0[x];
        }
        int sum=0;
        bool flag=0;
        for(int i=0;i<n;++i)
        {
            if(cnt0[i] && cnt1[i]) ++sum;
            if(!cnt0[i] && !cnt1[i]) flag=1;
            if(cnt0[i]>1 && cnt1[i]>1) flag=1;
            if(cnt0[i]==1 && cnt1[i]==1) flag=1;
        }
        if(sum>1 || flag)
        {
            printf("-1\n");
            continue;
        }
        for(int i=0;i<n;++i)
        {
            if(cnt0[i] && cnt1[i])
            {
                if(cnt0[i]==1) putchar('1');
                else putchar('0');
            }
            else if(cnt0[i]) putchar('0');
            else putchar('1');
        }
        putchar('\n');
    }
    return 0;
}

G.KFC Crazy Thursday

难度：medium-easy

明显回文自动机板子题，直接上代码。

#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

难度：easy

特别无语的是这个出题人把样例搞错了，弄的我们队没过样例不敢交。

这个计算几何应该不难，画个图就明白了。

alt

答案为 $(n/2)^2*2+(n/2)^2*\pi/2$ 。

#include<bits/stdc++.h>
using namespace std;

const double pi=acos(-1);
int main()
{
    double n;
    while(cin>>n)
    {
        n/=2;
        printf("%.9f\n",n*n*2+n*n*pi/2);
    }
    return 0;
}

K.Headphones

难度：check-in

确实签到题，因为要拿 $k + 1$ 对耳机，所以至少满足 $k \times 2+1 \le n$ 。

否则，在剩下的 $n - k$ 对耳机中，至少拿 $(n - k) + (k + 1) = n + 1$ 对才能满足条件。

#include<bits/stdc++.h>
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;
}