NOIP2015 - 模拟考试Ⅵ

2015.10.06-07

闲吹

Codeplay第一定律:考试状态与题目难度成反比。

Day 1

”曾有一个绝好AK的机会摆在我面前,我却没有好好珍惜。“

Convolution

[Description]

这里写图片描述

[Solution]

用来吓人的题面。这里写图片描述
其实是一道模拟水题。

Path

[Description]

n$(n≤10^5)$个点的一棵带权树,有一些点可以作为起点。求从起点开始走完所有点的最短路径。

[Solution]

从起点开始走完所有点再回到起点的最短路径为2*tot,tot为所有边的边权和。
不用回到起点,就找一个离起点最远的点,最终到达这个点,答案达到最小,为2*tot-起点到最远点的距离。
同时处理多个起点,用树形DP就好了~

[Summary]

实力打挂一个小细节…
lfw提供了更简单的打法:先求出直径,再跑最短路。
想想也是十分支持啊!

Noligon

[Description]

n$(n≤10^5)$个物品,用(k,w)描述,表示物品的价格为$2^k$,价值为$w$。
有不超过5000个背包,每种大小的背包用(t,h)描述,表示大小为$2^t$的背包共h个。
每个背包都要装满,求权值最小的方案的权值。无方案输出-1.

[Solution]

模拟。
实力口胡一下过程…
从小到大考虑每种背包,将这种大小的物品从小到大放进去。
将剩下的物品两两合并成一个更大的物品(剩下也没有用,无法填充一个新背包)。
然后就推出答案了…

[Summary]

以后优化前还是要想清楚…这里写图片描述

Day 2

Star

[Description]

n个大小不超过10000的背包,m个大小不超过128的物品。求总共最多放多少物品。

[Hint]

$n≤50,m≤1023$

[Solution]

二分+搜索。
二分答案然后判断。
一个优化是从大的物品和小的背包开始放,可以尽早的到不行的答案。

Race

[Description]

n个人,分别距终点ai米,初始每人每秒走1米。m个加速器,每个每秒可以使一个人的速度变为K。加速器试用完后下一秒可以回收继续使用。求最短的时间使得所有人经过终点。
T组数据。

[Hint]

$1≤T≤20,1≤n≤10^5,1≤ ai≤10^8,1≤m∗K≤100,000,000$

[Solution]

二分答案然后判断。

Hungry

[Description]

一个长度为n的整数序列a,区间[L,R]的质量为这里面所有不同元素之和。
Q个询问,询问[l,r]内所有区间的最优质量。

[Hint]

$1≤n,Q≤10^5,0≤|ai|≤10^5$

[Solution]

还不懂。把erSTD的代码贴下面…

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#include <stdlib.h>
typedef long long ll;
const int nmax = 100000, tmax = 1 << 18, shift = nmax;

int n, m, M = 1, H = 1, a[nmax + 18], last[nmax * 2 + 18], pre[nmax + 18];
ll f[tmax + 18], g[tmax + 18], fd[tmax + 18], gd[tmax + 18], ans[nmax + 18];
int l[nmax + 18], r[nmax + 18], p[nmax + 18];

int cmpor(const void *i, const void *j) {return r[*(int *)i] - r[*(int *)j];}
inline int max(int a, int b) {return a > b ? a : b;}
inline void update(ll &a, ll b) {if (a < b) a = b;}
inline void take(int i)
{

f[i] = max(f[i << 1], f[i << 1 | 1]), g[i] = max(g[i << 1], g[i << 1 | 1]);
}

inline void give(int i, int j)
{

update(g[i], f[i] + gd[j]), f[i] += fd[j];
update(gd[i], fd[i] + gd[j]), fd[i] += fd[j];
}

void pd(int i)
{

for (int h = H - 1, j; h; --h)
if (fd[j = i >> h] || gd[j])
give(j << 1, j), give(j << 1 | 1, j), fd[j] = gd[j] = 0;
}

void add(int l, int r, int x)
{

for (pd(l += M - 1), pd(r += M + 1); l ^ r ^ 1; take(l >>= 1), take(r >>= 1))
{
if (~l & 1)
update(g[l ^ 1], f[l ^ 1] += x), update(gd[l ^ 1], fd[l ^ 1] += x);
if ( r & 1)
update(g[r ^ 1], f[r ^ 1] += x), update(gd[r ^ 1], fd[r ^ 1] += x);
}
for (int tmp1, tmp2; l >>= 1;)
{
tmp1 = f[l], tmp2 = g[l];
take(l);
if (f[l] == tmp1 && g[l] == tmp2) break;
}
}

ll getmax(int l, int r)
{

ll ans = 0;
for (pd(l += M - 1), pd(r += M + 1); l ^ r ^ 1; l >>= 1, r >>= 1)
{
if (~l & 1) update(ans, g[l ^ 1]);
if ( r & 1) update(ans, g[r ^ 1]);
}
return ans;
}

int main()
{

freopen("hungry.in", "r", stdin);
freopen("hungry.out", "w", stdout);
scanf("%d", &n);
while (n >= M - 2) M <<= 1, ++H;
for (int i = 1; i <= n; ++i)
scanf("%d", a + i), pre[i] = last[a[i] + shift], last[a[i] + shift] = i;
scanf("%d", &m);
for (int i = 1; i <= m; ++i)
scanf("%d%d", l + i, r + i), p[i] = i;
qsort(p + 1, m, sizeof(p[0]), cmpor);
for (int i = 1, j = 1; i <= n && j <= m; ++i)
for (add(pre[i] + 1, i, a[i]); j <= m && r[p[j]] <= i; ++j)
ans[p[j]] = getmax(l[p[j]], r[p[j]]);
for (int i = 1; i <= m; ++i) printf("%I64d\n", ans[i]);
return 0;
}

总结

不知道,也没什么想说的。
总之感觉自己现在的状态有点奇怪。