Day2
T1 Attack
Description
chnlich 非常喜欢玩三国志这款游戏,并喜欢用一些策略出奇制胜。现在,他要开始征服世界的旅途了。他的敌人有N 座城市和N 个太守, N个城市可以看作在二维平面上的N 个点。N 座城市的标号为0,1,2,......,N-1。第i 座城市的坐标为(Xi,Yi),镇守这座城市的太守的能力值为Zi。
chnlich 每次会选择一个边平行于坐标轴的矩形区域,并奇袭其中太守能力值第K小的城市(奇袭结束之后城市与太守依然存在)。
不过,他的敌人经常会偷偷交换两座城市的太守,防止弱点被chnlich 发现。
现在,chnlich 想要知道,每次奇袭时他的敌人的能力值。
Input
输入的第一行包含两个整数 N,M,N 表示城市与太守的个数,M 表示接下来发生了 M 个事件。
输入的第二行到第 N+1行,每行包含三个整数,第 i+2行的三个整数依次表示编号为 i 的城市的 Xi,Yi,Zi,含义如题所述。
输入的第 N+2行到第 N+M+1行,每行有两种可能形式:
第一种
QUERY x0 y0 x1 y1 k
表示 chnlich 询问一个相对顶点为(x0,y0),(x1,y1)的矩形中,第 k 小能力值太
守的能力值。
第二种
SWAP x y
表示 chnlich 的敌人交换了编号为 x 和 y 两座城市的太守。
Output
对于每一个 QUERY,输出一行。
若不存在第 k 小能力值的太守,输出"It doesn't exist."(不包含引号)。
否则输出一个整数,表示矩形内能力值第 k 小太守的能力值。
Sample Input
3 5
1 1 1
2 2 2
3 3 3
QUERY 1 1 3 3 3
SWAP 0 1
QUERY 2 2 4 4 1
SWAP 2 2
QUERY 2 2 3 3 3
Sample Output
3
1
It doesn't exist.
Hint
对于100%的数据,N<=60000,M<=10000,0<=Xi,Yi,Zi<=10^9,k<=10^9,保证所有操作均合法。
开始想用树套数来维护，可是没打过树套树
然后打了NMlog(N)的暴力
#include<bits/stdc++.h>
using namespace std;
int n,m,ra,rb,rc,xl,xr,yl,yr,k,cnt,s[60001];
char op[101];
struct node{
int x,y,z;
}city[60001];
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int main()
{
read(n);read(m);
for(int i=0;i<n;i++)
{
read(city[i].x);
read(city[i].y);
read(city[i].z);
}
for(int i=1;i<=m;i++)
{
scanf("%s",op);
if(op[0]=='Q')
{
read(xl);read(yl);
read(xr);read(yr);
read(k);cnt=0;
for(int j=0;j<n;j++)
if(city[j].x>=xl&&city[j].x<=xr&&city[j].y>=yl&&city[j].y<=yr)
s[++cnt]=city[j].z;
if(cnt<k)
puts("It doesn't exist.");
else
{
sort(s+1,s+cnt+1);
printf("%d\n",s[k]);
}
}
else
{
read(ra);read(rb);
swap(city[ra].z,city[rb].z);
}
}
return 0;
} 但是几个点竟然Wa了
发现(X0,Y0)不仅仅可以给出左下角
由于时间给了10倍（10s），正解竟然可以用O(NM)的暴力
我却没有发现...当时就没想这个做法
先按太守的能力从小到大排序，再每次询问枚举所有城市
代码：
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,z,bis;
}city[60001];
int n,m,fi[60001],xl,xr,yl,yr,cnt,ra,rb,k;
char op[10001];
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
bool comp(node a,node b)
{
return a.z<b.z;
}
int main()
{
read(n);read(m);
for(int i=0;i<n;i++)
{
read(city[i].x);
read(city[i].y);
read(city[i].z);
city[i].bis=i;
}
sort(city,city+n,comp);
for(int i=0;i<n;i++)
fi[city[i].bis]=i;
for(int i=1;i<=m;i++)
{
scanf("%s",op);
if(op[0]=='Q')
{
read(xl);read(yl);
read(xr);read(yr);
read(k);
if(xr<xl)
swap(xr,xl);
if(yr<yl)
swap(yr,yl);
cnt=0;
for(int j=0;j<n;j++)
if(city[j].x>=xl&&city[j].x<=xr&&city[j].y>=yl&&city[j].y<=yr)
{
cnt++;
if(cnt==k)
{
printf("%d\n",city[j].z);
break;
}
}
if(cnt<k)
puts("It doesn't exist.");
}
else
{
read(ra);read(rb);
int ka=ra,kb=rb;
ra=fi[ra];rb=fi[rb];
swap(fi[ka],fi[kb]);
swap(city[ra].x,city[rb].x);
swap(city[ra].y,city[rb].y);
}
}
return 0;
} 但是1s的正解是这个：
进行 分块 并构建 划分树 ，我们将每个块中的划分树构成相同的形态，即每棵树的每一层的分割标准均相同，每次询问的时候，由于每棵树的形态相同，可以一起计算
出小于等于一个数的数有多少个，然后在所有树中同时向左走或者向右走即可，可以省去二分答案的复杂度。标程使用的方法是离散化后按每个数的二进制表示确定每个数在树中的位置。一次查询操作复杂度为 O(N/T*logN)，总时间复杂度大约为 为 O((N+M)根号（N）log（N）)，期望得分100分。至此，这道题被完美解决了。
还有整体二分加树套数的正解
这两种代码先咕着
T2 Contra
Description
偶然间,chnlich 发现了他小时候玩过的一个游戏“魂斗罗”,于是决定怀旧。但是这是一个奇怪的魂斗罗 MOD。有 N 个关卡,初始有 Q 条命。每通过一个关卡,会得到 u 分和1条命,生命上限为 Q。其中 u=min(最近一次连续通过的关数,R)。若没有通过这个关卡,将会失去1条命,并进入下一个关卡。当没有生命或没有未挑战过的关卡时,游戏结束,得到的分数为每关得到的分数的总和。由于 chnlich 好久不玩这个游戏了,每条命通过每个关卡的概率均为p(0<=p<=1),原先 chnlich 的最高分纪录是 S。现在 chnlich 想要知道,当 p 至少为多少时,chnlich 期望获得的总分数能够超过原先的最高分。
又是考数学...还是考期望...
二分答案之后不会dp求期望
此题完美爆0
#include<bits/stdc++.h>
using namespace std;
int n,r,q;
double s,le=0,ri=1,f[10001][21][6],md=1e-6;
bool check(double k)
{
double add=0;
for(int i=1;i<n;i++)
for(int j=0;j<=r;j++)
{
for(int l=1;l<=q;l++)
{
f[i+1][min(j+1,r)][min(l+1,q)]=f[i][j][l]*k+min(j+1,r);
f[i+1][0][q-1]=f[i][j][q]*(1-k);
}
f[i+1][0][0]=f[i][0][0];
}
for(int j=0;j<=r;j++)
for(int l=1;l<=q;l++)
add+=f[n][j][l];
return add>s;
}
int main()
{
cin>>n>>r>>q>>s;
while(ri-le>md)
{
double mid=(ri+le)/2;
if(check(mid))
ri=mid;
else
le=mid;
}
cout<<le<<endl;
return 0;
} 正解dp求期望
然而还要 矩阵快速幂 优化
#include <bits/stdc++.h>
#define ll long long
#define eps 1e-11
using namespace std;
int n,r,q,s,tot,sz,id[6][24];
double le=0,ri=1.0;
struct node
{
double f[105][105];
node(){memset(f,0,sizeof(f));}
friend node operator *(node a,node b)
{
node c;
for(int i=0;i<sz;i++)
for(int k=0;k<sz;k++)
{
if(a.f[i][k]<eps)continue;
for(int j=0;j<sz;j++)
{
if(b.f[k][j]<eps)continue;
c.f[i][j]+=a.f[i][k]*b.f[k][j];
}
}
return c;
}
};
bool check(double x)
{
node a,ans,b;
a.f[tot][tot]=b.f[0][tot]=1;
for(int i=1;i<=q;i++)
for(int j=1;j<=r;j++)
{
a.f[tot][id[i][j]]+=j*x;
if(i<q&&j<r)
a.f[id[i+1][j+1]][id[i][j]]+=x;
else if(i<q)
a.f[id[i+1][j]][id[i][j]]+=x;
else if(j<r)
a.f[id[i][j+1]][id[i][j]]+=x;
else
a.f[id[i][j]][id[i][j]]+=x;
if(i>1)
a.f[id[i-1][1]][id[i][j]]=(1.0-x);
}
for(int i=0;i<=tot;i++)
ans.f[i][i]=1;
int m=n;
while(m)
{
if(m&1)
ans=ans*a;
a=a*a;
m>>=1;
}
b=b*ans;
double sum=b.f[0][id[q][1]];
return sum-s>eps;
}
int main()
{
scanf("%d%d%d%d",&n,&r,&q,&s);
sz=r*q+1;
for(int i=1;i<=q;i++)
for(int j=1;j<=r;j++)
id[i][j]=tot++;
if(!check(1.0))
{
printf("Impossible.\n");
return 0;
}
while(ri-le>eps)
{
double mid=(le+ri)/2;
if(check(mid))
ri=mid;
else
le=mid;
}
printf("%.6lf\n",(le+ri)/2);
} 虽然只输出六位小数，但是eps赋大了还要Wa
矩阵快速幂还要加上特判来优化
在T与WA之间疯狂试探
T3 Bomb
Description
A 国和 B 国是两个超级大国，长期处于冷战状态；
A 国在 B 国中设有 N 个情报站，编号为 1,2,3, …… ,N ，每个情报站有一个坐标 (Xi,Yi) 。但是， A 国的工作人员发现，每个情报站里都被埋上了炸弹！
这些炸弹非常特殊 ， 只要同时拆除其中的三个炸弹 ， 所有炸弹就都不会爆炸了。
由于各个情报站联络需要代价 ， 拆除炸弹需要花费的总代价为这些炸弹两两之间的曼哈顿距离和。
现在 A 国的指挥部门找到了你 ， 希望知道可能需要的最大代价和最小代价 。
Input
输入的第一行包含一个整数 N 。接下来 N 行，第 i+1 行两个整数 Xi,Yi ，表示第 i 个情报站的坐标。
Output
输出两行 ， 每行包含一个整数 ， 第一行表示可能的最大代价 ， 第二行表示可能的最小代价。
Sample Input
4
1 1
1 2
2 1
2 3
Sample Output
6
4
Hint
对于 30% 的数据， N<=500
对于另外 10% 的数据，每个点出现至少两遍
对于 50% 的数据， N<=1000
对于 60% 的数据， N<=8000
对于 70% 的数据， N<=15000
对于 80% 的数据， N<=50000
对于 100% 的数据， N<=100000 ， 0<=Xi,Yi<=10^8
【 注释 】
对于两个点 (X0,Y0),(X1,Y1) ，
它们之间的曼哈顿距离为 abs(X0-X1)+abs(Y0-Y1) 。
最大值十分好求，很容易想到，然而最小值就有点麻烦了
没有办法打了个暴力
#include<bits/stdc++.h>
using namespace std;
int n,ansmx,ansmi=1e9;
struct node{
int x,y;
}pos[100001];
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int jl(int a,int b)
{
return abs(pos[a].x-pos[b].x)+abs(pos[a].y-pos[b].y);
}
int main()
{
read(n);
for(int i=1;i<=n;i++)
{
read(pos[i].x);
read(pos[i].y);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)
continue;
for(int k=1;k<=n;k++)
{
if(k==j||k==i)
continue;
ansmi=min(ansmi,jl(i,j)+jl(j,k)+jl(i,k));
ansmx=max(ansmx,jl(i,j)+jl(j,k)+jl(i,k));
}
}
}
cout<<ansmx<<endl<<ansmi<<endl;
return 0;
} 不出所料完美T飞
正解
分情况讨论，再枚举每个点，用线段树维护
首先通过不断翻转坐标系，假设三个点以横坐标为第一关键字，纵坐标为第二关键字排序后A在B前面，B在C前面。
那么只需要处理以下两种情况：
1.B的纵坐标在AC之间，这时三个点的距离和为2((xC+yC)−(xA+yA))。
可以用线段树处理出每个点作为B时xA+yA以及xC+yC的最值，然后更新答案即可。
2.B的纵坐标不超过A的纵坐标，这时三个点的距离和为2((xC+yC)−xA−yB)。
还是考虑枚举B，需要维护它左边每个A与右边每个C合并的答案。
于是用一棵线段树维护A集合，从n到1依次计算。
假设现在处理的是点B，那么先把B从A中删除，然后查询答案，再将B加入C集合中，也就是在A集合里进行区间更新。
时间复杂度O(nlogn)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ansmx,ansmi=1000000000,c[100001],d[100001],e[100001],fmx[100001],fmn[100001];
struct node{
int x,y;
}a[100001],b[100001];
bool cmp(node a,node b)
{
return a.x==b.x?a.y<b.y:a.x<b.x;
}
bool cmpb(node a,node b)
{
return a.x<b.x;
}
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
inline void umax(int&a,int b)
{
if(a<b)
a=b;
}
inline void umin(int&a,int b)
{
if(a>b)
a=b;
}
inline int findl(int x)
{
int l=1,r=n,mid,t;
while(l<=r)
{
mid=(l+r)>>1;
if(b[mid].x>=x)
{
t=mid;
r=mid-1;
}
else
l=mid+1;
}
return t;
}
inline int findr(int x)
{
int l=1,r=n,mid,t;
while(l<=r)
{
mid=(l+r)>>1;
if(b[mid].x<=x)
{
t=mid;
l=mid+1;
}
else
r=mid-1;
}
return t;
}
namespace Sub1
{
struct node{
int mx,mn;
}T[300001];
void build(int x,int a,int b)
{
T[x].mx=-1000000000,T[x].mn=1000000000;
if(a==b)
return;
int mid=(a+b)>>1;
build(x<<1,a,mid);
build(x<<1|1,mid+1,b);
}
void ins(int x,int a,int b,int c,int p)
{
umax(T[x].mx,p);
umin(T[x].mn,p);
if(a==b)
return;
int mid=(a+b)>>1;
if(c<=mid)
ins(x<<1,a,mid,c,p);
else
ins(x<<1|1,mid+1,b,c,p);
}
int askmx(int x,int a,int b,int c,int d)
{
if(c<=a&&b<=d)
return T[x].mx;
int mid=(a+b)>>1,t=-1000000000;
if(c<=mid)
t=askmx(x<<1,a,mid,c,d);
if(d>mid)
umax(t,askmx(x<<1|1,mid+1,b,c,d));
return t;
}
int askmn(int x,int a,int b,int c,int d)
{
if(c<=a&&b<=d)
return T[x].mn;
int mid=(a+b)>>1,t=1000000000;
if(c<=mid)
t=askmn(x<<1,a,mid,c,d);
if(d>mid)
umin(t,askmn(x<<1|1,mid+1,b,c,d));
return t;
}
}
namespace Sub2
{
struct Node{
int mxx,mnx,mxv,mnv,mxt,mnt;
}T[300001];
inline void tagmx(int x,int p)
{
umax(T[x].mxv,T[x].mxx+p);
umax(T[x].mxt,p);
}
inline void tagmn(int x,int p)
{
umin(T[x].mnv,T[x].mnx+p);
umin(T[x].mnt,p);
}
inline void pb(int x)
{
tagmx(x<<1,T[x].mxt);
tagmx(x<<1|1,T[x].mxt);
tagmn(x<<1,T[x].mnt);
tagmn(x<<1|1,T[x].mnt);
T[x].mxt=-1000000000,T[x].mnt=1000000000;
}
inline void up(int x)
{
T[x].mxx=max(T[x<<1].mxx,T[x<<1|1].mxx);
T[x].mnx=min(T[x<<1].mnx,T[x<<1|1].mnx);
T[x].mxv=max(T[x<<1].mxv,T[x<<1|1].mxv);
T[x].mnv=min(T[x<<1].mnv,T[x<<1|1].mnv);
}
void build(int x,int a,int b)
{
T[x].mxt=-1000000000,T[x].mnt=1000000000;
if(a==b)
{
T[x].mxx=T[x].mnx=e[a];
T[x].mxv=-1000000000,T[x].mnv=1000000000;
return;
}
int mid=(a+b)>>1;
build(x<<1,a,mid);
build(x<<1|1,mid+1,b);
up(x);
}
void del(int x,int a,int b,int c)
{
if(a==b)
{
T[x].mxx=T[x].mxv=-1000000000;
T[x].mnx=T[x].mnv=1000000000;
return;
}
pb(x);
int mid=(a+b)>>1;
if(c<=mid)
del(x<<1,a,mid,c);
else
del(x<<1|1,mid+1,b,c);
up(x);
}
void change(int x,int a,int b,int c,int d,int p)
{
if(c<=a&&b<=d)
{
tagmx(x,p);
tagmn(x,p);
return;
}
pb(x);
int mid=(a+b)>>1;
if(c<=mid)
change(x<<1,a,mid,c,d,p);
if(d>mid)
change(x<<1|1,mid+1,b,c,d,p);
up(x);
}
int askmx(int x,int a,int b,int c,int d)
{
if(c<=a&&b<=d)
return T[x].mxv;
pb(x);
int mid=(a+b)>>1,t=-1000000000;
if(c<=mid)
t=askmx(x<<1,a,mid,c,d);
if(d>mid)
umax(t,askmx(x<<1|1,mid+1,b,c,d));
return up(x),t;
}
int askmn(int x,int a,int b,int c,int d)
{
if(c<=a&&b<=d)
return T[x].mnv;
pb(x);
int mid=(a+b)>>1,t=1000000000;
if(c<=mid)
t=askmn(x<<1,a,mid,c,d);
if(d>mid)
umin(t,askmn(x<<1|1,mid+1,b,c,d));
return up(x),t;
}
}
void solve()
{
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
b[i].x=a[i].y;
b[i].y=i;
}
sort(b+1,b+n+1,cmpb);
for(int i=1;i<=n;i++)
{
c[i]=findl(a[i].y);
d[b[i].y]=i;
}
for(int i=1;i<=n;i++)
e[d[i]]=-a[i].x;
Sub1::build(1,1,n);
for(int i=1;i<=n;i++)
{
fmx[i]=Sub1::askmx(1,1,n,1,c[i]);
fmn[i]=Sub1::askmn(1,1,n,1,c[i]);
Sub1::ins(1,1,n,c[i],-a[i].x-a[i].y);
}
Sub1::build(1,1,n);
for(int i=n;i;i--)
{
umax(ansmx,Sub1::askmx(1,1,n,c[i],n)+fmx[i]);
umin(ansmi,Sub1::askmn(1,1,n,c[i],n)+fmn[i]);
Sub1::ins(1,1,n,c[i],a[i].x+a[i].y);
}
Sub2::build(1,1,n);
for(int i=n;i;i--)
{
Sub2::del(1,1,n,d[i]);
umax(ansmx,Sub2::askmx(1,1,n,c[i],n)-a[i].y);
umin(ansmi,Sub2::askmn(1,1,n,c[i],n)-a[i].y);
Sub2::change(1,1,n,1,findr(a[i].y),a[i].x+a[i].y);
}
}
signed main()
{
read(n);
for(int i=1;i<=n;i++)
{
read(a[i].x);
read(a[i].y);
}
solve();
for(int i=1;i<=n;i++)
{
a[i].x*=-1;
a[i].y*=-1;
}
solve();
for(int i=1;i<=n;i++)
a[i].x*=-1;
solve();
for(int i=1;i<=n;i++)
{
a[i].x*=-1;
a[i].y*=-1;
}
solve();
cout<<ansmx*2<<endl<<ansmi*2<<endl;
return 0;
} 
京公网安备 11010502036488号