今天早了一点起来，初三的大奆都来做比赛了，
自然，自测的有许多 AK
虽然今天的题比昨天简单，但还是脑子还是十分迟钝，以至于贪心都想不出
真为明天的提高组而担忧
T1
斜率被卡 90 ，直接用勾股定理判断边的放大比例是否相等，注意可以不开方
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-7;
typedef long long LL;
int T;
LL z1[5],x[10],y[10],z2[5],gg;
inline LL Dis(int p,int q) {
return (x[p]-x[q])*(x[p]-x[q])+(y[p]-y[q])*(y[p]-y[q]);
}
inline LL Gcd(LL p,LL q) {
return q?Gcd(q,p%q):p;
}
inline bool Chk() {
if(z1[1]!=z1[2]||z2[1]!=z2[2])return false;
if(z1[1]!=z1[3]||z2[1]!=z2[3])return false;
if(z1[2]!=z1[3]||z2[2]!=z2[3])return false;
return true;
}
int main() {
freopen("triangle.in","r",stdin);
freopen("triangle.out","w",stdout);
scanf("%d",&T);
while(T--) {
for(int i=1;i<7;i++)scanf("%lld%lld",&x[i],&y[i]);
z1[1]=Dis(1,2),z1[2]=Dis(1,3),z1[3]=Dis(2,3);
z2[1]=Dis(4,5),z2[2]=Dis(4,6),z2[3]=Dis(5,6);
sort(z1+1,z1+4),sort(z2+1,z2+4);
gg=Gcd(z1[1],z2[1]),z1[1]/=gg,z2[1]/=gg;
gg=Gcd(z1[2],z2[2]),z1[2]/=gg,z2[2]/=gg;
gg=Gcd(z1[3],z2[3]),z1[3]/=gg,z2[3]/=gg;
if(Chk())puts("YES");
else puts("NO");
}
}
T2
贪心，由于比 x 排名高的只有(sum_{j=1}^i r_j-1)个，考虑用贪心
- 最优，比 x 高的都是 100 ，比 x 低的都是 0 ， x 是 99.99999 ，即无限接近 100
只要有一个科排名低于 x 就比 x 分数低
若 (sumle (n-1)(i-1)) 排名为 1 ，否则为 (sum+1-(n-1)(i-1)) - 最坏，比 x 高的都是 100 ，比 x 低的都是 0 ， x 是 0.000001 ，即无限接近 0
只要有一个科排名高于 x 就比 x 分数高
若 (sumge n-1) 排名为 n ，否则为 (sum+1)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int m;
LL n,sm;
int main() {
scanf("%lld%d",&n,&m);
for(int i=1,x;i<=m;i++) {
scanf("%d",&x);
sm+=1LL*x-1LL;
if(sm<=1LL*(n-1)*(i-1))printf("1 ");
else printf("%lld ",sm-1LL*(n-1)*(i-1)+1);
if(sm>=n-1)printf("%lld
",n);
else printf("%lld
",sm+1);
}
}
T3
设 (sum(x)=sum_{i|x}lambda(i),n=Pi p_i^{e_i}) ，若 (e_k) 有一个是奇数，则(sum(x))可以抵消
否则，就是完全平方数，直接算出其个数还有其倍数的个数累加即可
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=998244353;
LL n,ans;
int main() {
// freopen("number.in","r",stdin);
// freopen("number.out","w",stdout);
scanf("%lld",&n);
for(LL i=1;i<=sqrt(n);i++)
ans+=n/(i*i),ans>=mod?ans-=mod:1;
printf("%lld",ans);
}
T4
设 F[i][j] 为左右都到 i 的前后差为 j 的方案，发现只用枚举 (lfloor frac{n}{2}
floor) 就行了
(F_{0,1}=1,iin [1,lfloor frac{n}{2}
floor],jin [1,n*n] F_{i,j}=sum_{k=max(j-n,0)}^{j+n} F_{i-1,k}*(n+1-|j-k|))
最后答案是 (sum_{j=1}^{n*n} F_{lfloor frac{n}{2}
floor,j})
若 n 是奇数，答案要乘 n+1 ，因为 (lfloor frac{n+1}{2}
floor) 可以放 0~n
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=998244353;
int n,m;
LL ans,f[105][20005];
int main() {
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
scanf("%d",&n);
m=n*n+1,f[0][1]=1;
for(int i=1;i<=(n>>1);i++)
for(int j=1;j<=m;j++)
for(int k=max(j-n,0);k<=j+n;k++)
f[i][j]+=f[i-1][k]*(n+1-abs(j-k)),f[i][j]%=mod;
for(int i=1;i<=m;i++)ans+=f[n>>1][i],ans%=mod;
if(n&1)ans=ans*(n+1)%mod;
printf("%lld",ans);
}
End
GDKOI 都是思维题，本蒟蒻的思维还是要多加磨炼