0+45+50
惊险刺激
8：30的时候我估计能拿250分
10：30的时候我估计我会爆零
一开始以为会做T1T3
结果打出来都不对
赛后发现反而是T2最简单
其实T1暴力能过
chnlich 非常喜欢玩三国志这款游戏,并喜欢用一些策略出奇制胜。现在,他要开始征服世界的旅途了。他的敌人有N 座城市和N 个太守, N个城市可以看作在二维平面上的N 个点。N 座城市的标号为0,1,2,......,N-1。第i 座城市的坐标为(Xi,Yi),镇守这座城市的太守的能力值为Zi。
chnlich 每次会选择一个边平行于坐标轴的矩形区域,并奇袭其中太守能力值第K小的城市(奇袭结束之后城市与太守依然存在)。
不过,他的敌人经常会偷偷交换两座城市的太守,防止弱点被chnlich 发现。
现在,chnlich 想要知道,每次奇袭时他的敌人的能力值。
对于100%的数据,N<=60000,M<=10000,0<=Xi,Yi,Zi<=10^9,k<=10^9,保证所有操作均合法。
Time Limits: 10000 ms
欺诈题
NM可以过
先按Z排序，每次询问找到第k个在矩形内的城市就是答案了
有 N 个关卡,初始有 Q 条命。每通过一个关卡,会得到 u 分和1条命,生命上限为 Q。其中 u=min(最近一次连续通过的关数,R)。
若没有通过这个关卡,将会失去1条命,并进入下一个关卡。当没有生命或没有未挑战过的关卡时,游戏结束,得到的分数为每关得到的分数的总和。
由于 chnlich 好久不玩这个游戏了,每条命通过每个关卡的概率均为p(0<=p<=1),原先 chnlich 的最高分纪录是 S。现在 chnlich 想要知道,当 p 至少为多少时,chnlich 期望获得的总分数能够超过原先的最高分。
对于100%的数据,N<=10^8,1<=R<=20,1<=Q<=5,保证 S 是一个可能出现的分数。
一眼二分加矩乘
方程是\[ f[i+1][min(j+1,Q)][min(k+1,R)]+=f[i][j][k]*p;\\ f[i+1][j-1][0]+=f[i][j][k]*(1-p);\\ ans+=f[i][j][k]*p*(min(k+1,R)); \] 一开始我以为那个ans不能矩乘，实际上是可以的
A 国在 B 国中设有 N 个情报站，编号为 1,2,3, …… ,N ，每个情报站有一个坐标 (Xi,Yi) 。但是， A 国的工作人员发现，每个情报站里都被埋上了炸弹！
这些炸弹非常特殊 ， 只要同时拆除其中的三个炸弹 ， 所有炸弹就都不会爆炸了。由于各个情报站联络需要代价 ， 拆除炸弹需要花费的总代价为这些炸弹两两之间的曼哈顿距离和。现在 A 国的指挥部门找到了你 ， 希望知道可能需要的最大代价和最小代价 。
对于 100% 的数据， N<=100000 ， 0<=Xi,Yi<=10^8
先考虑只要选择两个点的情况，令 Xmax 表示两个点中 X 坐标较大的点的 X 坐标，Xmin 表示两个点中 X 坐标较小的点的 X 坐标，Ymax,Ymin 同理。则答案即为 Xmax-Xmin+Ymax-Ymin。我们先计算最大值。考虑最大值的分布，显然我们只要选出使 Xmax+Ymax,-Xmin-Ymin，Xmax-Ymin,-Xmin+Ymax 这四个表达式值最大的点暴力即可。 然后计算最小值。若不考虑 Xmin=Xmax 或 Ymin=Ymax 这些极端情况，两个点的位置情况 只有两种(左下，左上)，是对称的，我们只考虑其中的一种情况。以第一个点在第二个点左 下方为例。则第一个点的坐标为(Xmin,Ymin)。显然，我们要查找的是 X>Xmin 且 Y>Ymin 且 X+Y 最小的点。我们可以按 X 轴从大到小枚举，保证 X>Xmin，按 Y 轴坐标维护一棵线 段树，记录区间 X+Y 最小的值，在每个点处只要在线段树中查询[Ymin,+ ∞)中的 X+Y 最小 值，更新答案，然后插入点(Xmin,Ymin)即可。时间复杂度 O(NlogN)。 接下来考虑三个点的情况。我们考虑三个点两两之间的曼哈顿距离和的实质。通过画图， 我们容易发现，问题的实质是求能包含这三个点的最小矩形的周长，即 2*(Xmax-Xmin+Ymax-Ymin)，因此我们只要最大化和最小化 Xmax-Xmin+Ymax-Ymin 即可。 考虑这四个未知量，显然，一个点最多确定一个 X 未知量和一个 Y 未知量，答案的组成可 能有两种情况： ①一个点确定了一个 X 和一个 Y，另外两个点分别确定了一个 X 和一个 Y。 ②一个点确定了一个 X 和一个 Y，另一个点同样确定了一个 X 和一个 Y，还有一个点 什么都没有确定(但必须存在这个点)。 我们分别考虑这两种情况。先考虑最大值。显然，确定最大值的点一定在 Xmax+Ymax,-Xmin+Ymax,-Xmin-Ymin,Xmax-Ymin,Xmin,Xmax,Ymin,Ymax 最大的至多 8个 点中选择三个，因此只需选出能使这些值变得最大的点暴力即可。 然后考虑最小值。先考虑情况①。假设确定了 X 和 Y 的点在左上方(即该点在 3 个点中 的-Xmin+Ymax 最小)，设另外两个点分别为(Xmax,Y)和(X,Ymin)。我们维护一棵线段树， 维护在 X 在 i 处时首先从下方往上方依次枚举每个点作为左上角，我们使用线段树维护所有 (X,Ymin)节点的 Xmax-Ymin 的最大值。每次枚举一个点，首先查询它(Xmin,+ ∞)中的 Xmax-Ymin 的最小值更新答案，然后将它作为可能的 Xmax 更新线段树在(-∞ ,Xmin)中的 Xmax-Ymin，然后把自己作为可能的 Ymin 更新线段树在这个点上的最大 Y 值，就可以完美 解决情况①，时间复杂度 O(NlogN)。 对于情况②，我们枚举中间的点，然后计算四个方向上离它最近的节点，这个即为两个 点求最近曼哈顿距离的情况。计算对角方向两个最近点的距离和并更新答案即可。时间复杂 度仍为 O(NlogN)。 这题同样可以使用分治算法解决，时间复杂度仍为 O(NlogN)。
By Bomb解题报告.pdf
~有很多小错误~
有几个地方需要注意
把全部点旋转时，点(x,y)变为(-y,x)解决情况①时，更新单点的时候不能更新答案，见代码对于情况②，为了防止重合的点重复计算，我们用1~i-1的点更新i的一个方向，用i+1~n的点更新i的对角方向 #include<cstdio> #include<cstring> #include<algorithm> #define INF 1000000000 using namespace std; struct kk { int x,y,rank; }; struct qy { int x,y,ans,tag,ans2; }; int n,i,j,k,ans1,ans2,fx; kk a[100005],b[100005]; int t1[100005],t2[100005]; qy tree[400005],treee[400005]; int sel[9]; int mi[5][100005]; int find1(int x) { int l=1,r=t1[0],mid=(l+r)/2; while (l<r) { if (t1[mid]<x) l=mid+1; else r=mid; mid=(l+r)/2; } return mid; } int find2(int x) { int l=1,r=t2[0],mid=(l+r)/2; while (l<r) { if (t2[mid]<x) l=mid+1; else r=mid; mid=(l+r)/2; } return mid; } int comp(kk a,kk b) { return ((a.x>b.x)||((a.x==b.x)&&(a.y>b.y))); } void clear(int k,int l,int r) { tree[k].x=tree[k].y=tree[k].tag=INF; tree[k].ans=INF; if (l!=r) { int mid=(l+r)/2; clear(k*2,l,mid); clear(k*2+1,mid+1,r); } } void clear2(int k,int l,int r) { treee[k].x=treee[k].y=treee[k].tag=INF; treee[k].ans=INF; treee[k].ans2=-INF; if (l!=r) { int mid=(l+r)/2; clear2(k*2,l,mid); clear2(k*2+1,mid+1,r); } } void pushdown(int k,int l,int r) { if (l!=r) { tree[k*2].ans=min(tree[k*2].ans,tree[k*2].x+tree[k].tag); tree[k*2].tag=min(tree[k*2].tag,tree[k].tag); tree[k*2+1].ans=min(tree[k*2+1].ans,tree[k*2+1].x+tree[k].tag); tree[k*2+1].tag=min(tree[k*2+1].tag,tree[k].tag); } tree[k].tag=INF; } void update(int k,int l,int r) { tree[k].x=min(tree[k*2].x,tree[k*2+1].x); tree[k].y=min(tree[k*2].y,tree[k*2+1].y); tree[k].ans=min(tree[k*2].ans,tree[k*2+1].ans); } int query(int k,int l,int r,int x,int y) { pushdown(k,l,r); if ((l<=y)&&(r>=x)) { if ((l>=x)&&(r<=y)) { return tree[k].ans; } int mid=(l+r)/2; return min(query(k*2,l,mid,x,y),query(k*2+1,mid+1,r,x,y)); } return INF; } int query2(int k,int l,int r,int x,int y) { if ((l<=y)&&(r>=x)) { if ((l>=x)&&(r<=y)) { return treee[k].ans; } int mid=(l+r)/2; return min(query2(k*2,l,mid,x,y),query2(k*2+1,mid+1,r,x,y)); } return INF; } int query3(int k,int l,int r,int x,int y) { if ((l<=y)&&(r>=x)) { if ((l>=x)&&(r<=y)) { return treee[k].ans2; } int mid=(l+r)/2; return max(query3(k*2,l,mid,x,y),query3(k*2+1,mid+1,r,x,y)); } return -INF; } void modify1(int k,int l,int r,int x,int y) { pushdown(k,l,r); if (l==r) { tree[k].x=min(tree[k].x,y); } else { int mid=(l+r)/2; if (x<=mid) modify1(k*2,l,mid,x,y); else modify1(k*2+1,mid+1,r,x,y); tree[k].x=min(tree[k*2].x,tree[k*2+1].x);//这里不能更新ans,因为旧的y都在x右边 } } void modify2(int k,int l,int r,int x,int y,int z) { pushdown(k,l,r); if ((l<=y)&&(r>=x)) { if ((l>=x)&&(r<=y)) { tree[k].ans=min(tree[k].ans,tree[k].x+z);//必须这样打，因为是用这个z跟以前的x匹配 tree[k].tag=min(tree[k].tag,z); return; } int mid=(l+r)/2; modify2(k*2,l,mid,x,y,z); modify2(k*2+1,mid+1,r,x,y,z); update(k,l,r); } } void modify3(int k,int l,int r,int x,int y) { if (l==r) { treee[k].ans=min(treee[k].ans,y); treee[k].ans2=max(treee[k].ans2,y); } else { int mid=(l+r)/2; if (x<=mid) modify3(k*2,l,mid,x,y); else modify3(k*2+1,mid+1,r,x,y); treee[k].ans=min(treee[k*2].ans,treee[k*2+1].ans); treee[k].ans2=max(treee[k*2].ans2,treee[k*2+1].ans2); } } void does() { int i,j,s1,s2; for (i=1;i<=n;i++) b[i].rank=i; t1[0]=0; for (i=1;i<=n;i++) t1[++t1[0]]=a[i].x; sort(t1+1,t1+1+t1[0]); for (i=1;i<=n;i++) b[i].x=find1(a[i].x); t2[0]=0; for (i=1;i<=n;i++) t2[++t2[0]]=a[i].y; sort(t2+1,t2+1+t2[0]); for (i=1;i<=n;i++) b[i].y=find2(a[i].y); sort(b+1,b+1+n,comp); clear(1,1,n); for (i=1;i<=n;i++) { s1=query(1,1,n,b[i].y,n); ans2=min(ans2,s1-t1[b[i].x]-t2[b[i].y]); modify1(1,1,n,b[i].y,t1[b[i].x]); modify2(1,1,n,1,b[i].y-1,t2[b[i].y]); } } void does2() { for (i=1;i<=n;i++) b[i].rank=i; t1[0]=0; for (i=1;i<=n;i++) t1[++t1[0]]=a[i].x; sort(t1+1,t1+1+t1[0]); for (i=1;i<=n;i++) b[i].x=find1(a[i].x); t2[0]=0; for (i=1;i<=n;i++) t2[++t2[0]]=a[i].y; sort(t2+1,t2+1+t2[0]); for (i=1;i<=n;i++) b[i].y=find2(a[i].y); sort(b+1,b+1+n,comp); clear2(1,1,n); fx++; for (i=1;i<=n;i++) { mi[fx][b[i].rank]=query2(1,1,n,b[i].y,n)-t1[b[i].x]-t2[b[i].y]; modify3(1,1,n,b[i].y,t1[b[i].x]+t2[b[i].y]); } clear2(1,1,n); fx++; for (i=n;i>=1;i--) { mi[fx][b[i].rank]=t1[b[i].x]+t2[b[i].y]-query3(1,1,n,1,b[i].y); modify3(1,1,n,b[i].y,t1[b[i].x]+t2[b[i].y]); } } int js(int x,int y,int z) { return (max(max(a[x].x,a[y].x),a[z].x)-min(min(a[x].x,a[y].x),a[z].x)+max(max(a[x].y,a[y].y),a[z].y)-min(min(a[x].y,a[y].y),a[z].y)); } int main() { freopen("read.in","r",stdin); ans1=0; ans2=100000000; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%d%d",&a[i].x,&a[i].y); } for (i=1;i<=8;i++) sel[i]=1; for (i=1;i<=n;i++) { if (a[sel[1]].x+a[sel[1]].y<a[i].x+a[i].y) sel[1]=i; if (a[sel[2]].x-a[sel[2]].y<a[i].x-a[i].y) sel[2]=i; if (-a[sel[3]].x+a[sel[3]].y<-a[i].x+a[i].y) sel[3]=i; if (-a[sel[4]].x-a[sel[4]].y<-a[i].x-a[i].y) sel[4]=i; if (a[sel[5]].x<a[i].x) sel[5]=i; if (-a[sel[6]].x<-a[i].x) sel[6]=i; if (a[sel[7]].y<a[i].y) sel[7]=i; if (-a[sel[8]].y<-a[i].y) sel[8]=i; } for (i=1;i<=8;i++) { for (j=i+1;j<=8;j++) { for (k=j+1;k<=8;k++) { if ((sel[i]!=sel[j])&&(sel[i]!=sel[k])&&(sel[j]!=sel[k])) ans1=max(ans1,js(sel[i],sel[j],sel[k])); } } } does(); for (i=1;i<=n;i++) { swap(a[i].x,a[i].y); a[i].x=-a[i].x; } does(); for (i=1;i<=n;i++) { swap(a[i].x,a[i].y); a[i].x=-a[i].x; } does(); for (i=1;i<=n;i++) { swap(a[i].x,a[i].y); a[i].x=-a[i].x; } does(); for (i=1;i<=n;i++) { swap(a[i].x,a[i].y); a[i].x=-a[i].x; } does2(); for (i=1;i<=n;i++) { swap(a[i].x,a[i].y); a[i].x=-a[i].x; } does2(); for (i=1;i<=n;i++) { ans2=min(ans2,mi[1][i]+mi[2][i]); ans2=min(ans2,mi[3][i]+mi[4][i]); if (ans2==0) { ans2=ans2; } } printf("%d\n%d",ans1*2,ans2*2); }丑死了
转载于:https://www.cnblogs.com/leason-lyx/p/11293740.html
