A. Shifting Stacks 题目链接
点我跳转
题目大意给定 \(N\) 个土堆，第 \(i\) 个土堆有 \(Ai\) 个木块
你可以将第 \(i\) 个土堆的木块转移至第 \(i + 1\) 个土堆
问能否使土堆的木块数量构成上升序列
解题思路最优的构造方法即令土堆的木块数一次为 $0 , 1 , 2 , 3 ... $
定义 \(sum[i]\) 为 \(ai\) 的前缀和，那么只要判断是否每个前缀和都满足 \(sum[i] >= (i - 1) × i / 2\)
AC_Code #include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e2 + 10; int n , a[N] , sum[N]; signed main() { int T = 1; cin >> T; while(T --) { cin >> n; for(int i = 1 ; i <= n ; i ++) cin >> a[i] , sum[i] = sum[i - 1] + a[i]; bool ok = true; for(int i = 1 ; i <= n ; i ++) { if(sum[i] - (i - 1) * i / 2 < 0) { ok = false ; break ; } } if(ok) cout << "YES\n"; else cout << "NO\n"; } return 0; }#include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e2 + 10; int n , a[N] , sum[N]; signed main() { int T = 1; cin >> T; while(T --) { cin >> n; for(int i = 1 ; i <= n ; i ++) cin >> a[i] , sum[i] = sum[i - 1] + a[i]; bool ok = true; for(int i = 1 ; i <= n ; i ++) { if(sum[i] - (i - 1) * i / 2 < 0) { ok = false ; break ; } } if(ok) cout << "YES\n"; else cout << "NO\n"; } return 0; } B. Eastern Exhibition 题目链接点我跳转
题目大意二维平面上给定 \(n\) 个点，问存在多少个整数坐标点使得这些点到 \(n\) 个点的曼哈顿距离总和最小
解题思路如果是一维直线，那么这些点只会存在于横坐标 \(x\) 的中位数之间，或者纵坐标 \(y\) 的中位数之间
那么满足条件的点个数即为 横坐标 \(x\) 的中位数之间的长度 或 纵坐标 \(y\) 的中位数之间的长度
拓展到二维这些点的个数即为横坐标 \(x\) 的中位数之间的长度 \(×\) 纵坐标 \(y\) 的中位数之间的长度
当 \(n\) 为奇数时，\(x\) 的中位数只有 \(1\) 个，\(y\) 的中位数只有 \(1\) 个，所以答案为 \(1\)
当 \(n\) 为偶数时，答案即是 \(x\) 的中位数之间的长度 \(×\) \(y\) 的中位数之间的长度
AC_Code #include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e3 + 10; int n , x[N] , y[N]; signed main() { int T = 1; cin >> T; while(T --) { cin >> n; for(int i = 1 ; i <= n ; i ++) cin >> x[i] >> y[i]; sort(x + 1 , x + 1 + n) , sort(y + 1 , y + 1 + n); if(n & 1) cout << 1 << '\n'; else cout << (x[n / 2 + 1] - x[n / 2] + 1) * (y[n / 2 + 1] - y[n / 2] + 1) << '\n'; } return 0; } C1&C2.Guessing the Greatest 题目链接点我跳转
题目大意交互问题
有一个序列，每次你可以询问区间 \([L , R]\) 的次大值的位置
要求在 \(20\) 次询问内找出最大值的位置
解题思路对于区间 \([L , R]\) 的次大值位置为 \(pos\)
那么最大值必然只出现在区间 \([L , pos - 1]\) 或区间 \([pos + 1 , R]\)
于是可以再次询问区间 \([L , pos]\) 的次大值位置判断最大值是位于区间 \([L , pos-1]\) 还是区间 \([pos +1 , R]\)
当 \(query([L , pos]) = pos\) , 且 \(pos != 1\) 时，最大值处于区间 \([L , pos - 1]\)
此时可以令 \(R = pos - 1\) , 并二分最大值的位置 \(mid\)
如果 \(query([mid , pos]) = pos\) ，则可以确定最大值位于区间 \([mid , pos]\) , 于是舍弃 \([l , mid - 1]\)
否则可以确定最大值不位于区间 \([mid , pos]\) , 于是二分的区间改为 \([l , mid - 1]\)
否则最大值位于区间 \([pos +1 , R]\) , 操作大致同上
AC_Code #include<bits/stdc++.h> using namespace std; int n , x; int query(int l , int r) { cout << "? " << l << " " << r << '\n'; cin >> x; return x; } signed main() { cin >> n; int l = 1 , r = n , res = 0; int pos = query(1 , n); if(pos != 1 && query(1 , pos) == pos) { l = 1 , r = pos - 1; while(l <= r) { int mid = l + r >> 1; if(query(mid , pos) == pos) res = mid , l = mid + 1; else r = mid - 1; } } else { l = pos + 1 , r = n; while(l <= r) { int mid = l + r >> 1; if(query(pos , mid) == pos) res = mid , r = mid - 1; else l = mid + 1; } } cout << "! " << res << '\n'; return 0; } D. Max Median 题目链接点我跳转
题目大意给定一个序列，要求选出一个长度大于等于 \(k\) 的连续子序列
使得该序列的中位数最大
问最大中位数是多少？
解题思路二分中位数 \(x\)
将序列中大于等于它的数变为 \(1\) ，小于它的数变为 \(0\)
假设选出的序列长度 \(len\) ， 序列中 1 的个数为 \(cnt\)
那么当 \(cnt - 1 >= len / 2\) 时，返回 \(true\)
这里解释下两个问题 ：
为什么式子左边是 \(cnt - 1\) 而不是 \(cnt\)?
为什么不是 \(cnt - 1 = len / 2\) 而是 \(cnt - 1 >= len / 2\)
q1. \(cnt - 1\) 是因为序列中的某个 \(1\) 得作为 x 本身