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]); }