[bzoj\lydsy\大视野在线测评]题解(持续更新）
目录：
一、DP
二、图论
1、最短路
2、强连通分量
三、利用单调性维护
四、贪心
五、数据结构
1、并查集
六、数学
1、计数问题
2、数学分析
七、博弈
八、搜索
//
一、DP：
1003 ：
（参见 http://hi.baidu.com/aekdycoin/item/88a8be0bf621c6314ac4a3d5 ）
首先对于某个时间段[i,j],我们可以轻松暴力删点以后求1-n的最短路然后就是一个区间DP的问题
DP[i][j] 表示从第 i 天到第 j天的最优值,于是方程很显然:
DP[i][j] = min{DP[i][w] + K + DP[w+1][j]} (i<=w
1 /* *************************************************************2 Problem: 1003
3 User: pikapika
4 Language: C++
5 Result: Accepted
6 Time:40 ms
7 Memory:1396 kb
8 *************************************************************** */
9
10 #include
11 #include
12 #include < string>
13 #include
14 #include
15 #include
可以用单调栈来做，维护一个单调增的栈（如果Ai > Aj 并且 i > j， 那么Ai 总是比 Aj 更加有可能成为答案），然后每次二分查找答案。
当然，更加暴力的方法是直接线段树搞。
1 /* *************************************************************2 Problem: 1012
3 User: pikapika
4 Language: C++
5 Result: Accepted
6 Time:452 ms
7 Memory:2836 kb
8 *************************************************************** */
9
10 #include
11 #include
12 #include
题目可以看成n个格子，每个格子可以染1到m任意一个颜色，问有多少种情况存在任意两个相邻格子同色。
首先我们知道总共的染色方案是m^n次，那么我们只要反过来求有多少种不越狱的情况就可以了。
第一个格子有m种染色方案，后面的每个格子都不可以和前面一个格子同色，即m-1种方案，所以答案就是m^n - m * (m - 1) ^ (n - 1)
用快速幂可以迅速求出答案
1 /* *************************************************************2 Problem: 1008
3 User: pikapika
4 Language: C++
5 Result: Accepted
6 Time:0 ms
7 Memory:1272 kb
8 *************************************************************** */
9
10 #include
11 #include
12 #include
经典的ANTI-NIM博弈问题
在anti-Nim游戏中，先手必胜当且仅当：
（1）所有堆的石子数都为1且游戏的SG值为0；
（2）有些堆的石子数大于1且游戏的SG值不为0。
参见2009年国家集训队论文贾志豪论文《组合游戏略述 ——浅谈SG游戏的若干拓展及变形》
（ http://wenku.baidu.com/view/25540742a8956bec0975e3a8.html )
1 /* *************************************************************2 Problem: 1022
3 User: pikapika
4 Language: C++
5 Result: Accepted
6 Time:40 ms
7 Memory:1272 kb
8 *************************************************************** */
9
10 #include
11 #include
12 #include
搜索
首先，要求分割出来的n块面积都一样，我们枚举当前矩形被切成两块时这两块矩形还将在以后被切几刀，于是相应的边长也被分成了对应比例。
1 /* *************************************************************2 Problem: 1024
3 User: pikapika
4 Language: C++
5 Result: Accepted
6 Time:184 ms
7 Memory:804 kb
8 *************************************************************** */
9
10 #include
11 #include
12
13 const double INF = 1e100;
14
15 double dfs( double x, double y, int c) {
16 if (y > x) std::swap(x, y);
17 if ( 1 == c) return x / y;
18 else {
19 double re = INF;
20 for ( int i = 1; i < c; ++i) {
21 re = std::min(re, std::max(dfs(x, y * i * ( 1. / c), i), dfs(x, y - y * i * ( 1. / c), c - i)));
22 }
23 for ( int i = 1; i < c; ++i) {
24 re = std::min(re, std::max(dfs(x * i * ( 1. / c), y, i), dfs(x - x * i * ( 1. / c), y, c - i)));
25 }
26 return re;
27 }
28 }
29 int main() {
30 double x, y;
31 int c;
32 while ( 3 == scanf( " %lf%lf%d ", &x, &y, &c)) {
33 printf( " %.6f\n ", dfs(x, y, c));
34 }
35 return 0;
36 } View Code
转载于:https://www.cnblogs.com/hewifi/p/3307793.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！