GCJ2019 Round1B 题解
A.Manhattan Crepe Cart
维护两个轴的到达数,其实就是区间加,做一个差分前缀和就可以了,复杂度
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100050;
int x[maxn],y[maxn];
int dx[maxn],dy[maxn];
void init(int q){
for(int i=0;i<=q;i++){
x[i]=y[i]=0;
dx[i]=dy[i]=0;
}
}
void addx(int l,int r){dx[l]++;dx[r]--;}
void addy(int l,int r){dy[l]++;dy[r]--;}
char str[3];
int main(){
int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
int p,q;
scanf("%d%d",&p,&q);
init(q);
for(int i=1;i<=p;i++){
int px,py;
scanf("%d%d%s",&px,&py,str);
if(str[0]=='W')addx(0,px);
if(str[0]=='E')addx(px+1,q+1);
if(str[0]=='S')addy(0,py);
if(str[0]=='N')addy(py+1,q+1);
}
x[0]=dx[0];
y[0]=dy[0];
for(int i=1;i<=q;i++){
x[i]=x[i-1]+dx[i];
y[i]=y[i-1]+dy[i];
}
int mxx=0,mxy=0;
int posx=0,posy=0;
for(int i=0;i<=q;i++){
if(x[i]>mxx){
mxx=x[i];
posx=i;
}
if(y[i]>mxy){
mxy=y[i];
posy=i;
}
}
printf("Case #%d: %d %d\n",cas,posx,posy);
}
return 0;
}
B.Draupnir
C写的太慢,没看,待补
C.Fair Fight
这里假设两个人叫小和小,假设小选中了兵器,i左边第一个熟练度比高的编号设为,同理右边第一个设为,那么我们给出的区间一定在内部,但是这样会有重复的情况,因此稍微改变一下的定义,改为满足,这样就完成了去重,线性找这个东西可以用单调栈搞一下,这里不赘述。
接下来问题就转化成了,找到序列中距离左边和右边的最近的一个大于等于下限的区间,以及最远的一个小于等于上限的区间,因为从点向左或向右扩展,区间最大值是单调的,因此这个地方可以用二分+rmq的手段解决,我偷懒直接写了线段树维护区间最大值,所以我的写法是两个log,假设求出来为
那么答案分类讨论一下就出来了,具体看代码,可以先判掉的情况以简化问题
分类讨论可以看这个图yy一下
#include<bits/stdc++.h>
#define ok (l==r)
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r)>>1
#define lson ls,l,m
#define rson rs,m+1,r
using namespace std;
typedef long long LL;
const int maxn=100010;
int c[maxn];
int l[maxn];
int r[maxn];
int d[maxn];
stack<int>mst;
int mxd[maxn<<2];
inline void pushup(int rt){
mxd[rt]=max(mxd[ls],mxd[rs]);
}
void build(int rt,int l,int r){
if(ok){
mxd[rt]=d[l];
return;
}
int m=mid;
build(lson);
build(rson);
pushup(rt);
}
int query(int rt,int l,int r,int L,int R){
if(l>=L&&r<=R)return mxd[rt];
int m=mid;
int ans=-1;
if(L<=m)ans=max(ans,query(lson,L,R));
if(R>m)ans=max(ans,query(rson,L,R));
return ans;
}
int main(){
int t,n,k;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
scanf("%d%d",&n,&k);
c[0]=c[n+1]=1e6;
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
for(int i=1;i<=n;i++)scanf("%d",&d[i]);
while(!mst.empty()){mst.pop();}mst.push(0);
for(int i=1;i<=n;i++){
while((!mst.empty())&&(c[mst.top()]<c[i]))mst.pop();
l[i]=mst.top()+1;
mst.push(i);
}
while(!mst.empty()){mst.pop();}mst.push(n+1);
for(int i=n;i>=1;i--){
while((!mst.empty())&&(c[mst.top()]<=c[i]))mst.pop();
r[i]=mst.top()-1;
mst.push(i);
}
build(1,1,n);
LL tot=0;
for(int i=1;i<=n;i++){
if(c[i]+k<d[i])continue;
int dl,dr,ans;
int cnt=0;
LL anslL,anslR,ansrL,ansrR;
dl=l[i];dr=i;
ans=i+1;
while(dl<=dr){
int m=(dl+dr)>>1;
int mx=query(1,1,n,m,i);
if(mx<=c[i]+k){
ans=m;
dr=m-1;
}
else if(mx>c[i]+k){
dl=m+1;
}
else {
dr=m-1;
}
}
anslL=ans;
//puts("1");
dl=l[i];dr=i;
ans=anslL-1;
while(dl<=dr){
int m=(dl+dr)>>1;
int mx=query(1,1,n,m,i);
if(mx>=c[i]-k){
ans=m;
dl=m+1;
}
else if(mx>c[i]+k){
dl=m+1;
}
else {
dr=m-1;
}
}
anslR=ans;
//puts("2");
dl=i;dr=r[i];
ans=i-1;
while(dl<=dr){
int m=(dl+dr)>>1;
int mx=query(1,1,n,i,m);
if(mx<=c[i]+k){
ans=m;
dl=m+1;
}
else if(mx>c[i]+k){
dr=m-1;
}
else {
dl=m+1;
}
}
ansrR=ans;
//puts("3");
dl=i;dr=r[i];
ans=ansrR+1;
while(dl<=dr){
int m=(dl+dr)>>1;
int mx=query(1,1,n,i,m);
if(mx>=c[i]-k){
ans=m;
dr=m-1;
}
else if(mx>c[i]+k){
dr=m-1;
}
else {
dl=m+1;
}
}
ansrL=ans;
//puts("4");
LL L=i-anslL+1;
LL R=ansrR-i+1;
LL PL=(anslR-anslL+1);
LL PR=(ansrR-ansrL+1);
// printf("%d %d %d %lld %lld %lld %lld %lld %lld\n",i,l[i],r[i],L,R,anslL,anslR,ansrL,ansrR);
if(PL>0||PR>0){
if(PL>0){
if(PR>0)tot+=(PL*R+PR*L-PL*PR);
else tot+=PL*R;
}
else if(PR>0)tot+=PR*L;
}
}
printf("Case #%d: %lld\n",cas,tot);
}
return 0;
}