团队程序设计天梯赛-3.31排位赛总结 港控/mmm° 2023-10-03 18:38 13阅读 0赞 #### 文章目录 #### * 7-1 逆序的三位数 (10 分) * * 题目描述 * 知识点 * 代码 * 7-2 九宫格输入法 (10 分) * * 题目描述 * 知识点 * 代码 * 7-3 装箱问题 (15 分)假设有N项物品,大小分别为s * * 思路 * 代码 * 7-4 掉入陷阱的数字 (15 分) * * 题目描述 * 知识点 * 代码 * 7-5 龟兔赛跑 (20 分) * * 题目描述 * 思路 * 注意点 * 知识点 * 代码一(参考代码) * 代码二(我的代码) * 7-6 谷歌的招聘 (20 分) * * 题目描述 * 思路 * 知识点 * 代码 * 7-7 火星文 (25 分) * * 题目描述 * 知识点 * 注意点 * 思路 * 代码 * 7-8 地下迷宫探索 (25 分) * * 题目描述 * 思路 * 知识点 * 代码 * 7-9 二叉搜索树的2层结点统计 (25 分) * * 题目描述 * 思路 * 知识点 * 说明 * 代码一(二叉链表建树) * 代码二(只有14分) * 7-10 天梯地图 (25 分) * * 题目描述 * 思路 * 代码 * * ps:还没看 * 7-11 长城 (25 分) * * 题目描述 * 思路 * 代码 * * ps:还没看 ## 7-1 逆序的三位数 (10 分) ## ### 题目描述 ### 程序每次读入一个正3位数,然后输出按位逆序的数字。注意:当输入的数字含有结尾的0时,输出不应带有前导的0。比如输入700,输出应该是7。 输入格式: 每个测试是一个3位的正整数。 输出格式: 输出按位逆序的数。 输入样例: 123 输出样例: 321 ### 知识点 ### * reverse()函数的使用:可以翻转数组,字符串,向量等!![C++中的reverse()函数][C_reverse] * stoi()函数的使用:将字符串转化为对应的数字,(会去掉前导0!!) ### 代码 ### #include<bits/stdc++.h> using namespace std; int main() { string s; cin >> s; reverse(s.begin(), s.end()); cout << stoi(s); return 0; } ## 7-2 九宫格输入法 (10 分) ## ### 题目描述 ### 假设有九宫格输入法键盘布局如下: [ 1,.?! ] [ 2ABC ] [ 3DEF ] [ 4GHI ] [ 5JKL ] [ 6MNO ] [ 7PQRS ] [ 8TUV ] [ 9WXYZ ] [ 0空 ] 注意:中括号\[ \]仅为了表示键盘的分隔,不是输入字符。每个中括号中,位于首位的数字字符即是键盘的按键,按一下即可输入该数字字符。多次按同一个键,则输入的字符依次循环轮流,例如按两次3,则输入D;按5次7,则输入S;按6次2,则输入A。按键0的输入组合是0和空格字符,即按两次0输入空格。 你需要对于给定的按键组合,给出该组合对应的文本。 输入格式: 输入在一行中给出数个字符的按键组合(例如 999 表示按3次9),每个字符的按键组合之间用空格间隔,最后一个输入法组合之后以换行结束。输入数据至少包括一个字符的按键组合,且输入总长度不超过500个字符。 输出格式: 在一行中输出该按键组合对应的文本。 输入样例: 22 5555 22 666 00 88 888 7777 4444 666 44 输出样例: ALAN TURING ### 知识点 ### 取模的运用,取模的时候要小心,不确定的话可以枚举几个看看 ### 代码 ### #include<bits/stdc++.h> using namespace std; int main() { string a[] = { "00", "1,.?!", "2ABC", "3DEF", "4GHI", "5JKL", "6MNO", "7PQRS", "8TUV", "9WXYZ" }; string s; while(cin>>s) { int t = (s.size()-1)%(a[s[0]-48].size()); if(s[0]=='0' && t==0) cout << '0'; else if(s[0]=='0' && t==1) cout << ' '; else cout << a[s[0]-48][t]; } return 0; } ## 7-3 装箱问题 (15 分)假设有N项物品,大小分别为s ## 1 、s 2 、…、s i 、…、s N ,其中s i 为满足1≤s i ≤100的整数。要把这些物品装入到容量为100的一批箱子(序号1-N)中。装箱方法是:对每项物品, 顺序扫描箱子,把该物品放入足以能够容下它的第一个箱子中。请写一个程序模拟这种装箱过程,并输出每个物品所在的箱子序号,以及放置全部物品所需的箱子数目。 输入格式: 输入第一行给出物品个数N(≤1000);第二行给出N个正整数s i (1≤s i ≤100,表示第i项物品的大小)。 输出格式: 按照输入顺序输出每个物品的大小及其所在的箱子序号,每个物品占1行,最后一行输出所需的箱子数目。 输入样例: 8 60 70 80 90 30 40 10 20 输出样例: 60 1 70 2 80 3 90 4 30 1 40 5 10 1 20 2 5 ### 思路 ### 两层循环,先用容量100初始化数组,循环时能装下就减去所需容量 ### 代码 ### #include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a; for(int i=0; i<n; i++) a.push_back(100); int max = 0; for(int i=0; i<n; i++) { int x, j; cin >> x; for(j=0; a[j]<x; j++); cout << x << " " << j+1 << endl; if(j+1>max) max = j+1; a[j] -= x; } cout << max; return 0; } ## 7-4 掉入陷阱的数字 (15 分) ## ### 题目描述 ### ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_11_color_FFFFFF_t_70_g_se_x_16] 输入格式: 在一行内给出一个自然数N 0(N 0 <30000)。 输出格式: ![在这里插入图片描述][f8d119e393e94f1482ce8ae8d754cad4.png] 输入样例: 5 输出样例: 1:16 2:22 3:13 4:13 ### 知识点 ### 关于求各个位数之和的两种方法 方法一(将数字分割后求) int fun(int x) { int res = 0; while(x) { res += x%10; x /= 10; } return res*3+1; } 方法二(转为字符串后各个位数相加) int each_num = n; string s = to_string(each_num); int sum_each=0; for(int i=0; i<s.size(); i++) { sum_each+=s[i]-'0'; } int each_res = sum_each*3+1; 按题目要求进行循环即可 ### 代码 ### #include<bits/stdc++.h> using namespace std; int fun(int x) { int res = 0; while(x) { res += x%10; x /= 10; } return res*3+1; } int main() { int n; cin >> n; for(int i=1; ; i++) { int x = fun(n); printf("%d:%d\n", i, x); if(x==n) break; n = x; } } ## 7-5 龟兔赛跑 (20 分) ## ### 题目描述 ### 乌龟与兔子进行赛跑,跑场是一个矩型跑道,跑道边可以随地进行休息。乌龟每分钟可以前进3米,兔子每分钟前进9米;兔子嫌乌龟跑得慢,觉得肯定能跑赢乌龟,于是,每跑10分钟回头看一下乌龟,若发现自己超过乌龟,就在路边休息,每次休息30分钟,否则继续跑10分钟;而乌龟非常努力,一直跑,不休息。假定乌龟与兔子在同一起点同一时刻开始起跑,请问T分钟后乌龟和兔子谁跑得快? 输入格式: 输入在一行中给出比赛时间T(分钟)。 输出格式: 在一行中输出比赛的结果:乌龟赢输出@*@,兔子赢输出\_,平局则输出-*\-;后跟1空格,再输出胜利者跑完的距离。 输入样例: 242 输出样例: @_@ 726 ### 思路 ### 参考代码中是把每一分钟两者的情况都算出来(先把乌龟的算出来) 我的代码是直接从0开始遍历每一分钟,根据对应的情况进行比较,flag为true时代表兔子在跑,false为在休息 ### 注意点 ### 注意两者打平的时候也要输出跑过的距离(两者相等) ### 知识点 ### .back()可取得容器中的最后一个值!!! ### 代码一(参考代码) ### #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; vector<int> a, b; a.push_back(0); b.push_back(0); for(int i=1; i<=t+30; i++) a.push_back(i*3);//提前计算乌龟第i分钟跑了多少米 int k = 0; while(k<=t) { if(k<=t) for(int i=0; i<10; i++, k++) //跑10分钟 b.push_back(b.back()+9); if(k<=t && b[k]>a[k]) //是否需要休息30分钟 for(int i=0; i<30; i++, k++) b.push_back(b.back()); } if(a[t]>b[t]) cout << "@_@ " << a[t]; else if(a[t]==b[t]) cout << "-_- " << a[t]; else cout << "^_^ " << b[t]; return 0; } ### 代码二(我的代码) ### #include <bits/stdc++.h> using namespace std; int main() { int rab = 0; int tut = 0; int n; cin>>n; int run_time=0; int flag = true; for(int i=0; i<n; i++) { if(i==run_time) { flag = true; } if(i%10==0&&flag) { if(rab>tut) { flag = false; run_time = i+30; } else { flag = true; } } if(flag) { rab+=9; } tut+=3; } // cout<<rab<<" "<<tut<<endl; if(rab>tut) { cout<<"^_^ "<<rab; } else if(rab<tut) { cout<<"@_@ "<<tut; } else { cout<<"-_- "<<tut; } } ## 7-6 谷歌的招聘 (20 分) ## ### 题目描述 ### 004 年 7 月,谷歌在硅谷的 101 号公路边竖立了一块巨大的广告牌(如下图)用于招聘。内容超级简单,就是一个以 .com 结尾的网址,而前面的网址是一个 10 位素数,这个素数是自然常数 e 中最早出现的 10 位连续数字。能找出这个素数的人,就可以通过访问谷歌的这个网站进入招聘流程的下一步。 自然常数 e 是一个著名的超越数,前面若干位写出来是这样的:e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921… 其中粗体标出的 10 位数就是答案。 ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_11_color_FFFFFF_t_70_g_se_x_16 1] 本题要求你编程解决一个更通用的问题:从任一给定的长度为 L 的数字中,找出最早出现的 K 位连续数字所组成的素数。 输入格式: 输入在第一行给出 2 个正整数,分别是 L(不超过 1000 的正整数,为数字长度)和 K(小于 10 的正整数)。接下来一行给出一个长度为 L 的正整数 N。 输出格式: 在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。如果这样的素数不存在,则输出 404。注意,原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数,0023 算是解;但第一位 2 不能被当成 0002 输出,因为在原始数字中不存在这个 2 的前导零。 输入样例 1: 20 5 23654987725541023819 输出样例 1: 49877 输入样例 2: 10 3 2468001680 输出样例 2: 404 ### 思路 ### 以字符串形式输入,遍历字符串,不断截取所需长度的字符串,使用stoi(会自动去掉前导0)将截取的字符串转为整型数,调用判断素数的函数,如果是素数则输出该数,flag设为true,若flag为false则输出404 ### 知识点 ### * 求素数的几种方法(一般开个方就够用了) [求质数(素数)的函数][Link 1] * 截取字符串中的子串:s.substr() 语法 substr(size\_type \_Off = 0,size\_type \_Count = npos) 一种构造string的方法 形式 : s.substr(pos, len) 返回值: string,包含s中从pos开始的len个字符的拷贝(pos的默认值是0,len的默认值是s.size() - pos,即不加参数会默认拷贝整个s) 异常 :若pos的值超过了string的大小,则substr函数会抛出一个out\_of\_range异常;若pos+n的值超过了string的大小,则substr会调整n的值,只拷贝到string的末尾 注意参数是开始位置和截取的长度!!!! * stoi ### 代码 ### #include<iostream> #include<string> #include<cmath> using namespace std; bool prime(int x) { if(x<=1) return false; int k = sqrt(x); for(int i=2; i<=k; i++) if(x%i==0) return false; return true; } int main() { int n, k; cin >> n >> k; string s; cin >> s; int flag = 0; for(int i=0; i<=n-k; i++) { string tmp = s.substr(i, k); if(prime(stoi(tmp))) { cout << tmp; flag = 1; break; } } if(flag==0) cout << "404"; return 0; } ## 7-7 火星文 (25 分) ## ### 题目描述 ### 火星人是以 13 进制计数的: 地球人的 0 被火星人称为 tret。 地球人数字 1 到 12 的火星文分别为:jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec。 火星人将进位以后的 12 个高位数字分别称为:tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou。 例如地球人的数字 29 翻译成火星文就是 hel mar;而火星文 elo nov 对应地球数字 115。为了方便交流,请你编写程序实现地球和火星数字之间的互译。 输入格式: 输入第一行给出一个正整数 N(<100),随后 N 行,每行给出一个 \[0, 169) 区间内的数字 —— 或者是地球文,或者是火星文。 输出格式: 对应输入的每一行,在一行中输出翻译后的另一种语言的数字。 输入样例: 4 29 5 elo nov tam 输出样例: hel mar may 115 13 ### 知识点 ### * 13进制与10进制的转换 * 用substr截取字符串中的子串 * isdigit判断该字符是否为数字对应的字符 ### 注意点 ### 注意输出火星文时有三种情况:1.只有高位(这时候低位不是输出tret!!!参考样例中的最后一个),2.只有低位 3. 高低位都有 ### 思路 ### 这个题目,考的是细心以及逻辑表现 数值转为火星后,如果低位为0,只输出高位(样例就是这样) 输出火星时:1.只有高位,2.只有低位 3. 高低位都有,要注意三种情况下的空格和换行处理 火星转数值:要注意高位单词有可能跟低位单词一起出现,也有可能单独出现 ### 代码 ### #include<bits/stdc++.h> using namespace std; string di[] = { "tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec" }; string gao[] = { "", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou" }; void huoxing(int x) { //数值转火星 if(x==0)//把这种情况放在下面的else-if一起处理也可以,不过这样写不容易错。 { cout << di[0] << endl; return; } if(x/13) cout << gao[x/13]; if(x/13 && x%13) cout << " " << di[x%13]; else if(x%13) cout << di[x%13]; cout << endl; } void shuzi(string s) { //火星转数值 ? if(s=="tret")//这五行不写也可以,因为下面会处理到这种情况 { cout << 0 << endl; return; } string t1 = "", t2; if(s.size()>3) { t1 = s.substr(0, 3); t2 = s.substr(4); } else t2 = s; int x = 0, y = 0; for(int i=0; i<13; i++) { if(gao[i]==t1) x = i*13; if(di[i]==t2) y = i; if(gao[i]==t2) y = i*13;//t2的单词有可能是高位单词也有可能是低位单词 } ??cout << x+y << endl; } int main() { int n; cin >> n; getchar(); while(n--) { string s; getline(cin, s); if(isdigit(s[0])) huoxing(stoi(s)); else shuzi(s); } return 0; } ## 7-8 地下迷宫探索 (25 分) ## ### 题目描述 ### 地道战是在抗日战争时期,在华北平原上抗日军民利用地道打击日本侵略者的作战方式。地道网是房连房、街连街、村连村的地下工事,如下图所示。 ![在这里插入图片描述][0e9d60df778943438fd9dad87911f36d.png] 我们在回顾前辈们艰苦卓绝的战争生活的同时,真心钦佩他们的聪明才智。在现在和平发展的年代,对多数人来说,探索地下通道或许只是一种娱乐或者益智的游戏。本实验案例以探索地下通道迷宫作为内容。 假设有一个地下通道迷宫,它的通道都是直的,而通道所有交叉点(包括通道的端点)上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点? ![在这里插入图片描述][c479d6e7ff744849a164f7c5bf710a31.png] 输入格式: 输入第一行给出三个正整数,分别表示地下迷宫的节点数N(1<N≤1000,表示通道所有交叉点和端点)、边数M(≤3000,表示通道数)和探索起始节点编号S(节点从1到N编号)。随后的M行对应M条边(通道),每行给出一对正整数,分别是该条边直接连通的两个节点的编号。 输出格式: 若可以点亮所有节点的灯,则输出从S开始并以S结束的包含所有节点的序列,序列中相邻的节点一定有边(通道);否则虽然不能点亮所有节点的灯,但还是输出点亮部分灯的节点序列,最后输出0,此时表示迷宫不是连通图。 由于深度优先遍历的节点序列是不唯一的,为了使得输出具有唯一的结果,我们约定以节点小编号优先的次序访问(点灯)。在点亮所有可以点亮的灯后,以原路返回的方式回到起点。 输入样例1: 6 8 1 1 2 2 3 3 4 4 5 5 6 6 4 3 6 1 5 输出样例1: 1 2 3 4 5 6 5 4 3 2 1 输入样例2: 6 6 6 1 2 1 3 2 3 5 4 6 5 6 4 输出样例2: 6 4 5 4 6 0 ### 思路 ### 每个顶点可以经过多次。 只要没遍历过的顶点都得遍历。 因为要列出返回路径,所以在访问了下一个顶点后,当前顶点还得入栈。 ### 知识点 ### 用vis数组记录当前点是否被访问 深搜 ### 代码 ### #include<bits/stdc++.h> using namespace std; int n, m, s; int a[1001][1001]; bool vis[1001]; vector<int> path, bpath; int cnt, bcnt = 0; void dfs(int t) { path.push_back(t); vis[t] = 1; for(int i=1; i<=n; i++) { if(a[t][i]==1 && vis[i]==0) { dfs(i); path.push_back(t);//回头会经过这个点 } } } int main() { cin >> n >> m >> s; while(m--) { int x, y; cin >> x >> y; a[x][y] = a[y][x] = 1; } dfs(s); int flag = 0; for(int x:path) { if(flag) cout << " "; flag = 1; cout << x; } for(int i=1; i<=n; i++) if(vis[i]==0) { cout << " 0"; break; } return 0; } ## 7-9 二叉搜索树的2层结点统计 (25 分) ## ### 题目描述 ### 二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉搜索树。 将一系列数字按给定顺序插入一棵初始为空的二叉搜索树,你的任务是统计结果树中最下面 2 层的结点数。 输入格式:输入在第一行给出一个正整数 N (≤1000),为插入数字的个数。第二行给出 N 个 \[−1000,1000\] 区间内的整数。数字间以空格分隔。 输出格式:在一行中输出最下面 2 层的结点总数。 输入样例: 9 25 30 42 16 20 20 35 -5 28 输出样例: 6 ### 思路 ### 根据题目要求建立二叉搜索树 这个不能使用map来建立二叉搜索树,会超时。因为map是基于红黑树的,每次查找都是O(logn) 使用数据结构里的二叉链表建树 ### 知识点 ### 使用二叉链表建树!! 先定义结点结构体 struct node{ int value; node *lch,*rch; }; 递归建立二叉搜索树 void cre(node* &t, int x, int level) { if(t==NULL) { t = new node; t->lch = t->rch = NULL; t->value = x; cnt[level]++; if(level>mmax) mmax = level; return; } if(x<=t->value) cre(t->lch, x, level+1); else cre(t->rch, x, level+1); } ### 说明 ### 我当时一开始用的是数组,结果段错误,然后用了vector也是段错误,一开始开的小只有10分,但后来开到1000000就有14分了!!但还是不能全过,后来改用了map结果有的点运行超时,还是不能全过,但这种建树的方法还是很棒的!!见代码二 ### 代码一(二叉链表建树) ### #include<bits/stdc++.h> using namespace std; struct node { int value; node *lch, *rch; }; int mmax = 0; map<int, int> cnt;//cnt[第几层] = 结点个数 void cre(node* &t, int x, int level) { if(t==NULL) { t = new node; t->lch = t->rch = NULL; t->value = x; cnt[level]++; if(level>mmax) mmax = level; return; } if(x<=t->value) cre(t->lch, x, level+1); else cre(t->rch, x, level+1); } int main() { int n; cin >> n; node *root = NULL; while(n--) { int x; cin >> x; cre(root, x, 1); } cout << cnt[mmax]+cnt[mmax-1]; } ### 代码二(只有14分) ### #include <bits/stdc++.h> using namespace std; //int tree[10000]; //int ceng[10000]; map<long long,long long> m1; map<long long,long long> m2; int max_id = 0; void insert(int x){ long long i=1; long long cnt = 0; while(m1[i]!=0){ cnt++; if(x<=m1[i]){ i=i*2; } else{ i=i*2+1; } } m1[i] = x; m2[i] = cnt; // max_id = max(max_id,i); } int main(){ long long n; cin>>n; long long root; cin>>root; m1[1] = root; for(long long i=2;i<=n;i++){ long long num; cin>>num; insert(num); } // for(long long i=1;i<=max_id;i++){ // cout<<tree[0][i]<<" "; // } // for(long long i=1;i<=max_id;i++){ // cout<<tree[1][i]<<" "; // } long long max_ceng = 0; // for(long long i=1;i<=max_id;i++){ for(auto t:m2){ if(t.second>max_ceng){ max_ceng = t.second; } } // } long long max_ceng_minus1 = max_ceng-1; long long cnt_res = 0; // for(long long i=1;i<=max_id;i++){ for(auto t:m2){ if(t.second == max_ceng||t.second == max_ceng_minus1){ cnt_res++; } } // } cout<<cnt_res; } ## 7-10 天梯地图 (25 分) ## ### 题目描述 ### 本题要求你实现一个天梯赛专属在线地图,队员输入自己学校所在地和赛场地点后,该地图应该推荐两条路线:一条是最快到达路线;一条是最短距离的路线。题目保证对任意的查询请求,地图上都至少存在一条可达路线。 输入格式: 输入在第一行给出两个正整数N(2 ≤ N ≤ 500)和M,分别为地图中所有标记地点的个数和连接地点的道路条数。随后M行,每行按如下格式给出一条道路的信息: V1 V2 one-way length time 其中V1和V2是道路的两个端点的编号(从0到N-1);如果该道路是从V1到V2的单行线,则one-way为1,否则为0;length是道路的长度;time是通过该路所需要的时间。最后给出一对起点和终点的编号。 输出格式: 首先按下列格式输出最快到达的时间T和用节点编号表示的路线: Time = T: 起点 => 节点1 => … => 终点 然后在下一行按下列格式输出最短距离D和用节点编号表示的路线: Distance = D: 起点 => 节点1 => … => 终点 如果最快到达路线不唯一,则输出几条最快路线中最短的那条,题目保证这条路线是唯一的。而如果最短距离的路线不唯一,则输出途径节点数最少的那条,题目保证这条路线是唯一的。 如果这两条路线是完全一样的,则按下列格式输出: Time = T; Distance = D: 起点 => 节点1 => … => 终点 输入样例1: 10 15 0 1 0 1 1 8 0 0 1 1 4 8 1 1 1 5 4 0 2 3 5 9 1 1 4 0 6 0 1 1 7 3 1 1 2 8 3 1 1 2 2 5 0 2 2 2 1 1 1 1 1 5 0 1 3 1 4 0 1 1 9 7 1 1 3 3 1 0 2 5 6 3 1 2 1 5 3 输出样例1: Time = 6: 5 => 4 => 8 => 3 Distance = 3: 5 => 1 => 3 输入样例2: 7 9 0 4 1 1 1 1 6 1 3 1 2 6 1 1 1 2 5 1 2 2 3 0 0 1 1 3 1 1 3 1 3 2 1 2 1 4 5 0 2 2 6 5 1 2 1 3 5 输出样例2: Time = 3; Distance = 4: 3 => 2 => 5 ### 思路 ### 使用Dijkstra满分,dfs最后一个点超时 但是这个问题的Dijkstra,少点耐心细心都不行,太容易错了 dfs始终只关注当前路径,那些最短找最少,最快找最短,设置变量就 行,不像Dijkstra,搞一大堆辅助数组。而且一个dfs可以同时求最短长度和时间。 ### 代码 ### #include<bits/stdc++.h> using namespace std; const int inf = INT_MAX; const int mm = 500; int n, m; int b, e; int len[mm][mm], ti[mm][mm]; int lenpre[mm], tipre[mm]; int blen[mm], bti[mm]; void Dij1(int data[][mm], int res[], int pre[]) { bool vis[mm] = { 0}; int pathlen[mm] = { 0}; fill(res, res+n, inf); for(int i=0; i<n; i++) { //初始化 if(data[b][i]!=inf) { res[i] = data[b][i]; pathlen[i]++; pre[i] = b; } } vis[b] = 1; for(int i=1; i<n; i++) { int min = inf, minid; for(int j=0; j<n; j++) { //选最小 if(!vis[j]) { if(res[j]<min) min = res[j], minid = j; else if(res[j]!=inf && res[j]==min) if(pathlen[j]<pathlen[minid]) minid = j; } } vis[minid] = 1; if(minid==e) break; for(int j=0; j<n; j++) { //根据最小刷新其他 if(!vis[j] && data[minid][j]!=inf) { if(data[minid][j]+res[minid] < res[j]) { res[j] = data[minid][j]+res[minid]; pathlen[j] = pathlen[minid]+1; pre[j] = minid; } else if(data[minid][j]+res[minid] == res[j] && pathlen[minid]+1<pathlen[j]) { pathlen[j] = pathlen[minid]+1; pre[j] = minid; } } } } } void Dij2(int data[][mm], int res[], int pre[]) { //时间 bool vis[mm] = { 0}; fill(res, res+n, inf); int dis[mm];//记录对应时间路径的最短距离 fill(dis, dis+n, inf); for(int i=0; i<n; i++) { //初始化 if(data[b][i]!=inf) { res[i] = data[b][i]; pre[i] = b; dis[i] = len[b][i];//原始数据 } } vis[b] = 1; for(int i=1; i<n; i++) { int min = inf, minid; for(int j=0; j<n; j++) { //选最小 if(!vis[j] && res[j]<min) min = res[j], minid = j; else if(!vis[j] && res[j]==min && dis[j]<dis[minid]) minid = j; } //cout << "minid: " << minid << endl; vis[minid] = 1; if(minid==e) break; for(int j=0; j<n; j++) { //根据最小刷新其他 if(!vis[j] && data[minid][j]!=inf) { if(data[minid][j]+res[minid] < res[j]) { res[j] = data[minid][j]+res[minid]; pre[j] = minid; dis[j] = dis[minid] + len[minid][j]; } else if(data[minid][j]+res[minid]==res[j] && dis[minid]+len[minid][j]<dis[j]) { pre[j] = minid; dis[j] = dis[minid] + len[minid][j]; } } } } } int main() { cin >> n >> m; fill(len[0], len[0]+mm*mm, inf); fill(ti[0], ti[0]+mm*mm, inf); while(m--) { int v1, v2, one, l, t; cin >> v1 >> v2 >> one >> l >> t; len[v1][v2] = l; ti[v1][v2] = t; if(one==0) len[v2][v1] = l, ti[v2][v1] = t; } cin >> b >> e; Dij1(len, blen, lenpre); Dij2(ti, bti, tipre); vector<int> lenpa, tipa;//存储最终路径 int now = e; while(now != b) { lenpa.push_back(now); now = lenpre[now]; } now = e; while(now != b) { tipa.push_back(now); now = tipre[now]; } if(lenpa!=tipa) { cout << "Time = " << bti[e] << ": " << b; for(int i=tipa.size()-1; i>=0; i--) printf(" => %d", tipa[i]); cout << "\nDistance = " << blen[e] << ": " << b; for(int i=lenpa.size()-1; i>=0; i--) printf(" => %d", lenpa[i]); } else { printf("Time = %d; Distance = %d: %d", bti[e], blen[e], b); for(int i=tipa.size()-1; i>=0; i--) printf(" => %d", tipa[i]); } } #### ps:还没看 #### ## 7-11 长城 (25 分) ## ### 题目描述 ### 正如我们所知,中国古代长城的建造是为了抵御外敌入侵。在长城上,建造了许多烽火台。每个烽火台都监视着一个特定的地区范围。一旦某个地区有外敌入侵,值守在对应烽火台上的士兵就会将敌情通报给周围的烽火台,并迅速接力地传递到总部。 现在如图1所示,若水平为南北方向、垂直为海拔高度方向,假设长城就是依次相联的一系列线段,而且在此范围内的任一垂直线与这些线段有且仅有唯一的交点。 ![在这里插入图片描述][bcae1a1216d74d0a994d05c8903f28f0.png] 进一步地,假设烽火台只能建造在线段的端点处。我们认为烽火台本身是没有高度的,每个烽火台只负责向北方(图1中向左)瞭望,而且一旦有外敌入侵,只要敌人与烽火台之间未被山体遮挡,哨兵就会立即察觉。当然,按照这一军规,对于南侧的敌情各烽火台并不负责任。一旦哨兵发现敌情,他就会立即以狼烟或烽火的形式,向其南方的烽火台传递警报,直到位于最南侧的总部。 以图2中的长城为例,负责守卫的四个烽火台用蓝白圆点示意,最南侧的总部用红色圆点示意。如果红色星形标示的地方出现敌情,将被哨兵们发现并沿红色折线将警报传递到总部。当然,就这个例子而言只需两个烽火台的协作,但其他位置的敌情可能需要更多。 然而反过来,即便这里的4个烽火台全部参与,依然有不能覆盖的(黄色)区域。 ![在这里插入图片描述][ea84cf113e714bd6ba4f725011bf8586.png] 另外,为避免歧义,我们在这里约定,与某个烽火台的视线刚好相切的区域都认为可以被该烽火台所监视。以图3中的长城为例,若A、B、C、D点均共线,且在D点设置一处烽火台,则A、B、C以及线段BC上的任何一点都在该烽火台的监视范围之内。 ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_12_color_FFFFFF_t_70_g_se_x_16] 好了,倘若你是秦始皇的太尉,为不致出现更多孟姜女式的悲剧,如何在保证长城安全的前提下,使消耗的民力(建造的烽火台)最少呢? 输入格式: 输入在第一行给出一个正整数N(3 ≤ N ≤10 5 ),即刻画长城边缘的折线顶点(含起点和终点)数。随后N行,每行给出一个顶点的x和y坐标,其间以空格分隔。注意顶点从南到北依次给出,第一个顶点为总部所在位置。坐标为区间\[−10 9 ,10 9 )内的整数,且没有重合点。 输出格式: 在一行中输出所需建造烽火台(不含总部)的最少数目。 输入样例: 10 67 32 48 -49 32 53 22 -44 19 22 11 40 10 -65 -1 -23 -3 31 -7 59 输出样例: 2 ### 思路 ### 用了个最粗笨的办法: 要判断当前点t是否需要设岗,那就判断 t是否 线段t+1->t 与 线段 t->之前的哨岗 之间的凸点,只要有一 次不是凸点,那t就不需要设岗,反之,说明之前的哨岗都看不到线段t+1->t,t必须设岗。 这个方法效率较低,因为每次都得跟之前的哨岗做判断,但居然满分。好吧。 ### 代码 ### #include<bits/stdc++.h> using namespace std; int n; int x[100000], y[100000]; vector<int> res; bool ju(int t) { //判断t是否 t->t+1->之前的哨岗 这条折线的凸点,如果全是,那t必须设置哨岗 int i; for(i=res.size()-1; i>=0; i--) { int k = res[i]; float k1 = 1.0*(y[t] - y[t+1]) / (x[t] - x[t+1]); float k2 = 1.0*(y[k] - y[t+1]) / (x[k] - x[t+1]); if(k2>=k1)//t+1与之前某哨岗k的连线斜率大于等于t+1与t的连线斜率,说明本次t不是凸点 ??return false;//无需设岗 } return true;//需要设岗 } int main() { cin >> n; for(int i=0; i<n; i++) cin >> x[i] >> y[i]; res.push_back(0);//0是哨岗 int cnt = 0; for(int i=1; i<n-1; i++) { //判断当前点与下一个点的连线斜率k2,当前点与上一个岗的连线斜率k1,谁大 if(ju(i)) { //判断当前点是否需要作为哨岗 cnt++; res.push_back(i); } } cout << cnt; } #### ps:还没看 #### [C_reverse]: https://blog.csdn.net/YMWM_/article/details/115468297 [watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_11_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/c52767c9668a43f683f9fbe299d558cd.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAR0NUVFRUVFQ=,size_11,color_FFFFFF,t_70,g_se,x_16 [f8d119e393e94f1482ce8ae8d754cad4.png]: https://img-blog.csdnimg.cn/f8d119e393e94f1482ce8ae8d754cad4.png [watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_11_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/51c0c0a1d6bc4ca692c59208e7def5a8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAR0NUVFRUVFQ=,size_11,color_FFFFFF,t_70,g_se,x_16 [Link 1]: https://blog.csdn.net/qq_43280520/article/details/86619122 [0e9d60df778943438fd9dad87911f36d.png]: https://img-blog.csdnimg.cn/0e9d60df778943438fd9dad87911f36d.png [c479d6e7ff744849a164f7c5bf710a31.png]: https://img-blog.csdnimg.cn/c479d6e7ff744849a164f7c5bf710a31.png [bcae1a1216d74d0a994d05c8903f28f0.png]: https://img-blog.csdnimg.cn/bcae1a1216d74d0a994d05c8903f28f0.png [ea84cf113e714bd6ba4f725011bf8586.png]: https://img-blog.csdnimg.cn/ea84cf113e714bd6ba4f725011bf8586.png [watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_12_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/fbf9dd2934dc4848b8290950b2f0afe2.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAR0NUVFRUVFQ=,size_12,color_FFFFFF,t_70,g_se,x_16
相关 团队程序设计天梯赛-4.9排位赛总结 文章目录 7-1 谁是赢家 (5 分) 题目描述 代码 7-2 有理数比较 (5 分) 题目描述 注意点 浅浅的花香味﹌/ 2023年10月03日 18:40/ 0 赞/ 12 阅读
相关 团队程序设计天梯赛-3.31排位赛总结 文章目录 7-1 逆序的三位数 (10 分) 题目描述 知识点 代码 7-2 九宫格输入法 (10 分) 港控/mmm°/ 2023年10月03日 18:38/ 0 赞/ 14 阅读
相关 团队程序设计天梯赛-3.19排位赛总结 文章目录 7-1 冠军魔术 (10 分) 题目 知识点 代码 7-2 单词长度 (10 分) 题目 水深无声/ 2023年10月03日 18:37/ 0 赞/ 10 阅读
相关 团队程序设计天梯赛-3.17字符串与数组基础排位赛总结 文章目录 7-1 Time Difference (10 分) 题目 思路 代码 7-2 念数字 (10 分) 一时失言乱红尘/ 2023年10月03日 18:34/ 0 赞/ 15 阅读
相关 团队程序设计天梯赛-3.12排位赛总结 文章目录 7-1 12-24小时制 (10 分) 题目 思路 代码 7-2 有理数加法 (10 分) 题目 淡淡的烟草味﹌/ 2023年10月03日 18:32/ 0 赞/ 14 阅读
相关 团队程序设计天梯赛-3.3排位赛总结 文章目录 7-1 心理阴影面积 (5 分) 题目 代码 7-2 世÷我=佬 (5 分) 题目 注意点 我会带着你远行/ 2023年10月03日 18:26/ 0 赞/ 14 阅读
相关 团队程序设计天梯赛-寒假训练1总结 文章目录 7-6 情人节 (15 分) 题目 知识点 代码 7-7 吃火锅 (15 分) 题目 灰太狼/ 2023年10月03日 18:26/ 0 赞/ 16 阅读
相关 团队程序设计天梯赛-1.21排位赛总结 文章目录 7-5 一帮一 (15 分) 题目 思路 知识点 代码 7-6 考试座位号 (15 分) 小灰灰/ 2023年10月03日 18:24/ 0 赞/ 52 阅读
相关 团队程序设计天梯赛-2.24排位赛总结 文章目录 7-3 就不告诉你 (10 分) 题目: 知识点 代码: 7-4 一元多项式求导 (10 分) 今天药忘吃喽~/ 2023年10月03日 18:23/ 0 赞/ 59 阅读
相关 PAT团队程序设计天梯赛L1-035 情人节 题目要求 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0 £神魔★判官ぃ/ 2022年04月03日 16:52/ 0 赞/ 294 阅读
还没有评论,来说两句吧...