牛客练习赛97

A. 特别的玛格丽特

对于数组 ,每次交换 ,当且仅当 ,问最终是否可以使数组从小到大排列?

, 再结合题目,由此想到冒泡排序,在排序中多加一个 判断即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
vector<int> a(n);
for(auto &i:a)cin>>i;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(a[i]>a[j]&&(a[i]-a[j])%2==0)swap(a[i],a[j]);
}
}
for(int i=1;i<n;i++)
if(a[i]<a[i-1]){
cout<<"No";
return 0;
}
cout<<"Yes";
}

B. 野比大雄的作业

表示以 最大值

为了方便, 表示以 最大值的 值, 表示以 最大值的 值,答案就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
vector<ll> a(n);
vector<pair<ll,ll>> f(n);
for(auto &i:a)cin>>i;
f[0].first=f[0].second=a[0];
ll ans=f[0].first+f[0].second;
for(int i=1;i<n;i++){
if(a[i]*2>((f[i-1].first&a[i])+(f[i-1].second|a[i]))){
f[i].first=a[i];
f[i].second=a[i];
}
else {
f[i].first=f[i-1].first&a[i];
f[i].second=f[i-1].second|a[i];
}
ans=max(ans,f[i].first+f[i].second);
}
cout<<ans;
}

C. 哦~唔西迪西小姐~

两种可能,走冰之格或走火之格

先考虑走冰之格,如果 ,那么是一定要选上的

再来考虑怎样改变格子状态,若改变的是火之格,那么它的贡献值就是 ,若改变的是冰之格,那么它的贡献值就是 ,那么就选 个最大的就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct dd{
ll pos,a,p;
};
ll n,m;
ll solve(vector<dd> x,vector<dd> y){
vector<ll> b;
for(auto i:x)b.push_back(max(0ll,i.a)-i.p);
for(auto i:y)b.push_back(-max(0ll,i.a)-i.p);
sort(b.begin(),b.end(),[](ll x,ll y){
return x>y;
});
ll ans=0,cnt=0;
for(auto i:b){
if(i<=0)break;
ans+=i;
cnt++;
if(cnt==m)break;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
vector<ll> a(n),p(n);
for(auto &i:a)cin>>i;
for(auto &i:p)cin>>i;
vector<dd> ice,fire;
ll sum_ice=0,sum_fire=0;
for(ll i=0,j;i<n;i++){
cin>>j;
if(j==1){
fire.push_back({i,a[i],p[i]});
sum_fire+=max(0ll,a[i]);
}
else{
ice.push_back({i,a[i],p[i]});
sum_ice+=max(0ll,a[i]);
}
}
ll ans=0;
ans=max(ans,max(sum_ice+solve(fire,ice),sum_fire+solve(ice,fire)));
cout<<ans;
}

D. 月之暗面

树形dp

是染色方案数

是当 染成一个确定的特殊颜色的染色方案数

分析 的状态转移方程:

  • 染成普通颜色时, 方案数为

  • 染成特殊颜色时,方案数为

  • 那么 方案数为

分析 的状态转移方程:

  • 染成一个确定的特殊颜色,则它的儿子一定不能是这个确定的颜色
  • 那么它的儿子的贡献值就是儿子染色方案数减去一个确定的特殊颜色的染色方案数

该题无论哪个点为根,答案都一样,为了方便就取 为树根,则答案为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mo 998244353
#define add(x,y) edge[++tail]={head[x],y};head[x]=tail;
struct Edge{
int ne,to;
}edge[2020201];
int head[1010101],n,tail;
ll f[1010101],g[1010101],p,q;
void dfs(int t,int fa){
f[t]=p;
g[t]=1;
for(int i=head[t];i;i=edge[i].ne){
int to=edge[i].to;
if(to!=fa){
dfs(to,t);
g[t]=(g[t]*(f[to]-g[to]))%mo;
f[t]=f[t]*f[to]%mo;
}
}
f[t]=(f[t]+q*g[t]%mo)%mo;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>p>>q;
for(int i=1,x,y;i<n;i++){
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs(1,0);
cout<<(f[1]+mo)%mo;
}
发布于

2022-03-10

更新于

2022-03-16

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...