Codeforces Round #618 (Div. 2)
小号AKdiv2成功上紫╰(*´︶`*)╯(第一次AKCF纪念一下)
A. Non-zero
题目链接：https://codeforces.com/contest/1300/problem/A
题意：
给你一个数组，每次操作你可以使其中任意元素的值+1，问最少操作几次使得元素和、元素积都不为0
分析：
因为积不为0,所以凡是值为0的元素我们都要将它+1,加完后若总和不为0,则操作结束,否则对任意元素+1即可
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int a[N] , t , n; int main() { cin >> t; while(t --) { cin >> n; int sum = 0 , z = 0; for(int i = 1 ; i <= n ; i ++) { cin >> a[i] , sum += a[i]; if(!a[i]) z ++; } sum += z; if(sum == 0) cout << z + 1 << '\n'; else cout << z << '\n'; } return 0; }
B. Assigning to Classes
题目链接：https://codeforces.com/contest/1300/problem/B
题意：
有2n个学生，每个学生都有自己的价值a[i]
现你要将他们分配到两个班，使两个班学生价值的中位数相差尽可能小
分析：
先按照价值对学生排个序
因为每个人都必须被分配，所以很显然我们能控制差值离得最近的就是中间那两人
所以答案就是 a[n + 1] – a[n]
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int a[N] , t , n; int main() { cin >> t; while(t --) { cin >> n; for(int i = 1 ; i <= 2 * n ; i ++) cin >> a[i]; sort(a + 1 , a + 1 + 2 * n); cout << a[n + 1] - a[n] << '\n'; } return 0; }
C. Anu Has a Function
题目链接：https://codeforces.com/contest/1300/problem/C
题意：
定义 f(x , y) = x | y – y，给你一个数组，你可以对它任意排序
问如何排序才能使 f ( f ( f ( f ( a[1] , a[2] ) , a[3] ) , a[4] ) , a[5])…的值最大
分析：
很显然 a[1] | a[2] | … | a[n] 的值是固定的，而除了 a[1] 的每个元素都会出现在 f(x,y)中的y的位置上
所以只有第一个数会影响结果，那第一个数怎么找呢？先随便举个例子：4 ，6（设得到的值为res）
4 的二进制为 100
6 的二进制为 110
如果选择4为a[1],6为a[2]，那么f(4 , 6) = 100|110 – 110 = 000
如果选择6位a[1],4为a[2]，那么f(6 , 4) = 110|100 – 100 = 010
我们会发现N个数中如果二进制位的某一位1的个数大于等于2，那么不论怎么排序res的这一位肯定为0
如果某一位1的个数等于1，那么把它排在第一位，就可以保证res的这一位为1
所以要让res最大，我们就要从高位往低位找——第一个所有数的这个位置为1的个数为1
em…说起来比较绕，可以在纸上画出来看看。
#include<bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 10; int a[N] , sum[100] , n; signed main() { cin >> n; for(int i = 1 ; i <= n ; i ++) cin >> a[i]; for(int i = 1 ; i <= n ; i ++) for(int j = 0 ; j <= 31 ; j ++) if(a[i] >> j & 1 == 1) sum[j] ++; int now = 35; while(~ now) { if(sum[now] == 1) break; now --; } for(int i = 1 ; i <= n ; i ++) if((a[i] >> now) & 1) {now = i ; break ;} if(now != -1) cout << a[now] << " "; for(int i = 1 ; i <= n ; i ++) if(i != now) cout << a[i] << " "; cout << '\n'; return 0; }
D. Aerodynamic
题目链接：https://codeforces.com/contest/1300/problem/D
题意：
给你一个多边形，你可以对它进行瞎操作
问你瞎操作后的多边形和原来的多边形是否相似
分析：
结论很好猜，只要多边形满足中心对称就为相似（应该多数人都能猜到这个结论吧？）
所以接下来只要判断多边形是否为中心对称就可以了
#include<bits/stdc++.h> using namespace std; #define fi first #define se second const int N = 2e5 + 10; pair<int , int>a[N] , ans , now; int main() { int n ; cin >> n; for(int i = 1 ; i <= n ; i ++) cin >> a[i].fi >> a[i].se , a[i].fi <<= 1 , a[i].se <<= 1; if(n & 1) return cout << "NO" << '\n' , 0; ans = make_pair((a[1].fi + a[1 + n / 2].fi) >> 1 , (a[1].se + a[1 + n / 2].se) >> 1); for(int i = 1 ; i <= n / 2 ; i ++) { now = make_pair(a[i].fi + a[i + n / 2].fi >> 1 , a[i].se + a[i + n / 2].se >> 1); if(now != ans) return cout << "NO" << '\n' , 0; } cout << "YES" << '\n'; return 0; }
E. Water Balance
题目链接：https://codeforces.com/contest/1300/problem/E
题意：
给你一个序列，你可以选择任意区间使这个区间内每个数的值变为区间内元素的平均值
要求你输出可以形成的字典序最小的序列
分析：
我们先把第 i 个数归类到第 [i , i] 个区间，并令第i个区间的平均值为a[i]，然后从第二个区间开始比较当前区间和前一个区间的平均值
若当前区间的平均值小于上一个区间的平均值，则我们对上一个区间更新平均值，然后用上一个区间再对上上个区间更新。。。
若当前区间的平均值大于等于上一个区间的平均值，则停止更新
因为最坏情况每个区间都要从后往前更新所有区间，而答案又满足单调性，所以我们可以用单调栈维护区间左端点右端点优化一下复杂度
#include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int n , top; struct node{ double ave; int l , r; }stk[N]; double ans[N] , a[N]; int main() { scanf("%d" , &n); for(int i = 1 ; i <= n ; i ++) scanf("%lf" , &a[i]); stk[++ top] = {a[1] , 1 , 1}; for(int i = 2 ; i <= n ; i ++) { stk[++ top] = {a[i] ,i , i}; while(top > 1 && stk[top].ave < stk[top - 1].ave) { int l = stk[top].l , r = stk[top].r , pl = stk[top - 1].l , pr = stk[top - 1].r; stk[top - 1].ave = (stk[top].ave * (r - l + 1) + stk[top - 1].ave * (pr - pl + 1)) / (r - pl + 1); stk[top - 1].r = r; top -- ; } } for(int i = 1 ; i <= top ; i ++) for(int j = stk[i].l ; j <= stk[i].r ; j ++) ans[j] = stk[i].ave; for(int i = 1 ; i <= n ; i ++) printf("%.12lf\n" , ans[i]); cout << '\n'; return 0; }