ACM 实验室2020.10.17天梯赛练习*3

时间：2020-10-25 19:57:00 收藏：0 阅读：62

7-1 判断素数 (10分)

没判断1，6分

#include<bits/stdc++.h>
#define ll long long
#define speed_up ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll f(ll n)
{
    if(n==3||n==2)return 1;
    if(n%2==0)return 0;
    if(n%6!=1&&n%6!=5)return 0;
    for(int i=5;i<sqrt(n)+1;i+=6)
    {
        if(n%i==0||n%(i+2)==0)return 0;
    }
    return 1;
}
int main()
{
    speed_up;
    ll n,t;
    cin>>n;
    while(n--)
    {
        cin>>t;
        if(t==1)cout<<"No"<<endl;//1不是素数
        else if(f(t)==1)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}

求素数另外几种方法：

(1)

int n,c=0;

cin>>n;
for(int i=2;i<=n;i++)
    {
        int f=0;
        for(int j=1;j<=n;j++)
        {
            if(i%j==0)//不是素数
                f++;
        }
        if(f==2)c++;
    }
    cout<<c<<endl;
}

(2)

int n,c=0;
cin>>n;
for(int i=2;i<=n;i++)
    {
        int f=0;
        for(int j=1;j<=sqrt(i);j++)
        {
            if(i%j==0)//不是素数
            {
                f++;
                if(f==2)break;
            }
        }
        if(f==1)c++;
    }
    cout<<c<<endl;
(3)
#include<bits/stdc++.h>
using namespace std;
#define speed_up ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
vector<int>sieve(int n)
{
    vector<int>a;
    int *f=new int[n+1];
    for(int i=2;i<n;i++)f[i]=1;
    for(int i=2;i*i<=n;i++)
    {
        if(f[i])
        {
            for(int j=i+i;j<=n;j+=i)f[j]=0;
        }
    }
    for(int i=2;i<=n;i++)
    {
        if(f[i])a.push_back(i);
    }
    return a;
}
int main(int argc,char const *argv[])
{
    speed_up;
    int n;
    cin>>n;
    vector<int>ans=sieve(n);
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i];
        if(i<ans.size()-1)cout<<" ";
    }
    cout<<endl;
    return 0;
}

(4)

#define maxn 10000000
bool vis[maxn];
int prime[maxn],x;

void oulasai(int n) //欧拉筛
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) prime[x++]=i;
        for(int j=0;j<x;j++)
        {
            if(i*prime[j]>n) break;
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

7-2 寻找250 (10分)

刚开始输入格式不对

    int n,i=0;
    while(1)
    {
        cin>>n;
        if(n==250)break;
        i++;
    }
    cout<<i+1<<endl;

7-5 敲笨钟 (20分)

这个题的代码有个地方数组可能会越界，结果有个样例运行时错误，18分

#include<bits/stdc++.h>
#define ll long long
#include<string>
#define speed_up ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int main()
{
    speed_up;
    int t;
    cin>>t;
    getchar();
    for(int i=0;i<t;i++)
    {
        string s;
        getline(cin,s);
        int f=0;
        for(int j=0;j<s.size();j++)
        {
            if(s[j]==‘,‘||s[j]==‘.‘)
            {
                //注意判断j是否大于3，否则可能越界。因为题目只说了下半句诗至少有 3 个字，没说逗号前也至少有3个
                if(j>=3&&(s.substr(j-3,3)=="ong"))continue;
                else f=1;//不符合两个都为ong
            }

        }
        if(f!=1)
        {
            int k=0,j;
            for(j=s.size()-1;;j--)
            {
                if(s[j]==‘ ‘||s[j]==‘,‘)k++;//k表示遇到第几个空格或逗号
                if(k==3)
                {
                    break;
                }
            }
            for(int kk=0;kk<=j;kk++)//输出kk位置前的所有字符
            {
                cout<<s[kk];
            }
            cout<<"qiao ben zhong."<<endl;
        }
        else cout<<"Skipped"<<endl;
    }
}

7-7 A-B (20分)

没看清楚题，第二个字符串也可能带空格。

7-9 小字辈 (25分)

#include<bits/stdc++.h>
#define ll long long
#include<string>
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<string>
#include<map>
#include<sstream>
#include<cstring>
#include<vector>
#include<iomanip>
#include<queue>
#include<set>
#define speed_up ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
/*
编号   辈分
-1      1
5 5 5   2
6 6 4   3
2 7     4

n   v[n]   层数(deep)
2   1       4
6   2 7     3
5   3 4 6   2
-1 5       1
4   8       3
7   9       4
*/
vector<int>v[100005],ans;
vector<int>::iterator it;
int maxx;
void dfs(int n,int deep)
{
    for(int i=0; i<v[n].size(); i++)
        {
            //cout<<n<<"*"<<deep<<endl;
            dfs(v[n][i],deep+1);
        }
    if(deep>maxx)//ans里只存最深的那一层的编号下标i
    {
        maxx=deep;//deep是层数，maxx记录最大层数
        //cout<<"&"<<maxx<<endl;
        ans.clear();
        ans.push_back(n);
    }
    else if(maxx==deep)
        ans.push_back(n);
}
int main()
{
    speed_up;
    int n,t,pos;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>t;
        if(t==-1)
        {
            pos=i;
            continue;
        }
        v[t].push_back(i);
    }
    dfs(pos,1);//从编号-1的位置开始搜
    sort(ans.begin(),ans.end());
    cout<<maxx<<endl;
    cout<<*ans.begin();
    for(it=ans.begin()+1; it!=ans.end(); it++)
    {
        cout<<‘ ‘<<*it;
    }
    cout<<endl;
}

7-11 互评成绩 (25分)

输出for循环有个地方写错了导致样例过了其他测试点没过。

原文：https://www.cnblogs.com/SyrupWRLD999/p/13852117.html