ITeye博客

Be A normal OIer

promiser · 共 72 篇文章

[置顶] 关于代码的补充

我几个星期才会更新一次博客,所以如果我的题解不是太详尽,还请大家见谅 我的代码的头文件在这里,平时就不放上去了,有可能会有更新 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <vector> #include <deque> #include <map> #include <stack> #include <queue> typedef long long LL…

2013-08-27 15:03 · oi · 评论(0)

bzoj1152: [CTSC2006]歌唱王国Singleland

这。。是一题神题,我就不多说了,太神了(对于我来说) 太弱了,众神犇可望不可即 题解: 话说在前……有公式恐惧症的勿读此文…… 用pow(a, b)代表a的b次方。 用Σ(a, b)代表条件为a,对b求和。 用|a|代表字符串a的长度。 用a . b代表数字串a和数字串b串联后的字符串。 而a + b代表数字串集合a与数字串集合b的并集。 数字a既可当数字a也可当只包括a的数字串。 数字串a既可当数字串a也可当只包括a的数字串集合。 设名字为数字串s 设数字串集合P = {a | a是s的后缀 且 a≠空串 且 a≠s 且 s去掉a这个后缀后,剩下的字符串既是s的前缀也是s的后缀} (这句话…

2013-10-21 21:24 · oi · 评论(0)

bzoj1151: [CTSC2007]动物园zoo

位压DP,就是五个位,表示第i个人看到的那5个动物的情况,最开始枚举有哪些动物走了,转移就很显然了 const int N = 100010, D = 31, M = 32; struct Node { int Start, Love, Afraid; inline void Read(int n) { int F, L, x; scanf("%d%d%d", &Start, &F, &L), Start--; Rep(j, F) scanf("%d", &x), Afraid |= 1 << ((x - Start - 1 + n) % n); Rep(j, L) scanf("%d", …

2013-10-21 21:19 · oi · 评论(0)

bzoj1150: [CTSC2007]数据备份Backup

没处理一个元素,就要维护他旁边的差 const int N = 100010; typedef pair<LL, int> PLI; priority_queue<PLI, vector<PLI>, greater<PLI> > Q; int n, m; LL Dat[N]; int L[N], R[N]; bool Okay[N]; inline void Input() { scanf("%d%d", &n, &m); For(i, 1, n) scanf("%I64d", &Dat[i]); } inline void Solve() { /* Init Begin */ Dat[n+…

2013-10-21 17:22 · oi · 评论(0)

bzoj1149: [CTSC2007]风玲Mobiles

咳,这是道水题,我不想多说。。 太弱太弱,做了这么久 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <vector> #include <deque> #include <map> #include <stack> #include <queue> typedef long long LL; typedef double DB; typedef unsigned…

2013-10-21 16:57 · oi · 评论(0)

bzoj1148: [CTSC2007]挂缀pendant

总的说,这道题目就是要求一个双关键字的最长序列,并让你数出来 关键字是给你的ci,wi 若我们按照ci+wi来进行排序,我们可以证明最有序列必然存在于这个排过序的序列中 证明: 我们令S[i]=W[1]+..+W[I] 若右移最有排列不是按照W[i]+C[i]排序,则必有 W[x]+C[x]>W[x+1]+C[x+1] 那他还能承受min{C[x]-S[x-1], C[x+1]-W[x]-S[x-1]} 若我们的排序的决定是错误的,我们将他交换,结果就会变优 那他能承受min{C[x+1]-S[x-1], C[x]-S[x-1]-W[x+1]} 显然 C[x+1]-S[x-1]>C[x+1]…

2013-10-21 16:53 · oi · 评论(0)

bzoj1146: [CTSC2008]网络管理Network

我用的是恶心的竹席(zhuxi擦,尽然是禁忌词)树 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <stack> #include <deque> #include <queue> #include <map> #define max( x , y ) ( ( x ) > ( y ) ? ( x ) : ( y ) ) #define min( x , y ) …

2013-10-16 10:03 · oi · 评论(0)

bzoj1145: [CTSC2008]图腾totem

http://hi.baidu.com/wjbzbmr/item/03de2de8d025eb07560f1dd0 设f(xxxx)表示排序xxx出现的数量。。 那么我们要求的是f(1324)-f(1243)-f(1432) 注意到f(1243)=f(12xx)-f(1234)。。这两个都很好求。。所以1243解决了。。 但其他两个几乎不可做啊。。题目既然让我们相减,这两个式子必然是有所关联的。。 f(1324)-f(1432) 我们尝试着在两边都+上一个f。。 (f(1324)+f(1423))-(f(1432)+f(1423)) =f(1x2x)-f(14xx) 这两个都是线段树可做的。…

2013-10-16 10:01 · oi · 评论(0)

bzoj1143: [CTSC2008]祭祀river

选出来的点只能是不能向流通的,所以就是从n个点的二分图(相连通的连边)里面,选出最大独立集 const int N = 110; int n, m; bool Graph[N][N], Okay[N]; int Disx[N], Disy[N], Que[N], Head, Tail; int Match[N], Vis[N]; inline void Input() { scanf("%d%d", &n, &m); Rep(i, m) { int x, y; scanf("%d%d", &x, &y); Graph[x][y] = 1; } } inline bool Bfs() { bo…

2013-10-16 09:59 · oi · 评论(0)

bzoj1103: [POI2007]大都市meg

利用dfs序的性质,使用树状数组统计 记录一下每个点进入dfs和退出dfs的时间,将进入的权值赋为1,退出的赋为-1,。每次修改公路,就把这两个值都修改为0,输出前缀和 const int N = 2500010; struct Edge { int V; Edge *Next; Edge() {} Edge(int _V, Edge *_Next) : V(_V), Next(_Next) {} } *First[N]; int n, m; int In[N], Out[N], Tot, Count[N << 1]; inline void Input() { scanf("%d", &n…

2013-10-16 09:56 · oi · 评论(0)

bzoj1096: [ZJOI2007]仓库建设

《用单调性优化动态规划》 这个是分析,超详细 const int N = 1000010; const DB Eps = 0.000001; struct Node { int l, r, ch; Node() {} Node(int _l, int _r, int _ch) : l(_l), r(_r), ch(_ch) {} }; int C[N], X[N], n; LL S[N], Sum[N], Dp[N]; inline void Input() { int x, p; scanf("%d", &n); For(i, 1, n) scanf("%d%d%d", &x, &p, &…

2013-10-16 09:53 · oi · 评论(0)

bzoj1095: [ZJOI2007]Hide 捉迷藏

树分治,我写的是点分治,把中心点拿出来,左右两边看成他的左右孩子就可以了,同时用堆维护,我偷懒用了priority_queue 我怎么调都wa,没办法以后再填坑吧 代码:no

2013-09-22 21:50 · oi · 评论(0)

bzoj1093: [ZJOI2007]最大半连通子图

先缩点,重新建图,DP 就行了,类似于树形 DP,先求出从每个点出发,能走的最长链是多长,统计最长的那条就是最大半连通子图的点的数量 但是,超时,你妹,我也没办法 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <vector> #include <deque> #include <map> #include <stack> #include <queue> ty…

2013-09-22 21:47 · oi · 评论(0)

bzoj1090: [SCOI2003]字符串折叠

同bzoj1068: [SCOI2007]压缩,一样的做法,思路,详解请看那篇文章 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <stack> #include <deque> #include <queue> #include <map> #include <vector> #include <set> typedef long long LL; typed…

2013-09-22 21:43 · oi · 评论(0)

bzoj1089: [SCOI2003]严格n元树

题解: http://hi.baidu.com/gzh19950711/item/c3ac0f0b0ad3b0c190571881 超级详细,我就不说了 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <stack> #include <deque> #include <queue> #include <map> #include <vector> #includ…

2013-09-22 21:41 · oi · 评论(0)