5.28 模拟赛

A 科学怪人

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

直接 bfs ,由于最终只有 O(n)O(n) 对,答案是 O(n)O(n) 的。

#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 鱼人

阴间题。

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

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

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

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

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

C 狼人

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

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

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

复杂度 O(nlogn)O(n\log n) ,瓶颈在 LCA

#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();
}








\