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

虽然这场题面数据idea啥的出了很多锅，但是评价题是佬们的事情，像我这种菜比就应该好好补题了。。。

K Headphones

一共有n对耳机，其中一人已经拿出k对，问另一人要是想拿出大于k对的耳机，至少要取多少只，耳机是蓝牙耳机，一只一只相互配对。

思路：简单容斥原理，考虑最坏情况下最少拿多少可以凑成k+1对，即一开始拿的时候每对取了一只。

 AC Code：

#include <bits/stdc++.h>

typedef long long ll;
ll n,k;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    while(std::cin>>n>>k){
        if(n-k<k+1) std::cout<<-1<<'\n';
        else std::cout<<n+1<<'\n';
    }
    return 0;
}

B Watches

给定n件物品和编号i，买k件物品每件的花费为a[i]+k*i，问给出一个钱数，最多可以买几件物品。

思路：不难想到我们可以二分答案k，对于每个k，贪心购买k件物品，判断和给出钱数的关系，时间复杂度为O(nlogn^2)，能过。

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
int n,m;
ll a[N];

struct node{
    ll val;
}e[N];

bool cmp(node a,node b){
    return a.val<b.val;
}

bool check(int mid){
    for(int i=1;i<=n;i++){
        e[i].val=a[i]+(ll)i*(ll)mid;
    }
    std::sort(e+1,e+1+n,cmp);
    ll sum=0;
    for(int i=1;i<=mid;i++){
        sum+=e[i].val;
    }
    if(sum>m) return true;
    else return false;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    while(std::cin>>n>>m){
        for(int i=1;i<=n;i++){
            std::cin>>a[i];
        }
        int l=0,r=n;
        while(l<r){
            int mid=(l+r+1)/2;
            if(check(mid)) r=mid-1;
            else l=mid;
        }
        std::cout<<l<<'\n';
    }
    return 0;
}

 H Cutting Papers

给出一个不等式和圆形的描述，计算两个图形在坐标轴上并集的面积大小。

思路：根据不等式和圆形描述画出图形，即：

计算的就是灰色部分和圆形的并集，直接按照数值计算即可。

AC Code：

#include <bits/stdc++.h>

const double PI=acos(-1);
double n;

int main(){
	while(~scanf("%lf",&n)){
		printf("%.9lf\n",n*n/(double)2+PI*n*n/(double)8);
	}
	return 0;
}

 C Bit Transmission

给出n*3个询问，每个询问给出关于该位是否是1的回答，所有的回答中至多有1个是错误的，问是否可以得到原来的答案，否则输出-1。

思路：我们可以记录每一位YES和NO的个数。先看不能得到答案的情况：如果存在不被问到的位置，输出-1；如果某一位YES/NO次数相同，输出-1；如果某一位YES/NO次数均大于1，输出-1；否则，我们判断下是否存在YES和NO均出现过的位置，假设共出现x次，如果x>1，输出-1；如果x=1，表明错误位置确定，此时能够确定唯一字符串； 如果x=0，那么我们判断下是否存在YES和NO总共出现1次的位置，存在表明无法确定，否则则能够唯一确定字符串。

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
const int N=1e5+5;
int n;
int ans[N];

struct node{
	int y,n;
}e[N];

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>n;
	for(int i=1;i<=3*n;i++){
		int pos;
		std::string s;
		std::cin>>pos>>s;
		if(s=="YES") e[pos].y++;
		else e[pos].n++;
	}
	int cnt=0;
	for(int i=0;i<n;i++){
		if(e[i].y&&e[i].n) cnt++;
		if(cnt>1){
			std::cout<<-1<<'\n';
			return 0;
		}
		if(e[i].y==e[i].n){
			std::cout<<-1<<'\n';
			return 0;
		}
		if(!e[i].y&&!e[i].n){
			std::cout<<-1<<'\n';
			return 0;
		}
		if(e[i].y>1&&e[i].n>1){
			std::cout<<-1<<'\n';
			return 0;
		}
		if(e[i].y>e[i].n) ans[i]=1;
		else  ans[i]=0;
	}
	if(!cnt){
		bool flag=false;
		for(int i=0;i<n;i++){
			if(e[i].y+e[i].n==1){
				flag=true;
			}
		}
		if(flag){
			std::cout<<-1<<'\n';
			return 0;
		}
	}
	for(int i=0;i<n;i++){
		std::cout<<ans[i];
	}
	std::cout<<'\n';
	return 0;
}

os：实质就是一个模拟， 不过分类讨论题真的ex。

G KFC Crazy Thursday

输出以三个字母为结尾的回文串数目。

思路：回文自动机(PAM)裸题，可以学习。

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
const int mod=1e9+7;
const int N=5e5+5;
int n;
char str[N];

struct PAM {
    int size,last,r0,r1;
    int trie[N][26],fail[N],len[N],cnt[N];
    PAM(){
        r0=size++,r1=size++;last=r1;
        len[r0]=0,fail[r0]=r1;
        len[r1]=-1,fail[r1]=r1;
    }
    void insert(int ch,int idx){
        int u=last;
        while(str[idx]!=str[idx-len[u]-1])u=fail[u];
        if(!trie[u][ch]){
            int cur=++size,v=fail[u];
            len[cur]=len[u]+2;
            for(;str[idx]!=str[idx-len[v]-1];v=fail[v]);
            fail[cur]=trie[v][ch];
            trie[u][ch]=cur;
            cnt[cur]=cnt[fail[cur]]+1;
        }
        last=trie[u][ch];
    }
    void build(char* str){
        int len=strlen(str);
        int K=0,C=0,F=0;
        for(int i=0;i<len;i++){
            insert(str[i]-'a'+1,i);
            if(str[i]=='k') K+=cnt[last];
            if(str[i]=='f') F+=cnt[last];
            if(str[i]=='c') C+=cnt[last];
        }
        printf("%d %d %d\n",K,F,C);
    }
}pam;

int main(){
    while(~scanf("%d",&n)){
        scanf("%s",str);
        pam.build(str);
    }
    return 0;
}

A Don’t Starve

给定n个点有食物（每个点可以吃多次），每个点有一个坐标，对与行走的规则是每一步都必须严格短于上一步，问最优的方案下能够吃到多少次食物。

思路：标解：我们考虑设立状态f[i][j]表示上一步在i，当前这步走到j了的情况下最多已经吃到次数是多少，而对于转移，因为我们知道了最近两步的行走，所以可以直接计算出上一步的长度从而进行转移了。（实际上我还是不太明白这个是怎么转移的呜呜呜）

AC Code：

#include <bits/stdc++.h>

#define int long long
const int N=3e3+5;
const int M=6e6+5;
int n,ans,cnt;
int f[N][N],tong[N];

struct Point{
	int x,y;
}e[N];

struct node{
	int u,v,w;
	bool operator <(const node &a)const{
		return w<a.w;
	}
}edge[M];

int dis(int u,int v){
	return (e[u].x-e[v].x)*(e[u].x-e[v].x)+(e[u].y-e[v].y)*(e[u].y-e[v].y);
}

signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>n;
	for(int i=1;i<=n;i++){
		std::cin>>e[i].x>>e[i].y;
	}
	for(int i=0;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) continue;
			cnt++;
			edge[cnt]={i,j,dis(i,j)};
		}
	}
	std::sort(edge+1,edge+1+cnt);
	for(int i=1;i<=cnt;){
		int b=i,e=i;
		while(edge[b].w==edge[e].w){
			int last=edge[e].u,cur=edge[e].v;
			f[last][cur]=std::max(f[last][cur],tong[cur]+1);
			++e;
		}
		for(int j=b;j<e;j++){
			int last=edge[j].u,cur=edge[j].v;
			tong[last]=std::max(tong[last],f[last][cur]);
		}
		i=e;
	}
	for(int i=1;i<=n;i++){
		ans=std::max(ans,f[0][i]);
	}
	std::cout<<ans<<'\n';
	return 0;
}

直接补不动了