Timus #1806. Mobile Telegraphs

题目:有n个数,每个数都由10个数字组成。并输入int costs[10];作为传递时间。每两个数之间要是有一位不同或有两位可以通过交换得到则这两个数可以互相传递,且传递时间为costs[有多少位相同的前缀]。输出从第一个数到最后一个数所要的最短时间。

解析:最短路径问题。记录两两之间的时间,用Dijkstra算法求解。

代码解析:
建议写代码前阅读以下条目
1. 存储数的方式可以是string,但是最好是long long,所占位数少,但对最终结果及是否通过没有太大关系。string好判断更简单,用long long判断比较烦,看个人喜好了。
2. 如果你卡在TLE(Time Limit Exceeded)8见此条。若用两个for循环依次记录相互之间的可达性会卡在Test 8。因为输入N非常大,导致超时。解决办法:建立所有数字/字符串的哈希表(map),改变每个数字一位/两位,看是否有相同的数字/字符串在输入中。因为哈希表的查找迅速,尽管改变次数多,但依旧比两个for循环来得快。
3. 如果你卡在WA(Wrong Answer)3见此条。你写的Dijkstra路径记录错误,Dijkstra算法是会更新路径,不是简单的输出此迭代得到的路径最短的点。
4. 如果你卡在WA8见此条。计算可达两点距离时出现错误,可能你写成了if(i == j)应写if(int(name[i] – ‘0’) == j)←对于储存形式为string来说。
5. 如果你卡在MLE(Memory Limit Exceeded)11见此条。在Dijkstra算法中只需要当前point相邻的点即可,并不需要全部的。最好不要在结构体中加入类似于unordered_map <Point*, int> neighbor;导致每个点都储存了可达点的数据,很容易造成内存溢出,并且没有这必要,造成内存浪费。记得new不用之后要delete。
7. 为了更加节省内存,你可以修改unordered_map <Point*, int> neighbor;为vector <int, int> neighbor;这样可能你放在结构体里面也不会MLE。
6. 推荐:
INF = 0x3f3f3f3f;
neighbor用unordered_map存储

Timus #1080. Map Coloring

题目:有k行,每行包含第i个点相邻的点。现有0/1两种颜色,相邻的颜色必须不一样,如果能进行涂色,输出每个点的颜色,如果不能进行涂色,则输出-1。

解析:
1. BFS
2. 我没用那么高级的方法,就只用vector迭代涂色。

Timus #1650. Billionaires

题目:有n个富豪(数据包含:姓名,开始时的所在地,拥有财富),某地财富即为在此的所有富豪财富相加。在接下来的m天,会有k个土豪在某一天晚上离开所在地,在第二天早上到达所在地。求每天拥有财富最多的城市,按照字母表顺序输出某城市财富最多的天数。ps:若某一天有两个及以上的城市财富相同则该天不算在这几个城市的天数中,若最终有城市天数为0则不输出此城市。

解析:该题目逻辑很简单,建立Person和City结构体,Person储存姓名,所在地,财富;City储存城市名,拥有财富。循环查找/插入/删除/更新City和Person中的数据,并找到City中财富最大的城市。

代码分析:你必须建立map或set容器或写自己的Tree结构来完成此题,否则必会超时。比如,如果你用顺序的方式遍历City中最大的城市/城市名必定会超时。
1. 我的解决方法是用map<string, City*>cityptr;用指针快速修改和查找。
2. 更加快捷的方式是map<string, pair<City*, long long>>Person;
3. 傻一点的方法是建立map<string, int>index;这种方法缺点是每次都要更新index。

Python 牛顿法求解多元非线性方程组

代码使用方式可见代码中示例代码。需安装numpy和sympy库。

浙ICP备2021019730-1    浙公网安备 33010902002953号
Copyright © 2022 PanCake