2024.12.28测试 总结

还是超级无敌寀啊~

T1 赠送笔记本

link

题意
有 $n$ 个宿舍，每个宿舍 $4$ 头奶牛，第 $i$ 个宿舍有 $a_i$ 头牛有笔记本（每头牛的笔记本都不同）。现在所有奶牛都把自己的笔记本送给与自己不同宿舍的奶牛，一头奶牛最多只能接收别人送的一本笔记本，求有多少种赠送方案，答案模 $1234567891$ 。

• $1\le n\le 47$ ，$0\le a_i\le 4$

思路
参考了 这篇题解的T5 。
注意到是计数类问题，考虑组合数，但是很难保证 “一头奶牛只收被人的一本笔记本” 。然后放弃。但是可以是 $DP$ ，看到赠送笔记本可以给前面的牛奶也可以给后面奶牛，担也可以等价于赠送笔记本给前面的奶牛和收下前面的奶牛送出的笔记本。所以设状态 $f_{i,j}$表示考虑到第 $i$ 个宿舍，还剩下 $j$ 本笔记本没送。

• 首先我们考虑接收前面的，设当前这个宿舍 $i$ 接收前面 $k$ 本 $(0\le k\le 4)$，那么贡献为 $A_j^k\times C_4^k$ ；
• 再考虑往前送，设往前送 $p$ 本 $(0\le p\le a_i)$，因为前面有 $4\times (i-1)-({\sum }_{d=1}^{i-1}{a}_d-j)$ 个人还没收到笔记本 （记这个未收到笔记本的人数为 $S$），所以贡献为 $A_S^p\times C_{a_i}^p$ ；

综上，得出状态转移方程：
$$f_{i,j-k+a_i-p}=f_{i-1,j}\times A_j^k\times C_4^k\times A_S^p\times C_{a_i}^p$$
注意一下，如果组合数（如 $A_m^n$ 或 $C_m^n$）要逆元求的话，预处理的过程中可能会爆栈，数很大但是又不能取模，但其实 $m$，$n$ 都很小，所以直接朴素计算即可，复杂度也就 $O(n)$ 。

所以 $DP$ 的总时间复杂度就为 $O(n^2\times 4^4)$ 。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=50;
const ll mod=1234567891;

ll A(ll m,ll n){ ll s=1; for(int i=0;i<n;i++) (s*=(m-i))%=mod; return s; } 
ll C(ll m,ll n){ ll s=1; for(int i=0;i<n;i++) (s*=(m-i))%=mod,(s/=(i+1))%=mod; return s; }

int a[maxn];
ll f[maxn][maxn*4];
int main(){
	int n; cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	int sum=0;
	f[0][0]=1;//f[i][j]：考虑到第 i 个宿舍，还剩下 j 本笔记本没送 
	for(int i=1;i<=n;i++){
		for(int j=0;j<=sum;j++)
			for(int k=0;k<=min(4,j);k++)//k：接收前面的 k 本 
				for(int p=0;p<=a[i];p++)//p：往前面送 p 本给那些还没有接收过本子的奶牛 
					(f[i][j-k+a[i]-p]+=f[i-1][j]*C(4,k)%mod*A(j,k)%mod*C(a[i],p)%mod*A(4*(i-1)-(sum-j),p)%mod)%=mod;
		sum+=a[i];
	}
	cout<<f[n][0];
	return 0;
}

T2 中位数

link
题意
序列的中位数是指：把序列从小到大排序后，下标是 $\frac{n}{2}+1$ 的那个数。给定一个整数序列$a_1,a_2,...,a_n$ ，对于 $a$ 序列的任意一个连续子序列 $a_L,a_{L+1},...,a_R$ （$1\le L\le R\le n$）, 记该连续子序列的中位数为 $b_{L,R}$ 。显然 $b$ 数组共有 $\frac{n\times (n+1)}{2}$ 个整数，求 $b$ 数组的中位数。

• $1\le n\le 10^5，1\le a_i\le 10^9$

思路

前置指示 —— 求中位数有一个很套路的方法：二分一个数 $mid$，对于原序列中 $<mid$ 的数标记为 $-1$；反之标记为 $1$。然后记所有标记求和为 $sum$。若 $sum<0$，说明中位数 $<mid$ ，那么向左继续二分；反之，向右二分。

对于这题，可以有一样的思路。先二分一个数 $mid$，并对原序列进行标记。那么问题就转化为：统计有多少个区间，其标记和 $\ge 0$。
记满足条件的区间有 $cnt$ 个，如果 $cnt\ge \frac{\frac{n\times (n+1)}{2}}{2}+1$，那么说明 $ans\ge mid$，继续向右二分；反之向左二分。那如何计算 $cnt$ ？我们考虑对标记做一个前缀和，设为 $sum$，一个满足条件的区间 $[l,r]$ 要有 $su{m}_r-su{m}_{l-1}\ge 0$ ，用树状数组维护即可。
时间复杂度为 $O(nlo{g}^{2}n)$ 。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;

int n;
ll tree[maxn*2];
void Add(int x,int y){ while(x<=2*n+1) tree[x]+=y,x+=x&(-x); }
ll Query(int x){ ll sum=0; while(x) sum+=tree[x],x-=x&(-x); return sum;}

int a[maxn],c[maxn];
bool Check(int x){
	ll res=0;
	Add(n+1,1);
	for(int i=1;i<=n;i++){
		c[i]=(a[i]>=x?1:-1),c[i]+=c[i-1];
		res+=Query(c[i]+n+1);
		Add(c[i]+n+1,1);
	}
	for(int i=1;i<=n;i++)
		Add(c[i]+n+1,-1);
	Add(n+1,-1);
	return (res>=1ll*n*(n+1)/2/2/*+1*/);//注意细节！
}

int b[maxn];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	int l=0,r=n+1,mid;
	while(l+1<r){
		mid=l+r>>1;
		if(Check(b[mid])) l=mid;
		else r=mid;
	}
	cout<<b[l];
	return 0;
}

T3 好子集

link
题意
有 $n$ 张卡片，每张卡片上有一个整数 $d_i$ ，这些整数之间有可能相同。求有多少个卡片子集（非空）满足子集里的卡片上的数字的乘积正好等于 $goodvalue$ 。多测，答案模 $1e9+7$。

• $g\le 4$，$1\le n\le 100$，$1\le goodvalue\le 2\times 10^9$，$1\le d_i\le 2\times 10^9$

思路
首先可知选出的卡片上的数一定是 $goodvalue$ 的因数。考虑 $DP$ ，设 $f_{i,j}$ 表示前 i 个数中选出的卡片子集的卡片数乘积恰好等于 j 的方案数。转移显而易见。发现状态的第二维 j 有存在意义的选择很少（因为 j 必为 $goodvalue$ 的因数），可以用 map 压缩状态，这就可以通过了。复杂度大概为 $O(nV)$ 。
有一个坑点：由于边界是f[0][1]=1 (因为不能f[0][0]=1)，转移的时候又会有f[i][j]+=f[i-1][j]，导致f[i][1]这一列全部多加了一个虚拟的1(1是f[0][1]的值)，所以最后要记得-1。

代码

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int maxn=105,mod=1e9+7;
ll a[maxn],b[2000005];
map<ll,ll>mp,f[maxn];
signed main(){
	int g; cin>>g;
	while(g--){
		int n2,n=0; ll gdval; cin>>n2>>gdval;
		for(int i=1,x;i<=n2;i++){
			cin>>x;
			if(gdval%x==0) a[++n]=x;
		}
		int tot=0;
		mp[1]=++tot,b[tot]=1;
		f[0][1]=1;
		for(int i=1;i<=n;i++)
			for(int j=1,m=tot;j<=m;j++){
				(f[i][j]+=f[i-1][j])%=mod;
				if(a[i]>gdval/b[j]) continue;
				if(gdval%(b[j]*a[i])!=0) continue;
				if(!mp.count(b[j]*a[i])) mp[b[j]*a[i]]=++tot,b[tot]=b[j]*a[i];
				(f[i][mp[b[j]*a[i]]]+=f[i-1][j])%=mod;
			}
		if(gdval==1) f[n][mp[gdval]]--,(f[n][mp[gdval]]+=mod)%=mod;//this！！！！！！！！
		cout<<f[n][mp[gdval]]<<"\n";
		for(int i=1;i<=n;i++)
			f[i].clear();
		mp.clear();
	}
	return 0;
}

T4 异或

link
题意
有一个长度为 $n$ 的自然数序列 $a$ , 要求将这个序列分成至少 $m$ 个非空连续子段。每个子段的价值为该子段的所有数的按位异或。要使所有子段的价值按位与的结果最大，输出这个最大值。(多测)

• $1\le q\le 12$ ，$1\le m\le n\le 1000$ ， $0\le a_i\le 2^{30}$

思路
对于与二进制有关的题目，考虑拆位（二进制下）处理。从高到低位依次枚举答案的二进制下的每一位为 $0/1$ 。
如果一段数可以划分，则尽早划分，可以证明这是优的。如果划分完可以为一段的数后还剩一些数，则考虑将其拼至最后的已经被划分的那一段之中。最后如果划分完所有数且段数 $\ge m$ ，那么这一位就可以为 $1$，否则只能为 $0$ 。时间复杂度 $O(n)$ 。就是简单贪心 （虽然我考场上不会） ，具体看代码。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int a[maxn];
int main(){
	int q; cin>>q;
	while(q--){
		int n,m; cin>>n>>m;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		int ans=0;
		for(int i=30;i>=0;i--){
			ans|=(1<<i);
			int now=0,cnt=0;
			for(int j=1;j<=n;j++){
				now^=a[j];
				if((now&ans)==ans) now=0,cnt++;
			}
			if(cnt<m||((ans^now)&ans)!=ans) ans^=(1<<i);
		}
		cout<<ans<<"\n";
	}
	return 0;
}

总结

不好评价，其实这些题也很常见，分不高说明本人的积累还是太 $little$ 了。