QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #29945 | #2906. XOR Island | George_Plover# | AC ✓ | 2685ms | 265948kb | C++23 | 1.2kb | 2022-04-23 15:33:58 | 2022-04-28 16:04:41 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per(i, r, l) for (int i = r; i >= l; --i)
using namespace std;
typedef long long ll;
const int N = 25;
const int M = 1 << N;
int n;
int a[N];
int f[M];
int dp[M];
int main() {
scanf("%d", &n);
rep(i, 0, n - 1) { scanf("%d", &a[i]); }
rep(i, 0, n - 1) {
rep(j, i + 1, n - 1) {
rep(k, j + 1, n - 1) {
if ((a[i] ^ a[j]) == a[k]) {
f[(1 << i) | (1 << j) | (1 << k)] |=
(1 << i) | (1 << j) | (1 << k);
}
}
}
}
rep(i, 0, n - 1) {
rep(S, 0, (1 << n) - 1) {
if (S & (1 << i)) continue;
f[S | 1 << i] |= f[S];
}
}
rep(S, 0, (1 << n) - 1) {
assert((f[S] & S) == f[S]);
if (!f[S])
dp[S] = 0;
else {
dp[S] = n;
rep(i, 0, n - 1) {
if (f[S] & (1 << i)) {
dp[S] = min(dp[S], dp[S - (1 << i)]);
}
}
dp[S]++;
}
}
printf("%d\n", dp[(1 << n) - 1]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 5756kb
input:
3 1 2 3
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5848kb
input:
11 9 1 14 2 11 7 6 7 6 5 3
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 2ms
memory: 5852kb
input:
6 18053353 18053353 31735788 31735788 16205573 16205573
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 3ms
memory: 5828kb
input:
9 8324820 8324820 8324820 21703420 21703420 21703420 20196392 20196392 20196392
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 3ms
memory: 5824kb
input:
12 13845321 13845321 13845321 13845321 15244518 15244518 15244518 15244518 3923887 3923887 3923887 3923887
output:
4
result:
ok single line: '4'
Test #6:
score: 0
Accepted
time: 4ms
memory: 5808kb
input:
15 22226925 22226925 22226925 22226925 22226925 11291487 11291487 11291487 11291487 11291487 33516722 33516722 33516722 33516722 33516722
output:
5
result:
ok single line: '5'
Test #7:
score: 0
Accepted
time: 15ms
memory: 6848kb
input:
18 15216629 15216629 15216629 15216629 15216629 15216629 9508343 9508343 9508343 9508343 9508343 9508343 7944706 7944706 7944706 7944706 7944706 7944706
output:
6
result:
ok single line: '6'
Test #8:
score: 0
Accepted
time: 136ms
memory: 20408kb
input:
21 13356922 13356922 13356922 13356922 13356922 13356922 13356922 32063243 32063243 32063243 32063243 32063243 32063243 32063243 19066993 19066993 19066993 19066993 19066993 19066993 19066993
output:
7
result:
ok single line: '7'
Test #9:
score: 0
Accepted
time: 1269ms
memory: 136376kb
input:
24 5624463 5624463 5624463 5624463 5624463 5624463 5624463 5624463 15098761 15098761 15098761 15098761 15098761 15098761 15098761 15098761 11776262 11776262 11776262 11776262 11776262 11776262 11776262 11776262
output:
8
result:
ok single line: '8'
Test #10:
score: 0
Accepted
time: 80ms
memory: 20956kb
input:
21 10 1 5 1 6 12 14 16 1 13 2 10 16 9 14 2 12 16 13 11 1
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 261ms
memory: 37056kb
input:
22 9 5 1 2 6 15 8 10 2 1 13 10 10 4 13 16 8 5 7 4 9 3
output:
7
result:
ok single line: '7'
Test #12:
score: 0
Accepted
time: 552ms
memory: 70256kb
input:
23 2 12 8 5 6 15 3 14 3 4 11 2 6 13 1 10 13 6 1 8 1 5 15
output:
7
result:
ok single line: '7'
Test #13:
score: 0
Accepted
time: 1139ms
memory: 136604kb
input:
24 4 13 10 8 4 12 10 1 13 16 1 10 5 3 6 3 9 6 14 4 7 4 9 2
output:
7
result:
ok single line: '7'
Test #14:
score: 0
Accepted
time: 2335ms
memory: 265912kb
input:
25 13 8 5 2 12 6 12 1 16 14 2 10 2 8 9 3 4 6 9 6 6 7 14 1 9
output:
7
result:
ok single line: '7'
Test #15:
score: 0
Accepted
time: 153ms
memory: 69616kb
input:
23 15925942 11051838 20346967 676939 779282 29980798 24484952 27328228 25636253 911824 30521853 23148136 24386971 30992542 4736184 8716393 26656418 1571228 10680642 25754292 7030770 9364603 4593643
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 346ms
memory: 136552kb
input:
24 14308376 17302931 4737216 25548643 20448845 30163626 24015986 16874513 1363340 25740273 26055670 2065166 22649380 27657047 20575156 5465887 28406514 2855073 29537258 24129214 23999010 30352648 4252441 13105059
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 700ms
memory: 265896kb
input:
25 7278802 5576962 9887589 28410596 6241564 4736865 29583733 13328658 24907097 21930886 31443909 25339020 20142713 32796255 4539481 28575359 13110054 13738964 14418498 10152417 4040993 5615463 16606164 25405528 15179433
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 586ms
memory: 70876kb
input:
23 1 131072 1 131072 131073 1 131073 131072 131072 131073 131072 131072 131073 131073 1 131072 131073 131073 1 131072 131073 131072 131073
output:
5
result:
ok single line: '5'
Test #19:
score: 0
Accepted
time: 519ms
memory: 69404kb
input:
23 1050688 1048576 2048 1048576 2048 1048640 1048576 1050624 1050688 1048640 2112 1048640 1048640 1048640 1050624 2048 1048640 1050688 1050624 1048640 1048576 1048576 1048640
output:
4
result:
ok single line: '4'
Test #20:
score: 0
Accepted
time: 1225ms
memory: 134844kb
input:
24 66560 1024 65536 66560 65536 1024 66560 66560 1024 66560 66560 66560 66560 66560 1024 65536 1024 1024 66560 65536 1024 1024 66560 66560
output:
4
result:
ok single line: '4'
Test #21:
score: 0
Accepted
time: 1214ms
memory: 136188kb
input:
24 32 256 32 800 800 512 512 256 256 800 512 544 544 544 512 288 800 800 768 256 512 32 256 256
output:
5
result:
ok single line: '5'
Test #22:
score: 0
Accepted
time: 2685ms
memory: 265948kb
input:
25 1056 1024 32 1024 32 1024 32 1056 1056 32 32 1056 32 32 1056 1056 1024 32 1056 1056 1024 32 32 1024 1024
output:
7
result:
ok single line: '7'
Test #23:
score: 0
Accepted
time: 2612ms
memory: 265920kb
input:
25 131328 131136 131136 64 131136 64 131072 131392 131136 131392 64 64 320 131136 320 131072 256 131328 131392 131072 131136 131136 131136 320 256
output:
7
result:
ok single line: '7'
Test #24:
score: 0
Accepted
time: 5ms
memory: 5952kb
input:
15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
output:
7
result:
ok single line: '7'
Test #25:
score: 0
Accepted
time: 2398ms
memory: 265916kb
input:
25 27882881 30145540 6457733 28446363 30443294 7991967 5008288 31792673 3072549 5705914 33449275 27061438 3512639 25153864 14066889 18700493 23374418 13492179 11490902 17179607 20167400 10145641 16271084 14892534 21645431
output:
10
result:
ok single line: '10'
Test #26:
score: 0
Accepted
time: 2477ms
memory: 265896kb
input:
25 972439 2867411 2423978 50417 1961336 2373723 2430532 77343 2813644 3655493 1310494 125678 998521 922214 3790115 1885031 3734332 1836950 1233153 3686349 1185264 3740114 1911177 2478773 2763325
output:
11
result:
ok single line: '11'
Test #27:
score: 0
Accepted
time: 2406ms
memory: 265928kb
input:
25 2700755 2567664 923683 3765664 1288823 256516 1988688 1946196 969910 2809815 1277666 1086694 212625 913959 54421 3776821 2744646 2755394 1926849 1065075 2364257 2410484 861874 2619749 2002117
output:
9
result:
ok single line: '9'