C/C++编程四级 题库
酒鬼
Santo刚刚与房东打赌赢得了一间在New Clondike 的大客厅。今天,他来到这个大客厅欣赏他的奖品。房东摆出了一行瓶子在酒吧上。瓶子里都装有不同体积的酒。令Santo高兴的是,瓶子中的酒都有不同的味道。房东说道:“你可以喝尽可能多的酒,但是一旦打开酒盖你就必须把它喝完,喝完一瓶后把它放回原处。还有一件最重要的事,你必须从左至右依次喝,并且不能连续超过三瓶,不然会给你带来坏运气。”现在可怜的Santo站在酒吧前努力的想着,他到底应该喝哪几瓶才能使喝的酒最多呢?请帮助他找出他应该喝的酒瓶号,因为思考让他感到不安。
时间限制:2000
内存限制:131072
输入
第一行一个整数N,有N个酒瓶。N<=700接下有N行,第I+1行的数字代表酒瓶I中酒的体积。
输出
一个数字,喝的酒的最大总体积。遵守以上规则,使得三个连续瓶子中至少一个瓶子是满的。
样例输入
6 6 10 13 9 8 1
样例输出
33
//样例代码 递推
#include <bits/stdc++.h>
using namespace std;
int n,a[10005],dp[10005][2];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
dp[1][0]=0; //第一瓶没喝
dp[1][1]=a[1];//第一瓶喝了
for(int i=2;i<=n;i++){
//第i瓶没喝=max(i-1瓶没喝,i-1瓶喝了)
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
//第i瓶喝了=max(i-1瓶没喝,i-2瓶没喝+i-1瓶喝了)
dp[i][1]=a[i]+max(dp[i-1][0],dp[i-2][0]+a[i-1]);
}
cout<<max(dp[n][0],dp[n][1]);
return 0;
}大盗
阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺,每家店中都有一些现金。阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。
作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?
时间限制:1000
内存限制:65536
输入
输入的第一行是一个整数 T (T <= 50) ,表示一共有 T 组数据。 接下来的每组数据,第一行是一个整数 N (1 <= N <= 100, 000) ,表示一共有 N 家店铺。第二行是 N 个被空格分开的正整数,表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 1000 。
输出
对于每组数据,输出一行。该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。
样例输入
2 3 1 8 2 4 10 7 6 14
样例输出
8 24
提示
对于第一组样例,阿福选择第 2 家店铺行窃,获得的现金数量为 8 。 对于第二组样例,阿福选择第 1 和 4 家店铺行窃,获得的现金数量为 10 + 14 = 24 。
//样例代码 递推
#include <iostream>
using namespace std;
const int N=100005;
int a[N],f[N];
int main()
{
int t,n;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
f[1]=a[1];//有1家店必偷
f[2]=max(a[1],a[2]);//第二家店可偷可不偷
for(int i=3;i<=n;i++){
//第i家店=max(第i家不偷,第i-1家不偷+第i家偷)
f[i]=max(f[i-1],f[i-2]+a[i]);
}
cout<<f[n]<<endl;
}
return 0;
}盒子与小球之二
N个有差别的盒子(1<=N<=20)。你有A个红球和B个蓝球。0 <= A <= 15, 0 <= B <= 15。球除了颜色没有任何区别。你可以将球放进盒子。一个盒子可以同时放进两种球,也可以只放一种,也可以空着。球不必全部放入盒子中。编程计算有多少种放置球的方法。
时间限制:10000
内存限制:131072
输入
就一行,N,A,B,用空格分开
输出
就一行,输出放置方案总数
样例输入
2 1 1
样例输出
9
//参考答案1
/*
对于红球和蓝球两种球,每个盒子可以同时放两种球,也可以放一种,
所以我们分开来考虑。ans=放红球的方案数*放蓝球的方案数。
现在我们来解决放红球的方案数,用插板法。
A个球放到N个盒子里,由于球可以不用放完,
我们可认为是求解方程x1+x2+...+xn<=A,其中x1,x2,...,xn>=0。
因此,我们可看作有(N+A)个空位,从这些空位中任选A个位置放小球,
方案数为C(N+A,A)。本题ans=C(N+A,A)*C(N+B,B)。
*/
#include <iostream>
using namespace std;
int n,a,b;
long long C(int n,int m)
{
long long ans=1;
for(int i=1;i<=m;i++)
ans=ans*(n-i+1)/i;//注意先乘进去 最后再除
return ans;
}
int main()
{
cin>>n>>a>>b;
cout<<C(n+a,a)*C(n+b,b);
return 0;
}//参考答案2
#include <iostream>
#include <algorithm>
using namespace std;
long long f[22][17][17];
//f[i][j][k]表示前i个盒子里一共放了j个红球和k个蓝球的方案数
int main()
{
int n,A,B;
cin>>n>>A>>B;
f[0][0][0]=1;
for(int i=1;i<=n+1;i++)//n个盒子
for(int j=0;j<=A;j++)
for(int k=0;k<=B;k++)
for(int a=0;a<=j;a++)
for(int b=0;b<=k;b++)
f[i][j][k]+=f[i-1][j-a][k-b];
cout<<f[n+1][A][B];
return 0;
}最长上升子序列(2024.3四级)
一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN),我们可以得到一些上升的子序列(ai1, ai2, …, aiK),这里1 <= i1 < i2 < … < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8). 你的任务,就是对于给定的序列,求出最长上升子序列的长度。
时间限制:11000
内存限制:65536
输入
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。
输出
最长上升子序列的长度。
样例输入
7 1 7 3 5 9 4 8
样例输出
4
#include <bits/stdc++.h>
#define fio \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
using namespace std;
const int maxn = 1010;
int a[maxn];
int maxLen[maxn];
int main() {
fio int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
maxLen[i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[i] > a[j]) {
maxLen[i] = max(maxLen[i], maxLen[j] + 1);
}
}
}
cout << *max_element(maxLen + 1, maxLen + n + 1) << endl;
}重启系统(2024.3四级)
小明帮助管理一个处理数据的计算系统,有N个待处理的任务,需要按照顺序来完成这些任务,即每次所完成任务的编号都要大于前一个完成任务的编号,且单个任务不可以分解完成。计算系统运行着一个奇怪的保护程序,它限制了系统当前所能处理的数据量不能超过上次完成任务所处理的数据量。重启系统可以使它立刻恢复到最高性能(一开始系统拥有最高性能,最高性能大于任何待处理任务的数据量)。小明有一次重启系统的权限(也可以不使用),你能帮他算出最多能完成几个任务吗?
时间限制:1000
内存限制:65536
输入
第一行: N (2 <= N <= 1000) 待处理的任务数 第二行: N个整数,每个任务的数据量
输出
输出只包括一行,这一行只包含一个整数,表示最多能完成的任务数。
样例输入
10
1 5 4 3 2 10 9 8 7 6
样例输出
9
提示
回想一下最长上升子序列问题
#include <bits/stdc++.h>
using namespace std;
int dpleft[10005], dpright[10005], a[10005];
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
dpright[i] = dpleft[i] = 1;
}
reverse(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[i] >= a[j]) {
dpleft[i] = max(dpleft[i], dpleft[j] + 1);
}
}
}
for (int i = 2; i <= n; i++) {
dpleft[i] = max(dpleft[i - 1], dpleft[i]);
}
// for(int i = 1; i <= n; i++){
// printf("%d = %d\n", i, dpleft[i]);
// }
for (int i = n - 1; i >= 1; i--) {
for (int j = n; j > i; j--) {
if (a[i] <= a[j]) {
dpright[i] = max(dpright[i], dpright[j] + 1);
}
}
}
for (int i = n - 1; i >= 1; i--) {
dpright[i] = max(dpright[i], dpright[i + 1]);
}
int ans = 0;
for (int x = 1; x <= n; x++) {
ans = max(ans, dpleft[x] + dpright[x + 1]);
}
// printf("---------\n");
// for(int i = 1; i <= n; i++){
// printf("%d = %d\n", i, dpright[i]);
// }
printf("%d\n", ans);
return 0;
}硬币(2024.3四级)
宇航员 Bob 有一天来到火星上, 他有收集硬币的习惯。 于是他将火星上所有面值的硬币都收集起来了, 一共有 n 种, 每种只有一个: 面值分别为 a1,a2… an。 Bob 在机场看到了一个特别喜欢的礼物, 想买来送给朋友 Alice, 这个礼物的价格是 X 元。 Bob 很想知道为了买这个礼物他的哪些硬币是必须被使用的, 即 Bob 必须放弃收集好的哪些硬币种类。 飞机场不提供找零, 只接受恰好 X 元。
时间限制: 1000
内存限制: 262144
输入
第一行包含两个正整数 n 和 x。 (1 <= n <= 200, 1 <= x <= 10000)
第二行从小到大为 n 个正整数 a1, a2, a3 … an (1 <= ai <= 10000)
输出
第一行是一个整数, 即有多少种硬币是必须被使用的。 第二行是这些必须使用的硬币的面值(从小到大排列) 。
样例输入
5 18 1 2 3 5 10
样例输出
2 5 10
提示
输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 X元。 如果不存在必须被使用的硬币, 则第一行输出 0, 第二行输出空行。
#include <iostream>
using namespace std;
int val[210] = {0};
int ways[10000] = {0};
int ans[210] = {0};
int cal(int x, int y) {
if (x < 0)
return 0;
return ways[x] - cal(x - y, y);
}
int main() {
int N, Max;
cin >> N >> Max;
for (int i = 1; i <= N; ++i)
cin >> val[i];
ways[0] = 1;
for (int i = 1; i <= N; ++i)
for (int j = Max; j >= val[i]; --j)
ways[j] += ways[j - val[i]];
int cnt = 0;
for (int i = 1; i <= N; ++i)
if (cal(Max, val[i]) == 0)
ans[cnt++] = val[i];
cout << cnt << endl;
if (cnt == 0)
cout << ' ' << endl;
else {
cout << ans[0];
for (int i = 1; i < cnt; ++i)
cout << ' ' << ans[i];
}
return 0;
}奶牛散步
从一个无限大的矩阵的中心点出发,一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法?
时间限制:10000
内存限制:131072
输入
一个数字,代表N,N<=1000
输出
输出有多少方案数模12345
样例输入
2
样例输出
7
// 上一步向上走,下一步可以向左、右、上
// 上一步向左走,下一步可以向左、上
// 上一步向右走,下一步可以向右、上
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long lr = 2, up = 1;
int i = 0;
long long tmplr = 0, tmpup = 0;
if (n == 1) {
cout << 3;
} else {
for (i = 2; i <= n; i++) {
tmplr = lr;
tmpup = up;
lr = (tmpup * 2 + tmplr) % 12345;
up = (tmpup + tmplr) % 12345;
}
cout << (up + lr) % 12345;
}
return 0;
}移动路线(2023.12)
桌子上有一个m行n列的方格矩阵,将每个方格用坐标表示,行坐标从下到上依次递增,列坐标从左至右依次递增,左下角方格的坐标为(1,1),则右上角方格的坐标为(m,n)。
小明是个调皮的孩子,一天他捉来一只蚂蚁,不小心把蚂蚁的右脚弄伤了,于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中,蚂蚁从左下角的方格中移动到右上角的方格中,每步移动一个方格。蚂蚁始终在方格矩阵内移动,请计算出不同的移动路线的数目。
对于1行1列的方格矩阵,蚂蚁原地移动,移动路线数为1;对于1行2列(或2行1列)的方格矩阵,蚂蚁只需一次向右(或向上)移动,移动路线数也为1……对于一个2行3列的方格矩阵,如下图所示:
-------------------
|(2,1)|(2,2)|(2,3)|
-------------------
|(1,1)|(1,2)|(1,3)|
-------------------
蚂蚁共有3种移动路线:
路线1:(1,1) → (1,2) → (1,3) → (2,3)
路线2:(1,1) → (1,2) → (2,2) → (2,3)
路线3:(1,1) → (2,1) → (2,2) → (2,3)
时间限制:1000
内存限制:65536
输入
输入只有一行,包括两个整数m和n(0<m+n<=20),代表方格矩阵的行数和列数,m、n之间用空格隔开
输出
输出只有一行,为不同的移动路线的数目。
样例输入
2 3
样例输出
3
// C++参考代码1
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 40;
const int dx[2] = {0, 1};
const int dy[2] = {1, 0};
int n, m, ans = 0;
bool flag = false;
struct node {
int x;
int y;
} st[N * N], tu[N * N][N * N];
int a[N * N];
bool ran_out(int x, int y) { return x < 1 || x > n || y < 1 || y > m; }
void fuzhi(int step) {
ans++;
a[ans] = step;
flag = true;
for (int i = 0; i <= step; i++) {
tu[ans][i].x = st[i].x;
tu[ans][i].y = st[i].y;
}
}
void dfs(int x, int y, int step) {
st[step].x = x;
st[step].y = y;
if (x == n && y == m) {
fuzhi(step);
return;
}
for (int i = 0; i < 2; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (!ran_out(xx, yy)) {
dfs(xx, yy, step + 1);
}
}
}
int main() {
std::ios::sync_with_stdio(false);
cin >> n >> m;
dfs(1, 1, 0);
printf("%d\n", ans);
for (int i = 1; i <= ans; i++)
return 0;
}// C++参考代码2
#include <iostream>
#include <vector>
using namespace std;
int countRoutes(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 1));
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
int main() {
int m, n;
cin >> m >> n;
int result = countRoutes(m, n);
cout << result << endl;
return 0;
}// C语言参考代码
#include <stdio.h>
int countRoutes(int m, int n) {
// 创建一个二维数组用于存储移动路线数
int routes[m][n];
// 初始化边界条件
for (int i = 0; i < m; i++) {
routes[i][0] = 1;
}
for (int j = 0; j < n; j++) {
routes[0][j] = 1;
}
// 计算每个方格的移动路线数
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
routes[i][j] = routes[i-1][j] + routes[i][j-1];
}
}
// 返回右上角方格的移动路线数
return routes[m-1][n-1];
}
int main() {
int m, n;
scanf("%d %d", &m, &n);
int result = countRoutes(m, n);
printf("%d\n", result);
return 0;
}公共子序列(2023.12)
我们称序列 Z = < z1, z2, ..., zk >是序列 X = < x1, x2, ..., xm >的子序列当且仅当存在 严格上升 的序列< i1, i2, ..., ik >, 使得对 j = 1, 2, ... ,k, 有xij = zj。 比如 Z = < a, b, f, c > 是 X = < a, b, c, f, b, c >的子序列。 现在给出两个序列 X 和 Y, 你的任务是找到 X 和 Y 的最大公共子序列, 也就是说要找到一个最长的序列 Z, 使得 Z 既是 X 的子序列也是 Y 的子序列。
时间限制: 3000
内存限制: 65536
输入
输入包括多组测试数据。 每组数据包括一行, 给出两个长度不超过200 的字符串, 表示两个序列。 两个字符串之间由若干个空格隔开。
输出
对每组输入数据, 输出一行, 给出两个序列的最大公共子序列的长度。
样例输入
abcfbc abfcab programming contest abcd mnp
样例输出
4 2 0
// C++参考代码1
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
if (a > b)
return a;
else
return b;
}
int main() {
char s1[201], s2[201];
while (scanf("%s %s", s1, s2) != EOF) {
int dp[201][201];
memset(dp, 0, sizeof(dp));
int m = strlen(s1), n = strlen(s2);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
printf("%d\n", dp[m][n]);
}
return 0;
}// C++参考代码2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int longestCommonSubsequence(string X, string Y) {
int m = X.length();
int n = Y.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (X[i - 1] == Y[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
int main() {
string X, Y;
while (cin >> X >> Y) {
int result = longestCommonSubsequence(X, Y);
cout << result << endl;
}
return 0;
}// C语言参考代码
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int longestCommonSubsequence(char* X, char* Y) {
int m = strlen(X);
int n = strlen(Y);
int L[m+1][n+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
return L[m][n];
}
int main() {
char X[201], Y[201];
while (scanf("%s %s", X, Y) != EOF) {
int result = longestCommonSubsequence(X, Y);
printf("%d\n", result);
}
return 0;
}田忌赛马(2023.12)
你一定听过田忌赛马的故事吧?
如果3匹马变成1000匹,齐王仍然让他的马按从优到劣的顺序出赛,田忌可以按任意顺序选择他的赛马出赛。赢一局,田忌可以得到200两银子,输一局,田忌就要输掉200两银子,平局的话不输不赢。
请问田忌最多能赢多少银子?
时间限制:5000
内存限制:65536
输入
输入包含多组测试数据. 每组测试数据的第一行是一个整数n(1<=n<=1000),表示田忌和齐王都拥有n匹马。接下来一行是n个整数,表示田忌的马的速度,下一行也是n个整数,表示齐王的马的速度。 输入的最后以一个0表示结束。
输出
对每组数据,输出一个整数,表示田忌至多可以赢多少银子,如果田忌赢不了,就输出一个负数,表示田忌最少要输多少银子。
样例输入
3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0
样例输出
200 0 0
// C++参考代码1
#include <bits/stdc++.h>
using namespace std;
int h1, h2, t1, t2, n, i, ans = 0;
int t[100001], k[100001];
int cmp(int a, int b) { return a > b; }
int main() {
while (cin >> n && n) {
for (i = 1; i <= n; i++)
cin >> t[i];
for (i = 1; i <= n; i++)
cin >> k[i];
sort(t + 1, t + n + 1, cmp);
sort(k + 1, k + n + 1, cmp);
h1 = h2 = 1;
t1 = t2 = n;
while (h1 <= t1) {
if (t[h1] > k[h2])
ans += 200, h1++, h2++;
else {
if (t[h1] < k[h2])
ans -= 200, t1--, h2++;
else {
if (t[t1] > k[t2])
ans += 200, t1--, t2--;
else {
if (t[t1] < k[h2])
ans -= 200;
t1--, h2++;
}
}
}
}
cout << ans << endl;
ans = 0;
}
}// C++参考代码2
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
while (cin >> n && n != 0) {
int tianji[1001], qiwang[1001];
for (int i = 0; i < n; i++) {
cin >> tianji[i];
}
for (int i = 0; i < n; i++) {
cin >> qiwang[i];
}
sort(tianji, tianji + n);
sort(qiwang, qiwang + n);
int tianjiIdx = 0, qiwangIdx = 0;
int profit = 0;
while (tianjiIdx < n && qiwangIdx < n) {
if (tianji[tianjiIdx] > qiwang[qiwangIdx]) {
profit += 200;
tianjiIdx++;
qiwangIdx++;
} else if (tianji[tianjiIdx] < qiwang[qiwangIdx]) {
profit -= 200;
tianjiIdx++;
} else {
if (tianji[n - 1] > qiwang[n - 1]) {
profit += 200;
}
tianjiIdx++;
qiwangIdx++;
}
}
cout << profit << endl;
}
return 0;
}// C语言参考代码
#include <stdio.h>
#include <stdlib.h>
int h1, h2, t1, t2, n, i, ans = 0;
int t[100001], k[100001];
int cmp(const void* a, const void* b) {
return (*(int*)b - *(int*)a);
}
int main() {
while (scanf("%d", &n) && n) {
for (i = 1; i <= n; i++) scanf("%d", &t[i]);
for (i = 1; i <= n; i++) scanf("%d", &k[i]);
qsort(t + 1, n, sizeof(int), cmp);
qsort(k + 1, n, sizeof(int), cmp);
h1 = h2 = 1;
t1 = t2 = n;
while (h1 <= t1) {
if (t[h1] > k[h2])
ans += 200, h1++, h2++;
else if (t[h1] < k[h2])
ans -= 200, t1--, h2++;
else if (t[t1] > k[t2])
ans += 200, t1--, t2--;
else if (t[t1] < k[h2])
ans -= 200, t1--, h2++;
else
break;
}
printf("%d\n", ans);
ans = 0;
}
return 0;
}宠物小精灵之收服(2023.12)
宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。
一天,小智和皮卡丘来到了小精灵狩猎场,里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而,野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言,小智可能需要使用很多个精灵球才能收服它,而在收服过程中,野生小精灵也会对皮卡丘造成一定的伤害(从而减少皮卡丘的体力)。当皮卡丘的体力小于等于0时,小智就必须结束狩猎(因为他需要给皮卡丘疗伤),而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。当小智的精灵球用完时,狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择:收服它,或者离开它。如果小智选择了收服,那么一定会扔出能够收服该小精灵的精灵球,而皮卡丘也一定会受到相应的伤害;如果选择离开它,那么小智不会损失精灵球,皮卡丘也不会损失体力。
小智的目标有两个:主要目标是收服尽可能多的野生小精灵;如果可以收服的小精灵数量一样,小智希望皮卡丘受到的伤害越小(剩余体力越大),因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力,已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。请问,小智该如何选择收服哪些小精灵以达到他的目标呢?
时间限制:1000
内存限制:65536
输入
输入数据的第一行包含三个整数:N(0 < N < 1000),M(0 < M < 500),K(0 < K < 100),分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。 之后的K行,每一行代表一个野生小精灵,包括两个整数:收服该小精灵需要的精灵球的数量,以及收服过程中对皮卡丘造成的伤害。
输出
输出为一行,包含两个整数:C,R,分别表示最多收服C个小精灵,以及收服C个小精灵时皮卡丘的剩余体力值最多为R。
样例输入
样例输入1:
10 100 5 7 10 2 40 2 50 1 20 4 20
样例输入2:
10 100 5 8 110 12 10 20 10 5 200 1 110
样例输出
样例输出1:
3 30
样例输出2:
0 100
提示
对于样例输入1:小智选择:(7,10) (2,40) (1,20) 这样小智一共收服了3个小精灵,皮卡丘受到了70点伤害,剩余100-70=30点体力。所以输出3 30 对于样例输入2:小智一个小精灵都没法收服,皮卡丘也不会收到任何伤害,所以输出0 100
// C++代码1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Pokemon {
int ballsNeeded;
int damage;
};
bool sortByDamage(const Pokemon& p1, const Pokemon& p2) {
return p1.damage < p2.damage;
}
int main() {
int N, M, K;
cin >> N >> M >> K;
vector<Pokemon> pokemons;
for (int i = 0; i < K; i++) {
int balls, damage;
cin >> balls >> damage;
pokemons.push_back({balls, damage});
}
sort(pokemons.begin(), pokemons.end(), sortByDamage);
int maxCaught = 0;
int maxRemainingHP = M;
int currentBalls = N;
int currentHP = M;
for (int i = 0; i < K; i++) {
int balls = pokemons[i].ballsNeeded;
int damage = pokemons[i].damage;
if (currentHP <= damage) {
break;
}
int maxPossibleCaught = min(currentBalls / balls, (currentHP - 1) / damage);
if (maxPossibleCaught > maxCaught) {
maxCaught = maxPossibleCaught;
maxRemainingHP = currentHP - maxCaught * damage;
}
currentHP -= damage;
currentBalls -= balls;
}
cout << maxCaught << " " << maxRemainingHP << endl;
return 0;
}// C++代码2
#include <bits/stdc++.h>
#define N 5000
using namespace std;
int f[N][N];
int n, m, k;
int a[N], b[N], c[N];
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= k; i++) {
cin >> a[i] >> b[i];
}
for (int i = 1; i <= k; i++) {
for (int j = n; j >= a[i]; j--) {
for (int l = m; l >= b[i]; l--)
f[j][l] = max(f[j][l], f[j - a[i]][l - b[i]] + 1);
}
}
int ans;
for (ans = 0; ans <= m; ans++) {
if (f[n][ans] == f[n][m])
break;
}
printf("%d %d\n", f[n][m], m - ans);
return 0;
}// C语言参考代码
#include <stdio.h>
#include <stdlib.h>
#define N 5000
int f[N][N];
int n, m, k;
int a[N], b[N], c[N];
int max(int a, int b) {
return (a > b) ? a : b;
}
int main() {
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= k; i++) {
scanf("%d %d", &a[i], &b[i]);
}
for (int i = 1; i <= k; i++) {
for (int j = n; j >= a[i]; j--) {
for (int l = m; l >= b[i]; l--) {
f[j][l] = max(f[j][l], f[j - a[i]][l - b[i]] + 1);
}
}
}
int ans;
for (ans = 0; ans <= m; ans++) {
if (f[n][ans] == f[n][m])
break;
}
printf("%d %d\n", f[n][m], m - ans);
return 0;
}人以群分
社交网络中我们给每个人定义了一个“活跃度”,现希望根据这个指标把人群分为两大类,即外向型(outgoing,即活跃度高的)和内向型(introverted,即活跃度低的)。要求两类人群的规模尽可能接近,而他们的总活跃度差距尽可能拉开。
时间限制:5000
内存限制:65536
输入
输入第一行给出一个正整数 N(2 ≤ N ≤ 105)。随后一行给出 N 个正整数,分别是每个人的活跃度,其间以空格分隔。题目保证这些数字以及它们的和都不会超过 231。
输出
按下列格式输出: Outgoing #: N1 Introverted #: N2 Diff = N3 其中 N1 是外向型人的个数;N2 是内向型人的个数;N3 是两群人总活跃度之差的绝对值。
样例输入
样例1:
10 23 8 10 99 46 2333 46 1 666 555
样例2:
13 110 79 218 69 3721 100 29 135 2 6 13 5188 85
样例输出
样例1:
Outgoing #: 5 Introverted #: 5 Diff = 3611
样例2:
Outgoing #: 7 Introverted #: 6 Diff = 9359
//参考代码1 C++
#include<iostream>
#include<algorithm>
using namespace std;
int sum[100005];
int main(){
int n;
cin>>n;
int s=0;
for(int i=0;i<n;i++){
cin>>sum[i];
s+=sum[i];
}
sort(sum+0,sum+n);
int out=0,in=0;
for(int i=0;i<n/2;i++){
in+=sum[i];
}
for(int i=n-1;i>=n/2;i--){
out+=sum[i];
}
printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d",n%2==0? n/2:n/2+1,n/2,out-in);
return 0;
}//参考代码2 C语言
#include <stdio.h>
#include <stdlib.h>
int main() {
int sum[100005];
int n;
int s = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &sum[i]);
s += sum[i];
}
// Sorting the array
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (sum[j] > sum[j + 1]) {
int temp = sum[j];
sum[j] = sum[j + 1];
sum[j + 1] = temp;
}
}
}
int out = 0, in = 0;
for (int i = 0; i < n / 2; i++) {
in += sum[i];
}
for (int i = n - 1; i >= n / 2; i--) {
out += sum[i];
}
printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d", n % 2 == 0 ? n / 2 : n / 2 + 1, n / 2, out - in);
return 0;
}凑零钱
韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球的硬币付钱,但是绝不找零,当然也不能欠债。韩梅梅手边有104枚来自各个星球的硬币,需要请你帮她盘算一下,是否可能精确凑出要付的款额。
时间限制:7000
内存限制:65535
输入
输入第一行给出两个正整数:N(≤104)是硬币的总个数,M(≤102)是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。
输出
在一行中输出硬币的面值V1≤V2≤…≤Vk,满足条件V1+V2+...+Vk=M。数字间以 1 个空格分隔,行首尾不得有多余空格。若解不唯一,则输出最小序列。若无解,则输出 No Solution。
注:我们说序列{ A[1], A[2], … }比{ B[1], B[2], … }“小”,是指存在 k ≥ 1 使得 A[i]=B[i] 对所有 i < k 成立,并且 A[k] < B[k]。
样例输入
样例1:
8 9 5 9 8 7 2 3 4 1
样例2:
4 8 7 2 4 3
样例输出
样例1:
1 3 5
样例2:
No Solution
//参考代码1 C++
#include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;
#define inf 0x3f3f3f3f
int n,money,a[20000],dp[20000];
struct node
{
int parent;
int data;
}path[20000];
int main()
{
int i,j;
cin>>n>>money;
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
memset(dp,-inf,sizeof(dp));//初始化为负无穷
for(i=0;i<20000;i++)
path[i].parent=-1;
dp[0]=0;
for(i=0;i<n;i++)
{
for(j=money;j>=a[i];j--)//次数越多,序列越小,所以我们dp求能构成序列的需要的最多的数
{
if(dp[j]<=dp[j-a[i]]+1)
{
dp[j]=dp[j-a[i]]+1;
path[j].parent=j-a[i];//记录路径
path[j].data=a[i];//记录路径元素
}
}
}
if(dp[money]>0)
{
int r[2000],k=0;
int temp=money;
while(temp!=-1)
{
r[k++]=path[temp].data;
temp=path[temp].parent;
}
for(i=k-2;i>0;i--)//输出会多一个0,主要是应为dp[0]=0,输出时单独去掉就可以啦
cout<<r[i]<<" ";
cout<<r[0]<<endl;
}
else
{
cout<<"No Solution"<<endl;
}
}//参考代码2 C语言
#include <stdio.h>
#include <stdlib.h>
#define N 10010
int dp[N], w[N];
int vis[N][N];
void solve() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
for (int i = 1; i <= n; ++i)
for (int j = m; j >= w[i]; --j)
if (dp[j] <= dp[j - w[i]] + w[i]) {
vis[i][j] = 1;
dp[j] = dp[j - w[i]] + w[i];
}
if (dp[m] != m) printf("No Solution\n");
else {
int a[N];
int v = m, idx = n, count = 0;
while (v > 0) {
if (vis[idx][v]) {
a[count++] = w[idx];
v -= w[idx];
}
idx--;
}
for (int i = 0; i < count; ++i) {
printf("%d%s", a[i], (i == count - 1) ? "" : " ");
}
}
}
int main() {
solve();
return 0;
}拼题A打卡奖励
拼题 A 的教超搞打卡活动,指定了 N 张打卡卷,第 i 张打卡卷需要 mi 分钟做完,完成后可获得 ci 枚奖励的金币。活动规定每张打卡卷最多只能做一次。活动总时长为 M 分钟。请你算出最多可以赢得多少枚金币?
时间限制:7000
内存限制:524288
输入
输入首先在第一行中给出两个正整数 N(≤ 103) 和 M(≤ 365×24×60),分别对应打卡卷的数量和以“分钟”为单位的活动总时长(不超过一年)。随后一行给出 N 张打卡卷要花费的时间 mi(≤ 600),最后一行给出 N 张打卡卷对应的奖励金币数量 ci(≤ 30)。上述均为正整数,一行内的数字以空格分隔。
输出
在一行中输出最多可以赢得的金币数量。
样例输入
5 110 70 10 20 50 60 28 1 6 18 22
样例输出
40
提示
样例解释: 选择最后两张卷子,可以在 50+60=110 分钟内获得 18+22=40 枚金币。
//参考代码1 C++
#include <iostream>
using namespace std;
const int N = 1e3 + 10, M = 365 * 24 * 60 + 10;
int n, m;
int v[N], w[N];
int dp[M];
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
cin >> n >> m;
cin >> v[0];
int yuanzi = v[0];
for (int i = 1; i < n; i ++ ) {
cin >> v[i];
yuanzi = gcd(v[i], yuanzi);
}
for (int i = 0; i < n; i ++ ) cin >> w[i];
for (int i = 0; i < n; i ++ ) {
int cnt = 0;
for (int j = m; j >= v[i]; j -= yuanzi ) {
if (dp[j - v[i]] + w[i] > dp[j]) dp[j] = dp[j - v[i]] + w[i];
else cnt ++;
if (cnt == 10) break;
}
}
cout << dp[m] << endl;
}//参考代码2 C语言
#include <stdio.h>
#define N 1004
#define INF 0x3f3f3f3f
int n, m;
int w[N], v[N];
int dp[30005];
int mv = 0;
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &w[i]);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &v[i]);
mv += v[i];
}
for (int j = 0; j <= mv; ++j) {
dp[j] = INF;
}
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = mv; j >= 0; --j) {
if (j >= v[i]) {
dp[j] = min(dp[j - v[i]] + w[i], dp[j]);
} else {
dp[j] = dp[j];
}
}
}
for (int j = mv; j >= 0; j--) {
if (dp[j] <= m) {
printf("%d", j);
break;
}
}
return 0;
}有几个PAT
字符串 APPAPT 中包含了两个单词 PAT,其中第一个 PAT 是第 2 位(P),第 4 位(A),第 6 位(T);第二个 PAT 是第 3 位(P),第 4 位(A),第 6 位(T)。
现给定字符串,问一共可以形成多少个 PAT?
时间限制:1000
内存限制:262144
输入
输入只有一行,包含一个字符串,长度不超过105,只包含 P、A、T 三种字母。
输出
在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大,只输出对 1000000007 取余数的结果。
样例输入
APPAPT
样例输出
2
#include<iostream>
#include<string>
using namespace std;
int main()
{
long long sum = 0;
string list;
getline(cin, list);
for (int i = 0,p=0,a=0; i < list.size(); ++i)
{
if (list[i] == 'P')
{
++p;
}
if (list[i] == 'A')
{
a += p;
}
if (list[i] == 'T')
{
sum += a;
}
}
sum %= 1000000007;
cout << sum << endl;
system("pause");
return 0;
}彩带
织女要织一条自己最爱的彩带,方法是从一条现成的彩带上按照她喜欢的颜色顺序保留她最爱的几种颜色,裁掉不要的部分,把留下的缝制在一起,就制成了她最喜欢的彩带。
一般肉眼能分辨的颜色不超过 200 种,所以织女的彩带颜色是有限的。但原始的彩带可是非常长,并且织女想最后形成的彩带也尽可能长,所以她需要你的帮助来得到一个最佳的结果。
注意到解可能是不唯一的,但你只需要告诉她结果的长度即可。例如,给定原始的彩带为 { 2 2 4 1 5 5 6 3 1 1 5 6 },其中数字代表颜色的编号。如果织女喜欢的颜色和顺序是 { 2 3 1 5 6 },则她可以得到 4 个不同的最优解:{ 2 2 1 1 1 5 6 }、{ 2 2 1 5 5 5 6 }、{ 2 2 1 5 5 6 6 } 和 { 2 2 3 1 1 5 6 },长度都是 7。
时间限制:1000
内存限制:262144
输入
输入第一行给出一个正整数 N(≤ 200),为颜色种类的数量(即颜色从 1 到 N 编号)。下一行先给出一个正整数 M(≤ 200),随后是织女喜欢的 M个颜色,按她喜欢的顺序给出。第三行也是先给出一个正整数 L(≤ 104),即原始彩带的长度,随后是 L 个颜色值。一行中的所有数字以空格分隔。
输出
只需要输出织女最喜欢的彩带的最大长度值。
样例输入
6 5 2 3 1 5 6 12 2 2 4 1 5 5 6 3 1 1 5 6
样例输出
7
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int N, M, L;
cin >> N; // 颜色总数,此处可忽略
// 读取织女喜欢的颜色序列
cin >> M;
vector<int> favorite(M);
for (int i = 0; i < M; ++i) {
cin >> favorite[i];
}
// 建立颜色到位置的映射,记录每个颜色最后出现的位置
unordered_map<int, int> colorToPos;
for (int i = 0; i < M; ++i) {
colorToPos[favorite[i]] = i + 1; // 位置从1开始
}
// 读取原始彩带并转换为有效的位置列表
cin >> L;
vector<int> positions;
for (int i = 0; i < L; ++i) {
int color;
cin >> color;
if (colorToPos.count(color)) {
positions.push_back(colorToPos[color]);
}
}
// 动态规划处理
vector<int> currentMax(M + 1, 0); // currentMax[i]表示以位置i结尾的最长子序列长度
vector<int> prefixMax(M + 1, 0); // prefixMax[i]表示前i个位置的最大长度
for (int p : positions) {
int newLen = prefixMax[p] + 1;
if (newLen > currentMax[p]) {
currentMax[p] = newLen;
// 更新prefixMax数组
for (int i = 1; i <= M; ++i) {
if (i == 1) {
prefixMax[i] = currentMax[i];
} else {
prefixMax[i] = max(prefixMax[i - 1], currentMax[i]);
}
}
}
}
cout << prefixMax[M] << endl;
return 0;
}方法思路:
预处理织女喜欢的颜色序列:建立一个颜色到位置的映射,记录每个颜色在织女喜欢的序列中最后出现的位置。
过滤原始彩带:将原始彩带中的颜色转换为对应的位置,过滤掉不在织女喜欢的颜色序列中的颜色。
动态规划:维护两个数组,current_max 和 prefix_max。current_max 数组记录以每个位置结尾的最长子序列长度,prefix_max 数组记录前缀最大值。遍历处理后的位置列表,更新这两个数组,最终得到最长子序列的长度。
四方定理
题目描述
给定一个自然数 n,请输出 n 的所有四平方拆分方案。
输入
单个整数:表示 n。
输出
若干行:每行四个由小到大排列的自然数,表示一种拆分方案。
如果有多种方案,先输出首项较小的方案,对于首项相同的方案,先输出第二项较小的方案,其他情况以此类推。
数据范围:
0≤n≤50,000。
输入样例1
25
输出样例1
0 0 0 5 0 0 3 4 1 2 2 4
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
for(int a=0; a*a<=n; a++) { //使用三重循环避免超时
for(int b=a; a*a+b*b<=n; b++) {
for(int c=b; a*a+b*b+c*c<=n; c++) {
int left=n-a*a-b*b-c*c; //剩余数
int d=sqrt(left);
if(d*d==left && d>=c) //判断d是整数即可
cout << a << " " << b << " " << c << " " << d << endl;
}
}
}
return 0;
}缺失的档案
题目描述
你有一套连续编号的绝密档案,共 n+1 份。它们被整齐地归档在档案柜中。然而,一场意外之后,你发现其中一份档案不翼而飞。
现在,你手上是剩下的 n 份档案的编号 a1, a2, …, an 。请你找出那份丢失的档案编号。
档案的编号是连续的,因此丢失的那一份是唯一确定的,即丢失的肯定不是第一份或最后一份。
输入
第一行:一个整数 n。
第二行:n 个整数 a1, a2, …, an,用空格隔开。
输出
一个整数,表示丢失的贴纸编号。
数据范围
2≤n≤100,1≤ai≤1000,输入均为整数,丢失的整数唯一确定。
输入样例1
3 5 3 2
输出样例1
4
输入样例2
4 111 115 112 114
输出样例2
113
#include <bits/stdc++.h>
using namespace std;
int a[100] = {0};
int main() {
int n;
cin >> n;
for(int i=0; i<n; i++) {
cin >> a[i];
}
sort(a, a+n); //排序
for(int i=1; i<n; i++) {
if(a[i]-a[i-1]!=1) {
cout << a[i] - 1;
break;
}
}
return 0;
}几何计数
题目描述
你在坐标纸上标记了 n 个互不相同的点。
现在你想知道:从这些点中任选三个,有多少种选择方式能构成一个真正的三角形?
所谓真正的三角形,是指三个顶点不共线,即面积大于零的三角形。请计算这个数目。
输入
第一行,一个整数 n,表示点的数量。
接下来 n 行,每行包含两个整数 xi 和 yi ,表示第 i 个点的坐标。
输出
输出一个整数,表示能够构成三角形的三点组合的数量。
数据范围
3≤N≤300,-10^9≤Xi、Yi≤10^9,所有点的坐标互不相同。
输入样例1
3 0 0 2 0 0 -3
输出样例1
1
输入样例2
20 224 433 987654321 987654321 2 0 6 4 314159265 358979323 0 0 -123456789 123456789 -1000000000 1000000000 124 233 9 -6 -4 0 9 5 -7 3 333333333 -333333333 -9 -1 7 -10 -1 5 324 633 1000000000 -1000000000 20 0
输出样例2
1124
#include <bits/stdc++.h>
using namespace std;
int x[300] = {0}, y[300] = {0};
int main() {
int n, cnt = 0;
cin >> n;
for(int i=0; i<n; i++) {
cin >> x[i] >> y[i];
}
//枚举所有情况
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
for(int k=j+1; k<n; k++) {
// (x2-x1)(y3-y1)-(x3-x1)(y2-y1)不为0
long long s=(x[j]-x[i])*(y[k]-y[i])-(x[k]-x[i])*(y[j]-y[i]);
if(s!=0)
cnt++;
}
}
}
cout << cnt;
return 0;
}最佳操作数
题目描述
给定一个数字 x,再给定一个等差数列。请寻找这个等差数列距离 x 最近的数字,并输出这个最小距离。
等差数列的第一项叫做首项,用数字 a 表示,接下来每一项都比前一项多 d,d 称之为公差,数列的项数记为 n。
输入
输入四个整数分别表示 x、a、d、n。
输出
输出一个整数表示最少的操作次数。
数据范围
-10^18≤x、a≤10^18,-10^6≤d≤10^6,1≤n≤10^12。
输入样例1
3 1 3 3
输出样例1
1
输入样例2
-1000000000000000000 1 3 3
输出样例2
1000000000000000001
#include <bits/stdc++.h>
using namespace std;
int main() {
long long x, a, d, n;
cin >> x >> a >> d >> n;
if(d==0) { //公差为0
cout << abs(x-a);
} else {
long long L=a; //左边界
long long R=a+(n-1)*d; //右边界
if(d < 0)
swap(L, R);
if(x <= L) {
cout << abs(L-x);
} else if(x>=R) {
cout << abs(R-x);
} else {
long long k = (x - a) / d; //最接近的项
//比较邻近的第k-1项,k项和k+1项
long long minDelta=abs(a+k*d-x);
if(k-1>=0)
minDelta=min(minDelta, abs(a+(k-1)*d-x));
if(k+1<n)
minDelta=min(minDelta, abs(a+(k+1)*d-x));
cout << minDelta;
}
}
return 0;
}