<题面链接> 提取码：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
|
#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 即角色阵亡的状态是不能转移的，对于其他状态：
第 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)；
第 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
|
#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
|
#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，欢迎提问！