Codeforces Round 881 (Div. 3)（A~F1题解）

这场比赛可能是因为比较老吧，我感觉很轻松，就是第五个卡了一下，看错题了，原本应该是严格大于的，从而导致代码一直出现bug，在1小时20分钟才解决

A. Sasha and Array Coloring

题意：就是说给你n个组数，然后你可以给每个数一个颜色，让我们判断每个颜色种类内的最大值和最小值的差值的累加和最大是多少

思路：先排序，将数组分成两部分然后用最大值减去最小值，算累加和就可以求出来

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int a[200005];void solve()
{cin>>n;int len=n/2;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);int ans=0;for(int i=n;i>n-len;i--)ans+=a[i];for(int i=1;i<=len;i++)ans-=a[i];cout<<ans<<"\n";;
}signed main()
{cin>>t;while(t--)solve();return 0;
}

B. Long Long

题意：就是说给你一个数组，然后你可以每次选择翻转一个区间，区间内的值变成相反数，然后问你最少翻转几次，才能让整个数组的最大累加和

思路：想要得到最大值肯定就是将所有负数翻转成正数，所以我们的数组最大值就是所有元素的绝对值之和，那么我们考虑最少翻转问题？

什么时候才需要翻转呢？当我们碰到负数才需要翻转。什么时候停止翻转？当碰到正数的时候就要停止翻转，我们用flag去记录状态，flag=0，表示没有在翻转状态，当flag=1，表示当前在翻转状态

当我们flag=0时，碰到负数，翻转次数就要+1，同时将flag变成1。当我们flag=1时，当我们碰到正数就要停止翻转状态，同时将flag变成0

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int a[200005];void solve()
{cin>>n;int ans=0,cnt=0;for(int i=1;i<=n;i++){cin>>a[i];ans+=abs(a[i]);}int flag=0;for(int i=1;i<=n;i++){if(a[i]<0&&flag==0){flag=1;cnt++;}else if(flag==1&&a[i]>0){flag=0;}}cout<<ans<<" "<<cnt<<"\n";
}signed main()
{cin>>t;while(t--)solve();return 0;
}

C. Sum in Binary Tree

 

题意：就是说给你一个数n，让你判断，从1到n这个路径上的所有数的累加和是多少

 思路：感觉比第二个还水，三分钟写完，就用到了一个二叉树的性质，假设根节点是1的话，那么对于i节点来说，其左子节点是2*i，右子节点是2*i+1,

于是我们就可以反推，假设我们当前n节点是奇数，那么(n-1)/2就是其父节点，如果n节点是偶数的话，那么n/2就是其父节点，然后累加起来就行

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int a[200005];void solve()
{cin>>n;int sum=0;while(n){sum+=n;if(n%2==1)n=(n-1)/2;elsen/=2;}cout<<sum<<"\n";
}signed main()
{cin>>t;while(t--)solve();return 0;
}

D. Apple Tree

题意：就是说树上有两个苹果，而且是可以在树上的任意节点，其下落过程只能下落在其子节点上，问你这两个苹果下落的组合有多少种情况

思路：其实读懂题之后你就会发现，最终的结果数就是两个苹果最低端的叶子结点总数的乘积

我们用dp[i]表示，第i个节点有dp[i]个叶子节点，我们深搜跑一遍，碰到叶子结点就是dp[n]=1;

碰到子节点就是dp[v]+=dp[u]（v是当前结点，u是v的子节点）

#include <bits/stdc++.h>
using namespace std;
#define int long longint t;
int n, q;
int dp[200005];  
vector<int> e[200005]; void dfs(int v, int fa) 
{dp[v] = 0; bool isLeaf = true; for (int u : e[v]) {if (u != fa) {isLeaf = false;dfs(u, v); dp[v] += dp[u]; }}if (isLeaf) {dp[v] = 1;}
}void solve() 
{cin >> n;for (int i = 1; i <= n; ++i) {e[i].clear(); dp[i] = 0;    }int u, v;for (int i = 1; i <= n - 1; ++i) {cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}dfs(1, 0);cin >> q;for (int i = 1; i <= q; ++i) {cin >> u >> v;cout << dp[u] * dp[v] << "\n"; }
}signed main() 
{ios_base::sync_with_stdio(false);  cin.tie(0);  cout.tie(0);  cin >> t; while (t--) {solve(); }return 0;
}

E. Tracking Segments

题意：就是说给你一个长度为n的数组，数组里面的每个数都是0，然后给你m个询问序列，每次给你一个L和R，问你这段区间内的1的数量能否严格大于0的数量，然后给你q个操作，每次可以将x位置的0变成1，然后问你最少操作几次，就可以让上述m个区间里面，有一个能够让其1的数量能否严格大于0的数量

思路：一眼前缀和+二分，但是我没有注意到严格大于，被卡了40分钟，现在想来纯纯裂开

我们的二分的答案，肯定是在1~q之间，那么我们跑一遍二分，然后去判断，mid前的操作能否让上述m个区间里面，至少有一个满足条件，如果满足就缩小mid，如果不满足，就扩大mid

#include <bits/stdc++.h>
using namespace std;
#define int long longint t;
int n, m;
int l[100005], r[100005];
int q;
int x[100005];
int pre[100005];bool check(int mid) {memset(pre, 0, sizeof(pre));for (int i = 1; i <= mid; i++) {pre[x[i]] = 1;}for (int i = 1; i <= n; i++) {pre[i] += pre[i - 1];}for (int i = 1; i <= m; i++) {int qu = r[i] - l[i] + 1;int num = qu/2+1; // 修正计算方式if (pre[r[i]] - pre[l[i] - 1] >= num)return true;}return false;
}void solve() {cin >> n >> m;for (int i = 1; i <= m; i++) {cin >> l[i] >> r[i];}cin >> q;for (int i = 1; i <= q; i++) {cin >> x[i];}int L = 1, R = q;while (L < R) {int mid = (L + R) / 2;if (check(mid)) {R = mid;} else {L = mid + 1;}}if(check(L))cout << L << "\n";elsecout<<-1<<"\n";
}signed main() {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> t;while (t--)solve();return 0;
}

F1. Omsk Metro (simple version)

题意：就是说给你一棵树，每个节点的值为1或者-1，然后问你有没有一条路径上的值为k

思路：树上dp跑一遍，求最大值和最小值，处在这个区间那就是满足，输出yes，否则就是no

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
char flag;
int u,v,x;
void solve()
{cin>>n;vector<int>dmax(n+10),dmin(n+10),dx(n+10),dn(n+10);dmax[1]=1;dmin[1]=0;dx[1]=1;dn[1]=0;int cnt=2;//去统计该第几个点了 for(int i=1;i<=n;i++){cin>>flag;if(flag=='+'){cin>>v>>x;dmax[cnt]=max(x,dmax[v]+x);dx[cnt]=max(dx[v],dmax[cnt]);dmin[cnt]=min(x,dmin[v]+x);dn[cnt]=min(dn[v],dmin[cnt]);cnt++;}else{cin>>u>>v>>x;if(x>=dn[v]&&dx[v]>=x)cout<<"YES\n";elsecout<<"NO\n";}}
}signed main()
{cin>>t;while(t--)solve();return 0;
}

不要问我F2为什么不写，因为我不会树剖，我是贵物