2022牛客多校联赛第五场 题解

比赛传送门
作者： fn

---

前言（一点吐槽）

本场的E、F是两道原题，并且有好几题的数据锅了。。。

签到题

K题 Headphones / 耳机

题目大意
NIO和他的妹妹想从抽屉里拿些耳机。雅莎就拿出了 $k$ 对耳机。NIO应该带多少只耳机才能确保他比他姐姐得到更多的耳机，即 $k+1$ 对耳机。假设抽屉中有 $N$ 对耳机，每对耳机都不同。

考察内容
签到

分析
分类讨论。
$n-k\le k$ 时答案存在，答案为 $n-k+k+1$

#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e6+10;
ll n,m,k,a[N];
string s;
int main(){
     
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>k;
	
	if(n-k<=k){
    
		cout<<"-1"<<endl;
	}
	else{
     
		cout<<n-k + k+1<<endl;
	}

	return 0;
}
/* */ 

---

B题 Watches / 手表

题目大意
NIO是手表店的老板。有一天，他想从工厂买一批手表。然而，他住的国家的税收很高。如果他买 $k$ 块手表，他名单上的那块手表要花他 $a_i$ 块钱加上 $k\times i$ 美元的税。（i是原先给的序号)

现在NIO只有 $M$ 美元，所以NIO问你他最多能买多少块手表。

考察内容
二分答案

分析
直接在 $0$ 到 $n$ 之间二分答案，check时选最便宜的手表即可。

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
struct node1{
    
    ll p;
}arr1[100010];

struct node2{
    
    ll end;
}arr2[100010];

int n,m;

bool cmp(node2 a,node2 b){
    
    return a.end<b.end;
}

bool ck(ll k){
    
    for(int i = 1;i<=n;i++){
    
        arr2[i].end = arr1[i].p+k*i;
    }
    sort(arr2+1,arr2+1+n,cmp); // 价格小的先买 
    
    int sum = 0;
    for(int i = 1;i<=k;i++){
    
        sum+=arr2[i].end;
    }
    if(sum<=m) return true;
    else return false;
}

signed main(){
    
    while(scanf("%lld %lld",&n,&m)!=EOF){
    
        for(int i = 1;i<=n;i++){
    
            scanf("%lld",&arr1[i].p);
        }
        
        int l = 0;
        int r = n;
		ll mid;
        int ans = 0;

		while(l<r){
    
			int mid=(l+r+1)>>1;
			if(ck(mid))l=mid; else r=mid-1;	
		}

        printf("%lld\n",l);
    }
}
/* 4 13 3 4 5 6 */

---

H题 Cutting Papers / 剪纸

题目大意
求一块斜的六边形和一个圆面积的并集。

考察内容
数学

分析
直接画图计算。

#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const double pi=3.14159265358979323846264338327950288419716939937510;

double n;
int main(){
     
	cin>>n;
	
	double ans=2*(n*0.5)*(n*0.5)+0.5*pi*(n*0.5)*(n*0.5);
	
	printf("%.7f\n",ans);
	return 0;
}
/* */ 

---

基本题

G题 KFC Crazy Thursday / 肯德基疯狂星期四

题目大意
求字符串中以“k”、“f”和“c”结尾的回文数的数量。

考察内容
回文树

分析
回文树板子题。

#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int MAXN = 5e5+5;
struct node {
    
    int next[26];// 指向在当前节点串的基础上左右两边同时添加相同字符后形成的回文串 
    int len;// 此节点串的长度 
    int sufflink;// 此节点的最长后缀回文串的指针 
    int num;// 此节点中的回文子串的个数 
};
 
int len;
char s[MAXN];
node tree[MAXN];
int num;            // node 1 - root with len -1, node 2 - root with len 0
int suff;           // max suffix palindrome
long long ans;
 
bool addLetter(int pos) {
    
    int cur = suff;// 当前以pos-1结尾的最长后缀回文子串的节点标号（即p的长度） 
	int curlen;
    int let = s[pos] - 'a';
	// 沿着后缀链接边找到满足xAx形式的最长后缀回文子串 
    while (true) {
    
        curlen = tree[cur].len;// 当前A的长度 
        // 判断xAx的两个x处的的字母是否都是x 
        if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
            break;
        cur = tree[cur].sufflink;// 沿着后缀链接边找 (节点下标)
    }
    // 找到xAx后接着找此节点是否存在
	// 注意：节点表示A的next指针指向xAx，每个节点表示的是一个回文串 
	// xAx即为 以pos下标结尾的最长后缀回文子串的标号
    if (tree[cur].next[let]) {
    
        suff = tree[cur].next[let];// 保留当前以pos下标结尾的最长后缀回文子串的标号（已经有的） 
        return false;
    }
	// 每增加一个节点，num++ 
    num++;
    suff = num;// 保留当前以pos下标结尾的最长后缀回文子串的标号(新增加的)
    tree[num].len = tree[cur].len + 2;// 增加了连个x 
    tree[cur].next[let] = num;// 节点表示A的next指针指向xAx
	// 判断A是都对应长度为-1的根 
    if (tree[num].len == 1) {
    
        tree[num].sufflink=2;// 指向长度为0的根 
        tree[num].num = 1;
        return true;
    }
	// 接下来找tree[num].sufflink 
    while (true) {
    
        cur = tree[cur].sufflink;
        curlen = tree[cur].len;
        if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
    
            tree[num].sufflink=tree[cur].next[let];
            // tree[cur].next[let]--->xBx 
            break;
        }
    }
    // 求num节点中回文串的个数
	// 就是回文串xBx的个数加一(多了一个xAx) 
    tree[num].num = 1 + tree[tree[num].sufflink].num;
    return true;
}
 
void initTree() {
    
    num = 2; suff = 2;
    tree[1].len = -1; tree[1].sufflink = 1;// 长度为-1的根 
    tree[2].len = 0; tree[2].sufflink = 1;// 长度为0的根 
}
 
int main() {
    
	cin>>len; 
    scanf("%s", s);
 
    initTree();
 	ll ansk=0,ansf=0,ansc=0;
 	
    for (int i = 0; i < len; i++) {
    
        addLetter(i);
        
        if(s[i]=='k'){
    
        	ansk += tree[suff].num;// 加上每个节点的回文串个数 
        }
        else if(s[i]=='f'){
    
        	ansf += tree[suff].num;
        }
        else if(s[i]=='c'){
    
        	ansc += tree[suff].num;
        }
	}
    cout << ansk<<' '<<ansf<<' '<<ansc << endl;
    return 0;
}

---

C题 Bit Transmission / 位传输

题目大意
对一个01序列询问，返回的结果最多有一个是错的。
求是否可以确定一个唯一的01序列，如果可以确定则输出这个序列。

考察内容
模拟

分析
分类讨论模拟一下。
对一个点询问3次以上且发现有1次误报时，对其他点的1次询问肯定是准确的。
没有发现误报时，对其他点的1次询问是不准确的。

#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e5+10;
ll n;
vector<int> v[N];
ll num[N];
int ans[N];

string s;
int main(){
     
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	while(cin>>n){
     
		for(int i=0;i<n;i++){
    
			v[i].clear();
		}
		memset(num,0,sizeof(num[0])*(n+1));
		memset(ans,0,sizeof(ans[0])*(n+1));
		
		ll h=n*3;
		ll op;
		for(int i=1;i<=h;i++){
    
			cin>>op>>s;
			num[op]++;
			if(s=="YES"){
    
				v[op].push_back(1);
			}
			else{
    
				v[op].push_back(0);
			}
		}
		
		int F=1;
		for(int i=0;i<n;i++){
    
			if(num[i]==0){
     // 没有被询问到
				F=0;
				break;
			}
		}
		if(!F){
     // 存在没有被询问到的位置 
			cout<<-1<<endl;
			continue;
		}
		
		// 都被询问过时 
		F=1; //
		int has1=0; // 有1的情况 
		for(int i=0;i<n;i++){
    
			ll sum=0; 
			for(auto a1:v[i]){
    
				sum+=a1;
			}
			
			if(num[i]>=3){
     // 询问了大于3次 
				if(sum==0){
     // 全都是0 
					ans[i]=0;
				}
				else if(sum==1){
     // 一个误报为1 
					ans[i]=0; 
					if(F==1){
    
						F=2; // 用掉了错误机会 
					} 
					else if(F==2){
    
						F=0;
					}
				}
				else if(sum==num[i]-1){
     // 一个误报为0
					ans[i]=1;
					if(F==1){
    
						F=2; // 用掉了错误机会 
					} 
					else if(F==2){
    
						F=0;
					}
				}
				else if(sum==num[i]){
     // 全都是1
					ans[i]=1;
				}
				else{
    
					F=0; // 答案不存在 
					break;
				} 
			}
			else if(num[i]==2){
     // 询问 
				if(sum==1){
    
					F=0; // 答案不存在 
				}
				else if(sum==2){
    
					ans[i]=1;
				} 
				else{
     // sum==0
					ans[i]=0;
				}
			}
			else if(num[i]==1){
    
				has1=1; // 
				if(sum==1){
    
					ans[i]=1;
				}
				else{
     // sum==0
					ans[i]=0;
				}
			}
		}
		if(F==0){
     // 答案不存在
			cout<<-1<<endl;
			continue;
		}
		else if(F==2){
     // 找到误报 
			for(int i=0;i<n;i++){
    
				cout<<ans[i];
			}
			cout<<endl;
		} 
		else{
     // F==1，没发现误报 
			if(has1){
    
				cout<<-1<<endl;
			}
			else{
     // 询问都在2次以上 
				for(int i=0;i<n;i++){
    
					cout<<ans[i];
				}
				cout<<endl;
			}
		}
	}
	return 0;
}
/* 输入ctrl+Z结尾 */ 

---

F题 A Stack of CDs / 一叠CD

题目大意
有 $n$ 个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红色线条的总长度即为所求。

考察内容
数学知识

分析
洛谷原题

依次枚举每个圆，覆盖的时候记录覆盖的曲线的左右端点即可。

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

const int maxn = 10005;
const double pi = 3.1415926535897932;
const double pi2 = 2*pi;

struct Point{
    
	double x, y;
};

inline double sqr(double x){
    
	return x*x;
}

inline double get_dist(Point x, Point y){
    
	return sqrt(sqr(x.x-y.x) + sqr(x.y-y.y));
}

struct Circle{
    
	Point O;
	double r;
} c[maxn];

inline double get_dist(Circle x, Circle y){
    
	return get_dist(x.O, y.O);
}

int n;

struct Fugai{
    
	double l, r;

	inline bool operator < (const Fugai& other) const{
    
		return l < other.l;
	}
} fugai[maxn];

int nown;
inline void cha(double l, double r){
    
	fugai[++nown] = (Fugai){
    
		l, r
	};
}

bool gaif = false;// gaif = true表示该圆盘被上面的大圆盘完全覆盖

inline void jiao(Circle A, Circle B){
    
	double dist = get_dist(A, B);
	if(dist > A.r+B.r || A.r + dist < B.r)// 没有任何覆盖
		return;
	if(dist + B.r < A.r)// 如果被一个大圆盘完全覆盖，直接跳出
	{
    
		gaif = true;
		return;
	}
	double alpha = acos((sqr(B.r)+sqr(dist)-sqr(A.r))/(B.r*dist*2.));// 上图中的角CAD
	double beta = atan2(B.O.y-A.O.y, A.O.x-B.O.x);// 上图中的角CAE
	double jiao1 = beta-alpha;// 线段覆盖中的l
	double jiao2 = beta+alpha;// 线段覆盖中的r
	if(jiao1 < 0 && jiao2 < 0)// 对极角的一些特判
	{
    
		jiao1 += pi2, jiao2 += pi2;
	}
	if(jiao1 >= 0 && jiao2 <= pi2)
		cha(jiao1, jiao2);
	else
	{
    
		if(jiao1 < 0)
		{
    
			cha(jiao1+pi2, pi2);
			cha(0, jiao2);
		}
		else
		{
    
			cha(jiao1, pi2);
			cha(0, jiao2-pi2);
		}
	}
}

inline double get_ans()
{
    
	double ans = 0;
	sort(fugai+1, fugai+nown+1);
	double lastr = fugai[1].l;
	for(int i = 1; i <= nown; ++i)
	{
    
		if(lastr >= fugai[i].r)
			continue;
		if(fugai[i].l > lastr)
			ans += fugai[i].r - fugai[i].l;
		else
			ans += fugai[i].r - lastr;
		lastr = fugai[i].r;
	}
	return ans;
}

int main(){
    
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%lf%lf%lf", &c[i].O.x, &c[i].O.y, &c[i].r);
	double ans = 0;
	for(int i = n; i; --i)
	{
    
		nown = 0;
		for(int j = n; j > i; --j)// 枚举所有该圆盘之后的圆盘
		{
    
			jiao(c[j], c[i]);
			if(gaif)
				break;
		}
		if(gaif)
			gaif = false;
		else
			ans += (pi2-get_ans())*c[i].r;
		nown = 0;
	}
	printf("%.7f", ans);
	return 0;
}

---

进阶题

D题 Birds in the tree / 树上的鸟

题目大意
给定 $n$ 个节点的树，树上每个节点的颜色为0或1，问最终有多少个子树（连通块）的所有叶子颜色都是一样的。

考察内容
树形dp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define maxn 300005
ll ans;
ll a[maxn], b[maxn], c[maxn], d[maxn];
char ch[maxn];
vector<int> vec[maxn];
void dfs(int u, int fa) {
    
	ll p = 1, q = 1;
	for (int i = 0; i < vec[u].size(); i++) {
    
		int v = vec[u][i];
		if (v == fa) continue;
		dfs(v, u);
		p = (p * (a[v] + 1)) % mod;
		q = (q * (b[v] + 1)) % mod;
	}
	if (ch[u] == '0')p = (p + mod - 1) % mod;
	else q = (q + mod - 1) % mod;
	for (int i = 0; i < vec[u].size(); i++) {
    
		int v = vec[u][i];
		if (v == fa) continue;
		if (ch[u] == '1')ans = (ans - b[v] + mod) % mod;
		else ans = (ans - a[v] + mod) % mod;
	}
	a[u] = p;
	b[u] = q;
	ans += p + q;
	ans %= mod;
}
int main(){
     // 树形dp
	int n;
	scanf("%d", &n);
	scanf(" %s", ch + 1);
	for (int i = 1; i < n; i++) {
    
		int a, b;
		scanf("%d%d", &a, &b);
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	
	dfs(1, 0);
	
	printf("%lld", ans);
	return 0;
}

---

A题 Don’t Starve / 《饥荒》

题目大意
给定 $n$ 个有食物的点，每个点可以吃多次。
每个点有一个坐标，从原点开始行走，每一次行走都必须严格短于上一步，问最优的方案下能够吃到多少次食物。

考察内容
动态规划

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2010;

int n;
int x[N],y[N];

struct edge{
    
	int dis,x,y;
}a[N*N];

int cmp(edge x,edge y){
    
	return x.dis>y.dis;
}
int sta1[N*N],sta2[N*N],top; 
int tot;

int Max[N];
void Commit(){
    
	while(top){
    
		Max[sta1[top]]=max(Max[sta1[top]],sta2[top]);
		top--;
	}
}

signed main(){
     // dp
	// 输入数据 
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
    
		scanf("%lld %lld",&x[i],&y[i]);
	}
	
	for(int i=1;i<=n+1;i++){
    
		for(int j=1;j<=n;j++){
    
			if(i==j) continue;
			
			a[++tot]=(edge){
    
				(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]),i,j
			};
		}
	}

	sort(a+1,a+tot+1,cmp); // 按照边长从大到小排序 

	// 初始化Max数组 
	for(int i=1;i<=n;i++)
		Max[i]=-1000000000;
		
	// 转移 
	for(int i=1;i<=tot;i++){
    
		if(a[i].dis!=a[i-1].dis) 
			Commit();
			
		int tmp=Max[a[i].x]+1;
		sta1[++top]=a[i].y;
		sta2[top]=tmp;
	}
	Commit();
	
	
	int ans=0;
	for(int i=1;i<=n;i++)
		ans=max(ans,Max[i]);
	cout<<ans<<endl;
}

---