Yijan's Blog HomeArchives
4.25 写题

Light switches

注意到 $S \le 30$ ，我们考虑进行折半搜索。考虑复杂度是啥，如果所有集合操作都使用 bitset ，不难发现这里的两个开关并起来就是做个异或，那么考虑枚举一下前 $A$ 个开关的情况进行预处理，然后查询的时候对剩下的开关枚举情况，预处理的东西丢进一个 unordered_map 里（貌似 unordered_map 对 bitset 有自带的 Hash 方式），复杂度就是 $O(2^A \frac Nw + q\frac N w 2^{S-A})$ ，不难发现在 $A$ 大概取到 $20$ 的时候，运算次数大概是 $\frac{10^9}{32}$ 左右，非常稳。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "bitset"
#include "queue"
#include "unordered_map"
using namespace std;
#define MAXN 1036
//#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 = 418254373;
const int base = 332;
int n , s , d;
int A[MAXN];

bitset<MAXN> K[MAXN] , S[1 << 20 | 6] , rS[1 << 10 | 6];
unordered_map<bitset<MAXN>,int> M;

int pw[MAXN];
int cal( bitset<MAXN>& s ) {
	int re = 0;
	rep( i , 1 , n ) if( s[i] ) re = ( re + pw[i] ) % P;
	return re;
}

void solve() {
	cin >> n >> s >> d;
	pw[0] = 1;
	rep( i , 1 , n ) pw[i] = pw[i - 1] * 1ll * base % P;
	rep( i , 1 , s ) {
		int c , w;
		scanf("%d",&c); 
		rep( j , 1 , c ) scanf("%d",&w) , K[i][w] = 1;
	}
	int ps = s - s / 3 , rs = s / 3;
	M[0] = 0;
	for( int i = 1 ; i < ( 1 << ps ) ; ++ i ) {
		S[i] = S[i ^ ( i & -i )] ^ K[__builtin_ctz( i ) + 1];
		if( !M.count( S[i] ) ) M[S[i]] = __builtin_popcount( i );
		else M[S[i]] = min( M[S[i]] , __builtin_popcount( i ) );
	}
	for( int i = 1 ; i < ( 1 << rs ) ; ++ i ) {
		rS[i] = rS[i ^ ( i & -i )] ^ K[__builtin_ctz( i ) + ps + 1];
	}
	rep( i , 1 , d ) {
		bitset<MAXN> cur;
		int c;
		scanf("%d",&c);
		rep( j , 1 , c ) {
			int w; scanf("%d",&w);
			cur[w] = 1;
		}
		int as = 0x3f3f3f3f;
		for( int w = 0 ; w < ( 1 << rs ) ; ++ w ) {
			bitset<MAXN> t = cur ^ rS[w];
			if( M.count( t ) ) as = min( as , __builtin_popcount( w ) + M[t] );
		}
		printf("%d\n",as > 1e9 ? -1 : as);
	}
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

Nikita and game

开始的做法比较憨憨，拿一个 set 维护所有当前能成为直径端点的 dfs 序，每次加入一个点，如果它可以成为直径端点，暴力枚举一下 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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 600046
//#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;
int n , m;
int A[MAXN];

vi G[MAXN];
int dfn[MAXN] , bc[MAXN] , clo;
int g[MAXN][20] , dep[MAXN];

void dfs( int u ) {
	dfn[u] = ++ clo , bc[clo] = u;
	if( u == 1 ) dep[u] = 1;
	for( int v : G[u] ) {
		g[v][0] = u;
		dep[v] = dep[u] + 1;
		rep( k , 1 , 18 ) if( g[g[v][k - 1]][k - 1] ) g[v][k] = g[g[v][k - 1]][k - 1]; else break;
		dfs( v );
	}
}

int lca( int u , int v ) {
	if( dep[u] < dep[v] ) swap( u , v );
	if( dep[u] != dep[v] ) per( k , 18 , 0 ) if( dep[g[u][k]] >= dep[v] ) u = g[u][k];
	if( u == v ) return u;
	per( k , 18 , 0 ) if( g[u][k] != g[v][k] ) u = g[u][k] , v = g[v][k];
	return g[u][0];
}

int dis( int u , int v ) {
	return dep[u] + dep[v] - 2 * dep[lca( u , v )];
}

set<int> S;

void solve() {
	cin >> n;
	++ n;
	rep( i , 2 , n ) {
		int p;
		scanf("%d",&p);
		G[p].pb( i );
	}
	dfs( 1 );
	int s = 1 , t = 1 , lt = 0;
	auto wkr = [&]( int x ) {
		return max( dis( x , s ) , dis( x , t ) );
	};
	S.insert( 1 );
	rep( i , 2 , n ) {
		int is = dis( i , s ) , it = dis( i , t ) , flg = 0;
		if( is >= lt && is >= it ) t = i , lt = is , flg = 1;
		else if( it >= lt && it >= is ) s = i , lt = it , flg = 1;
		if( !flg ) {
			printf("%d\n",(int)S.size());
			continue;
		}
		auto tr = S.lower_bound( dfn[i] ) , st = tr;
		while( tr != S.end() ) {
			if( wkr( bc[*tr] ) < lt ) ++ tr;
			else break;
		}
		if( tr == S.end() ) {
			auto sr = S.begin();
			while( sr != st ) {
				if( wkr( bc[*sr] ) < lt ) ++ sr;
				else break;
			}
			S.erase( S.begin() , sr );
		}
		S.erase( st , tr );
		tr = S.lower_bound( dfn[i] ) , st = tr;
		while( tr != S.begin() ) {
			-- tr;
			if( wkr( bc[*tr] ) >= lt ) { ++ tr; break; }
		}
		if( tr == S.begin() ) {
			auto sr = S.end();
			while( sr != st ) {
				-- sr;
				if( wkr( bc[*sr] ) >= lt ) { ++ sr; break; }
			}
			S.erase( sr , S.end() );
		}
		S.erase( tr , st );
		S.insert( dfn[i] );
//		for( int x : S ) printf("%d ",bc[x]); puts("");
		printf("%d\n",(int)S.size());
	}
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

Looping Labyrinth

官方题解图画得太好了，嫖一下官方题解的图。

考虑 $(0,0)$ 可以到达哪些点。我们考虑进行一种每个点在模意义下只经过一次（也就是只访问 vis[x % n][y % m] == 0 的点）的 bfs ，然后可以得到开始就可以到的点，这些点的坐标并不一定在 $n,m$ 之内。

B__AMUCR3_5IPH_5___V_IH.png

图中，红色格子是初始矩阵，绿色格子是开始能到的点。

然后考虑在这样的基础上哪些点可以到。可以发现只有两种情况：要么所有被访问过的点都可以到，要么一定存在一个向量 $vx,vy$ ，如果 $(x,y)$ 可以到达，那么 $(x+vx,y+vy)$ 也可以到达。具体来说，大概就是这两种情况：

X_L_2_B_T5OFCPTC598O0_7.png

以及

UE9AMR_4NN_K_IYPEJKLDET.png8_OH2K_2L0P_X37__MYOE_M.png

其实事实上，第一种情况就是在有两种向量存在的时候导致的。具体来说，如果存在两个第二次在模意义下第二次访问到的点 $P_1(x_1,y_1),P_2(x_2,y_2)$ ，第一次访问的位置是 $P’_1(x_1’,y_1’),P’_2(x_2’,y_2’)$ ，而且向量 $P_1P_1’,P_2P_2’$ 不共线，那么所有在模意义下可以访问到的点最终一定可以访问到（可以感性理解一下，因为从一个点出去两个路径肯定会有交）。如果所有 $P_1P_2$ 共线，那么就直接判掉即可。复杂度 $O(nm)$ 。

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 "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 106
//#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 dx[] = { 0,1,-1,0 } , dy[] = { 1,0,0,-1 };

int n , m , q;
int A[MAXN];
char S[MAXN][MAXN];

int vis[MAXN][MAXN];
pii ps[MAXN][MAXN];

void solve() {
	cin >> n >> m;
	rep( i , 0 , n - 1 ) {
		scanf("%s",S[i]);
	}
	queue<pii> Q;
	Q.emplace( 0 , 0 );
	int vx = 0 , vy = 0 , fuck = 0;
	while( !Q.empty() ) {
		int x = Q.front().fi , y = Q.front().se; Q.pop();
		int tx = ( x % n + n ) % n , ty = ( y % m + m ) % m;
		if( !vis[tx][ty] ) {
			if( tx == 5 && ty == 4 ) 
				printf("");
			vis[tx][ty] = 1;
			ps[tx][ty] = mp( x , y );
			rep( d , 0 , 3 ) {
				int xx = x + dx[d] , yy = y + dy[d];
				int px = ( xx % n + n ) % n , py = ( yy % m + m ) % m;
				if( S[px][py] != '#' ) Q.emplace( xx , yy );
			}
		} else {
			if( tx == 5 && ty == 4 ) 
				printf("");
			int dx = x - ps[tx][ty].fi , dy = y - ps[tx][ty].se;
			if( !vx && !vy ) vx = dx , vy = dy;
			else if( dx * 1ll * vy != dy * 1ll * vx ) fuck = 1;
		}
	}
	cin >> q;
	rep( i , 1 , q ) {
		int x , y;
		scanf("%d%d",&x,&y);
		int px = ( x % n + n ) % n , py = ( y % m + m ) % m;
		if( !vis[px][py] ) puts("no");
		else if( fuck ) puts("yes");
		else {
			int dx = x - ps[px][py].fi , dy = y - ps[px][py].se;
			if( dx * 1ll * vy == dy * 1ll * vx ) puts("yes");
			else puts("no");
		}
	}
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}
文章作者: yijan
文章链接: https://yijan.co/0425-zuo-ti-ji-lu/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！