收录非传统题
1. qoj364/JOISC2017 - Broken Device
考虑每三位一组，那么若三位都可行存 \(2\) 位，三位有两位可行存 \(1\) 位即可。
考虑如下映射：
\[\begin{aligned} 0&\to 010\\ 1&\to100,011\\ 00&\to101\\ 01&\to111\\ 10&\to001\\ 11&\to110\\ \end{aligned} \]那么唯一的问题变成了 \(\texttt{oxo}\)（即最中间一位坏掉）不能表示 \(0\)。但是这一位可以表示 \(00\) 和 \(10\)！于是解决了问题。
点击查看代码
//qoj364
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #include "Annalib.h"
int p[60], tmp[160];
void Set(int x, int i){
putchar(i+'0');
tmp[x] = i;
}
int ban[160];
void Anna(int N, ll X, int K, int P[]){
memset(ban, 0, sizeof(ban));
for(int i = 0; i < K; ++ i){
ban[P[i]] = 1;
}
int cnt = 0;
for(int i = 0; i < 150; i += 3){
if(!ban[i] && !ban[i+1] && !ban[i+2]){
// puts("1234");
int p = X % 4; X /= 4; cnt += 2;
cerr << -p << ' ';
if(p == 0){ Set(i, 1); Set(i+1, 0); Set(i+2, 1); }
if(p == 1){ Set(i, 1); Set(i+1, 1); Set(i+2, 1); }
if(p == 2){ Set(i, 0); Set(i+1, 0); Set(i+2, 1); }
if(p == 3){ Set(i, 1); Set(i+1, 1); Set(i+2, 0); }
} else if(!ban[i] && !ban[i+1]){
// puts("1234");
int p = X % 2; X /= 2; ++ cnt;
cerr << p << ' ';
if(p == 0){ Set(i, 0); Set(i+1, 1); Set(i+2, 0); }
if(p == 1){ Set(i, 1); Set(i+1, 0); Set(i+2, 0); }
} else if(!ban[i] && !ban[i+2]){
// puts("1234");
int p = X % 2;
if(p){
p = X % 2; X /= 2; ++ cnt;
cerr << p << ' ';
Set(i, 1); Set(i+1, 0); Set(i+2, 0);
} else {
p = X % 4; X /= 4; ++ cnt;
cerr << -p << ' ';
if(p == 0){ Set(i, 1); Set(i+1, 0); Set(i+2, 1); }
if(p == 2){ Set(i, 0); Set(i+1, 0); Set(i+2, 1); }
}
} else if(!ban[i+1] && !ban[i+2]){
int p = X % 2; X /= 2; ++ cnt;
cerr << p << ' ';
if(p == 0){ Set(i, 0); Set(i+1, 1); Set(i+2, 0); }
if(p == 1){ Set(i, 0); Set(i+1, 1); Set(i+2, 1); }
} else {
Set(i, 0); Set(i+1, 0); Set(i+2, 0);
}
cerr << '\n';
}
cerr << cnt << ' ' << X << '\n';
}
// #include <bits/stdc++.h>
// using namespace std;
// typedef long long ll;
// #include "Brunolib.h"
long long Bruno(int N, int A[]){
ll ans = 0, bs = 1;
for(int i = 0; i < 150; i += 3){
int val = A[i] * 4 + A[i+1] * 2 + A[i+2];
if(val == 1){ ans += bs * 2; bs <<= 2; }
if(val == 2){ ans += bs * 0; bs <<= 1; }
if(val == 3){ ans += bs * 1; bs <<= 1; }
if(val == 4){ ans += bs * 1; bs <<= 1; }
if(val == 5){ ans += bs * 0; bs <<= 2; }
if(val == 6){ ans += bs * 3; bs <<= 2; }
if(val == 7){ ans += bs * 1; bs <<= 2; }
}
cerr << ans << ' ' << bs << '\n';
return ans;
}
int main(){
for(int i = 1; i <= 40; ++ i){
p[i] = i * 3 + rand() %3;
}
Anna(150, 235813068146480210ll, 40, p);
for(int i = 1; i <= 40; ++ i){
tmp[p[i]] = 0;
}
printf("%lld\n", Bruno(150, tmp));
}