游记&OI - 广州纪中游记 Day9 | Lucky_Glass's Blog

以心为名，名为爱惜

0%

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

发表于 更新于 分类于 Valine：

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

<题面链接> 提取码：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，要满足 rt 与 root 的 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，欢迎提问！