4.25 写题

Light switches

注意到 $S \le 30$ ,我们考虑进行折半搜索。考虑复杂度是啥,如果所有集合操作都使用 bitset ,不难发现这里的两个开关并起来就是做个异或,那么考虑枚举一下前 $A$ 个开关的情况进行预处理,然后查询的时候对剩下的开关枚举情况,预处理的东西丢进一个 unordered_map 里(貌似 unordered_mapbitset 有自带的 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/2021/04/25/0425-zuo-ti-ji-lu/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog