promiser
- 浏览: 77059 次
- 性别:
- 来自: 广州
-
最近访客 更多访客>>
最新评论
-
promiser：
xlaohe1 写道这是C吗？看不懂呀～加上注释就好了。说明也 ...
bzoj1071: [SCOI2007]组队 -
xlaohe1：
这是C吗？看不懂呀～加上注释就好了。说明也行啊，算法思想也可以 ...
bzoj1071: [SCOI2007]组队
文章列表
bzoj1088: [SCOI2005]扫雷Mine
- 博客分类：
- oi
枚举第一个格子有无雷，O(n)检验
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <stack>
#include <deque>
#include <queue>
#include <map>
#includ ...
状态压缩Dp，要与处理哪个可以转移到哪个
const int N = 10, K = 100, M = 1024;
struct Edge {
int V;
Edge *Next;
Edge() {}
Edge(int _V, Edge *_Next) : V(_V), Next(_Next) {}
} *Fir[M];
vector<int> State, Num;
int n, m;
LL Dp[N][K][M], Tot;
inline void Input() {
scanf("%d%d", &n, & ...
bzoj1086: [SCOI2005]王室联邦
- 博客分类：
- oi
求强联通分块，让其变成一棵树，对于书上每一个点（强连通分量，其内部点数为权值），对于他每一个孩子，若>k就分成一个省，省会为该点，最后再加上该点的权值，若>k，分省，否则递归上去给父亲，最后出来要特殊处理
const int N = 1010;
typedef vector<int> VI;
struct Edge {
int v;
Edge *Next;
Edge() {}
Edge(int _v, Edge *_Next) : v(_v), Next(_Next) {}
} *Fir[N];
int n, m;
int Belong[N] ...
bzoj1085: [SCOI2005]骑士精神
- 博客分类：
- oi
迭代加深搜索，枚举层数，估价函数就是当前状态与目标状态不同的个数，鉴于此题代码写得比较丑，不发了
bzoj1084: [SCOI2005]最大子矩阵
- 博客分类：
- oi
m<=2，分m==1和m==2的情况讨论，，然后就是一道水DP题，转移见代码
const int N = 110;
int n, m, k, dat[2][N];
int S[4][N];
int f[N][N] = {0};
inline void sol1() {
For(i, 1, k)
For(j, 1, n) {
f[i][j] = f[i][j - 1];
For(l, 0, j - 1)
f[i][j] = max(f[i][j], f[i - 1][l] + S[1][j] - S[1][l]);
}
print ...
第一问n-1无疑
第二问最小生成树kruskal（不知道有没有算错）算法的改进版
const int N = 310, M = 90010;
struct Edge {
int u, v, Val;
inline bool operator <(const Edge &B) const { return Val < B.Val; }
//friend bool operator <(const Edge &A, const Edge &B) { return A.Val < B.Val; }
} E[M];
int n, ...
bzoj1082: [SCOI2005]栅栏
- 博客分类：
- oi
这里有题解：http://blog.sina.com.cn/s/blog_8442ec3b01017ks5.html
请看神剪枝
二分能够得到多少木板，然后用Dfs验证能否全部得到1..mid这些木块。
这样会有1个点过不了。
这道题加一个优化：如果当前这个木块和前一个木块相同（倒着枚举小木块），那么搜大木块的时候就从当前这个大木块开始，具体看代码。
由于这是USACO题目的弱化版，如果是USACO的话，还有一个优化才能过：用waste表示每一个已经裁过的木材浪费的木材和，所谓浪费的木材就是最小的木块都比它大，那么他当前就已经裁不出任何木块了。就把这个木材加到waste ...
bzoj1081: [SCOI2005]超级格雷码
- 博客分类：
- oi
水题，大水题，只不过bzoj上没有设special judge，WA了几次
const int N = 20;
int Dat[N], Base[N], Sum;
int n, m;
inline void Input() {
scanf("%d%d", &n, &m);
Sum = 1;
Rep(i, n) Sum *= m, Base[i] = 1;
}
inline void Write() {
Sum--;
Rep(i, n) printf("%c", Dat[i] < 10 ? '0 ...
bzoj1080: [SCOI2008]劣质编码
- 博客分类：
- oi
正解我不太懂，最后使用clj的神暴力水过去了，总而言之我还是太弱了
typedef vector<int> VI;
const int N = 40;
map<VI, int> Hash;
queue<VI> Q;
int n;
string Dat[N];
inline void Input() {
scanf("%d", &n);
Rep(i, n) cin >> Dat[i];
}
inline void write(int Ans) {
printf("%d\n& ...
bzoj1079: [SCOI2008]着色方案
- 博客分类：
- oi
我写的是状态压缩DP（其实没有必要），所有的燃料其实都可以按照能够染多少格子来划分种类，那至多只有5种染料，马上状压（也不算状压，记忆化搜索吧）
const int N = 20, Mod = 1000000007;
map<int, int> Dp;
map<int, bool> Vis;
int n, Dat[6], St, Base[6];
inline void Input() {
int x;
for(scanf("%d", &n); n--; ) scanf("%d", &x), ...
非常详细，我就不写了
传送门：http://www.cppblog.com/MatoNo1/archive/2012/10/07/192131.html
const int N = 60;
struct Node {
int V, Lc, Rc, Size, C[N];
} Tr[N];
int n;
int L[N], R[N], C[N];
inline void Input() {
scanf("%d", &n);
For(i, 1, n) {
int t;
scanf("%d", &t) ...
bzoj1077: [SCOI2008]天平
- 博客分类：
- oi
恶心题，代码完全抄袭某神，请无视
const int N = 60;
struct Edge {
int v;
Edge *next;
Edge(int v, Edge* next) : v(v), next(next){}
} *Fir1[N], *Fir2[N];
int A, B, n;
char Dat[N][N];
int Fa[N];
int Ans1, Ans2, Ans3;
bool E[N][N];
int Cnt[N];
inline int Find(int x) { return (Fa[x] == x) ? x : Fa[x] = ...
bzoj1076: [SCOI2008]奖励关
- 博客分类：
- oi
倒推期望Dp
const int N = 16, M = 110;
int Need[N], n, k;
DB Dat[N], Dp[M][1 << N];
inline void Input() {
scanf("%d%d", &k, &n);
Rep(i, n) {
int x;
Need[i] = 0;
scanf("%lf", &Dat[i]);
while(scanf("%d", &x), x--) Need[i] |= 1 <& ...
这个就是个爆搜+剪枝
1.预处理每个点到终点的最快时间和最慢时间，最快到达都比t2慢，或者最慢到达都比t1快，此时剪枝。
2.Hash判重
3.如果当前时间加上最快到终点时间、当前油量加上到终点所需的最少油量都不如已经搜到的答案优，剪枝。
这样就可以开开心心AC了
const int N = 15;
const DB Eps = 1e-8;
struct State {
int Ox, Oy;
State() {}
State(int _Ox, int _Oy) : Ox(_Ox), Oy(_Oy) {}
inline State operator -(State ...
从后往前逆推
const int N = 10;
struct Point {
DB Ox, Oy;
Point(){}
Point(DB _Ox, DB _Oy) : Ox(_Ox), Oy(_Oy) {}
friend Point operator -(Point a, Point b) { return Point(a.Ox-b.Ox, a.Oy-b.Oy); }
friend Point operator + (Point a, Point b){ return Point(a.Ox + b.Ox, a.Oy + b.Oy); }
DB Len() { r ...