「GDKOI2021普及组Day3」简要题解

T1:三角形相似

题目大意:给定两个三角形,判断这两个三角形是否相似

题解:

直接根据点的坐标求出三边长,然后全排列枚举一下边匹配的关系

注意精度

Code

#include<cmath>
#include<cstdio>
#include<cstring>
#define db long double
#define ll long long
#define mxdb 1e-9
using namespace std;
struct node
{
	db a,b,c;
}tri1,tri2;
int n,t;
ll x[5],y[5];
db k1,k2,k3;
ll sqr(ll x) {return x*x;}
db getdis(ll pos_x1,ll pos_y1,ll pos_x2,ll pos_y2) {return (double)(sqrt(sqr(pos_x1-pos_x2)+sqr(pos_y1-pos_y2)));}
bool issame(db x,db y) 
{
	if (fabs(x-y)<mxdb) return true;
	else return false;
}
int main()
{
	scanf("%d",&t);
	while (t--)
	{
		for (int i=1;i<=3;++i)
			scanf("%lld%lld",&x[i],&y[i]);
		tri1.a=getdis(x[1],y[1],x[2],y[2]);
		tri1.b=getdis(x[1],y[1],x[3],y[3]);
		tri1.c=getdis(x[2],y[2],x[3],y[3]);
		for (int i=1;i<=3;++i)
			scanf("%lld%lld",&x[i],&y[i]);
		tri2.a=getdis(x[1],y[1],x[2],y[2]);
		tri2.b=getdis(x[1],y[1],x[3],y[3]);
		tri2.c=getdis(x[2],y[2],x[3],y[3]);
		k1=tri1.a/tri2.a;k2=tri1.b/tri2.b;k3=tri1.c/tri2.c;
		if (issame(k1,k2)&&issame(k2,k3))
		{
			printf("YES\n");
			continue;
		}
		k2=tri1.b/tri2.c;k3=tri1.c/tri2.b;
		if (issame(k1,k2)&&issame(k2,k3))
		{
			printf("YES\n");
			continue;
		}
		k1=tri1.a/tri2.b;k2=tri1.b/tri2.a;k3=tri1.c/tri2.c;
		if (issame(k1,k2)&&issame(k2,k3))
		{
			printf("YES\n");
			continue;
		}
		k2=tri1.b/tri2.c;k3=tri1.c/tri2.a;
		if (issame(k1,k2)&&issame(k2,k3))
		{
			printf("YES\n");
			continue;
		}
		k1=tri1.a/tri2.c;k2=tri1.b/tri2.a;k3=tri1.c/tri2.b;
		if (issame(k1,k2)&&issame(k2,k3))
		{
			printf("YES\n");
			continue;
		}
		k2=tri1.b/tri2.b;k3=tri1.c/tri2.a;
		if (issame(k1,k2)&&issame(k2,k3))
		{
			printf("YES\n");
			continue;
		}
		printf("NO\n");
	}
	return 0;
}

T2:樱花再见

题目大意:有 n n n个学生, k k k个学科,每个人每科分数是0~100里的任意实数,依次给出小A(化名)的排名,问在给出 i i i科后小A可能的最优和最差排名( 1 ≤ i ≤ k 1\le i\le k 1≤i≤k)

题解:

首先对于最优的情况,我们可以认为所有考的比小A好的人都是100,小A是99,比小A差的都是0,那么只有当某个人人到目前为止全部100那么ta才可能排名比小A高,否则都会在小A的后面

那么我们就统计下到目前为止总共有多少个比小A考的差的(即考0分的) c n t cnt cnt,如果 c n t ≥ n − 1 cnt\ge n-1 cnt≥n−1,小A就会是第1,否则是 n − c n t n-cnt n−cnt

对于最差的情况也可以这么考虑,认为考的比小A好的拿了1分,小A及考的比ta差的拿了0分,那么只要某个人任意一科拿了分就可以比小A高

于是我们就统计有多少个考的比小A好的 c n t cnt cnt,如果 c n t ≥ n − 1 cnt\ge n-1 cnt≥n−1,那么小A就是最后一名,否则就是 c n t + 1 cnt+1 cnt+1名

Code

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
int k;
ll n,x1,x2,x;
int main()
{
	scanf("%lld%d",&n,&k);
	for (int i=1;i<=k;++i)
	{
		scanf("%lld",&x);
		x1+=x-1;
		x2+=n-x;
		printf("%lld %lld\n",max(n-x2,(long long)1),min(n,x1+1));
	}
	return 0;
}

T3:数论

题目大意:若 n n n的质因数分解为 n = ∏ p i e i n=\prod p_i^{e_i} n=∏piei​​定义 λ ( i ) = ( − 1 ) ∑ e i \lambda(i)=(-1)^{\sum e_i} λ(i)=(−1)∑ei​,求 ∑ k = 1 n ∑ i ∣ k ∑ j ∣ i λ ( i ) λ ( j ) \sum\limits_{k=1}^n\sum\limits_{i|k}\sum\limits_{j|i}\lambda(i)\lambda(j) k=1∑n​i∣k∑​j∣i∑​λ(i)λ(j)

题解:

推柿子:

∑ k = 1 n ∑ i ∣ k ∑ j ∣ i λ ( i ) λ ( j ) = ∑ i = 1 i 2 < n ⌊ n i 2 ⌋ \sum\limits_{k=1}^n\sum\limits_{i|k}\sum\limits_{j|i}\lambda(i)\lambda(j)=\sum\limits_{i=1}^{i^2<n}\left\lfloor\dfrac{n}{i^2}\right\rfloor k=1∑n​i∣k∑​j∣i∑​λ(i)λ(j)=i=1∑i2<n​⌊i2n​⌋

留坑填……

Code

#include<cstdio>
#define mod 998244353
#define ll long long
ll n,ans;
using namespace std;
int main()
{
	scanf("%lld",&n);
	for (ll i=1;i*i<=n;++i)
		ans=(ans+(n/(i*i)))%mod;
	printf("%lld\n",ans);
	return 0;
}

T4:好序列

题目大意:给定一个数字 n n n,每个位置可以填0~ n n n,求有多少种填法使得序列是好序列。关于好序列的定义:若记 l s u m k = ∑ i = 1 k A i , r s u m k = ∑ i = 1 k A n − i + 1 lsum_k=\sum\limits_{i=1}^kA_i,rsum_k=\sum\limits_{i=1}^kA_{n-i+1} lsumk​=i=1∑k​Ai​,rsumk​=i=1∑k​An−i+1​,则序列 A A A是好的,当且仅当 ∀ 1 ≤ k ≤ n , l s u m k ≥ r s u m k \forall1\le k\le n,lsum_k\ge rsum_k ∀1≤k≤n,lsumk​≥rsumk​

题解:

首先根据定义来看,如果 k > ⌊ n 2 ⌋ k>\lfloor\dfrac{n}{2}\rfloor k>⌊2n​⌋,那么 1 → k 1\rightarrow k 1→k和 n − k + 1 → n n-k+1\rightarrow n n−k+1→n就会有重叠的部分,减去重叠部分后 k k k又会小于 ⌊ n 2 ⌋ \lfloor\dfrac{n}{2}\rfloor ⌊2n​⌋,所以我们只用判断前 ⌊ n 2 ⌋ \lfloor\dfrac{n}{2}\rfloor ⌊2n​⌋部分就可以了

那么设个 f [ i ] [ j ] f[i][j] f[i][j]表示两端分别填了 i i i个数,差为 j j j的方案数,枚举一个旧差 k k k(那么 j − k j-k j−k就是第 i i i位能提供的贡献),简单思考可得 max ⁡ ( 0 , j − n ) ≤ k ≤ j + n \max(0,j-n)\le k\le j+n max(0,j−n)≤k≤j+n(因为这位最多能提供 n n n,最少提供 − n -n −n的贡献,又要保证在此之前是合法的,所以就要 0 0 0和 j − n j-n j−n取 max ⁡ \max max)

转移方程: f [ i ] [ j ] = ∑ k = max ⁡ ( 0 , j − n ) j + n f [ i − 1 ] [ k ] × ( n − ∣ j − k ∣ + 1 ) f[i][j]=\sum_{k=\max(0,j-n)}^{j+n}f[i-1][k]\times(n-|j-k|+1) f[i][j]=∑k=max(0,j−n)j+n​f[i−1][k]×(n−∣j−k∣+1)

注意 i < ⌊ n 2 ⌋ i<\lfloor\dfrac{n}{2}\rfloor i<⌊2n​⌋

最后 a n s = ∑ j = 0 ⌊ n 2 ⌋ × n f [ n ] [ j ] ans=\sum_{j=0}^{\lfloor\frac{n}{2}\rfloor\times n} f[n][j] ans=∑j=0⌊2n​⌋×n​f[n][j]

注意到如果 n n n是奇数,那么会忽略最中间那个数,而最中间那个数的取值随意,所以在 n n n是奇数的时候 a n s ans ans要乘上 n + 1 n+1 n+1

Code

#include<cmath>
#include<cstdio>
#include<algorithm>
#define mod 998244353
#define N 105
#define ll long long
using namespace std;
ll n,ans,f[N][N*N];
int main()
{
	scanf("%d",&n);
	f[0][0]=1;
	for (ll i=1;i<=(n>>1);++i)
	{
		for (ll j=0;j<=i*n;++j)
			for (ll k=max((long long)0,j-n);k<=j+n;++k)
				f[i][j]=(f[i][j]+f[i-1][k]*(n+1-abs(j-k))%mod)%mod;
	}
	for (int j=0;j<=(n>>1)*n;++j)
		ans=(ans+f[n>>1][j])%mod;
	if (n%2==1) ans=ans*(n+1)%mod;
	printf("%lld\n",ans);
	return 0;
}
上一篇:Day3


下一篇:ECS 7天实践训练营-day3-使用PolarDB和ECS搭建门户网站