游记&OI - 广州纪中游记 Day5 & Day6

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


Part1. 游记

当你们看到我把 Day5&Day6 合在一起写了……你们应该就会知道 Day6 又是讲课……

反正 Day6 是没什么可写的,稍微水一点应该也没事

- Day5

这场考试非常(非常)友好,第一次在模拟赛里面 AC 一道题 QwQ。

反正就暴力推式子,感觉就像一道签到题,虽然说不上“人口普查”,反正是比之前的题好做多了。

但是除了签到题,其他题就翻车了 TAT ,想要动态倍增来优化一下时间复杂度,结果不知道怎么写,最后还写爆了,TLE 得渣渣都不剩(好吧,还是剩了 5 分的渣渣),还不如写一个 30 分的暴力……

Tab. 这一篇的原稿在某一天因为 计算机D盘 莫名清空就丢失了(如果你看过之前几天的 Blog 应该会知道),这一篇是在 Day11 的时候补的……

所以就只记得打比赛了……那些什么奇怪的日常就想不起来了。

本来下午要讲课,结果被 t*y 神仙拉去打多校(然后相当于他自己打),没有一点参与感……

以下是某段对话:
- “我好像知道这道题怎么做了。”
- “你看 t*y 已经 AC 了”
- “……”

另外一段对话:
- “你不要动这道题,我来!”
- “嗯好,我去做另外一道”
- (当 t*y 把另外一道 AC 的时候)“算了,我切不动了,还是你来吧”

咕咕咕……

平平淡淡的一天。

- Day6

讲课讲课讲课……

数据结构专场,倒是听懂了很多新奇的结构(其实只是我没学过),像什么 LCT、重量平衡树、可持久化Treap 什么的……

不得不吐槽,上午的讲课是真的水没有下午好。

感觉浪费了一上午,不过似乎下午把上午浪费的时间补回来了 awa。


Part2. Solution

仍然是题解……没有题面(或许我之后想起来会把题面PDF分享出来,放一个链接在这里)咕咕咕

- T1. 矩阵游戏(game)

[Experience]

这道题考试的时候就 AC 了,终于可以按照自己的思路来讲这道题了。

考试的时候思路很清晰,抓住答案的那个式子就开始一波推导,然后就做出来了(当时我还不是特别相信)。

[Solution]

我们定义 r[i] 表示第 i 行在操作后变为原来的多少倍,c[i] 对于第 i 列同理。

可以知道第 $i$ 行第 $j$ 列的数字为 $\big[(i-1)M+j\big]$ 。然后第 $i$ 行所有数字之和用一个等差数列求和就好了,记作 s[i]

如果只考虑行上的翻倍(即只考虑 r[i]),则答案为:

但是现在列上有翻倍,考虑先把每一行的翻倍做完,然后做第 $i$ 行第 $j$ 列的翻倍,第 i 行第 j 列的数字会增加 (c[j]-1) 倍,即该数字会对答案造成额外的 r[i]*(c[j]-1) 倍的贡献,即答案为:

Tab. a[i][j] 是原方阵 i 行 j 列的数字;则 a[i][j]=(i-1)*M+j

开始化简:

得到了上面的式子:令 $A=\sum_{j-1}^M(c_j-1)j$ ;$B=\sum_{j=1}^M(c_j-1)$ ,则:

观察 $A,B$ 的式子,显然我们可以预先算出 $A,B$。

[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
/*Lucky_Glass*/
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int NM=1e6;
const ll MOD=ll(1e9)+7;

ll Rol[NM+3],Col[NM+3];
int n,m,q,x,y;
ll T1,T2;
char opr;
int QRead(){
int ret=0;char ch=getchar();
while(ch<'0' || '9'<ch) ch=getchar();
while('0'<=ch && ch<='9')
ret=(ret<<1)+(ret<<3)+ch-'0',
ch=getchar();
return ret;
}
ll QPow(ll cura,ll curb){
ll ret=1;
while(curb){
if(curb&1) ret=ret*cura%MOD;
cura=cura*cura%MOD;
curb>>=1;
}
return ret;
}
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
n=QRead();m=QRead();q=QRead();
for(int i=1;i<=n;i++) Rol[i]=1;
for(int i=1;i<=m;i++) Col[i]=1;
for(int i=1;i<=q;i++){
opr=getchar();
while(opr!='S' && opr!='R') opr=getchar();
x=QRead();y=QRead();
if(opr=='R') Rol[x]=Rol[x]*y%MOD;
else Col[x]=Col[x]*y%MOD;
}
for(int j=1;j<=m;j++)
T1=(T1+j*Col[j]-j+MOD)%MOD,
T2=(T2+Col[j]-1+MOD)%MOD;
ll ans=0;
ll inv2=QPow(2ll,MOD-2);
for(int i=1;i<=n;i++){
ans=(ans+((1ll*(2*i-1)*m+1)%MOD*m%MOD*inv2%MOD*Rol[i]%MOD
+Rol[i]*m%MOD*(i-1)%MOD*T2%MOD
+Rol[i]*T1%MOD))%MOD;
}
printf("%lld\n",ans);
return 0;
}

- T2. 跳房子 (jump)

[Experience]

发现这道题每一次询问时,跳的步数很大,可到 $10^9$,但是它 $\log$ 一下不过 $32$ ……于是就开始想倍增……

然后发现带修改,于是就是一个带修的倍增,即动态倍增(受之前的试题中有一道正解就是动态倍增的影响,我就想试一试)。众所周知更新倍增数组时不能修改一次就全部更新,我也知道……但是不知道该怎么写,好像有一个剪枝条件写错了 QwQ ,导致每修改一次就会更新许多倍增数组,然后 TLE 飞了……

还不如老老实实写暴力……

[Solution]

正解其实是分块啦~

我们定义 go[i] 表示从第 i 行第一列出发走 M 步(也就是刚好回到第一列),能够到达第 go[i] 行第 1 列。

显然如果移动的步数足够大,就会形成一个循环。我们考虑利用 go[i] 找到从第 i 列第 1 行出发能够找到的循环,时间复杂度为 $O(N)$;

把一次移动(询问)考虑成以下几步:

  1. 如果当前节点不在第一列,就暴力模拟移动到第一列,复杂度 $O(N)$;
  2. 从当前位置找到循环,并走到该循环的起点($O(N)$);
  3. 一直沿着该循环走(不需要模拟,直接步数取模循环的长度即可),$O(1)$;
  4. 如果当前剩余步数不小于 $M$,则利用 go[] 一次走 $M$ 步,由于已经走完了循环,走 $M$ 步的次数小于 $N$(因为循环的长度最大 $N\times M$,则剩余步数小于 $N\times M$),$O(N)$;
  5. 如果还有剩余步数,则剩余步数小于 $M$,暴力走完剩下的步数,$O(N)$;

所以总时间复杂度 $\require{cancel}\enclose{horizontalstrike}{O(\text{玄学})}$ $O(N)$。

以上是询问;然后是修改。

我们实际上只需要修改 go[] (移动时需要更新的就是 go)。首先我们知道如果格点 (x,y1)(x,y2) 移动若干步都经过 格点t ,则 y1,y2 之间的所有格点也会经过 t。(即每一个格点影响纵向连续的一段格点)

考虑修改后要更新格点 (xt,yt)go[] 的影响,分为以下几步:

  1. t 出发走到第一列,记当前所在行为 第 s 行;

  2. 写个伪代码方便理解:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    int y1,y2;//表示 y1 到 y2 的连续一段格点都会经过 (xt,yt)
    for i = (xt-1 -> 1){
    bool faily1=false,faily2=false;
    //要让 y1 尽可能小
    if(i,y1-1) 会经过 (i+1,y1) y1=y1-1;
    else if (i,y1) 会经过 (i+1,y1) y1=y1;
    else if (i,y1+1) 会经过 (i+1,y1) y1=y1+1;
    else faily1=true;
    //要让 y2 尽可能大
    //更新 y2 与 y1 同理
    if faily1
    if (i+1,y1+1)<(i+1,y1-1) //如果满足该条件,(i,y1)仍会经过 (xt,yt)
    y1=y1;
    else
    y1=y1-1;
    //更新 y2 同理
    }
    for i = (y1 -> y2)
    go[i] = s

以上就是更新一个节点的影响。

不难发现,修改格点 (xt,yt) 后,只有 (xt-1,yt-1),(xt-1,yt),(xt-1,yt+1) 会受影响。所以只要更新这几个格点即可。

这道题的细节很多,不建议写……

Warning:又长又丑的代码即将出现

[Source]

【抄代码你也不一定能一遍AC……点击展开/折叠代码
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2000;
int rol,col,qry;
int num[N+3][N+3];
int go[N+3];
int lascntt[N+3];
int vis[N+3],visid;
void CorX(int &x){
if(x<1) x=x%rol+rol;
if(x>rol) x=x%rol==0? rol:x%rol;
}
int main(){
freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
scanf("%d%d",&rol,&col);
for(int i=1;i<=rol;i++)
for(int j=1;j<=col;j++)
scanf("%d",&num[i][j]);
for(int i=1;i<=rol;i++){
int i_=i;
for(int j=1;j<=col;j++){
int i1=i_+1,i2=i_,i3=i_-1,j_=j+1;
CorX(i1);CorX(i2);CorX(i3);
if(j_==col+1) j_=1;
if(num[i1][j_]>num[i2][j_] && num[i1][j_]>num[i3][j_]) i_=i1;
if(num[i2][j_]>num[i1][j_] && num[i2][j_]>num[i3][j_]) i_=i2;
if(num[i3][j_]>num[i2][j_] && num[i3][j_]>num[i1][j_]) i_=i3;
}
go[i]=i_;
}
scanf("%d",&qry);
int px=1,py=1;
while(qry--){
char opr[10]={};
scanf("%s",opr);
if(opr[0]=='m'){
int inp;scanf("%d",&inp);
while(inp && py!=1){
int x1=px-1,x2=px,x3=px+1,y_=py+1;
CorX(x1);CorX(x2);CorX(x3);
if(y_>col) y_=1;
if(num[x1][y_]>num[x2][y_] && num[x1][y_]>num[x3][y_]) px=x1;
if(num[x2][y_]>num[x1][y_] && num[x2][y_]>num[x3][y_]) px=x2;
if(num[x3][y_]>num[x1][y_] && num[x3][y_]>num[x2][y_]) px=x3;
py=y_;
inp--;
}
int cntt=0,row=0;
visid++;
while(inp>=col){
if(vis[px]==visid){
row=cntt-lascntt[px];
break;
}
lascntt[px]=cntt;
cntt+=col;
inp-=col;
vis[px]=visid;
px=go[px];
}
if(row) inp%=row;
while(inp>=col){
inp-=col;
px=go[px];
}
while(inp){
int x1=px-1,x2=px,x3=px+1,y_=py+1;
CorX(x1);CorX(x2);CorX(x3);
if(y_>col) y_=1;
if(num[x1][y_]>num[x2][y_] && num[x1][y_]>num[x3][y_]) px=x1;
if(num[x2][y_]>num[x1][y_] && num[x2][y_]>num[x3][y_]) px=x2;
if(num[x3][y_]>num[x1][y_] && num[x3][y_]>num[x2][y_]) px=x3;
py=y_;
inp--;
}
printf("%d %d\n",px,py);
}
else{
int ix,iy,iv;
scanf("%d%d%d",&ix,&iy,&iv);
if(num[ix][iy]==iv) continue;
num[ix][iy]=iv;
for(int uuu=-1;uuu<=1;uuu++){
int fy=iy-1,celx=ix+uuu,flrx=ix+uuu;
if(fy<1) fy=col;
bool fail=false;
for(int x1,x2,x3;(fy!=1)&&!fail;fy=fy==1? col:fy-1){
bool ifcel=false;
x1=celx-2;x2=celx-1;x3=celx;
CorX(x1);CorX(x2);CorX(x3);
if(num[x3][fy]>num[x2][fy] && num[x3][fy]>num[x1][fy])
if(!ifcel){
celx=celx-1;
ifcel=true;
}
x1=celx-1;x2=celx;x3=celx+1;
CorX(x1);CorX(x2);CorX(x3);
if(num[x2][fy]>num[x1][fy] && num[x2][fy]>num[x3][fy])
if(!ifcel){
celx=celx;
ifcel=true;
}
x1=celx;x2=celx+1;x3=celx+2;
CorX(x1);CorX(x2);CorX(x3);
if(num[x1][fy]>num[x2][fy] && num[x1][fy]>num[x3][fy])
if(!ifcel){
celx=celx+1;
ifcel=true;
}
bool ifflr=false;
x1=flrx+2;x2=flrx+1;x3=flrx;
CorX(x1);CorX(x2);CorX(x3);
if(num[x3][fy]>num[x2][fy] && num[x3][fy]>num[x1][fy])
if(!ifflr){
flrx=flrx+1;
ifflr=true;
}
x1=flrx+1;x2=flrx;x3=flrx-1;
CorX(x1);CorX(x2);CorX(x3);
if(num[x2][fy]>num[x1][fy] && num[x2][fy]>num[x3][fy])
if(!ifflr){
flrx=flrx;
ifflr=true;
}
x1=flrx;x2=flrx-1;x3=flrx-2;
CorX(x1);CorX(x2);CorX(x3);
if(num[x1][fy]>num[x2][fy] && num[x1][fy]>num[x3][fy])
if(!ifflr){
flrx=flrx-1;
ifflr=true;
}
if(!ifcel){
x1=celx+1;x2=celx;x3=celx-1;
CorX(x1);CorX(x2);CorX(x3);
if(num[x3][fy]>num[x1][fy]) celx=celx+1;
else celx=celx;
}
if(!ifflr){
x1=flrx+1;x2=flrx;x3=flrx-1;
CorX(x1);CorX(x2);CorX(x3);
if(num[x1][fy]>num[x3][fy]) flrx=flrx-1;
else flrx=flrx;
}
if(celx>flrx)
fail=true;
}
if(fail) continue;
int hx=ix+uuu,hy=iy-1;
if(hy<1) hy=col;
for(;hy<=col;hy++){
int _hy=hy+1;
if(_hy>col) _hy=1;
int x1=hx+1,x2=hx,x3=hx-1;
CorX(x1);CorX(x2);CorX(x3);
if(num[x1][_hy]>num[x2][_hy] && num[x1][_hy]>num[x3][_hy]) hx=x1;
if(num[x2][_hy]>num[x1][_hy] && num[x2][_hy]>num[x3][_hy]) hx=x2;
if(num[x3][_hy]>num[x2][_hy] && num[x3][_hy]>num[x1][_hy]) hx=x3;
}
for(int i=celx;i<=flrx;i++){
int III=i;
CorX(III);
go[III]=hx;
}
}
}
}
return 0;
}

- T3. 优美序列 (sequence)

这是一道好题!好题!

建议各位 reader 们可以自己写一下!

[Experience]

考场上炸鱼,什么思路都没有……

赛后某神仙 ST表 卡常碾标算,然后另一个线段树小王子用另一种时间复杂度很OK的算法再一次吊打标算 awa

仍然是

My Vegetable has Explosed.

[Solution]

那个卡常神仙就不说了……

讲一下线段树的做法(其实是我不会正解分治)

这个做法最重要的是定义的一个函数 num(i,j) 表示数列中第 i 个到第 j 个的数字中存在 num(i,j) 对数对 <x,y> 满足 x+1=y 。根据这个定义,我们可以得出如果 [l,r] 是优美序列,则 l+num(l,r)=r ,即 [l,r] 内恰好有 r-l<x,y> 满足 x+1=y

有一个结论不难发现:对于任意一个序列 [l,r],满足 l+num(l,r)≤r

那么对于一个 r,以 r 为右端点的优美序列即找到一个左端点 l 满足 l+num(l,r)=r ,又因为对于任意 l 满足 l+num(l,r)≤r ,所以就相当于找 l+num(l,r) 的最大值。

然后 l+num(l,r) 就是用线段树来维护的,下面讲具体做法。

设原序列的第 i 个位置为 a[i],数字 i 在原数列的第 pos[i] 个位置。

离线处理询问,从左到右枚举答案的右端点 R,若询问 [l,r] 的右端点 r 小于等于 R ,就把询问插入一个优先队列中,表示要处理的询问(优先队列内按询问左端点从大到小排序)。

考虑把 R 向右移动一个,并把新加入的数字 a[R] 加入线段树,如果 数字 a[R]-1 存在且 pos[a[R]-1] 在 R 左边,则把线段树内的 [1,pos[a[R]-1]] 这段区间 +1,表示只要左端点选在 [1,pos[a[R]-1]] 内,数对 <a[R]-1,a[R]> 就会对 num(l,r) 产生 1 的贡献;对于 数字 a[R]+1 作相同处理。

最后对于每个询问 [li,ri],查询线段树内 [1,li] 中尽可能靠右的最大值,如果该最大值为 R,则存在解。

[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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5;

struct QUERY{int lef,rig,id;}qry[N+3];
bool operator <(const QUERY cpr1,const QUERY cpr2){return cpr1.lef<cpr2.lef;}
bool cmpQUERY(const QUERY cpr1,const QUERY cpr2){return cpr1.rig<cpr2.rig;}

struct SEGTREE{
pair<int,int> mx[N*6+3];
int add[N*6+3];
void PushUp(int u){
mx[u]=max(mx[u<<1],mx[u<<1|1]);
}
void PushDown(int u){
if(add[u]){
add[u<<1]+=add[u];mx[u<<1].first+=add[u];
add[u<<1|1]+=add[u];mx[u<<1|1].first+=add[u];
add[u]=0;
}
}
void Build(int u,int lef,int rig){
add[u]=0;
if(lef==rig){mx[u]=make_pair(lef,lef);return;}
int mid=(lef+rig)>>1;
Build(u<<1,lef,mid);Build(u<<1|1,mid+1,rig);
PushUp(u);
}
void Modify(int u,int lef,int rig,int L,int R,int val){
if(R<lef || rig<L) return;
if(L<=lef && rig<=R){
add[u]+=val;
mx[u].first+=val;
return;
}
PushDown(u);
int mid=(lef+rig)>>1;
Modify(u<<1,lef,mid,L,R,val);
Modify(u<<1|1,mid+1,rig,L,R,val);
PushUp(u);
}
pair<int,int> Query(int u,int lef,int rig,int L,int R){
if(L<=lef && rig<=R) return mx[u];
if(R<lef || rig<L) return make_pair(-1,-1);
PushDown(u);
int mid=(lef+rig)>>1;
return max(Query(u<<1,lef,mid,L,R),Query(u<<1|1,mid+1,rig,L,R));
}
}seg;

int num[N+3],pos[N+3],ans[N+3][2]; //pos[num[i]]=i
int n,m;
priority_queue< QUERY > que;

int main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]),
pos[num[i]]=i;
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&qry[i].lef,&qry[i].rig),
qry[i].id=i;
sort(qry+1,qry+m+1,cmpQUERY);
int tmp=1;
seg.Build(1,1,n);
for(int ar=1;ar<=n;ar++){
while(tmp<=m && qry[tmp].rig==ar)
que.push(qry[tmp++]);
if(num[ar]!=1 && pos[num[ar]-1]<ar) seg.Modify(1,1,n,1,pos[num[ar]-1],1);
if(num[ar]!=n && pos[num[ar]+1]<ar) seg.Modify(1,1,n,1,pos[num[ar]+1],1);
int al=(1<<29);
while(!que.empty()){
QUERY now=que.top();
if(al<=now.lef){ //如果上一个最短优美区间也是当前询问的答案,则当前询问的答案一定是该区间
ans[now.id][0]=al;ans[now.id][1]=ar;
que.pop();
continue;
}
pair<int,int> res=seg.Query(1,1,n,1,now.lef);
if(res.first==ar){
al=res.second;
ans[now.id][0]=al;ans[now.id][1]=ar;
que.pop();
}
else
break; //如果找不到优美区间,则之后的询问也不会找到
}
}
for(int i=1;i<=m;i++)
printf("%d %d\n",ans[i][0],ans[i][1]);
return 0;
}

The End

Thanks for reading!

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

0%