promiser
- 浏览: 76932 次
- 性别:
- 来自: 广州
-
最近访客 更多访客>>
最新评论
-
promiser：
xlaohe1 写道这是C吗？看不懂呀～加上注释就好了。说明也 ...
bzoj1071: [SCOI2007]组队 -
xlaohe1：
这是C吗？看不懂呀～加上注释就好了。说明也行啊，算法思想也可以 ...
bzoj1071: [SCOI2007]组队
文章列表
bzoj1073: [SCOI2007]kshort
- 博客分类：
- oi
擦，栈溢出
这个做法么，就是明显的二分+爆搜验证取最优解了
// please forgive my foolish, I Cheat the last two points
const int N = 60;
typedef pair<int, int> II;
vector<II> E[N], Back[N];
int n, m, Kth, S, T;
int G[N], Cnt[N], Num, Limit, Now;
bool Vis[N];
queue<int> Q;
bool Cheat;
inline void Inp ...
分半搜索，枚举那几个数字分成两半的方案，然后暴力看它们组合Mod d 的余数，并记录，left[i]表示左边的有多少组合mod d = i ，right[i] 也相同，然后用简单数学方法合并
const int N = 15, M = 1010;
int Dat[N], TDat[N], Cnt[2][M], Ans;
int n, Mod;
char S[N];
inline void Solve() ;
inline void NextState(int x, int Pick) ;
inline void Input() {
int T;
for(scanf(& ...
bzoj1071: [SCOI2007]组队
- 博客分类：
- oi
利用单调性+堆+乱搞即可
const int N = 5010;
struct Node {
int Speed, Height, Val;
friend bool operator <(Node A, Node B) { return A.Val < B.Val; }
} Dat[N];
priority_queue<Node> Q;
int n, A, B, C;
inline void Input() {
scanf("%d%d%d%d", &n, &A, &B, &C);
For ...
bzoj1070: [SCOI2007]修车
- 博客分类：
- oi
网络流，将维修人员拆成N个，记为P(i,j)，然后每辆车对P(i,j)连一条容量为1，权为j*time[i][j]的边，表示让第i个维修人员在倒数第j的位置修这辆车，于是会导到剩下的所有人多等j*time[i][j]的时间
const int N = 700;
struct Edge {
int V, Val, Cost;
Edge *Next, *Pair;
Edge() {}
Edge(int _V, int _Val, int _Cost, Edge *_Next) :
V(_V), Val(_Val), Cost(_Cost), Next(_Next) {} ...
bzoj1069: [SCOI2007]最大土地面积
- 博客分类：
- oi
1、O(N^2)地枚举对角线。
2、分别求出这条对角线左右两侧到这条线段所在直线距离最大的点，记为l、r，相当于求出以这条对角线为底、左右两侧分别高最大（面积最大）的三角形。
3、对于枚举的每条对角线，计算四边形面积并更新答案。
这样的时间复杂度是O(N^3)的，不能承受，一个优化就是，可以证明：如果按照逆时针顺序存储凸包，那么对于对角线(i,j+1)，与之相对应的l、r分别在对角线(i,j)的逆时针方向，也就是说可以省略一些不必要的枚举过程。对于对角线(i,j+1)的l、r，可以直接从对角线(i,j)的l、r开始枚举。
传送门：http://hi.baidu.com/poet_shy ...
状态定义是（l,r,t）表示l到r的字串，t表示中间能否放M,注意最开始有个M
const int N = 60;
char Dat[N];
int Dp[N][N][2];
bool Vis[N][N][2];
inline void Input() {
scanf("%s", Dat + 1);
}
inline bool Match(int A, int B) {
int Len = B - A;
Rep(i, Len)
if(Dat[A + i] ^ Dat[B + i]) return 0;
return 1;
}
...
最水最水最水的一道题目， 完全不需要多说
const int N = 50010, D = 17;
struct Node {
int Year, Water;
Node() {}
Node(int _Year, int _Water) : Year(_Year), Water(_Water) {}
} Dat[N];
int Dp[D][N];
int n, m;
inline void Input() {
scanf("%d", &n);
For(i, 1, n) scanf("%d%d", & ...
bzoj1066: [SCOI2007]蜥蜴
- 博客分类：
- oi
每个点(i,j)，(i,j)→(i,j)'连上容量为h[i][j]的边。(i,j)为入点。(i,j)'为出点
对于所有有蜥蜴的点，从S给它连一条容量为1的边。对于所有可以跳到外面的点，连到T，容量是h[i][j]。
网络流跑一遍
const int N = 30;
struct Point {
int Ox, Oy, H;
Point() {}
Point(int _Ox, int _Oy, int _H) : Ox(_Ox), Oy(_Oy), H(_H) {}
} Dat[sqr(N)], Start[sqr(N)];
struct Edge {
int V, ...
bzoj1065: [NOI2008]奥运物流
- 博客分类：
- oi
传送门：http://blog.csdn.net/whjpji/article/details/7593329
const int N = 70;
int Fa[N], n, m;
DB Dp[N][N][N], S[N][N][N];
DB C[N], F[N], K[N], Ans;
inline void Input() {
scanf("%d%d%lf", &n, &m, &K[1]);
For(i, 2, n) K[i] = K[i - 1] * K[1];
For(i, 1, n) scanf("%d& ...
bzoj1064: [Noi2008]假面舞会
- 博客分类：
- oi
传送门：http://blog.sina.com.cn/s/blog_86942b1401015r81.html
const int N = 100010, M = 1000010;
struct Edge {
int V, Val;
Edge *Next;
Edge() {}
Edge(int _V, int _Val, Edge *_Next) : V(_V), Val(_Val), Next(_Next) {}
} *Fir[N];
int n, m;
int Dep[N];
bool Vis[N];
vector<int> C;
i ...
再来一道神题
题解传送门：https://www.byvoid.com/blog/noi-2008-design/
const int N = 100010;
struct Edge {
int V;
Edge *Next;
Edge() {}
Edge(int _V, Edge *_Next) : V(_V), Next(_Next) {}
} *Fir[N];
int Q[N], Head, Tail, Fa[N];
int n, m, Mod;
bool Vis[3][N][11];
LL Dp[3][N][11];
inline void Inp ...
bzoj1062: [NOI2008]糖果雨
- 博客分类：
- oi
又是一道神题
题解传送门：http://blog.sina.com.cn/s/blog_86942b1401015yln.html
代码完全抄袭某神，请无视掉
const int N = 1010, M = 1000010;
struct Dat {
int t, p;
} Dat[M];
int C1[N * 3][N << 2], C2[N * 3][N << 2];
int n, m, Len, T;
inline void Input() {
scanf("%d%d", &T, &Len), n = ...
这是一道网络流神题
题解传送门：https://www.byvoid.com/blog/noi-2008-employee/
const int N = 1100;
struct node {
int From, To, Next, Cost, Pair, Val;
} Edge[N * 40];
int First[N], pre[N * 40], Tot;
int n, m, S, T, Dat[N];
int Ans, Dis[N];
bool InQ[N];
queue<int> Q;
inline void Add(int x, int ...
在一个矩阵中任意一个黑色点都可以通过旋转到任意一个位置，所以只要尽可能的选择一些黑点，让每一行&每一列都用且仅用一次，二分匹配就显然了
以前打过一种快速二分匹配算法，但现在忘，只能打普通的二分匹配算法。那种快速二分匹配算法是用了网络流的思想，用BFS重标号，多路增广
const int N = 210;
int n, Dat[N][N], Link[N];
bool Vis[N];
inline void Input() {
clr(Dat, 0), clr(Link, 0);
scanf("%d",&n);
For ...
bzoj1058: [ZJOI2007]报表统计
- 博客分类：
- oi
一看就知道是数据结构的题目，乍一看可以用STL水过去
题目中有几个细节要注意，这里不说看代码
const int N = 500010;
int n, m, Dat[N], Sort[N];
set<int> s1, s2;
map<int, int> Hash;
vector<int> g[N];
int Ans1, Ans2;
inline void Input() {
scanf("%d%d", &n, &m);
Ans2 = INF, Ans1 = INF;
Rep(i, n) {
...