纪中游记

发表于 | 更新于 | 分类于 | 阅读次数：

全部再来一遍。

いいよ。

Day0 2019.7.31

苍生啊，你们肃然倒地了吗?宇宙啊，你感悟到那创造者了吗？

火车上干了不少事情。

  • 看了大部分的《悲剧的诞生》
    打了斗地主
    出了塞妈

总体来说收获挺大。

中山纪念中学真的很漂亮，如S所说有山有水，还有游泳池体育馆，总体来说吊打外高了。占地面积挺大的，拍了不少照片，找时间补上。（回家同步到github上时贴图床好了）。晚上试了机，尝试打了这道题,然而并没有打过。

IMG_20190731_163054.jpg

IMG_20190731_163059.jpg

晚餐前充饭卡顺便看了一下社团的海报们。

IMG_20190731_161359.jpg

IMG_20190731_161418.jpg

回去睡觉了。宿舍环境一般，没有插头，没有开水泡面，但是一堆人在一起还挺有氛围的。（指cyx的夜谈)

晚上洗的澡，本以为宿管10点半左右来查寝。结果11点半他拿着发光体走进来瞪着我看他。

Day1 2019.8.1

明明只是活在这个世界上，痛苦和悲伤却不断涌来。

早餐面包豆浆。感觉一点都不配所以去壹加壹买了瓶牛奶。

早上模拟赛变成挂题赛了。。。

T1 Game

博弈论裸题，二维前缀和维护01串，递推得答案。考虑4种情况，打胜负标记，并且判断是否可取（当前行/列和是否为偶数）。

具体的思路是这样:

  • 目前状态的上方和左方如果都是必胜tag， 那么先手必负。
  • 目前状态的上方和左方只有一个为必胜tag，那么先手必胜。
  • 目前状态的上方和左方没有必胜tag，那么先手必胜。

这上面的先决条件是当前列（上方）/当前行（左方）和为偶数。

所以就可以在$O(N^2)$的时间复杂度内完成了。

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

const int MAXN = 1005;

int f[MAXN][MAXN];
bool tag[MAXN][MAXN];
int sum[MAXN][MAXN];
void _Init()
{
	memset(f, 0, sizeof(f));
	memset(tag, 0, sizeof(tag));
	memset(sum, 0, sizeof(sum));
}
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		_Init();
		int N;
		scanf("%d", &N);
		for(int i = 1; i <= N; i++)
		{
			for(int j = 1; j <= N; j++)
			{
				scanf("%d", &f[i][j]);
				sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + f[i][j];
			}
		}
		tag[1][1] = f[1][1] % 2;
		for(int i = 1; i <= N; i++)
		{
			for(int j = 1; j <= N; j++)
			{
				if(tag[i][j - 1] && tag[i - 1][j])
				{
					continue;
				}
				else if(tag[i][j-1]&&!tag[i-1][j])
				{
					if((sum[i][j]-sum[i-1][j])%2==0)
					{
						tag[i][j]=1;
					}
				}
				else if(tag[i-1][j]&&!tag[i][j-1])
				{
					if((sum[i][j]-sum[i][j-1])%2==0)
					{
						tag[i][j]=1;
					}
				}
				else if(!tag[i-1][j]&&!tag[i][j-1])
				{
					if((sum[i][j]-sum[i][j-1])%2==0||(sum[i][j]-sum[i-1][j])%2==0)
					{
						tag[i][j]=1;
					}
				}
			}
		}
		if(tag[N][N])
		{
			printf("W\n");
		}
		else
		{
			printf("L\n");
		}
	}	
	return 0;
}

T2 hexagon

正解是转六边形为矩形大模拟，考场上手推了一些关系，基本上过了1000的数据。但是交成打表程序了…

以下是Ted的代码，我等休息日再调。

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
#include <cstdio>
#include <iostream>
#include <cmath>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10100;
int t,n;
int ans[N]={1,2,3,4,5,2,3};
struct data{
	int col,t;
	bool operator < (const data & p) const {
		return this->t==p.t ? this->col < p.col : this->t < p.t;
	}
}datas[10];
void init(){
	for(int i=1; i<=5; i++){
		datas[i].col=i;
	}
	datas[1].t=1;
	datas[2].t=2;
	datas[3].t=2;
	datas[4].t=1;
	datas[5].t=1;
	int  cir=2,num=0,cnt=0,tot=6;//tot表示上一圈最后一个的位置 
	bool blk[6];
	for(int i=7; i<=10005; i++){
		memset(blk, 0, sizeof blk); //清空数组 blk表示与该点冲突 
		sort(datas+1,datas+6);  //按照题目要求sort 
		num=i-tot;  //num 表示是该圈第num个 
		
		/*以下是求与内圈冲突的*/ 
		if(num%cir==0){ //如果在6个特殊位置 
			int id=num/cir; //判断在第几个特殊位置 
			blk[ans[tot-(cir-1)*6+(cir-1)*id]]=1;
		}
		else{
			cnt++;
			if(cnt==1){	
				blk[ans[tot]]=1;
				blk[ans[tot-(cir-1)*6+1]]=1;
			}
			else{
				blk[ans[tot-(cir-1)*6+cnt]]=1;
				blk[ans[tot-(cir-1)*6+cnt-1]]=1;
			}
		}
		/**********************/
		
		if(i==tot+6*cir){
			blk[ans[tot+1]]=1;
			tot=tot+6*cir;
			cir++;
			cnt=0;
		}
		
		else if (i!=tot+1){
			blk[ans[i-1]]=1;
		}
		for(int j=1; j<=5; j++){
			int col=datas[j].col;
			if(!blk[col]){
				datas[j].t++;
				ans[i]=col;
				break;
			}
		}
		continue;
	}
}
int main(){
	scanf("%d",&t);
	init();
	while(t--){
		scanf("%d",&n);
		printf("%d\n",ans[n-1]);
	}
	return 0;
}

T3 Query

送分题。$O(N)$统计取模余数，最后$O(K)$排列组合求每一对模数对答案的贡献，贡献是$a[i]*(a[i]-1)/2$，也就是区间的个数。

别的学校的同学提供了$O(N\log N)$的分治算法，就是从中间分开，左边取模放进桶内，右边取模放进桶内，然后ans加上贡献为$L_0R_0+\sum_{k=1}^{N-1}L_kR_{N-k}$。

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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=2100005;
int a,sum,book[MAXN];
void _Init()
{
	memset(book,0,sizeof(book));
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		_Init();
		sum=0;
		int N,K;
		int OUT=0;
		scanf("%d%d",&K,&N);
		for(int i=1;i<=N;i++)
		{
			scanf("%d",&a);
			a%=K;
			sum+=a;
			sum%=K;
			book[sum]++;
		}
        for(int i=0;i<=K-1;i++)
        {
            OUT+=(book[i]*(book[i]-1))>>1;
        }
		printf("%d\n",OUT+book[0]);
	}
	return 0;
}

中餐是辣子鸡（没吃出来）和清炒椰菜（包菜）。还是锟斤拷好吃。

IMG_20190801_071644.jpg

纪中小卖部好大好棒啊。

讲课是几个同学轮流上去讲，总体来说风趣有活力。

这次考试就我最菜石锤了。

然后回来按要求完成xc所说的五个阶段

XC五大阶段

1 做模拟赛

2 听课做笔记

3 写小结

4 改题

5 写博客

然而，我直接去做题了。历经13次提交，终于A了昨晚那道题。

晚饭有好多梗（盐局鸡?）,其实伙食还是很不错的。

IMG_20190801_171820.jpg

这个茄子我笑一年。

晚上复习了一下珂朵莉树，然后滚回寝室睡觉了。

Day 2 2019.8.2

不必太纠结于当下，也不必太忧虑未来

当你经历过一些事情的时候

眼前的风景已经和从前不一样了

早餐面包牛奶，实际菜单比昨天多很多，但起的太晚什么都没买到。

早上模拟赛看起来好简单？（然而只有200分）

解题顺序:T1-T2-T3-T4

午餐很好啊。肉沫豆腐加蒸肉饼（看起来略微反胃但味道却出人意料）。纪中真的好棒啊，不愧是kfdong大爷待过的学校。我也想来

T1 Meal

送分题，N<10，直接DFS爆搜就可以了。坑点大概是必须要有原料。

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
#include <cstdio>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN=15;
int N,a[MAXN],b[MAXN],tema=1,temb;
int ans=INF;
int book=0;
void DFS(int now,int state)
{
	if(state)
	{
		tema*=a[now];
		temb+=b[now];
		book++;
	}
	if(now==N)
	{
		if(book)
		{
			ans=min(ans,abs(tema-temb));
		}
		return;
	}
	DFS(now+1,0);
	DFS(now+1,1);
	tema/=a[now+1];
	temb-=b[now+1];
	book--;
}

int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
	}
	DFS(0,0);
	printf("%d",ans);
	return 0;
}

T2 Game

破环为链的博弈论DP。状态定义很有意思。考场上写的错解（我感觉和正解沾不上边的方法）得了30。可见数据的水分。

我们定义$f[i][j]$为区间$i,j$中的奇数个数，定义$dp[i][j]$为区间$i j$中先手选到奇数最多个数，所以可以得到转移方程

$$ dp[i][j]=f[i][j]-min(dp[i+1][j],dp[i][j-1] )$$

我们来看上式，区间$i,j$先手可以得到最多奇数个数就是$i,j$中的奇数个数减去上一步（后手时）的最多个数。

既然我们现在的区间是$i,j$也就说明上一步应该是在$i$的右边或者是$j$的左边。
在这里面取小值就行了。

然后枚举第一次取得数，如果先手分数大于后手分数就ans++。

其他的操作

  • 破环为链
    每次清空dp数组
    注意$i $ 和  $j$的遍历顺序，防止遍历到没有计算的部分。

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

const int MAXN = 505;
int ans;
int N;
int a[MAXN];
int f[MAXN][MAXN];
int dp[MAXN][MAXN];
int main()
{
	scanf("%d", &N);
	for(int i = 1; i <= N; i++)
	{
		scanf("%d", a + i);
		a[i + N] = a[i];
	}
	for(int i = 1; i <= N * 2; i++)
	{
		for(int j = 1; j <= N * 2; j++)
		{
			for(int k = i; k <= j; k++)
			{
				f[i][j] += a[k] % 2;
			}
		}
	}
	for(int k = 1; k <= N; k++)
	{
		memset(dp, 0, sizeof(dp));
		for(int i = 1; i <= N * 2; i++)
		{
			dp[i][i] = f[i][i];
		}
		for(int i = k + N - 1; i >= k + 1; i--)
		{
			for(int j = i + 1; j <= k + N - 1; j++)
			{
				dp[i][j] = f[i][j] - min(dp[i + 1][j], dp[i][j - 1]);
			}
		}
		if(f[k + 1][k + N] - dp[k + 1][k + N - 1] > dp[k + 1][k + N - 1])
		{
			ans++;
		}
	}
	printf("%d", ans);
	return 0;
}

T3 Delete

玄学人品算法，没有正确的时间复杂度。

考场上跑了800遍50分，同时跑200遍的xze只有30分。最后发现写的就是正解，只要在原题上换成链表维护傻逼题目什么都不需要，再加上一个标记来判断什么时候结束防止超时。

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
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=1000005;
int ans,_count,tag;
int a[MAXN],b[MAXN],c[MAXN];
int book2[MAXN],book3[MAXN];
int main()
{
	int N;
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		scanf("%d",a+i);
	}
	for(int i=1;i<=N;i++)
	{
		scanf("%d",b+i);
		book2[b[i]]++;
	}
	for(int i=1;i<=N;i++)
	{
		scanf("%d",c+i);
		book3[c[i]]++;
	}
	tag=1;
	while(tag)
	{
		tag=0;
		for(int i=1;i<=N;i++)
		{
			if(a[i]&&(!book2[a[i]]||!book3[a[i]]))
			{
				book2[b[i]]--;
				book3[c[i]]--;
				ans++;
				a[i]=0;
				tag=1;
			}
		}
	}
	printf("%d",ans);
	return 0;
}

T4 Section

可做题。 用结构体sort出每一段区间的左右端点，先按左端点从小到大排序，再按右端点从大到小排序。易证，如果一段区间$i$想要包含另一段区间$j$，要做到$L_i<=L_j$&&$R_j<=R_i$。因为左区间已经排好序了，所以题目就变成了右端点的最长不下降子序列 用upper_bound二分查找来实现$O(N\log N)$的做法就可以啦。

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 <algorithm>
#include <iostream>
using namespace std;
const int MAXN=1000005;

int dp[MAXN];
int ans,temp,now,all;
struct AR
{
	int l,r;
};
AR ar[MAXN];

bool cmp(AR a,AR b)
{
	if(a.l==b.l)
	{
		return a.r>b.r;
	}
	return a.l<b.l;
}

int len,d[MAXN];

int main()
{
	int N;
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d",&ar[i].l,&ar[i].r);
	}
	sort(ar+1,ar+1+N,cmp);
	d[1]=ar[1].r;
	len++;
	for(int i=2;i<=N;i++)
	{
		if(ar[i].r<=d[len])
		{
			len++;
			d[len]=ar[i].r;
		}
		else
		{
			int now=upper_bound(d+1,d+1+len,ar[i].r,greater <int> ())-d;
			d[now]=ar[i].r;
		}
	}
	printf("%d",len);
	return 0;
}

今天算是真的学懂LIS和lower_bound/upper_bound了。

是我没错了

是我没错了

晚餐吃的支竹煲鸭+黑椒鸡扒，支竹就是腐竹。

Day 3 2019.8.3

一只手挡开笼罩着命运的绝望，同时，另一只手记下在废墟中看到的一切。

早上上课。

讲了神仙DP。

还有DP必讲：飞扬的小鸟。

全校就我没听懂。

早上的DP真的好难啊。

下午做题3道题愣是都没调出来。

讲一下树形DP吧。

没有上司的舞会这道题，很好的阐述了树形DP，每个节点都只有一个父节点，所以转移总是向父节点转移。实现的方法大多情况下是DFS。

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
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 20000;

int head[MAXN], a[MAXN], dp[MAXN][5], _count, root, ind[MAXN];
struct EDGE
{
	int _next, to, w;
};
EDGE edge[MAXN];

void Add_Line(int a, int b)
{
	_count++;
	edge[_count]._next = head[a];
	edge[_count].to = b;
	head[a] = _count;
}

void DFS(int NowNode)
{
	dp[NowNode][1]+=a[NowNode];
	for(int i=head[NowNode];i;i=edge[i]._next)
	{
		int NextNode=edge[i].to;
		DFS(NextNode);
		dp[NowNode][0]+=max(dp[NextNode][1],dp[NextNode][0]);
		dp[NowNode][1]+=dp[NextNode][0];
	}
}

int main()
{
	int N;
	scanf("%d", &N);
	for(int i = 1; i <= N; i++)
	{
		scanf("%d", a + i);
	}
	for(int i = 1; i <= N; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		if(!(!x && !y))
		{
			Add_Line(y,x);
			ind[x]++;
		}
	}
	for(int i=1;i<=N;i++)
	{
		if(!ind[i])
		{
			root=i;
		}
	}
	DFS(root);
	printf("%d",max(dp[root][0],dp[root][1]));
	return 0;
}

松好像开始了强制打球的下午（然而下雨，场地湿滑）。

终于发现了学校里打热水的地方，竟然在食堂的正中央，服气，星际玩家无疑了。

晚上把前几天的题做了，今天就这么迷迷糊糊地颓过去了。靠。以后再也不能这样了。

Day 4 2019.8.4

万物仍按原来的轨迹运行

纪中网站门口的监视屏一直闪烁着”CF”。
eRNZfs.jpg

eRNVYj.jpg
早上模拟赛没交。。但貌似200分？

T1 Math

这一题考场上打的是$O(N^2)$的60分部分分方法。听讲课有老哥神仙memmove可以优化到80分，学好语法果然有用。

正解是开两倍数组，每次改变一个数的位置，就直接把当前段的第一个直接插到最后一个后面一位。然后不断循环这个操作。要注意的坑点是余数的那部分要特判。

时间复杂度$O(N)$

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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=5000005;
int N;
int a[MAXN],temp;
int t,p;
int head,tail;
int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		a[i]=i;
	}
	head=0,tail=N-1;
	t=a[1];
	for(int i=2;i<=N;i++)
	{
		head++;
		tail++;
		for(int j=head;j<=tail;j+=i)
		{
			if(j==head)
			{
				t=a[j];
			}
			if(j+i-1>tail)
			{
				p=a[j+i];
				int now=head+N;
				a[now]=t;
				t=p;
				continue;
			}
			p=a[j+i];
			a[j+i]=t;
			t=p;
		}
	}
	for(int i=N;i<=2*N-1;i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}

T2 Card

游戏王背景好评，哪一天来个万智？

这一题最后得到了错误的贪心。但是考场上的思路是正确的，需要加上二分查找来降低复杂度到$O(NlogN)$。

有两种策略，第一种是打完所有对手的手牌，然后走脸。

第二种是只打对手的进攻表示牌。

显然，第二种的做法是对对手的进攻牌从小到大排序，对自己的手牌从大到小排序。然后每次进攻就加上差值，直到不能再起再打。

第一种的做法是，选择尽可能接近的手牌打对手的防守牌，然后依次打对手的进攻牌，直到不能再打。最后全走脸。

抄一份xze的代码太懒了

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
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#define ll long long
#define il inline
#define rgi register ll

using namespace std;

const int oo = 0x3f3f3f3f;
const ll N = 100000 + 10;

ll n, m, step, ans1, ans2, minn = oo;
ll def[N], atk[N], x[N];
ll sum_def[N], sum_atk[N], sum_x[N];

il ll read()
{
    rgi x = 0, f = 0, ch;
    while(!isdigit(ch = getchar())) f |= ch == '-';
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

int main()
{
    m = read(), n = read();
    for(rgi i = 1; i <= m; ++i)
    {
        char op[10];
        ll val;
        scanf("%s %lld", op, &val);
        if(op[0] == 'A')
            atk[++atk[0]] = val;
        else if(op[0] == 'D')
            def[++def[0]] = val;
    }
    for(rgi i = 1; i <= n; ++i)
        x[i] = read();
    sort(atk + 1, atk + atk[0] + 1);
    sort(def + 1, def + def[0] + 1);
    sort(x + 1, x + n + 1);
    for(rgi i = 1; i <= atk[0]; ++i)
        sum_atk[i] = sum_atk[i - 1] + atk[i];
    for(rgi i = 1; i <= def[0]; ++i)
        sum_def[i] = sum_def[i - 1] + def[i];
    for(rgi i = 1; i <= n; ++i)
        sum_x[i] = sum_x[i - 1] + x[i];//处理前缀和
    atk[atk[0] + 1] = oo; //（1）破了别人的防，然后直接走脸
    for(rgi i = 1; i <= n; ++i)
    {
        while(x[i] >= atk[step])
            step++;
        step--;
        minn = min(minn, step + n - i);
    }
    ans1 = sum_x[n] - sum_x[n - minn] - sum_atk[minn];
    if(minn >= atk[0] && n > m)
    {
        step = 1;
        for(rgi i = 1; i <= def[0]; ++i)
        {
            while(def[i] >= x[step])//打对方DEF最小的牌
                step++;
            x[step] = 0;
        }
        if(step <= n - minn)//如果把对方的防都打完了
            for(rgi i = 1; i <= n - minn; ++i)//走脸
                ans1 += x[i];
    }
    for(rgi i = 1; i < minn; ++i)//（2）只怼别人的攻
        ans2 = max(ans2, sum_x[n] - sum_x[n - i] - sum_atk[i]);
    printf("%lld", max(ans1, ans2));
    return 0;
}

T3 Show

拥有奇怪的复杂度的题，貌似有各种搜索方法，如$O(NMK)$和$O(N^4)$
实际上是DP。继续抄xze的代码。

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
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#define ll long long
#define il inline
#define rgi register int

using namespace std;

const int oo = 0x3f3f3f3f;
const int N = 200 + 10;

int n, m, x, y, k, ans = -oo;
char e[N][N];
int f[N][N][N];
int d[5][2] =
{
    {0, 0}, { -1, 0}, {1, 0}, {0, -1}, {0, 1}
};

il int read()
{
    rgi x = 0, f = 0, ch;
    while(!isdigit(ch = getchar())) f |= ch == '-';
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

int main()
{
    n = read(), m = read(), x = read(), y = read(), k = read();
    for(rgi i = 1; i <= n; ++i)
        scanf("%s", e[i] + 1);
    memset(f, -1, sizeof(f));
    f[0][x][y] = 0;
    for(rgi l = 1; l <= k; ++l)
    {
        int a = read(), b = read(), c = read();
        for(rgi i = 1; i <= n; ++i)
            for(rgi j = 1; j <= m; ++j)
            {
                if(f[l - 1][i][j] == -1)
                    continue;
                f[l][i][j] = max(f[l][i][j], f[l - 1][i][j]);
                int xx = i, yy = j;
                for(rgi t = 1; t <= b - a + 1; ++t)
                {
                    xx += d[c][0];
                    yy += d[c][1];
                    if(xx < 1 || xx > n || yy < 1 || yy > m || e[xx][yy] != '.')
                        break;
                    f[l][xx][yy] = max(f[l][xx][yy], f[l - 1][i][j] + t);
                }
            }
    }
    for(rgi i = 1; i <= n; ++i)
        for(rgi j = 1; j <= m; ++j)
            ans = max(ans, f[k][i][j]);
    printf("%d", ans);
    return 0;
}

lcx实在tql，打篮球被锤爆了 ，高中混不下去了。

傍晚看到彩虹（现在知道没下雨也能看到彩虹）了，这边夕阳景象很好看。

eRNKXV.jpg

eRNnlq.jpg

eRN17F.jpg

eRNu60.jpg

晚上打了第一场Atcoder，Rank还算过得去，A掉了4道题。

T1 Transfer

入门题，输出C-B+A，但要注意负数，如果小于0就直接输出0。

T2 Uneven Number

问N以内数位是奇数的数有多少个，就模拟数位计算，然后注意最高位的奇偶就好了。

T3 Building stairs

给N个数，每个数可以选择做1次减1高度的操作。问数列有没有可能成为不下降子序列。

模拟，如果目前所在的比后面的大2，直接break。输出NO

如果大1，后面的加1。

如果跑到倒数第2个都没问题。那么输出yes。

T4 Gathering Children

给N个字符，字符只能为$L,R$中的一个，一开始，N个字符上各有一个小朋友，每过一轮，字符上的小朋友就向字符的方向跑一格。问$10^{100}$轮后，每个字符上各有几个小朋友。保证最左边为R，最右边为L。

刚读完题，很懵逼，但是通过Ted的想法，我明白了。因为$10^{100}$是一个很大的数，可以把它当做趋近于无限大，所以，考虑下面这个情况。

在一个左边是L，右边是R的地方，站在上面的人最后只会在上面打转转。

因为只有$L,R$两种状态。所以R的右边不是L就是R，对于每个L，我们找到它左边最近的L，对于每个R，我们找到它右边最近的L。

然后判断奇偶性，如果是偶数，那么直接落在最近的L/R身上，否则，落在L的左边/R的右边。

处理最近的$L,R$就用单调栈在$O(N)$时间内预处理出来。

代码

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
char a[MAXN];
int b[MAXN];
int ans[MAXN];
int d[MAXN];
int stack[MAXN];
int top;
bool tag;
int lef[MAXN],righ[MAXN];
int ou[MAXN];
int main()
{
	scanf("%s",a);
	int N=strlen(a);
	for(int i=1;i<=N;i++)
	{
		if(a[i-1]=='R')
		{
			b[i]=1;
		}
		else
		{
			b[i]=0;
		}
	}
	for(int i=1;i<=N;i++)
	{
		if(b[i]==b[stack[top]]&&top)
		{
			top--;
		}
		if(!b[i])
		{
			righ[i]=stack[top];
		}
		top++;
		stack[top]=i;
	}
	top=0;
	for(int i=N;i>=1;i--)
	{
		if(b[i]==b[stack[top]]&&top)
		{
			top--;
		}
		if(b[i])
		{
			lef[i]=stack[top];
		}
		top++;
		stack[top]=i;
	}
	for(int i=1;i<=N;i++)
	{
		if(b[i])
		{
			if((lef[i]-i)%2==1)
			{
				ou[lef[i]-1]++;
			}
			else
			{
				ou[lef[i]]++;
			}
		}
		else
		{
			if((i-righ[i])%2==1)
			{
				ou[righ[i]+1]++;
			}
			else
			{
				ou[righ[i]]++;
			}
		}
	}
	for(int i=1;i<=N;i++)
	{
		printf("%d ",ou[i]);
	}
	return 0;
}

Day 5 2019.8.5

见人见多了想看海

集体OJ丢包。

T1 Pipes

枚举空地每种管道的可能性，然后从起点开始搜索，如果可达终点就输出。

搜索，模拟管道走向，要注意的点：

  • 第一次DFS不能直接到达终点
    要记录来的路防止往回走
    十字路口必须保证与来的路对应。

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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 35;

struct NODE
{
	int x, y;
};
NODE S, T;
int R, C;
int _map[MAXN][MAXN];
int book;
bool tag;
void DFS(int x, int y, int lastx, int lasty)
{
	if(x == T.x && y == T.y)
	{
		tag = 1;
		return;
	}
	if(!_map[x][y] || x < 1 || y < 1 || x > C || y > R)
	{
		return;
	}
	if(_map[x][y] == 1)
	{
		if(x == lastx && y - 1 == lasty)
		{
			DFS(x, y + 1, x, y);
		}
		if(x == lastx && y + 1 == lasty)
		{
			DFS(x, y - 1, x, y);
		}
	}
	if(_map[x][y] == 2)
	{
		if(x - 1 == lastx && y == lasty)
		{
			DFS(x + 1, y, x, y);
		}
		if(x + 1 == lastx && y == lasty)
		{
			DFS(x - 1, y, x, y);
		}
	}
	if(_map[x][y] == 3)
	{
		if(x - 1 == lastx && y == lasty)
		{
			DFS(x + 1, y, x, y);
		}
		if(x + 1 == lastx && y == lasty)
		{
			DFS(x - 1, y, x, y);
		}
		if(x == lastx && y + 1 == lasty)
		{
			DFS(x, y - 1, x, y);
		}
		if(x == lastx && y - 1 == lasty)
		{
			DFS(x, y + 1, x, y);
		}
	}
	if(_map[x][y] == 4)
	{
		if(x + 1 == lastx && y == lasty)
		{
			DFS(x, y + 1, x, y);
		}
		if(x == lastx && y + 1 == lasty)
		{
			DFS(x + 1, y, x, y);
		}
	}
	if(_map[x][y] == 5)
	{
		if(x == lastx && y - 1 == lasty)
		{
			DFS(x + 1, y, x, y);
		}
		if(x + 1 == lastx && y == lasty)
		{
			DFS(x, y - 1, x, y);
		}
	}
	if(_map[x][y] == 6)
	{
		if(x - 1 == lastx && y == lasty)
		{
			DFS(x, y - 1, x, y);
		}
		if(x == lastx && y - 1 == lasty)
		{
			DFS(x - 1, y, x, y);
		}
	}
	if(_map[x][y] == 7)
	{
		if(x - 1 == lastx && y == lasty)
		{
			DFS(x, y + 1, x, y);
		}
		if(x == lastx && y + 1 == lasty)
		{
			DFS(x - 1, y, x, y);
		}
	}
}

int main()
{
	scanf("%d%d", &R, &C);
	for(int i = 1; i <= R; i++)
	{
		char a[MAXN];
		cin >> a;
		for(int j = 0; j < C; j++)
		{
			if(a[j] == '|')
			{
				_map[j + 1][i] = 1;
			}
			if(a[j] == '-')
			{
				_map[j + 1][i] = 2;
			}
			if(a[j] == '+')
			{
				_map[j + 1][i] = 3;
			}
			if(a[j] == '1')
			{
				_map[j + 1][i] = 4;
			}
			if(a[j] == '2')
			{
				_map[j + 1][i] = 5;
			}
			if(a[j] == '3')
			{
				_map[j + 1][i] = 6;
			}
			if(a[j] == '4')
			{
				_map[j + 1][i] = 7;
			}
			if(a[j] == 'Z')
			{
				T.y = i;
				T.x = j + 1;
			}
			if(a[j] == 'M')
			{
				S.y = i;
				S.x = j + 1;
			}
		}
	}
	for(int i = 1; i <= C; i++)
	{
		for(int j = 1; j <= R; j++)
		{
			if(_map[i][j])
			{
				continue;
			}
			for(int k = 1; k <= 7; k++)
			{
				_map[i][j] = k;
				if(S.x + 1 != T.x || S.y != T.y)
					DFS(S.x + 1, S.y, S.x, S.y);
				if(S.x - 1 != T.x || S.y != T.y)
					DFS(S.x - 1, S.y, S.x, S.y);
				if(S.x != T.x || S.y + 1 != T.y)
					DFS(S.x, S.y + 1, S.x, S.y);
				if(S.x != T.x || S.y - 1 != T.y)
					DFS(S.x, S.y - 1, S.x, S.y);
				if(tag)
				{
					printf("%d %d ", j, i);
					if(k == 1)
					{
						printf("|");
					}
					if(k == 2)
					{
						printf("-");
					}
					if(k == 3)
					{
						printf("+");
					}
					if(k == 4)
					{
						printf("1");
					}
					if(k == 5)
					{
						printf("2");
					}
					if(k == 6)
					{
						printf("3");
					}
					if(k == 7)
					{
						printf("4");
					}
					return 0;
				}
			}
			_map[i][j] = 0;
		}
	}
	return 0;
}

T2 Digits

只记录每次操作，然后模拟。

T3 Water

压缩每一种情况。用hash，map之类的。这里因为只有2种状态所以可以直接用倍增思想压位。那么需要开$2^N$的vis来存某一种状态第一次出现的时刻。
然后每次判断是否出现。注意要用前缀和来记录，最后才能算出答案。比较简单的一道题，但调了好久好久。

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
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 22;
int G[MAXN][MAXN];
bool _map[MAXN];
bool temp[MAXN];
long long ans;
int sum[1<<MAXN];
int vis[1<<MAXN];
int N,H;
int second,first;
int Get(bool a[])
{
	int now=0;
	for(int i=1;i<=N;i++)
	{
		now+=(1<<i-1)*a[i];
	}
	return now;
}

int main()
{
	scanf("%d%d",&N,&H);
	for(int i=1;i<=N;i++)
	{
		char a[25];
		scanf("%s",a);
		for(int j=0;j<N;j++)
		{
			G[i][j+1]=a[j]-'0';
		}
	}
	for(int i=1;i<=N;i++)
	{
		if(G[i][1])
		{
			_map[i]^=1;
			sum[1]++;
		}
	}
	int book=Get(_map);
	vis[book]=1;
	for(int i=2;i<=H;i++)
	{
		for(int j=1;j<=N;j++)
		{
			temp[j]=0;
		}
		int now=0;
		for(int j=1;j<=N;j++)
		{
			if(_map[j]==1)
			{
				for(int k=1;k<=N;k++)
				{
					if(G[j][k])
					{
						now++;
						temp[k]^=1;
					}
				}
			}
			else
			{
				for(int k=1;k<=N;k++)
				{
					if(G[j][k])
					{
						now+=2;
					}
				}
			}
		}
		for(int j=1;j<=N;j++)
		{
			_map[j]=temp[j];
		}
		sum[i]=now+sum[i-1];
		book=Get(temp);
		if(vis[book])
		{
			first=vis[book];
			second=i;
			break;
		}
		vis[book]=i; 
	}
//	putchar('\n');
//	for(int i=1;i<=H;i++)
//	{
//		printf("%d ",sum[i]);
//	}
//	putchar('\n');
	if(first&&second)
	{
		H-=first;
		ans+=sum[first];
		ans+=(long long)H/(second-first)*(sum[second]-sum[first]);
		int all=H%(second-first);
		ans+=sum[first+all]-sum[first];
		printf("%lld",ans);
	}
	else
	{
		printf("%d",sum[H]);
	}
	return 0;
}

T4 Flowers

对题目建模，变成区间修，单点查，用线段树维护就好。

中午寝室里飞来一只蝴蝶。我想把它养起来，但cyx不让。

eRNQmT.jpg

然后我的花被cyx踢翻了，烦。

下午还是去打球了。

纪中船。

eRNl0U.jpg

晚上九点五十下课后，去了一趟食堂，真如xze所说的，有宵夜卖。

瘦肉汤粉和鸡柳非常棒！

Day 6 2019.8.6

贬低他人并不能给自己带来成功。

早上讲了并茶几并查集和堆。其实知识点什么的比较正常，但是题目非常有趣，例如NOI的荷马史诗。学到了Huffman树，总算了解了一些新知识。

但是，老师的讲课节奏实在让我难以接受，于是我和xze，E队预定zzy一起回机房敲题去了。

下午，总算是调出了序列变换，感觉自己像智障一样。

还有好多题没有调出来啊。感觉休息日会非常充实。

今天终于战胜了lcx，虽然是在1+0+0V3的情况下赢的。

IMG_20190806_175652.jpg

果然还是太菜了。仅仅只是联赛就还有知识点没搞懂。更别提未来了。

出了这道题，打了$O(N^2)$的标程，和不知道正确性的$O(N)$优化。

怎么所有人都会Splay，就我不会。

晚上调题的时候，cyx电脑上跳了一只蚂蚱2333。

IMG_20190806_194419.jpg

Day 7 2019.8.7

人生在世何其痛苦，所以咖啡至少要甜一点。

疯狂挂分啊。第一周的Ending day。

T1 Triangle

O(2)算法

暴力枚举，通过各种编译优化水过。

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
#pragma GCC optimize(2)
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN=2000;
const double EPS=0.01;
struct NODE
{
	long long x,y;
};
NODE node[MAXN]; 
double dis[MAXN][MAXN];
long long Umi(NODE x,NODE y)
{
	return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}
long long ans;
int main()
{
	long long N;
	scanf("%lld",&N);
	for(int i=1;i<=N;i++)
	{
		scanf("%lld%lld",&node[i].x,&node[i].y);
	}
	for(int i=1;i<=N;i++)
	{
		for(int j=i+1;j<=N;j++)
		{
			for(int k=j+1;k<=N;k++)
			{
				if(i==j||j==k||i==k)
				{
					continue;
				}
				long long Len1=Umi(node[i],node[j]),Len2=Umi(node[i],node[k]),Len3=Umi(node[j],node[k]);
				if(Len1+Len2==Len3||Len2+Len3==Len1||Len3+Len1==Len2)
				{
//					printf("%d %d %d %d %d %d\n",i,j,k,Umi(node[i],node[j]),Umi(node[i],node[k]),Umi(node[j],node[k]));
					ans++;
				}
			}
		}	
	}
	printf("%lld",ans);
	return 0;
}

T2 Sort

不贴代码，因为实现方式很多，就只讲一讲思想好了。

首先用树状数组预处理出动态前缀和与动态后缀和，来表示每个数前面比它大的以及后面比它小的数。

然后每一次询问，如果是单数，就是前面比它大的总和，反之就是后面比它小的。易证，在每一次询问之前，如果它是单数，他前面的未复原的都比他大，如果是偶数则后面的未复原的都比它小。注意，在每一次询问之后，那个数是复原了的，所以它的前面比它大的那些部分，要在记录后面比那些部分小的上面减1，反之是在后面比它小的那些部分，记录前面比它大的上面减1。

用树状数组，线段树，或者分块维护。
姑且就算这道题做了吧。

T3 Competition

tarjan求环+树形DP。貌似大家都不会。我也不会

T4 L

先咕了，等模块式讲解矩阵快速幂。

晚上cyx搬出去住了，睡得早多了。

Day 8 2019.8.8

海的另一边是自由。

休息日。

“中山是一个小城”——–XC。

早上坐了好久好久的公交车，再看过去仿佛过了一段茶色的百年。（强行通感句）

参与的人有：我 xze wym myf ccx wlo

早上八点在门口集合，xzh咕咕咕了。（后来了解到他收到了cyx错误的信息，淦）

myf太强了，地理大佬，他好像对所有的路，交通方式都如自家大院一样了解。

公交车是人工售票，从学校（基本上是郊区）到中心城区要4元5角，比武汉贵好多啊。

跟着wym和myf去修wym的手机，华为效率真的高，说1个小时就可以修好。

mwPUmQ.jpg

经过投票表决，最后同意放弃公园（太热了），去购物中心。

mwPBYq.jpg
逛了NIKE的店，真鸡儿贵，没一个买的起的。奆佬wlo给自己买了件T-shirt，我非常担心他怎么洗。

然后就在里面打了一个上午的电玩。商家还是挺良心的，五毛钱一个代币。玩第一滴血一条命只要一个代币。我和wym+wlo把第一滴血3打穿了。

mwPawj.jpg
然后是音游老狗和投篮机。xze320多分破了记录。我难得的在落球机上打到了jackpot获得160多张彩票。

mwPY6S.jpg

中午在茶餐厅吃的。咖喱鱼蛋和鳗鱼炒饭很好吃。

我发现如果想吃当地菜，不能去大商场，大商场里面少有卖当地菜的。

这个beats我酸了。

mwPtOg.jpg

下午和xzh xze ccx 在学校旁边（我这才发现学校建在公园里）的中山故居参观，了解了一些”史实”。

mwPdTs.jpg

mwP0kn.jpg

mwPDf0.jpg

mwPspV.jpg

mwP66U.jpg

mwPcXF.jpg

mwP2m4.jpg

mwPR0J.jpg

我看孙中山的子女亲人，大多都侨居海外了。还有孙中山当时对中国的规划图，武汉是超级大城市，通铁路水路什么的都要经过武汉。哎，可惜了。

最后一段是赞美中国共产党的。真·行为艺术。

Day 9 2019.8.9

May the odds be ever in your favor.

阿华田实在是太***好喝了。

mwPJl8.jpg

今天早上是个DP round，还全是SC省选题。

T1 Painter

一道DP好题。 好像是全场唯一会的一道题

我们看题面，有说每块木板最多被粉刷一次，所以可以通过它得到没有后效性这一个DP突破口。然后我们再考虑如何做DP。题目的数据范围指出，$N,M\le50$，好像怎么瞎搞都可以过。对于每一块木板，上方和下方木板对它是没有影响的，所以每一块木板都可以是一个独立的状态。最后再一起统计。

那么对于每一块木板，我们设$f[i][j]$为当前这一行前i个木板用j次粉刷次数，最多可以满足的木板块的个数是多少。
转移方程：

$$dp[i][j] = max(dp[i-1][j], dp[k][j - 1] + max(sum[i] - sum[k], i - k - (sum[i] - sum[k])))$$

其中$K\in0$~$ i-1$ 。

$sum$是这一组的前缀和，表示蓝色的个数，那么$i-k-(sum[i]-sum[k])$就应该是红色的，这个转移就比较好理解了。就是要么不涂，要么找一段涂蓝色或红色。

然后，问题就转化为已知对每一块长木板刷$i$次可以获得$v[i]$的价值，求刷$N$次可以得到的最大值。原题就变成了一个分组背包问题了。

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
//每个格子最多只能被粉刷一次。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

const int MAXN = 70;
int G[MAXN][MAXN];
int f[MAXN][MAXN*MAXN];
int dp[MAXN][MAXN*MAXN];
int sum[MAXN];
char s[MAXN];
int n, m, t;
int main()
{
	scanf("%d%d%d", &n, &m, &t);
	for(int p = 1; p <= n; p++)
	{
		scanf("%s", s);
		for(int j = 1; j <= m; j++)
		{
			G[p][j] = s[j - 1] - '0';
		}
		for(int j = 1; j <= m; j++)
		{
			sum[j] = sum[j - 1] + G[p][j];
		}
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= m; ++i)
		{
			for (int j = 1; j <= t; ++j)
			{
				dp[i][j] = dp[i - 1][j];
				for (int k = 0; k < i; ++k)
				{
					dp[i][j] = max(dp[i][j], dp[k][j - 1] + max(sum[i] - sum[k], i - k - (sum[i] - sum[k])));
				}
			}
		}
		for (int i = 1; i <= t; ++i)
		{
			for (int j = 0; j <= i; ++j)
			{
				f[p][i] = max(f[p][i], f[p - 1][j] + dp[m][i - j]);
			}
		}
	}
	printf("%d", f[n][t]);
	return 0;
}

T2 Maze

一道拆点+矩阵乘法好题

对于每一个点，我们将他的入度的边权拆成边权个权值为1的点，然后跑floyd，对于边权只有1的点，有这样的性质，方案数就是矩阵乘法的定义，因为在边权只有1的时候，方案数也是1，所以方案数的转移就和路径长度的转移一样了。

T3 Game

一道找性质+DP好题

事实上对于每一组解，就是找到一个循环节，这个循环节是对于每一个数回到自己的组数的最小公倍数。

T4 Windy numbers

一道数位DP裸题

非常裸的题，但我不会。

Day 10 2019.8.10

一觉醒来时,你将成为新世界的一部分。

现在B组的题目怎么越来越难了！！！

这次四道是什么克罗地亚国家赛的题。

T1 flood

只会口胡正解，代码实在调不出来。

对每一个洪水进行BFS预处理出洪水到达每个点的深度。
然后再对画家进行BFS，路径上如果深度大于等于洪水的深度，就不能走。

BFS模拟就好，但是我码力trl。

不知道为什么被卡的代码

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;

const int MAXN=1000;
struct NODE
{
	int x,y;
};
NODE _arrayp[MAXN*MAXN],_arrayf[MAXN*MAXN];
int R,C;
int _map[MAXN][MAXN],visf[MAXN][MAXN],visp[MAXN][MAXN],f[MAXN][MAXN],p[MAXN][MAXN];
char a[MAXN];
int headf,tailf,headp,tailp,sx,sy;
int main()
{
	
	scanf("%d%d",&R,&C);
	for(int i=1;i<=R;i++)
	{
		scanf("%s",a);
		for(int j=1;j<=C;j++)
		{
			if(a[j-1]=='X')
			{
				_map[i][j]=0;
			}
			else if(a[j-1]=='.')
			{
				_map[i][j]=1;
			}
			else if(a[j-1]=='*')
			{
				_map[i][j]=2;
				tailf++;
				_arrayf[tailf].x=i;
				_arrayf[tailf].y=j;
				f[i][j]=1;
			}
			else if(a[j-1]=='D')
			{
				_map[i][j]=3;
				f[i][j]=INF;
				sx=i;
				sy=j;
			}
			else if(a[j-1]=='S')
			{
				_map[i][j]=4;
				tailp++;
				_arrayp[tailp].x=i;
				_arrayp[tailp].y=j;
				p[i][j]=1;
			}
		}
	}
	while(headf<tailf)
	{
		headf++;
		int x=_arrayf[headf].x;
		int y=_arrayf[headf].y;
		visf[x][y]=1;
		if(x==sx&&y==sy)
		{
			break;
		}
		if(_map[x-1][y]&&!visf[x-1][y]&&_map[x-1][y]!=3)
		{
			tailf++;
			_arrayf[tailf].x=x-1;
			_arrayf[tailf].y=y;
			f[x-1][y]=f[x][y]+1;
		}
		if(_map[x+1][y]&&!visf[x+1][y]&&_map[x+1][y]!=3)
		{
			tailf++;
			_arrayf[tailf].x=x+1;
			_arrayf[tailf].y=y;
			f[x+1][y]=f[x][y]+1;
		}
		if(_map[x][y-1]&&!visf[x][y-1]&&_map[x][y-1]!=3)
		{
			tailf++;
			_arrayf[tailf].x=x;
			_arrayf[tailf].y=y-1;
			f[x][y-1]=f[x][y]+1;
		}
		if(_map[x][y+1]&&!visf[x][y+1]&&_map[x][y+1]!=3)
		{
			tailf++;
			_arrayf[tailf].x=x;
			_arrayf[tailf].y=y+1;
			f[x][y+1]=f[x][y]+1;
		}
	}
	while(headp<tailp)
	{
		headp++;
		int x=_arrayp[headp].x;
		int y=_arrayp[headp].y;
		visp[x][y]=1;
		if(x==sx&&y==sy)
		{
			break;
		}
		if(_map[x-1][y]&&!visp[x-1][y]&&(f[x-1][y]>p[x][y]+1||!f[x-1][y]))
		{
			tailp++;
			_arrayp[tailp].x=x-1;
			_arrayp[tailp].y=y;
			p[x-1][y]=p[x][y]+1;
		}
		if(_map[x+1][y]&&!visp[x+1][y]&&(f[x+1][y]>p[x][y]+1||!f[x+1][y]))
		{
			tailp++;
			_arrayp[tailp].x=x+1;
			_arrayp[tailp].y=y;
			p[x+1][y]=p[x][y]+1;
		}
		if(_map[x][y-1]&&!visp[x][y-1]&&(f[x][y-1]>p[x][y]+1||!f[x][y-1]))
		{
			tailp++;
			_arrayp[tailp].x=x;
			_arrayp[tailp].y=y-1;
			p[x][y-1]=p[x][y]+1;
		}
		if(_map[x][y+1]&&!visp[x][y+1]&&(f[x][y+1]>p[x][y]+1||!f[x][y+1]))
		{
			tailp++;
			_arrayp[tailp].x=x;
			_arrayp[tailp].y=y+1;
			p[x][y+1]=p[x][y]+1;
		}
	}
	if(p[sx][sy])
	{
		printf("%d",p[sx][sy]-1);
	}
	else
	{
		printf("KAKTUS");
	}
	return 0;
	
}

补于2019/9/10:今天竟然考了原题，训练没调出来，考场竟然调出来了。。

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
173
174
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;

const int MAXN=250;

struct NODE
{
	int x,y;
};

int _map[MAXN][MAXN],f[MAXN][MAXN],p[MAXN][MAXN],visf[MAXN][MAXN],visp[MAXN][MAXN];
int fl,fr,pl,pr,sx,sy;
NODE _arrayf[MAXN*MAXN*MAXN],_arrayp[MAXN*MAXN*MAXN];
int main()
{
	memset(f,INF,sizeof(f));
	memset(p,INF,sizeof(p));
	int N,M;
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++)
	{
		char a[MAXN];
		cin>>a;
		for(int j=1;j<=M;j++)
		{
			if(a[j-1]=='.')
			{
				_map[i][j]=1;
			}
			if(a[j-1]=='X')
			{
				_map[i][j]=0;
			}
			if(a[j-1]=='*')
			{
				_map[i][j]=2;
				visf[i][j]=1;
				f[i][j]=0;
				fr++;
				_arrayf[fr].x=i;
				_arrayf[fr].y=j;
			}
			if(a[j-1]=='D')
			{
				_map[i][j]=3;
				sx=i,sy=j;
			}
			if(a[j-1]=='S')
			{
				_map[i][j]=4;
				p[i][j]=0;
				visp[i][j]=1;
				pr++;
				_arrayp[pr].x=i;
				_arrayp[pr].y=j;
			}
		}
	}	
	while(fl<fr)
	{
		fl++;
		int x=_arrayf[fl].x;
		int y=_arrayf[fl].y;
		if(x+1<=N&&_map[x+1][y]!=0&&_map[x+1][y]!=3&&!visf[x+1][y])
		{
			f[x+1][y]=min(f[x+1][y],f[x][y]+1);
			fr++;
			_arrayf[fr].x=x+1;
			_arrayf[fr].y=y;
			visf[x+1][y]=1;
		}
		if(x-1>=1&&_map[x-1][y]!=0&&_map[x-1][y]!=3&&!visf[x-1][y])
		{
			f[x-1][y]=min(f[x-1][y],f[x][y]+1);
			fr++;
			_arrayf[fr].x=x-1;
			_arrayf[fr].y=y;
			visf[x-1][y]=1;
		}
		if(y+1<=M&&_map[x][y+1]!=0&&_map[x][y+1]!=3&&!visf[x][y+1])
		{
			f[x][y+1]=min(f[x][y+1],f[x][y]+1);
			fr++;
			_arrayf[fr].x=x;
			_arrayf[fr].y=y+1;
			visf[x][y+1]=1;
		}
		if(y-1>=1&&_map[x][y-1]!=0&&_map[x][y-1]!=3&&!visf[x][y-1])
		{
			f[x][y-1]=min(f[x][y-1],f[x][y]+1);
			fr++;
			_arrayf[fr].x=x;
			_arrayf[fr].y=y-1;
			visf[x][y-1]=1;
		}
	}
	while(pl<pr)
	{
		pl++;
		int x=_arrayp[pl].x;
		int y=_arrayp[pl].y;
		if(x+1<=N&&_map[x+1][y]&&!visp[x+1][y]&&p[x][y]+1<f[x+1][y])
		{
			p[x+1][y]=min(p[x+1][y],p[x][y]+1);
			pr++;
			_arrayp[pr].x=x+1;
			_arrayp[pr].y=y;
			visp[x+1][y]=1;
		}
		if(x-1>=1&&_map[x-1][y]&&!visp[x-1][y]&&p[x][y]+1<f[x-1][y])
		{
			p[x-1][y]=min(p[x-1][y],p[x][y]+1);
			pr++;
			_arrayp[pr].x=x-1;
			_arrayp[pr].y=y;
			visp[x-1][y]=1;
		}
		if(y+1<=M&&_map[x][y+1]&&!visp[x][y+1]&&p[x][y]+1<f[x][y+1])
		{
			p[x][y+1]=min(p[x][y+1],p[x][y]+1);
			pr++;
			_arrayp[pr].x=x;
			_arrayp[pr].y=y+1;
			visp[x][y+1]=1;
		}
		if(y-1>=1&&_map[x][y-1]&&!visp[x][y-1]&&p[x][y]+1<f[x][y-1])
		{
			p[x][y-1]=min(p[x][y-1],p[x][y]+1);
			pr++;
			_arrayp[pr].x=x;
			_arrayp[pr].y=y-1;
			visp[x][y-1]=1;
		}
	}
//	for(int i=1;i<=N;i++)
//	{
//		for(int j=1;j<=M;j++)
//		{
//			printf("%d ",_map[i][j]);
//		}
//		putchar('\n');
//	}
//	putchar('\n');
//	for(int i=1;i<=N;i++)
//	{
//		for(int j=1;j<=M;j++)
//		{
//			printf("%d ",f[i][j]);
//		}
//		putchar('\n');
//	}
//	putchar('\n');
//	for(int i=1;i<=N;i++)
//	{
//		for(int j=1;j<=M;j++)
//		{
//			printf("%d ",p[i][j]);
//		}
//		putchar('\n');
//	}
	if(p[sx][sy]==INF)
	{
		printf("KAKTUS");
	}
	else
	{
		printf("%d",p[sx][sy]);
	}
	return 0;
}

T2 Bond

$N$很小，考虑对题目进行状压DP。

T3 Dinner Table

水法是暴力枚举每一行的连续长区间，以及每一列的连续长区间，找到周长最长的一段。然后统计答案就好。水法并不是严格$O(N^2)$的。

正确的方法是前缀和，但我确实看不懂。

水法代码，感谢mjc的完整版。

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
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool a[2010][2010];
int l[2010][2010];
int r[2010][2010];
int up[2010][2010];

int main(){
    cin>>n>>m; 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char ch;
            cin>>ch;
            if(ch=='X'){
                a[i][j]=0;
            }
            else a[i][j]=1;
        }
    } 
//      for(int i=1;i<=n;i++){
//      for(int j=1;j<=m;j++){
//          cout<<a[i][j]<<" ";
//      }
///     cout<<endl;
//  }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            l[i][j]=j;
            r[i][j]=j;
            up[i][j]=1;
        }

    //处理l
    for(int i=1;i<=n;i++)
        for(int j=2;j<=m;j++)
            if(a[i][j]&&a[i][j-1])
            l[i][j]=l[i][j-1];//如果当前和其左皆可，当前能到的最左边就是左边能到的最左边 
                              //当然这里存的还是位置

    //处理r
    for(int i=1;i<=n;i++)
        for(int j=m-1;j>=1;j--)
            if(a[i][j]&&a[i][j+1])
             r[i][j]=r[i][j+1];
//              cout<<"FUCK3"<<endl;     

    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i>1 && a[i][j] && a[i-1][j]){
                l[i][j]=max(l[i][j],l[i-1][j]);
                r[i][j]=min(r[i][j],r[i-1][j]);
                up[i][j]=up[i-1][j]+1;
            }
        ans=max(ans,(r[i][j]-l[i][j]+1)+up[i][j]);
        }
    }

    cout<<ans*2-1<<endl;
    return 0;
}

正解代码（虽然我觉得很混）

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 2005;
int _map[MAXN][MAXN];
int ans;
char a[MAXN];
int main()
{
	int N, M;
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i++)
	{
		scanf("%s", a);
		for (int j = 1; j <= M; j++)
		{
			if (a[j - 1] == 'X')
			{
				_map[i][j] = -INF;
			}
		}

	}
	for (int i = 1; i <= M; i++)
	{
		if (_map[M][i] != -INF)
		{
			_map[M][i] = 1;
		}
	}
	for (int i = N - 1; i >= 1; i--)
	{
		for (int k = 1; k <= M; k++)
		{
			if (_map[i][k] != -INF)
			{
				if (_map[i + 1][k] == -INF)
				{
					_map[i][k] = 1;
				}
				else
				{
					_map[i][k] = _map[i + 1][k] + 1;
				}
			}
		}
	}
	int __x, ___x;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (_map[i][j])
			{
				___x = j;
				__x = INF;
				while (_map[i][___x] > 0)
				{
					if (_map[i][___x] < __x)
					{
						__x = _map[i][___x];
					}
					ans = max(ans, (___x - j + 1 + __x) * 2 - 1);
					___x++;
				}
			}
		}
	}
	printf("%d", ans);
	return 0;
}

T4 Bike

Tarjan求强连通分量得到环，然后从1号节点开始BFS到2号节点看路径上有没有环。

其实我不会这道题。等回家做Tarjan详解时加上好了。

晚上atcoder。

还是A了四道题，这次rank900多，rating猛涨，吓死我了。TedA了5题，rank500多。以后打atcoder，不能因为A了4道题就放弃E题，还是要努力去冲一下E题的。

T1 +-x

输入$a,b$, 输出$a+b$ , $a-b$ , $a*b$ 中的最大值，直接模拟就好了。

T2 One Clue

输入$a,b$, 输出$a-b+1$~$a+b-1$，直接模拟。

T3 Green Bin

输入N个长度为10的字符串，我们称拥有相同数量的相同字符的字符串为同一个字符串。（即内容一样，但是可能乱序）。统计相同字符串的无序对数。

我们对每个字符串做字典序排序，然后丢入一个map里，在线统计答案。

设当前字符串的键值为$a$那么每次统计答案就应该：

$ans+=a*(a-1)/2$

$ans-=(a-1)*(a-2)/2$

T4 Summer Vacation

给定N个工作，M天，每个工作有两个关键字，需要的时间和价值。每天可以做很多工作，但是每天只能接一个新工作。我们考虑贪心，先按价值排序。然后把当前任务尽量往后排，但是不能超过$M-t[i]+1$，问题就转化成在$1$~$M-t[i]+1$之间最靠后的没接任务的天。然后把这个任务插入到当天去并统计答案。

如果暴力查找肯定会超时，我们考虑用线段树来维护。

预处理时把每天的权值设为天数，然后问题就转化成了区间最大值，每次插入一个新工作就把那一天的权值改成-1表示已经有任务了。

代码如下。

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
#define ll int
using namespace std;
const int MAXN = 100005;
int book[MAXN];
int N, M;

int n;
int a[MAXN]; 
struct tree { int l, r, dat; }t[MAXN << 2];

inline int ls(int p) { return p << 1; }
inline int rs(int p) { return ((p << 1) | 1); }

inline void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	if (l == r) { t[p].dat = a[l]; return ; }
	int mid = (l + r) >> 1;
	build(ls(p), l, mid);
	build(rs(p), mid + 1, r);
	t[p].dat = max(t[ls(p)].dat, t[rs(p)].dat);
}

inline void change(int p, int x, int v) {
	if (t[p].l == t[p].r) { t[p].dat = v; return ; }
	int mid = (t[p].l + t[p].r) >> 1;
	if (x <= mid) change(ls(p), x, v);
	else change(rs(p), x, v);
	t[p].dat = max(t[ls(p)].dat, t[rs(p)].dat);
}

inline int ask(int p, int l, int r) {
	if (l <= t[p].l && r >= t[p].r) return t[p].dat;
	int mid = (t[p].l + t[p].r) >> 1;
	int val = -inf;
	if (l <= mid) val = max(val, ask(ls(p), l, r));
	if (r > mid) val = max(val, ask(rs(p), l, r));
	return val;
}
struct TASK
{
	int t, v;
};
TASK task[MAXN];
bool cmp(TASK a, TASK b)
{
	if(a.v == b.v)
	{
		return a.t < b.t;
	}
	return a.v > b.v;
}
int ans;
int main()
{
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= N; i++)
	{
		scanf("%d%d", &task[i].t, &task[i].v);
	}
	sort(task + 1, task + 1 + N, cmp);
	for(int i=1;i<=M;i++)
	{
		a[i]=i;
	}
	build(1,1,M);
	for(int i = 1; i <= N; i++)
	{
		if(task[i].t>M)
		{
			continue;
		}
		int time = M - task[i].t + 1;
		int pos=ask(1,1,time);
		if(pos >= 1)
		{
			change(1,pos,-1);
			ans += task[i].v;
		}
	}
	printf("%d", ans);
	return 0;
}

Day 11 2019.8.11

如果奇迹有颜色，那么一定是橙色。’

哎，物理楼门前的树被砍了。

mwP5fx.jpg

串串算法+搜索分治贪心。

早上的串串算法讲的还蛮不错的。除了ExKMP以外好像都能懂，但是什么题也没做非常慌。

例如这道妮厨的愤怒我就不会。

mwPhkR.jpg

夕阳真美。

mwP4t1.jpg

Day 12 -12550820.115.12550820

相信集体是死亡宣告。

不断地做噩梦。

不如去死。

早上10点20才起来。宿舍里热的要命，除了我，只有寒蝉。

到教室强行骗10分，发现10分都没骗到。

晚上还是去订题好了。

要开始补知识点了。

目前紧急：

  • KMP Trie ACauto-machine
  • 线段树 树状数组 分块的完全应用
  • tarjan的其他用处
  • DP
  • BFS的优化们
  • 睡觉
  • 矩阵ksm
  • 迭代加深

没那么紧急但不要带回武汉：

  • 珂朵莉的完全应用
  • 自我认识
  • 网络流专题
  • 二分图之流
  • 码力
  • Splay
  • 记忆化搜索
  • 日语

还可以挺下去。这几天真是越来越颓了。晚上心情总是非常糟。主啊，请帮助我摆脱困境吧。

Day 13 2019.8.13

不要活在自己的阴影中。

有趣的一天。

题目都相当有意思。

T1 Rank

错误的题目。傻逼题。直接读入，从小到大排序，输出1到K。

T2 Seek

求又是字符串前缀又是字符串后缀的数，可以用hash水过去，就直接算出前缀的hash，再算出后缀的hash，然后$O(N)$判断输出就可以了。

这里给出一种KMP的做法。我们知道，KMP的next数组里面存的是前面这一串字符的前缀可以匹配上后缀的地方。所以最后一位的next数组就是最长的，而他指向的就是上一个可行的。把答案塞到栈里面，然后依次输出答案，最后加上总长度。

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN=400005;
char a[MAXN];
int _next[MAXN];
void Get_Next(char *s)
{
    int len = strlen(s);
    int i = 0, j = -1;
    _next[0] = -1;
    while (i < len)
    {
        if (j == -1 || s[i] == s[j])
        {
            i++;
            j++;
            _next[i] = j;
        }
        else
        {
            j = _next[j];
        }
    }
}
int ans[MAXN],top;
int main()
{
	scanf("%s",a);
	Get_Next(a);
	int len=strlen(a);
	int now=len;
	while(_next[now])
	{
		top++;
		ans[top]=_next[now];
		now=_next[now];
	}
	while(top)
	{
		printf("%d ",ans[top]);
		top--;
	}
	printf("%d",len);
	return 0;
}

Day 14 2019.8.14

奇迹不是免费的，如果你祈求了希望，也会散播出同等的绝望。

图论讲课日。有一些有意思的算法。

例如这个什么Boruvka，拥有在随机数据下十分优秀的时间复杂度，但是我问老师怎么卡，他说不晓得。

mwP5fx.jpg

所以不知道怎么卡的算法就是无敌算法。

二分图网络流还是懵逼。

mwPop6.jpg

这个人长得像沙霸。

mwPT1K.jpg

刮台风了，这台风真牛逼。

Day 15 2019.8.15

昨天你说过今天就做了吧

难得一天只有三道题。

T1 Vectors

前置知识：排序不等式

对于2个N维向量的内积，我们把这2个看做2个长度为N的数列，对于全排列的乘积之和，最小的就是其中一边的最小值乘另一边的最大值。

sort一遍，然后统计答案。记得开longlong

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
const int MAXN = 1500;
int a[MAXN], b[MAXN];
int ans;
bool cmp (int a,int b)
{
	return a>b;
}
signed main(void)
{
	int N;
	scanf("%lld", &N);
	for(int i = 1; i <= N; i++)
		scanf("%lld", a + i);
	for(int i = 1; i <= N; i++)
		scanf("%lld", b + i);
	sort(a+1,a+1+N,cmp);
	sort(b+1,b+1+N);
	for(int i=1;i<=N;i++)
	{
		ans+=a[i]*b[i];
	}
	printf("%lld",ans);
}

T2 Rules

数学题，求$N^2$的正因子个数，用约数公式即可。但是要写压位高精。所以我选择Python。

T3 Dolls

有趣的题目，可以对原图建模转化为二分图，然后贪心求解。

今天总算上了天文社。结果发现关了。

mwPHXD.jpg

日清的面真jb好吃啊。

mwPqne.jpg

Day 16 2019.8.16

我只是做了我能做的事，没有时间想将来。

真·休息日。

提前买了去珠海的火车票。

和xze myf wym一起去。

然后很早就起床了。总算吃到了奶油味的忌廉奶油面包（以前只吃过香辣牛肉味和芝士烟肉味的），配阿华田真尼玛绝了。

在门卫那里被卡住，通过打电话（工具人？）的方法，李教练帮我们出去了。

要赶公交车（几路来着？）去火车站。因为每30分钟才发一班车，当我们7:32赶出去时，本绝望的以为赶不上的。但是后面来的一辆竟然跑的飞快，我们在8点前就到了。

打了几把皇，赢了和myf的BO3。不久后火车就来了。在站台上发现了这个，sher笑死我了。

mwPL0H.jpg

mwPO7d.jpg

在火车上喝了倒数第二罐可乐。wym卡等好高啊。

为什么经济特区这么发达啊，感觉人家的近郊挺繁华的。

在某“近郊”下了车。找到了一家有元气森林水卖的店，买了这个月第一瓶和第二瓶桃子苏打水。

然后全身湿透的走了一段路（太阳真大，为什么不在街上安空调？？）

直到一家肠粉店，一路上发现了很多梗。

mwPjAA.jpg

蛋肉肠粉真好吃，和武汉的肠粉给人不同的感觉。

支持HKP。

mwPvtI.jpg

然后到了“新圆明园”，见识到了现实生活中的“竹鼠3元1只，10元3只”。

新圆明园里有一座叫板樟山的山。本以为是游客，结果却变成了登山客。一路上险象迭生，但是非常有趣，爬上了山顶，在观景台上喊了“NOIp2019RP++”（现在没用了，真讽刺），看到了一个非常牛逼的十阶幻方，算法真伟大。山路挺难走的，几乎每个人都差点掉下山过。

mwPxht.jpg

mwiS9P.jpg

mwip1f.jpg

路上把水喝光了，却遇到了好心人，送了2瓶水。如果打经典RPG就是触发随机事件了。

山顶真好，可以看到港珠澳大桥和市区。

mwi9c8.jpg

mwiCjS.jpg

mwiing.jpg

mwiFBQ.jpg

mwik7j.jpg

mwiEAs.jpg

mwiVNn.jpg

mwiZhq.jpg

走最后一段路，想了好多事情。仿佛看到曙光。

中午在山脚的一家面馆吃面，我吃的是肉酱牛腩捞公仔面。老板问我们四个：“你们四个都是捞的吗？”xswl。

坐公汽去海边。果然市区里都是无人售票（空调车1元好便宜）。

在沙滩上wym写了“I AK IOI”，我在后面补上了ACM/ICPC。

mwim90.jpg

mwin3V.jpg

mwiucT.jpg

然后就去火车站了，我发现原来是在关口建的，另一边就是澳门了。

可惜的是没赶上下午的火车，坐公汽回的中山。（那辆车很迷惑，从车站绕了一圈回来。）

下了好大的雨，然后在回去的路上看了日常。忽然有消息说NOIp取消了。我傻了。后来发现只是CCF的传统艺能。

mwiKjU.jpg

这鞋子xswl。

mwiQuF.jpg

生活真美好啊。

Day 17 2019.8.17

人们害怕改变，而我害怕人。

早上10分钟切掉了T1，结果换题了？？能10分钟切掉的确实水。

后来的T1 Paint

暴力，枚举每一种横着涂的方法，然后推出竖着涂的方法，在这些方法中取总数最小的值。

后来的T2 calc

比较有趣的DP。看题面。

鸡腿想到了一个很高（sha）明（bi）的运算符，那就是’!’，没错就是感叹号。他给了如下的定义：

1、$n!k$ = $n!(k-1) * (n-1)!k$ ($n> 0$ and $k > 0$)

2、$n!k = 1$ ($n = 0$)

3、$n!k = n$ ($k = 0$)

现在鸡腿告诉你n和k你能告诉他n!k的不同约数个数有多少个吗？只要对1,000,000,009取模就可以了哦！

就是说，给两个参，和递推式，让我们求结果的约数个数。我们可以发现，对后者有贡献的就只有值不为1的时候。对于每一个数，它的约数是所有它质因子的指数+1的乘积。我们定义$f[i][j]$是数i对于第j个质数的指数，$g[i][j][k]$是指$i!j$对于第k个质数的指数。做乘积运算时，指数是相加的。

那么转移方程:

$$g[i][j][k]=g[i][j-1][k]+g[i-1][j][k] $$

记得先打出质数表，对每个$n!0$赋初值。

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXTOT = 170, MAXN = 1005;
const int MOD = 1000000009;
int prime[MAXTOT];
int f[MAXN][MAXN], g[MAXN][170][MAXTOT];
long long ans = 1;
int N, K, _count;
void Get_Prime()
{
	for(int i = 2; i <= N; i++)
	{
		int flag = 0;
		for(int j = 2; j < i; j++)
		{
			if(i % j == 0)
			{
				flag = 1;
				break;
			}
		}
		if(!flag)
		{
			_count++;
			prime[_count] = i;
		}
	}
}

void Get()
{
	for(int i = 1; i <= N; i++)
	{
		int x = i;
		for(int j = 1; j <= _count; j++)
		{
			while(x % prime[j] == 0)
			{
				f[i][j]++;
				x /= prime[j];
			}
		}
	}
}

int main()
{
	scanf("%d%d", &N, &K);
	Get_Prime();
	Get();
	for(int i = 1; i <= N; ++i)
	{
		for(int j = 1; j <= _count; ++j)
		{
			g[i][0][j] = f[i][j];
		}
	}
	for(int i = 1; i <= N; ++i)
	{
		for(int j = 1; j <= K; ++j)
		{
			for(int l = 1; l <= _count; ++l)
			{
				g[i][j][l] = (g[i - 1][j][l] + g[i][j - 1][l]) % MOD;
			}
		}
	}
	for(int i = 1; i <= _count; ++i)
	{
		ans = (ans * (g[N][K][i] + 1) % MOD) % MOD;
	}
	printf("%lld", ans);
	return 0;
}

后来的T3 slope

极角排序，转坐标系瞎搞，我不会。暂时咕咕咕。

松回来了，给我们带了狗屎糖。（疑惑）

mwi1HJ.jpg

今天真要求我们换教室，换寝室，事情好多好烦。

喝掉了最后一罐可乐。

mwilB4.jpg

还差点搬出去住了。思考后还是算了….

换了个女宿管。

Day 18 2019.8.18

我们一日日所读过的日常，实际上可能是接连不断的奇迹。

其实睡得还比较踏实，尽管睡得很晚。

今天打了A组，还算不错的成绩，主要是A了T2很开心。

T1 Backpack

超大容量的完全背包。

可以用正确性不高的贪心水过，或者用我不会的矩阵快速max。

我的代码是贪心+背包。

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
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
struct NODE
{
	int a,w;
	double yep;
};
NODE node[10000005];
int T, M,  dp[1000005], maxx, i, j;
int ans;
bool cmp(NODE c,NODE b)
{
	return c.yep>b.yep;
}
signed main(void)
{
	freopen("backpack.in","r",stdin);
	freopen("backpack.out","w",stdout);
	scanf("%lld%lld", &M, &T);
	for(i = 1; i <= M; i++)
	{
		scanf("%lld%lld",&node[i].w,&node[i].a);
		node[i].yep=node[i].a*1.00000/node[i].w;
	}
	sort(node+1,node+1+M,cmp);
	if(T>500)
	{
		ans+=(T-500)/node[1].w*node[1].a;
		T-=(T-500)/node[1].w*node[1].w;
	}
	for(i = 1; i <= M; i++)
	{
		for(j = node[i].w; j <= T; j++)
		{
			dp[j] = max(dp[j], dp[j - node[i].w] + node[i].a);
			if(dp[j] > maxx)
			{
				maxx = dp[j];
			}
		}
	}
	printf("%lld", ans+dp[T]);
}

T2 Median

给两个非严格单调上升序列，N次操作，操作有修改和询问。

  • 修改是直接修改一个序列的某一位数，但不破坏单调性。
  • 询问是求第一个序列的一段区间和第二个序列的一段区间合并后的中位数（保证是奇数个数）。

考虑单调性。

因为是单调不下降的，我们对所求的区间的前总数一半的数进行比较，小的那边对答案没有贡献，直接舍弃。然后递归下去直到找到答案。
时间复杂度$O(M\log N)$。

具体实现有细节，看代码吧。

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
//区间是非严格单调递增
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 500005;
int N, M;
int a[MAXN], b[MAXN];
int ans;
int aim;
int cur;
void _Binary_Search(int l1, int r1, int l2, int r2, int goal)
{
	if(r1<l1)
	{
		ans=b[l2+goal-1];
		return;
	}
	if(r2<l2)
	{
		ans=a[l1+goal-1];
		return;
	}
	if(goal==1)
	{
		ans=min(a[l1],b[l2]);
		return;
	}
	int mid1=min(l1+(goal>>1)-1,r1);
	int mid2=min(l2+(goal>>1)-1,r2);
	if(a[mid1]>=b[mid2])
	{
		_Binary_Search(l1,r1,mid2+1,r2,goal-(mid2-l2+1));
	}
	else
	{
		_Binary_Search(mid1+1,r1,l2,r2,goal-(mid1-l1+1));
	}
}



int main()
{
//	freopen("median.in","r",stdin);
//	freopen("median.out","w",stdout);
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= N; i++)
	{
		scanf("%d", a + i);
	}
	for(int i = 1; i <= N; i++)
	{
		scanf("%d", b + i);
	}
	while(M--)
	{
		int opt;
		scanf("%d", &opt);
		if(opt == 1)
		{
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			if(!x)
			{
				a[y] = z;
			}
			else
			{
				b[y] = z;
			}
		}
		if(opt == 2)
		{
			cur = 0;
			ans = 0;
			int l11, r11, l22, r22;
			scanf("%d%d%d%d", &l11, &r11, &l22, &r22);
			aim = ((r11 - l11 + 1) + (r22 - l22 + 1)) >> 1;
			aim++;
			_Binary_Search(l11, r11, l22, r22, aim);
			printf("%d\n", ans);
		}
	}
	return 0;
}

T3 Sequence

数学题。啥？啥是积性函数？怎么做啊？我在哪里？我是谁？HOME RUN！！！！

lcx回来了。

不出意外晚上还要打AtCoder。

A Red or Not

判断数字是否大于3200

B Resistors in Parallel

求所有数的倒数的和的倒数。

C Alchemist

合并果子简单版。

D Ki

在每个节点上打Tag，DFS传递下去。或用树链剖分。

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 400005;
int head[MAXN], lazy[MAXN];
struct EDGE
{
	int _next, to;
};
EDGE edge[MAXN];
int _count;
int ans[MAXN];
void Add_Line(int a, int b)
{
	_count++;
	edge[_count]._next = head[a];
	edge[_count].to = b;
	head[a] = _count;
}

void DFS(int NowNode,int fa,int temp)
{
	ans[NowNode]=temp+lazy[NowNode];
	for(int i=head[NowNode];i;i=edge[i]._next)
	{
		int NextNode=edge[i].to;
		if(NextNode==fa)
		{
			continue;
		}
		DFS(NextNode,NowNode,temp+lazy[NowNode]);
	}
}

int main()
{
	int N, M;
	scanf("%d%d", &N, &M);
	for(int i = 1; i < N; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		Add_Line(a, b);
		Add_Line(b, a);
	}
	for(int i = 1; i <= M; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		lazy[a] += b;
	}
	DFS(1,0,0);
	for(int i=1;i<=N;i++)
	{
		printf("%d ",ans[i]);
	}
	return 0;
}

然后被松叫出去了。。E题没做啊！！！

Day 19 2019.8.19

吃泡面最舒服的一刻，感觉到整个宇宙都在里面。

上午数论听的听懂的。

敲了线性基的模板。

下午大概是第三次听莫比乌斯和狄利克雷，果然没听懂。

过了昨天的题。

日清真是太好吃了。

Day 20 2019.8.20

一定一定活下去。

昨天讲的东西竟然今天就考了。

T1 Travle

$O(N^4)$水过。将观赏值相近的连一条有向边。然后暴力枚举走边方案就可以了。其实是错误的时间复杂度，但是数据太弱了，所以完全没有可能跑满，甚至效率还非常的高。

T2 Dream

先推出M以内。

看下面这个式子$f(x)=\sum\limits_{i=1}^{m}f(x-i)*f(i)$

然后矩阵ksm即可。

T3 Count

类欧几里得算法模板题。

看这个证明吧。yes

Day 21 2019.8.21

然后，黑夜降临。

GMOJ的评测姬可玩。

T1 Ratio

枚举每个参与组成的点。然后跑kruskal。注意精度问题，比较简单。

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 20;
int _map[MAXN][MAXN];
int father[MAXN];
int N, M;
int _count;
int book[MAXN];
int sumup, sumdown;
int sum1,sum2;
int _array[MAXN];
int w[MAXN];
struct EDGE
{
	int from, to, w;
};
EDGE edge[MAXN*MAXN];

void _Init()
{
	for(int i = 1; i <= N; i++)
	{
		father[i] = i;
	}
	sumdown=0;
	sumup=0;
}

int Find(int x)
{
	if(x == father[x])
	{
		return x;
	}
	return father[x] = Find(father[x]);
}

bool Judge(int x, int y)
{
	int r1 = Find(x);
	int r2 = Find(y);
	if(r1 == r2)
	{
		return true;
	}
	return false;
}

void Union(int x, int y)
{
	int r1 = Find(x);
	int r2 = Find(y);
	if(r1 == r2)
	{
		return;
	}
	father[r1] = r2;
}

void Kruskal()
{
	_Init();
	int dot = 0;
	for(int i = 1; i <= N; i++)
	{
		if(book[i])
		{
//			printf("%d ",i);
			sumdown += w[i];
		}
	}
	for(int i = 1; i <= _count; i++)
	{
		if(!book[edge[i].from] || !book[edge[i].to])
		{
			continue;
		}
		if(!Judge(edge[i].from, edge[i].to))
		{
			Union(edge[i].from, edge[i].to);
			sumup += edge[i].w;
			dot++;
		}
		if(dot == M - 1)
		{
			break;
		}
	}
//	printf("%d %d %lf ",sumup,sumdown,(double)1.00000 * sumup / sumdown);
	if(sum1*sumdown>=sum2*sumup)
	{
		for(int i = 1; i <= N; i++)
		{
			_array[i] = book[i];
		}
		sum1=sumup;
		sum2=sumdown;
	}
//	putchar('\n');
}


void DFS(int now, int cur)
{
	if(cur == M)
	{
		Kruskal();
		return;
	}
	if(now == N)
	{
		return;
	}
	DFS(now + 1, cur);
	book[now + 1] = 1;
	DFS(now + 1, cur + 1);
	book[now + 1] = 0;
}

bool cmp(EDGE a, EDGE b)
{
	return a.w < b.w;
}

int main()
{
	freopen("ratio.in","r",stdin);
	freopen("ratio.out","w",stdout);
	sum1=999999;
	sum2=1;
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= N; i++)
	{
		scanf("%d", w + i);
	}
	for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <= N; j++)
		{
			scanf("%d", &_map[i][j]);
			if(i == j)
			{
				continue;
			}
			_count++;
			edge[_count].from = i;
			edge[_count].to = j;
			edge[_count].w = _map[i][j];
		}
	}
	sort(edge + 1, edge + 1 + _count, cmp);
	DFS(0, 0);
	for(int i = 1; i <= N; i++)
	{
		if(_array[i])
		{
			printf("%d ", i);
		}
	}
	fclose(stdin); fclose(stdout);
	return 0;
}

T2 Company

考场上做出了比较正确的DP，但是并不完全正确。

我们设$f[i][j]$表示前$i$个员工做j个1号项目，能在规定时间内完成多少的2号项目。

显而易见的。可以推出DP转移方程。

$$f[i][j]=max(f[i][j],f[i-1][j-k]+(time-k*a[i])/b[i]) $$

于是可以二分time。每次判断当前的time满不满足要求。

即

$f[N][M]\ge M$

如果满足就更新答案。

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN=105;
int N,M,l,r;
int ans=INF;
int a[MAXN],b[MAXN];
int dp[MAXN][MAXN];
int Check(int l,int r)
{
	if(l>r)
	{
		return l;
	}
	int x=(l+r)>>1;
	for(int i=0;i<=N;i++)
	{
		for(int j=1;j<=M;j++)
		{
			dp[i][j]=-INF;
		}
		dp[i][0]=0;
	}
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<=M;j++)
		{
			for(int k=0;k<=j;k++)
			{
				if(k*a[i]<=x)dp[i][j]=max(dp[i][j],dp[i-1][j-k]+(x-k*a[i])/b[i]);
			}
		}
	}
	if(dp[N][M]>=M)
	{
		return Check(l,x-1);
	}
	return Check(x+1,r);
}

int main()
{
	freopen("company.in","r",stdin);
	freopen("company.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d",a+i,b+i);
	}
	l=0,r=10000000;
	ans=Check(l,r); 
	printf("%d",ans);
    return 0;
}

T3 Warp

这题的难点是建图。

学到了三维的距离公式。

$$dis=\sqrt{(a.x-b.x)^2+(a.y-b.y)^2+(a.z-b.z)^2}$$

然后注意dis还要减去两个星云之间的半径。

在建好的图上跑一遍Floyd。

输出答案即可，注意精度。

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN=105;
int N;
struct GALAXY
{
	int x,y,z,r;	
};
GALAXY fhk[MAXN];

double dis[MAXN][MAXN];

void _Init()
{
	memset(dis,INF,sizeof(dis));
}

double Euc(GALAXY a,GALAXY b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z))-a.r-b.r>0?sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z))-a.r-b.r:0;
}
int main()
{
	freopen("warp.in","r",stdin);
	freopen("warp.out","w",stdout);
	while(1)
	{
		_Init();
		scanf("%d",&N);
		if(N==-1)
		{
			break;
		}
		for(int i=1;i<=N;i++)
		{
			scanf("%d%d%d%d",&fhk[i].x,&fhk[i].y,&fhk[i].z,&fhk[i].r);
		}
		scanf("%d%d%d",&fhk[N+1].x,&fhk[N+1].y,&fhk[N+1].z);
		fhk[N+1].r=0;
		scanf("%d%d%d",&fhk[N+2].x,&fhk[N+2].y,&fhk[N+2].z);
		fhk[N+2].r=0;
		for(int i=1;i<=N+2;i++)
		{
			for(int j=1;j<=N+2;j++)
			{
				dis[i][j]=Euc(fhk[i],fhk[j]);
			}
		}
		for(int k=1;k<=N+2;k++)
		{
			for(int i=1;i<=N+2;i++)
			{
				for(int j=1;j<=N+2;j++)
				{
					dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
				}
			}
		}
		printf("%d\n",(int)(dis[N+1][N+2]*10+0.5));
	}
    return 0;
}

T4 Bus

在最短路上一个个爆破点，然后递归跑最短路。

按理来说，暴力找点可以过。是$O(?)$级别的算法。

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;

const int MAXN = 6000;
const int MAXM = 500000;
int _array[MAXM << 2], head[MAXN], dis[MAXN], vis[MAXN], book[MAXN], pre[MAXN];
int _count;
int N, M, K;
int ans = INF;
struct EDGE
{
	int _next, to;
};

EDGE edge[MAXN];

void Add_Line(int a, int b)
{
	_count++;
	edge[_count]._next = head[a];
	edge[_count].to = b;
	head[a] = _count;
}

void _Init()
{
	memset(dis, INF, sizeof(dis));
	memset(vis, 0, sizeof(vis));

}

bool SPFA(int S, int T)
{
	_Init();
	int l = 0, r = 1;
	_array[r] = S;
	vis[S] = 1;
	dis[S] = 0;
	while(l < r)
	{
		l++;
		int NowNode = _array[l];
		vis[NowNode] = 0;
		for(int i = head[NowNode]; i; i = edge[i]._next)
		{
			int NextNode = edge[i].to;
			if(book[NextNode])
			{
				continue;
			}
			if(dis[NextNode] > dis[NowNode] + 1)
			{
				dis[NextNode] = dis[NowNode] + 1;
				pre[NextNode]=NowNode;
				if(!vis[NextNode])
				{
					r++;
					_array[r] = NextNode;
					vis[NextNode] = 1;
				}
			}
		}
	}
	if(dis[T] > K)
	{
		return true;
	}
	return false;
}

void DFS(int cur)
{
	if(cur >= ans)
	{
		return;
	}
	if(SPFA(1, N))
	{
		ans = min(cur, ans);
		return;
	}
	int now=N;
	int t[MAXN]={0},cnt=0;
	while(now!=1)
	{
		now=pre[now];
		t[++cnt]=now;
	}
	for(int i=1;i<cnt;i++)
	{
		book[t[i]]=1;
		DFS(cur+1);
		book[t[i]]=0;
	}
	return;
}

int main()
{
	freopen("bus.in", "r", stdin);
	freopen("bus.out", "w", stdout);
	scanf("%d%d%d", &N, &M, &K);
	for(int i = 1; i <= M; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		Add_Line(a, b);
	}
	DFS(0);
	printf("%d", ans);
	return 0;
}

今天有一件令人开心的事。

苏打绿要回归了。

Day 22 2019/8/22

到第七日、神造物的工已经完毕、就在第七日歇了他一切的工、安息了。

神赐福给第七日、定为圣日、因为在这日神歇了他一切创造的工、就安息了。

今天是最后一天了。

让上帝决定一切吧。

Day 0x3f 2019/9/11

心血来潮想写后记了。最近有很多事情发生了，有很大的触动，身边的人是什么样的状态。我有些迷茫。自己到底会变成什么样子呢。OI和whk的日子历历在目，再过三年就要成年。那时的我是什么样子？唉唉，日记也不再写了，果然还是懒了吧！我的人生掌控在自己手上，一定要活下去，做更多想做的事情。

纪中，果然是一个很值得回忆的地方呢。