算法竞赛入门【码蹄集进阶塔335题】(MT2306

编程入门行业动态更新时间:2024-10-26 02:26:31

算法竞赛入门【码蹄集<a href=https://www.elefans.com/category/jswz/34/1769503.html style= 进阶塔335题】(MT2306"/>

算法竞赛入门【码蹄集进阶塔335题】(MT2306

算法竞赛入门【码蹄集进阶塔335题】(MT2306-2310）

文章目录

算法竞赛入门【码蹄集进阶塔335题】(MT2306-2310）
前言
- - 为什么突然想学算法了？
  - 为什么选择码蹄集作为刷题软件？
目录
- 1. MT2306 二维矩阵中的最长下降序列
- 2. MT2307 循环空间
- 3. MT2308 calculate
- 4. MT2309 跑图
- 5. MT2310 继续跑图
- 结语

前言

为什么突然想学算法了？

> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下快到了考研和找工作的年纪(ಥ_ಥ)，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个暑假速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

为什么选择码蹄集作为刷题软件？

码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。

（1）题目描述
给定一个n * m的矩阵，然后可以随机选取一个点作为起点，每次可以选择该点的上下左右四个相邻点中的一个并且保证相邻点的值小于当前点的值。问最长的下降序列的长度是多少?请编写一个函数dfs 并且尝试使用记忆化搜索来完成此题。

格式

输入格式:
第一行两个整数n, m(1 ≤n, m ≤100)，
接下来n行，每行有m 个数字a[i][](1≤a[][j]≤4 * 104)。
.
输出格式: 输出最长下降序列的长度。

样例1

输入格式:
5 4
1 2 3 4
16 17 18 19
15 24 25 20
14 23 22 21
13 12 11 10
.
输出格式: 16

备注：

提示
1.1 ≤n, m ≤ 100 ，
2.1≤a[i][j]≤4 * 104。
样例选取起点25，然后25->24-> 23- >22- >…- > 16- > …一>13- > …- > 10，长度为16。

（2）参考代码

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;const int N = 110;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;int a[N][N];int len[N][N];int n, m;int ans = 0;int dx[] = { 0, 0, 1, -1 };int dy[] = { 1, -1, 0, 0 };int dfs(int x, int y){if (len[x][y])return len[x][y];int res = 1;for (int t = 0; t < 4; t++) {int x1 = x + dx[t], y1 = y + dy[t];if (a[x1][y1] < a[x][y])res = max(res, dfs(x1, y1) + 1);}return len[x][y] = res;}signed main(){memset(a, INF, sizeof a);cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {ans = max(ans, dfs(i, j));}}cout << ans << endl;return 0;}

2. MT2307 循环空间

（1）题目描述

在那两个人前面更远处，也可以看到白房子和树，与这里的完全一样，由于角度原因看不到地面，但可以预料那里也有一块同这里一样的黑色田地。也就是说，在这个世界的尽头，又有一个该世界的复制品，也可能是映像。

世界的复制品和映像在周围都存在，他们向两侧看，都看到一个同样的田园世界，他们也在那个世界中，但只能看到背影，他们转头时复制世界中的人也同时转头。他们向后看，吃惊地发现身后也是一个同样的田园世界，只不过他们是在从另一个方向看，那个田园中的他们远在另一端。

他们决定先熟悉周围的环境再进入这些房子，于是继向前走，很快来到了这个小世界的边缘。现在，他们面对着前面的复制世界，最初，他们以为那是个映像，虽然无法解释它的方向，但走到一半时就否定了这个想法，因为那个复制世界太真切了，不像在镜子中。果然，他们向前迈一步就毫无阻碍地进入了复制世界，四下看看，程心的心中升起了一丝恐惧。

—切都恢复到他们刚进入时的状态:他们身处一个与刚才一模一样的田园中，前方、两侧都是这个田园的复制世界，在这些复制世界中，他们也存在。回头看看，在他们刚刚迈出的田园中，他们正在田园最远的一侧，也在回头看。

程心听到关一帆长长地出了一口气，“好了，不要再走了，永远走不完。”他指指天和地，“这两个方向有阻挡，要不也能看见同样的世界。”

“你知道这是什么?"

“你听说过查尔斯·米什内尔这个人吗?”

“没有。”

“他是公元世纪的一个物理学家，他是最早想象出这种东西的人。我们所在的世界其实很简单，是一个正立方体，边长我估计在一千米左右，你可以把它想象成一个房间，有四面墙，加上天花板和地板。但这房间的奇怪之处在于，它的天花板就是地板，在四面墙中，相对两面墙其实是一面墙，所以它实质上只有两面墙。如果你从一面墙前向对面的墙走去，当你走到对面的墙时，你立刻就回到了你出发时的那面墙前。天花板和地板也一样。所以，这是一个全封闭的世界，走到尽头就回到起点。至于我们周围看到的这些映像，也很简单，只是到达世界尽头的光又返回到起点的缘故。咱们现在还是在刚才的那个世界中，是从尽头返回起点，只有这一个世界，其他都是映像。”

——摘自《三体·死神永生》

给出一个二维的由012组成的n * n空间，0表示障碍物，1表示可行走，2表示起点，这个空间是循环的，如走到左边界再往左走，你会出现在右边界对应位置，我们每次能向上下左右其中一个方向走一格。

请输出从起点到每个点的最短路路程。

格式

输入格式:
第一行一个整数n，表示地图的边长。
接下来n行，每行n个整数，О表示障碍物，1表示可行走，2表示起点。
.
输出格式: 输出n行，每行n个整数，О表示起点或无法到达的点，其它以数字表示从起点到此处的最短路路程。

样例1

输入:
5
0 1 2 1 0
0 0 1 0 1
1 1 0 0 1
1 0 0 1 0
1 1 1 0 0
.
输出:
0 1 0 1 0
0 0 1 0 7
5 6 0 0 6
4 0 0 0 0
3 2 1 0 0

备注：

保证：
对于30%的数据:1≤n ≤30。
对于60%的数据:1<n ≤300 。
对于100%的数据:1<n ≤2,000。

（2）参考代码

#include<bits/stdc++.h> using namespace std;
const int N=100;
const int inf=1e8;
int n,m,mp[N][N],g[N][N],price[N],next[N],res=inf;
vector<int> v;void floyd(){res=inf;for(int k=1;k<=n;k++){for(int i=1;i<k;i++)for(int j=i+1;j<k;j++){int num=res;res=min(res,g[i][j]+mp[i][k]+mp[k][j]);//满足题目条件的3}}}int main(){scanf("%d %d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&price[i]);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=j){mp[i][j]=g[i][j]=inf;}}}for(int i=1;i<=m;i++){int u,v;scanf("%d %d",&u,&v);mp[u][v]=mp[v][u]=g[u][v]=g[v][u]=min(price[u]+price[v],mp[u][v]);}floyd();if(res==inf){cout<<-1<<endl;}else{cout<<res/2<<endl;}return 0;}

3. MT2308 calculate

（1）题目描述
小码哥和小码妹打赌，比谁24点算得快，算得慢的那个人请客。24点的规则是这样的:给定4个1~9的整数，用括号改变运算顺序，通过加、减、乘、除中的一系列运算，得到整数24。注意所有中间结果必须是整数(例如(22)/4是允许的，而2(2/4)是不允许的）。为了赢得这个比赛，请写一个程序帮助小码哥作弊，快速地计算出24点。

格式

输入格式:
只有一行用空格隔开的4个整数。
.
输出格式: 一行，以字符串的形式输出结果。注意将每一步的运算的括号补齐(例如(3＋5)＋6和3*(5＋6))。如果有多种解答，输出字典顺序最小的一个。如果无解，输出zzzzzzzzzzzzz。

样例1

输入格式: 2 3 5 7
.
输出格式: (((3*5)+2)+7)

（2）参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int i,j,k,n,m,t,l,r,a[5];
string res="zzzzzzzzzzzzz";
map<int,string> f[5][5];
void chk(int l,int r,int w,string s){if(f[l][r].count(w))f[l][r][w]=min(f[l][r][w],s);else f[l][r][w]=s;
}
int main() {ios::sync_with_stdio(0);for(i=1;i<=4;i++){cin>>a[i];}for(t=1;t<=24;t++){for(i=1;i<=4;i++)for(j=1;j<=4;j++)f[i][j].clear();for(i=1;i<=4;i++)f[i][i][a[i]]=to_string(a[i]);f[1][4][24]=res;for(j=2;j<=4;j++){for(l=1;l+j-1<=4;l++){r=l+j-1;for(i=l;i<r;i++){for(auto [w1,s1]:f[l][i])for(auto [w2,s2]:f[i+1][r]){chk(l,r,w1+w2,"("+s1+"+"+s2+")");chk(l,r,w1-w2,"("+s1+"-"+s2+")");chk(l,r,w1*w2,"("+s1+"*"+s2+")");if(w2&&!(w1%w2))chk(l,r,w1/w2,"("+s1+"/"+s2+")");}}}}res=min(res,f[1][4][24]);next_permutation(a+1,a+5);}cout<<res;
}

4. MT2309 跑图

（1）题目描述
给出一张有向图，你需要返回图中每个节点所连接的最长的边的指向节点和长度。

格式

输入格式:
第一行n, m，表示有n个节点, m条边，第二行开始m行，每行有三个数acyz ,表示有一条从a到y的边,长度为z。
.
输出格式: 输出n行，每行输出2个数为从i出发的最长的边的指向节点和长度，如果该节点没有出边，输出0。

样例1：

输入：
5 5
1 2 3
2 3 4
2 4 5
3 1 1
3 5 2
输出：
2 3
4 5
5 2
0
0

（2）参考代码

#include<bits/stdc++.h> using namespace std;
typedef unsigned long long ull;
typedef long long LL;struct node{int a,b;bool operator < (const node & o) const{if(a!=o.a) return a<o.a;return b<o.b;}
};int main( )
{ull tot=0;int a,b;int n,d;scanf("%d %d",&n,&d);vector<node>T;T.reserve(n);for(int i=0;i<n;i++) {scanf("%d %d",&a,&b);T.push_back({a,b});}sort(T.begin(),T.end());int ii=0,jj=0;tot = T[0].b;ull ans = tot;while(ii<n){while(jj+1<n&&T[jj+1].a-T[ii].a<d){jj+=1;tot+=T[jj].b;}ans = max(ans,tot);tot-=T[ii].b;ii++;if(ii>jj){jj=ii;tot=T[ii].b;}}printf("%llu\n",ans);return 0;
}

5. MT2310 继续跑图

（1）题目描述
给出一张有向图，你需要返回:
图中节点1连接的最长的边指向的节点α和长度，然后是α连接的最长的边指向的节点和长度，以此类推，直到目标节点已经被输出过或者当前节点没有出边。

如果完全没有输出内容，则输出字符串“none”(不包括引号)。

格式

输入格式:
第一行n, m，表示有n个节点，m条边，
第二行开始m行，每行有三个数ayz ,表示有一条从c到y的边,长度为z。
.
输出格式: 输出若干行，每行输出2个数，为从i出发的最长的边的指向节点和长度，如果该节点没有出边或目标节点已被输出，则停止输出，如果完全没有输出内容，则输出字符串“none”(不包括引号)。

样例1

输入格式:
5 5
1 2 3
2 3 4
2 4 5
3 1 1
3 5 2
.
输出格式:
2 3
4 5

（2）参考代码

#include <stdio.h>#include <stdlib.h>#include <string.h>int main() {int n, m;scanf("%d%d", &n, &m);int* flag = (int*)calloc(n + 1, sizeof(int));int** line = (int**)calloc(m, sizeof(int*));for (int i = 0; i < m; i++) {line[i] = (int*)calloc(3, sizeof(int));scanf("%d%d%d", &line[i][0], &line[i][1], &line[i][2]);flag[line[i][0]] = 1;flag[line[i][1]] = 1;}int curN = 1;int fflag = 0;while (1) {int nextN = 0;int max = 0;for (int i = 0; i < m; i++) {if (line[i][0] == curN) {if (line[i][2] > max) {max = line[i][2];nextN = line[i][1];}}}if (flag[nextN] != 0) {curN = nextN;flag[nextN] = 0;fflag = 1;printf("%d %d\n", nextN, max);} else {if (fflag == 0) {printf("none\n");}break;}}return 0;}