竞赛讨论区 > 牛客小白月赛46题解
头像
牛客784438398号
编辑于 2022-03-25 21:41
+ 关注

牛客小白月赛46题解

A.

显然赢 k 次的概率是 的。因此当赢的次数为 时可能性最大。n 为偶数输出 n 为奇数输出 即可。

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin>>n;
	if(n&1)cout<<n/2<<' '<<(n+1)/2<<endl;
	else cout<<n/2<<endl;
} 

B.

显然有 0 的时候和只存在 a-a 两种数的时候无解。

其他情况就直接排序,如果正负数的交界出的两个数和为 0 的话,其中一个换成正负性一样但数字不一样大的,这样就完成了构造。

#include<bits/stdc++.h>
#define mod 1000000007
#define N 1000005
#define int long long
using namespace std;
int n,a[N],cnt;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==0)puts("NO"),exit(0);
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)if(i!=1&&a[i]!=a[i-1])cnt++;
	if(cnt==1&&a[1]+a[n]==0)puts("NO"),exit(0);
	puts("YES");
} 
C.

双指针+map维护每个单词出现的次数即可。
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int data=10,n,k,l,r;
string word[N];
long long ans;
map<string,int>cnt;
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>word[i];
	l=1;
	for(int i=1;i<=n;i++){
		while(i-l>k+1){
			cnt[word[l]]--;
			l++;
		}
		ans+=cnt[word[i]];
		cnt[word[i]]++;
	}
	cout<<ans<<endl;
}

D.

显然可能走到的只有父亲,父亲的父亲,儿子,儿子的儿子,自己,父亲的儿子六种情况。分类讨论,父亲,父亲的父亲,儿子就直接看能不能到。这时顺便给父亲的父亲也加上就不用考虑儿子的儿子了。至于父亲的儿子,就看能不能1步到父亲,在看父亲1步能到的儿子数量(不包括自己)。

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,u,f[N],son[N],w[N],ans[N];
long long dep[N];
struct node{
	int to,dis;
};
vector<node>e[N];
void dfs1(int now){
	if(f[f[now]]&&dep[now]-dep[f[f[now]]]<=2)ans[now]++,ans[f[f[now]]]++;
	for(int i=0;i<e[now].size();i++){
		int y=e[now][i].to;
		if(e[now][i].dis==1)son[now]++;
		if(e[now][i].dis<=2)ans[now]++,ans[y]++;
		dep[y]=dep[now]+e[now][i].dis;
		dfs1(y);
	}
}
void dfs2(int now){
	if(w[now]==1)ans[now]+=son[f[now]];
	else ans[now]++;
	for(int i=0;i<e[now].size();i++){
		int y=e[now][i].to;
		dfs2(y);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		scanf("%d%d",&f[i],&w[i]);
		e[f[i]].push_back((node){
			i,w[i]
		});
	}
	dfs1(1);
	dfs2(1);
	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
} 

E.

我们先从小到大排序。对于每个人,我们先让他把能力小于等于他的人干掉,如果已经有了 k 次比赛或还差一个的话直接看能不能把最强的人用两个道具干掉(其他的由最强的干掉)。这时有一个特例,就是能力值为 的人可以用乘 2 的道具干掉能力值为 的人,能力值为 x 的人可以用除 2 的道具干掉能力值为 的人。这个特判一下,其他的例子可以对能力值最大的人 分类讨论排除。如果还差两次,看能不能用道具干掉剩下最强的和最弱的,其他还是由最强的干掉。如果差的不止两次肯定没戏。

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,k,ans[N],now,flag;
struct node{
	int x,p;
}a[N];
bool cmp(node u,node v){
	return u.x<v.x;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i].x,a[i].p=i;
	sort(a+1,a+n+1,cmp);
	if(a[n].x%4==2)for(int i=1;i<=n;i++)if(a[i].x==a[n].x/2)flag=1;
	for(int i=1;i<=n;i++){
		while(a[now+1].x<=a[i].x&&now<n)now++;
		if(k-(now-1)>2)continue;
		if(now>=k){
			if(a[i].x*2>=a[n].x/2||(flag&&a[i].x>=a[n].x/4)){
				for(int j=i;j<=n;j++)ans[a[j].p]=1;
				break;
			}
			else continue;
		}
		else{
			if(a[i].x>=a[n].x/2&&a[i].x*2>=a[now+1].x){
				for(int j=i;j<=n;j++)ans[a[j].p]=1;
				break;
			}
			else continue;
		}
	} 
	for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
	cout<<endl;
} 

F.

首先我们只考虑 两个条件。可以先把 的部分提出来算,这时对于每个满足 v 都是成立的。然后如果我们取一个小于 ku,就只有 k-uu-1 中的数可以作为 v 的取值,然后用等比数列求和的相关知识求就好了。这时我们尝试加进去 的条件,发现当且仅当 时不满足这个的条件且 ,所以只要减去这部分就行了。
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int T,n,k,ans;
int q(int x){
	return x*(x+1)/2;
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n>>k;
		if(k==1){
			cout<<q(n-1)<<endl;
			continue;
		}
		if(n>=k)ans=q(n-1)-q(k-2),n=k-1;
		else ans=0;
		if(k-1!=1&&1<=n&&k-1<=n)ans--;
		int tmp=(k+1)/2;
		if(tmp<=n)ans=ans-k*(n-tmp+1)+2*(q(n)-q(tmp-1));
		cout<<ans<<endl;
	}
} 

最后,出题人为这场比赛出锅的题面,B题过水的数据和毒瘤道歉qwq

全部评论

(6) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐