作死小能手LTY又和TZG打cf啦！这次是半夜潜入学校。。。还有保安来查我们。。真是吓死了。。
经过这次比赛。。我rating终于涨了不少。。。然而还是每有TZG高，因为TZG太神了。
然而这次div2的难度比上次高了。。但是这些题都是有着水题本质的，在看透他们的伪装之后这些题就全是水题了。。
A题：送邮件小哥
题意：给你数轴上N个点，这些点以单调上升的顺序给出。对于每一个点，求离他们最远的点和最近的点。。
数据范围<=10^5
这题直接扫一遍，贪心的想，对于每一个点，最近的一定是他两边的点取min 最远的是和最左端和最右端的取max
然而有个小tirck 就是端点一定要特判（最后好不容易抓到一个人没特判想cha他结果没时间了。。）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int N=110005; long long a[N]; long long max(long long a,long long b) {return a>b?a:b;} long long min(long long a,long long b) {return a<b?a:b;} int n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%I64d",&a[i]); a[n+1]=(1LL<<31); printf("%I64d %I64d\n",abs(a[2]-a[1]),abs(a[1]-a[n])); for(int i=2;i<n;i++) printf("%I64d %I64d\n",min(abs(a[i+1]-a[i]),abs(a[i]-a[i-1])),max(abs(a[i]-a[1]),abs(a[n]-a[i]))); printf("%I64d %I64d\n",abs(a[n]-a[n-1]),abs(a[n]-a[1])); }
B题：疯狂图书管理员
题意：有一个图书馆，你现在开始在图书馆门口守着，可以看到现在出去的人和进去的人的编号，求根据你观察的结果，求这段时间内图书馆内人最多的时候的人的最小值。。
数据范围<=100
题意是不是很鬼畜。。举个例子
+ 1
+ 2
+ 3
– 100
– 200
这个数据答案应该是5 首先走进去了3个人，后来又出来了两个人。这样人最多的时候应该是100号出来之前的时候。根据观测，之前人数不可能少于5人（1号，2号，3号，100号和200号）所以输出5。
想了想 我们应该这样考虑：
每一个人，如果我们知道了他什么时候进去，也知道他什么时候出去，那么扫一遍就知道结果了。
对于数据进行预处理，每个人如果之前没有进去/出去与当前的进去/出去匹配的话，那么在开头/结尾加上这个人进去/出去
还是对于刚刚的样例，我们预处理后可以得到：
+ 100
+ 200
+ 1
+ 2
+ 3
– 100
– 200
– 1
– 2
– 3
这样扫一遍出解。。【水题本质啊！】
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map> using namespace std; const int N=1000; int a[N],b[N],c[N],p[N],cnt1,cnt2; char r[N][10]; map<int,int>vis; int now,n; void init() { for(int i=1;i<=n;i++) if(r[i][0]=='-') { bool flag=0; for(int j=i-1;j;j--) if(a[j]==a[i]){flag=1;break;} if(!flag){b[++cnt1]=a[i];} } else if(r[i][0]=='+') { bool flag=0; for(int j=i+1;j<=n;j++) if(a[j]==a[i]){flag=1;break;} if(!flag)p[++cnt2]=a[i]; } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%s%d",r[i],&a[i]); init(); for(int i=1;i<=cnt1;i++)c[i]=b[i]; for(int i=cnt1+1,j=1;i<=cnt1+n,j<=n;i++,j++)c[i]=a[j]; for(int i=cnt1+n+1,j=1;i<=cnt1+n+cnt2,j<=cnt2;i++,j++)c[i]=p[j]; int ans=0; for(int i=1;i<=cnt1+n+cnt2;i++) { if(!vis[c[i]]){vis[c[i]]=1;now++;} else if(vis[c[i]]){vis[c[i]]=0;now--;} ans=max(ans,now); } printf("%d\n",ans); }
C题：等比子序列
题意：给出数列an，求有多少个 ax ay az 满足ax*k=ay ay*k=az 即他们成公比为k的等比
数据范围<=10^5
这个想了好半天。。TZG提示了下。。这个都给出了公比了啊。。
那么对于等比中项ai 只需要看它自己是否%k==0 左边是否有ai/k 右边是否有ai*k即可
这个我们使用两个map搞定。。
水题本质
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map> using namespace std; const int N=300005; map<long long,long long>h1,h2; long long a[N]; long long n,k; long long ans; void init() { for(int i=1;i<=n;i++)h2[a[i]]++; } int main() { scanf("%I64d%I64d",&n,&k); for(int i=1;i<=n;i++)scanf("%I64d",&a[i]);init(); for(int i=1;i<=n;i++) { h2[a[i]]--; if(a[i]%k==0) { long long l=h1[a[i]/k]; long long r=h2[a[i]*k]; ans+=l*r; } h1[a[i]]++; } printf("%I64d\n",ans); }
D题：战舰世界
题意：俩脑残玩战舰世界，这个世界是一维的，每艘船有固定长度k，在一个固定长度n的场地里有x艘船，船与船之间不能接触，即两艘船之间必须空1个格子。
现在其中一个脑残开始打♂炮♀，另一个人通晓哲♂学♀。对于每一发炮弹，第二个人总是说你没打到，无论你打没打到。
给出第一个脑残打炮的位置，求打到至少第多少次的时候能断定第二个人在撒谎。。
数据范围n<=10^9 打炮次数<=10^5
考试时候正好做到这开始肚子疼。。还发现了hack功能，后面就开始浪了。。也没好好想。。
其实这个非常简单的==
对于每个区间[l,r]，在其中间打了一发炮，这个区间就被分为了两部分[l,x] [x,r]
每个区间能放多少船我们是可以算的 即现在能放的船数=第一部分能放的+第二部分能放的
现在对于每一发炮，找到离他最近的两个点，作为l,r 更新答案，当答案小于船数时，就代表那个人一定撒谎了。
找最近的两个点可以用平衡树维护（前驱，后继），TZG当时写的是树状数组+二分，orz
【水题本质啊！！！！！！！！想不到啊啊啊啊！！！】
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cstdlib> using namespace std; const int N=300005; int n,mn,k; struct treap {int l,r,v,size,rank,w;}tr[N]; int root,cnt,ans,t; void up(int p) {tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].w;} void rturn(int &p) { int t=tr[p].l;tr[p].l=tr[t].r;tr[t].r=p; tr[t].size=tr[p].size;up(p);p=t; } void lturn(int &p) { int t=tr[p].r;tr[p].r=tr[t].l;tr[t].l=p; tr[t].size=tr[p].size;up(p);p=t; } void insert(int &p,int x) { if(p==0) { p=++cnt; tr[p].size=tr[p].w=1; tr[p].v=x; tr[p].rank=rand(); return; } tr[p].size++; if(tr[p].v==x)tr[p].w++; else if(tr[p].v>x) { insert(tr[p].l,x); if(tr[tr[p].l].rank<tr[p].rank)rturn(p); } else { insert(tr[p].r,x); if(tr[tr[p].r].rank<tr[p].rank)lturn(p); } } void ask_pre(int &p,int x) { if(p==0)return; if(tr[p].v<x) ans=p,ask_pre(tr[p].r,x); else ask_pre(tr[p].l,x); } void ask_sub(int &p,int x) { if(p==0)return; if(tr[p].v>x) ans=p,ask_sub(tr[p].l,x); else ask_sub(tr[p].r,x); } int main() { scanf("%d%d%d",&n,&mn,&k); int all=(n+1)/(k+1); insert(root,0),insert(root,n+1); int q; scanf("%d",&q); for(int i=1;i<=q;i++) { int x;scanf("%d",&x); ask_pre(root,x); int l=tr[ans].v; ask_sub(root,x); int r=tr[ans].v; // cout<<l<<" "<<r<<endl; int past=(r-l)/(k+1); int now=(x-l)/(k+1)+(r-x)/(k+1); // cout<<past<<" "<<now<<endl; all-=past-now; if(all<mn){printf("%d\n",i);return 0;} insert(root,x); } puts("-1"); }