题解 | #牛客练习赛90#
梦想赛道
https://ac.nowcoder.com/acm/contest/11180/A
梦想赛道
题目描述：
给出一颗树，你需要构造一个图使得这个树在这个图中是一个严格的次小生成树，问图的权值最小可以是多少
思路：
只需要在原树的基础上加一条边即可，因为是要最小权值，所以我们就加1，（加0的话就不是严格的次小生成树了，况且题目中给的最小权值就是1）
有个特殊的情况就是如果这个树的权值全是1，那就无法构造了，因为如果加1，就不是严格次下生成树，如果加大于1的值，就变成最小生成树了，所以这里判一下就可以
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 425
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
//typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 300000 + 10
int n, k, m, x, y, z, q, p;
int op;
string s;
int sum, num;
void work()
{
cin>>n;
for(int i = 1; i < n; ++i){
cin>>x>>y>>z;
if(z == 1)++num;
sum += z;
}
if(num == n - 1)cout<<-1<<endl;
else cout<<sum + 1<<endl;
}
int main(){
io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
寒冬信使
题目描述：
01串，只有一种操作：选择一个1，翻转他和他前一个数
判断先手赢还是后手赢
思路：
先分析一下结束条件：全0
- 如果选择的是
01，那反转后就是10，相当于把1的位置向前移了一位- 如果选择的是
11，那反转以后就是00，相当于消除了两个相邻的1，因为是相邻，所以肯定一个是奇数，一个是偶数，相当于给1的位置向前移动了一个奇数位两种操作都是把1向前移动奇数次，所以我们可以直接统计1的位置的和，判奇偶即可
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 425
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
//typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 300000 + 10
int n, k, m, x, y, z, q, p;
int op;
string s;
int sum, num;
void work()
{
cin>>s;
num = 0;
for(int i = 0; i < s.size(); ++i){
if(s[i] == '1')num += i + 1;
}
if(num % 2)cout<<"T\n";
else cout<<"X\n";
}
int main(){
io;
int tt;cin>>tt;
for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
}
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
盾与战锤
题目描述：
敌人出现了，敌人的技能是获得一个能抵挡一定伤害的护盾。
你有一个长度为
n的攻击序列，每个攻击都会造成一定伤害，你可以选出它的一个 子序列 进行攻击，每一秒按照子序列中的顺序进行一次攻击。敌人开始时拥有一个可以抵抗
s点伤害的护盾，并且它在获得护盾之后第一次被攻击时开始，k 秒之后恢复它的护盾（k 秒后先恢复护盾再被攻击）。但是因为 QuantAsk 忘记了敌人刷盾的时间，所以你要对于 k∈[1,n] 求出最大能对敌人造成的伤害。
思路：
这个题我们需要知道护盾不是说只能破一次，所以我们可以枚举破盾的次数来计算答案
对于每一个k，我们枚举破盾的次数为 j ，可选择的攻击的数量为
k * j次，护盾的总伤害是j * s，理想情况下我们能造成的伤害是sum - j * s，sum指的是选择的k*j次攻击的伤害和，在理想情况下(也就是这 j 个盾都可以在过程中被破开)，我们肯定是尽可能使的sum越大越好，那肯定就是选伤害高的k * j个即可。但是因为是按顺序来的子序列，而不是按我们喜欢的顺序来打，所以会存在非理想的情况，也就是破不了盾的情况，这个时候其实也可以这么来计算，原因是非理想情况下破
j次盾产生的伤害是绝对不会优于j-1次破盾的我们举个例子来理解：
6 7 8 1 1 1 2 9 5 4
盾值为 s = 7
伤害按高到低排序后得到：9 8 7 6 5 4 2 1 1 1
k = 3时，假设能破盾2两次，我们选伤害高的3 * 2个数，也就是9 8 7 6 5 4这六个，放在原数组就是6 7 8 1 1 1 2 9 5 4，可以看到，实际操作的时候会先拿6 7 8，再拿9 5 4，两次都能破盾，所以伤害就是9 + 8 + 7 + 6 + 5 + 4 - 2 * 7 = 25
假设能破盾3次，我们选伤害高的3 * 3个数，也就是9 8 7 6 5 4 2 1 1 放在原数组就是6 7 8 1 1 1 2 9 5 4，先是6 7 8，再是1 1 2， 最后是 9 5 4，很显然1 1 2破不了盾，此时我们计算伤害为：9 + 8 + 7 + 6 + 5 + 4 + 2 + 1 + 1 - 3 * 7 = 22
显然22 < 25，也就如果某一次破不了盾，那他肯定不如上一次的伤害更优，那这里就可以不管
所以我们可以对每个k 都去枚举破盾次数，有了破盾次数就有了攻击次数，有了攻击次数就可以用前缀和来直接获取前多少多少次数的最高伤害，然后就可以更新该 k 的ans了
注意：
- 如果可以用的攻击次数超过n个，就用的是pre[n]来当作伤害
- 还有就是数据范围都是1e18，要开longlong，枚举的变量也记得开longlong
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 425
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
//typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 1000000 + 10
int n, k, m, x, y, z, q, p;
int op;
int s;
ll tr[MAX];
void work()
{
cin>>n>>s;
for(int i = 1; i <= n; ++i)cin>>tr[i];
sort(tr + 1, tr + 1 + n, greater<ll>());
for(int i = 1; i <= n; ++i)tr[i] += tr[i - 1];
for(ll k = 1; k <= n; ++k){//枚举护盾的恢复时间
ll maxn = 0;
for(ll j = 1; ; ++j){//破盾的次数
if(j * k > n){
maxn = max(maxn, tr[n] - j * s);
break;
}
maxn = max(maxn, tr[j * k] - j * s);
}
cout<<maxn<<endl;
}
}
int main(){
io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
妄想集合
题目描述：
开始有 n 个可重集合，开始时每一个集合中都有一个数，有 m个操作。
- 往编号在 l∼r 的每个集合中加入一个数 x
- 询问能否从 l∼r 的集合中取出三个数使得他们能作为边长组成一个三角形（即最小两个和要大于最大的）。
思路1：
当数列中的所有数都是斐波那契数列中的数的时候，任意三个数不能组成三角形
根据上述理论，我们可以计算一下发现1e9中只有44个斐波那契数
那再根据鸽巢原理，如果一个集合的数量大于44，就说明肯定会满足至少存在一种情况使的从中取出来三个数能组成三角形
所以我们可以考虑使用势能线段树，维护一个标记数组，表示线段树的上的区间的数的数量是否大于44，再维护一个num数组，维护区间集合的数字的总数量
因为一个集合最多加44个数就可以了，所以在这之前就暴力修改，大于44后就给标记值更新，表明这个区间此后不用再更新了，查询的时候就查询l到r的集合的num是否大于44即可，如果没有就暴力判断，将[l,r]的集合的所有元素都扔进一个vector，排序以后暴力判断
当然，那个标记数组可以通过维护区间最小值来代替，不过bool来说会快点，所以就用了
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 425
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
//typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 100000 + 10
int n, k, m, x, y, z, q, p;
bool tmp;
string op;
int s;
vector<int>v[MAX];
int num[4 * MAX];
bool vis[4 * MAX];
inline void pushup(int p){
num[p] = num[ls] + num[rs];
vis[p] = vis[ls] & vis[rs];
}
void built(int p, int l, int r){
if(l == r){
num[p] = 1;
vis[p] = 0;
return;
}
int mid = (l + r) / 2;
built(ls, l, mid);
built(rs, mid + 1, r);
pushup(p);
}
void update(int p, int l, int r, int s, int t, int c){
if(s <= l && r <= t && vis[p]){
return;
}
if(l == r){
num[p] += 1;
if(num[p] >= 46)vis[p] = 1;
v[l].push_back(c);
return;
}
int mid = (l + r) / 2;
if(mid >= s)update(ls, l, mid, s, t, c);
if(mid < t)update(rs, mid + 1, r, s, t, c);
pushup(p);
}
int getans(int p, int l, int r, int s, int t){
if(s <= l && r <= t){
return num[p];
}
int mid = (l + r) / 2;
int ans = 0;
if(mid >= s)ans += getans(ls, l, mid, s, t);
if(mid < t)ans += getans(rs, mid + 1, r, s, t);
return ans;
}
void work()
{
cin>>n>>m;
for(int i = 1; i <= n; ++i){
cin>>x;
v[i].push_back(x);
num[i] = 1;
}
built(1, 1, n);
for(int i = 1; i <= m; ++i){
cin>>op;
if(op[0] == 'A'){
cin>>x>>y;
p = getans(1, 1, n, x, y);
if(p < 3){
cout<<"NO\n";
}
else if(p >= 56){
cout<<"YES\n";
}
else{
// cout<<p<<endl;
vector<int>san;
for(int i = x; i <= y; ++i){
for(int j = 0; j < v[i].size(); ++j){
san.push_back(v[i][j]);
}
}
sort(san.begin(), san.end());
tmp = 0;
for(int i = 0; i < san.size() - 2; ++i){
if(san[i] + san[i + 1] > san[i + 2]){
tmp = 1;
break;
}
}
if(tmp){
cout<<"YES\n";
}
else cout<<"NO\n";
}
}
else{
cin>>x>>y>>z;
update(1, 1, n, x, y, z);
}
}
}
int main(){
io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
思路2:
一个新的用法：用并查集实现类似于链式前向星的跳动方式。
总的来说就是说“暴力查询暴力修改”
查询的时候就求[l,r]的集合数的和，与44判断大小关系，大于就是YES，小于的话就暴力判断一下，和上面的一样
修改的时候就是用并查集维护当前集合下一个数量低于44的数组的位置
for(int i = x; i <= y; i = getfa(i + 1)){//i=getfa(i+1)就是类似于链式前向星的跳动方法，跳到下一个不数量低于44的集合 if(v[i].size() > 44)continue; v[i].push_back(z);//更新点 if(v[i].size() == 44)fa[i] = getfa(i + 1);//如果达到44，就把当前的点连到下一个点去，下次并查集找爹的时候就不会找到他了 }
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 425
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
//typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 100000 + 10
int n, k, m, x, y, z, q, p;
bool tmp;
string op;
int s;
vector<int>v[MAX];
int fa[MAX];
inline int getfa(int x){
return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
void work()
{
cin>>n>>m;
for(int i = 1; i <= n; ++i){
cin>>x;
v[i].push_back(x);
}
for(int i = 1; i < MAX; ++i)fa[i] = i;
for(int i = 1; i <= m; ++i){
cin>>op;
if(op[0] == 'A'){
cin>>x>>y;
if(y - x + 1 > 44){
cout<<"YES\n";
continue;
}
int num = 0;
tmp = 0;
for(int i = x; i <= y; ++i){
num += v[i].size();
if(num > 44){
tmp = 1;
break;
}
}
if(!tmp){
vector<int>san;
for(int i = x; i <= y; ++i){
for(int j = 0; j < v[i].size(); ++j){
san.push_back(v[i][j]);
}
}
sort(san.begin(), san.end());
for(int i = 0; i < (int)san.size() - 2; ++i){
if(san[i] + san[i + 1] > san[i + 2]){
tmp = 1;
break;
}
}
}
if(tmp){
cout<<"YES\n";
}
else cout<<"NO\n";
}
else{
cin>>x>>y>>z;
for(int i = x; i <= y; i = getfa(i + 1)){
if(v[i].size() > 44)continue;
v[i].push_back(z);
if(v[i].size() == 44)fa[i] = getfa(i + 1);
}
}
}
}
int main(){
io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
