填坑ing

T1 card

神仙 czk 在休息时间和同学们玩卡牌游戏。 一共有 \(n\) 张卡牌，每张卡牌上有一个数字 \(A_i\)，每次可以从中选出 \(k\) 张卡牌。一种选取方 案的幸运值为这 \(k\) 张卡牌上数的异或和。 神仙 czk 为了考倒你们，想知道所有选取方案的幸运值之和。 但是良心搬题人为了不为难大家，只需要你们输出所有选取方案的幸运值之和除以 \(998244353\) 的余数，

对于 30% 的数据 \(n\leq 20\) ,对于 100% 的数据 \(n\leq 10^5\)

30pts 随便状压一下就可以。

100pts

考虑把每一位分开来考虑。假设当前这一位上为 \(1\) 个数字个数为 \(num1\) ,那么 为零的就有 \(n-num1\)

对答案的贡献就是 \(\displaystyle\sum_{i=1, i 为奇数}^{k} C_{num1}^{i} \times C_{num0}^{k-i} \times 2 ^i\)

直接模拟就做完了。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N = 1e5+10;
const int p = 998244353;
int n,m,x,ans;
int jz[N],inv[N],num[35][2],base[35];
inline int read()
{
	int s = 0,w = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
int ksm(int a,int b)
{
	int res = 1;
	for(; b; b >>= 1)
	{
		if(b & 1) res = res * a % p;
		a = a * a % p;
	}
	return res;
}
void YYCH()
{
	jz[0] = inv[0] = 1;
	for(int i = 1; i <= N-5; i++) jz[i] = jz[i-1] * i % p;
	inv[N-5] = ksm(jz[N-5],p-2);
	for(int i = N-6; i >= 1; i--) inv[i] = inv[i+1] * (i+1) % p;
}
int C(int n,int m)
{
	if(n < m) return 0;
	return jz[n] * inv[m] % p * inv[n-m] % p;
}
signed main()
{
	freopen("card.in","r",stdin);
	freopen("card.out","w",stdout);
	n = read(); m = read(); base[0] = 1; YYCH();
	for(int i = 1; i <= 32; i++) base[i] = base[i-1] * 2 % p;
	for(int i = 1; i <= n; i++)
	{
		x = read();
		for(int j = 0; j <= 32; j++)
		{
			int c = (x>>j) & 1;
			num[j][c]++; 
		}
	}
	for(int i = 0; i <= 32; i++)
	{
		for(int j = 1; j <= min(num[i][1],m); j += 2)
		{
			ans = (ans + C(num[i][1],j) * C(num[i][0],m-j) % p * base[i] % p) % p;
		}
	}
	printf("%lld\n",ans);
	fclose(stdin); fclose(stdout);
	return 0;
}

T2 赌注

Desprition

\(N\) 个庄家。你可以到庄家那边下注，每次可以猜大猜小，猜一次一元钱。每一次开彩前，你都可以到任意个庄家那里下赌注。如果开彩结果是大，你就可以得到你之前猜大的庄家相应的 \(a_i\) 元钱。如果开彩结果是小，你就可以得到你之前猜小的庄家相应的 \(b_i\) 元钱。你可以在同一个庄家那里既猜大又猜小（这样是两块钱），也可以什么都不猜（这样不用钱）。但是阴险狡诈的庄家会根据你下注的信息控制开彩的结果，让你赢的钱数尽量少。问怎么样下注，才能赢走最多的钱。输出一个四位小数。

对于 100% 的数据 \(n\leq 10^5\)

sloution

假设我们现在猜大可以得到 \(sum1\) 元，猜小可以得到 \(sum2\) 元，一共猜了 \(x+y\) 次。

那么答案就是 \(max(sum1-sum2) - x-y\). 我们要最大化这个价值。

很显然，当猜的次数一定的时候，我们希望 \(sum1,sum2\) 尽可能的大。

所以把 \(a_i,b_i\) 分别按从小到大排一遍序，处理个前缀和。

用双指针扫一遍就能得到答案。

考试的时候没注意到边界 \(100pts -> 70pts\)

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int n;
double a[N],b[N],ans;
bool comp(double a,double b)
{
	return a > b;
}
int main()
{
	freopen("coin.in","r",stdin);
	freopen("coin.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lf%lf",&a[i],&b[i]);
	}
	sort(a+1,a+n+1,comp);
	sort(b+1,b+n+1,comp);
	for(int i = 1; i <= n; i++) a[i] = a[i-1] + a[i];
	for(int i = 1; i <= n; i++) b[i] = b[i-1] + b[i];
	int l = 1;
	for(int i = 1; i <= n; i++)
	{
		if(l > n) break;
		while(l <= n && b[l] <= a[i]) l++;
		if(b[l] > a[i] || l > n) l--;
		ans = max(ans,b[l] - (i + l));
	}
	l = 1;
	for(int i = 1; i <= n; i++)
	{
		if(l > n) break;
		while(l <= n && a[l] <= b[i]) l++;
		if(a[l] > b[i] || l > n) l--;
		ans = max(ans,a[l] - (i+l));
	}
	printf("%.4lf",ans);
	fclose(stdin); fclose(stdout);
	return 0;
}