DAY1 T1
题意：
- 对于两个互质的数$a,b$,求最小不能用$xa+yb (x>=0,y>=0)$表示的数。
题解：
不妨设$a<b$假设答案为$x$若
$x≡ma$ $mod(b)$ (1≤m≤b−1)
即
$x=ma+nb$ (1≤m≤b−1)
显然当 $n≥0$ 时 $x$可以用 $a, b$表示出来，不合题意。
因此当n=−1时$x$取得最大值，此时$x = ma - b $。
显然当$m$取得最大值$b - 1$时$x$最大，此时$x = (b - 1)a - b = ab - a - b$
因此$ a, b $所表示不出的最大的数是$ab-a-b$
代码：
1 |
|
DAY1 T2
题目太长，请手动点击链接。。。。。。
题解：大大大大模拟，请看代码。
代码：
1 |
|
DAY1 T3
题意:
- 求$dis(1,n)<=MinDis(1,n)+K$的路径数
题解：
- 说实话我觉得这道题作为第三题还是很仁慈的。
- 对于没有零边的7组数据点，我们可以用$f[i][j]$表示从1到n比它们之间最短路大k的方案数，然后根据与1之间最短路的大小从小到大来dp。
这样你就可以拿到70分的好成绩。 - 然后我们来考虑有边长为零的边的情况，显然必须按照拓扑序来更新。那-1的情况呢？？我们只需将零边新建一个图，然后跑拓扑排序，找到一个零环，并且其中的点到1和n的最短路之和小于等于1到n的最短路+k;
- 根据思路我们要正反建图，跑两遍dijkstra和一遍拓扑排序，然后dp。
- 记得清空数组（多组数据。。）
代码如下：
1 |
|
- 下面将粘一个记忆化搜索的代码，比起dp记忆化搜索简短了许多，也快了许多。我们只需反跑一边dijkstra，然后从1向n dfs。在dfs中记录每个状态是否重复出现，从而来判断-1的情况。
代码：
1 |
|
DAY2 T1
题意：
- 给定n点及其属性（需自己建图），问是否能从底走到顶。
题解：
- 按照题意建图，跑dfs就能A掉。
- 用并查集，能连边的就分在一个集合内，最后查询顶面和地面是不是在一个集合内。
代码：
1 |
|
并查集
1 |
|
DAY2 T2
题意：
- 有n个点，m条边，可从任意一个点出发，连一条边的代价是这条边的长度乘上从起点到这条边的始点所经过的点数，求最小代价。
题解：
其实dfs就能拿到一个好分数（60分,如果你还会一些神奇卡常，你就会得到AC的好成绩。但是蒟蒻我并不会。。。。请找这位巨佬
接下来讲记忆化搜索，f[i]表示状态i的最优解,dep[i]表示当前点与起点之间的距离，然后就和dfs很像了。
代码：
dfs(70分)
1 |
|
记忆化搜索（100分）
1 |
|
本文作者：
syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/3a5ac64a.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/3a5ac64a.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！