NOIP2015 - 模拟考试Ⅵ

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

Day 1

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

Convolution

[Description]

[Solution]

用来吓人的题面。
其实是一道模拟水题。

Path

[Description]

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

[Solution]

从起点开始走完所有点再回到起点的最短路径为2*tot，tot为所有边的边权和。

不用回到起点，就找一个离起点最远的点，最终到达这个点，答案达到最小，为2*tot-起点到最远点的距离。
同时处理多个起点，用树形DP就好了~

[Summary]

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

Noligon

[Description]

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

[Solution]

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

[Summary]

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

Day 2

Star

[Description]

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

[Hint]

n≤50,m≤1023n≤50,m≤10^{23}

[Solution]

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

Race

[Description]

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

[Hint]

1≤T≤20,1≤n≤105,1≤ai≤108,1≤m⋅K≤100,000,0001≤T≤20,1≤n≤10^5,1≤a_i≤10^8,1≤m\cdot K≤100,000,000

[Solution]

二分答案然后判断。

Hungry

[Description]

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

[Hint]

1≤n,Q≤105,0≤∣ai∣≤1051≤n,Q≤10^5,0≤|a_i|≤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;
}

总结

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

Comment