C/C++编程三级 题库
谁是你的潜在朋友
“臭味相投”——这是我们描述朋友时喜欢用的词汇。两个人是朋友通常意味着他们存在着许多共同的兴趣。然而作为一个宅男,你发现自己与他人相互了解的机会并不太多。幸运的是,你意外得到了一份北大图书馆的图书借阅记录,于是你挑灯熬夜地编程,想从中发现潜在的朋友。 首先你对借阅记录进行了一番整理,把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;
}课程冲突
小 A 修了 n 门课程, 第 i 门课程是从第 ai 天一直上到第 bi 天。
定义两门课程的冲突程度为 : 有几天是这两门课程都要上的。
例如 a1=1,b1=3,a2=2,b2=4 时, 这两门课的冲突程度为 2。
现在你需要求的是这 n 门课中冲突程度最大的两门课的冲突程度。
时间限制:1000
内存限制:65536
输入
第一行一个正整数 n 表示课程数量。 接下来 n 行,每行两个正整数 ai,bi。 2 ≤ n≤ 1000, 1 ≤ ai ≤ bi ≤ 1000。
输出
输出一个整数表示最大的冲突程度
样例输入
3 1 3 2 4 5 5
样例输出
2
//参考答案1
#include <bits/stdc++.h>
using namespace std;
//#define PPYDEBUG
struct lesson{
int no; //课程编号
int a; //课程开始a天
int b; //课程结束b天
};
int max_chongtu(lesson x, lesson y){
int r = min(x.b, y.b) - max(x.a, y.a) + 1;
if(r < 0){
r = 0;
}
#ifdef PPYDEBUG
printf("%d = x[%d,%d] - y[%d,%d]\n", r, x.a, x.b, y.a, y.b);
#endif
return r;
}
int main() {
#ifdef LOCAL
freopen("202209_3_1.in", "r", stdin);
#endif
int n;
scanf("%d", &n);
lesson le[1010];
for(int i = 0; i < n; i++){
le[i].no = i + 1;
scanf("%d%d", &le[i].a, &le[i].b);
}
int r = 0;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
r = max(r, max_chongtu(le[i], le[j]));
}
}
printf("%d", r);
return 0;
}//参考答案2
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct project {
int start;
int end;
project(int a,int b):start(a),end(b){}
bool operator <(const project A)const {
if (start == A.start)
return end < A.end;
else
return start < A.start;
}
};
int main() {
int n;
cin >> n;
vector<project>alls;
for (int i = 0; i < n; i++)
{
int a, b;
cin >> a >> b;
alls.push_back(project(a, b));
}
sort(alls.begin(), alls.end());
int result = 0;
for (int i = 0; i < n; i++) {
if (alls[i].end - alls[i].start < result)//剪枝
continue;
for (int j = i + 1; j < n; j++) {
if (alls[j].start > alls[i].end)
break;
int t = min(alls[i].end, alls[j].end) - alls[j].start + 1;
result = max(t, result);
}
}
cout << result << 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;
}Pell数列
Pell数列a1, a2, a3, ...的定义是这样的,a1 = 1, a2 = 2, ... , an = 2 * an − 1 + an - 2 (n > 2)。 给出一个正整数k,要求Pell数列的第k项模上32767是多少。
时间限制:3000
内存限制:65536
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数k (1 ≤ k < 1000000)。
输出
n行,每行输出对应一个输入。输出应是一个非负整数。
样例输入
2 1 8
样例输出
1 408
//解法1:递推
#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main()
{
int n, x;
a[1] = 1, a[2] = 2;
for(int i = 3; i <= 1000000; ++i)
a[i] = (2*a[i-1] + a[i-2])%32767;
cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> x;
cout << a[x] << endl;
}
return 0;
}//解法2:迭代
#include<bits/stdc++.h>
using namespace std;
int main()
{
int ct, p;
cin >> ct;
for(int i = 1; i <= ct; ++i)
{
cin >> p;
if(p <= 2)
cout << p << endl;//第1项是1,第2项是2
else
{
int a = 1, b = 2, t;
for(int j = 3; j <= p; ++j)
{
t = b;
b = (2*b + a)%32767;
a = t;
}
cout << b << endl;
}
}
return 0;
}//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 1000010
#define k 32767
using namespace std;
int a[N];
int f(int x)
{
if(a[x]!=0) return a[x];
if(x==1) return 1;
if(x==2) return 2;
return a[x]=(2*(f(x-1))%k+(f(x-2))%k)%k;
}
int main()
{
int n,a;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a;
cout<<f(a)<<endl;
}
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;
}吉利矩阵
所有元素为非负整数,且各行各列的元素和都等于 7 的 3x3 方阵称为“吉利矩阵”,因为这样的矩阵一共有 666 种。
本题就请你统计一下,把 7 换成任何一个 [2, 9] 区间内的正整数 L,把矩阵阶数换成任何一个 [2, 4] 区间内的正整数 N,满足条件“所有元素为非负整数,且各行各列的元素和都等于 L”的 NxN 方阵一共有多少种?
时间限制:6000
内存限制:65535
输入
输入在一行中给出 2 个正整数 L 和 N,意义如题面所述。数字间以空格分隔。
输出
在一行中输出满足题目要求条件的方阵的个数。
样例输入
7 3
样例输出
666
//参考代码1 C语言
#include <stdio.h>
int res = 0;
int sum_row[4] = {0};
int sum_col[4] = {0};
void dfs(int x, int sum, int width) {
if (x == width * width) {
++res;
return;
}
for (int i = 0; i <= sum; i++) {
if (x % width == width - 1 && i != sum - sum_row[x / width]) continue;
if (x / width == width - 1 && i != sum - sum_col[x % width]) continue;
if (sum_row[x / width] + i <= sum && sum_col[x % width] + i <= sum) {
sum_col[x % width] += i;
sum_row[x / width] += i;
dfs(x + 1, sum, width);
sum_col[x % width] -= i;
sum_row[x / width] -= i;
}
}
}
int main() {
int sum, width;
scanf("%d %d", &sum, &width);
dfs(0, sum, width);
printf("%d\n", res);
return 0;
}//参考代码2
#include<iostream>
using namespace std;
const int N=20;
int a[N][N];
int main(){
int l,n;cin>>l>>n;
a[2][2]=3;
a[2][3]=21;
a[2][4]=282;
a[3][2]=4;
a[3][3]=55;
a[3][4]=2008;
a[4][2]=5;
a[4][3]=120;
a[4][4]=10147;
a[5][2]=6;
a[5][3]=231;
a[5][4]=40176;
a[6][2]=7;
a[6][3]=406;
a[6][4]=132724;
a[7][2]=8;
a[7][3]=666;
a[7][4]=381424;
a[8][2]=9;
a[8][3]=1035;
a[8][4]=981541;
a[9][2]=10;
a[9][3]=1540;
a[9][4]=2309384;
cout<<a[l][n];
}胖达与盆盆奶
大熊猫,俗称“胖达”,会排队吃盆盆奶。它们能和谐吃奶的前提,是它们认为盆盆奶的分配是“公平”的,即:更胖的胖达能吃到更多的奶,等胖的胖达得吃到一样多的奶。另一方面,因为它们是排好队的,所以每只胖达只能看到身边胖达的奶有多少,如果觉得不公平就会抢旁边小伙伴的奶吃。
已知一只胖达每次最少要吃 200 毫升的奶,当另一份盆盆奶多出至少 100 毫升的时候,它们才能感觉到是“更多”了,否则没感觉。
现在给定一排胖达的体重,请你帮饲养员计算一下,在保持给定队形的前提下,至少应该准备多少毫升的盆盆奶?
时间限制:6000
内存限制:65535
输入
输入首先在第一行给出正整数 n(≤ 104),为胖达的个数。随后一行给出 n 个正整数,表示 n 只胖达的体重(公斤)。每个数值是不超过 200 的正整数,数字间以空格分隔。
输出
在一行中输出至少应该准备多少毫升的盆盆奶。
样例输入
10 180 160 100 150 145 142 138 138 138 140
样例输出
3000
提示
样例解释: 盆盆奶的分配量顺序为: 400 300 200 500 400 300 200 200 200 300
//参考代码1 C++
#include <iostream>
using namespace std;
int n, ans, A[10005], L[10005], R[10005];
int main(){
cin >> n;
for (int i = 1; i <= n; i++) cin >> A[i];
for (int i = 1; i < n; i++) {
int j = i;
while(j + 1 <= n && A[j] >= A[j + 1]) {
if (A[j] > A[j + 1]) ++L[i];
++j;
}
}
for (int i = n; i > 1; i--) {
int j = i;
while(j - 1 >= 1 && A[j] >= A[j - 1]) {
if (A[j] > A[j - 1]) ++R[i];
--j;
}
}
for (int i = 1; i <= n; i++) ans += max(L[i], R[i]) * 100 + 200;
cout << ans;
return 0;
}//参考代码2 C语言
#include <stdio.h>
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n, ans = 0;
int A[10005], L[10005] = {0}, R[10005] = {0};
// 读取胖达的个数
scanf("%d", &n);
// 读取每只胖达的体重
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
}
// 计算 L 数组
for (int i = 1; i < n; i++) {
int j = i;
while (j + 1 <= n && A[j] >= A[j + 1]) {
if (A[j] > A[j + 1]) ++L[i];
++j;
}
}
// 计算 R 数组
for (int i = n; i > 1; i--) {
int j = i;
while (j - 1 >= 1 && A[j] >= A[j - 1]) {
if (A[j] > A[j - 1]) ++R[i];
--j;
}
}
// 计算总量
for (int i = 1; i <= n; i++) {
ans += max(L[i], R[i]) * 100 + 200;
}
// 输出结果
printf("%d\n", ans);
return 0;
}加号放哪里
给定任一个正整数 N,我们要从它开始,经过一系列操作得到一个个位数。操作方法是在 N 的各位数字之间放置一个加号,然后执行这个加法计算,得到一个新的数字 N1,再对 N1 执行同样操作,得到 N2 …… 以此类推,直到最后得到的数字只有 1 位,则停止。
例如我们从 N=1234567890 出发,在 5 和 6 之间放置加号,计算 12345+67890=80235;然后在 0 和 2 之间放置加号,计算 80+235=315;然后在 1 和 5 之间放置加号,计算 31+5=36;最后在 3 和 6 之间放置加号,得到 3+6=9 而停止。这样我们通过 4 次计算得到了一个个位数 9。
本题就请你为任一给定的正整数计算:最少需要多少次加号放置可以得到个位数?
注意:加号必须放置在两个数字之间,不可放置在数字的首尾。
时间限制:7000
内存限制:65536
输入
输入在一行中给出一个正整数 n(≤ 1020)。
输出
在一行中首先输出将输入的整数变为个位数,需要放置加号的最少次数;随后输出最后得到的那个个位数。如果最后得到的个位数不唯一,输出最小的那个。 数字间以 1 个空格分隔,行首尾不得有多余空格。
样例输入
1234567890
样例输出
3 9
提示
样例解释: 最优划分是: 1. 12345678+90=12345768 2. 1234+5768=7002 3. 7+002=9
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
long ansfqy = __LONG_MAX__;
int ansnum = 10;
void justdfs(long n, long frequency);
void exceeddfs(char *n, long frequency);
void justdfs(long n, long frequency) {
if (ansfqy < frequency) {
return;
}
if (n < 10 && (n < ansnum || frequency < ansfqy)) {
ansnum = n;
ansfqy = frequency;
return;
}
long temp = 10;
while (n / temp > 0) {
long nleft = n / temp;
long nright = n % temp;
temp *= 10;
justdfs(nleft + nright, frequency + 1);
}
}
void exceeddfs(char *n, long frequency) {
if (ansfqy < frequency) {
return;
}
for (int i = 1; i < strlen(n); i++) {
char BIleft[1025], BIright[1025];
strncpy(BIleft, n, i);
BIleft[i] = '\0';
strncpy(BIright, n + i, strlen(n) - i);
BIright[strlen(n) - i] = '\0';
long sum = atol(BIleft) + atol(BIright);
char temp[1025];
sprintf(temp, "%ld", sum);
if (strlen(temp) < 19) {
justdfs(sum, frequency + 1);
} else {
exceeddfs(temp, frequency + 1);
}
}
}
int main() {
char n[1025];
scanf("%s", n);
if (strlen(n) < 19) {
justdfs(atol(n), 0);
} else {
exceeddfs(n, 0);
}
printf("%ld %d\n", ansfqy, ansnum);
return 0;
}三足鼎立
当三个国家中的任何两国实力之和都大于第三国的时候,这三个国家互相结盟就呈“三足鼎立”之势,这种状态是最稳定的。
现已知本国的实力值,又给出 n 个其他国家的实力值。我们需要从这 n 个国家中找 2 个结盟,以成三足鼎立。有多少种选择呢?
时间限制:10000
内存限制:65536
输入
输入首先在第一行给出 2 个正整数 n(2 ≤ n ≤ 105)和 P(≤ 109),分别为其他国家的个数、以及本国的实力值。随后一行给出 n 个正整数,表示n 个其他国家的实力值。每个数值不超过 109,数字间以空格分隔。
输出
在一行中输出本国结盟选择的个数。
样例输入
7 30 42 16 2 51 92 27 35
样例输出
9
提示
样例解释: 能联合的另外 2 个国家的 9 种选择分别为: {16, 27}, {16, 35}, {16, 42}, {27, 35}, {27, 42}, {27, 51}, {35, 42}, {35, 51}, {42, 51}。
//参考代码1 C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, p;
int a[N];
ll s;
int main() {
cin >> n >> p;
for (int i = 1; i <= n; i ++)
cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i ++) {
int l = i + 1, r = n;
int minn = abs(a[i]-p), maxx = a[i] + p;
int n1, n2; // 记录下标
if (l>r) break;
while (l <= r) { // 找到大于最小值的数
int mid = (l + r) / 2;
if (a[mid] <= minn)
l = mid + 1;
else
r = mid - 1;
}
n1 = l;
l = i + 1, r = n;
while (l <= r) { // 找到小于最大值的数
int mid = (l + r) / 2;
if (a[mid] < maxx)
l = mid + 1;
else
r = mid - 1;
}
n2 = r;
s += (n2 - n1) + 1;
}
cout << s;
return 0;
}//参考代码2 C语言
#include <stdio.h>
#include <stdlib.h>
long long n, x, cnt;
int a[100005];
int cmpfunc(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int upper_bound(int arr[], int n, int x) {
int l = 0;
int r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] <= x) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
int lower_bound(int arr[], int n, int x) {
int l = 0;
int r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] < x) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
int main() {
scanf("%lld %lld", &n, &x);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
qsort(a, n, sizeof(int), cmpfunc);
for (int i = 0; i < n - 1; ++i) {
int l, r;
if (a[i] < x) {
l = upper_bound(a + i + 1, n - i - 1, x - a[i]);
} else {
l = upper_bound(a + i + 1, n - i - 1, a[i] - x);
}
r = lower_bound(a + i + 1, n - i - 1, a[i] + x) - 1;
if (l == n - i - 1) {
continue;
}
cnt += (r - l + 1);
}
printf("%lld\n", cnt);
return 0;
}最近的斐波那契数
斐波那契数列 Fn 的定义为:对 n ≥ 0 有 Fn+2 = Fn+1 + Fn,初始值为 F0 = 0 和 F1 = 1。所谓与给定的整数 N 最近的斐波那契数是指与 N 的差之绝对值最小的斐波那契数。
本题就请你为任意给定的整数 N 找出与之最近的斐波那契数。
时间限制:1000
内存限制:65536
输入
输入在一行中给出一个正整数 N(≤ 108)。
输出
在一行输出与 N 最近的斐波那契数。如果解不唯一,输出最小的那个数。
样例输入
305
样例输出
233
提示
样例解释 部分斐波那契数列为 { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... }。可见 233 和 377 到 305 的距离都是最小值 72,则应输出较小的那个解。
#include<iostream>
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int main(){
int n[101];
n[0]=0,n[1]=1;
for(int i=2;i<43;i++){
n[i]=n[i-1]+n[i-2];
}
int N;
cin>>N;
int min_diff=9999999;
int temp[101]={0},j=0;
for(int i=0;i<43;i++){
if(abs(n[i]-N)<min_diff){
min_diff=abs(n[i]-N);
temp[j++]=n[i];
}
}
cout<<temp[j-1];
return 0;
}构造性证明
关于数学定理证明,也有高下之分。最暴力的证明方法是“构造性证明”,即当需要证明某种解存在时,直接把解构造出来,而不是仅通过推理证明解之存在。
下面有一个定理:
设 ai(i=1, … , 5)均为正实数。则一定存在 4 个互不相同的下标 i、j、k、l,使得 |ai / aj - ak / al| < 1/2。
作为程序员,就请你编写程序构造出正确的下标,验证这个结论。
时间限制:1000
内存限制:65536
输入
输入在一行中顺序给出 5 个正实数。为保证计算中不产生浮点溢出,我们令输入的数字在 [10-10, 1010] 区间内,且小数点后不超过 10 位小数。
输出
在一行中首先输出使得定理结论成立的下标有多少套,随后输出最小的一套下标。数字间以 1 个空格分隔,行首尾不得有多余空格。 注:所谓下标集 {i1, …, i4} 小于下标集 {j1, …, j4},是指存在 1 ≤ k ≤ 4 使得 il=jl 对所有 l < k 成立,且 ik < jk。
样例输入
3.12 5.27 0.0007 9825.4413 10
样例输出
18 1 4 3 2
提示
样例解释: 易验证 |a1/a4-a3/a2|=|3.12/9825.4413 - 0.0007/5.27| < 1/2。满足条件的解有 18 个,例如 5、4、3、2 就是另一套解。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const double EPS = 1e-9;
// 比较两个双精度浮点数是否相等(考虑精度误差)
bool doubleEqual(double a, double b) {
return fabs(a - b) < EPS;
}
int main() {
vector<double> nums(5);
for (int i = 0; i < 5; ++i) {
cin >> nums[i];
}
int count = 0;
vector<int> result(4);
// 四重循环遍历所有可能的四个下标组合
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
if (i == j) continue;
for (int k = 0; k < 5; ++k) {
if (k == i || k == j) continue;
for (int l = 0; l < 5; ++l) {
if (l == i || l == j || l == k) continue;
double val = fabs(nums[i] / nums[j] - nums[k] / nums[l]);
if (val < 0.5) {
count++;
if (count == 1) {
result = {i + 1, j + 1, k + 1, l + 1};
}
}
}
}
}
}
cout << count << " ";
for (int idx : result) {
cout << idx << " ";
}
return 0;
}环形公路出口
一条环形高速路上有 N 个出口。给定任意一对出口,请你算出这两个出口之间的最短距离。
时间限制:1000
内存限制:65536
输入
输入第一行给出区间 [3,105] 内的整数 N,以及 N 个整数距离 D1 D2 … DN,其中 Di 是第 i 和第 i+1 个出口之间的距离,DN 是第 N 和第 1 个出口之间的距离。同行数字间以空格分隔。 第二行给出正整数 M (≤ 104)。随后 M 行,每行给出一对出口的编号(出口从 1 到 N 顺序编号)。题目保证公路全长不超过 107。
输出
输出 M 行,每行给出对应输入的一对出口之间的最短距离。
样例输入
5 1 2 4 14 9 3 1 3 2 5 4 1
样例输出
3 10 7
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> distances(N);
for (int i = 0; i < N; ++i) {
cin >> distances[i];
}
vector<int> prefixSum(N + 1, 0);
for (int i = 0; i < N; ++i) {
prefixSum[i + 1] = prefixSum[i] + distances[i];
}
int M;
cin >> M;
for (int i = 0; i < M; ++i) {
int start, end;
cin >> start;
cin >> end;
if (start > end) {
swap(start, end);
}
int sum = prefixSum[end - 1] - prefixSum[start - 1];
int total = prefixSum.back();
cout << min(sum, total - sum) << endl;
}
return 0;
}子串与子列
子串是一个字符串中连续的一部分,而子列是字符串中保持字符顺序的一个子集,可以连续也可以不连续。例如给定字符串 atpaaabpabtt,pabt 是一个子串,而 pat 就是一个子列。
现给定一个字符串 S 和一个子列 P,本题就请你找到 S 中包含 P 的最短子串。若解不唯一,则输出起点最靠左边的解。
时间限制:1000
内存限制:65536
输入
输入在第一行中给出字符串 S,第二行给出 P。S 非空,由不超过 104 个小写英文字母组成;P 保证是 S 的一个非空子列。
输出
在一行中输出 S 中包含 P 的最短子串。若解不唯一,则输出起点最靠左边的解。
样例输入
atpaaabpabttpcat pat
样例输出
pabt
#include <stdio.h>
#include <string.h>
int main(){
char s[10001], p[10001];
int i, j, t = 0, len, min = 10001, m, n, k = 0, flag = 0;
scanf("%s\n%s", s, p);
while(1){
for(i = 0;i < strlen(p);i++){
if(!i){
for(j = t + k;j < strlen(s);j++){
if(s[j] == p[i]){
k = 1;
break;
}
}
t = j;
}else{
for(j++;j < strlen(s);j++){
if(s[j] == p[i]) break;
}
}
if(j == strlen(s)){
flag = 1;
break;
}
}
if(flag == 1) break;
len = j - t + 1;
if(len < min){
min = len;
m = t;
n = j;
}
}
for(i = m;i <= n;i++) printf("%c", s[i]);
return 0;
}拼大数
如何随机生成一个有 n 位数的大数呢?一种方法是,找到 n 个小朋友,每人发一张卡片,卡片一面写着编号(这里假设小朋友们从 1 到 n 编号),另一面让他们随便写下一个 1 位数字。然后让小朋友们把自己的卡片在墙上钉成一排,要求一张挨着一张,按他们的编号升序排列,显示他们自己写的数字。
但是,让十万个孩子都按指令行动,可太难了。结果是卡片乱七八糟满墙都是,有些甚至显示的不是正确的面。例如第 23 号小朋友在卡片上写了 8,我们应该在墙上看到 8,但是却看到了 23…… 你的任务就是把这些卡片整理好,得到我们真想要拼成的大数。
时间限制:6000
内存限制:65536
输入
输入第一行给出一个正个整数 n (≤ 105),随后 n 行,每行按 n1 n2的格式给出一张卡片两面的数字。
输出
在一行中输出我们真想要拼成的 n 位大数。 如果卡片两面都是 1 位数,那么就很难说哪个数字是编号,哪个数字是小朋友自己写的,所以解可能是不唯一的。这时候需要输出能得到的最小的数字。
样例输入
12 7 11 8 9 3 1 2 12 4 6 10 0 5 1 2 5 6 8 1 4 7 2 9 3
样例输出
359114268072
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n;
cin >> n;
vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>> pq(n + 1);
vector<pair<int, int>> cards(n);
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
cards[i].first = a;
cards[i].second = b;
// Check if a is a valid id and b is a valid digit
if (a >= 1 && a <= n && b >= 0 && b <= 9) {
pq[a].emplace(b, i);
}
// Check if b is a valid id and a is a valid digit
if (b >= 1 && b <= n && a >= 0 && a <= 9) {
pq[b].emplace(a, i);
}
}
vector<bool> used(n, false);
vector<int> result(n + 1, -1);
for (int i = 1; i <= n; ++i) {
while (!pq[i].empty()) {
auto [d, idx] = pq[i].top();
pq[i].pop();
if (!used[idx]) {
used[idx] = true;
result[i] = d;
break;
}
}
if (result[i] == -1) {
cout << "No solution" << endl;
return 0;
}
}