2016暑假计划

树，一种十分优美的数据结构，因为它本身就具有的递归性，所以它和子树见能相互传递很多信息，还因为它作为被限制的图在上面可进行的操作更多，所以各种用于不同地方的树都出现了，二叉树、三叉树、静态搜索树、AVL树，线段树、SPLAY树，后缀树等等.. 枚举那么多种数据结构只是想说树方面的内容相当多，本专辑只针对在树上的动态规划，即树形DP.做树形DP一般步骤是先将树转换为有根树，然后在树上进行深搜操作，从子节点或子树中返回信息层层往上更新至根节点。这里面的关键就是返回的信息部分，这个也没一般性的东西可讲，因为每道题目要求做的事都不尽相同。

题目链接 水题 乱搞。 1/* *********************************************** 2Author :111qqz 3Created Time :2016年03月30日 星期三 23时59分47秒 4File Name :code/cf/#346/A.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33int n,a,b; 34int main() 35{ 36 #ifndef ONLINE_JUDGE 37 freopen("code/in.txt","r",stdin); 38 #endif 39 cin>>n>>a>>b; 40 a = a + b; 41 while (a<=0) a+=n; 42 while (a>n) a-=n; 43 cout<<a<<endl; 44 45 #ifndef ONLINE_JUDGE 46 fclose(stdin); 47 #endif 48 return 0; 49}

题目链接 题意：给出n和k,给出一个长度为n的字符串表示房间的占用情况（0表示没占用，1表示已占用），从n个房间中找出k+1个，使得k+1中的k个距离k+1个中的1个的距离和最小。

https://ac.2333.moe/Problem/view.xhtml?id=1457 题意：求一段区间内数字个数的立方和。 思路：由于一共才1E5,而数字1E9,所以先离散化，再莫队，类似小z的袜子。 注意 ：%lld会WA,要用%I64d

http://acm.hdu.edu.cn/showproblem.php?pid=5610 题意：有重量为a,b两种铁圈每种无限多个…能能否组成一个重量为c且平衡杠铃（中间的杆的重量忽略不计） a,b,c都是整数。 思路：平衡的话。。就是两边重量一样。。那么c为奇数的时候显然不行。 由于有多组答案的时候输出铁圈数之和小的。。。那么我们枚举的话。应该把里面那层枚举的变量放置成重量较大的。。。。