promiser
- 浏览: 76673 次
- 性别:
- 来自: 广州
-
最近访客 更多访客>>
最新评论
-
promiser：
xlaohe1 写道这是C吗？看不懂呀～加上注释就好了。说明也 ...
bzoj1071: [SCOI2007]组队 -
xlaohe1：
这是C吗？看不懂呀～加上注释就好了。说明也行啊，算法思想也可以 ...
bzoj1071: [SCOI2007]组队
文章列表
bzoj1042: [HAOI2008]硬币购物
- 博客分类：
- oi
Dp[i]表示硬币个数不受限制，且面额为i的方案数，那受限制的方案数就等于减去当每种硬币超过限制的方案数，又因为有重复，所以要加回来，整个过程比较抽象
const int N = 4, S = 100010;
LL Dp[S] = {0};
int Dat[N], D[N], T, s;
inline void Input() {
Rep(i, 4) scanf("%d", &Dat[i]);
scanf("%d", &T);
}
inline LL Dfs(int Now, bool flag, int ...
bzoj1041: [HAOI2008]圆上的整点
- 博客分类：
- oi
设a=m^2-n^2,b=2*m*n,c=m^2+n^2,则已经满足a^2+b^2=c^2,枚举m，n（m>n），只统计一个象限的答案，最后答案乘以4
LL r, n, m;
typedef pair<int, int> II;
set<II> S;
inline void Cal(int d) {
LL r = ::r / d;
for(n = 1, m = 1; sqr(m) < r; m++);
while(n < m) {
while(n < m && sqr(n) + sqr(m) > ...
bzoj1040: [ZJOI2008]骑士
- 博客分类：
- oi
树形DP，加上环状DP
环状DP就把它当成一条链来做，特殊处理头与最后的关系
const int N = 1000010;
LL Dp[N][2];
int n, Dat[N], C[N], Cnt[N] = {0};
inline void Input() {
scanf("%d", &n);
For(i, 1, n) {
scanf("%d%d", &Dat[i], &C[i]);
Dp[i][0] = 0, Dp[i][1] = Dat[i], Cnt[C[i]]++;
}
}
...
bzoj1038: [ZJOI2008]瞭望塔
- 博客分类：
- oi
半平面交求最低点，较裸
此题答案非常大，用INFwa了很久
const DB eps = 0.000001;
const int N = 310;
int n, m;
inline int Equal(DB a, DB b) {
if(fabs(a - b) < eps) return 0;
return a < b ? -1 : 1;
}
struct Point {
DB x, y;
Point(DB _x, DB _y) : x(_x), y(_y) {}
Point() {}
} P[N];
struct Line {
DB ...
Dp[i][j][k1][k2]表示前i个人，有j个男孩，从后往前，男孩最多比女孩多k1个，女孩最多比男孩多k2个的方案数
Dp[Now][j + 1][k1 + 1][max(k2 - 1, 0)] += Dp[Last][j][k1][k2]
Dp[Now][j][max(k1 - 1, 0)][k2 + 1] += Dp[Last][j][k1][k2]
const int N = 160, K = 25, Mod = 12345678;
int n, m, k, Dp[2][N][K][K];
inline void Input() {
scanf("%d% ...
两个数组从小到大排序
最小和最大的能赢就赢 否则 用最小的打最大的，证明略
const int N = 100010;
int Dat[2][N], n;
inline void Input() {
scanf("%d", &n);
Rep(i, 2)
Rep(j, n) scanf("%d", &Dat[i][j]);
sort(Dat[0], Dat[0] + n), sort(Dat[1], Dat[1] + n);
}
inline int Work(int *A, int *B) {
i ...
恶心的模拟题，不多说
const int N = 30, dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
struct Ant {
int x, y, lx, ly;
int age, life, blood, level;
bool cake;
friend bool operator<(Ant a, Ant b) {
return a.age > b.age;
}
} ant[N];
struct Node {
int x, y;
} Dat[N];
int n, m, S, d, r, nu ...
比较裸的AC自动机+Dp，F[i][j][k]表示第i个节点，走了j步，有无有单词(k)的方案数题。
SPOJ的GEN，是这道的加强版。
const int N = 26, M = 110, Maxn = 7010, Mod = 10007;
struct Node {
Node *Child[N], *Next;
int Dat, Id;
bool Danger;
Node(int _Dat) : Dat(_Dat) {
Danger = 0, Next = NULL;
Rep(i, N) Child[i] = NULL;
}
} *Root;
i ...
bzoj1029: [JSOI2007]建筑抢修
- 博客分类：
- oi
按照t2从小到大排列之后贪心
若当前任务可以插入，则插入
若当前任务不可以插入，分两种情况：
任务的耗时大于等于之前插入的任务的最大耗时，跳过当前任务
任务的耗时小于之前插入的任务的耗时，将最前插入的耗时最大的那个任务删除，插入当前任务
const int N = 150010;
struct Node {
int L, T;
inline bool operator <(const Node &p)const {
return L < p.L;
}
} Dat[N];
priority_queue<in ...
n<=400的话，就很容易想到暴力枚举n^3的做法，现枚举加进去的数，再枚举对子的数字，再判断是否合法就可以了
const int N = 410;
int A[N], B[N], n, m;
inline void Input() {
scanf("%d%d", &n, &m);
int x;
Rep(i, m * 3 + 1) scanf("%d", &x), A[--x]++;
}
inline bool Check() {
Rep(K, n)
if(A[K] >= 2) ...
每种材料可以用前两个表示，设为X，Y，分别作为横纵坐标，那么两个点的连线上的点都可以被这两个点表示，几个点围城的凸包可以表示凸包内的所有点，那么问题就转化为求最少的点，使他们围城的凸包能够包含所有的点，答案用最小环求解
//-----------------------------------发现原来的代码有点bug，虽然可以AC，但最小环是错的，以更正
const int N = 510;
const DB Eps = 1e-9;
typedef pair<DB, DB> DD;
int n, m;
DD Material[N], Product[N];
in ...
简单的数位DP，F[i][k][2]表示第i个数字位为K(0<=k<=9)是否为满数的方案数
//------------------------------------------------------------------------------------------
上主程序
#define For(i, s, t) for(int i = (s); i <= (t); i++)
#define Ford(i, s, t) for(int i = (s); i >= (t); i--)
#define Rep(i, n) for(int i = 0 ...