游记&OI - 广州纪中游记 Day2 & Day3

<题面链接> 提取码:7puf


Part1. 游记

- 小插曲

其实 reader 们看到的这篇文章并不是原稿……我在 Day3 结束当天写的原稿因为 D盘 格式化过后就没了 QwQ,跟着丢失的是 Day4&Day5 的游记……(awsl)

不是说好的D盘不清空吗 awa,不得不吐槽……再也不信这电脑了,现在这篇 blog 是 Day7 写的,趁明天放假,没什么要紧的事情,把博客按照之前写的思路补一补。可能有什么小错误,可以在邮箱里面疯狂吐槽……

- Day2

依然是上午考试,下午评讲,晚上补题。后面应该每天都是这样,但也不显单调(毕竟碰见了各种各样奇妙的题目)。

dalao 讲题讲的非常清楚,仿佛跟我考试的时候自己想的一模一样(???)那么现在问题来了?我是被卡常了吗?(en)

- Day3

突然不考试了,今天讲课(狂喜 ???)

这里的讲课安排还是非常人性化的,分了几个专题,在 Day2 的晚上把安排发下来给大家看了一看。今天的专题是 动态规划(鬼画)。

上午、下午以及晚上的课程按难度递增,可以自主选择参加。

本来上午联赛难度的课程不想去的,结果被同学拉着一起去了……感觉的确不是特别适合,参与度不是特别高,也没有听到自己真正想听的内容,中途休息的时候就和几个同学一起溜回机房了(据说几个我想听的内容比如凸优化之类的后半节课讲了,没有去还是有点遗憾的)。

下午仍然是 D(alao)P(ower) ,各种各样奇怪的题目,虽然很难,基本上不能自己想出正解,但还是发现了几种新的模型,收获还行。

晚上NOI难度的讲课就 咕 了。


Part2. Solution

T1. Attack

- Experience

这道题真的没有想到正解,主要是没有想到可以按照太守的能力值排序……还有一个坑点不知道 reader 们是否注意到:时限是 $10s$ ……

$10s$ 诶!$10s$!!!难道你们就不想搞点什么事情??

正解 $O(NM)$ ,$N\leq6*10^4,M\leq10^4$ ……好像刚好能卡过???

- Solution

之前也提到了,按太守的能力值排序,具体是从小到大。

这样的话对于每个询问,我们就可以依次枚举城市,判断当前城市是否在当前询问的矩形中,找到第 $k$ 个在矩形中的城市即可。

对于修改,因为我们对城市排了序,城市的编号也相应有改变:记城市 i 在排序后变为了 idmap[i] ;这样我们就能迅速地找到要交换太守的两个城市的编号了。在修改时,因为我们仍然要保证太守的能力值有序,所以我们不能直接交换两座城市的太守,而是交换城市的坐标,以及它原来的编号,最后别忘了 idmap 也要相应地交换!

- Source

[养成不随便看代码的好习惯.点击展开/折叠代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=60000;

struct CITY{int x,y,z,id;}cty[N+3];
bool CmpCITY(const CITY cpr1,const CITY cpr2){return cpr1.z<cpr2.z;}

int n,m;
int idmap[N+3];

int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&cty[i].x,&cty[i].y,&cty[i].z),
cty[i].id=i;
sort(cty+1,cty+1+n,CmpCITY);
for(int i=1;i<=n;i++)
idmap[cty[i].id]=i;
for(int t=1;t<=m;t++){
char str[10]="";
scanf("%s",str);
if(str[0]=='Q'){
int cnt=0,Lef,Rig,Cel,Flr,rnk;
scanf("%d%d%d%d%d",&Lef,&Cel,&Rig,&Flr,&rnk);
if(Flr>Cel) swap(Flr,Cel);
if(Lef>Rig) swap(Lef,Rig);
for(int i=1;i<=n;i++)
if(Lef<=cty[i].x && cty[i].x<=Rig && Flr<=cty[i].y && cty[i].y<=Cel){
cnt++;
if(cnt==rnk){
printf("%d\n",cty[i].z);
break;
}
}
if(cnt<rnk) printf("It doesn't exist.\n");
}
else{
int cur1,cur2;scanf("%d%d",&cur1,&cur2);
cur1++;cur2++;
cur1=idmap[cur1];cur2=idmap[cur2];
swap(cty[cur1].x,cty[cur2].x);
swap(cty[cur1].y,cty[cur2].y);
swap(cty[cur1].id,cty[cur2].id);
idmap[cty[cur1].id]=cur1;idmap[cty[cur2].id]=cur2;
}
}
return 0;
}

T2 - Contra

- Experience

这道题可以顺藤摸瓜……

一开始看到 $p$ 是一个小数,还要求期望,显然很难一次性求出 $p$,然后就能够想到二分查找,进一步发现可以检验 $p$ 是否满足条件。

然后就开始想怎么检验——既然是期望……期望Dp?right

好像就是这样了?看了一眼数据规模,$N\leq10^8$,WTF?矩阵快速幂?发现每次转移其实是一样的,开心的发现能够用矩阵快速幂。

~~~ 非常顺利,于是在构造矩阵这里卡住了,卡了将近 40 分钟,有一点爆炸,去看最后一题了……把最后一题暴力骗分写完过后又回来补这道题,最后还是没写完(My vegetable has explosed.)

- Solution

二分查找非常显然,二分出 $p$ 后就需要检验,在当前的 $p$ 的条件下能否使得期望总分高于历史最高分即可。

= 检验答案(动态规划)

比较显然的 DP 状态定义:f[i][j][k] 表示通过(只是到达下一关,不一定胜利)第 i 关时,剩余 j 点生命,当前的 $u$ 为 k概率。(忘了 $u$ 是什么东西的 reader 们看题面去)

考虑第 i 关向第 i+1 关转移,首先我们知道 j=0 即角色阵亡的状态是不能转移的,对于其他状态:

  1. i 关胜利:生命回复 1 点,变为 min(j+1,Q);$u$ 增加 1 点,变为 min(k+1,R)

    则有 f[i+1][min(j+1,Q)][min(k+1,R)]+=f[i][j][k]*p,注意是 += ,因为还可能有其他状态转移过来。

    另外,因为我们算的是期望,这一步获得的分数对最终期望的贡献为 “获得该分数的概率 乘 获得分数”,即 f[i][j][k]*p*min(k+1,R)

  2. i 关失败:生命减少 1,$u$ 变为 0(因为没有连续胜利);

    则有 f[i+1][j-1][0]+=f[i][j][k]*(1-p)

    不得分,对答案没有贡献;

于是 Dp 就结束啦。

= 矩阵加速

因为我们只从 f[i] 转移到 f[i+1] ,考虑把 f[i][0~Q][0~R] 储存到一个矩阵中,只需要把每个状态 [j][k] 编号即可。

最后还要在矩阵中加上一行,即当前的答案。

转移矩阵就从之前的转移方程式中可以得出。

由此我们可以构造出一个边长为 $(Q+1)(R+1)+1$ 的转移矩阵,对其快速幂即可。

= 一点小优化

你以为这道题会让你这么轻而易举地 AC ??于是你轻蔑地提交了一发,自信满满地以为自己能切掉这道题……结果惊讶的发现自己 TLE 了?

于是你算了一下时间复杂度:

  • 二分查找:虽然说只要 $6$ 位小数,但是它卡精度……所以要计算 $9$ 位,时间 $O(\log_2 10^9)\approx30$ ;
  • 矩阵乘法:转移矩阵的边长的立方,约为 $O(Q^3R^3)\approx10^6$ ;
  • 矩阵快速幂:$O(\log_2n)\approx 25$;

总时间复杂度……$30\times25\times10^6=7.5\times10^8$ ???好像 low 不住……

所以你才知道,你需要一点小优化。

我们发现对于一些状态 [j][k],它一定不会出现(即概率为0),正因为概率为 0,它们对答案也不会有贡献,所以我们可以把它们删掉。具体这样的状态有:

  • [0][1~R],角色生命值为 0 时,上一局一定是失败,故不可能有连续通过关卡;
  • [0~Q-1][Q+1~R],角色连续通过关卡数大于 $Q$ ,因为每次通过角色都会恢复一点生命,故此时生命应满,这种生命不为满血的状态是不合法的。

应该还有一些不合法的状态,但这两个删去后就可以 AC 了。

- Source

[养成不随便看代码的好习惯.点击展开/折叠代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int cntvalue;
int value[100][100];

struct MATRIX{
double mat[200][200];
int rol,col;
void Make(int r,int c,int val){
rol=r;col=c;
for(int i=1;i<=rol;i++)
for(int j=1;j<=col;j++)
if(val) mat[i][j]=1.0*(i==j);
else mat[i][j]=0;
}
MATRIX operator *(const MATRIX curb)const{
MATRIX ret;
ret.Make(rol,curb.col,0);
for(int i=1;i<=ret.rol;i++)
for(int j=1;j<=ret.col;j++)
for(int k=1;k<=col;k++)
ret.mat[i][j]+=mat[i][k]*curb.mat[k][j];
return ret;
}
MATRIX QPow(int curb)const{
MATRIX ret,cura=*this;
ret.Make(rol,col,1);
while(curb){
if(curb&1) ret=ret*cura;
cura=cura*cura;
curb>>=1;
}
return ret;
}
}Mmid,Mfir,Mres;

int n,q,r,s;

inline int Index(int j,int k){
return value[j][k];
}
bool Check(double p){
int idxlim=cntvalue+1;
Mmid.Make(idxlim,idxlim,0);
for(int j=1;j<=q;j++)
for(int k=0;k<=r;k++){
int idx1,idx2;
idx1=Index(min(j+1,q),min(k+1,r));idx2=Index(j,k);
if(idx1 && idx2) Mmid.mat[idx1][idx2]+=p;
idx1=Index(j-1,0);idx2=Index(j,k);
if(idx1 && idx2) Mmid.mat[idx1][idx2]+=1-p;
idx1=idxlim;idx2=Index(j,k);
if(idx1 && idx2) Mmid.mat[idx1][idx2]+=min(k+1,r)*p;
}
Mmid.mat[idxlim][idxlim]++;
Mfir.Make(idxlim,1,0);
Mfir.mat[Index(q,0)][1]++;
Mres=Mmid.QPow(n);
Mres=Mres*Mfir;
double res=Mres.mat[idxlim][1];
return res>1.0*s;
}
int main(){
scanf("%d%d%d%d",&n,&r,&q,&s);
for(int i=0;i<=q;i++)
for(int j=0;j<=r;j++){
if(!i && j) continue;
if(j>q && i!=q) continue;
value[i][j]=++cntvalue;
}
double Plef=0,Prig=1;
while(Plef+1e-7<Prig){
double Pmid=(Plef+Prig)/2;
if(Check(Pmid)) Prig=Pmid;
else Plef=Pmid;
}
if(Check(Prig)) printf("%.6f\n",Prig);
else printf("Impossible.\n");
return 0;
}

T3 - Bomb

- Experience

没什么感觉,主要是把暴力分拿了就回去写 T2 了……

最后发现这不是一道 xx 分治暴力题吗??

- Solution

= 最大值

求最大值有一个比较显然的结论,三个点中,至少包含横坐标的最大值、最小值和纵坐标的最大值、最小值中的三个。

所以我们可以统计出:$x_{\max}$,$x_{\min}$,$y_{\max}$,$y_{\min}$,$(x+y)_{\max}$,$(x+y)_{\min}$,$(x-y)_{\max}$,$(x-y)_{\min}$。

则最大值在以下值之中:

  • $(x+y)_{\max}-x_{\min}-y_{\min}$;
  • $x_{\max}+y_{\max}-(x+y)_{\min}$;
  • $(x-y)_{\max}-x_{\min}+y_{\max}$;
  • $x_{\max}-(x-y)_{\min}-y_{\min}$;
= 最小值

下面的 $x_p$ 表示 $p$ 的横坐标,$y_p$ 同理。

我们把所有点按横坐标排序,考虑选取的 $3$ 个点在区间 $[L,R]$ 之中。

如果 $[L,R]$ 的大小不超过 $12$ ,我们可以暴力枚举其中的 $3$ 个点构成答案。

否则我们把 $[L,R]$ 从中间分为两个区间 $[L,M]$ 和 $[M+1,R]$ ,分别求解这两个区间。
求解完两个子区间后,考虑到可能存在答案:一部分点在 $[L,M]$ 中,另一部分在 $[M+1,R]$ 中,我们选择出一个最大的区间 $[L’,R’]$ ,使得区间内的每一个点的横坐标与 $x_M$(中间的点的横坐标)之差小于当前答案。即对于任何 $i\in[L’,R’]$,满足 $|x_i-x_M|<ans$ 。

显然只有从这个区间中选出 $3$ 个点可能使答案更小。
我们将 $[L’,R’]$ 中的点按纵坐标排序,类似于滑窗。考虑一定选择点 $t$($t\in[L’,R’]$) ,保证另外两个点的纵坐标小于 $y_t$ 且与 $y_t$ 之差小于当前答案,则可以确定另外两个点所在区间,再次暴力枚举求解。

为了防止被卡,划分区间时我们不一定从中间划分,而是从贴近中间的一个位置切开,即随机化。

- Source

[养成不随便看代码的好习惯.点击展开/折叠代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define qwq 3538

const int N=100000;

struct GPOINT{int x,y;}pnt[N+13],oth[N+13];
bool operator <(GPOINT cpr1,GPOINT cpr2) {
return cpr1.x!=cpr2.x?cpr1.x<cpr2.x:cpr1.y<cpr2.y;
}
bool Cmp(const GPOINT cpr1,const GPOINT cpr2){
return cpr1.y==cpr2.y? cpr1.x<cpr2.x:cpr1.y<cpr2.y;
}

int n,MinAns;

int GAbs(int num){
if(num<0) return -num;
else return num;
}
int MHD(int A,int B){return GAbs(pnt[A].x-pnt[B].x)+GAbs(pnt[A].y-pnt[B].y);}
int MaxCoc(int x,int y,int z){
return max(max(x,y),z)-min(min(x,y),z);
}
void Solve(int Lef,int Rig){
int Siz=Rig-Lef+1;
if(Siz<12){
for(int i=Lef;i<=Rig;i++)
for(int j=Lef;j<i;j++)
for(int k=Lef;k<j;k++)
MinAns=min(MinAns,MaxCoc(pnt[i].x,pnt[j].x,pnt[k].x)+MaxCoc(pnt[i].y,pnt[j].y,pnt[k].y));
return;
}
int Mid=(Siz<100? (Lef+Rig)/2 : Lef+rand()%(Siz-2));
nth_element(pnt+Lef,pnt+Mid,pnt+Rig+1);
int xmid=pnt[Mid].x;
if(rand()%2) Solve(Lef,Mid),Solve(Mid+1,Rig);
else Solve(Mid+1,Rig),Solve(Lef,Mid);
int noth=0;
for(int i=Lef;i<=Rig;i++)
if(GAbs(xmid-pnt[i].x)<MinAns)
oth[++noth]=pnt[i];
sort(oth+1,oth+1+noth,Cmp);
int L=1;
for(int R=3;R<=noth;R++){
while(L<R && GAbs(oth[L].y-oth[R].y)>=MinAns)
L++;
for(int i=L;i<R;i++)
for(int j=L;j<i;j++){
int cur=MaxCoc(oth[i].x,oth[j].x,oth[R].x)+MaxCoc(oth[i].y,oth[j].y,oth[R].y);
MinAns=min(MinAns,cur);
}
}
}
int main(){
srand(qwq);
scanf("%d",&n);
int maxx=-(1<<29),minx=(1<<29),
maxy=-(1<<29),miny=(1<<29),
maxxy=-(1<<29),minxy=(1<<29),
maxx_y=-(1<<29),minx_y=(1<<29);
for(int i=1;i<=n;i++)
scanf("%d%d",&pnt[i].x,&pnt[i].y),
maxx=max(maxx,pnt[i].x),
minx=min(minx,pnt[i].x),
maxy=max(maxy,pnt[i].y),
miny=min(miny,pnt[i].y),
maxxy=max(maxxy,pnt[i].x+pnt[i].y),
minxy=min(minxy,pnt[i].x+pnt[i].y),
maxx_y=max(maxx_y,pnt[i].x-pnt[i].y),
minx_y=min(minx_y,pnt[i].x-pnt[i].y);
int MaxAns=0;
MaxAns=max(MaxAns,maxxy-minx-miny);
MaxAns=max(MaxAns,maxx+maxy-minxy);
MaxAns=max(MaxAns,maxx_y-minx+maxy);
MaxAns=max(MaxAns,maxx-minx_y-miny);
MinAns=(1<<29);
Solve(1,n);
printf("%d\n%d\n",2*MaxAns,MinAns*2);
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com,欢迎提问!

0%