信息学奥赛-入门级 题库
将第7行的“gcd(b,a%b)”改为“gcd(a,a%b)”后,程序可能出现的问题是()。
319和377的最大公约数是?
使用辗转相除法计算最大公约数(319,377)=(319,58)=(58,29)=29
无论是TCP/IP模型还是OSI模型,都可以视为网络的分层模型,每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”,以下最恰当的是 ( )。




319和377的最大公约数是?
使用辗转相除法计算最大公约数(319,377)=(319,58)=(58,29)=29
一台计算机如果要利用电话线上网,就必须配置能够对数字信号和模拟信号进行互相转换的设备,这种设备是( )
网卡
网关
在24*24 点阵的字库中,汉字“一 ”与“编”的字模占用字节数分别是( )。
龙虎斗
【问题描述】
轩轩和凯凯正在玩一款叫《龙虎斗》的游戏,游戏的棋盘是一条线段,线段上有 n个兵营(自左至右编号 1 ~ n),相邻编号的兵营之间相隔 1 厘米,即棋盘为长度为n − 1 厘米的线段。i 号兵营里有 ci 位工兵。
下面图 1 为 n = 6 的示例:

轩轩在左侧,代表“龙”;凯凯在右侧,代表“虎”。 他们以 m 号兵营作为分界,靠左的工兵属于龙势力,靠右的工兵属于虎势力,而第 m 号兵营中的工兵很纠结,他们不属于任何一方。
一个兵营的气势为:该兵营中的工兵数 × 该兵营到 m 号兵营的距离;参与游戏一方的势力定义为:属于这一方所有兵营的气势之和。
下面图 2 为 n = 6, m = 4 的示例,其中红色为龙方,黄色为虎方:

游戏过程中,某一刻天降神兵,共有 s1 位工兵突然出现在了 p1 号兵营。作为轩轩和凯凯的朋友,你知道如果龙虎双方气势差距太悬殊,轩轩和凯凯就不愿意继续玩下去了。为了让游戏继续,你需要选择一个兵营 p2,并将你手里的 s2 位工兵全部派往兵营 p2,使得双方气势差距尽可能小。
注意:你手中的工兵落在哪个兵营,就和该兵营中其他工兵有相同的势力归属(如果落在 m 号兵营,则不属于任何势力)。
【输入格式】
输入文件名为 fight.in。
输入文件的第一行包含一个正整数 n,代表兵营的数量。
接下来的一行包含 n 个正整数,相邻两数之间以一个空格分隔,第 i 个正整数代表编号为 i 的兵营中起始时的工兵数量 ci。
接下来的一行包含四个正整数,相邻两数间以一个空格分隔,分别代表 m, p1, s1, s2。
【输出格式】
输出文件名为 fight.out。
输出文件有一行,包含一个正整数,即 p2,表示你选择的兵营编号。如果存在多个编号同时满足最优,取最小的编号。
【输入输出样例 1】

【输入输出样例 1 说明】
见问题描述中的图 2。
双方以 m = 4 号兵营分界,有 s1 = 5 位工兵突然出现在 p1 = 6 号兵营。
龙方的气势为:
2 × (4 − 1) + 3 × (4 − 2) + 2 × (4 − 3) = 14
虎方的气势为:
2 × (5 − 4) + (3 + 5) × (6 − 4) = 18
当你将手中的 s
2 = 2 位工兵派往 p2 = 2 号兵营时,龙方的气势变为:
14 + 2 × (4 − 2) = 18
此时双方气势相等。
【输入输出样例 2】

【输入输出样例 2 说明】
双方以 m = 5 号兵营分界,有 s1 = 1 位工兵突然出现在 p1 = 4 号兵营。
龙方的气势为:
1 × (5 − 1) + 1 × (5 − 2) + 1 × (5 − 3) + (1 + 1) × (5 − 4) = 11
虎方的气势为:
16 × (6 − 5) = 16
当你将手中的 s2 = 1 位工兵派往 p2 = 1 号兵营时,龙方的气势变为:
11 + 1 × (5 − 1) = 15
此时可以使双方气势的差距最小。
【数据规模与约定】
1 < m < n, 1 ≤ p1 ≤ n。
对于 20% 的数据,n = 3, m = 2, ci = 1, s1, s2 ≤ 100。
另有 20% 的数据,n ≤ 10, p1 = m, ci = 1, s1, s2 ≤ 100。
对于 60% 的数据,n ≤ 100, ci = 1, s1, s2 ≤ 100。
对于 80% 的数据,n ≤ 100, ci, s1, s2 ≤ 100。
对于 100% 的数据,n ≤ 105, ci, s1, s2 ≤ 10^9。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, m, p1, p2;
long long a[maxn], s1, s2, sum;
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
cin >> m >> p1 >> s1 >> s2;
a[p1] += s1;
p2 = 1;
for (int i = 1; i <= n; i ++)
sum += ( (long long) (i - m) ) * a[i];
for (int i = 1; i <= n; i ++)
if ( abs(sum + (i-m) * s2) < abs(sum + (p2-m) * s2) ) p2 = i;
cout << p2 << endl;
return 0;
}
摆渡车
【问题描述】
有 n 名同学要乘坐摆渡车从人大附中前往人民大学,第 i 位同学在第 ti 分钟去等车。只有一辆摆渡车在工作,但摆渡车容量可以视为无限大。摆渡车从人大附中出发、把车上的同学送到人民大学、再回到人大附中(去接其他同学),这样往返一趟总共花费 m 分钟(同学上下车时间忽略不计)。摆渡车要将所有同学都送到人民大学。
凯凯很好奇,如果他能任意安排摆渡车出发的时间,那么这些同学的等车时间之和最小为多少呢?
注意:摆渡车回到人大附中后可以即刻出发。
【输入格式】
输入文件名为 bus.in。
第一行包含两个正整数 n,m,以一个空格分开,分别代表等车人数和摆渡车往返一趟的时间。
第二行包含 n 个正整数,相邻两数之间以一个空格分隔,第 i 个非负整数 ti 代表第 i 个同学到达车站的时刻。
【输出格式】
输出文件名为 bus.out。
输出一行,一个整数,表示所有同学等车时间之和的最小值(单位:分钟)。
【输入输出样例 1】

【输入输出样例 1 说明】
同学 1 和同学 4 在第 3 分钟开始等车,等待 0 分钟,在第 3 分钟乘坐摆渡车出发。摆渡车在第 4 分钟回到人大附中。
同学 2 和同学 3 在第 4 分钟开始等车,等待 0 分钟,在第 4 分钟乘坐摆渡车出发。摆渡车在第 5 分钟回到人大附中。
同学 5 在第 5 分钟开始等车,等待 0 分钟,在第 5 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。总等待时间为 0。
【输入输出样例 2】

【输入输出样例 2 说明】
同学 3 在第 1 分钟开始等车,等待 0 分钟,在第 1 分钟乘坐摆渡车出发。摆渡车在第 6 分钟回到人大附中。
同学 4 和同学 5 在第 5 分钟开始等车,等待 1 分钟,在第 6 分钟乘坐摆渡车出发。摆渡车在第 11 分钟回到人大附中。
同学 1 在第 11 分钟开始等车,等待 2 分钟;同学 2 在第 13 分钟开始等车,等待 0 分钟。他/她们在第 13 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。
总等待时间为 4。可以证明,没有总等待时间小于 4 的方案。
【数据规模与约定】

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4000400;
int n, m, t, maxt;
long long f[maxn], cnt[maxn];
int main() {
cin >> n >> m;
for (int i = 0; i < n; i ++) {
cin >> t;
cnt[t] ++;
if (t > maxt) maxt = t;
}
for (int i = 0; i <= maxt + m; i ++) {
long long tmp = 0;
for (int j = 0; j < m && i-j >=0; j ++) {
tmp += cnt[i-j] * ( (long long) j );
}
f[i] = tmp;
if (i >= m) f[i] += f[i-m];
for (int j = m+1; j <= 2*m && i - j >= 0; j ++) {
tmp += cnt[i-j+1] * ( (long long) (j-1) );
if (f[i-j] + tmp <= f[i]) f[i] = f[i-j] + tmp;
}
}
long long ans = f[maxt];
for (int i = 1; i <= m; i ++) {
ans = min(ans, f[maxt+i]);
}
cout << ans << endl;
return 0;
}
对称二叉树
【问题描述】
一棵有点权的有根树如果满足以下条件,则被轩轩称为对称二叉树:
1. 二叉树;
2. 将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。
下图中节点内的数字为权值,节点外的 id表示节点编号。

现在给出一棵二叉树,希望你找出它的一棵子树,该子树为对称二叉树,且节点数最多。请输出这棵子树的节点数。
注意:只有树根的树也是对称二叉树。本题中约定,以节点 T 为子树根的一棵“子树”指的是:节点 T 和它的全部后代节点构成的二叉树。
【输入格式】
输入文件名为 tree.in。
第一行一个正整数 n,表示给定的树的节点的数目,规定节点编号 1~n,其中节点1 是树根。
第二行 n 个正整数,用一个空格分隔,第 i 个正整数 vi 代表节点 i 的权值。接下来 n 行,每行两个正整数 li, ri,分别表示节点 i 的左右孩子的编号。如果不存在左 / 右孩子,则以 −1 表示。两个数之间用一个空格隔开。
【输出格式】
输出文件名为 tree.out。
输出文件共一行,包含一个整数,表示给定的树的最大对称二叉子树的节点数。
【输入输出样例 1】

【输入输出样例 1 说明】

最大的对称二叉子树为以节点 2 为树根的子树,节点数为 1。
【输入输出样例 2】

【输入输出样例 2 说明】

最大的对称二叉子树为以节点 7 为树根的子树,节点数为 3。
【数据规模与约定】
共 25 个测试点。
vi ≤ 1000。
测试点 1~3,n ≤ 10,保证根结点的左子树的所有节点都没有右孩子,根结点的右子树的所有节点都没有左孩子。
测试点 4~8,n ≤ 10。
测试点 9~12,n ≤ 10^5,保证输入是一棵“满二叉树”。
测试点 13~16,n ≤ 10^5,保证输入是一棵“完全二叉树”。
测试点 17~20,n ≤ 10^5,保证输入的树的点权均为 1。
测试点 21~25,n ≤ 10^6。
本题约定:
层次:节点的层次从根开始定义起,根为第一层,根的孩子为第二层。树中任一节点的层次等于其父亲节点的层次加 1。
树的深度:树中节点的最大层次称为树的深度。
满二叉树:设二叉树的深度为 h,且二叉树有 2^h − 1 个节点,这就是满二叉树。

完全二叉树:设二叉树的深度为 h,除第 h 层外,其它各层的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n;
struct node
{
int v;
int l,r;
}tree[maxn];
int sum[maxn]={0};
int count1=0;
int check(int l,int r)//判断二叉树是否对称
{
if(l==r) return 1;
if(tree[l].v==tree[r].v)
{
if(check(tree[l].l,tree[r].r)&&check(tree[l].r,tree[r].l))
return 1;
}
return 0;
}
void yu(int i)//统计结点数量
{
int l=tree[i].l;
int r=tree[i].r;
if(i==-1) return ;
sum[i]=1;
yu(l);yu(r);
sum[i]+=sum[l]+sum[r];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>tree[i].v;
}
for(int i=1;i<=n;i++)
{
cin>>tree[i].l>>tree[i].r;
}
yu(1);
int ans=0;
for(int i=1;i<=n;i++)
{
if(check(tree[i].l,tree[i].r)) ans=max(ans,sum[i]);
}
cout<<ans<<endl;
return 0;
}
图书管理员
【问题描述】
图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个
正整数。
每位借书的读者手中有一个需求码,这个需求码也是一个正整数。如果一本书的图
书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。
小 D 刚刚当上图书馆的管理员,她知道图书馆里所有书的图书编码,她请你帮她写
一个程序,对于每一位读者,求出他所需要的书中图书编码最小的那本书,如果没有他
需要的书,请输出-1。
【输入格式】
输入文件名为 librarian.in。
输入文件的第一行,包含两个正整数 n 和 q,以一个空格分开,分别代表图书馆里
书的数量和读者的数量。
接下来的 n 行,每行包含一个正整数,代表图书馆里某本书的图书编码。
接下来的 q 行,每行包含两个正整数,以一个空格分开,第一个正整数代表图书馆
里读者的需求码的长度,第二个正整数代表读者的需求码。
【输出格式】
输出文件名为 librarian.out。
输出文件有 q 行,每行包含一个整数,如果存在第 i 个读者所需要的书,则在第 i
行输出第 i 个读者所需要的书中图书编码最小的那本书的图书编码,否则输出-1。
【输入输出样例 1】

【输入输出样例 1 说明】
第一位读者需要的书有 2123、1123、23,其中 23 是最小的图书编码。第二位读者需要
的书有 2123、1123,其中 1123 是最小的图书编码。对于第三位,第四位和第五位读者,没
有书的图书编码以他们的需求码结尾,即没有他们需要的书,输出-1。
【数据规模与约定】
对于 20%的数据,1 ≤ n ≤ 2。
另有 20%的数据,q = 1。
另有 20%的数据,所有读者的需求码的长度均为 1。
另有 20%的数据,所有的图书编码按从小到大的顺序给出。
对于 100%的数据,1 ≤ n ≤ 1,000,1 ≤ q ≤ 1,000,所有的图书编码和需求码均
不超过 10,000,000。
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define M 1000
int n,q;
int a[M+5],ans;
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);//从小到大排序
for(int i=1;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
int f=0;
for(int j=1;j<=n;j++)
{
if(a[j]%int(pow(10,x))==y)//取末尾编码
{
f=1;
printf("%d\n",a[j]);
break;
}
}
if(f==0)printf("-1\n");
}
return 0;
}
棋盘
【问题描述】
有一个m × m的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在
要从棋盘的最左上角走到棋盘的最右下角。
任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的),你只能向上、下、
左、右四个方向前进。当你从一个格子走向另一个格子时,如果两个格子的颜色相同,那你
不需要花费金币;如果不同,则你需要花费 1 个金币。
另外,你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个
魔法不能连续使用,而且这个魔法的持续时间很短,也就是说,如果你使用了这个魔法,走
到了这个暂时有颜色的格子上,你就不能继续使用魔法;只有当你离开这个位置,走到一个
本来就有颜色的格子上的时候,你才能继续使用这个魔法,而当你离开了这个位置(施展魔
法使得变为有颜色的格子)时,这个格子恢复为无色。
现在你要从棋盘的最左上角,走到棋盘的最右下角,求花费的最少金币是多少?
【输入格式】
输入文件名为 chess.in。
数据的第一行包含两个正整数 m,n,以一个空格分开,分别代表棋盘的大小,棋盘上
有颜色的格子的数量。
接下来的 n 行,每行三个正整数 x,y,c,分别表示坐标为(x,y)的格子有颜色 c。
其中 c=1 代表黄色,c=0 代表红色。相邻两个数之间用一个空格隔开。棋盘左上角的坐标
为(1, 1),右下角的坐标为(m, m)。
棋盘上其余的格子都是无色。保证棋盘的左上角,也就是(1,1)一定是有颜色的。
【输出格式】
输出文件名为 chess.out。
输出一行,一个整数,表示花费的金币的最小值,如果无法到达,输出-1。
【输入输出样例 1】

【输入输出样例 1 说明】

从(1,1)开始,走到(1,2)不花费金币
从(1,2)向下走到(2,2)花费 1 枚金币
从(2,2)施展魔法,将(2,3)变为黄色,花费 2 枚金币
从(2,2)走到(2,3)不花费金币
从(2,3)走到(3,3)不花费金币
从(3,3)走到(3,4)花费 1 枚金币
从(3,4)走到(4,4)花费 1 枚金币
从(4,4)施展魔法,将(4,5)变为黄色,花费 2 枚金币,
从(4,4)走到(4,5)不花费金币
从(4,5)走到(5,5)花费 1 枚金币
共花费 8 枚金币。
【输入输出样例 2】

【输入输出样例 2 说明】

从(1,1)走到(1,2),不花费金币
从(1,2)走到(2,2),花费 1 金币
施展魔法将(2,3)变为黄色,并从(2,2)走到(2,3)花费 2 金币
从(2,3)走到(3,3)不花费金币
从(3,3)只能施展魔法到达(3,2),(2,3),(3,4),(4,3)
而从以上四点均无法到达(5,5),故无法到达终点,输出-1
【数据规模与约定】
对于 30%的数据,1 ≤ m ≤ 5, 1 ≤ n ≤ 10。
对于 60%的数据,1 ≤ m ≤ 20, 1 ≤ n ≤ 200。
对于 100%的数据,1 ≤ m ≤ 100, 1 ≤ n ≤ 1,000。
#include <iostream>
#include <bits/stdc++.h>
#include<set>
#include<string.h>
#include<algorithm>
using namespace std;
// 1 黄 0 红
int dis[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int n,m;
const int maxn=105;
struct node
{
int x,y,c,v;
};
queue<node>q;
int yy[maxn][maxn],val[maxn][maxn];
int ans=0x7f7f7f7f;
void Init()
{
memset(yy,-1,sizeof(yy));
memset(val,0x7f,sizeof(val));
}
void dfs(int x,int y)
{
node pq;
pq.x=x,pq.y=y,pq.c=yy[x][y],pq.v=0;
val[x][y]=0;
q.push(pq);
while(!q.empty())
{
node now=q.front();
if(now.v>ans)
{
q.pop();
continue;
}
if(now.x==m&&now.y==m)
{
ans=min(ans,now.v);
q.pop();
continue;
}
for(int i=0;i<4;i++)
{
int dx=now.x+dis[i][0],dy=now.y+dis[i][1];
if(dx>0&&dy>0&&dx<=m&&dy<=m)
{
int bc=yy[now.x][now.y],dc=yy[dx][dy],mv=val[dx][dy],dv;
if(bc>=0&&dc>=0)
{
dv=now.v+(bc==dc?0:1);
if(mv>dv)
{
q.push((node){dx,dy,dc,dv});
val[dx][dy]=dv;
}
}
else if(dc<0&&bc>=0)
{
dv=now.v+2;
if(mv>dv)
{
q.push((node){dx,dy,bc,dv});
val[dx][dy]=dv;
}
}
else if(bc<0&&dc>=0)
{
dv=now.v+(now.c==dc? 0:1);
if(mv>dv)
{
q.push((node){dx,dy,dc,dv});
val[dx][dy]=dv;
}
}
}
}
q.pop();
}
}
int main()
{
cin>>m>>n;
Init();
int x,y,c;
for(int i=1;i<=n;i++)
{
cin>>x>>y>>c;
yy[x][y]=c;
}
dfs(1,1);
if(ans==0x7f7f7f7f)
cout<<-1<<endl;
else
cout<<ans<<endl;
return 0;
}
跳房子
【问题描述】
跳房子,也叫跳飞机,是一种世界性的儿童游戏,也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下:
在地面上确定一个起点,然后在起点右侧画 n 个格子,这些格子都在同一条直线上。每个格子内有一个数字(整数),表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳,跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳,依此类推。规则规定:
玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏,获得的分数为曾经到达过的格子中的数字之和。
现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷,它每次向右弹跳的距离只能为固定的 d。小 R 希望改进他的机器人,如果他花 g 个金币改进他的机器人,那么他的机器人灵活性就能增加 g,但是需要注意的是,每次弹跳的距离至少为 1。具体而言,当g < d时,他的机器人每次可以选择向右弹跳的距离为 d-g, d-g+1, d-g+2,…,d+g-2,d+g-1,d+g;否则(当g ≥ d时),他的机器人每次可以选择向右弹跳的距离为 1,2,3,…,d+g-2,d+g-1,d+g。
现在小 R 希望获得至少 k 分,请问他至少要花多少金币来改造他的机器人。
【输入格式】
输入文件名为 jump.in。
第一行三个正整数 n,d,k,分别表示格子的数目,改进前机器人弹跳的固定距离,以及希望至少获得的分数。相邻两个数之间用一个空格隔开。
接下来 n 行,每行两个正整数xi, si,分别表示起点到第i个格子的距离以及第i个格子的分数。两个数之间用一个空格隔开。保证xi按递增顺序输入。
【输出格式】
输出文件名为 jump.out。
共一行,一个整数,表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 k 分,输出-1。
【输入输出样例 1】

【输入输出样例 1 说明】
花费 2 个金币改进后,小 R 的机器人依次选择的向右弹跳的距离分别为 2,3,5,3,4,3,先后到达的位置分别为 2,5,10,13,17,20,对应 1, 2, 3, 5, 6, 7 这 6 个格子。这些格子中的数字之和 15 即为小 R 获得的分数。
【输入输出样例 2】

【输入输出样例 2 说明】
由于样例中 7 个格子组合的最大可能数字之和只有 18 ,无论如何都无法获得 20 分。
【数据规模与约定】
本题共 10 组测试数据,每组数据 10 分。对于全部的数据满足1 ≤ n ≤ 500000, 1 ≤ d ≤2000, 1 ≤ xi, k ≤ 10^9, |si| < 10^5。
对于第 1,2 组测试数据,n ≤ 10;
对于第 3,4,5 组测试数据,n ≤ 500
对于第 6,7,8 组测试数据,d = 1
#include<bits/stdc++.h>
using namespace std;
#define INF 1e18
typedef long long ll;
struct node{
ll pos=0,value=0;
}a[500005];
ll n,d,k;
ll dp[500005];
bool check(ll minn,ll maxx){
for(int i=1;i<=n;i++) dp[i]=-INF;
dp[0]=0LL;
deque<int> q;
int now=0;
for(ll i=1;i<=n;i++){
while(a[i].pos-a[now].pos>maxx&&now<i) now++;
while(a[i].pos-a[now].pos<=maxx&&a[i].pos-a[now].pos>=minn&&now<i){
while(!q.empty()&&(dp[q.back()]<=dp[now]||a[i].pos-a[q.back()].pos>maxx)) q.pop_back();
q.push_back(now);
now++;
}
while(!q.empty()&&a[i].pos-a[q.front()].pos>maxx) q.pop_front();
if(!q.empty()) dp[i]=dp[q.front()]+a[i].value;
if(dp[i]>=k) return true;
}
return false;
}
int main()
{
cin>>n>>d>>k;
for(ll i=1;i<=n;i++) cin>>a[i].pos>>a[i].value;
ll l=1,r=a[n].pos;
while(l<r){
ll mid=(l+r)>>1;
if(check(max((long long)1,d-mid),d+mid)) r=mid;
else l=mid+1;
}
cout<<(r==INF?-1:r);
return 0;
}
公交换乘
【问题描述】
著名旅游城市B市为了鼓励大家采用公共交通方式出行,推出了一种地铁换乘公交 车的优惠方案:
1.在搭乘一次地铁后可以获得一张优惠票,有效期为45分钟,在有效期内可以 消耗这张优惠票,免费搭乘一次票价不超过地铁票价的公交车。在有效期内指 开始乘公交车的时间与开始乘地铁的时间之差小于等于45分钟,即:tbus-tsubway≤45
2. 搭乘地铁获得的优惠票可以累积,即可以连续搭乘若干次地铁后再连续使用优 惠票搭乘公交车。
3. 搭乘公交车时,如果可以使用优惠票一定会使用优惠票;如果有多张优惠票满 足条件,则优先消耗获得最早的优惠票。
现在你得到了小轩最近的公共交通出行记录,你能帮他算算他的花费吗?
【输入格式】
输入文件名为transfer . in。
输入文件的第一行包含一个正整数n,代表乘车记录的数量。
接下来的n行,每行包含3个整数,相邻两数之间以一个空格分隔。第i行的 第1个整数代表第i条记录乘坐的交通工具,0代表地铁,1代表公交车;第2个 整数代表第i条记录乘车的票价pricei;第三个整数代表第i条记录开始乘车的时 间ti (距0时刻的分钟数)。
我们保证出行记录是按照开始乘车的时间顺序给出的,且不会有两次乘车记录出现 在同一分钟。
【输出格式】
输出文件名为transfer . out。
输出文件有一行,包含一个正整数,代表小轩出行的总花费
【 输入输出样例 1】

【输入输出样例1说明】
第一条记录,在第3分钟花费10元乘坐地铁。
第二条记录,在第46分钟乘坐公交车,可以使用第一条记录中乘坐地铁获得的优 惠票,因此没有花费。
第三条记录,在第50分种花费12元乘坐地铁。
第四条记录,在第96分钟乘坐公交车,由于距离第三条记录中乘坐地铁已超过45 分钟,所以优惠票已失效,花费3元乘坐公交车。
第五条记录,在第110分钟花费5元乘坐地铁。
第六条记录,在第135分钟乘坐公交车,由于此时手中只有第五条记录中乘坐地铁 获得的优惠票有效,而本次公交车的票价为6元,高于第五条记录中地铁的票价5元, 所以不能使用优惠票,花费6元乘坐公交车。
总共花费36元。
【输入输出样例2】

【输入输出样例2说明】
第一条记录,在第1分钟花费5元乘坐地铁。
第二条记录,在第16分钟花费20元乘坐地铁。
第三条记录,在第23分钟花费7元乘坐地铁。
第四条记录,在第31分钟乘坐公交车,此时只有第二条记录中乘坐的地铁票价高 于本次公交车票价,所以使用第二条记录中乘坐地铁获得的优惠票。
第五条记录,在第38分钟乘坐公交车,此时第一条和第三条记录中乘坐地铁获得 的优惠票都可以使用,使用获得最早的优惠票,即第一条记录中乘坐地铁获得的优惠票。
第六条记录,在第68分钟乘坐公交车,使用第三条记录中乘坐地铁获得的优惠票。 总共花费32元。
【数据规模与约定】

#include<bits/stdc++.h>
using namespace std;
int n,opt,m,t,num=0,ans=0;
struct data {
int m,t;
bool ok;
} p[100001];
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d%d%d",&opt,&m,&t);
if(opt==0) {
num++;
p[num].m=m;
p[num].t=t;
p[num].ok=0;
ans+=m;
}
if(opt==1) {
bool ok=0;
for(int j=1; j<=num; j++) {
if(t-p[j].t<=45&&p[j].ok==0&&m<=p[j].m) {
p[j].ok=1;
ok=1;
break;
}
}
if(ok==0)
ans+=m;
}
}
printf("%d\n",ans);
return 0;
}
纪念品
【问题描述】
小伟突然获得一种超能力,他知道未来T天N种纪念品每天的价格。某个纪念品 的价格是指购买一个该纪念品所需的金币数量,以及卖出一个该纪念品换回的金币数量。
每天,小伟可以进行以下两种交易无限次:
1. 任选一个纪念品,若手上有足够金币,以当日价格购买该纪念品;
2. 卖出持有的任意一个纪念品,以当日价格换回金币。
每天卖出纪念品换回的金币可以立即用于购买纪念品,当日购买的纪念品也可以当 日卖出换回金币。当然, 一直持有纪念品也是可以的。
T天之后,小伟的超能力消失。因此他一定会在第T天卖出所有纪念品换回金币。 小伟现在有M枚金币,他想要在超能力消失后拥有尽可能多的金币。
【输入格式】
输入文件名为souvenir . in。
第一行包含三个正整数T,N,M,相邻两数之间以一个空格分开,分别代表未来天数 T,纪念品数量N,小伟现在拥有的金币数量M。
接下来T行,每行包含N个正整数,相邻两数之间以一个空格分隔。第i行的N个正整数分别为Pi1,Pi2, …… ,Pin,其中Pi,j表示第i天第j种纪念品的价格。
【输出格式】
输出文件名为souvenir . out。
输出仅一行,包含一个正整数,表示小伟在超能力消失后最多能拥有的金币数量。
【输入输出样例1】

【 输入输出样例1说明】
最佳策略是:
第二天花光所有100枚金币买入5个纪念品1;
第三天卖出5个纪念品1,获得金币125枚;
第四天买入6个纪念品1,剩余5枚金币;
第六天必须卖出所有纪念品换回300枚金币,第四天剩余5枚金币,共305枚金币。
超能力消失后,小伟最多拥有305枚金币。
【输入输出样例2】

【输入输出样例2说明】
最佳策略是:
第一天花光所有金币买入10个纪念品1;
第二天卖出全部纪念品1得到150枚金币并买入8个纪念品2和1个纪念品3,剩 余1枚金币;
第三天必须卖出所有纪念品换回216枚金币,第二天剩余1枚金币,共217枚金币。 超能力消失后,小伟最多拥有217枚金币。
【数据规模与约定】
对于10%的数据,T=1。
对于30%的数据,T≤4,N≤4,M≤100,所有价格10≤Pij≤100。
另有15%的数据,T≤100,N=1。
另有15%的数据,T=2,N≤100。
对于100%的数据,T≤100,N≤100,M≤
,所有价格1≤Pij≤10⁴,数 据保证任意时刻,小明手上的金币数不可能超过10⁴。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2+10;
const int M = 1e4+10;
int t,n,m;
int val[N][N];
int f[N]; //第 x 天最多有多少钱
int tmp[M],mx;
void solve(){
f[1] = m;
for(int day = 2;day <= t;day++){
for(int i = 1;i < day;i++){
memset(tmp,0,sizeof tmp); mx = m;
for(int j = 1;j <= n;j++){
for(int v = val[i][j]; v <= f[i];v++){
tmp[v] = max(tmp[v-val[i][j]]+val[day][j],tmp[v]);
mx = max(mx,tmp[v]+f[i]-v);
}
}
f[day] = max(f[day],mx);
}
f[day] = max(f[day],f[day-1]);
}
//for(int i = 1;i <= t;i++) printf("%d\n",f[i]);
printf("%d\n",f[t]);
}
int main(){
scanf("%d%d%d",&t,&n,&m);
for(int i = 1;i <= t;i++)
for(int j = 1;j <= n;j++) scanf("%d",&val[i][j]);
solve();
return 0;
}
买铅笔 (pencil)
【问题描述】
P 老师需要去商店买 n 支铅笔作为小朋友们参加NOIP 的礼物。她发现商店一共有 3 种包装的铅笔,不同包装内的铅笔数量有可能不同,价格也有可能不同。为了公平起 见,P 老师决定只买同一种包装的铅笔。
商店不允许将铅笔的包装拆开,因此P老师可能需要购买超过 n 支铅笔才够给小朋 友们发礼物。
现在P 老师想知道,在商店每种包装的数量都足够的情况下,要买够至少n 支铅 笔最少需要花费多少钱。
【输入格式】
从文件pencil.in 中读入数据。
输入的第一行包含一个正整数n ,表示需要的铅笔数量。
接下来三行,每行用两个正整数描述一种包装的铅笔:其中第一个整数表示这种 包装内铅笔的数量,第二个整数表示这种包装的价格。
保证所有的 7 个数都是不超过 10000 的正整数。
【输出格式】
输出到文件pencil.out 中。
输出一行一个整数,表示P 老师最少需要花费的钱。
【样例1输入】
57
2 2
50 30
30 27
【样例1输出】
54
【样例1说明】
铅笔的三种包装分别是:
● 2 支装,价格为 2 ;
● 50 支装,价格为 30 ;
● 30 支装,价格为 27 。
P老师需要购买至少57 支铅笔。
如果她选择购买第一种包装,那么她需要购买 29 份,共计 2 × 29 = 58 支,需要花 费的钱为 2 × 29 = 58 。
实际上,P老师会选择购买第三种包装,这样需要买 2 份。 虽然最后买到的铅笔数 量更多了,为 30 × 2 = 60 支,但花费却减少为 27 × 2 = 54 ,比第一种少。
对于第二种包装,虽然每支铅笔的价格是最低的,但要够发必须买 2 份,实际的 花费达到了 30 × 2 = 60 ,因此P老师也不会选择。
所以最后输出的答案是 54 。
【样例2输入】
9998
128 233
128 2333
128 666
【样例2输出】
18407
【样例3输入】
9999
101 1111
1 9999
1111 9999
【样例3输出】
89991
【子任务】
子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难,可以尝试 只解决一部分测试数据。
每个测试点的数据规模及特点如下表:

上表中“整倍数”的意义为:若为“√” ,表示对应数据所需要的铅笔数量 n 一定是每 种包装铅笔数量的整倍数 (这意味着一定可以不用多买铅笔)。
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int want, pcl[3], prc[3], sum = 1; //pcl 为三种铅笔的个数,prc 为三种铅笔的价格
cin >> want >> pcl[0] >> prc[0] >> pcl[1] >> prc[1] >> pcl[2] >> prc[2];
for(int i = 0; i < 3; i++){ //遍历三种铅笔
while(pcl[i]*sum < want) sum++; //循环求出 sum,即最小购买的包数
prc[i] *= sum; //求出每种铅笔的最终花费
sum = 1; //sum 重置
}
sort(prc,prc+3); //将三个花费排序,得到最小花费
cout << prc[0];
return 0;
}