讨论详情 - HNUAHE-OJ

25级新生周赛(四)
25级新生周赛题解(四)
Hhh LV 6 MOD @ 2025-11-23 10:26:44

A.来签到（剑染黎明）

//c
#include<stdio.h>
int main() {
	printf("我签上了\n"); 
	return 0;
}

B.数论基石（剑染黎明）

对每个数暴力枚举即可，枚举所有小于它的正整数（除 $1$ 外），计算能否整除，若有能整除的，则原数不是素数；若无自然是素数。

//c
#include<stdio.h>
int main() {
	bool f=1;
	int ans=0; 
    for(int i=2;i<=30000000;i++){
    	f=1;
    	for(int j=2;j<i;j++){//从小到大枚举，显然越小是因子的概率越大。
    		if(i%j==0){
    			f=0;
    			break;//一旦判断不是素数，直接退出，不必枚举完全。
			}
		}
		if(f){
		printf("%d ",i);
		ans++;	
		}
		if(ans==2025)
		break;
	} printf("\n");
    return 0;
}

下面介绍一种较高效的筛法。
我们知道一个数不是素数，那么他必然可以由比他小的数相乘得来。
比他小的数也必然如此，最后递推发现所有合数都是由素数相乘得来。
我们可以从小到大，将每一个素数的倍数标记为合数，轮到某个数，若它还未被标记，则为素数。

//c++
#include<bits/stdc++.h>
using namespace std;
int main() {
	int ans=0;
	vector<int>a(100000,1);//数组，先全部标记为1素数：
	a[0]=0;a[1]=0;//0,1不是素数;
    for(int i=2;i<100000;i++){
    	if(a[i]){
    		ans++;
    		cout<<i<<" ";//输出素数;
    		for(int j=i*2;j<100000;j+=i){//枚举素数的倍数，不是素数;
    		a[j]=0;
    	    }
		}
		if(ans>=2025)break;
	}cout<<endl;
    return 0;
}

还有更高效的线性筛，感兴趣，可自行了解。

C.数论基石2.0（剑染黎明）

不会找素数请看数论基石1.0
与数论基石1.0不同的是，你需要将素数标记在数组里。
进行分析，查询范围是 $10^4$ ,次数是 $10^6$ 。如果每次查询你都从 $l$ 到 $r$ 一个个查看是不是素数，则极限情况时间复杂度超过 $10^9$ ,所以我们需要用前缀和。
关于前缀和，可看《新生周赛题解（三）》的F题和《前缀和与二分查找思想》，群内文件或OJ讨论中有。

//c
//c
#include<stdio.h>
int a[10010];
int b[10010];
void Prime(){//素数判断函数；
	bool f=1;
	int ans=0; 
    for(int i=2;i<=10010;i++){//别求超了，这种求素数的方法时间复杂度挺大！！！
    	f=1;
    	for(int j=2;j<i;j++){//从小到大枚举，显然越小是因子的概率越大。
    		if(i%j==0){
    			f=0;
    			break;//一旦判断不是素数，直接退出，不必枚举完全。
			}
		}
		if(f)a[i]=1;			
	}
}
int main(){
	int n,l,r;
	scanf("%d",&n);
	Prime();
	for(int i=1;i<10010;i++){//求前缀和;
		b[i]=a[i]+b[i-1];
	}
	for(int i=0;i<n;i++){
		scanf("%d%d",&l,&r);
		printf("%d\n",b[r]-b[l-1]);
	} 
	return 0;
}

D.愤怒的 Om Nom（小b)

思路：当你看到两个点，不由自主的就会想起来 y=k*x+b 对不对？k=(y1-y2)/(x1-x2),题目里x1-x2!=0,我们剩下要判断的是所给的点在不在这个 “线段” 上，下面看代码

#include <stdio.h>
int main()
{
   double a1,b1,a2,b2;
   int n;
   scanf("%lf %lf %lf %lf",&a1,&b1,&a2,&b2);
   scanf("%d",&n);
  double k=(b1-b2)/(a1-a2);
  double b=b1-a1*k;
  double U=b1>b2?b1:b2,D=b1<b2?b1:b2;
  double R=a1>a2?a1:a2,L=a1<a2?a1:a2;//判断是否超出线段，用一个长方形，U，D,R,L,就是四个边界
  int ans=0;
  for(int i=1;i<=n;i++)
  {
   double x,y;scanf("%lf%lf",&x,&y);
   if(y<=U&&y>=D&&x>=L&&x<=R)
   if(y==k*x+b)ans++;
  }
  printf("%d",ans);
  return 0;
}

E.对弈(小b)

思路：小李能排列数组，但是轮到宁次的时候他会交换相邻两个元素的值，我们先对数组进行从小到大的排序，然后想怎么才能保证交换后，数组还是按非递减排列的呢？很容易的想到如果宁次交换的前后两个数组的值相同，就能解决了，思路明确下面是代码

#include<stdio.h>
int main() {
    int t;
    scanf("%d",&t);
    while(t--)
  {
    int n;
        scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
    for(int i=0;i<n;i++)

    {
      for(int j=i+1;j<n;j++)
      {
        if(a[j]<a[i])
        {
          int temp=a[j];a[j]=a[i];a[i]=temp;
        }
      }
    }//冒泡排序
        //sort(a,a+n);sort排序c++里的，推荐去学
    int falg=1;//做标记
    for(int i=1;i<n-1;i+=2)//i<n-1 是进行n-1轮
    {
      if(a[i]!=a[i+1])
      {
        printf("NO\n");falg=0;break;
      }
    }
    if(falg==1)
    printf("YES\n");
    }
    return 0;
}

F.棋盘2.0（剑染黎明）

我们先让 $m$ 为边长的限制（若 $n<m$ 交换 $n,m$ 的值）。
从小到大枚举正方形边长 $i$ ，发现 $n$ 边可划分出边长为 $i$ 的正方形数量最多 $(n-i+1)$ ；
同理 $m$ 边可划分出边长为 $i$ 的正方形数量最多 $(m-i+1)$ ；
所以边长为 $i$ 的正方形数量为 $(n-i+1) \times (m-i+1)$ 。
注意最后的结果 $ans$ 可能超过 $10^9$ ,超过了 $int$ 的范围，需要开 $long long$ 。

//C
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int main() {
	int n,m;
	long long ans=0;
	scanf("%d%d",&n,&m);
	if(n<m){
		swap(&n,&m);
	}
	for(int i=1;i<=m;i++){
		ans+=(n-i+1)*(m-i+1);
	}
	printf("%lld\n",ans);
}

G.我的天啊，是诺谛卡大人（涵涵）

思路：对于每组用例，我们在用数组存储最大生命值并计入的同时，还需要再定义一组相同的数组去记录最大生命值，用来矫正每次恢复血量后的生命值，而先前的一组用来记录实时的当前生命值。其次根据技能效果可以将他们分为三种，第一种是通过消耗生命值，最后结算薪血，第二种是直接增加薪血点数，第三种是恢复所有人的生命值。按照第二条的提示要求，每次优先计算消耗的生命值，并计入消耗生命值总和，用来在最后结算。

// 1代表诺蒂卡 2代表玛丽安娜 3代表塞梅尔维斯 4代表野树莓
#include <stdio.h>
typedef long long ll;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int HP[5];
        int HP_[5];
        int HPsum=0;
        int ans=0;
        for(int i=1;i<=4;i++){
            scanf("%d",&HP[i]);
            HP_[i]=HP[i];
        }
        for(int i=1;i<=4;i++){
            int x;
            scanf("%d",&x);
            //消耗
            if(x==1||x==3){
                for(int j=1;j<=4;j++){
                    int hp=HP[j]*0.2;
                    HPsum+=hp;
                    HP[j]-=hp;
                }
            }
            //直加
            else if(x==2) ans++;
            //恢复
            else{
                for(int j=1;j<=4;j++) HP[j]=HP_[j];
            }
        }
        ans=ans+HPsum/3000;
        printf("%d\n",ans);
    }
    return 0;
}

H.DNA的转录（剑染黎明）

以下是DNA与mRNA配对的示意图，体现5'到3'端的方向对应关系：
DNA模板链：3' — T — A — C — G — 5'
mRNA链：5' — A — U — G — C — 3'

由于题目中给的两条链都是由5'到3'，所以需要先反转mRNA。
求出与反转后的mRNA互补配对的DNA片段。
暴力遍历DNA模板链的每一个碱基，以他们为开头，尝试匹配。

//c
#include<stdio.h>
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	char s1[n];
	char s2[m];
	scanf("%s",s1);
	scanf("%s",s2);
	char s3[m];
	for(int i=0;i<m;i++){
		if(s2[i]=='U')s2[i]='A';//转化为互补配对的DNA碱基。 
		else if(s2[i]=='A')s2[i]='T';
		else if(s2[i]=='C')s2[i]='G';
		else if(s2[i]=='G')s2[i]='C';
		s3[m-1-i]=s2[i];//反转s2（注意顺序，不要把没转化的碱基反转了）;
	}
	for(int i=0;i<n-m+1;i++){
		bool f=1;
		for(int j=i;j<i+m;j++){//以i为起点依次比较后面m个字符是否相同;
			if(s3[j-i]==s1[j]){
				continue;
			}
			else f=0;
		}
		if(f){
			printf("YES");
			return 0;
		}
	}
	printf("NO");
	return 0;
}

下面提供c++版本，c++有字符串反转和截取函数，比c语言方便很多。

//c++
#include<bits/stdc++.h>//若想使用下列函数，请用此万能头文件，或补充对应头文件;
using namespace std;
int main() {
	int n,m;
	cin>>n>>m;//cin就是scanf输入;
	string s1,s2;
	cin>>s1>>s2;//输入字符串;
	for(int i=0;i<m;i++){
		if(s2[i]=='U')s2[i]='A';
		else if(s2[i]=='A')s2[i]='T';
		else if(s2[i]=='C')s2[i]='G';
		else if(s2[i]=='G')s2[i]='C';
	} 
	reverse(s2.begin(),s2.end());//反转s2;
	for(int i=0;i<n-m+1;i++){
		string s3=s1.substr(i,m);//s3为截取s1的字符串（从s1的下标i开始，长度为m);
		if(s3==s2){//c++的stirng可以直接用==判同;
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
	return 0;
}

I.37的钻研(涵涵)

思路：按照题目要求分为两次判断，第一次是判断三边是否能组成三角形，成立条件为两边之和大于第三边和两边之差的绝对值小于第三边，注意两边之差时要带绝对值。第二次是按照优先级顺序根据边之间的关系逐个判断三角形的类型。三角形的面积直接套入公式即可。在判断直角三角形时，建议提前计算好各个边的平方值。

#include <stdio.h>
#include <math.h>
typedef long long ll;
int a,b,c;
int main()
{
    scanf("%d%d%d",&a,&b,&c);
    if(a+b>c&&abs(a-b)<c){
        int aa=a*a,bb=b*b,cc=c*c;
        if(a==b&&a==c){
            printf("Perfect equilateral crystal!!!\n");
        }
        else if(a==b||b==c||a==c){
            if(aa+bb==cc||aa+cc==bb||bb+cc==aa){
                printf("Isosceles right-angle crystal!!\n");
            }
            else{
                printf("Isosceles crystal!\n");
            }
        }
        else if(aa+bb==cc||aa+cc==bb||bb+cc==aa){
            printf("Right-angle crystal!\n");
        }
        else{
            printf("Common triangular crystal.\n");
        }
        double p=(a+b+c)/2.0;
        double n=sqrt(p*(p-a)*(p-b)*(p-c));
        printf("%.2f\n",n);
    }
    else printf("It cannot form an energy triangle.\n");
    return 0;
}

目前还没有评论...

25级新生周赛题解(四)

A.来签到（剑染黎明）

B.数论基石（剑染黎明）

C.数论基石2.0（剑染黎明）

D.愤怒的 Om Nom（小b)

E.对弈(小b)

F.棋盘2.0（剑染黎明）

G.我的天啊，是诺谛卡大人（涵涵）

H.DNA的转录（剑染黎明）

I.37的钻研(涵涵)

0 条评论

学校链接

平台

系统设置

25级新生周赛题解(四)

A.来签到（剑染黎明）

B.数论基石（剑染黎明）

C.数论基石2.0（剑染黎明）

D.愤怒的 Om Nom（小b)

E.对弈(小b)

F.棋盘2.0（剑染黎明）

G.我的天啊，是诺谛卡大人（涵涵）

H.DNA的转录（剑染黎明）

I.37的钻研(涵涵)

0 条评论

学校链接

平台

系统设置

还没有账户？

登录