龙湖地产 网站建设,高平企业网站,母婴护理服务网站模板,手把手教你做网站7【团体程序设计天梯赛 往年关键真题 详细分析完整AC代码】搞懂了赛场上拿下就稳
【团体程序设计天梯赛 往年关键真题 25分题合集 详细分析完整AC代码】#xff08;L2-001 - L2-024#xff09;搞懂了赛场上拿下就稳了
【团体程序设计天梯赛 往年关键真题 25分题合…【团体程序设计天梯赛 往年关键真题 详细分析完整AC代码】搞懂了赛场上拿下就稳
【团体程序设计天梯赛 往年关键真题 25分题合集 详细分析完整AC代码】L2-001 - L2-024搞懂了赛场上拿下就稳了
【团体程序设计天梯赛 往年关键真题 25分题合集 详细分析完整AC代码】L2-025 - L2-048搞懂了赛场上拿下这些分就稳了
L2-036 网红点打卡攻略 模拟
一个旅游景点如果被带火了的话就被称为“网红点”。大家来网红点游玩俗称“打卡”。在各个网红点打卡的快省乐钱方法称为“攻略”。你的任务就是从一大堆攻略中找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。
输入格式
首先第一行给出两个正整数网红点的个数 N1N≤200和网红点之间通路的条数 M。随后 M 行每行给出有通路的两个网红点、以及这条路上的旅行花费为正整数格式为“网红点1 网红点2 费用”其中网红点从 1 到 N 编号同时也给出你家到某些网红点的花费格式相同其中你家的编号固定为 0。
再下一行给出一个正整数 K是待检验的攻略的数量。随后 K 行每行给出一条待检攻略格式为
n V1 V2 ⋯ V**n
其中 n(≤200) 是攻略中的网红点数V**i 是路径上的网红点编号。这里假设你从家里出发从 V1 开始打卡最后从 V**n 回家。
输出格式
在第一行输出满足要求的攻略的个数。
在第二行中首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号从 1 开始然后输出这个攻略的总路费其间以一个空格分隔。如果这样的攻略不唯一则输出序号最小的那个。
题目保证至少存在一个有效攻略并且总路费不超过 109。
输入样例
6 13
0 5 2
6 2 2
6 0 1
3 4 2
1 5 2
2 5 1
3 1 1
4 1 2
1 6 1
6 3 2
1 2 1
4 5 3
2 0 2
7
6 5 1 4 3 6 2
6 5 2 1 6 3 4
8 6 2 1 6 3 4 5 2
3 2 1 5
6 6 1 3 4 5 2
7 6 2 1 3 4 5 2
6 5 2 1 4 3 6输出样例
3
5 11样例说明
第 2、3、4、6 条都不满足攻略的基本要求即不能做到从家里出发在每个网红点打卡仅一次且能回到家里。所以满足条件的攻略有 3 条。
第 1 条攻略的总路费是(0-5) 2 (5-1) 2 (1-4) 2 (4-3) 2 (3-6) 2 (6-2) 2 (2-0) 2 14
第 5 条攻略的总路费同理可算得1 1 1 2 3 1 2 11是一条更省钱的攻略
第 7 条攻略的总路费同理可算得2 1 1 2 2 2 1 11与第 5 条花费相同但序号较大所以不输出。
代码
#includebits/stdc.h
using namespace std;
#define PII pairint,intconst int INF 0x3f3f3f3f;
const int N 1e310;int main(){int n, m;scanf(%d%d, n, m);int mp[n5][n5];for ( int i 0 ; i n ; i )for ( int j 0 ; j n ; j )mp[i][j] mp[j][i] 0;for ( int i 1 ; i m ; i ){int x, y, w; scanf(%d%d%d, x, y, w);mp[x][y] mp[y][x] w;}vectorPII ans;int q, minwINF; scanf(%d, q);for ( int i 1 ; i q ; i ){int k; scanf(%d, k);vectorint v;setint s;v.push_back(0);for (int j 0 ; j k ; j ){int x; scanf(%d, x);v.push_back(x);s.insert(x);}v.push_back(0);int w 0;if(k ! n || s.size() ! n) continue;bool flag true;for (int j 0 ; j v.size()-1 ; j ){if (mp[v[j]][v[j1]]!0) w mp[v[j]][v[j1]];else {flag false;break;}}if (!flag) continue;minw min(minw, w);ans.push_back({i, w});}printf(%d\n, ans.size());for ( int i 0 ; i ans.size() ; i )if ( ans[i].second minw ){printf(%d %d\n, ans[i].first, ans[i].second);break;}return 0;
}L2-037 包装机 栈和队列
一种自动包装机的结构如图 1 所示。首先机器中有 N 条轨道放置了一些物品。轨道下面有一个筐。当某条轨道的按钮被按下时活塞向左推动将轨道尽头的一件物品推落筐中。当 0 号按钮被按下时机械手将抓取筐顶部的一件物品放到流水线上。图 2 显示了顺序按下按钮 3、2、3、0、1、2、0 后包装机的状态。 图1 自动包装机的结构 图 2 顺序按下按钮 3、2、3、0、1、2、0 后包装机的状态
一种特殊情况是因为筐的容量是有限的当筐已经满了但仍然有某条轨道的按钮被按下时系统应强制启动 0 号键先从筐里抓出一件物品再将对应轨道的物品推落。此外如果轨道已经空了再按对应的按钮不会发生任何事同样的如果筐是空的按 0 号按钮也不会发生任何事。
现给定一系列按钮操作请你依次列出流水线上的物品。
输入格式
输入第一行给出 3 个正整数 N≤100、M≤1000和 Smax≤100分别为轨道的条数于是轨道从 1 到 N 编号、每条轨道初始放置的物品数量、以及筐的最大容量。随后 N 行每行给出 M 个英文大写字母表示每条轨道的初始物品摆放。
最后一行给出一系列数字顺序对应被按下的按钮编号直到 −1 标志输入结束这个数字不要处理。数字间以空格分隔。题目保证至少会取出一件物品放在流水线上。
输出格式
在一行中顺序输出流水线上的物品不得有任何空格。
输入样例
3 4 4
GPLT
PATA
OMSA
3 2 3 0 1 2 0 2 2 0 -1输出样例
MATA分析
队列模拟传送带栈模拟筐
代码
#includebits/stdc.h
using namespace std;
#define PII pairint,intconst int INF 0x3f3f3f3f;
const int N 1e310;int main(){int n, m, s; scanf(%d%d%d, n, m, s);queueint q[n5];stackint sta;for ( int i 1 ; i n ; i ){ //第i号轨道 char str[m5]; scanf(%s,str);for ( int j 0 ; j m ; j ) //第j个物品 q[i].push(str[j]-A);}int x;while ( scanf(%d, x) x ! -1){if ( x 0 q[x].size() ){int t q[x].front();q[x].pop();if(sta.size() s) {printf(%c, sta.top()A);sta.pop();}sta.push(t);}if ( x 0 sta.size() ){printf(%c, sta.top()A);sta.pop();}}return 0;
}
