思路
因为要最后钱变多，那么要么存在一个包含s的环，绕一圈后钱变多，要么是通过不断绕正环增加自己的钱。所以本题我们需要找正环。类比Bellman-ford找负环计算即可，不同在于初始dist数组为0。
CodeForces - 8C Looking for Order
思路
做的第一道状压dp题。状压dp通常是用来解一些NP完全（没有多项式时间算法）的问题。当然，这种题的范围一般比较小。状压dp的思路就是使用2进制保存状态（这也是为什么范围比较小的原因之一），比如旅行商问题，我们用数位上的1代表以访问过的点，0则是未访问过。通常状压dp的格式是1
2
3
4
5
6
7for(int i=0;i<(1<<n)-1;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
//dp的转移方程
}
}
}
大部分的时间复杂度为O(n^2log(n))。
一开始想写个O((n^2)(2^n))的，结果似乎会TLE，题目要求的复杂度是O((2^n)n)。对于这道题我们能够发现，选取的顺序其实是无关的。所以我们强制要求顺序取，也就是i之前的物品必须都取了，这个思路最终表现在剪枝上，我们对1-(1<<n-1)的每个数都只在最低0位上进行或1的操作。我们很显然发现每个点都取一次，那么显然时间复杂度为O((2^n)n).
2017 EC-Final 总结
Day 1
热身赛两个队友考四六级去了，就我一个人调机子。。前一个多小时电脑无限连不上网，10多个志愿者一个一个过来让我刷新网页？热身赛的题目是google的kickstart的题，第四题比较简单，一个裸的最小生成树（分析选取过程可以发现是kruskal），然后b题感觉可以三分x再三分y？开始无限乱搞然后无限WA？就这样结束了热身赛，赛后听说三分和模拟退火都能过B，感觉自己裸写三分的能力非常捉急。。在座的各位大佬还是强，花式AK
Day 2
现场赛三道水题，A开始队友想用Lucas结果TLE，然后我来搞发现N范围小可以发现把C(k,n)变成C(n-k,n)，然后使用组合数的递推公式让复杂度来到10^5*100，第一发因为有一个地方忘取模爆long long所以WA了，第二发过了。最后一道水题，判断票位于哪一轮比赛即可，不过我题读完没搞懂赛制？就让另一个队友再读了一遍（大锅，不怎么看世界杯不了解，重复读题有点浪费时间），读完后2发A了。K题陷入了三个人都读不懂题的困境？？？我到最后都没读懂，不过幸好队友脑袋清醒A了。然后我开始无脑推J，J的思路其实就是枚举起点终点然后对每个起点贪心判最近终点距离是不是>=3。这题我推得实在是太慢了，封榜后才推出结论。然后第一发蜜汁TLE，改了个错A了，然后4题到结束。在后面的时间我猜了个C，结论跟正确的就差一点，我本来以为只需要考虑第一个红灯，之后的就都能绿灯了，交了猜想WA，然后队友跟我说让我枚举红灯，我：？？？，队友：？？？我俩交流出了问题，不然C题就A了。然后B题又没读懂。。队友很早就告诉了我D题的题意，我开始觉得能够枚举比例来打表，但后来考虑到存不下就没跟队友说，结果思路其实没问题。。E题大模拟我们没看，题目太长，而且需要的机时太长了。F题用了KMP的next思想，我看了题解才明白，这题是真的不会。G题LCA，没看。H题DP，我居然没看出来。。（大锅）I题似乎是三分，但我们队计算几何不是很好，比赛中没有看。L题推结论推到最后也没推出来。。
总结
- 要加强读题，比赛中两道题因为读题浪费了时间
- 模的时候怎么总是忘了要所有地方都要取模啊？以后最后交的时候一定要检查一遍
- 队友交流的时候最好举两个例子
- CCPC，ecfinal都反映出我dp巨烂无比，寒假把cf所有dp标签的题都刷一遍
就是这些吧，主要原因还是自己水平不够，知识点覆盖太少，接下来准备这两周不弄算法了，专心准备考试，然后寒假好好训练一下，就酱