文章目录
1.[岁月神偷](http://acm./aspnet/Question.aspx?qid=1649)2.[字母移动游戏](http://acm./aspnet/Question.aspx?qid=1653)3.[黑孔雀和小太阳](http://acm./aspnet/Question.aspx?qid=1655)4.[埃及分数](http://acm./aspnet/Question.aspx?qid=1657)5.[探索洞穴](http://acm./aspnet/question.aspx?qid=1658)1.岁月神偷
暴力能过，但是正解是贪心
要使初始状态变为目标状态，我们不仅需要两个状态相邻雕像的相对朝向相同，还需要每个雕像的绝对朝向相同。
观察四种操作，我们可以发现：
操作一，仅改变所有雕像的绝对朝向。
操作四，改变“朱雀”和{“青龙”,“玄武”,“白虎”}的相对朝向。
操作二，改变{“朱雀”,“青龙”}和{“玄武”,“白虎”}的相对朝向。
操作三，改变{“朱雀”,“白虎”}和{“青龙”,“玄武”}的相对朝向。
所以，我们可以按照最少使用操作三、二、四的顺序，修改“玄武”和“白虎”、“青龙”和“玄武”、“朱雀”和“青龙”的相对朝向，最后再用操作一修改绝对朝向，即可使用最少操作达到目标状态。
时间复杂度O(1)。
2.字母移动游戏
直接每个点移一下的话是完全可以在 n n n次内完成的，我们的目的就是尽可能偷点懒，一些点不移动
手玩一下样例以后会发现实际上是求 S S S的子序列和 T T T的子串相同的最大长度
因为我们可以把 S S S选中的这些点不动，其他的放到前面或后面，发现这些点并在了一起，并且相对顺序没变，所以可以做到与 T T T完全相同
具体做法可以使用双指针
时间复杂度 O ( n 2 ) O(n^2) O(n2)
3.黑孔雀和小太阳
当小太阳先手时，手动模拟可以发现只有 n n n是 3 3 3的倍数，且 a i ai ai都为 1 1 1的情况小太阳才会输
（如果熟悉巴什博弈的话，可能不用模拟也能想到 3 3 3这个数）
当黑孔雀先手时，因为黑孔雀想赢所以肯定想转换到上述小太阳会输的状态，
所以小太阳在 n n n是 3 3 3的倍数，且有 n − 1 n-1 n−1个数为 1 1 1时会输（这时黑孔雀只需从不是 1 1 1的那堆石子里拿掉一些石子使状态变为1 1 1），
或者 n n n是 3 3 3的倍数余 1 1 1，且 n − 1 n-1 n−1个数为 1 1 1时会输（此时黑孔雀只需拿掉一堆石子，小太阳就到了必输态）
4.埃及分数
从 1 … i n f 1…inf 1…inf，每一个分母，都有选中和不选中两种状态，如果选中，那么就减去这个分数，没有就是跳过，我们可以逐次放宽项数的限制，即迭代加深搜索。
主要的两个剪枝如下：
1. 1. 1. 限制开头：并不是每次都要从 1 1 1开始遍历分母
假设现在要分解 a b \frac{a}{b} ba，那么分母 b a \frac{b}{a} ab就是起点： 1 b a = a b \frac{1}{\frac{b}{a}}=\frac{a}{b} ab1=ba ，假设起点 s < b a s<\frac{b}{a} s<ab，那么显而易见，起点的分数已经比我们要的总和 a b \frac{a}{b} ba大了。
2. 2. 2. 限制结尾：
比较简单的限制结尾可以这样看：如果我已经找到分母k了，而现在要分解得分数是 a b \frac{a}{b} ba，现在还要找 m m m个单位分数，
那么可以想象：有可能 m k < a b \frac{m}{k}<\frac{a}{b} km<ba，也就是说就算全是 1 k \frac{1}{k} k1，我凑够 m m m个，也达不到 a / b a/b a/b，
那么说明前面的分配方案肯定有无，直接可以 r e t u r n return return了。加上这个剪枝已经可以得到答案了，只是时间有点慢罢了。
5.探索洞穴
因为查询次数较多，范围较大，所以我们记录探索完 i i i个点所需最小 x x x。
设 f [ i ] [ u ] [ 0 / 1 ] f[i][u][0/1] f[i][u][0/1]为探索完 u u u的子树中 i i i个节点（包括自己），是 ( 1 ) (1) (1)否 ( 0 ) (0) (0)回到 u u u的最短路径长
然后在树上每个点做一边背包就好了
要注意的是，做背包时不能从 1 1 1到 n n n枚举，这样总复杂度是 O ( n 3 ) O(n^3) O(n3)的
考虑到 u u u中选的点数一定 ≤ s i z e [ u ] ≤size[u] ≤size[u]，那么 d p dp dp时可以只枚举到 s i z e [ u ] size[u] size[u]
这时就会发现复杂度降为了 O ( n 2 ) O(n^2) O(n2)
原理戳这
#include<cstdio>#include<cstring>const int N=502;int T,i,tot,h[N],l,r,mid,f[N][N][2],n,x,y,z,vis[N],q,sz[N];struct node{int to,ne,w;}e[N<<1];inline char gc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}inline int rd(){int x=0,fl=1;char ch=gc();for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);return x*fl;}inline void wri(int a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);}inline void wln(int a){wri(a),puts("");}inline int min(int x,int y){return x<y?x:y;}void add(int x,int y,int z){e[++tot]=(node){y,h[x],z},h[x]=tot;}void dfs(int u,int fa){f[1][u][1]=0,f[1][u][0]=1e9,sz[u]=1;for (int i=2;i<=n;i++) f[i][u][0]=f[i][u][1]=1e9;for (int i=h[u],v;i;i=e[i].ne)if ((v=e[i].to)!=fa){dfs(v,u),sz[u]+=sz[v];int w=e[i].w;for (int i=sz[u];i>1;i--)for (int j=1;j<i && j<=sz[v];j++)f[i][u][1]=min(f[i][u][1],f[i-j][u][1]+2*w+f[j][v][1]),f[i][u][0]=min(f[i][u][0],min(f[i-j][u][1]+w+min(f[j][v][0],f[j][v][1]),f[j][v][1]+w*2+min(f[i-j][u][0],f[i-j][u][1])));}}int main(){for (T=rd();T;T--){n=rd(),tot=0,memset(h,0,n<<2);for (i=1;i<n;i++) x=rd(),y=rd(),z=rd(),add(x,y,z),add(y,x,z),vis[x]=T;for (i=0;i<n;i++)if (vis[i]!=T) break;dfs(i,-1);for (q=rd();q--;){x=rd(),l=1,r=n;while (l<r){mid=l+r+1>>1;if (f[mid][i][0]<=x) l=mid;else r=mid-1;}wln(l); }}}
