noip第17课作业

时间:2022-09-25 21:57:27

1.  召见骑士

【问题描述】

某王国有5位骑士,每位骑士都有自己的编号,且这个王国的编号都为奇数,分别为1,3,5,7,9,在国王召见他们之前他们都必须经过只能从一边进出的长廊,长廊的宽度只能坐一个人。2018年1月1日这天,所有骑士依照编号从小到大的次序提前在长廊的入口等待,且只有当前面的人进入长廊后,后面的人才能进入长廊。国王想要召见一些骑士,把他们的编号写在纸上,让侍卫去宣传召见,问国王写的召见编号是否合理?

【输入格式】

输入一个编号序列。

【输出格式】

如果合理,输出“YES”,如果不合理,输出“NO”。

【输入样例】

3 1 9 7 5

【输出样例】

YES

【输入样例】

5 1 3 7 9

【输出样例】

NO

#include <iostream>
using namespace std;
const int N = 1010;
int stack[N],a[N];
int top,n;
int main() {
    for (int i = 1; i <= 5; ++ i) {
        cin >> a[i];
    }
    top = 0;
    for (int i = 1,cur = 1; i <= 5; i++) {
        while (cur <= a[i]) {
            stack[++top] = cur;
            cur = cur+2; 
        }
        if (stack[top] == a[i]) {
            --top;
        } else {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

2.  出栈顺序

【问题描述】

给定一个由n个元素构成的序列,你需要将其中的元素按顺序压入一个大小为c的栈并弹出。元素按它们的出栈顺序进行排列,会得到一个新的序列。我们知道,这样的序列会有很多种,请输出所有新序列中第一个元素最小的序列(若第一个元素最小的序列有多个,则令第二个尽可能小;若仍有多个,则令第三个最小,以此类推)。

【输入格式】

第一行,两个数n,c;

第二行n个数,为序列中n个元素的值。

【输出格式】

输出n个数,为满足要求的序列。

【样例输入】  

6 3

5 2 3 8 7 4

【样例输出】

2 3 5 4 7 8

#include<iostream>
#include <climits>
using namespace std;
int n,c,flag,m;
int stack[10005],top;
int num[10005];
int main() {
    int i,j;
    cin >> n>> c;
    for(i=1; i<=n; i++)
        cin >> num[i];
    //6 3
    //5 2 3 8 7 4 
    while(m<n) {  // 变量m表示输出的数的个数
        if(flag<n) {   //flag表示栈内数字的个数 
            int minn=INT_MAX,q;
            //根据栈的空余位置,找出数组的前几项(例如开始栈为空,空余3个位置那么我们就看数字前三位的最小值) 
            for(i=flag+1; i<=flag+c-top && i<=n; i++) {
                if(num[i]<minn) {
                    minn=num[i];
                    q=i;
                }
            }
            //如果栈为空,我们直接把q项数据入栈 
            if(!top) {
                for(i=flag+1; i<q; i++) {
                    stack[++top]=num[i];
                }
                flag = q;
                cout << num[flag]<<" ";  //输出栈顶的最小值 
                m++;
            } else {  //如果栈不为空 
                //如果要入栈的数字比栈顶元素大,输出栈顶元素
                if(stack[top]<num[q]) {
                    cout << stack[top--]<<" ";
                    m++;
                } else {   //如果要入栈数字比栈顶元素小,把该数字入栈 
                    for(i=flag+1; i<q; i++) {
                        stack[++top]=num[i];
                    }
                    flag = q;
                    cout << num[flag]<<" ";
                    m++;
                }
            }
        } else {  //如果满了,那么把栈里面的数据全部输出 
            while(top) {
                cout << stack[top--]<<" ";
                m++;
            }
        }
    }
    return 0;
}

1.  回文素数

【问题描述】

一个数如果从左往右读和从右往左读数字是相同的,则称这个数是回文数,如121,1221,15651都是回文数。给定位数n,找出所有既是回文数又是素数的n位十进制数。(注:不考虑超过整型数范围的情况)。

输入:位数n,其中1<=n<=9。

输出:第一行输出满足条件的素数个数,第二行按照从小到大的顺序输出所有满足条件的素数,两个数之间用一个空格区分。

【样例输入1】

1

【样例输出1】

4

2 3 5 7                    

【样例输入2】

3

【样例输出2】

15

101 131 151 181 191 313 353 373 383 727 757 787 797 919 929

#include<iostream>
using namespace std;
int n;
long long a,b,res[50000],cnt;
//计算并返回10^x
long long mypow(int x) { 
    long long ans=1;
    for(int i=1; i<=x; i++) {
        ans=ans*10;
    }
    return ans;
}
//关键是构造回文数 例如:n等于123,返回12321这样一个回文数
long long huiwen(long long x) { 
    long long ans=x;
    x=x/10;
    while(x>0) {
        ans=ans*10+x%10;
        x/=10;
    }
    return ans;
}
//判断是否为素数 
bool is_prime(long long x) {
    for(long long i=2; i*i<=x; i++) {
        if(x%i==0) {
            return false;
        }
    }
    return true;
}
int main() {
    cin>>n;
    if(n==1) {
        cout << 4 << endl;
        cout << "2 3 5 7" << endl;
    } else if(n==2) {
        cout << 1 << endl;
        cout  << 11 << endl;
    } else if(n%2==0) {
        cout << 0 << endl;
    } else {
        cnt=0;
        n=(n+1)/2;
        //构造[a,b)区间内的回文数
        a=mypow(n-1);
        b=mypow(n);
        for(long long i=a; i<b; i++) {
            long long t=huiwen(i);
            if(is_prime(t)) {
                res[cnt++]=t;
            }
        }
        cout<<cnt<<endl;
        for(int i=0; i<cnt; i++) {
            cout<<res[i]<<" ";
        }
        cout<<endl;
    }

}

2.  栈的操作

【问题描述】

现在有四个栈,其中前三个为空,第四个栈从栈顶到栈底分别为1,2,3,…,n。每一个栈只支持一种操作:弹出并压入。它指的是把其中一个栈A的栈顶元素x弹出,并马上压入任意一个栈B中。但是这样的操作必须符合一定的规则才能进行。规则1:A栈不能为空。规则2:B栈为空或x比B栈栈顶要小。

对于给定的n,请你求出把第四个栈的n个元素全部移到第一个栈的最少操作次数。

由于最少操作次数可能很多,请你把答案对2018取模。

 

 

【输入格式】

    一行,一个n

【输出格式】

一行,一个正整数,为把最少操作次数mod 2018的值

【样例输入】  

2

【样例输出】

3

#include<iostream>
#include<cstdio>
using namespace std;
const long long mod=1000007;
long long  n,ans;
int main() {
    cin >> n;
    long long to;
    for(long long i=1; i<=n; ++i) {
        if((i+1)*i>=2*n) {
            to=i-1;
            break;
        }
    }
    //get to,求出几大块完整的相同项
    long long last=1;
    for(long long i=1; i<=to; ++i) {
        long long it=i*last;
        it%=mod;
        ans+=it;
        ans%=mod;
        last*=2;
        last%=mod;
    }
    //累和
    long long need=2*n-to*to-to;
    need/=2;
    //求出剩下项
    ans+=1*(need*last)%mod;
    //取模
    ans%=mod;
    cout<<ans<<endl;
}
#include<iostream>
#include<cstdio>
using namespace std;
const long long mod=1000007;
long long  n,ans;
int main() {
    cin >> n;
    long long to;
    for(long long i=1; i<=n; ++i) {
        if((i+1)*i>=2*n) {
            to=i-1;
            break;
        }
    }
    //get to,求出几大块完整的相同项
    long long last=1;
    for(long long i=1; i<=to; ++i) {
        long long it=i*last;
        it%=mod;
        ans+=it;
        ans%=mod;
        last*=2;
        last%=mod;
    }
    //累和
    long long need=2*n-to*to-to;
    need/=2;
    //求出剩下项
    ans+=1*(need*last)%mod;
    //取模
    ans%=mod;
    cout<<ans<<endl;
}

3.  波兰表达式

【问题描述】

波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2 + 3) * 4的波兰表示法为* + 2 3 4。本题求解波兰表达式的值,其中运算符包括+ - * /四个。

【输入格式】

输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。

【输出格式】

输出为一行,表达式的值。可直接用printf("%f\n", v)输出表达式的值v。

【样例输入】

* + 11.0 12.0 + 24.0 35.0

【样例输出】

1357.000000

提示:可使用atof(str)把字符串转换为一个double类型的浮点数。atof定义在math.h中

#include <iostream>
#include <cstring>
#include <math.h>
using namespace std;
int main() {
    char str[1001][101]= {};
    int s=1,i = 1;
    int a1,a2;
    a1=a2=0;
    double a[1001]= {};
    int p=0;
    while(cin>>str[s])
        s++;
    s--;
    for(i=s; i>=1; i--) {
        if(strcmp(str[i],"+")==0||strcmp(str[i],"-")==0
                ||strcmp(str[i],"*")==0||strcmp(str[i],"/")==0) {
            if(strcmp(str[i],"-")==0) {
                a[p-1]=a[p]-a[p-1];
                a[p]=0;
                p--;
            }
            if(strcmp(str[i],"+")==0) {
                a[p-1]=a[p]+a[p-1];
                a[p]=0;
                p--;
            }
            if(strcmp(str[i],"*")==0) {
                a[p-1]=a[p]*a[p-1];
                a[p]=0;
                p--;
            }
            if(strcmp(str[i],"/")==0) {
                a[p-1]=a[p]/a[p-1];
                a[p]=0;
                p--;
            }
        } else {
            a[++p]=atof(str[i]);
        }
    }
    printf("%f\n",a[1]);
}