bef-> NO.39

Veröffentlicht am

P5002 专心OI - 找祖先

题目背景

最后一个点15pts

Imakf是一个小蒟蒻，他最近刚学了LCA，他在手机APP里看到一个游戏也叫做LCA就下载了下来。

题目描述

这个游戏会给出你一棵树，这棵树有NN个节点，根结点是RR，系统会选中MM个点P_1,P_2…P_MP1,P2…PM，要Imakf回答有多少组点对(u_i,v_i)(ui,vi)的最近公共祖先是P_iPi。Imakf是个小蒟蒻，他就算学了LCA也做不出，于是只好求助您了。

Imakf毕竟学过一点OI,所以他允许您把答案模 (10^9+7)(109+7)

输入输出格式

输入格式：

第一行 N , R , MN,R,M

此后N-1N−1行 每行两个数a,ba,b 表示a,ba,b之间有一条边

此后11行 MM个数 表示P_iPi

输出格式：

MM行，每行一个数，第ii行的数表示有多少组点对(u_i,v_i)(ui,vi)的最近公共祖先是P_iPi

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
7 1 3
1 2
1 3
2 4
2 5
3 6
3 7
1 2 4

输出样例#1：

1
2
3
31
7
1

说明

img

题解

一道D1T1水平的结论题成功找错结论调了半天。

我连最基本的组合数学都不会了呢。

今天上午的考试大概也是彻底失望了。

假如一道编程复杂度很小的结论题出现错误，请检查结论是否有误而不是调试程序
以及尽量把结论化简，往往能看出你的错误

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 500005
#define ll long long
#define mod 1000000007
int n , m , rt , head[maxn] , cnt;
struct edge{
	int next , to ;
}e[maxn*2]; 
ll f[maxn] , sz[maxn] , sq[maxn];
inline void add(int x , int y)
{
	e[++cnt].next = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
void dfs(int x , int fx)
{
	sz[x] = 1 ;
	int chd = 0;
	for(int i = head[x] ; i ; i = e[i].next){
		int v = e[i].to;
		if(v == fx)	continue;
		dfs(v , x);
		++chd;
		sz[x] += sz[e[i].to];
		sq[x] += sz[e[i].to] * sz[e[i].to];
	}
	f[x] += (sz[x] << 1) - 1; 
	f[x] += ((sz[x] - 1) * (sz[x] - 1)) - sq[x];
}
int main()
{
	scanf("%d%d%d",&n,&rt,&m);
	for(int i = 1 ; i <= n - 1 ; ++i){
		int x , y;
		scanf("%d%d",&x,&y);
		add(x,y) , add(y,x);
	}
	dfs(rt,rt);
	for(int i = 1 ; i <= m ; ++i){
		int x;
		scanf("%d",&x);
		printf("%lld\n",f[x] % mod);
	}
}

P5004 专心OI - 跳房子

题目背景

数据已经重做

Imakf有一天参加了PINO 2017 PJ组，他突然看见最后一道题

img

他十分蒟蒻，写不出来

而如今他还是一个蒟蒻，他又看见一道题

img

他还是写不出来，于是便来请教您

题目描述

您有NN个格子，排成一行，从左往右编号为1,2,…,N1,2,…,N。您站在11号格子的左边，开始从左往右跳，跳到NN号格子右侧为止。由于您是一位成功的OIerOIer，您自然长得很胖，但您的力量也非常大！这使得您跳一次，当前格子到目标格子中间必须至少空出来MM格，但您可以跳无数格远！

您认为这么跳太没意思了，于是便想计算出有多少种方案可以跳完全程。由于方案可能过多，您会输出方案数量模(10^9+7)(109+7)的值

方案指经过格子编号的顺序不同，具体可见说明

题目简化一下……把NN个无色格子排成一行，可以把某些格子染成黑色，但两个黑色格子之间必须至少有MM个无色格子，求方案数

输入输出格式

输入格式：

第一行 N,MN,M

输出格式：

跳完全程的方案模(10^9+7)(109+7)

输入输出样例

输入样例#1：

1
5 1

输出样例#1：

1
13

输入样例#2：

1
6 2

输出样例#2：

1
13

样例一

luogu

样例二

luogu

绿色格子为您站在上面过的格子

对于100%的数据：

题解

一道难度较低的递推+矩阵加速

显然用加法原理分类讨论合并方案数可得到

前m+1项使用搜索解决，后面即可构造矩阵递推。

写的比较成功的一道题。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxm 21
#define mod 1000000007
#define ll long long
ll f[maxm << 1] , n , m;
int dfs(int now , int fin , int sta)
{
	if(now == fin + 1)	return 1;
	if(!sta)	return dfs(now + 1 , fin , m) + dfs(now + 1 , fin , sta);
	else	return dfs(now + 1 , fin , sta - 1);	
}
struct Matrix
{
	ll p[maxm][maxm] , n , m;
	ll* operator[](const int& x){
		return p[x];
	}
	inline void unit(){
		for(int i = 1 ; i <= 20 ; ++i)
			p[i][i] = 1;
	}
	Matrix(){
		n = m = 20;
		for(int i = 0 ; i <= n ; ++i)	
			for(int j = 0 ; j <= m ; ++j)
				p[i][j] = 0;
	}
	inline void print(){
		for(int i = 1 ; i <= n ; ++i){
			for(int j = 1 ; j <= m ; ++j)
				printf("%lld ",p[i][j]);
			putchar(10);
		}
	}
}fr , tr;
Matrix operator * (Matrix& x , Matrix& y)
{
	Matrix c;
	if(x.m != y.n)	return c;
	c.n = x.n , c.m = y.m;
	for(int i = 1 ; i <= c.n ; ++i)
		for(int j = 1 ; j <= c.m ; ++j)
			for(int k = 1 ; k <= x.m ; ++k)
				(c[i][j] += x[i][k] * y[k][j]) %= mod;
	return c;
}
Matrix pow(Matrix& x , ll y)
{
	Matrix ans , base = x;
	ans.n = ans.m = x.m;
	ans.unit();
	while(y){
		if(y&1)		ans = ans * base;
		base = base * base;
		y /= 2;
	}
	return ans;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i = 1 ; i <= m + 1; ++i)
		f[i] = dfs(1 , i , 0);
	fr.n = 1 , fr.m = m + 1;
	for(int i = 1 ; i <= m + 1 ; ++i){
		fr[1][m-i+2] = f[i];
	}
	if(n <= m + 1){
		printf("%lld\n",f[n]%mod);
		return 0;
	}
	tr.n = tr.m = m + 1;
	tr[1][1] = tr[m + 1][1] = 1;
	for(int i = 1 ; i <= m ; ++i)
		tr[i][i+1] = 1;
	tr = pow(tr , n - m - 1);
	Matrix ans = fr * tr;
	printf("%lld",ans[1][1]);
}

P5005 中国象棋 - 摆上马

题目背景

相信自己的做法 大喊一声 I won’t MLE！您就会过这道题

Imakf玩腻了国际象棋，决定玩一玩中国象棋

他发现中国象棋的马和国际象棋的马有所不同，他意识到这又是一个十分有价值的问题，于是他又准备摆一摆马了

题目描述

Imakf有一个XX行YY列的棋盘，还有很多的马(你可以认为有无数个)。现在在棋盘上摆上马（或者不摆），求任何马无法攻击另一匹马的方案数

中国象棋的马和国际象棋的马不同。

img

注意：实际问题中没有兵！！！

当然由于方案可能过多，请输出对(10^9+7)取模的值

输入输出格式

输入格式：

第一行 X,YX,Y

输出格式：

方案对(10^9+7)取模的值

输入输出样例

输入样例#1：

1
1 1

输出样例#1：

1
2

输入样例#2：

1
3 3

输出样例#2：

1
145

说明

对于 100% 的数据，有X\leq100,Y\leq6X≤100,Y≤6

对于 20% 的数据，有X,Y\leq6X,Y≤6

对于另外 20% 的数据，有X\leq20X≤20

对于样例1，可以选择不摆或者摆

对于样例2，无法解释……方案太多啦！

题解

眼瞎脑残型选手又在写了正解之后为了智障错误调了2个多小时，考场必爆零。

一开始直接位运算判断后来发现不对改成一个复杂些的判断函数，结果忘了改最初两行dp时候的check。。。

思路比较简单，类似炮兵阵地的转移即可。注意滚动数组优化空间

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 105
#define mod 1000000007
#define ll long long 
int f[2][1<<6][1<<6] , n , m;
void write(int x)
{
	if(!x)	return ;
	write(x >> 1);
	putchar((x&1)+48);
}
bool check1(int s , int t)
{
	for(int i = 0 ; i < m ; ++i){
		int v = 1 << i;
		if(s & v){
			if(!(s & (v << 1))){
				if(t & (v << 2))	return true;
			}
			if(!(s & (v >> 1))){
				if(t & (v >> 2))	return true;
			}
		}
		if(t & v){
			if(!(t & (v << 1))){
				if(s & (v << 2))	return true;
			}
			if(!(t & (v >> 1))){
				if(s & (v >> 2))	return true;
			}
		}
	}
	return false;
}
bool check2(int s , int mid , int t)
{
	for(int i = 0 ; i < m ; ++i){
		int v = 1 << i;
		if(s & v){
			if((i < m - 1) && (t & (v << 1)) && (!(mid & (v << 1)) || !(mid & v)))	return true;
			if((i > 0) && (t & (v >> 1)) && (!(mid & (v >> 1)) || !(mid & v)))	return true;
		}
	}
	return false;
}
int main()
{
	scanf("%d%d",&n,&m);
	int S = (1 << m) - 1;
	for(int i = 0 ; i <= S ; ++i)
		f[1&1][i][0] = 1;
	for(int i = 0 ; i <= S ; ++i)
		for(int j = 0 ; j <= S ; ++j){
			if(check1(i,j))	continue;
			(f[2&1][i][j] += f[1&1][j][0]) %= mod;
		}
	if(n == 1){
		int ans = 0;
		for(int i = 0 ; i <= S ; ++i)
			ans += f[1][i][0];
		printf("%d",ans);
		return 0;
	}
	if(n == 2){
		ll ans = 0 ;
		for(int i = 0 ; i <=  S ; ++i)
			for(int j = 0 ; j <= S ; ++j)
				(ans += f[2&1][i][j]) %= mod;
		printf("%lld",ans);
		return 0;
	}
	for(int i = 3 ; i <= n ; ++i){
		std::memset(f[i&1],0,sizeof(f[i&1]));
		for(int j = 0 ; j <= S ; ++j)
			for(int k = 0 ; k <= S ; ++k){
				if(check1(j,k))	continue;
				for(int t = 0 ; t <= S ; ++t){
					if(check2(j,k,t))	continue;
					if(check1(k,t))	continue;
					(f[i&1][j][k] += f[(i-1)&1][k][t]) %= mod;
				}
			}
	}
	ll ans = 0;
	for(int i = 0 ; i <= S ; ++i)
		for(int j = 0 ; j <= S ; ++j)
			(ans += f[n&1][i][j]) %= mod;
	printf("%lld",ans);
}

[SDOi2012]Longge的问题

题目背景

SDOi2012

题目描述

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。

输入输出格式

输入格式：

一个整数，为N。

输出格式：

一个整数，为所求的答案。

输入输出样例

输入样例#1：

1
6

输出样例#1：

1
15

说明

对于60%的数据，0<N<=2^16

对于100%的数据，0<N<=2^32

题解

很简单的数论题嘛

答案显然随便变形一下就出来了

时间复杂度

Code:

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define ll long long
ll ans , n;
inline ll phi(ll x)
{
	ll ans = x;
	for(long long i = 2 ; i * i <= n ; ++i){
		if(!(x % i))	ans = ans / i * (i-1);
		while(!(x%i))	x /= i; 
	}
	if(x > 1){
		ans = ans / x * (x - 1);
	}
	return ans;
}
inline ll f(ll n)
{
	long long i;
	for(i = 1 ; i * i < n ; ++i){
		if(!(n % i))
			ans += i * phi(n / i) + (n / i) * phi(i);
	}
	if(i * i == n)	ans += i * phi(n / i);
	return ans;
}
int main()
{
	scanf("%lld",&n);
	printf("%lld",f(n));
}

[COCI2017-2018#5] Pictionary

题目描述

There is a planet, in a yet undiscovered part of the universe, with a country inhabited solely by mathematicians. In this country, there are a total of N mathematicians, and the interesting fact is that each mathematician lives in their own city. Is it also interesting that no two cities are connected with a road, because mathematicians can communicate online or by reviewing academic papers. Naturally, the cities are labeled with numbers from 1 to N.

Life was perfect until one mathematician decided to write an academic paper on their smartphone. The smartphone auto-corrected the word “self-evident” to “Pictionary” and the paper was published as such. Soon after, the entire country discovered pictionary and wanted to meet up and play, so construction work on roads between cities began shortly. . The road construction will last a total of M days, according to the following schedule: on the first day, construction is done on roads between all pairs of cities that have M as their greatest common divisor. On the second day, construction is done on roads between all pairs of cities that have M-1 as their greatest common divisor, and so on until the M^{th}Mth day when construction is done on roads between all pairs of cities that are co-prime. More formally, on the i^{th}ith day, construction is done on roads between cities a and b if gcd(a, b) = M-i+1M−i+1.

Since the mathematicians are busy with construction work, they’ve asked you to help them determine the minimal number of days before a given pair of mathematicians can play pictionary together.

输入输出格式

输入格式：

The first line of input contains three positive integers N, M and Q (1 ≤ N , Q ≤ 100 000, 1 ≤ M ≤ N ), the number of cities, the number of days it takes to build the roads, and the number of queries.

Each of the following Q lines contains two distinct positive integers A and B (1 ≤ A , B ≤ N ) that denote the cities of the mathematicians who want to find out the minimal number of days before they can play pictionary together.

输出格式：

The i^{th}ith line must contain the minimal number of days before the mathematicians from the i^{th}ith query can play pictionary together.

输入输出样例

输入样例#1：

1
2
3
4
8 3 3
2 5
3 6
4 8

输出样例#1：

1
2
3
3
1
2

输入样例#2：

1
2
25 6 1
20 9

输出样例#2：

1
4

输入样例#3：

1
2
3
9999 2222 2
1025 2405
3154 8949

输出样例#3：

1
2
1980
2160

说明

In test cases worth 40% of total points, it will hold N ≤ 1000, Q ≤ 100 000.

Clarification of the first test case:

On the first day, road (3, 6) is built. Therefore the answer to the second query is 1.

On the second day, roads (2, 4), (2, 6), (2, 8), (4, 6) and (6, 8) are built. Cities 4 and 8 are now connected (it is possible to get from the first to the second using city 6).

On the third day, roads between relatively prime cities are built, so cities 2 and 5 are connected.

Clarification of the second test case:

On the second day, road (20, 15) is built, whereas on the fourth day, road (15, 9) is built. After the fourth day, cities 20 and 9 are connected via city 15.

题解

一道相当好的贪心题，难度适合放在D2T2。

而这种好题最终总是以我做不出来，其他人都做出来看了题解为终结。

这道题我倒是想出一个暴力（似乎全场都想出来了暴力吧2333）

40分做法：

考虑什么情况下两个数能被更早联通。

显然是一个数作为中间桥梁，这个中间数与两个数的gcd中较小的也比这两个直接gcd要打。

这里面显然包含了最短路中松弛的思想。因此我们任意两数以gcd为边，Floyd任意两点最短距离查询。

时间复杂度

满分做法：

为什么我考试不观察一下转移的方程呢。。

这不就是在连完图后使得两点间最小边最大吗。。不就是最大生成树吗。。

看出了这点唯一剩下的问题就是如何优化建图（建树）

这张图上的边权是有道理可循的，显然x与它倍数之间连的边权是x自己，而没有这种关系的数对可以视为它们分别向gcd连边权为gcd的边，这个数对之间的广义距离（即当前答案）还是不变。

不难想出从m开始倒着枚举（即倍数）加与当前枚举值相同边权的边，Kruskal的最大生成树即可，这个加边的过程已经优化到了

因此最后只需要查询最大生成树树链上最小边，HPD可以做到常数极小的

总结：从松弛看到最短路到更本质的两点间最小边，进而应用最大生成树，本题核心之一。

如何避免

枚举点对，从建图的边中找到哪些是可能最后在最大生成树上的，哪些边是冗余的（任意点对之间连边均可转换成gcd向它们连边），完成最后的时间复杂度优化，本题的难点。

最终时间复杂度

前者为最大生成树复杂度，后者为查询总复杂度。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
#define INF 0x7ffffff
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define pushup(x)	minn[x] = std::min(minn[ls(x)] , minn[rs(x)])
int head[maxn] , cnt , n , m , q , val[maxn] , uf[maxn];
struct edge{
	int next , to , dis;
}e[maxn*2];
struct HPD
{
	int id[maxn] , top[maxn] , sz[maxn] , hs[maxn] , f[maxn] , dep[maxn] , minn[maxn<<2] , idx , v[maxn];
	void dfs1(int x , int fx){
		f[x] = fx;
		dep[x] = dep[fx] + 1;
		sz[x] = 1;
		for(int i = head[x] ; i ; i = e[i].next){
			int v = e[i].to;
			if(v == fx)	continue;
			dfs1(v , x);
			sz[x] += sz[v];
			if(sz[v] > sz[hs[x]])	hs[x] = v;
		}
	}
	void dfs2(int x , int topv)
	{
		top[x] = topv;
		id[x] = ++idx;
		v[id[x]] = val[x];
		if(!hs[x])	return;
		dfs2(hs[x] , topv);
		for(int i = head[x] ; i ; i = e[i].next){
			int v = e[i].to;
			if(v == f[x] || v == hs[x])	continue;
			dfs2(v , v);
		}
	}
	void build(int l , int r , int node)
	{
		if(l == r){
			minn[node] = v[l];
			return;
		}
		int mid = l + r >> 1;
		build(l , mid , ls(node));
		build(mid + 1 , r , rs(node));
		pushup(node);
	}
	int query(int L , int R , int l , int r , int node)
	{
		if(L <= l && r <= R){
			return minn[node];
		}
		int mid = l + r >> 1 , ans = INF;
		if(L <= mid)	ans = std::min(ans , query(L , R , l , mid , ls(node)));
		if(R > mid)		ans = std::min(ans , query(L , R , mid + 1 , r , rs(node)));
		return ans;
	}
	int queryMin(int x , int y)
	{
		int ans = INF;
		while(top[x] != top[y]){
			while(dep[top[x]] < dep[top[y]])	std::swap(x,y);
			ans = std::min(ans , query(id[top[x]] , id[x] , 1 , n , 1));
			x = f[top[x]];
		}
		if(dep[x] < dep[y])	std::swap(x,y);
		ans = std::min(ans , query(id[y] + 1, id[x] , 1 , n , 1));
		return ans ;
	}
}tr;
inline void add(int x,  int y , int dis)
{
	e[++cnt].next = head[x];
	e[cnt].to = y;
	e[cnt].dis = dis;
	head[x] = cnt;
}
int find(int x)
{
	if(uf[x] != x)	return uf[x] = find(uf[x]);
	return uf[x];
}
void dfs(int x , int fx , int d)
{
	val[x] = d;
	for(int i = head[x] ; i ; i = e[i].next){
		if(e[i].to != fx)
			dfs(e[i].to , x , e[i].dis);
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i = 1 ; i <= n ; ++i)
		uf[i] = i;
	for(int i = m ; i >= 1 ; --i){
		for(int j = 2 * i ; j <= n ; j += i){
			if(find(i) != find(j))
				uf[find(i)] = find(j) , add(i , j , i) , add(j , i , i);
		}
	}
	dfs(1,1,INF);
	tr.dfs1(1,1);
	tr.dfs2(1,1);
	tr.build(1,n,1);
	for(int i = 1 ; i <= q ; ++i){
		int x , y;
		scanf("%d%d",&x,&y);
		printf("%d\n",m - tr.queryMin(x,y) + 1);
	}
}

Problem 3 Permutation

【题目描述】

将 1 到 N 任意排列，然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。

问在所有排列中，有多少个排列恰好有K个“<”。

例如排列(3, 4, 1, 5, 2)

3 < 4 > 1 < 5 > 2

共有2个“<”

【输入格式】

N,K

【输出格式】

答案

【样例输入】

5 2

【样例输出】

66

【数据范围】

20%：N <= 10

100%：K < N <= 1000

题解

一道不错的递推，我一开始写了个

的算法。。

显然题目要求一个

的算法。

考虑前i个数中已经有了j个小于号。

我们只需要考虑往里插入的数有的可能就可以了

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 2005
int f[maxn][maxn] , n , k;
int main()
{
	freopen("permutation.in","r",stdin);
	freopen("permutation.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i = 1 ; i <= n ; ++i)	
		f[i][0] = 1;
	for(int i = 2 ; i <= n ; ++i)
		for(int j = 1 ; j <= i - 1 && j <= k; ++j)
			f[i][j] = f[i-1][j] * (j + 1) + f[i-1][j-1] * (i - j);
	printf("%d\n",f[n][k]);
}