The 17th Heilongjiang Provincial Collegiate Programming Contest

A. Bookshelf Filling

对于求书架的最小宽度，其实是不好做的。但是如果把问题转换成给定一个宽度，判断这个宽度是否满足要求，那么就可以二分求解。注意到，宽度的变化也是满足单调性的。

需要注意的是，书本要horizontally水平放置，如果英语不好的话会做假题（点名某人

ll a,b,n,m,h;
bool check(ll x){
	ll ans1=(h-a)*(n/b);
	ll ans2=((x-(n/b)*b)/b)*(h-b);
	return (ans1+ans2)>=m-(x-n);
}
void solves(){
	cin>>a>>b>>n>>m>>h;
	ll l=n+1,r=n+m;
	while(l<r){
		ll mid=(l+r)>>1;
		if(check(mid))
			r=mid;
		else
			l=mid+1;
	}
	cout<<l<<endl;
}

D. Collision Detector

$O_1$的圆心是红色区域的内点的话就输出yes

不想写代码

E. Exclusive Multiplication

莫反不会做wfl

对于$n=\prod p_i^{a_i}$，定义$f$为

$f(n)=\prod_{i=1}^{m}p_i^{a_i\%2}$

对于给定序列$\{b_i\}$，求

$\sum_{i=1}^n\sum_{j=i+1}^{n}f(b_i×b_j)\quad mod \;(10^9+7)\qquad(1)$

注意到，$f$是积性函数，但不是完全积性函数。对于$f(b_i×b_j)$，我们考虑将其拆成$f(b_i)f(b_j)h(b_i,b_j)$的形式。

观察$f(n)$的定义，容易发现当$n$的质因子的重数为偶数时，对$f$不产生贡献。即

$f(b_j × b_j)=f(\frac{b_i}{gcd(b_i,b_j)} × \frac{b_j}{gcd(b_i,b_j)} × gcd(b_i,b_j)^2 )=f(\frac{b_i}{gcd(b_i,b_j)} × \frac{b_j}{gcd(b_i,b_j)} )=f(\frac{b_i}{gcd(b_i,b_j)}) × f(\frac{b_j}{gcd(b_i,b_j)})$

所以$(1)$可化简为

$\begin{aligned} \sum_{i=1}^n\sum_{j=i+1}^{n}f(b_i×b_j) &=\frac{\sum_{i=1}^n\sum_{j=1}^{n}f(b_i×b_j)-\sum_{i=1}^{n}f(b_i^2)}{2}\\ &=\frac{\sum_{i=1}^n\sum_{j=1}^{n}f(b_i×b_j)-n}{2}\\ &=\frac{\sum_{i=1}^n\sum_{j=1}^{n}f(\frac{b_i}{gcd(b_i,b_j)}) × f(\frac{b_j}{gcd(b_i,b_j)})-n}{2}\\ &=\frac{\sum_{i=1}^n\sum_{j=1}^{n}\frac{f(b_i)}{f(gcd(b_i,b_j))} × \frac{f(b_j)}{f(gcd(b_i,b_j))}-n}{2}\\ &=\frac{\sum_{i=1}^n\sum_{j=1}^{n}\frac{f(b_i) × f(b_j)}{f^2(gcd(b_i,b_j))} -n}{2}\\ \end{aligned}$

对于$\frac{f(b_i) × f(b_j)}{f^2(gcd(b_i,b_j))}$，

ps这个先暂时🕊一下

F. 342 and Xiangqi

枚举49种情况取最小值，但其实由于具有对称性，只需要枚举一半。

int mp[10][10]={
	{0},
	{0,0,1,1,2,3,3,4},//1
	{0,1,0,2,1,2,2,3},//2
	{0,1,2,0,1,2,2,3},//3
	{0,2,1,1,0,1,1,2},//4
	{0,3,2,2,1,0,2,1},//5
	{0,3,2,2,1,2,0,1},//6
	{0,4,3,3,2,1,1,0},//7
};
void solves(){
	int a1,a2,b1,b2;
	cin>>a1>>a2>>b1>>b2;
	cout<<min(mp[a1][b1]+mp[a2][b2],mp[a2][b1]+mp[a1][b2])<<endl;
}

H. Kanbun

主要是一开始看了很久才看明白在讲啥吧。。递归一下就好，栈模拟一下也行。不过一开始因为递归写的太无脑了，直接t了一发。

int n;string s;
int dfs(int idx){
	for(int i=idx;i<n;i++){
		if(s[i]=='('){
			int r=dfs(i+1);
			cout<<i+1<<" ";
			i=r;
			continue;
		}
		cout<<i+1<<" ";
		if(s[i]==')')
			return i;
	}
}
void solves(){
	cin>>n>>s;
	dfs(0);
}

I. Equal Sum Arrays

对于整数$k$的分拆其实是可以转换成探求方程的整数解个数（Problem 1.0.0.）的模型，形如求共有多少个不同的非负整数向量$(x_1,x_2,...,x_r)$，满足$x_1+x_2+...+x_r=n$的问题。

对于不同的$r$进行求和，发现其实是一个二项式展开系数的求和。

打赏