题解 - 南昌五中初一第二次阶段测试 & 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; }`