协会建设网站的必要性,南通住房和城乡建设局网站首页,专业公司网站 南通,企业策划书怎么做A. Shifting Stacks给出一个数组#xff0c;每次可以将一个位置-1#xff0c;右侧相邻位置1#xff0c;判断是否可以经过若干次操作后使得数列严格递增。思路#xff1a;对于每个位置#xff0c;前缀和必须都大于该位置应该有的最少数字#xff0c;即第一个位置最少是0每次可以将一个位置-1右侧相邻位置1判断是否可以经过若干次操作后使得数列严格递增。思路对于每个位置前缀和必须都大于该位置应该有的最少数字即第一个位置最少是0 第二个位置最少是1第三个位置最少是2取一下前缀和。AC Code#include bits/stdc.htypedef long long ll;
const int N 105;
int t, n;
ll a[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin t;while(t --) {std::cin n;ll num 0;bool flag true;for(int i 1; i n; i ) {std::cin a[i];a[i] a[i - 1];if(a[i] num)flag false;num i;}std::cout (flag ? YES : NO) \n;}return 0;
}B. Eastern Exhibition给出二维平面上若干个坐标在二维平面上选择一个位置使得这个位置到所有点的距离之和最小求满足条件的点有多少个。思路考虑先放到一维里考虑这样很容易想到是放到中间位置即中间两个点之间的距离都可以如果放到二维其实也是一样的就是两个维度的中间两点距离差的乘积。AC Code#include bits/stdc.h
using namespace std;long long solve(vectorint x) {sort(x.begin(), x.end());return x[x.size() / 2] - x[(x.size() - 1) / 2] 1;
}void solve() {int n;cin n;vectorint x(n), y(n);for (int i 0; i n; i)cin x[i] y[i];cout solve(x) * solve(y) \n;
}int main() {int t;cin t;while (t--) solve();return 0;
}os贴的标解hhhC. Guessing the Greatest 交互题每次可以询问任意区间内第二大的数的位置在不超过20次询问后得到最大值的位置。思路20次可以想到二进制枚举因为数据范围在1e5内完全可以完成枚举。考虑倍增如果一开始的次大值位置为p若是1~p内存在最大值则可以用倍增不断增大l缩减当前范围到最后最大值一定是l的位置反之则用倍增不断缩小r的范围最后最大值的位置就是r。AC Code;#include bits/stdc.htypedef long long ll;
#define int long long
const int N 1e3 5;
int n;
int pow2[25];int ask(int l, int r) {if(l r) return -1;std::cout ? l r \n;std::cout.flush();int pos;std::cin pos;return pos;
}void init() {pow2[0] 1; for(int i 1; i 20; i ) {pow2[i] pow2[i - 1] * 2;}
}signed main() {init();std::cin n;int l 1, r n;int p ask(l, r);if(ask(1, p) p) {for(int i 18; i 0; i --) {if(pow2[i] l p ask(l pow2[i], p) p)l pow2[i];}std::cout ! l \n;}else {for(int i 18; i 0; i --) {if(r - pow2[i] p ask(p, r - pow2[i]) p)r - pow2[i];}std::cout ! r \n;}std::cout.flush();return 0;
}D. Max Median给出一个数组要求找到长度至少为k中间数最大的序列输出最大的中间数的值。思路可以考虑二分答案。在值域上二分对于每个mid判断序列中是否存在长度为至少为k的子序列中位数为mid。可以这样处理check函数遍历数组大于等于mid的为1小于mid的为-1处理前缀和和前缀最小值。处理前缀最小值的原因是这样可以不局限于长度为k的子序列长度大于等于k的子序列只要有满足条件的都会被找到。AC Code#include bits/stdc.htypedef long long ll;
const int N 2e5 5;
int n, k;
int a[N], pre[N];bool check(int mid) {int sum 0;for(int i 1; i n; i ) {if(a[i] mid)sum ;elsesum --;pre[i] std::min(pre[i - 1], sum);if(i k sum - pre[i - k] 0)return true;}return false;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin n k;for(int i 1; i n; i ) {std::cin a[i];}int l 1, r n;while(l r) {int mid l r 1 1;if(check(mid)) l mid;else r mid - 1;}std::cout l \n;return 0;
}
