“蔚来杯“2022牛客暑期多校训练营4（A,D,H,K,N）

 N. Particle Arts

给出若干粒子，两个粒子碰撞之后一个所带的能量变成两个能量相或，一个变成两个能量相与，问经过无数次碰撞之后，所有粒子的方差趋于的数。

思路： 因为位运算的性质，所以若干次操作使得所有数二进制中的1趋向于大数，所以我们可以重构数组，选择方差公式直接计算。方差公式选择不同可能需要int128解决。在此选择：

这样就直接开ll即可。

AC Code：

#include
 
typedef long long ll;
const int N=1e5+5;
ll n,x;
int ans[N],cnt[20];
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>n;
	for(int i=1;i<=n;i++){
		std::cin>>x;
		int k=0;
		for(int j=0;j<=15;j++){
			if(x&(1<
		}
	}
	ll s=0,p=0;
	for(int i=1;i<=n;i++){
		for(int j=15;j>=0;j--){
			if(cnt[j]){
				ans[i]<<=1,ans[i]++;
				cnt[j]--;
			}
			else ans[i]<<=1;
		}
		p+=ans[i]*ans[i];
		s+=ans[i];
	}
	ll aa=p*n-s*s;
	ll bb=n*n;
	ll gcd=std::__gcd(aa,bb);
	std::cout<'/'<'\n';
	return 0;
}

 os：这签到题太难为我了呜呜呜

 K. NIO’s Sword

玩家初始有一把攻击力为0的剑，需要依次击杀n个敌人，仅当攻击力模n与i同余才能击杀第i个敌人。玩家可以升级剑，每次升级相当于在当前攻击力后面添加一个数字，问最少需要几次升级。

思路：标解：

纯纯的推公式题，按照第二个公式，直接枚举k，使得存在一个x[i]在0~10^k[i]范围内，即可满足同余n为i的条件。

AC Code：

#include
 
typedef long long ll;
const int N=1e6+5;
ll n;
ll a[N];
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>n;
	if(n==1){
		std::cout<<0<<'\n';
		return 0;
	}
	a[0]=1;
	for(int i=1;i<10;i++){
		a[i]=a[i-1]*10;
	}
	ll sum=0;
	for(int i=1;i<=n;i++){
		ll x=i-1;
		for(int j=1;j<10;j++){
			ll tmp=x*a[j];
			ll k=((i-tmp)%n+n)%n;
			if(k
				sum+=j;
				break;
			}
		}
	}
	std::cout<'\n';
	return 0;
}

 os：好怪，还能这样

D. Jobs (Easy Version)

每个公司对于每个应聘者有三个评价标准，只有三个评价标准都满足，该人才会被该公司录取，某个公司只要存在一个职位该人满足条件，即可进入该公司工作，给出若干个应聘者，询问每人可以进入几个公司工作。

思路：大佬的思路n<=10,m<=400。暴力做的话，开一个三维的数组s[10][400][400][400]，求一下前缀或，表示某一个公司的某一个工作的属性能否有工作可以胜任，时间比较极限，考虑优化。其实这是比较经典的二维偏序做法，少开一维，s[10][400][400]表示某一个公司在满足a和b的要求后c最低是多少，然后求前缀最小值，相当于把a<=i和b<=j里最小的c找到，也就能够满足要求了。那么我们就可以m^2预处理出，然后直接查询。

 AC Code：

#include 
 
typedef long long ll;
#define INF 0x3f3f3f3f
const int N=405;
const int mod=998244353;
int s[12][N][N];
int n,m;
ll pow_seed[2000005];
 
int solve(int a,int b,int c){
	int res=0;
	for(int u=1;u<=n;u++){
		if(s[u][a][b]<=c) res++;
	}
	return res;
}
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>n>>m;
	memset(s,INF,sizeof(s));
	for(int u=1;u<=n;u++){
		int cnt;
		std::cin>>cnt;
		while(cnt--){
			int a,b,c;
			std::cin>>a>>b>>c;
			s[u][a][b]=std::min(s[u][a][b],c);
		}
		for(int i=1;i<=400;i++){
			for(int j=1;j<=400;j++){
				s[u][i][j]=std::min(s[u][i][j],s[u][i-1][j]);
				s[u][i][j]=std::min(s[u][i][j],s[u][i][j-1]);
			}
		}
	}
	int seed;
	std::cin>>seed;
	std::mt19937 rng(seed);
	std::uniform_int_distribution<> u(1,400);
	pow_seed[0]=1;
	for(int i=1;i<=m;i++){
		pow_seed[i]=(pow_seed[i-1]*seed)%mod;
	}
	ll ans=0,lastans=0;
	for(int i=1;i<=m;i++){
		int IQ=(u(rng)^lastans)%400+1;
		int EQ=(u(rng)^lastans)%400+1;
		int AQ=(u(rng)^lastans)%400+1;
		lastans=solve(IQ,EQ,AQ);
		ans=(ans+lastans*pow_seed[m-i])%mod;
	}
	std::cout<'\n';
	return 0;
}

Problem H. Wall Builder II

现有n个1*1的，n-1个1*2的，n-2个1*3的，……1个1*n的板子，怎样使用这些板子拼成一个矩形并使得矩形周长最短。

思路：我们易知，当长和宽长度尽量相差小一些，周长就小。基于这个结论，我们直接找到最小差值的长和宽，贪心去摆每一层，一定存在一种摆满该规格矩形的方式。

AC Code：

#include 
 
typedef long long ll;
const int N=1e5+5;
int t,n;
int a[N];
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n;
		int s=0;
		for(int i=1;i<=n;i++){
			s+=(n-i+1)*i;
			a[i]=n-i+1;
		}
		int y=0;
		for(int i=1;i*i<=s;i++){
			if(s%i==0) y=i;
		}
		int x=s/y;
		int C=x*2+y*2;
		std::cout<'\n';
		for(int i=1;i<=y;i++){
			int res=0;
			for(int k=n;k>=1;k--){
				while(a[k]&&x-res>=k){
					std::cout<' '<-1<<' '<' '<'\n';
					res+=k;
					a[k]--;
					if(res==x) break;
				}
			}
		}
	}
	return 0;
}

  A. Task Computing

给出n个数，从中选择m个数并任意排列，最大化给出的计算式。

思路：因为可以任意排列，我们考虑选择了一个数后放在已选数组的前面还是后面。若放在后面，对于答案的贡献是w[i]*p[(1~i-1)]，这样就涉及到1~i的值，并不好确定；再考虑放在数组前面，这样我们假设它的目前的价值为now，那么我们在队头加入一个{w, p}，价值就会变为now*p+w，因为我们发现在前面加相当于后面所有的数在第二项上又多乘了一个p，而对于新加入的物品本身在第一位还要加上一个w。 然后就可以考虑怎样选择，化简计算式如下：（摘自严格鸽）

 因为m的范围很小，直接背包找最大值即可。

AC Code：

#include 
 
typedef long long ll;
const int N=2e5+5;
int t,n,m;
double f[N][25];
 
struct node{
	double w,p;
	bool operator <(const node &a) const{
		return w+p*a.w
	}
}a[N];
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>n>>m;
	for(int i=1;i<=n;i++){
		std::cin>>a[i].w;
	}
	for(int i=1;i<=n;i++){
		std::cin>>a[i].p;
		a[i].p/=10000;
	}
	std::sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=std::min(i,m);j++){
			f[i][j]=std::max(f[i-1][j],a[i].w+a[i].p*f[i-1][j-1]);
		}
	}
	std::cout<setprecision(10)<'\n';
	return 0;
}

os：其实整体看来也是个不算难的大体方向，但是主要是前期的分析并不好想。

嗯，，，计算几何啊，，还没接触过呢先算了吧