(建议您从上方链接进入我的个人网站查看此 Blog,在 Luogu 中图片会被墙掉,部分 Markdown 也会失效)
存在
能到达输出 TAK
,反之输出 NIE
。
n k
S T
(偷个懒就不写文字叙述了。。。)
这道题我本来还以为是和 LG-P7966 [COCI2021-2022#2] Hiperkocka 差不多的题,该题题解,按照那道题的思路想了一下然后假了,改了一下之后 T 掉了,寄,和之前的题关系不是很大,只是定义一样。
Lemma 1:对于一个
证明:A proof is left to the reader.
证明:这东西大多数地方都没有人证明,甚至官方题解,感觉可以当成一个已知结论记住,关于严谨证明网上也找到了个大佬的证明(看不懂),戳此进入。
Lemma 2:对于一个
证明:假设我们现在有两个连通块,其点集分别为
于是只要有了 Lemma 2,我们就可以很容易想到,令出发点和终点分别为
于是我们分别从 unordered_set
记录其所在连通块有哪些点,如果从搜索过程中遇到另一个点了,则两者同在一个小连通块中,直接输出连通然后 exit
,如果连通块大小超过 return
。两者都搜完后如果两个连通块都超过
另外个人建议把二进制转成 long long
再存,否则还会存在一个 hash 的复杂度,虽然我感觉好像嗯搞也能过???
然后写位移的时候记得写成 1ll
。
这个的复杂度大概是 我不会。
A proof is left to the reader.
然后。。。Luogu 评测记录
unordered_set
寄了,cc_hash_table
寄的更多,经典被卡常,调了亿会怎么 Luogu 上都是两个点 TLE,一个点 MLE,于是开始手搓 hash 挂链,队列之类的,最终终于在 Luogu 上把这破题给卡过去了。。。
xxxxxxxxxx
1161
2
3
4
5
6
7
8
9
10
11/******************************
12abbr
13uex => unexist
14******************************/
15
16using namespace std;
17using namespace __gnu_pbds;
18
19mt19937 rnd(random_device{}());
20int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
21bool rnddd(int x){return rndd(1, 100) <= x;}
22
23typedef unsigned int uint;
24typedef unsigned long long unll;
25typedef long long ll;
26typedef long double ld;
27
28template<typename T = int>
29inline T read(void);
30
31ll str2ll(char* s, int n){
32 ll ret(0), base(0);
33 for(int i = n - 1; i >= 0; --i)
34 ret += (1ll << (base++)) * (s[i] == '0' ? 0 : 1);
35 return ret;
36}
37
38struct Edge{
39 Edge* nxt;
40 ll val;
41 OPNEW;
42}eData[4145149];
43ROPNEW(eData);
44Edge* head[2737330];
45void clear(void){memset(head, 0, sizeof(head));}
46void Add(ll val){
47 int idx = val % MOD;
48 head[idx] = new Edge{head[idx], val};
49}
50bool Check(ll val){
51 int idx = val % MOD;
52 for(auto i = head[idx]; i; i = i->nxt)
53 if(i->val == val)return true;
54 return false;
55}
56
57ll S, T;
58int N, K;
59ll cur[5100000];
60int fnt(0), til(0);
61void bfs(ll S, ll T){
62 fnt = til = 0;
63 cur[til++] = S;
64 Add(S);
65 while(fnt < til){
66 ll tp = cur[fnt++];
67 for(int base = 0; base <= N - 1; ++base){
68 ll val = tp ^ (1ll << base);
69 if(val == T)printf("TAK\n"), exit(0);
70 if(Check(val))continue;
71 else{
72 Add(val);
73 cur[til++] = val;
74 }
75 }
76 if(til > N * K)return;
77 }
78 printf("NIE\n"); exit(0);
79}
80char c[65];
81vector < ll > values;
82int main(){
83 // freopen("in.txt", "r", stdin);
84 N = read(), K = read();
85 scanf("%s", c); S = str2ll(c, N);
86 scanf("%s", c); T = str2ll(c, N);
87 if(S == T)printf("TAK\n"), exit(0);
88 for(int i = 1; i <= K; ++i){
89 scanf("%s", c); ll tmpp = str2ll(c, N);
90 values.push_back(tmpp);
91 }
92 for(auto i : values)Add(i);
93 bfs(S, T);
94 clear();
95 for(auto i : values)Add(i);
96 bfs(T, S);
97 printf("TAK\n");
98 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
99 return 0;
100}
101
102template<typename T>
103inline T read(void){
104 T ret(0);
105 short flag(1);
106 char c = getchar();
107 while(c != '-' && !isdigit(c))c = getchar();
108 if(c == '-')flag = -1, c = getchar();
109 while(isdigit(c)){
110 ret *= 10;
111 ret += int(c - '0');
112 c = getchar();
113 }
114 ret *= flag;
115 return ret;
116}
update-2022_09_27 初稿