Yijan's Blog HomeArchives
5.28 模拟赛

A 科学怪人

可以发现，只需要求出 $(\frac{n}{\gcd(n,b)},0) , (0,\frac{n}{\gcd(n,a)}),(a,b)$ 的所有线性组合即可。

直接 bfs ，由于最终只有 $O(n)$ 对，答案是 $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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 300006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 998244353;
int n , a , b;

vector<pii> vec;

int gcd( int a , int b ) {
	return !b ? a : gcd( b , a % b );
}

void exgcd( int a , int b , int& d , int& x , int& y ) {
	if( !b ) x = 1 , y = 0 , d = a;
	else exgcd( b , a % b , d , y , x ) , y -= a / b * x;
}

set<pii> vs;

void solve() {
	cin >> n >> a >> b;
	int g = gcd( gcd( n , a ) , b );
	int pr = g;
	n /= g , a /= g , b /= g;
	int gb = n / gcd( a , n ) , ga = n / gcd( b , n );
	queue<pii> Q;
	Q.emplace( 0 , 0 ) , vs.emplace( 0 , 0 );
	auto wkr = [&]( pii s ) {
		s.fi %= n , s.se %= n;
		if( vs.count( s ) ) return;
		Q.push( s ) , vs.insert( s );
	};
	while( !Q.empty() ) {
		pii s = Q.front(); Q.pop();
		wkr( mp( s.fi + ga , s.se ) ) , wkr( mp( s.fi , s.se + gb ) ) , wkr( mp( s.fi + a , s.se + b ) );
	}
	cout << vs.size() << endl;
	for( auto t : vs ) printf("%d %d\n",t.fi * pr,t.se * pr);
}

signed main() {
	freopen("doga.in","r",stdin);
	freopen("doga.out","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}




B 鱼人

阴间题。

我场上的贪心好像假掉了，就不写了。

首先，我们判掉每个位置的方向形成一个环的情况，这个可以直接判。

然后我们考虑枚举一个点作为汇点，显然一定存在这样一个汇点。那么此时我们就确定了所有除终点在汇点的路径的方向。并且根据这些路径，我们可以确定一个分界点落在的区间，这里分界点指的是一个位置，使得这个位置左边和右边连向汇点的方向不同。

然后我们考虑所有连向汇点的路径，显然我们对这种路径排序后，一定是一段前缀从某个方向到汇点，一个后缀从另一个方向到汇点。

于是我们可以直接对这个东西做扫描线来解决这个问题。但事实上代码非常难写，因为这些路径都是在环上的，而一旦断环成链后就需要讨论 $1$ 的情况以及跨环情况。

C 狼人

首先考虑一条链的情况，如果两个点距离为奇数，那么就会形成 $1,0,1,0,\dots,1,0,2,0,2,0,\dots$ 的循环，如果距离是偶数，那么会形成 $1,-1,1,-1,\dots$ 的形状。

然后考虑非链的情况，会发现如果两个人相遇了，那么这两个人肯定会对冲，也就是一个人会去走到另一个人的位置，因为这样可以获得 $2$ 的优势，这样必然是好的。然后我们考虑由于双方知道一共要走多少步，而相遇所需的步数的奇偶性是确定的，也就是说相遇后两个人分别需要走多少步的奇偶性确定，那么肯定是如果相遇，那么最终停留的位置大的人想要相遇，另一个人不想相遇，也就是说我们可以看成一个人跑一个人追的过程。然后答案只和是否追到有关。

考虑怎么求这个是否追到。可以发现本质上是求在一个子树（这里的子树可能是原树砍掉一个子树）内部，距离一个点最远点的距离。我们知道在树里这样的点一定是直径的端点，因此之需要求出所有子树，以及砍去某个子树剩下的部分的直径分别是啥即可。这个可以一次换根 $dp$ 解决，具体来说就是直径的合并问题（这个可以直接 chk 每一对直径端点）

复杂度 $O(n\log n)$ ，瓶颈在 LCA 。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 300006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 998244353;
int n , q;
vi G[MAXN];

int g[MAXN][20] , dep[MAXN];
pii S[MAXN];
void dfs( int u , int f ) {
	dep[u] = dep[f] + 1;
	for( int v : G[u] ) if( v != f ) {
			g[v][0] = u;
			rep( k , 1 , 17 ) if( g[g[v][k - 1]][k - 1] )
				g[v][k] = g[g[v][k - 1]][k - 1]; else break;
			dfs( v , u );
		}
}
int lca( int u , int v ) {
	if( dep[u] < dep[v] ) swap( u , v );
	per( k , 17 , 0 ) if( dep[g[u][k]] >= dep[v] ) u = g[u][k];
	if( u == v ) return u;
	per( k , 17 , 0 ) if( g[u][k] != g[v][k] ) u = g[u][k] , v = g[v][k];
	return g[u][0];
}
int jump( int u , int k ) {
	per( t , 17 , 0 ) if( k & ( 1 << t ) ) u = g[u][t];
	return u;
}
int dis( int u , int v ) {
	return dep[u] + dep[v] - 2 * dep[lca( u , v )];
}
void ck( pii& r , int& d , pii b ) {
	int p = dis( b.fi , b.se );
	if( p > d ) d = p , r = b;
}
pii merge( pii a , pii b ) {
	pii re = a;
	int ds = dis( a.fi , a.se );
	ck( re , ds , b );
	ck( re , ds , mp( a.fi , b.fi ) ) , ck( re , ds , mp( a.se , b.fi ) );
	ck( re , ds , mp( a.fi , b.se ) ) , ck( re , ds , mp( a.se , b.se ) );
	return re;
}
void afs( int u , int f ) {
	S[u] = mp( u , u );
	for( int v : G[u] ) if( v != f ) {
			afs( v , u );
			S[u] = merge( S[u] , S[v] );
		}
}
pii ot[MAXN];
pii pr , su[MAXN];
void pfs( int u , int f ) {
	for( int i = G[u].size() - 1 ; i >= 0 ; -- i ) {
		int v = G[u][i];
		if( v == f ) { su[i] = su[i + 1]; continue; }
		if( i != G[u].size() - 1 ) su[i] = merge( S[v] , su[i + 1] );
		else su[i] = S[v];
	}
	pr = u == f ? mp( u , u ) : merge( mp( u , u ) , ot[u] );
	rep( i , 0 , G[u].size() - 1 ) {
		int v = G[u][i];
		if( v == f ) continue;
		ot[v] = i != G[u].size() - 1 ? merge( pr , su[i + 1] ) : pr;
		pr = merge( pr , S[v] );
	}
	for( int v : G[u] ) if( v != f )
			pfs( v , u );
}

void solve() {
	cin >> n >> q;
	rep( i , 2 , n ) {
		int u , v;
		scanf("%d%d",&u,&v);
		G[u].pb( v ) , G[v].pb( u );
	}
	dfs( 1 , 1 );
	afs( 1 , 1 );
	pfs( 1 , 1 );
	rep( i , 1 , q ) {
		int u , v , k;
		scanf("%d%d%d",&u,&v,&k);
		if( k & 1 ) swap( u , v );
		int l = lca( u , v ) , t = jump( v , ( k + 1 ) / 2 ) , d = dep[u] + dep[v] - 2 * dep[l];
		int ok = 0;
		if( ( k + 1 >> 1 ) >= d ) ok = 0;
		else if( !t || dep[t] <= dep[l] ) {
			int d = ( dep[u] - dep[l] ) - ( ( k + 1 >> 1 ) - ( dep[v] - dep[l] ) );
			int t = jump( u , d - 1 );
			int x = S[t].fi , y = S[t].se;
			if( dis( x , u ) >= k / 2 || dis( y , u ) >= k / 2 ) ok = 1;
		} else {
			int x = ot[t].fi , y = ot[t].se;
//			if( i == 227 ) cerr << dep[x] << ' ' << dep[y] << ' ' << k << endl;
			if( dis( x , u ) >= k / 2 || dis( y , u ) >= k / 2 ) ok = 1;
		}
		if( d & 1 ) {
			if( k & 1 )
				if( ok ) puts("1");
				else puts("2");
			else
				puts("0");
		} else {
			if( k & 1 )
				puts("1");
			else
			if( ok ) puts("0");
			else puts("-1");
		}
	}
}

signed main() {
	freopen("wolf.in","r",stdin);
	freopen("wolf.out","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}








文章作者: yijan
文章链接: https://yijan.co/529-mo-ni-sai/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！