题解 - 南昌五中初一第二次阶段测试 & ooliver 的复仇
题解 - 南昌五中初一第二次阶段测试 & ooliver 的复仇
说在前面
这次题目确实有点难，但是大家要习惯信奥比赛中遇到难题时的压力，所以没有必要抱怨题目的难度，毕竟大家都不会……
信奥分组
不难发现，偶数+偶数=偶数，所以只要 nn 是偶数就可以了？ 因为每组人数既要大于 0，也要为偶数，所以每组最少 2 人，也就是说总人数最少要 4 个人。 那么 nn 要是大于或等于 4 的偶数。
代码：
#include
using namespace std;
int n;
int main(){
cin>>n;
if(n%2==0&&n>=4) cout
`#include
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 类型计算 ab\frac{a}{b}， 这样会出现一个问题，就是 double 类型最多存储到小数点后 15-16 位，所以如果两个小数知道小数点后 16 位才有不一样的地方，用 double 类型就比较不出来他们的大小。
那怎么办呢？我们知道有个东西叫做交叉相乘，在 0">a,b,c,d>0a,b,c,d>0 的情况下， \frac{c}{d} ">ab>cd\frac{a}{b} > \frac{c}{d} 等价于 bc">ad>bcad > bc，同理可知，比较 ab\frac{a}{b} 与 cd\frac{c}{d} 的大小等价于比较 adad 与 bc bc 的大小，这样就转化为了正整数的大小比较，不会出现精度问题。
代码：
#include
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
`#include
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
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
`#include
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;
}`
求圆周率
观察到分母都是奇数，第 ii 个奇数为 2i−12i-1，且当 ii 是奇数时它前面的符号是加号，当 ii 是偶数时它前面的符号是减号，计算出等式右边的值后乘 4 就是 π\pi 了，记得保留 4 位小数。
代码：
#include
using namespace std;
int n;
double pai=0;
signed main(){
cin>>n;
for(int i=1;i
`#include
using namespace std;
int n;
double pai=0;
signed main(){
cin>>n;
for(int i=1;i
if(i%2==1) pai+=1.0/(2*i-1);
else pai-=1.0/(2*i-1);
}
coutsetprecision(6)4;
return 0;
}`
系数展开
可以先分析一下题目：
(2x+3)⋅(x−1)=2x2+x−3(2x + 3) \cdot(x - 1) = 2x^2 + x - 3
这里展开后的所有系数与常数项之和显然是 2+1−3=02+1-3=0。但是对于 (x+a)n(x+a)^n 这样的式子就不太好求展开式，那怎么办呢？
考虑转化问题，怎么把 2x2+x−32x^2 + x - 3 转化为 2+1−32+1-3？不难发现，当我们令 x=1x=1 时，2x2+x−32x^2 + x - 3 的值就正好等于 2+1−32+1-3。
所以我们直接令 x=1x=1，则问题就转化成了求 (1+a)n(1+a)^n，直接使用 pow 函数即可。
代码：
#include
using namespace std;
int main(){
long long a,n;
cin>>a>>n;
cout
`#include
using namespace std;
int main(){
long long a,n;
cin>>a>>n;
coutlong long)pow(a+1,n);
return 0;
}`
多维空间
这是一道阅读理解题，只要你读懂了，这题就变得很简单。
作为三维生物，n≤3n\le 3 时我们是可以想象的。
-
n=1n=1 时，此时两个 nn 维体就变成了两个线段，题目也简化成了已知两个线段的坐标，求两个线段重合部分的长度。这个时候我们可以分类讨论两个线段左右端点之间的关系，但这里给出一个更简单的理解方法： 我们可以考虑分别求出重合部分的左右端点，显然左端点应该是两个线段左端点的最大值，右端点时两个线段右端点的最小值，搞不明白的可以多画几个图试一试。 当然，可能会出现左端点大于右端点的情况，这表示两个端点没有重合部分。
-
n=2n=2 时，问题变成了求两个矩形，也就是长方形的重合部分的面积。面积等于长乘高，所以我们可以借用一维求线段重合部分长度的代码，分别求出两个长方形长和宽的重合线段的长度，再相乘即可。
-
n=3n=3 时，讨论重合长方体的长、宽、高即可。
所以根据以上的规律，我们只需要找到两个 nn 维体在每一位的重合线段的长度并相乘即可。
记得考虑没有重合部分的情况，也就是在某一维两线段无重合，直接记重合长度为 0，那么乘起来就是 0 了。
代码：
#include
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>a[i];
for(int i=1;i>b[i];
for(int i=1;i>c[i];
for(int i=1;i>d[i];
for(int i=1;i
`#include
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>a[i];
for(int i=1;i>b[i];
for(int i=1;i>c[i];
for(int i=1;i>d[i];
for(int i=1;if(a[i],b[i],c[i],d[i])%mod;
cout
return 0;
}
`
勾八题目
首先，对于数字串中出现的 1，2，4，8 一定要修改，因为他们分别是 2 的 0 到 3 次方幂。
这个时候如果我们枚举所有小于 10(106)10^{(10^6)} 的 2k(k≥0)2^k(k\ge 0)，会惊奇地发现只有神奇的 **65536 **不包含 1，2，4，8 这些数字。
所以我们修改所有的 1，2，4，8 后再特殊判断一下是否出现了 65536 即可。
注意还有一种特殊情况，就是 655365536。这里虽然出现了两个 65536，但是只需要删除中间的 6 即可。
代码：
#include
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
`#include
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;ia.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;ia.size();i++){
if(a[i]=='1'||a[i]=='2'||a[i]=='4'||a[i]=='8')
ans++;
}
cout'\n';
}
return 0;
}`
序列变换
考虑一个相差为 1 的数对对整个 aa 序列的贡献：
设有 xx，x+1x+1，与 aa 序列中随意一元素 aia_i，有以下变换：
[xx+1ai]→[ai−1aiai]→[ai−2ai−1ai]→[ai−2xx+1]→[xx+1ai−2]\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}
同理可知，aa 序列中相差为 1 的数对可以将元素加 2。也就是说，相差为 1 的数对可以在不改变其他元素奇偶的情况下改变其他元素大小。
这个时候就可以开始分类讨论：
-
aa 序列中和 bb 序列中都有相差为 1 的数对：因为数对的奇偶显然也是对应的，所以直接比较序列奇数偶数个数是否一致即可。
-
aa 序列中有相差为 1 的数对，bb 中没有：显然不可能，因为数对相差唯一的相对性无法改变。
-
aa 序列中没有相差为 1 的数对：这时 aa 序列无法做任何操作，直接判断 aa 序列是否等于 bb 序列即可。
代码：
#include
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>a[i];
if(i>1&&a[i]-a[i-1]==1) tag1=1;
if(a[i]%2==1) cnt1++;
}
for(int i=1;i>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
`#include
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
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
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;
}`
终局之战
1x+1y=1nxn+yn=xyxy−n(x+y)=0(x−n)(y−n)=n2\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}
设 dd 是 n2n^2 的一个正因子，有：
不难发现，n">x,y>nx,y>n，不然当 x,y,nx,y,n 都为正整数时原式不可能成立。
则有 x=d+n,y=n2d+nx=d+n,y=\frac{n^2}{d}+n。
又 (x,y)(x,y) 是无序正整数对，所以如果枚举因数的话，所有的整数对都应该出现两次，除了 x=y (d=n)x=y\ (d=n) 时会重复计算。
所以我们不妨先当作有序数对来写，然后再加上 x=y (d=n)x=y\ (d=n) 时的贡献后除以 2 就是最终答案。
当 (x,y)(x,y) 是有序数对是，答案是：
Ans有序=∑d|n2(d+n)(n2d+n)=∑d|n2(2n2+nd+n3d)=2n2d(n)+n∑d|n2d+n∑d|n2n2d=2n2d(n2)+2σ(n2)\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)(2n,2n) 的贡献为 4n24n^2，所以：
Ans=Ans有序+4n22=n2d(n2)+σ(n2)+2n2\begin{aligned} Ans&=\frac{Ans_{有序}+4n^2}{2} \ &=n^2d(n^2)+\sigma (n^2)+2n^2 \end{aligned}
这个时候公式就推完了，这里我们需要对 n2n^2 质因数分解，显然如果 n=p1a1·p2a2·......·pkakn=p_1^{a_1}·p_2^{a_2}·......·p_k^{a_k}，那么 n2=p12a1·p22a2·......·pk2akn^2=p_1^{2a_1}·p_2^{2a_2}·......·p_k^{2a_k}，然后根据题目下面的提示套公式即可。注意这里有取模意义下的除法，所以要计算逆元。
注：d(x)d(x) 表示正整数 xx 的正因子个数，σ(x)\sigma(x) 表示正整数 xx 的正因子之和。
代码（这里大量取模运算可能会被 O2 优化掉，所以提交时不要开 O2 优化）：
#include
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*i1) 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
`#include
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
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;
coutsolve(n)"\n";
}
return 0;
}`