Peterliang

《算法竞赛进阶...

PAT挑战日记(15) 心路历程(1) 未归档(5) 模板(2) 题解(145)

/ 注册

全部文章 / 《算法竞赛进阶指南》系列题解（共4篇）

闇の連鎖

这个题目首先思路是参考书上的，就是一个树上差分的思想，通过观察题目可以发现，一定要先砍主要边，然后才能砍附加边，这样的话，我们可以发现，在一棵生成树里面，如果加上一条附加边的话，会形成一个环，如果首先砍这个环上面的主要边，那么第二次一定要砍这条附加边，才能把树分成两半，这是唯一的，但是如果你砍的不是...

刷题

2021-02-21

0 522

最短Hamilton路径

我们可以先自然想到一个朴素的做法，就是直接通过枚举n个点所以的序列，然后求出每条路的权值和，最后取最小的即可。但是，我们看一下数据范围，发现如果这样算的话时间复杂度为n（n!）。所以我们要想一下用什么办法进行优化，我们发现，对于最多n个点的状态，我们可以用一个二进制进行表示，比如，我们遍历了1,3,...

刷题

2021-02-20

0 597

64位整数乘法

我们可以发现，如果将a和b直接进行相乘的话，那肯定会爆long long。当然，python选手自动忽略。那么，我们可以这样思考，对于任意一个整数，我们都可以用二进制进行表示，也就是用二进制进行拆分，比如：b=2^n+2^(n-1)+...+2^3+2^0.所以我们就可以把ab=a2^n+a2^(n...

刷题

2021-02-16

0 705

a^b

对于这个题目，我们可以知道，其实就是一个快速幂的写法。 //非递归的写法 #include<iostream> using namespace std; typedef long long ll; int main(){ ll a,b,mod; cin>>a&...

刷题

2021-02-16

0 573