2/3线性基与100%构造题

T140977 线性基 (hard version)

排序也没用啊

第一个数构造2^19+k

第二个数构造2^18+k

第三个数及以后构造2^18

会发现他们会向搞一个2¹⁹⁺²18之后完蛋

然后我们2¹⁹⁺²18+k显然最优解

如果这个k和1e6同阶就完蛋了....

然额这个会fst,第一个是n=2的时候,k!=0一定无解

第二个是k=0的时候随便构造一下就行了


#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n, k;

int main() {
	scanf("%d%d", &n, &k);
	if(k != 0) {
		if(n == 2)puts("-1");
		else {
			printf("%d %d ", k + (1 << 19), k + (1 << 18));
			for(int i = 3; i <= n; ++i)printf("%d ", (1 << 18));
			puts("");
		}
	} else {
		for(int i = 1; i <= n; ++i)printf("%d ", (1 << 19));
		puts("");
	}
	return 0;
}

P4301 [CQOI2013] 新Nim游戏

k太小了吧?

先手必胜就是在最后异或起来不是0的时候,也就是说无论第二个人怎么拿走都无法出现0的局面

仔细想想我们线性基插入过程中插不进去的就能被异或成0....

而我们其实是想让这个值尽可能的小,也就是说大数能插进去,所以我们从大到小插入就行了

code:


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 7;
int n, a[MAXN], b[MAXN];
long long ans;

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)scanf("%d", a + i);
	sort(a + 1, a + n + 1);
	for(int i = n; i >= 1; --i) {
		int tmp = a[i];
		// printf("%d?\n", tmp);
		bool flg = 1;
		for(int k = 30; k >= 0; --k) {
			if(tmp & (1 << k)) {
				if(b[k])
					tmp ^= b[k];
				else {
					b[k] = tmp;
					flg = 0;
					break;
				}
			}
		}
		// printf("%d?%d\namespace", flg, tmp);
		if(flg)ans += a[i];
	}
	printf("%lld\n", ans);
	return 0;
}

P3226 [HNOI2012]集合选数

显然这个东西每个数能选的是一样的qwq

然后.....QAQ了

容斥一下吗?完蛋了,和枚举自己没啥区别

点开标签: 状压?

啊这...

等等啊,这个东西从小到大DP?

啊这.....

打开题解:显然这个结论很难搞,我们要找一个等价命题

构造一个矩阵,第一行第一列的值为1,每一行后面的数都是前面那个数的两倍

每列的数是他上面的数的三倍


1  2  4  8   16  32  ...
3  6  12 24  48  96  ...
9  18 36 72  ...
27 ...

每个数都是前面那个数2倍,最后长为 $log_2n$ 宽为 $log_3n$

然后就发现每个数我们选了他就不能选择相邻的,否则会自闭

然后这样显然没有包括所有的数,可以枚举并check所有的数qwq

code:


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int P = 1e9 + 1;
const int MAXN = 1e5 + 7;
const int MAXS = 4096;
const int MAXH = 20;
int n, p;
int vis[MAXN], flg[MAXN], Vvis[MAXN], num[MAXN];
int dp[MAXH][MAXS];
ll ans;
inline void build(int x) {
	p = 1;
	for(int i = x; i <= n; i = i * 2, ++p) {
		num[p] = 0;
		flg[p] = 0;
		for(int j = i, q = 1; j <= n; j = j * 3, ++q) {
			++num[p];
			Vvis[j] = 1;//值已经有了qwq
			flg[p] |= (1 << (q - 1));
		}
	}
	p--;
	for(int S = flg[1], qwq = 1; S >= 0 && qwq; S = (S - 1)&flg[1]) {
		if(S == 0)
			qwq = 0;
		if(vis[S]) {
			dp[1][S] = 1;
		}
	}
	return ;
}

void solve(int x) {
	memset(dp, 0, sizeof(dp));
	build(x);
	for(int i = 2; i <= p; ++i) {
		for(int S1 = flg[i], qwq = 1; S1 >= 0 && qwq; S1 = (S1 - 1)&flg[i]) {
			if(S1 == 0)qwq = 0;
			if(!vis[S1])continue;
			for(int S2 = flg[i - 1], qaq = 1; S2 >= 0 && qaq; S2 = (S2 - 1)&flg[i - 1]) {
				if(S2 == 0)qaq = 0;
				if(!vis[S2])continue;
				if(!(S2 & S1)) {
					dp[i][S1] = (dp[i][S1] + dp[i - 1][S2]) % P;
				}
			}
		}
	}
	ll Sum = 0;
	for(int S = flg[p], qwq = 1; S >= 0 && qwq; S = (S - 1)&flg[p]) {
		if(S == 0)qwq = 0;
		if(!vis[S])continue;
		Sum = (Sum + dp[p][S]) % P;
	}
	ans = 1ll * ans * Sum % P;
}

int main() {
	scanf("%d", &n);
	for(int i = 0; i <= 4096; ++i)
		vis[i] = (((i << 1) & i) || ((i >> 1) & i)) ? 0 : 1;
	ans = 1;
	for(int i = 1; i <= n; ++i)
		if(!Vvis[i]) {
			solve(i);
		}
	printf("%lld\n", ans);
	return 0;
}

夏晓光(loveJY)的博客

OI赛制小错误集锦