2024年6月赛丙组

丙组6月卷涉及了：枚举、位运算、简单数论、数学或宽搜、单调队列优化。
按CCF考纲来看，已经超出入门组范畴，属于入门组+或提高组-难度。

T1 布置会场（二）

可以用选择结构解决，但是漏情况会错。
数据并不大，不妨用枚举遍历所有情况来寻找答案。
一束花用$c$朵，不妨枚举束的数量，剩余的单买。

#include<bits/stdc++.h>  
using namespace std;  
int n,a,b,c,ans=2e9;   
int main()  
{  
	ios::sync_with_stdio(0);  
	cin.tie(0);  
	cout.tie(0);  
	cin>>n>>a>>b>>c;  
	for(int i = 0; i <= n/c+1; i++){  
		int m = n - i*c;  
		int tmp = i*b;  
		if(m>0) tmp += m*a;  
		ans = min(ans,tmp);  
	}  
	cout<<ans;  
	return 0;  
}  
  

为什么枚举的范围是$n/c+1$，而不是$n/c$？这是因为有可能剩余的买一束比单买便宜，题目也没说刚好凑到$n$朵，只要价格便宜就行（多出来的可以扔……）。

T2 位运算

还没接触过位运算的会无从下手。
来看下需要满足的三个条件：
$n\mathrm{\&}m\ne 0$
$n\mid m\ne 0$
$n\oplus m\ne 0$
题目要求找出最小的正整数$m$，第一个条件，只要找出$n$最后一个二进制位$1$，这样数字足够小，也满足条件。
第二个条件，用第一个条件找出来的$m$符合要求。因为$1|1=1$。
第三个条件是异或，异或是当二进制位不同的时候结果为$1$。
共有两种情况：

• $n$有多个二进制位$1$，那么最终答案还是$n$最后一个二进制位$1$，因为$m$其他二进制位为$0$，而$n$有多个二进制位$1$，那么异或结果必然不等于$0$。
• $n$只有一个二进制位$1$，也有两种情况：(1)$1$在最后一位，那么要在前$1$位补$1$，即答案$3$。(2)$1$不在最后一位，那么最后$1$位补$1$

#include<bits/stdc++.h>  
using namespace std;  
int n,m;  
int main()  
{  
	ios::sync_with_stdio(0);  
	cin.tie(0);  
	cout.tie(0);  
	cin>>n;  
	m = n & -n;  
	if(__builtin_popcount(n)>1) cout<<m;  
	else{  
		if(m==1) cout<<3;  
		else cout<<(m|1)<<endl;  //或者输出m+1
	}  
	return 0;  
}  
  

学过树状数组的知道n&-n可以算出$n$最后一个二进制$1$，例如$5$，二进制$(101{)}_2$，那么$5\mathrm{\&}-5=(001{)}_2$。
$\mathrm{\_}\mathrm{\_}builtin\mathrm{\_}popcount()$能够快速计算出二进制$1$的个数，会位运算的也可以手动计算二进制位$1$的个数（移位判断）

T3 完全平方数对

分解质因数+思维
应该是这份试题中最优价值的一题。
题意：两个因数相乘，因数不超过$n$的前提下，乘积为完全平方数的数对有多少个（两个不同的因数交换位置属于不同的数对）。
对整数$i$($1\le i\le n$)，符合要求乘积最大的完全平方数数对为$(i,i)$，现在要计算$(i,j)$是平方数的数对有几个（$1\le j\le i$)。
如果直接枚举，$n$最大为${10}^5$，显然会超时。
完全平方数的中不同的质因数必须偶数个才能形成完全平方数。
例如$2\ast 2\ast 3=12$，质数$3$只有一个，如果在配一个$3$就能形成完全平方数：$2\ast 2\ast 3\ast 3=36$。
根据这个思路，我们可以先对$i$分解质因数，然后质因数如果是奇数个，则补上一个质因数，求出需要补的因数$j$（$j$由若干个需要补的质因数相乘得到），这样可以找出符合要求最小完全平方数的数对$(i,j)$。
那么$i$的其他数对如何找呢？
以$175$为例：$5\ast 5\ast 7=175$
显然最小的$j=7$。
最大的数对为$(i,i)=(175,175)$
也就是$5\ast 5\ast 7\ast 7\ast 5\ast 5$是符合要求的最大数对。
从因数角度入手，只要因数成双的，它们的乘积必然是完全平方数。

通过上面的例子可以发现规律，找到最小的$j$后，和$i$能形成符合要求的数对为：$j\ast 1\ast 1$、$j\ast 2\ast 2$、$j\ast 3\ast 3$、$j\ast 4\ast 4$、$j\ast 5\ast 5$
那么在整数$i=175$中，去掉配对的因数$7$后，剩下的为$5\ast 5$，那么之后补因数的时候是不能超过$5\ast 5$的，显然符合要求的数对数量为$sqrt(5)\ast 2$，因为交换位置算一种方案，所以要cheng乘$2$，但是$(i,i)$只能算一种方案，所以最后方案数要减去$n$，一共有$n$个两个数相同的数对：$(1,1)$、$(2,2)$、$(3,3)$...$(n,n)$。

#include<bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
ll n,ans;  
void divid(int x)  
{  
	int tx = x, res = 1;  //res用来求最小的数对(i,res)  
	for(int i = 2; i <= sqrt(x); i++){  
		int cnt = 0;       //cnt用来统计相同质因数个数  
		while(x % i==0) x /= i,cnt++;  
		if(cnt % 2==1) res *= i;  
	}  
	if(x > 1) res *= x;  
	ans += int(sqrt(tx / res)) * 2;  //最终符合要求的数对  
}  
int main()  
{  
	ios::sync_with_stdio(0);  
	cin.tie(0);  
	cout.tie(0);  
	cin>>n;  
	for(int i = 1; i <= n; i++) divid(i);  
	cout<<ans - n<<endl;  //扣除n对(i,i)  
	return 0;  
}  
  

T4 超级奇数

数学规律或宽搜
这里讲一下宽搜做法。
超级奇数只有1、3、5、7、9组成，最大为$9$位数，所以超级奇数一共有：$5+5^2+5^3+5^4+5^5+5^6+5^7+5^8+5^9=2441405$
可以发现并不多，所以直接用宽搜扩展寻找即可。

#include<bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
ll n,ans,b[]={1,3,5,7,9},cnt;  
queue<ll> q;   
int main()  
{  
	ios::sync_with_stdio(0);  
	cin.tie(0);  
	cout.tie(0);  
	cin>>n;  
	for(int i = 0; i < 5; i++) q.push(b[i]);  
	while(q.size()){  
		ll x = q.front();  
		q.pop();  
		cnt++;  
		if(x == n){  
			cout<<cnt<<endl;  
			return 0;  
		}  
		for(int i = 0; i < 5; i++){  
			ll t = x * 10 + b[i];  
			q.push(t);  
		}  
	}  
	return 0;  
}  
  

T5 环岛旅行

单调队列优化
这题是一本通旅行问题的简化版。
环形问题，先破环成链，即用$2$倍长度的线性序列代替环形。
例如，假设$n=5$，环形序列为$1$,$2$,$3$,$4$,$5$，$2$倍长度序列为$1$,$2$,$3$,$4$,$5$,$1$,$2$,$3$,$4$,$5$。
序列编号为$1$到$10$，则求从编号$1$的点顺时针出发能否回到编号$1$的点，就是求从编号$1$的点出发能否到达编号$6$的点。
能否到达取决于油量是否够，所以途中的任意一个加油站，存储的油量必须大于等于消耗的油量，才能到达下一个加油站。
设$p[i]$表示第$i$个加油站可以加的油量，$d[i]$表示从第$i$个点走到第$i+1$个点消耗的油量，则$p[i]-d[i]$就表示从第$i$个点到第$i+1$个点油量的增减情况。
考虑顺时针情况，$s[i]=s[i-1]+p[i]-d[i]$表示剩余油量的前缀和，也就是说$s[i]$表示刚走到第$i+1$个点还未加油时汽车的剩余油量，如果油是负数，则说明无法到达。
那么在区间$[i,n+i]$共$n$个加油站，每个站点的剩余油量都不能为负数，否则无法到达。所以会想到枚举这些区间和，如果油负数，则无法到达，但是这样时间复杂度很高。其实我们的目标只要找最小的前缀和，找到最小的前缀和不就可以计算最小的区间和吗？那么在一个区间中寻找最小值，就可以使用单调队列优化。
破环成链和前缀和

	for(int i = 1; i <= n; i++){  
		cin>>p[i]>>c[i];  
		p[n+i] = p[i];  
		c[n+i] = c[i];  
	}  
	for(int i = 1; i < 2 * n; i++) sum[i] = sum[i-1] + p[i] - c[i];  

单调队列维护

	int head = 0, tail = 0;  
	for(int i = 1; i <= 2 * n; i++){  
		while(head <= tail && i - q[head] >= n) head++;  
		while(head <= tail && sum[q[tail]] >= sum[i]) tail--;  
		q[++tail] = i;  
		if(i >= n && sum[q[head]] - sum[i - n] >= 0){ //i为1的时候表示走向2，所以i为n的时候表示走向1  
			cout<<i - n + 1;  
			return 0;  
		}   
	}  
	cout<<0<<endl;  //没有符合要求的起点  

因为是顺时针，所以当$i=n$的时候，表示回到原点。需要注意的是，第$i=n$的时候，表示走回加油站$1$。
$sum[q[head]]-sum[i-n]$计算的是区间和，如果最小的区间和大于等于$0$，那么其他区间和必然大于$0$，就不会出现半路没油的情况，也就能返回起点。