promiser
- 浏览: 76671 次
- 性别:
- 来自: 广州
-
最近访客 更多访客>>
最新评论
-
promiser：
xlaohe1 写道这是C吗？看不懂呀～加上注释就好了。说明也 ...
bzoj1071: [SCOI2007]组队 -
xlaohe1：
这是C吗？看不懂呀～加上注释就好了。说明也行啊，算法思想也可以 ...
bzoj1071: [SCOI2007]组队
文章列表
我几个星期才会更新一次博客，所以如果我的题解不是太详尽，还请大家见谅
我的代码的头文件在这里，平时就不放上去了，有可能会有更新
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
# ...
这。。是一题神题，我就不多说了，太神了（对于我来说）
太弱了，众神犇可望不可即
题解：
话说在前……有公式恐惧症的勿读此文……
用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的数字串集合。
位压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 &l ...
没处理一个元素，就要维护他旁边的差
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("%I ...
咳，这是道水题，我不想多说。。
太弱太弱，做了这么久
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>
#include <stac ...
总的说，这道题目就是要求一个双关键字的最长序列，并让你数出来
关键字是给你的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+ ...
我用的是恶心的竹席（zhuxi擦，尽然是禁忌词）树
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <stack>
#include <deque>
#include <queue>
#include <map>
...
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)
选出来的点只能是不能向流通的，所以就是从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, ...
bzoj1103: [POI2007]大都市meg
- 博客分类：
- oi
利用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 ...
bzoj1096: [ZJOI2007]仓库建设
- 博客分类：
- oi
《用单调性优化动态规划》
这个是分析，超详细
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", &a ...
树分治，我写的是点分治，把中心点拿出来，左右两边看成他的左右孩子就可以了，同时用堆维护，我偷懒用了priority_queue
我怎么调都wa，没办法以后再填坑吧
代码：no
先缩点，重新建图，DP 就行了，类似于树形 DP，先求出从每个点出发，能走的最长链是多长，统计最长的那条就是最大半连通子图的点的数量
但是，超时，你妹，我也没办法
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#includ ...
同bzoj1068: [SCOI2007]压缩，一样的做法，思路，详解请看那篇文章
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <stack>
#include <deque>
#include <queue>
#incl ...
bzoj1089: [SCOI2003]严格n元树
- 博客分类：
- oi
题解：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 ...