C/C++编程三级 题库
鸡兔同笼
一个笼子里面关了鸡和兔子(鸡有2只脚,兔子有4只脚,没有例外)。已经知道了笼子里面脚的总数a,问笼子里面至少有多少只动物,至多有多少只动物。
时间限制:1000
内存限制:65536
输入
一行,一个正整数a (a < 32768)。
输出
一行,包含两个正整数,第一个是最少的动物数,第二个是最多的动物数,两个正整数用一个空格分开。 如果没有满足要求的答案,则输出两个0,中间用一个空格分开。
样例输入
20
样例输出
5 10
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n % 2 == 1) // jishu
cout << 0 << " " << 0 << endl;
else {
if (n % 4 == 0)
cout << n / 4 << " " << n / 2 << endl;
else
cout << 1 + (n - 2) / 4 << " " << n / 2 << endl;
}
return 0;
}猴子吃桃
海滩上有一堆桃子,N只猴子来分。第一只猴子把这堆桃子平均分为N份,多了一个,这只猴子把多的一个扔入海中,拿走了一份。第二只猴子接着把剩下的桃子平均分成N份,又多了一个,它同样把多的一个扔入海中,拿走了一份。第三、第四、……,第N只猴子仍是最终剩下的桃子分成N份,扔掉多了的一个,并拿走一份。
编写程序,输入猴子的数量N,输出海滩上最少的桃子数,使得每只猴子都可吃到桃子。
时间限制:3000
内存限制:65536
输入
一个整数N。
输出
输出当猴子数量为N时海滩上最少的桃子数。结果保证在int型范围内。
样例输入
2
样例输出
7
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 1;; i++) {//从一开始,没有上界
int ans = i * n + 1;//第n只猴子见到的桃子
for (int j = 1; j < n; j++) {
if (ans % (n - 1) != 0) {
ans = -1;
break;
}
ans = ans / (n - 1) * n + 1;//第n-1,,,只猴子见到的
}
if (ans != -1) {
cout << ans;
break;
}
}
}上台阶
楼梯有n(100 > n > 0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶,编程计算共有多少种不同的走法。
时间限制:1000
内存限制:65536
输入
输入的每一行包括一组测试数据,即为台阶数n。最后一行为0,表示测试结束。
输出
每一行输出对应一行输入的结果,即为走法的数目。
样例输入
1 2 3 4 0
样例输出
1 2 4 7
// 参考答案1:
#include <iostream>
using namespace std;
int t[102];
int main() {
int n;
while (cin >> n) {
if (n == 0)
break;
t[1] = 1;
t[2] = 2;
t[3] = 4;
for (int i = 4; i <= n; i++) {
t[i] = t[i - 1] + t[i - 2] + t[i - 3];
}
cout << t[n] << endl;
}
return 0;
}
// 参考答案2:
#include <iostream>
#include <math.h>
using namespace std;
int main() {
int n;
int f[101];
int i = 0;
while (cin >> n) {
if (n == 0)
break;
f[1] = 1;
f[2] = 2;
f[3] = 4;
for (i = 4; i <= n; i++)
f[i] = f[i - 1] + f[i - 2] + f[i - 3];
cout << f[n] << endl;
}
return 0;
}和数(2023.3)
给定一个正整数序列,判断其中有多少个数,等于数列中其他两个数的和。 比如,对于数列1 2 3 4, 这个问题的答案就是2, 因为3 = 2 + 1, 4 = 1 + 3。
时间限制:10000
内存限制:65536
输入
共两行,第一行是数列中数的个数n ( 1 <= n <= 100),第二行是由n个不大于10000的正整数组成的数列,相邻两个整数之间用单个空格隔开。
输出
一个整数,即数列中等于其他两个数之和的数的个数。
样例输入
4 1 2 3 4
样例输出
2
// 参考答案1:
#include <cstdio>
#include <iostream>
using namespace std;
int a[105];
int main() {
int n, ans = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
bool f = false;
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (i != j && i != k && j != k && a[i] == a[j] + a[k]) {
f = true;
}
}
}
if (f == true)
ans++;
}
cout << ans;
return 0;
}// 参考答案2:
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
int main() {
int N[100];
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> N[i];
}
int total = 0;
for (int c = 0; c < n; c++) {
bool done = false;
for (int a = 0; a < n && !done; a++) {
for (int b = a; b < n && !done; b++) {
if (a != b && a != c && b != c && N[c] == N[a] + N[b]) {
total++;
done = true;
}
}
}
}
cout << total << endl;
return 0;
}质数的和与积(2023.3)
两个质数的和是S,它们的积最大是多少?
时间限制:10000
内存限制:65536
输入
一个不大于10000的正整数S,为两个质数的和。
输出
一个整数,为两个质数的最大乘积。数据保证有解。
样例输入
50
样例输出
589
// 参考答案1:
#include <iostream>
using namespace std;
bool ss(int x) {
for (int i = 2; i < x; i++) {
if (x % i == 0) {
return false;
break;
}
}
return true;
}
int main() {
int x;
cin >> x;
for (int i = x / 2; i >= 1; i--) {
if (ss(i) && ss(x - i)) {
cout << i * (x - i);
break;
}
}
return 0;
}// 参考答案2:
#include <iostream>
using namespace std;
int zs(int n) {
int i, flag = 1;
for (i = 2; i * i <= n; i++) {
if (n % i == 0) {
flag = 0;
break;
}
}
if (flag == 1)
return 1;
else
return 0;
}
int main() {
int mul, a, b, i, s;
cin >> s;
// cout<<zs(6)<<endl;
for (i = s / 2; i >= 2; i--) {
a = zs(i);
b = zs(s - i);
if (a == 1 && b == 1) {
break;
}
}
// cout<<i<<" "<<s-i<<endl;
mul = i * (s - i);
cout << mul << endl;
}铺砖(2023.3)
对于一个2行N列的走道。现在用1*2,2*2的砖去铺满。问有多少种不同的方式。
时间限制:3000
内存限制:131072
输入
整个测试有多组数据,请做到文件底结束。每行给出一个数字N,0 <= n <= 250
输出
如题
样例输入
2 8 12 100 200
样例输出
3 171 2731 845100400152152934331135470251 1071292029505993517027974728227441735014801995855195223534251
#include <algorithm>
#include <iostream>
using namespace std;
string myadd(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int len;
if (a.length() > b.length()) {
len = a.length();
while (b.length() == len)
b += " ";
} else {
len = b.length();
while (a.length() == len)
a += " ";
}
int i = 0, t = 0;
string ans;
while (i < len) {
t += a[i] + b[i] - '0' - '0';
ans += (t % 10 + '0');
t /= 10;
i++;
}
if (t > 0)
ans += t + '0';
reverse(ans.begin(), ans.end());
return ans;
}
int main() {
int n;
string dp[300];
dp[0] = "1";
dp[1] = "1";
dp[2] = "3";
for (int i = 3; i <= 250; i++) {
dp[i] = myadd(dp[i - 1], myadd(dp[i - 2], dp[i - 2]));
}
while (cin >> n) {
cout << dp[n] << endl;
}
return 0;
}找和为K的两个元素
在一个长度为n(n < 1000)的整数序列中,判断是否存在某两个元素之和为k。
时间限制:1000
内存限制:65536
输入
第一行输入序列的长度n和k,用空格分开。 第二行输入序列中的n个整数,用空格分开。
输出
如果存在某两个元素的和为k,则输出yes,否则输出no。
样例输入
9 10 1 2 3 4 5 6 7 8 9
样例输出
yes
//解法1
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;cin>>a>>b;
int s[a];
for(int i=0;i<a;i++){
cin>>s[i];
}
for(int i=0;i<a;i++){
for(int j=0;j<a;j++){
if(s[i]+s[j]==b && s[i]!=s[j]){
cout<<"yes";
return 0;
}
}
}
cout<<"no";
return 0;
}//解法2 数据量比较小暴力即可
#include<bits/stdc++.h>
using namespace std;
int a[1002];
int main(int argc, char *argv[])
{
int n,k;
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(a[j]+a[i]==k) {
printf("yes\n");
return 0;
}
printf("no\n");
return 0;
}硬币面值组合
使用1角、2角、5角硬币组成 n 角钱。
设1角、2角、5角的硬币各用了a、b、c个,列出所有可能的a, b, c组合。
输出顺序为:先按c的值从小到大,若c相同则按b的值从小到大。
时间限制:1000
内存限制:65536
输入
一个整数n(1 <= n <= 100),代表需要组成的钱的角数。
输出
输出有若干行,每行的形式为: i a b c 第1列i代表当前行数(行数从001开始,固定3个字符宽度,宽度不足3的用0填充),后面3列a, b, c分别代表1角、2角、5角硬币的个数(每个数字固定12个字符宽度,宽度不足的在左边填充空格)。
样例输入
10
样例输出
001 10 0 0 002 8 1 0 003 6 2 0 004 4 3 0 005 2 4 0 006 0 5 0 007 5 0 1 008 3 1 1 009 1 2 1 010 0 0 2
//解法1
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b=0;cin>>a;
for(int x=0;x<=a;x++){
for(int j=0;j<=a;j++){
for(int i=a;i>=0;i--){
if(i+2*j+5*x==a){
b+=1;
printf("%03d%12d%12d%12d\n",b,i,j,x);
}
}
}
}
return 0;
}//解法2 暴力枚举
#include<bits/stdc++.h>
using namespace std;
int book[6];
int main()
{
int n;
scanf("%d",&n);
int a,b,c,i=0;
for(c=0;c<=n;c++)
for(b=0;b<=n;b++)
for(a=0;a<=n;a++)
if(a+b*2+c*5==n){
i++;
printf("%03d%12d%12d%12d\n",i,a,b,c);
}
return 0;
}因子问题(2023.12)
任给两个正整数N、M,求一个最小的正整数a,使得a和(M-a)都是N的因子。
时间限制:10000
内存限制:65536
输入
包括两个整数N、M。N不超过1,000,000。
输出
输出一个整数a,表示结果。如果某个案例中满足条件的正整数不存在,则在对应行输出-1
样例输入
35 10
样例输出
5
// C++参考代码1
#include <bits/stdc++.h>
using namespace std;
int a[105][105], row[105], col[105];
int main() {
int n, m;
cin >> n >> m;
int a = 1;
while (true) {
if (n % a == 0 && n % (m - a) == 0) {
cout << a;
return 0;
}
a++;
}
cout << -1;
return 0;
}// C++参考代码2
#include <iostream>
int main() {
int N, M;
std::cin >> N >> M; // 输入N和M
int a = -1; // 结果变量,默认为-1
for (int i = 1; i <= N; i++) {
if (N % i == 0 && N % (M - i) == 0) {
a = i;
break;
}
}
std::cout << a << std::endl;
return 0;
}// C语言参考代码
#include <stdio.h>
int main() {
int N, M;
scanf("%d %d", &N, &M); // 输入N和M
int a = -1; // 结果变量,默认为-1
for (int i = 1; i <= N; i++) {
if (N % i == 0 && N % (M - i) == 0) {
a = i;
break;
}
}
printf("%d\n", a);
return 0;
}Minecraft(2023.12)
Minecraft是一个几乎无所不能的沙盒游戏,玩家可以利用游戏内的各种资源进行创造,搭建自己的世界。
在Minecraft中,基本的建筑元素是边长为1个单位的立方体,Tony想用N个这种小立方体搭建一个长方体,并用他珍藏已久的贴纸对其进行装饰。如果一张贴纸可以贴满小立方体的一个面。那么,他需要用掉多少张贴纸呢?
时间限制:1000
内存限制:65536
输入
一个整数N,表示小明所拥有的小立方体的个数。N不会超过1000。
输出
一个整数,即小明最少用掉的贴纸有多少张。
样例输入
9
样例输出
30
// C++参考代码1
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, ans;
cin >> n;
ans = 10000 * 4;
for (int i = 1; i <= n; i++) // i行
for (int j = 1; i * j <= n; j++) { // j列
if (n % (i * j) == 0) { // 最小单元
int k = n / (i * j);
ans = min(ans, 2 * (i * k + j * k + i * j));
}
}
cout << ans;
return 0;
}// C++参考代码2
#include <iostream>
int main() {
int i, j, k, n, s = 0, min = 1001 * 1001 * 1001;
std::cin >> n;
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
for (k = 1; k <= i; k++) {
if (i * j * k == n && (i * j + j * k + k * i) * 2 <= min) {
min = (i * j + j * k + k * i) * 2;
}
}
}
}
std::cout << min << std::endl;
return 0;
}// C语言参考代码
#include <stdio.h>
int main() {
int i, j, k, n, s = 0, min = 1001 * 1001 * 1001;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
for (k = 1; k <= i; k++) {
if (i * j * k == n && (i * j + j * k + k * i) * 2 <= min) {
min = (i * j + j * k + k * i) * 2;
}
}
}
}
printf("%d\n", min);
return 0;
}吃糖果2(2023.12)
现有n(50 > n > 0)个糖果,每天只能吃2个或者3个,请计算共有多少种不同的吃法吃完糖果。
时间限制:1000
内存限制:65536
输入
输入的每一行包括一组测试数据,即为糖果数n。最后一行为0,表示测试结束。
输出
每一行输出对应一行输入的结果,即为吃法的数目。
样例输入
1 2 3 4 12 0
样例输出
0 1 1 1 12
// C++参考代码1
#include <bits/stdc++.h>
using namespace std;
int a[52] = {0, 0, 1, 1};
int f(int n) {
if (n <= 3)
return a[n];
if (a[n] > 0)
return a[n];
a[n] = f(n - 2) + f(n - 3);
return a[n];
}
int main() {
int n;
while (true) {
cin >> n;
if (n == 0)
break;
cout << f(n) << endl;
}
return 0;
}// C++参考代码2
#include <iostream>
#include <vector>
int countWays(int n) {
std::vector<int> dp(n + 1, 0);
dp[0] = 1; // 初始条件
for (int i = 1; i <= n; i++) {
if (i >= 2) {
dp[i] += dp[i - 2];
}
if (i >= 3) {
dp[i] += dp[i - 3];
}
}
return dp[n];
}
int main() {
int n;
while (std::cin >> n && n != 0) {
int ways = countWays(n);
std::cout << ways << std::endl;
}
return 0;
}// C语言参考代码
#include <stdio.h>
int countWays(int n) {
if (n == 0 || n == 1)
return 0;
else if (n == 2)
return 1;
else if (n == 3)
return 1;
else
return countWays(n - 2) + countWays(n - 3);
}
int main() {
int n;
while (scanf("%d", &n) == 1 && n != 0) {
int ways = countWays(n);
printf("%d\n", ways);
}
return 0;
}谁是你的潜在朋友
“臭味相投”——这是我们描述朋友时喜欢用的词汇。两个人是朋友通常意味着他们存在着许多共同的兴趣。然而作为一个宅男,你发现自己与他人相互了解的机会并不太多。幸运的是,你意外得到了一份北大图书馆的图书借阅记录,于是你挑灯熬夜地编程,想从中发现潜在的朋友。 首先你对借阅记录进行了一番整理,把N个读者依次编号为1,2,…,N,把M本书依次编号为1,2,…,M。同时,按照“臭味相投”的原则,和你喜欢读同一本书的人,就是你的潜在朋友。你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。
时间限制:1000
内存限制:65536
输入
第一行两个整数N,M,2 <= N ,M<= 200。接下来有N行,第i(i = 1,2,…,N)行每一行有一个数,表示读者i-1最喜欢的图书的编号P(1<=P<=M)
输出
包括N行,每行一个数,第i行的数表示读者i有几个潜在朋友。如果i和任何人都没有共同喜欢的书,则输出“BeiJu”(即悲剧,^ ^)
样例输入
4 5 2 3 2 1
样例输出
1 BeiJu 1 BeiJu
#include<iostream>
using namespace std;
const int N = 210;
int n, m;
int q[N], cnt[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> q[i], cnt[q[i]]++;
for(int i = 1; i <= n; i++)
if(cnt[q[i]] == 1) puts("BeiJu");
else cout << cnt[q[i]] - 1 << endl;
return 0;
}踩方格(2023.9)
有一个方格矩阵,矩阵边界在无穷远处。我们做如下假设:
a. 每走一步时,只能从当前方格移动一格,走到某个相邻的方格上;
b. 走过的格子立即塌陷无法再走第二次;
c. 只能向北、东、西三个方向走;
请问:如果允许在方格矩阵上走n步,共有多少种不同的方案。2种走法只要有一步不一样,即被认为是不同的方案。
时间限制:1000
内存限制:65536
输入
允许在方格上行走的步数n(n <= 20)
输出
计算出的方案数量
样例输入
2
样例输出
7
//解法1:以第i步总走法数量为状态
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, f[25];
cin >> n;
f[0] = 1, f[1] = 3;
for(int i = 2; i <= n; ++i)
f[i] = 2*f[i-1] + f[i-2];
cout << f[n];
return 0;
}//解法2:以第i步向左、右、上方向走法数量为状态
#include <bits/stdc++.h>
using namespace std;
#define N 25
int main()
{
int n, l[N], r[N], u[N];
l[1] = r[1] = u[1] = 1;
cin >> n;
for(int i = 2; i <= n; ++i)
{
l[i] = l[i-1] + u[i-1];
r[i] = r[i-1] + u[i-1];
u[i] = l[i-1] + r[i-1] + u[i-1];
}
cout << l[n] + r[n] + u[n];
return 0;
}//解法3:
#include<iostream>
#include<cstring>
using namespace std;
int a[30];
int main()
{
int n,i;
cin>>n;
a[1]=3;
a[2]=7;
for(i=3;i<=n;i++)
a[i]=2*a[i-1]+a[i-2];
cout<<a[n]<<endl;
return 0;
}迷信的病人(2023.9)
医院为了方便对患者进行建档和管理,引入了9位整数ID号来标识每个病人。最近医院入住了一个迷信的病人,他认为ID号的好坏直接决定了自己的命运。他对ID号x有如下要求:
(1)x的前三位数构成的整数是素数
(2)x的后三位数构成的整数是平方数(所谓平方数,是指它是某一个正整数的平方,e.g. 1,4,9,16...)
(3)x中不包含"13"
为了避免不必要的医患矛盾,医院须尽量满足他的需求。现给定正整数区间[m,n],请你判断存在几个满足病人需求的ID号。
时间限制:1000
内存限制:65536
输入
两个正整数m,n,以空格隔开。(999999999>=n>=m>=111111111)
输出
一个整数(满足要求的ID的个数)。
样例输入
157689476 157689687
样例输出
5
提示
存在5个满足要求的ID:157689484,157689529,157689576,157689625,157689676
#include<bits/stdc++.h>
using namespace std;
bool su(int x){
for(int i=2;i<x;i++){
if(x%i==0)
return false;
}
return true;
}
bool pf(int x){
int n=sqrt(x);
if(n*n==x)
return true;
return false;
}
int main(){
int m,n,ans=0;
cin>>m>>n;
for(int i=m;i<=n;i++){
int q,h;
q=i/1000000;
h=i%1000;
int flag=0,k=i;
while(k){
if(k%10==3&&k/10%10==1)
flag=1;
k/=10;
}
if(flag==0&&su(q)&&pf(h))
ans++;
}
cout<<ans;
return 0;
}我家的门牌号(2024.3三级)
我家住在一条短胡同里,这条胡同的门牌号从1开始顺序编号。
若所有的门牌号之和减去我家门牌号的两倍,恰好等于n,求我家的门牌号及总共有多少家。
数据保证有唯一解。
时间限制:1000
内存限制:65536
输入
一个正整数n。n < 100000。
输出
一行,包含两个正整数,分别是我家的门牌号及总共有多少家,中间用单个空格隔开。
样例输入
100
样例输出
10 15
#include <bits/stdc++.h>
using namespace std;
int plass(int n) { return (1 + n) * n / 2; }
int main() {
int n;
int sum, my;
cin >> n;
for (sum = 1; sum > 0; sum++) {
for (my = 1; my <= sum; my++) {
if (plass(sum) - (2 * my) == n) {
cout << my << " " << sum;
return 0;
}
}
}
}最接近的分数
分母不超过 N 且 小于 A/B 的最大最简分数是多少?
时间限制:10000
内存限制:65536
输入
三个正整数 N,A,B,相邻两个数之间用单个空格隔开。1 <= A < B <N <= 1000。
输出
两个正整数,分别是所求分数的分子和分母,中间用单个空格隔开。
样例输入
100 7 13
样例输出
50 93
#include <iostream>
using namespace std;
int main()
{
int n, a, b, p, q, x, y;
scanf("%d%d%d", &n, &a, &b);
// 分子x从1-n,分母y从n-1;结果p/q,开始时1/n(最小值)
p = 1, q = n;
for(x=1; x<=n; x++)
for(y=n; y>=1; y--)
if(b * x < a * y && x * q > p * y)
p = x, q = y;
printf("%d %d\n", p, q);
return 0;
}菲波那契数列(2024.3三级)
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。 给出一个正整数a,要求菲波那契数列中第a个数对10000取模的结果是多少。
时间限制:1000
内存限制:65536
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1 <= a <= 1000000)。
输出
n行,每行输出对应一个输入。输出应是一个正整数,为菲波那契数列中第a个数对10000取模得到的结果。
样例输入
4 5 2 19 1
样例输出
5 1 181 1
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int num;
int a, b, c;
while (n--) {
scanf("%d", &num);
a = 1;
b = 1;
c = 2;
if (num == 1 || num == 2) {
printf("1\n");
} else if (num == 3) {
printf("2\n");
} else {
num -= 3;
while (num--) {
a = b;
b = c;
c = (a + b) % 1000;
}
printf("%d\n", c);
}
}
return 0;
}表达式求值(2024.3三级)
输入一个布尔表达式,请你输出它的真假值。
比如:( V | V ) & F & ( F | V )
V表示true,F表示false,&表示与,|表示或,!表示非。
上式的结果是F
时间限制:1000
内存限制:65536
输入
输入包含多行,每行一个布尔表达式,表达式中可以有空格,总长度不超过1000
输出
对每行输入,如果表达式为真,输出"V",否则出来"F"
样例输入
( V | V ) & F & ( F| V) !V | V & V & !F & (F | V ) & (!F | F | !V & V) (F&F|V|!V&!F&!(F|F&V))
样例输出
F V V
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
char s[1005];
stack<bool> B;
stack<char> C;
int main() {
while (cin.getline(s, 1000, '\n')) {
int len = strlen(s);
while (!B.empty())
B.pop();
while (!C.empty())
C.pop();
for (int i = 0; i < len; ++i) {
if (s[i] == ' ')
continue;
if (s[i] == 'V') {
bool tmp = true;
while (!C.empty() && C.top() == '!') {
C.pop();
tmp = !tmp;
}
B.push(tmp);
} else if (s[i] == 'F') {
bool tmp = false;
while (!C.empty() && C.top() == '!') {
C.pop();
tmp = !tmp;
}
B.push(tmp);
} else if (s[i] == '(' || s[i] == '!') {
C.push(s[i]);
} else if (s[i] == ')') {
while (C.top() != '(') {
char op = C.top();
C.pop();
bool tmp1 = B.top();
B.pop();
bool tmp2 = B.top();
B.pop();
if (op == '&')
B.push(tmp2 && tmp1);
else if (op == '|')
B.push(tmp2 || tmp1);
}
C.pop();
while (!C.empty() && C.top() == '!') {
bool tmp = B.top();
B.pop();
B.push(!tmp);
C.pop();
}
} else if (s[i] == '&') {
while (!C.empty() && C.top() == '&') {
C.pop();
bool tmp1 = B.top();
B.pop();
bool tmp2 = B.top();
B.pop();
B.push(tmp1 && tmp2);
}
C.push(s[i]);
} else if (s[i] == '|') {
while (!C.empty() && (C.top() == '|' || C.top() == '&')) {
bool tmp1 = B.top();
B.pop();
bool tmp2 = B.top();
B.pop();
char op = C.top();
C.pop();
if (op == '&')
B.push(tmp1 && tmp2);
else if (op == '|')
B.push(tmp1 || tmp2);
}
C.push(s[i]);
}
}
while (!C.empty()) {
bool tmp1 = B.top();
B.pop();
bool tmp2 = B.top();
B.pop();
char op = C.top();
C.pop();
if (op == '&')
B.push(tmp1 && tmp2);
else if (op == '|')
B.push(tmp1 || tmp2);
}
if (B.top())
cout << "V" << endl;
else
cout << "F" << endl;
}
return 0;
}广义格雷码(2024.3三级)
在一组数的编码中,若任意两个相邻(首尾也视为相邻)的代码只有一位二进制数不同,则称这种编码为格雷码。如四位格雷码:
0000、0001、0011、0010、0110、0111、0101、0100、1100、1101、1111、1110、1010、1011、1001、1000
现在将格雷码扩展至其他进制,仍然是相邻两个数只能有一位不同。输入两个正整数n,m分别表示长度和进制,每行输出一个n位m进制数,输出任意一种编码即可。(提示:putchar输出效率更高)
时间限制:1000
内存限制:65536
输入
一行,两个整数n,m。其中 2 ≤ n ≤ 12 ,2 ≤ m ≤ 10 且mn ≤ 500000
输出
任意一种编码方案,每个编码一行。相邻两个编码相差一位。第一个编码和最后一个编码算相邻
样例输入
2 3
样例输出
00 10 20 21 01 11 12 22 02
//答案仅供参考,来源于csdn,有部分错误
#include <cstring> //memset(flag,0,sizeof(bool)*12*50010);
#include <iostream>
#include <queue>
using namespace std;
string a[12][50010];
bool flag[12][50010];
queue<string> q;
int n, m;
int main() {
cin >> n >> m;
string temp = "";
// n为1的时候
if (n == 1) {
for (int i = 0; i < m; i++) {
cout << i << endl;
}
return 0;
}
// n大于2的时候
for (int i = 0; i < m; i++) {
// cout<<(temp+char(i+48))<<endl;
q.push(temp + char(i + 48)); // i=0,把字符0入队
}
for (int time = 2; time <= n; time++) {
memset(flag, 0, sizeof(bool) * 12 * 50010);
int size = q.size(), l = 0; // l这里赋值0 因为要从1开始
while (!q.empty()) {
a[0][++l] = q.front();
// cout<<a[0][l]<<" ";
q.pop();
}
// 复制一份 其他行数的
for (int i = 1; i < m; i++) {
for (int j = 1; j <= size; j++) {
a[i][j] = a[0][j];
}
}
// 添加前面一个值: 0—(m-1)
for (int i = 0; i < m; i++) {
for (int j = 1; j <= size; j++) {
a[i][j] = char(i + 48) + a[i][j];
// cout<<a[i][j]<<" ";
flag[i][j] = true;
}
// cout<<endl;
}
// 蛇形取值
int t = size * m; // t表示当前总个数
// 保存第一行到q队列中
for (int i = 1; i <= size; i++) {
q.push(a[0][i]);
flag[0][i] = false;
t--;
}
// cout<<q.size()<<endl;
int x = 0, y = size;
while (t > 0) {
while (flag[x + 1][y] && t > 0) {
flag[++x][y] = false;
q.push(a[x][y]);
t--;
} // 向下
if (flag[x][y - 1] && t > 0) {
flag[x][--y] = false;
q.push(a[x][y]);
t--;
} // 向左一位
while (flag[x - 1][y] && t > 0) {
flag[--x][y] = false;
q.push(a[x][y]);
t--;
} // 向上
if (flag[x][y - 1] && t > 0) {
flag[x][--y] = false;
q.push(a[x][y]);
t--;
} // 再向左一位
}
}
// 输出
while (!q.empty()) {
cout << q.front() << endl;
q.pop();
}
return 0;
}谷歌的招聘
2004年7月,谷歌在硅谷的101号公路边竖立了一块巨大的广告牌用于招聘。内容超级简单,就是一个以 .com 结尾的网址,而前面的网址是一个 10 位素数,这个素数是自然常数 e 中最早出现的 10 位连续数字。能找出这个素数的人,就可以通过访问谷歌的这个网站进入招聘流程的下一步。
自然常数 e 是一个著名的超越数,前面若干位写出来是这样的:e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921… 其中粗体标出的 10 位数就是答案。
本题要求你编程解决一个更通用的问题:从任一给定的长度为 L 的数字中,找出最早出现的 K 位连续数字所组成的素数。
时间限制:7000
内存限制:65535
输入
输入在第一行给出 2 个正整数,分别是 L(不超过 1000 的正整数,为数字长度)和 K(小于10的正整数)。接下来一行给出一个长度为 L 的正整数 N。
输出
在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。如果这样的素数不存在,则输出“404”。注意,原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数,0023 算是解;但第一位 2 不能被当成 0002 输出,因为在原始数字中不存在这个 2 的前导零。
样例输入
样例1:
20 5 23654987725541023819
样例2:
10 3 2468024680
样例输出
样例1:
49877
样例2:
404
//参考代码1 C++
#include<bits/stdc++.h>
using namespace std;
bool prime(int num)
{
if(num <= 1)
return false;
for(int i=2; i<=sqrt(num); i++)
{
if(num%i == 0)
return false;
}
return true;
}
int main()
{
int L,K;
string str;
cin>>L>>K>>str;
bool flag = false;//没有找到的标记
for(int i=0; i<=L-K; i++)
{
//提取字符串
string temp(str,i,K);
//转成数字
stringstream ss(temp);
int num;
ss>>num;
//判断
if(prime(num))
{
flag = true;
cout<<temp;
break;
}
}
if(!flag)
cout<<"404";
return 0;
}//参考代码2 C语言
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int isPrime(long long n) {
if (n < 2) {
return 0;
}
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}
int main() {
int l, k;
scanf("%d %d", &l, &k);
char s[1001];
scanf("%s", s);
int pos = 0;
for (int i = 0; i <= l - k; i++) {
char w[11];
strncpy(w, s + i, k);
w[k] = '\0';
long long ans = atoll(w);
if (isPrime(ans)) {
printf("%s", w);
return 0;
}
pos++;
}
printf("404");
return 0;
}