牛客练习赛90题解

A题

题意：给出一个n个点的有边权的树，求一个图满足给出的树是图上的一个严格次小生成树（注意原树上的边权不能改变）且该图的所有边权和最小，并且要求所有的边权都是正整数。无解输出-1

解：注意：题目中写明可以有重边，严格次小声成树代表图中一定有一条权比当前小的边，并且可以想到只需要添加这一条边就可以满足条件。边权和需要最小且边权是正整数，所以我们只需要任意找一条边添加一个边权为1的边，无解的情况是这棵严格次小生成树的所有边权都是1.

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

int n,x,y,z,s;
int ans;

int main()
{
	cin>>n;
	for(int i = 1;i < n; ++i)
	{
		cin>>x>>y>>z;
		ans += z;
		if(z == 1) s++;
	}	
	if(s == n - 1) cout<<"-1\n";
	else cout<<(ans + 1)<<'\n';
	return 0;
}

B题

题意：给出一个01串，两人轮流操作，每次选择一个1的格子，将这个格子和前面的一个格子翻转，最后无法操作者败，问先手是否有必胜策略

解：可以发现只有两种情况：

01->10

11->00

考虑1的位置之和，第一种操作似的位置和-1（选第一个格子可以看作把1转移到了0这个位置），第二种使得位置和-（i+i+1）（假设选择的两个格子分别是i和i+1），可以发现这两种操作都会使得和的奇偶性发生改变。

因为最终状态是00000，位置和为偶数，所以只有当初始位置和为偶数的时候，先手必胜。

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

int t;
string s;
int ans;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>s;
		ans = 0;
		int x = s.size();
		for(int i = 0;i < x; ++i)
		{
			if(s[i] == '1' && i % 2 == 0) ans++; 
		}
		cout<<(ans % 2 == 1 ? 'T':'X')<<'\n';
	}
	return 0;
}

C题

题意：有一个长度为n的伤害序列，可以选择一个子序列进行攻击，对方又一个盾牌，可以抵抗m点伤害，每k分钟更新一次，问k取1、2...n时，最多可以造成多少伤害

解：首先可以知道，如果在k秒内没有击穿盾牌，是无意义的。

对更新时间为k，枚举更新了i次，排序选择最大的ik个，减去im就是i次时最大的伤害。

例如：

m = 10

序列为5 6 7 1

k=2时，i = 1，ans = （6 + 7） - 10 = 3

i = 2，ans = （5 + 6 + 7 + 1）- 20 = -1

可以发现的是，如果有一段区间没有击穿，那么结果一定是要比之间更差的。

所以直接排序后枚举即可，复杂度O（Nlog N）

复杂度其实是（n/1+n/2+n/3+...+n/n）即n * （1/1+1/2+...+1/n），后面是一个调和级数，复杂度可以看作O（NlogN）

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

const int N = 1e6 + 10;
ll n,m;
ll a[N],ans;

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i <= n; ++i) cin>>a[i];
	sort(a + 1,a + n + 1);
	reverse(a + 1,a + n + 1);
	for(int i = 1;i <= n; ++i) a[i] += a[i - 1];
	for(int k = 1;k <= n; ++k)
	{
		ans = 0;
		for(int i = 1;(i - 1) * k <= n; ++i)
			ans = max(ans,a[min(1ll * i * k,n)] - i * m);//,cout<<a[i * k]<<'\n';
		cout<<ans<<'\n';
	}
	return 0;
}

D题

题意：n个可重集合，操作有两种：

1.l-r区间内的集合插入数字x

2.询问能否从l-r区间内的集合里取3个数字构成一个三角形

解：首先不能构成三角形的条件是这个序列是一个斐波那契序列。

可以发现当序列数字超过45的时候，最大值超过1e9，所以只要数字个数超过45个，就必然能构成三角形，不够的话暴力看能否构成即可。