A. Shifting Stacks (*900)
题意
有(n(1leq nleq 100))堆块，每堆有一个高度(h_i(0leq h_ileq 1e9))，可以从第(i)堆移动一个块到第((i+1))堆，能否实现整个序列严格单调递增？
题解
严格单调递增时，前(i)堆总和最小时，高度依次为(0,1,2,3,cdots)，总和最小值(frac{i(i-1)}{2})。所以只需要检查每个位置的前缀和是否大于等于(frac{i(i-1)}{2})
#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) x&(-x)
#define eps 1e-6
using namespace std;
const int maxn=110;
int T,n;
LL a[maxn];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
LL need=0,sum=0;
bool f=true;
for(int i=1;i<=n;i++){
need+=i-1;
sum+=a[i];
if(sum<need){
f=false;
break;
}
}
printf("%s
",f?"YES":"NO");
}
}
B. Eastern Exhibition (*1500)
题意
二维平面上有(n(1leq nleq 1000))座房屋，每座房屋有横纵坐标(x_i,y_i(0leq x_i,y_ileq 1e9))，计算平面上到所有房屋的曼哈顿距离最小的点的个数
题解
首先，问题不是二维的，因为两个一维互不影响，所以可以转化为对一维求解，再将答案相乘
对于一维情况，也就是一条直线上的点，有已知结论：总数为奇数时，中间的点符合条件，总数为偶数时，中间的两个点以及它们中间的点符合条件
#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) x&(-x)
#define eps 1e-6
using namespace std;
const int maxn=1010;
int T,n;
LL x[maxn],y[maxn];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld %lld",&x[i],&y[i]);
sort(x+1,x+1+n);
sort(y+1,y+1+n);
LL ans1=1,ans2=1;
if(n%2==0){
ans1=(x[n/2+1]-x[n/2])+1;
ans2=(y[n/2+1]-y[n/2])+1;
}
printf("%lld
",ans1*ans2);
}
}
C1. Guessing the Greatest (easy version) (*1600)
题意
交互题
有一个长度为(n(1leq n leq 1e5))的数组，每次可以选择一个区间([l,r](1leq l,r leq n))，询问区间内次大值的位置。在不超过(40)次询问中找到数组中最大值的下标
题解
二分
由于(2^{17}approx 1e5)，所以使用二分时，需要在(2)次询问中确定最大值位于左半边还是右半边。首先询问([l,r])内的次大值的位置，设为(smax)，之后二分区间([l,r])，设(mid=frac{(l+r)}{2})，在两个区间([l,mid])和([mid+1,r])中，如果(smax)所在区间长度大于(1)，再询问(smax)所在区间的次大值的位置，如果依然是(smax)，则说明最大值在这个区间中，否则说明最大值在另一个区间中
#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
int n;
int main(){
scanf("%d",&n);
int l=1,r=n;
while(r>l){
printf("? %d %d
",l,r);
fflush(stdout);
int smax;
scanf("%d",&smax);
int mid=(l+r)>>1;
if(smax<=mid){
if(l==mid){
l=mid+1;
continue;
}
printf("? %d %d
",l,mid);
fflush(stdout);
int t;
scanf("%d",&t);
if(t==smax){
r=mid;
}
else l=mid+1;
}
else{
if(mid+1==r){
r=mid;
continue;
}
printf("? %d %d
",mid+1,r);
fflush(stdout);
int t;
scanf("%d",&t);
if(t==smax){
l=mid+1;
}
else r=mid;
}
}
printf("! %d
",r);
}
C2. Guessing the Greatest (hard version) (*1900)
题意
(c1)提高版，在不超过(20)次询问中找到数组中最大值的下标
题解
首先通过两次询问找到最大值位于次大值左边还是右边，具体方法是首先找到次大值的位置(smax)，之后询问([1,smax])，如果结果仍为(smax)，说明最大值位于([1,smax])，否则说明最大值位于([smax+1,r])。之后每次经过一次询问二分区间，询问的是以(smax)为一个端点，二分另一个端点得到的区间，总询问次数为(2+lceil log_21e5 ceil=19)
#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
int n;
int main(){
scanf("%d",&n);
printf("? %d %d
",1,n);
fflush(stdout);
int smax,t;
scanf("%d",&smax);
if(smax>1){
printf("? %d %d
",1,smax);
fflush(stdout);
scanf("%d",&t);
}
int l,r;
if(smax>1 && t==smax){
l=1;
r=smax-1;
while(r>l){
int mid=(l+r+1)>>1;
printf("? %d %d
",mid,smax);
fflush(stdout);
int tt;
scanf("%d",&tt);
if(tt==smax) l=mid;
else r=mid-1;
}
}
else{
l=smax+1;
r=n;
while(r>l){
int mid=(l+r)>>1;
printf("? %d %d
",smax,mid);
fflush(stdout);
int tt;
scanf("%d",&tt);
if(tt==smax) r=mid;
else l=mid+1;
}
}
printf("! %d
",r);
}
D. Max Median (*2100)
题意
有一个长度为(n(1leq nleq 2e5))的数组(a)，(1leq a_ileq n)，中位数定义为将一个序列按照递增排序之后下标为(lfloor frac{(n+1)}{2} floor)的数。给定(k(1leq kleq n))，计算数组(a)中长度至少为(k)并且中位数最大的连续子段的中位数的值
题解
二分答案，设二分出的值是(x)，判断数组中是否存在满足条件，并且中位数大于等于(x)的子段
将数组(a)处理成只包含(-1,1)的数组，方法为如果(a_igeq x)，则赋为(1)，否则赋为(-1)。这样如果某个子段的中位数至少是(x)，等价于子段和为正数
问题转化为寻找长度至少为(k)，并且子段和最大的子段，判断子段和是否为正数
计算前缀和，扫一遍数组，计算以位置(i)结尾的满足条件的子段的最大子段和，具体方法是用(i)的前缀和减去(0,1,cdots,i-k)中最小的前缀和
时间复杂度(O(nlog n))
#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) x&(-x)
#define eps 1e-6
using namespace std;
const int maxn=200010;
int n,k,a[maxn],b[maxn];
bool check(int x){
for(int i=1;i<=n;i++){
if(a[i]>=x) b[i]=1;
else b[i]=-1;
}
for(int i=1;i<=n;i++) b[i]+=b[i-1];
int ans=b[k];
int mini=0;
for(int i=k+1;i<=n;i++){
mini=min(mini,b[i-k]);
ans=max(ans,b[i]-mini);
}
return ans>0;
}
int main(){
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int l=1,r=n;
while(r>l){
int mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d
",r);
}