游记&OI - 广州纪中游记 Day9

虽然说有一道签到题没想到正解,但是我还是觉得这是我这几天以来打的最棒的模拟赛 ヾ(・ω・`。)

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


Part1. 游记

这篇 blog 仍然是 Day11 的晚上补的……不过还没过多久,应该不会忘……

这场模拟赛打的得心应手(???),拿到了自己估计的分数~顺便冲了一下排行榜~

出题人比较友好,给我们留了快乐的一天!

反正题目很简单,不需要多少时间去改正,所以就叫上几个同学去打 ping-pong φ(≧ω≦*)♪

虽然乒乓拍特别差(无摩擦无弹性无拉力简称三无),但是仍然玩的非常开心,只是乒乓球馆没有空调,打完出了一身汗,回机房吹空调遇冷差点感冒……


Part2. Solution

写这个题解就很愉悦了~

T1. 走格子(cell)

[Experience]

没 get 到这道题的难点,感觉做题的时候顺理成章的就发现这题是最短路……

[Solution]

既然说了是最短路,就看怎么建图了,首先一个格点向它四周的格点连一条长度为 1 的边,很好理解。

然后就考虑传送门操作了!

考虑对于一个格点,从它出发向两个不同方向发射传送门——那么最优方案一定是向离当前格点最近的墙(同行或者同列)发射一个传送门,再向另外一面墙发射传送门,那么从当前节点到达最近的墙的方案即直接走过去,而到达另外3面墙是先走到最近的墙,然后从传送门到达

先处理出每个格点上下左右分别离它最近的墙的距离。记上下左右四面墙中距离最近为 MinWal,则对于上下左右离当前格点最近的墙,连一条值为 MinWal 的边,其余连值为 MinWal+1 的边。

跑最短路,单源单汇,堆优化 Dijkstra、SPFA 都可以。

良心出题人不卡SPFA

Q:这个数据不会卡掉程序吗?

1
2
3
4
5
6
7
8
9
10
11
12
#########
####.####
#.......#
#....C..#
#.......#
####.####
####.####
####F####
#########

应该先往下打一个传送门;再向左走一步,向下打一个传送门;向右走一步;向下走一步;进入传送门;
总共4步

A:不会,程序会找到另一种路径:向左走,向下走,向下走,向下打传送门、向左打传送门,进入传送门……

而且你发现没有数据能够卡掉它……

[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<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=500;
const int DIR[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
int rol,col,Sx,Sy,Tx,Ty;
char maz[N+3][N+3];
int wal[N+3][N+3][4],dis[N+3][N+3];
bool vis[N+3][N+3];

struct QN{
int x,y,far;
QN(){}
QN(int _x,int _y,int _f):x(_x),y(_y),far(_f){}
};
bool operator <(const QN cura,const QN curb){
return cura.far>curb.far;
}

//lef,rig,up,down
int main(){
freopen("cell.in","r",stdin);
freopen("cell.out","w",stdout);
scanf("%d%d",&rol,&col);
for(int i=1;i<=rol;i++){
scanf("%s",maz[i]+1);
for(int j=1;j<=col;j++){
if(maz[i][j]=='C') Sx=i,Sy=j;
if(maz[i][j]=='F') Tx=i,Ty=j;
}
}
for(int i=2;i<rol;i++){
for(int j=2;j<col;j++)
if(maz[i][j-1]=='#') wal[i][j][0]=0;
else wal[i][j][0]=wal[i][j-1][0]+1;
for(int j=col-1;j>=2;j--)
if(maz[i][j+1]=='#') wal[i][j][1]=0;
else wal[i][j][1]=wal[i][j+1][1]+1;
}
for(int j=2;j<col;j++){
for(int i=2;i<rol;i++)
if(maz[i-1][j]=='#') wal[i][j][2]=0;
else wal[i][j][2]=wal[i-1][j][2]+1;
for(int i=rol-1;i>=2;i--)
if(maz[i+1][j]=='#') wal[i][j][3]=0;
else wal[i][j][3]=wal[i+1][j][3]+1;
}
memset(dis,0x3f,sizeof dis);
dis[Sx][Sy]=0;
priority_queue< QN > que;
que.push(QN(Sx,Sy,dis[Sx][Sy]));
for(int h=1;!que.empty() && h<rol*col;h++){
QN u=que.top();que.pop();
if(vis[u.x][u.y]) continue;
vis[u.x][u.y]=true;
int MinWal=(1<<29);
for(int i=0;i<4;i++) MinWal=min(MinWal,wal[u.x][u.y][i]);
QN v;
for(int i=0;i<4;i++){
v=QN(u.x+DIR[i][0],u.y+DIR[i][1],u.far+1);
if(maz[v.x][v.y]=='#' || dis[v.x][v.y]<=v.far) continue;
dis[v.x][v.y]=v.far;
que.push(v);
}
for(int i=0;i<4;i++){
v=QN(u.x+DIR[i][0]*wal[u.x][u.y][i],u.y+DIR[i][1]*wal[u.x][u.y][i],u.far+MinWal+1);
if(wal[u.x][u.y][i]==MinWal) v.far--;
if(maz[v.x][v.y]=='#' || dis[v.x][v.y]<=v.far) continue;
dis[v.x][v.y]=v.far;
que.push(v);
}
}
if(vis[Tx][Ty]) printf("%d\n",dis[Tx][Ty]);
else printf("no\n");
return 0;
}

T2. 扭动的树 (tree)

[Experience]

用一个奇妙的思路想到了 60 分做法……

感觉非常顺利,不过确实没有想到满分做法。

[Solution]

=P1. 让我们看看这道题为什么是区间DP

考虑把一个 key 值有序的序列建成一棵二叉查找树,我们可以把序列中的一个数提起来当做根节点,然后原序列就被分成了左右两个子序列,再从这两个子序列中提起一个数当左右子树的根……直到做完所有序列。

其实也就是二叉查找树的性质:

一棵子树内的所有点的键值 key 是连续的

所以我们可以想到一个状态定义:f[l][r][i] 表示将所有点按 key 排序后,区间 [l,r] 中把 i 提起来作为根的最大 sum 之和。

=P2. 那个60分

按照上面的状态定义,我们先枚举整棵二叉查找树的根 rt,然后记忆化搜索 DP(1,n,rt)

在记忆化搜索 DP(l,r,root) 中:root 把 [l,r] 分成左右两个子区间;特别的,root=r 时,只有左区间,root=l 时,只有右区间。

显然左右区间是互不影响的,可以分别求出左右区间的最大值,然后求和。

拿左区间举例,先枚举左区间的根节点 rt,要满足 rtroot 的 key 互质。然后递归 DP(l,root-1,rt) 即可。

(右区间同理~)

总复杂度 $O(N^4)$ 。

= P3. 满分怎么改

我们发现除了区间 [1,n]其他区间 [l,r] 要么是 l-1 的右区间,要么是 r+1 的左区间

于是可以定义 f[l][r][0/1] ,0表示 [l,r] 作为 r+1 的右区间,1表示 [l,r] 作为 l-1 的左区间。

一开始枚举整个区间的根节点 root,,分成 DP(1,root-1,1),DP(root+1,n,0) 求解,即 [1,root-1] 是 root 的左区间,[root+1,n] 是 root 的右区间。

之后对于每个子区间都像上面说的这样递归就可以了。注意有一些状态是不存在合法方案的,这种状态要打上标记,还要注意打的标记一定是不同于“未计算”、“存在合法方案”的值。(比如存在合法方案,值为正数;未计算值为-1,不合法值为-2)

时间复杂度 $O(N^3)$ - Accepted

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

typedef long long ll;
const int N=300;

struct NODE{ll key,val;}nod[N+3];
bool cmpNODE(const NODE cpr1,const NODE cpr2){
return cpr1.key<cpr2.key;
}

int n;
ll sum[N+3],f[N+3][N+3][2];
bool abl[N+3][N+3];

ll GCD(ll A,ll B){return A? GCD(B%A,A):B;}
ll DP(int l,int r,int tmp){
if(f[l][r][tmp]!=-1) return f[l][r][tmp];
if(l==r){
if(tmp) return f[l][r][tmp]=abl[l][l+1]? nod[l].val:-233;
else return f[l][r][tmp]=abl[l][l-1]? nod[l].val:-233;
}
ll &ret=f[l][r][tmp];
ret=-233ll;
for(int i=l;i<=r;i++){
if(!abl[i][tmp? r+1:l-1]) continue;
ll resL,resR;
if(i==l){
resR=DP(l+1,r,0);
if(resR!=-233)
ret=max(ret,resR+sum[r]-sum[l-1]);
}
else if(i==n){
resL=DP(l,r-1,1);
if(resL!=-233)
ret=max(ret,resL+sum[r]-sum[l-1]);
}
else{
resL=DP(l,i-1,1);resR=DP(i+1,r,0);
if(resL!=-233 && resR!=-233)
ret=max(ret,resL+resR+sum[r]-sum[l-1]);
}
}
return ret;
}
int main(){
memset(f,-1,sizeof f);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&nod[i].key,&nod[i].val);
sort(nod+1,nod+1+n,cmpNODE);
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+nod[i].val;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(GCD(nod[i].key,nod[j].key)!=1)
abl[i][j]=abl[j][i]=true;
ll ans=-233;
for(int i=1;i<=n;i++){
ll resL,resR;
if(i==1){
resR=DP(2,n,0);
if(resR!=-233) ans=max(ans,resR+sum[n]);
}
else if(i==n){
resL=DP(1,n-1,1);
if(resL!=-233) ans=max(ans,resL+sum[n]);
}
else{
resL=DP(1,i-1,1);resR=DP(i+1,n,0);
if(resL!=-233 && resR!=-233)
ans=max(ans,resL+resR+sum[n]);
}
}
printf("%lld\n",ans);
return 0;
}

T3. 旋转子段(rotate)

签到题没做出来系列……

[Experience]

把第一题正解写了,再写了第二题的骗分,第三题就没什么时间想了……

而且我以为第三题应该是最难的(因为第一题能 AC,第二题只能骗分,那么第三题……)然后就把这道签到题的分扔了……

[Solution]

pos[i] 表示 i 的位置、num[i] 表示位置 i 上的数字。

首先有一个贪心的结论:

最优方案下,选择旋转的区间的左右端点 l,r 在旋转后,一定会形成不动点。(要么 l 上的数字旋转到 r 形成不动点,要么 r 上的数字旋转到 l 形成不动点,或者两个同时满足)

否则我们可以把区间缩小,使得区间内翻转后不动点的个数不变,但是缩小后区间外的点可能原来就是不动点,就会产生额外贡献。

于是,如果我们确定了右端点 R,只存在两种可能的左端点 L

  1. L=num[R] ,则 num[R] 旋转到 R 时会产生不动点;
  2. L=pos[R],则 num[L]=R ,当 num[L] 旋转到 R 时会产生不动点;

cnt[mid] 表示在已经找到的区间中,中点为 mid 的区间的个数

我们从左往右枚举右端点 R ,找到对应的两种可能的左端点 L。对于区间 [L,R] ,我们找到它的中点 mid,使 cnt[mid]++。不难发现此时的 cnt[mid] 就是区间 [L,R] 内不动点的个数,所以把 cnt[mid] 加上区间外不动点的个数就可以了。

至于区间外不动点的个数,前缀和就好了~

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

const int N=100000;

int n,m,ans;
int num[N+5],cnt[N+5],tot[2*N+5],pos[N+3];

int main(){
freopen("rotate.in","r",stdin);
freopen("rotate.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]),
pos[num[i]]=i;
for(int i=1;i<=n;i++) cnt[i]=cnt[i-1]+(num[i]==i);
for(int i=1;i<=n;i++){
int r=i,l=num[i];
if(l<=r){
int mid=l+r;
tot[mid]++;
ans=max(ans,tot[mid]+cnt[l-1]+cnt[n]-cnt[r]);
}
r=i;l=pos[i];
if(pos[num[i]]==num[i]) continue;
if(l<=r){
int mid=l+r;
tot[mid]++;
ans=max(ans,tot[mid]+cnt[l-1]+cnt[n]-cnt[r]);
}
}
printf("%d\n",ans);
return 0;
}

The End

Thanks for reading!

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

0%