题意：有n种数量无限的方块，每种方块后可以拼接另一个方块，但是只能拼接给定种类的方块，问最多拼接M次能拼接出多少种不同的样式。 这道题中n只有50，很容易想到矩阵快速幂，毕竟这种题已经烂大街了。然而比赛的时候我居然没有读到这道题！！！！！ 重点在于构造转移矩阵，显然如果a后面可以拼接b，那么有tmp[a][b]=1;tmp[a][b]=1;tmp[a][b]=1;代表a->b有一种转移方式，构造完了之后，对这个矩阵自乘m次，那么矩阵的结果tmp′[a][b]tmp'[a][b]tmp′[a][b]代表的就是起点为a，终点为b，经过m次转移的方法数，但是我们要求0次转移 1次转移 2次转移 。。。M次转移的总和，所以把最后一列赋为1，就可以了。 第一次写的时候矩阵构造太挫T了，然后优化了一点勉强过了， 第二次和第三次都是优化过的。 优化过的矩阵构造。 代码1： //author: CHC//First Edit Time: 2015-08-25 21:13#include <iostream>#include <cstdio>#include & ...

题意：给一个包含n个点m条边的无环单向简单图，然后问有多少条多余边。(u,v)(u,v)(u,v)是多余边当且仅当u−>vu->vu−>v不经过(u,v)(u,v)(u,v)这条边。 都说了是无环单向图。因此很容易想到拓扑排序：对于当且点u，如果存在(u,v)(u,v)(u,v)，v可以由u通过另一条路径到达，那么(u,v)(u,v)(u,v)这条边就是多余边，但是这样暴力下来复杂度大概是O(n(n+m))O(n(n+m))O(n(n+m))，然后再乘以一个T(T≤20T \le 20T≤20)，就T了。。我的第一个想法是这么做的。然后交上去真的T了。然后又YY到一种做法。能不能保存有哪些点可以到达当前点，维护每一个点的所能到达点的集合，不过这样一来维护的复杂度是O(n)O(n)O(n)，复杂度也没变。。这个是真的没想到能用位运算优化，后来baidu了说用bitset突然就明白了。用位运算可以优化，空间复杂度可以降为O(N232)O(\frac{N^2}{32})O(32N2​)，而且每一次维护的复杂度可以从O(N)O(N)O(N)降为O(N32)O(\frac{N} ...

题意：给一个n个点m条边的无向图，对于每一条边，输出删掉这条边后不连通的两个点，如果有多个，输出最大的u和最小的v（u < v）。 队友居然没有读到这题！！！我居然没有看这题！！！！。。。= = 桥的定义：删掉一条边，使得图不连通。 边双连通分量：除了桥以外的边所连接起来的点。 当然所有的桥都可以找到（tarjan算法） 这道题的难点应该就是在于输出，找最大的u和最小的v。 对于每一条桥，删掉这条桥之后一定会形成两个连通分量。 可以求这两个连通分量的点的最大值max1和max2，max1和max2必然有一个是n，因此就输出另一个和另一个+1 所以问题就成了找不包含n这个点的连通分量的最大值。 首先将所有的边双连通分量缩点，重建图，然后以n所在边双连通分量为根，找子树的最大值。总体来说还是比较容易想到的。。 代码： //author: CHC//First Edit Time: 2015-08-24 15:30//#pragma comment(linker, "/STACK:102400000,102400000")#include <iostream ...

题意： http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=620&pid=1003 题目求有多少对互为充要条件，很容易看出是直接求强连通分量然后分量再计算就可得出。。但是没想到怎么建图，如果暴力直接建图复杂度达到O(n2)O(n^2)O(n2)这样会TLE的。看了题解后觉得服气了。。对于每个节点记录其子树深度为i的节点，然后新增节点，深度高的向深度低的连边，每个节点连向代表它的真实节点。 代码： //author: CHC//First Edit Time: 2015-08-23 19:58#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#in ...

题意：Victor有一个机器，这个机器每次开启的瞬间会弹出一个小球，之后每隔ww秒会弹出一个小球。因为机器不是很完善，该机器每开启xx秒就得关闭yy秒进行调整，在机器关闭的瞬间可能会有小球弹出，关闭之后一直到下一次开启之前都不会有小球弹出。 0时刻，机器第一次开启，Victor想要知道第nn个小球弹出的时刻，你能够告诉他吗？ 推下公式就行了 //author: CHC//First Edit Time: 2015-08-22 23:13#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long ...

题意：给n个点m条边的图，边有边权，求从1开始走，走过这n个点至少一次的最少边权和。 我没有想到怎么做。。看了题解说是状压DP，恍然大悟。。其实这种类型的题做的不是很多。。没有反应过来。。 因为n比较小只有16， 所以可以把状态压缩起来。dp[s][j]dp[s][j]dp[s][j]代表集合s(s是二进制，对应为为1代表已走过，否则代表没有做过)中的城市都走过，走的最后一个点是j的最小边权，可以建立转移方程dp[s][j]=min(dp[s⊗(1<<i)][j]+dis[i][j])dp[s][j]=min(dp[s\otimes(1<<i)][j]+dis[i][j])dp[s][j]=min(dp[s⊗(1<<i)][j]+dis[i][j]) 代码： //author: CHC//First Edit Time: 2015-08-22 22:33#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#incl ...

题意：给一颗树，定义f(u,v)为u到v路径上的异或结果，现在给定s，要求异或结果为s的路径有多少条。(1,2)和(2,1)只算一种。 根据异或的特性有f(u,v)=f(1,u)f(1,v)，先把f(1,i)的所有i都求出，然后对于每一个u(1~n)如果有f(u,v)=s的话那么有f(1,v)=sf(1,u)，所以求一下f(1,v)有多少个，加起来就行了，最后要特殊讨论下s==0的情况。 //author: CHC//First Edit Time: 2015-08-22 15:41#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>usin ...

SBT:http://blog.csdn.net/acceptedxukai/article/details/6921334 Treap:来源忘了。 有个可以优化的地方，就是将相同值合并为同一点，以后改了再放上来。 题目：hdu 5412 Treap版本1: //author: CHC//First Edit Time: 2015-08-20 12:15#pragma comment(linker, "/STACK:102400000,102400000")#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using ...

题意： 给n个数，然后有两个操作 1.把第i个点的值修改为v 2.求[l,r]区间内第k小的数 树状数组+平衡树。 我写了两份代码：树状数组+SBT和树状数组+Treap 代码： //author: CHC//First Edit Time: 2015-08-20 14:10#pragma comment(linker, "/STACK:102400000,102400000")#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>#include <time.h>using namespace std;typedef ...

题意：A想从0走到n，A每走一单位的距离就要吃一颗糖，现在给出第i个点离0的距离a[i]（保证a[i] < a[i+1]），和每个点买入一颗糖和卖出一颗糖的单价buy[i]和sell[i]，A能携带糖的上限为C，问从0走到n的最小花费。 如何使得花费最小？低价买入&高价卖出这种情况可以使得花费最小，而且走的顺序是定下来的。。必须从0…1…2…3…n，可以这么做，记录走到每个点都满载的情况花费，然后只需要考虑退油该怎么退，退油的时候减去卖价高的，走到每一个点，对于买入价格小于当前卖价的那些油，都合并成当前卖价买入，对于买入价格大于当前买价的那些油，都以原价退回，这里的“原价”不是一定是原价，而是可以为卖出的价格，将退油的时机改为原价买原价卖改为原价买高价卖。 这些操作需要一个双端队列。。 贴标程。。。。 代码： //author: CHC//First Edit Time: 2015-08-17 13:34#include <iostream>#include <cstdio>#include <cstring>#include < ...