题解 - 南昌五中初一第二次阶段测试 & ooliver 的复仇

说在前面

~~这次题目确实有点难~~，但是大家要习惯信奥比赛中遇到难题时的压力，所以没有必要抱怨题目的难度，~~毕竟大家都不会~~……

信奥分组

不难发现，偶数+偶数=偶数，所以只要 $n$ 是偶数就可以了？
因为每组人数既要大于 0，也要为偶数，所以每组最少 2 人，也就是说总人数最少要 4 个人。
那么 $n$ 要是大于或等于 4 的偶数。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    cin>>n;
    if(n%2==0&&n>=4) cout<<"no problem";
    else cout<<"no!!!";
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    cin>>n;
    if(n%2==0&&n>=4) cout<<"no problem";
    else cout<<"no!!!";
    return 0;
}

分数比较

如果你 50 pts，盲猜你使用了 double 类型计算 $\frac{a}{b}$ ，这样会出现一个问题，就是 double 类型最多存储到小数点后 15-16 位，所以如果两个小数知道小数点后 16 位才有不一样的地方，用 double 类型就比较不出来他们的大小。

那怎么办呢？我们知道有个东西叫做交叉相乘，在 $a,b,c,d>0$ 的情况下， $\frac{a}{b} > \frac{c}{d}$ 等价于 $ad > bc$ ，同理可知，比较 $\frac{a}{b}$ 与 $\frac{c}{d}$ 的大小等价于比较 $ad$ 与 $bc$ 的大小，这样就转化为了正整数的大小比较，不会出现精度问题。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T;
int a,b,c,d;
signed main(){
	cin>>T;
	while(T--){
		cin>>a>>b>>c>>d;
		if(a*d>b*c) cout<<"YE5\n";
		else if(a*d==b*c) cout<<"TlE\n";
		else cout<<"N0\n";
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T;
int a,b,c,d;
signed main(){
	cin>>T;
	while(T--){
		cin>>a>>b>>c>>d;
		if(a*d>b*c) cout<<"YE5\n";
		else if(a*d==b*c) cout<<"TlE\n";
		else cout<<"N0\n";
	}
	return 0;
}

还有一种邪修方法，就是使用 long double 类型，这也是个存储小数的类型，且精度更高，足够支撑 AC 这道题。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T;
long double a,b,c,d;
signed main(){
	cin>>T;
	while(T--){
		cin>>a>>b>>c>>d;
		if(a/b>c/d) cout<<"YE5\n";
		else if(a/b==c/d) cout<<"TlE\n";
		else cout<<"N0\n";
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T;
long double a,b,c,d;
signed main(){
	cin>>T;
	while(T--){
		cin>>a>>b>>c>>d;
		if(a/b>c/d) cout<<"YE5\n";
		else if(a/b==c/d) cout<<"TlE\n";
		else cout<<"N0\n";
	}
	return 0;
}

求圆周率

观察到分母都是奇数，第 $i$ 个奇数为 $2i-1$ ，且当 $i$ 是奇数时它前面的符号是加号，当 $i$ 是偶数时它前面的符号是减号，计算出等式右边的值后乘 4 就是 $\pi$ 了，记得保留 4 位小数。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
double pai=0;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		if(i%2==1) pai+=1.0/(2*i-1);
		else pai-=1.0/(2*i-1);
	}
	cout<<fixed<<setprecision(6)<<pai*4;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n;
double pai=0;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		if(i%2==1) pai+=1.0/(2*i-1);
		else pai-=1.0/(2*i-1);
	}
	cout<<fixed<<setprecision(6)<<pai*4;
	return 0;
}

系数展开

可以先分析一下题目：

(2x + 3) \cdot(x - 1) = 2x^2 + x - 3

这里展开后的所有系数与常数项之和显然是 $2+1-3=0$ 。但是对于 $(x+a)^n$ 这样的式子就不太好求展开式，那怎么办呢？

考虑转化问题，怎么把 $2x^2 + x - 3$ 转化为 $2+1-3$ ？不难发现，当我们令 $x=1$ 时， $2x^2 + x - 3$ 的值就正好等于 $2+1-3$ 。

所以我们直接令 $x=1$ ，则问题就转化成了求 $(1+a)^n$ ，直接使用 pow 函数即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	long long a,n;
	cin>>a>>n;
	cout<<(long long)pow(a+1,n);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main(){
	long long a,n;
	cin>>a>>n;
	cout<<(long long)pow(a+1,n);
	return 0;
}

多维空间

这是一道阅读理解题，只要你读懂了，这题就变得很简单。

作为三维生物， $n\le 3$ 时我们是可以想象的。

$n=1$ 时，此时两个 $n$ 维体就变成了两个线段，题目也简化成了已知两个线段的坐标，求两个线段重合部分的长度。这个时候我们可以分类讨论两个线段左右端点之间的关系，但这里给出一个更简单的理解方法：
我们可以考虑分别求出重合部分的左右端点，显然左端点应该是两个线段左端点的最大值，右端点时两个线段右端点的最小值，搞不明白的可以多画几个图试一试。
当然，可能会出现左端点大于右端点的情况，这表示两个端点没有重合部分。
$n=2$ 时，问题变成了求两个矩形，也就是长方形的重合部分的面积。面积等于长乘高，所以我们可以借用一维求线段重合部分长度的代码，分别求出两个长方形长和宽的重合线段的长度，再相乘即可。
$n=3$ 时，讨论重合长方体的长、宽、高即可。

所以根据以上的规律，我们只需要找到两个 $n$ 维体在每一位的重合线段的长度并相乘即可。

记得考虑没有重合部分的情况，也就是在某一维两线段无重合，直接记重合长度为 0，那么乘起来就是 0 了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int mod=10003;
int n,ans=1;
int a[N],b[N],c[N],d[N];
int f(int m,int n,int p,int q){
	return max(0,min(n,q)-max(m,p));
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i]; 
	for(int i=1;i<=n;i++) cin>>b[i]; 
	for(int i=1;i<=n;i++) cin>>c[i]; 
	for(int i=1;i<=n;i++) cin>>d[i]; 
	for(int i=1;i<=n;i++) ans=ans*f(a[i],b[i],c[i],d[i])%mod;
	cout<<ans;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int mod=10003;
int n,ans=1;
int a[N],b[N],c[N],d[N];
int f(int m,int n,int p,int q){
	return max(0,min(n,q)-max(m,p));
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i]; 
	for(int i=1;i<=n;i++) cin>>b[i]; 
	for(int i=1;i<=n;i++) cin>>c[i]; 
	for(int i=1;i<=n;i++) cin>>d[i]; 
	for(int i=1;i<=n;i++) ans=ans*f(a[i],b[i],c[i],d[i])%mod;
	cout<<ans;
	return 0;
}

勾八题目

首先，对于数字串中出现的 1，2，4，8 一定要修改，因为他们分别是 2 的 0 到 3 次方幂。

这个时候如果我们枚举所有小于 $10^{(10^6)}$ 的 $2^k(k\ge 0)$ ，会惊奇地发现只有神奇的 65536 不包含 1，2，4，8 这些数字。

所以我们修改所有的 1，2，4，8 后再特殊判断一下是否出现了 65536 即可。

注意还有一种特殊情况，就是 655365536。这里虽然出现了两个 65536，但是只需要删除中间的 6 即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	int T;
	cin>>T;
	while(T--){
		string a;
		int ans=0;
		cin>>a;
		for(int i=0;i<a.size();i++){
			if(a[i]=='6'&&a[i+1]=='5'&&a[i+2]=='5'&&a[i+3]=='3'&&a[i+4]=='6')
				ans++,i+=4;
		}
		for(int i=0;i<a.size();i++){
			if(a[i]=='1'||a[i]=='2'||a[i]=='4'||a[i]=='8')
				ans++;
		}
		cout<<ans<<'\n';
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	int T;
	cin>>T;
	while(T--){
		string a;
		int ans=0;
		cin>>a;
		for(int i=0;i<a.size();i++){
			if(a[i]=='6'&&a[i+1]=='5'&&a[i+2]=='5'&&a[i+3]=='3'&&a[i+4]=='6')
				ans++,i+=4;
		}
		for(int i=0;i<a.size();i++){
			if(a[i]=='1'||a[i]=='2'||a[i]=='4'||a[i]=='8')
				ans++;
		}
		cout<<ans<<'\n';
	}
	return 0;
}

序列变换

考虑一个相差为 1 的数对对整个 $a$ 序列的贡献：

设有 $x$ ， $x+1$ ，与 $a$ 序列中随意一元素 $a_i$ ，有以下变换：

\begin{bmatrix} x&x+1&a_i \end{bmatrix} \to \begin{bmatrix} a_i-1&a_i&a_i \end{bmatrix} \to \begin{bmatrix} a_i-2&a_i-1&a_i \end{bmatrix} \to \begin{bmatrix} a_i-2&x&x+1 \end{bmatrix} \to \begin{bmatrix} x&x+1&a_i-2 \end{bmatrix}

同理可知， $a$ 序列中相差为 1 的数对可以将元素加 2。也就是说，相差为 1 的数对可以在不改变其他元素奇偶的情况下改变其他元素大小。

这个时候就可以开始分类讨论：

$a$ 序列中和 $b$ 序列中都有相差为 1 的数对：因为数对的奇偶显然也是对应的，所以直接比较序列奇数偶数个数是否一致即可。
$a$ 序列中有相差为 1 的数对， $b$ 中没有：显然不可能，因为数对相差唯一的相对性无法改变。
$a$ 序列中没有相差为 1 的数对：这时 $a$ 序列无法做任何操作，直接判断 $a$ 序列是否等于 $b$ 序列即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int T,n;
int a[N],b[N];

signed main(){
	cin>>T;
	while(T--){
		bool tag1=0,tag2=0,tag3=1;
		int cnt1=0,cnt2=0;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(i>1&&a[i]-a[i-1]==1) tag1=1;
			if(a[i]%2==1) cnt1++;
		}
		for(int i=1;i<=n;i++){
			cin>>b[i];
			if(i>1&&b[i]-b[i-1]==1) tag2=1;
			if(b[i]%2==1) cnt2++;
			if(b[i]!=a[i]) tag3=0;
		}
		if(tag1&&tag2){
			if(cnt1==cnt2) cout<<"yes\n";
			else cout<<"no\n";
		}
		else{
			if(tag3) cout<<"yes\n";
			else cout<<"no\n";
		}
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int T,n;
int a[N],b[N];

signed main(){
	cin>>T;
	while(T--){
		bool tag1=0,tag2=0,tag3=1;
		int cnt1=0,cnt2=0;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(i>1&&a[i]-a[i-1]==1) tag1=1;
			if(a[i]%2==1) cnt1++;
		}
		for(int i=1;i<=n;i++){
			cin>>b[i];
			if(i>1&&b[i]-b[i-1]==1) tag2=1;
			if(b[i]%2==1) cnt2++;
			if(b[i]!=a[i]) tag3=0;
		}
		if(tag1&&tag2){
			if(cnt1==cnt2) cout<<"yes\n";
			else cout<<"no\n";
		}
		else{
			if(tag3) cout<<"yes\n";
			else cout<<"no\n";
		}
	}
	return 0;
}

终局之战

\begin{aligned} \frac{1}{x} +\frac{1}{y}&=\frac{1}{n} \\ xn+yn&=xy \\ xy-n(x+y)&=0 \\ (x-n)(y-n)&=n^2 \\ \end{aligned}

设 $d$ 是 $n^2$ 的一个正因子，有：

不难发现， $x,y>n$ ，不然当 $x,y,n$ 都为正整数时原式不可能成立。

则有 $x=d+n,y=\frac{n^2}{d}+n$ 。

又 $(x,y)$ 是无序正整数对，所以如果枚举因数的话，所有的整数对都应该出现两次，除了 $x=y\ (d=n)$ 时会重复计算。

所以我们不妨先当作有序数对来写，然后再加上 $x=y\ (d=n)$ 时的贡献后除以 2 就是最终答案。

当 $(x,y)$ 是有序数对是，答案是：

\begin{aligned} Ans_{有序}&=\sum_{d|n^2} (d+n)(\frac{n^2}{d}+n) \\ &=\sum_{d|n^2}(2n^2+nd+\frac{n^3}{d}) \\ &=2n^2d(n)+n\sum_{d|n^2}d+n\sum_{d|n^2}\frac{n^2}{d} \\ &=2n^2d(n^2)+2\sigma (n^2) \end{aligned}

又因为 $(2n,2n)$ 的贡献为 $4n^2$ ，所以：

\begin{aligned} Ans&=\frac{Ans_{有序}+4n^2}{2} \\ &=n^2d(n^2)+\sigma (n^2)+2n^2 \end{aligned}

这个时候公式就推完了，这里我们需要对 $n^2$ 质因数分解，显然如果 $n=p_1^{a_1}·p_2^{a_2}·......·p_k^{a_k}$ ，那么 $n=p_1^{2a_1}·p_2^{2a_2}·......·p_k^{2a_k}$ ，然后根据题目下面的提示套公式即可。注意这里有取模意义下的除法，所以要计算逆元。

注： $d(x)$ 表示正整数 $x$ 的正因子个数， $\sigma(x)$ 表示正整数 $x$ 的正因子之和。

代码（这里大量取模运算可能会被 O2 优化掉，所以提交时不要开 O2 优化）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int T,n;

int mi(int x,int y){
	int ans=1;
	while(y){
		if(y%2) ans*=x,ans%=mod;
		y/=2,x=x*x%mod;
	}
	return ans;
}

int solve(int n){
	int d=1,sigma=1,x=n;
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			int cnt=0;
			while(x%i==0) x/=i,cnt++;
			d=d*(2*cnt+1)%mod,sigma=sigma*(mi(i,2*cnt+1)-1+mod)%mod*mi(i-1,mod-2)%mod;
		}
	}
	if(x>1) d=d*3%mod,sigma=sigma*(mi(x,3)-1+mod)%mod*mi(x-1,mod-2)%mod;
	return (n%mod*n%mod*d%mod+n%mod*sigma%mod+2*n%mod*n%mod)%mod;
}

signed main(){
	cin>>T;
	while(T--){
		cin>>n;
		cout<<solve(n)<<"\n";
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int T,n;

int mi(int x,int y){
	int ans=1;
	while(y){
		if(y%2) ans*=x,ans%=mod;
		y/=2,x=x*x%mod;
	}
	return ans;
}

int solve(int n){
	int d=1,sigma=1,x=n;
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			int cnt=0;
			while(x%i==0) x/=i,cnt++;
			d=d*(2*cnt+1)%mod,sigma=sigma*(mi(i,2*cnt+1)-1+mod)%mod*mi(i-1,mod-2)%mod;
		}
	}
	if(x>1) d=d*3%mod,sigma=sigma*(mi(x,3)-1+mod)%mod*mi(x-1,mod-2)%mod;
	return (n%mod*n%mod*d%mod+n%mod*sigma%mod+2*n%mod*n%mod)%mod;
}

signed main(){
	cin>>T;
	while(T--){
		cin>>n;
		cout<<solve(n)<<"\n";
	}
	return 0;
}