qbxtD3 && NOIP提高组考前刷题冲刺班（第三场）

枚举哪一位开始小于于k

前k位都是子集,后k位随便选即可

也就是说前k位预处理出来,后面的最高位都要小于一个位,去这样统计

但是最后要处理正好等于k的情况


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 7;
int n, k;
ll ans, ans1;
int x, y;
ll f[MAXN], f2[MAXN];
int main() {
	// freopen("data.in", "r", stdin);
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d", &x, &y);
		if(x > k)continue;
		if((x & k) == x) {
			ans1 += y;
		}
		bool flg = 1;
		for(int g = 30; g >= 0; --g) {
			if((x >> g & 1) && !(k >> g & 1)) {//我有你没有,gg了
				break;
			}
			if(!flg && (x >> g & 1)) {
				flg = 1;
				f2[g] += y;
			}
			if(flg && !(x >> g & 1) && (k >> g & 1)) {
				f[g] += y;//这一位是1他这一位不是1
			}
		}
	}
	//我们钦定最高位一定已经出现了
	//然后才算
	for(int i = 1; i <= 30; ++i) {
		f2[i] += f2[i - 1];
	}
	ans = ans1;
	// printf("%lld\n", ans1);
	for(int g = 0; g <= 30; ++g) {
		if(k >> g & 1)
			ans = max(ans, f[g] + f2[g - 1]);
	}
	printf("%lld\n", ans);
	return 0;
}
/*
4 136
135 5
23 5
136 9
7 2
*/

洛谷的一道原题:绝世好题



#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 7;

int n;
int a[MAXN], dp[MAXN], ans;

signed main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);
	for(int i = 1; i <= n; ++i) {
		int qwq = 0;
		for(int j = 0; j <= 30; ++j) {
			if(a[i] & (1 << j)) {
				qwq = max(dp[j], qwq);
			}
		}
		for(int j = 0; j <= 30; ++j) {
			if(a[i] & (1 << j)) {
				dp[j] = max(dp[j] + 1, qwq + 1);
			}
		}
	}
	for(int j = 0; j <= 30; ++j) {
		ans = max(ans, dp[j]);
	}
	printf("%d\n", ans);
	return 0;

}

...

爆搜考虑整数划分

然后转移再枚举一个整数划分

然后两个整数划分再看看是否合法

然后当m<=5的时候

好像是有规律的,相当于一个直线下的下取整

正解:

观察发现,我们可以单独考虑每个石子,然后每次一个石子被动就表一个1,否则就标一个0

然后又因为相当于我们给每个石子分配01串应该不同,要是都相同岂不是出大问题(一堆)

所以我们二分答案来考虑一个mid是否合法

然后我们判断合法其实就是看看本质不同的0/1串个数在超过n的情况下能不能用1的个数小于 $m*mid$

显然0/1串长度是一样的是我们操作序列长,设其为x

而这个东西是能够构造到上界的,就是 $1*C_{1,x}$ + $2*C_{2,x}$ ....

那么我们就可以二分这个答案用组合数判断了

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;

int T, n, m;

inline bool chk(int x) {
	ll nw = 1, qb = n, su = 0;
	// printf("%d ?\n", x);
	for(int i = 0; i <= x; ++i) {
		nw = min(nw, qb);
		qb -= nw;
		su += i * nw;
		// printf("%d %lld %lld %lld \n", i, qb, su, nw);
		if(qb <= 0)break;
		nw = nw * (x - i) / (i + 1);
	}
	if(qb > 0)return 0;
	return su <= 1ll * x * m;
}

int main() {
	scanf("%d", &T);
	for(int i = 1; i <= T; ++i) {
		scanf("%d%d", &n, &m);
		int l = 1, r = n, mid, ans;
		while(l <= r) {
			mid = (l + r) >> 1;
			if(chk(mid)) {
				r = mid - 1;
				ans = mid;
			} else {
				l = mid + 1;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

#143. Jump

就是说会返回两个串异或后的 $n-popcount$

先想问出 $n/2$ ,随机一些01串去问即可

成功的概率为 $\binom{n}{2}*2^{-n/2}$

随机出之后我们就可以枚举一个位置i,改变 $a_1,a_i$ 然后询问 $a_1,a_i$

如果得到n/2,我们就有目标串 $a_1$ 和 $a_i$ 这两个位置相同

否则我们就是 $a_1$ 和 $a_i$ 两个位置不同

那么我们就这样问n次即可

最后得到哪些和1相同哪些和0相同,再问两次

夏晓光(loveJY)的博客

qbxtD3 && NOIP提高组考前刷题冲刺班（第三场）

qbxtD2