Codeforces Round 835 (Div. 4)题解ABCDEFG

Problem - A - Codeforces

题意：你有 t 组数据，每组有两两不同的三个数 a,b,c，现在需要你求出他们的中位数。

思路：模拟即可

// Code Start Here	int t;cin >> t;while(t--){vector<int> a(3);for(int i = 0;i<3;i++)cin >> a[i];sort(a.begin(),a.end());cout << a[1] <<endl;}

Problem - B - Codeforces

题意：

现在对于任意一个单词，定义：它需要一个最小的大小为 x 的字母表，当且仅当这个单词只用到了英文字母中的前 x 个字符。

你现在需要对于 t 组长度为 n 的字符串 s，求出每一个单词的最小字母表。

思路：找最大的char，模拟即可

// Code Start Here	int t;cin >> t;while(t--){int l;string s;cin >> l >> s;int ans = -0x3f;for(auto ch : s){ans = max(ans,int(ch - 'a'));}cout << ans + 1 <<endl;}

Problem - C - Codeforces

题意：

若干个参赛者正在比拼。

每个人想要知道除自己以外的最厉害的人力量比自己弱多少，现在他们依次在向你询问。

思路：一个蛮坑的模拟题，注意到只需要讨论最大值和次大值即可，然后分类讨论最大值的数量

// Code Start Here	int t;cin >> t;while(t--){i64 n;cin >> n;vector<i64> a(n);map<i64,i64> mp;for(i64 i = 0;i<n;i++){cin >> a[i];mp[a[i]]++;}i64 max_val = *max_element(a.begin(),a.end());i64 second_max_val = -0x3f;for(i64 i = 0;i<n;i++){if(a[i]!=max_val){second_max_val = max(second_max_val , a[i]);}}if(i64(mp.size()) == 1){for(i64 i = 0;i<n;i++)cout <<"0 ";}else{if(i64(mp[max_val]) == 1){for(i64 i = 0;i<n;i++){if(a[i] == max_val){cout << max_val - second_max_val <<" ";}else cout << a[i] - max_val << " ";}}else{for(i64 i = 0;i<n;i++){cout << a[i] - max_val << " ";}}}cout << endl;}

Problem - D - Codeforces

题意：

一个含 n 个整数元素的序列 a[0…n−1]，如果有且只有一个连续子序列 a[l…r] 同时满足以下条件，那么我们称原序列是 valley 的。

• 0≤l≤r≤n−1 ,
• al​=al+1​=al+2​=⋯=ar​ ,
• l=0 或者 al−1​>al​ ,
• r=n−1 或者 ar​<ar+1​ 。

对于每次询问，判断给定的序列是否是一个 valley。

思路：注意到valley只有三种情况  左右升  左右降  左降右升。可以模拟跑一下各种情况，或者判断是不是只有一个解即可

// Code Start Here	int tt;cin >> tt;while (tt--) {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}int cnt = 0;int beg = 0;while (beg < n) {int end = beg;while (end + 1 < n && a[end + 1] == a[end]) {end += 1;}if (beg == 0 || a[beg - 1] > a[beg]) {if (end == n - 1 || a[end + 1] > a[end]) {cnt += 1;}}beg = end + 1;}cout << (cnt == 1 ? "YES" : "NO") << '\n';}

Problem - E - Codeforces

题意：给定长度为 n 的 01 串，问至多将一个数字取反后逆序对的数量最大是多少。

思路：注意到数据范围是2e5思考如何优化计算方式，考虑到逆序对的定义是 i < j and ai > aj，而且每次只修改一个字符，思考到可以计算一下在当前位置的逆序对数量，对0 / 1分情况讨论，对另一半取反然后取最大值即可，逆序对数量可以用类似前缀和的方式快速计算

// Code Start Here	int t;cin >> t;while(t--){int n;cin >> n;vector<int> a(n+1),s(n+1,0);for(int i = 1;i<=n;i++){cin >> a[i];s[i] = s[i-1] + a[i];}int cnt = 0;int ans = 0;for(int i = 1;i<=n;i++){if(a[i] == 1){//后面多少个0ans += (n-i) -(s[n] - s[i]);}else{//前面多少个1ans += s[i-1];}}ans /= 2;cnt = ans;for(int i = 1;i<=n;i++){if(a[i] == 1){int now = s[i-1];ans = max(ans,(cnt - ((n-i) -(s[n] - s[i])) + now));}else{int now = (n-i) -(s[n] - s[i]);ans = max(ans,(cnt - s[i-1] + now));}}cout << ans <<endl;}

Problem - F - Codeforces

题意：

有 n 个任务，你每一天都可以选择其中的一个任务完成或不选。当你完成了第 i 个任务，你将获得 ai​ 元。但是如果你今天完成了一个任务，那么你之后 k 天内都不能再完成这个任务。

给出两个数 c，d，要求求出满足在 d 天内可以收集至少 c 元的最大的 k。

思路：首先注意到不存在和无限的情况

1.当全部的和大于c，即d天内只跑一轮就能完成，无限

2.每天都跑最大的还是不能达到c，不存在

其他情况一定有答案，可以二分天数，或者贪心看跑一遍什么时候刚好大于即可，这里跑了一遍贪心

// Code Start Here	int t;cin >> t;while(t--){//n个数  c元  d天memset(s , 0 , sizeof s);int n , c , d;cin >> n >> c >> d;for(int i = 1;i<=n;i++){cin >> a[i];}sort(a + 1 , a + 1 + n , [&](const int & a,const int & b){return a > b;});for(int i = 1;i<=n;i++){s[i] = s[i-1] + a[i];}if(s[min(n , d)] >= c){cout <<"Infinity" << '\n';continue;}if(s[1] * d < c){cout <<"Impossible" << '\n';continue;}int ans = -1;for(int i =  d- 1;i>=0;i--){int Round = d / (i + 1);int Res = d % (i + 1);if(s[min(n , Res)] + Round * s[min(n , i + 1)] >= c){ans = i;break;}}cout << max(ans , 0LL) << endl;}

Problem - G - Codeforces

題意：给你一棵树和两个点 a,b，边有边权。你可以在任意时刻从当前所在的点跳到任意除了 b 以外的点。求有没有方案使得从 a 出发，到达 b 时边权 xor 和为 0。

思路：根据xor的性质，当两个数相等时，xor值为0，因此题目可以变形为：有没有一种方案，使得从a出发和从b出发到达一个非b , a的点时两个路径的xor权值相等。

马上想到对其中一条边跑一遍dfs，然后记录下来所有简单路径的xor值，然后再跑一遍另外一个点查询即可。

// Code Start Here	int t;cin >> t;while(t--){int n , a , b;cin >> n >> a >> b;vector<vector<pair<int,int>>> g(n + 1);for(int i = 1;i<=n-1;i++){int u , v , w;cin >> u >> v >> w;g[u].push_back({v , w});g[v].push_back({u , w});}set<int> st;bool flag = false;st.insert(0);auto dfs1 = [&](auto dfs1 , int x ,int father , int val)->void{for(pair<int,int> &now : g[x]){if(now.first == father || now.first == b)continue;st.insert(val^now.second);dfs1(dfs1 , now.first , x ,val^now.second);}};auto dfs2 = [&](auto dfs2 , int x ,int father , int val)->void{for(pair<int,int> &now : g[x]){if(now.first == father)continue;if(st.count(val ^ now.second)) flag = true;dfs2(dfs2,now.first , x , val ^ now.second);}};dfs1(dfs1 , a , 0 , 0);dfs2(dfs2 , b , 0 , 0);if(flag)cout <<"Yes" << '\n';else cout <<"No" << '\n';}