cool's Blog
[单纯形]bzoj1061
1061: [Noi2008]志愿者招募
Time Limit: 20 Sec Memory Limit: 162 MBSubmit: 3017 Solved: 1866
[Submit][Status][Discuss]
Description
申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。
Input
第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负整数，表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。
Output
仅包含一个整数，表示你所设计的最优方案的总费用。
Sample Input
2 3 4
1 2 2
2 3 5
3 3 2
Sample Output
HINT
招募第一类志愿者3名，第三类志愿者4名 30%的数据中，1 ≤ N, M ≤ 10，1 ≤ Ai ≤ 10； 100%的数据中，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均 不超过2^31-1。
[分块]bzoj2002
一直听主力讲分块大法好，xllend3似乎证明莫队都可以用分块做！（%一发）
一开始看到标签写着Splay 启发式合并感觉很厉害的样子，然后发现分块可以操！
思路：把N个蹦床分成sqrt(n）块，然后在每块里记录这个点飞出这个块要的步数和会飞到哪个点。
修改：把这个块里的点都重新算一遍，O（n^0.5)
询问：显然O（n^0.5）
#include <cstdio>
#include <cmath>
using namespace std;
#define maxn 200010
#define INF 0x7f7f7f7f
int a[maxn],p[maxn],num[maxn],size;
int LG(int x)//询问X属于哪个块
{
return (x-1)/size+1;
}
int head(int x)//询问第x块的头
{
return (x-1)*size+1;
}
int main()
{
int n;
scanf("%d",&n);
for (int i = 1;i <= n;i++)
scanf("%d",&a[i]);
size = sqrt(n);
if (size*size < n) size++;
for (int i = n;i >= 1;i--)
{
if (i+a[i] > n)
p[i] = INF,num[i] = 1;
else if (LG(i+a[i])!=LG(i))
p[i] = i+a[i],num[i] = 1;
else p[i] = p[i+a[i]],num[i] = 1+num[i+a[i]];
}
int q;
scanf("%d",&q);
for (;q--;)
{
int x;
scanf("%d",&x);
if (x == 1)
{
int y,ans = 0;
scanf("%d",&y);
for (y++;y < INF;y = p[y])ans += num[y];
printf("%d\n",ans);
}
else
{
int y,z;
scanf("%d%d",&y,&z);
a[++y] = z;
int t = head(LG(y));
for (;y >= t;y--)
{
if (y+a[y] > n)
p[y] = INF,num[y] = 1;
else if (LG(y+a[y])!=LG(y))
p[y] = y+a[y],num[y] = 1;
else p[y] = p[y+a[y]],num[y] = 1+num[y+a[y]];
}
}
}
return 0;
}
[斜率优化DP]bzoj1096
1096: [ZJOI2007]仓库建设
Description
L公司有N个工厂，由高到底分布在一座山上。如图所示，工厂1在山顶，工厂N在山脚。 由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L公司的总裁L先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件，在第i个工厂位置建立仓库的费用是Ci。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于L公司产品的对外销售处设置在山脚的工厂N，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，假设一件产品运送1个单位距离的费用是1。假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据： 工厂i距离工厂1的距离Xi（其中X1=0）; 工厂i目前已有成品数量Pi; 在工厂i建立仓库的费用Ci; 请你帮助L公司寻找一个仓库建设的方案，使得总的费用（建造费用+运输费用）最小。
Input
第一行包含一个整数N，表示工厂的个数。接下来N行每行包含两个整数Xi, Pi, Ci, 意义如题中所述。
Output
仅包含一个整数，为可以找到最优方案的费用。
Sample Input
0 5 10
5 3 100
9 6 10
Sample Output
[单调队列优化DP]bzoj3831
3831: [Poi2014]Little Bird
Description
Input
Output
[Noip2015]蒟蒻受虐记
Day0：乘了4个半小时的大巴 到了衢州 愉快地在食堂吃了晚餐。晚上按照国际惯例就不多说了= =
Day1：早上起来觉得睡的不是很好（晚上真的好热= =）
人生第一次进入Noip提高组（蒟蒻好激动= =）
T1：幻方（= =）貌似只要按他说的做就行了（= =）
T2：信息传输（= =）第一眼看到 Floyed最小环？（原谅本蒟蒻）
看到n<=200000 突然觉得好难（= =）突然发现 好像拓扑就行了（= =）
T3：斗地主！（= =）作为一位线下资深的斗地主玩家，我竟不知道还可以四带二（= =）
然后觉得这道题好难（= =自古T3码农题！）枚举所有情况？貌似不行= =
根据斗地主的经验，机智的组顺子可以加快出牌。所以就枚举了所有的顺子情况，然后剩下就可以贪心了。
最后在想四带二到底能不能带1对，仔细思考+平时经验后觉得应该不行，就果断不写了（= =为本蒟蒻受虐埋下了伏笔）
[树剖]bzoj1036
十天时间学了树剖（= =）
这是道裸题，只要单点修改，区间查询。
深搜如下
void FHE(int x,int father,int depth)
{
fa[x] = father;dep[x] = depth;
size[x] = 1;
int maxsize = 0;
son[x] = 0;
for (int i = head[x];i;i = last[i])
if (!visit[h[i]])
{
visit[h[i]] = 1;
FHE(h[i],x,depth+1);
size[x] += size[h[i]];
if (size[h[i]] > maxsize)
{
maxsize = size[h[i]];
son[x] = h[i];
}
}
}
void CHE(int x,int ancestor)
{
tid[x] = ++label;
optid[label] = x;
top[x] = ancestor;
if (son[x]) {visit[son[x]] = 1;CHE(son[x],ancestor);}
for (int i = head[x];i;i = last[i])
if (!visit[h[i]])
{
visit[h[i]] = 1;
CHE(h[i],h[i]);
}
}
查询如下
int Respond_max(int x,int y)
{
int ans = -100000000;
for (;top[x]-top[y];)
{
if (dep[top[x]] < dep[top[y]]) swap(x,y);
ans = max(ans,tree.query_max(1,tid[top[x]],tid[x]));//tree.query_max就是数据结构的最值查询
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x,y);
return max(ans,tree.query_max(1,tid[x],tid[y]));
}
int Respond_num(int x,int y)
{
int ans = 0;
for (;top[x]-top[y];)
{
if (dep[top[x]] < dep[top[y]]) swap(x,y);
ans += tree.query_num(1,tid[top[x]],tid[x]);//tree.query_num就是数据结构的和查询
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x,y);
return ans+tree.query_num(1,tid[x],tid[y]);
}
【并查集】bzoj1015
每次删边显然十分复杂，所谓正难则反（= = 数学思路？）
只要把摧毁的建筑倒着加入并查集就行了
每次合并，连通块就会减1，但总的连通块要减去那些还未加入的星球（= = 貌似说不清楚）
直接上代码。
#include <cstdio>
#define maxm 200001
#define maxn 400001
int b[maxn],f[maxn],d[maxn],c[maxn],h[maxn],last[maxn],head[maxn],l;
void add(int x,int y)
{
l++;
h[l] = y;
last[l] = head[x];
head[x] = l;
}
int find(int x)
{
if (f[x] == x) return x;
return f[x] = find(f[x]);
}
void read(int &i)
{
char x;
for (x = getchar();x < '0';x = getchar());
for (i = 0;x >= '0';x = getchar()) i = i * 10 + x - '0';
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for (int i = 1;i <= m;i++)
{
int x,y;
read(x);read(y);
add(++x,++y);
add(y,x);
}
int q;
read(q);
for (int i = 1;i <= n;i++)
b[i] = 1,f[i] = i;
for (int i = 1;i <= q;i++)
{
read(d[i]);
b[++d[i]] = 0;
}
int t = q;\\t就是还没加入的星球个数
int sum = n;
for (int i = 1;i <= n;i++)
if (b[i] == 1)
{
for (int x = head[i];x;x = last[x])
if (b[h[x]] == 1)
{
int r1 = find(i),r2 = find(h[x]);
if (r1 != r2)
{
f[r1] = r2;
sum--;
}
}
}
for (int i = q;i >= 1;i--)
{
c[i] = sum - t;
b[d[i]] = 1;
for (int x = head[d[i]];x;x = last[x])
if (b[h[x]] == 1)
{
int r1 = find(d[i]),r2 = find(h[x]);
if (r1 != r2)
{
f[r1] = r2;
sum--;
}
}
t--;
}
printf("%d\n",sum-t);
for (int i = 1;i <= q;i++)
printf("%d\n",c[i]);
return 0;
}
[DP]bzoj1037
话说我的DP真的好水 这种题目根本做不出
f[i][j][x][y] 表示 总共i人 有j个男的 从i人往前的一段人中，男比女最多多x人 女比男最多做y人
这是 网上的题解 代码如下
f[0][0][0][0] = 1;
for (int i = 0;i < n+m;i++)
for (int j = 0;j <= n;j++)
for (int x = 0;x <= k;x++)
for (int y = 0;y <= k;y++)
if (f[i][j][x][y])
{
if (x + 1 <= k&&j+1 <= n)
f[i+1][j+1][x+1][max(y-1,0)] += f[i][j][x][y],f[i+1][j+1][x+1][max(y-1,0)] %= mod;
if (y + 1 <= k&&i+1-j <= m)
f[i+1][j][max(x-1,0)][y+1] += f[i][j][x][y],f[i+1][j][max(x-1,0)][y+1] %= mod;
}
但有点让我想不通 为什么不干脆f[i][j][x][y] i表示男 j表示女呢 而且空间 时间都快了。
而且在bz上也AC了 请大神教导
【倍增LCA】 NOIP2013 T3货车运输
人生第一道A掉的提高组T3= =
倍增+LCA 就能轻松AC了
但lbn大神让我去学树剖LCA 而我连树剖都不会 结果被大D一通