C/C++编程四级 题库
怪盗基德的滑翔翼
怪盗基德是一个充满传奇色彩的怪盗,专门以珠宝为目标的超级盗窃犯。而他最为突出的地方,就是他每次都能逃脱中村警部的重重围堵,而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。
有一天,怪盗基德像往常一样偷走了一颗珍贵的钻石,不料却被柯南小朋友识破了伪装,而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已,怪盗基德只能操作受损的滑翔翼逃脱。
假设城市中一共有N幢建筑排成一条线,每幢建筑的高度各不相同。初始时,怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑,但是不能中途改变方向(因为中森警部会在后面追击)。因为滑翔翼动力装置受损,他只能往下滑行(即:只能从较高的建筑滑翔到较低的建筑)。他希望尽可能多地经过不同建筑的顶部,这样可以减缓下降时的冲击力,减少受伤的可能性。请问,他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)?
时间限制:1000
内存限制:65536
输入
输入数据第一行是一个整数K(K < 100),代表有K组测试数据。 每组测试数据包含两行:第一行是一个整数N(N < 100),代表有N幢建筑。第二行包含N个不同的整数,每一个对应一幢建筑的高度h(0 < h < 10000),按照建筑的排列顺序给出。
输出
对于每一组测试数据,输出一行,包含一个整数,代表怪盗基德最多可以经过的建筑数量。
样例输入
3 8 300 207 155 299 298 170 158 65 8 65 158 170 298 299 155 207 300 10 2 1 3 4 5 6 7 8 9 10
样例输出
6 6 9
//解法1
#include<bits/stdc++.h>
using namespace std;
#define N 105
int a[N], dpu[N], dpd[N];
int main()
{
int k, n, mxu, mxd;
cin >> k;
while(k--)
{
mxu = mxd = 0;
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> a[i];
for(int i = 1; i <= n; ++i)//求最长上升子序列
{
dpu[i] = 1;
for(int j = 1; j < i; ++j)
if(a[i] > a[j])
dpu[i] = max(dpu[i], dpu[j]+1);
mxu = max(mxu, dpu[i]);
}
for(int i = 1; i <= n; ++i)//求最长下降子序列
{
dpd[i] = 1;
for(int j = 1; j < i; ++j)
if(a[i] < a[j])
dpd[i] = max(dpd[i], dpd[j]+1);
mxd = max(mxd, dpd[i]);
}
cout << max(mxu, mxd) << endl;
}
return 0;
}//解法2
#include<bits/stdc++.h>
using namespace std;
#define N 105
int a[N], dpu[N], dpd[N];
int main()
{
int k, n, mx;
cin >> k;
while(k--)
{
mx = 0;
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> a[i];
for(int i = 1; i <= n; ++i)//求最长上升子序列
{
dpu[i] = dpd[i] = 1;
for(int j = 1; j < i; ++j)
{
if(a[i] > a[j])
dpu[i] = max(dpu[i], dpu[j]+1);
if(a[i] < a[j])
dpd[i] = max(dpd[i], dpd[j]+1);
}
mx = max(max(dpd[i], dpu[i]), mx);
}
cout << mx << endl;
}
return 0;
}//解法3
#include <bits/stdc++.h>
using namespace std;
int k, n
int a[105][3], ans;
int main()
{
cin >> k; // 从标准输入读取一个整数 k
while (k--) // 循环执行 k 次
{
cin >> n; // 从标准输入读取一个整数 n
memset(a, 0, sizeof(a)); // 将数组 a 的所有元素置为 0
ans = 0; // 将变量 ans 置为 0
// 动态规划计算最长上升子序列
for (int i = 1; i <= n; i++) // 从第 1 个位置到第 n 个位置遍历
{
cin >> a[i][0]; // 从标准输入读取一个整数到数组 a 中的第 i 行第 0 列
a[i][1] = 1; // 将数组 a 中的第 i 行第 1 列置为 1
for (int j = 1; j <= i - 1; j++) // 从第 1 个位置到第 i-1 个位置遍历
if (a[j][0] > a[i][0] && a[j][1] + 1 > a[i][1]) // 如果数组 a 中第 j 行第 0 列的元素大于数组 a 中第 i 行第 0 列的元素,并且数组 a 中第 j 行第 1 列的元素加 1 大于数组 a 中第 i 行第 1 列的元素
a[i][1] = a[j][1] + 1; // 将数组 a 中第 i 行第 1 列置为数组 a 中第 j 行第 1 列的元素加 1
ans = max(ans, a[i][1]); // 更新变量 ans,取 ans 和数组 a 中第 i 行第 1 列的元素的较大值
}
// 动态规划计算最长下降子序列
for (int i = n; i >= 1; i--) // 从第 n 个位置到第 1 个位置遍历
{
a[i][2] = 1; // 将数组 a 中的第 i 行第 2 列置为 1
for (int j = n; j >= i + 1; j--) // 从第 n 个位置到第 i+1 个位置遍历
if (a[j][0] > a[i][0] && a[i][2] < a[j][2] + 1) // 如果数组 a 中第 j 行第 0 列的元素大于数组 a 中第 i 行第 0 列的元素,并且数组 a 中第 i 行第 2 列的元素小于数组 a 中第 j 行第 2 列的元素加 1
a[i][2] = a[j][2] + 1; // 将数组 a 中第 i 行第 2 列置为数组 a 中第 j 行第 2 列的元素加 1
ans = max(ans, a[i][2]); // 更新变量 ans,取 ans 和数组 a 中第 i 行第 2 列的元素的较大值
}
cout << ans << endl; // 输出变量 ans 到标准输出
}
return 0; // 返回 0,表示程序正常结束
}数字组合
有n个正整数,找出其中和为t(t也是正整数)的可能的组合方式。如: n=5,5个数分别为1,2,3,4,5,t=5; 那么可能的组合有5=1+4和5=2+3和5=5三种组合方式。
时间限制:1000
内存限制:65536
输入
输入的第一行是两个正整数n和t,用空格隔开,其中1<=n<=20,表示正整数的个数,t为要求的和(1<=t<=1000) 接下来的一行是n个正整数,用空格隔开。
输出
和为t的不同的组合方式的数目。
样例输入
5 5 1 2 3 4 5
样例输出
3
//解法1
#include <bits/stdc++.h>
using namespace std;
int a[25],n,t,ans;
void dfs(int i,int sum){
if(i==n){
if(t==sum){
ans++;
}
return;
}
i++;
dfs(i,sum+a[i]);
dfs(i,sum);
}
int main(){
cin>>n>>t;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dfs(0,0);
cout<<ans;
return 0;
}//解法2 背包问题
#include <bits/stdc++.h>
using namespace std;
int n,t;
int a[22],f[1005];
int main()
{
cin >> n >> t; // 从标准输入读取两个整数 n 和 t
for (int i = 1; i <= n; i++)
cin >> a[i]; // 从标准输入读取 n 个整数,并存储到数组 a 中
f[0] = 1; // 将数组 的第 0 个元素置为 1,表示容积为 0 时的方式数量为 1
for (int i = 1; i <= n; i++) {
for (int j = t; j >= a[i]; j--)
f[j] += f[j - a[i]]; // 动态规划转移方程,累加之前容积 j 和当前物品体积之差的容积的方式数量
}
cout << f[t]; // 输出数组 f 中第 t 个元素,表示容积为 t 时的方式数量
return 0;
}//解法3 递归求解
#include <bits/stdc++.h>
using namespace std;
int n, t;
int a[22];
int f(int sum, int p) {
if (sum == t)
return 1; // 如果当前总和等于目标值 t,则返回1 表示找到一种组合方式。
if (sum > t || p > n)
return 0; // 如果当前总和大于目标值 t 或已经遍历完所有物品,则返回 0 表示没有合适的组合方式。
// 递归调用 f 函数,分别尝试选取下一个物品和不选取下一个物品两种情况,并累加它们的结果
return f(sum + a[p], p + 1) + f(sum, p + 1);
}
int main() {
cin >> n >> t; // 从标准输入读取两个整数 n 和 t
for (int i = 1; i <= n; i++)
cin >> a[i]; // 从标准输入读取 n 个整数,并存储到数组 a 中
cout <<f(0, 1); // 调用函数 f,初始总和为 0,从第一个物品开始选取
return 0;
}带通配符的字符串匹配
通配符是一类键盘字符,当我们不知道真正字符或者不想键入完整名字时,常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号(*)等,其中,“?”可以代替一个字符,而“*”可以代替零个或多个字符。
你的任务是,给出一个带有通配符的字符串和一个不带通配符的字符串,判断他们是否能够匹配。
例如,1?456 可以匹配 12456、13456、1a456,但是却不能够匹配23456、1aa456;
2*77?8可以匹配 24457798、237708、27798。
时间限制:1000
内存限制:65536
输入
输入有两行,每行为一个不超过20个字符的字符串,第一行带通配符,第二行不带通配符
输出
如果两者可以匹配,就输出“matched”,否则输出“not matched”
样例输入
1*456? 11111114567
样例输出
matched
//解法1
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
int f[3005][3005]={0},q[3005]={0},prt[3005][3005]={0};
string st1,st2;
int gcd(int a,int b)
{ if(b==0)return a;
return gcd(b,a%b);}
void Get(int x,int y)
{ if(x==0&&y==0)return;
int lx=x-1,ly=prt[x][y];
if(st1[x]=='*'&&y!=ly){q[++q[0]]=y-ly;}
Get(lx,ly);}
int main()
{ cin>>st1>>st2;
int i,j,k,bj,div,ans=0,len1=st1.length(),len2=st2.length();
st1=' '+st1;st2=' '+st2;
f[0][0]=1;
for(i=1;i<=len1;i++)
for(j=0;j<=len2;j++)
{if(st1[i]=='?'||st1[i]==st2[j])
{f[i][j]=f[i-1][j-1];
if(f[i][j])prt[i][j]=j-1;}
else if(st1[i]=='*')
{for(k=j,bj=0;k>=0;k--)
if(f[i-1][k]){bj=1;break;}
if(bj){f[i][j]=1;prt[i][j]=k;}}}
if(f[len1][len2])
{cout<<"matched\n";}
else cout<<"not matched";
return 0;}//解法2 动态规划
#include <bits/stdc++.h>
using namespace std;
string s1,s2;
bool dp[30][30];//dp[i][j] 表示模式串s1的前i个字符和字符串s2的前j个字符是否匹配
int main() {
cin>>s1>>s2;
int l1=s1.size();
int l2=s2.size();
dp[0][0]=true;//将dp[0][0]置为 true,表示空字符串匹配
for(int i=1;i<=l1;i++)
for(int j=0;j<=l2;j++){
//如果s1[i-1]是*,则在dp[i-1][k]中寻找最后一个为true的位置(其中k>=j),
//如果找到,则将dp[i][j]置为true。
if(s1[i-1]=='*'){
for(int k=j;k>=0;k--){
if(dp[i-1][k]){
dp[i][j]=true;
break;
}
}
}else {
//如果当前字符可以匹配(即s1[i-1]==s2[j-1]或者s1[i-1]=='?')
//且前面的子问题匹配成功(dp[i-1][j-1] 为 true),则将dp[i][j]置为true。
if((s1[i-1]==s2[j-1]||s1[i-1]=='?') && (j && dp[i-1][j-1]))
dp[i][j]=true;
}
}
if(dp[l1][l2]) cout<<"matched";
else cout<<"not matched";
return 0;
}股票买卖
最近越来越多的人都投身股市,阿福也有点心动了。谨记着“股市有风险,入市需谨慎”,阿福决定先来研究一下简化版的股票买卖问题。
假设阿福已经准确预测出了某只股票在未来 N 天的价格,他希望买卖两次,使得获得的利润最高。为了计算简单起见,利润的计算方式为卖出的价格减去买入的价格。
同一天可以进行多次买卖。但是在第一次买入之后,必须要先卖出,然后才可以第二次买入。
现在,阿福想知道他最多可以获得多少利润。
时间限制:1000
内存限制:65536
输入
输入的第一行是一个整数 T (T <= 50) ,表示一共有 T 组数据。 接下来的每组数据,第一行是一个整数 N (1 <= N <= 100, 000) ,表示一共有 N 天。第二行是 N 个被空格分开的整数,表示每天该股票的价格。该股票每天的价格的绝对值均不会超过 1,000,000 。
输出
对于每组数据,输出一行。该行包含一个整数,表示阿福能够获得的最大的利润。
样例输入
3 7 5 14 -2 4 9 3 17 6 6 8 7 4 1 -2 4 18 9 5 2
样例输出
28 2 0
提示
对于第一组样例,阿福可以第 1 次在第 1 天买入(价格为 5 ),然后在第 2 天卖出(价格为 14 )。第 2 次在第 3 天买入(价格为 -2 ),然后在第 7 天卖出(价格为 17 )。一共获得的利润是 (14 - 5) + (17 - (-2)) = 28 对于第二组样例,阿福可以第 1 次在第 1 天买入(价格为 6 ),然后在第 2 天卖出(价格为 8 )。第 2 次仍然在第 2 天买入,然后在第 2 天卖出。一共获得的利润是 8 - 6 = 2 对于第三组样例,由于价格一直在下跌,阿福可以随便选择一天买入之后迅速卖出。获得的最大利润为 0
//解法1:
//基本解法
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define INF 0x3f3f3f3f
int t, n, ans, a[N], de[N], db[N], dpe[N], dpb[N];
int main()
{
int mn, mx;
scanf("%d", &t);
while(t--)
{
memset(dpe, 0, sizeof(dpe));
memset(dpb, 0, sizeof(dpb));
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
mn = a[1];
for(int i = 1; i <= n; ++i)
{
mn = min(mn, a[i]);
de[i] = a[i] - mn;//以a[i]为结尾的所有区间中,区间差值的最大的区间的区间差值。
dpe[i] = max(dpe[i-1], de[i]);//第1到第i个数字构成的所有区间中,区间差值最大的区间的区间差值。
}
mx = a[n];
for(int i = n; i >= 1; --i)
{
mx = max(mx, a[i]);
db[i] = mx - a[i];//以a[i]为起始的所有区间中,区间差值的最大的区间的区间差值。
dpb[i] = max(dpb[i+1], db[i]);//第i到第n个数字构成的所有区间中,区间差值最大的区间的区间差值。
}
ans = -INF;//原序列中不相交的两个区间的区间差值加和的最大值
for(int i = 1; i < n; ++i)//枚举分割点
ans = max(ans, dpe[i]+dpb[i+1]);
printf("%d\n", ans);
}
return 0;
}//优化:变递推为迭代
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define INF 0x3f3f3f3f
int t, n, ans, mn, mx, a[N], dpe[N], dpb[N];
int main()
{
scanf("%d", &t);
while(t--)
{
memset(dpe, 0, sizeof(dpe));
memset(dpb, 0, sizeof(dpb));
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
mn = a[1];
for(int i = 1; i <= n; ++i)
{
mn = min(mn, a[i]);
dpe[i] = max(dpe[i-1], a[i] - mn);//第1到第i个数字构成的所有区间中,区间差值最大的区间的区间差值。
}
mx = a[n];
for(int i = n; i >= 1; --i)
{
mx = max(mx, a[i]);
dpb[i] = max(dpb[i+1], mx - a[i]);//第i到第n个数字构成的所有区间中,区间差值最大的区间的区间差值。
}
ans = -INF;//原序列中不相交的两个区间的区间差值加和的最大值
for(int i = 1; i < n; ++i)//枚举分割点
ans = max(ans, dpe[i]+dpb[i+1]);
printf("%d\n", ans);
}
return 0;
}//解法2:
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define INF 0x3f3f3f3f
int t, n, mn, mx, mxde, ans, a[N], de[N], db[N];
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
mn = a[1];
for(int i = 1; i <= n; ++i)
{
mn = min(mn, a[i]);
de[i] = a[i] - mn;//以a[i]为结尾的所有区间中,区间差值的最大的区间的区间差值。
}
mx = a[n];
for(int i = n; i >= 1; --i)
{
mx = max(mx, a[i]);
db[i] = mx - a[i];//以a[i]为起始的所有区间中,区间差值的最大的区间的区间差值。
}
mxde = ans = -INF;//ans:原序列中不相交的两个区间的区间差值加和的最大值
for(int i = 1; i < n; ++i)//枚举分割点
{
mxde = max(mxde, de[i]);//mxde为第1到第i个数字构成的所有区间中,区间差值最大的区间的区间差值。
ans = max(ans, mxde + db[i+1]);
}
printf("%d\n", ans);
}
return 0;
}//解法3:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 100001
#define MOD 100001
#define E 1e-12
using namespace std;
int a[N],f1[N],f2[N];
int main()
{
int t,ans;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int minn=INF,maxx=-INF;
f1[0]=0;
f2[n+1]=0;
for(int i=1;i<=n;i++)
{
minn=min(minn,a[i]);
f1[i]=max(f1[i-1],a[i]-minn);
}
for(int i=n;i>=1;i--)
{
maxx=max(maxx,a[i]);
f2[i]=max(f2[n+1],maxx-a[i]);
}
int ans=-INF;
for(int i=1;i<=n;i++)
ans=max(ans,f1[i]+f2[i]);
printf("%d\n",ans);
}
return 0;
}//解法4 动态规划
#include <bits/stdc++.h>
using namespace std;
int t,n,w[100005],dp[1000005][2];
int main() {
cin>>t;//测试案例的数量
int k=2;//最大买卖次数
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
memset(dp,0,sizeof(dp));//将f数组的所有元素置为0
for(int i=0;i<=k;i++) dp[i][1]=-1e6;//将f[j][1]列中的所有元素置为负无穷大
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++){
//第j次购入股票
dp[j][0]=max(dp[j][0],dp[j][1]+w[i]);
//第j次抛售股票
dp[j][1]=max(dp[j][1],dp[j-1][0]-w[i]);
}
cout<<dp[k][0]<<endl;
}
return 0;
}酒鬼
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个放核物质的坑,坑排列在一条直线上。如果连续M个坑中放入核物质,则会发生爆炸,于是,在某些坑中可能不放核物质。
任务:对于给定的N和M,求不发生爆炸的放置核物质的方案总数
时间限制:6000
内存限制:131072
输入
只一行,两个正整数N,M( 1 < N < 50,2 ≤ M ≤ 5 )
输出
一个正整数S,表示方案总数。
样例输入
4 3
样例输出
13
//样例代码 动态规划
#include <bits/stdc++.h>
using namespace std;
int n,m;
long long dp[55][7];//前i个坑现在已经连续埋了j个的方案
int main()
{
cin>>n>>m;
dp[1][1]=1;//第1个放
dp[1][0]=1;//第1个不放
for(int i=2;i<=n;i++){
for(int j=0;j<m;j++){
if(j==0){//第j个不放
for(int k=0;k<m;k++)//0~m-1的位置都可放可不放
dp[i][j]+=dp[i-1][k];
}
else //第j个放
dp[i][j]+=dp[i-1][j-1];
}
}
long long ans=0;
for(int i=0;i<m;i++)
ans+=dp[n][i];
cout<<ans;
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;
}那就别担心了
下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题,其实都不用担心。

博主将这种逻辑推演称为“逻辑自洽”,即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题(开玩笑的,千万别以为这是真正的逻辑自洽的定义……)。现给定一个更为复杂的逻辑推理图,本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的,以及存在多少种不同的推理路径。例如上图,从“你遇到难题了吗?”到“那就别担心了”就是一种“逻辑自洽”的推理,一共有 3 条不同的推理路径。
时间限制:7000
内存限制:65536
输入
输入首先在一行中给出两个正整数 N(1 < N ≤ 500)和 M,分别为命题个数和推理个数。这里我们假设命题从 1 到 N 编号。 接下来 M 行,每行给出一对命题之间的推理关系,即两个命题的编号 S1 S2,表示可以从 S1 推出 S2。题目保证任意两命题之间只存在最多一种推理关系,且任一命题不能循环自证(即从该命题出发推出该命题自己)。 最后一行给出待检验的两个命题的编号 A B。
输出
在一行中首先输出从 A 到 B 有多少种不同的推理路径,然后输出 Yes 如果推理是“逻辑自洽”的,或 No 如果不是。 题目保证输出数据不超过 109。
样例输入
样例1:
7 8 7 6 7 4 6 5 4 1 5 2 5 3 2 1 3 1 7 1
样例2:
7 8 7 6 7 4 6 5 4 1 5 2 5 3 6 1 3 1 7 1
样例输出
样例1:
3 Yes
样例2:
3 No
//参考代码1 C++ #includeusing namespace std; const int N = 510; int n, m; int way[N][N]; int cnt[N], st, en; bool st1[N], flag = false; void dfs(int u) { if (u == en) { cnt[en] ++; return; } if (way[u][0] == 0) flag = true; for (int i = 1; i <= way[u][0]; i ++ ) { int j = way[u][i]; if (!st1[j]) { dfs(j); st1[j] = true; } cnt[u] += cnt[j]; } } int main() { cin >> n >> m; for (int i = 0; i < m; i ++ ) { int a, b; cin >> a >> b; way[a][0] ++; way[a][way[a][0]] = b; } cin >> st >> en; dfs(st); if (flag) cout << cnt[st] << " No"; else cout << cnt[st] << " Yes"; }
//参考代码2 C语言 #include#include #define MAX_NODES 502 int N, M, S1, S2, A, B, consistency, laneNum[MAX_NODES]; int Edge[MAX_NODES][MAX_NODES]; int dfs(int index) { if (laneNum[index] != 0) return laneNum[index]; for (int i = 0; i < MAX_NODES; i++) { if (Edge[index][i] != 0) { if (laneNum[i] == 0) dfs(i); laneNum[index] += laneNum[i]; } } if (laneNum[index] == 0) consistency = 1; return laneNum[index]; } int main() { scanf("%d %d", &N, &M); for (int i = 0; i < M; ++i) { scanf("%d %d", &S1, &S2); Edge[S1][S2] = 1; } scanf("%d %d", &A, &B); laneNum[B] = 1; dfs(A); printf("%d %s", laneNum[A], (consistency ? "No" : "Yes")); 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;
}