首页 > 其他 > 详细

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

时间:2020-10-25 19:57:00      阅读:61      评论:0      收藏:0      [点我收藏+]

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循环有个地方写错了导致样例过了其他测试点没过。

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

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!