简单写了 T1, T2 的代码， T3, T4 因为没有评测数据就先咕了。
T1 归程 (return)
签到题做了一个多小时，我真废物。
考虑进行 dp ，题目描述中说明了：每个决策根据当前时间，当前雨是否变大和小 S 所处位置决定。因此这三个参数就是我们 dp 的状态。具体的，设 \(f_{i,j,0/1}\) 表示当前位于点 \(i\) ，当前时刻为 \(j\) ，雨是否变大时到达 \(y\) 的最小的期望淋雨量。转移时考虑经过当前边时雨是否变大，设 \(P_i\) 表示前 \(i-1\) 个时刻雨没有变大时，第 \(i\) 个时刻雨变大的概率，显然我们可以得到转移：
直接 dp 即可。
code
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int max1 = 1000, max2 = 2e4, front = 25;
const double inf = 0x3f3f3f3f3f3f3f3f;
int n, m, k, x, y, P[max2 + front + 5], sum[max2 + front + 5];
struct Edge
{
int v, w, A, B;
Edge () {}
Edge ( int __v, int __w, int __A, int __B )
{ v = __v, w = __w, A = __A, B = __B; }
};
vector <Edge> edge[max1 + 5];
double f[max1 + 5][front + 5][2], val[front + 5], g[front + 5];
pair <double, double> h[front + 5];
int main ()
{
scanf("%d%d%d%d%d", &n, &m, &k, &x, &y);
for ( int i = 1, u, v, w, A, B; i <= m; i ++ )
{
scanf("%d%d%d%d%d", &u, &v, &w, &A, &B);
edge[u].push_back(Edge(v, w, A, B));
edge[v].push_back(Edge(u, w, A, B));
}
for ( int i = 1, T, w; i <= k; i ++ )
{ scanf("%d%d", &T, &w); P[T] = sum[T] = w; }
for ( int i = max2 + front; i >= 0; i -- )
sum[i] += sum[i + 1];
int now = 0;
for ( int i = 1; i <= n; i ++ )
for ( int T = 0; T < front; T ++ )
f[i][T][0] = f[i][T][1] = inf;
for ( int T = 0; T < front; T ++ )
f[y][T][0] = f[y][T][1] = 0;
for ( int T = max2; T >= 0; T -- )
{
now = ( now + front - 1 ) % front;
for ( int i = 1; i <= n; i ++ )
f[i][now][0] = f[i][now][1] = inf;
f[y][now][0] = f[y][now][1] = 0;
for ( int i = 1; i <= front; i ++ )
{
val[i] = 1;
g[i] = 0;
h[i] = make_pair(0, 0);
for ( int j = 1; j <= i; j ++ )
{
if ( P[T + j] )
{
g[i] += val[i] * P[T + j] / sum[T + j];
h[i].first += val[i] * P[T + j] / sum[T + j] * j;
h[i].second += val[i] * P[T + j] / sum[T + j] * ( i - j );
val[i] = val[i] * ( 1.0 - 1.0 * P[T + j] / sum[T + j] );
}
}
}
for ( int i = 1; i <= n; i ++ )
{
if ( i == y )
continue;
for ( auto Tmp : edge[i] )
{
int v = Tmp.v, w = Tmp.w, A = Tmp.A, B = Tmp.B;
f[i][now][0] = min(f[i][now][0], val[w] * ( f[v][( now + w ) % front][0] + w * A ) + g[w] * f[v][( now + w ) % front][1] + h[w].first * A + h[w].second * B);
f[i][now][1] = min(f[i][now][1], w * B + f[v][( now + w ) % front][1]);
}
}
}
printf("%.10lf\n", f[x][now][0]);
return 0;
}
T2 最大连续和 (sequence)
发现题意很容易转化为取出 \(a\) 的一段连续区间，取出 \(b\) 序列中一些数来替换区间中的一些数，求解所有操作中区间和的最大值。
首先有一个简单的结论：
设 \(f(l,r)\) 为 \(a\) 中取出的区间为 \([l,r]\) 时，所有替换操作中区间和的最大值，考虑对于每个 \(l\) 找到取值最大的 \(r\) 记作 \(pos_l\) ，那么 \(pos_i\) 随 \(i\) 单调不降。
很容易发现当区间扩张时，一个元素只能从被替换变为不被替换。
于是简单进行证明，假设当前考虑的位置为 \(i\) ， 考虑左端点移动到 \(i+1\) 的过程，根据定义我们有 \(f(i,pos_i)\ge f_{i,j},j\in[i,pos_i]\) ，显然存在 \(f_{i,pos_i}-a_i\ge f_{i,j}-a_i,j\in[i,pos_i]\) ，也就是对于所有没有替换掉 \(i\) 的右端点 \(j\) ，此时的 \(f_{i+1,j}\) 一定小于 \(f_{i+1,pos_i}\) ，考虑替换掉 \(i\) 的右端点 \(j\) ，假设替换 \(a_i\) 的元素为 \(x\) ，显然有 \(x\ge a_i\) ，显然此时存在两种情况： \(x\) 用于替换其他元素或 \(x\) 不在被用于替换，后面的情况很容易考虑，很显然 \(f_{i,j}-x\le f_{i,pos_i}-a_i\) ，因此成立，考虑 \(x\) 用于替换其他元素的情况，容易发现区间 \([i+1,pos_i]\) 的替换方案中一定也可以去替换这个元素，仍然可以发现 \(f_{i+1,pos_i}\ge f_{i+1,j}\) 。
因此考虑分治法优化决策单调性，考虑求解 \(f(l,r)\) ，假设当前我们将 \(a\) 取出区间 \([l,r]\) 并从小到大排序，将 \(b\) 从大到小排序，现在我们需要找到一个最大的 \(k\) ，满足 \(a_k<b_k\) ，很容易用权值线段树维护，由于指针的移动次数为 \(O(n\log n)\) ，因此总复杂度为 \(O(n\log^2n)\) 。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 1e5;
const int inf = 0x3f3f3f3f;
int n, m, a[max1 + 5], b[max1 + 5];
long long sum[max1 + 5];
int save[max1 + 5], len;
struct Segment_Tree
{
#define lson(now) ( now << 1 )
#define rson(now) ( now << 1 | 1 )
struct Data
{ int maxval, count; long long sum; } tree[max1 * 4 + 5];
void Push_Up ( int now )
{
tree[now].maxval = max(tree[lson(now)].maxval, tree[rson(now)].maxval);
tree[now].count = tree[lson(now)].count + tree[rson(now)].count;
tree[now].sum = tree[lson(now)].sum + tree[rson(now)].sum;
return;
}
void Build ( int now, int L, int R )
{
tree[now].maxval = -inf;
tree[now].count = 0;
tree[now].sum = 0LL;
if ( L == R )
return;
int mid = L + R >> 1;
Build(lson(now), L, mid);
Build(rson(now), mid + 1, R);
return;
}
void Insert ( int now, int L, int R, int pos, int x )
{
if ( L == R )
{
tree[now].maxval = -inf;
tree[now].count += x;
tree[now].sum += 1LL * x * save[L];
if ( tree[now].count )
tree[now].maxval = save[L];
return;
}
int mid = L + R >> 1;
if ( pos <= mid )
Insert(lson(now), L, mid, pos, x);
else
Insert(rson(now), mid + 1, R, pos, x);
Push_Up(now);
return;
}
void Insert ( int pos, int x )
{ return Insert(1, 1, len, pos, x); }
long long Query ( int now, int L, int R, int start )
{
if ( L == R )
{
int l = start + 1, r = min(m, start + tree[now].count), pos = start;
while ( l <= r )
{
int mid = l + r >> 1;
if ( b[mid] > save[L] )
pos = mid, l = mid + 1;
else
r = mid - 1;
}
return sum[pos] + 1LL * ( start + tree[now].count - pos ) * save[L];
}
int mid = L + R >> 1;
if ( start + tree[lson(now)].count <= m && tree[lson(now)].maxval < b[start + tree[lson(now)].count] )
return Query(rson(now), mid + 1, R, start + tree[lson(now)].count);
return Query(lson(now), L, mid, start) + tree[rson(now)].sum;
}
long long Query ()
{ return Query(1, 1, len, 0); }
}Tree;
int nowl, nowr;
long long Solve ( int L, int R, int ql, int qr )
{
if ( L > R )
return 1LL * -inf * inf;
int mid = L + R >> 1;
while ( nowr < max(mid, ql) - 1 )
Tree.Insert(a[++nowr], 1);
while ( nowl > mid )
Tree.Insert(a[--nowl], 1);
while ( nowr > max(mid, ql) - 1 )
Tree.Insert(a[nowr--], -1);
while ( nowl < mid )
Tree.Insert(a[nowl++], -1);
long long ans = 1LL * -inf * inf;
int pos = 0;
while ( nowr < qr )
{
Tree.Insert(a[++nowr], 1);
long long up = Tree.Query();
if ( up > ans )
ans = up, pos = nowr;
}
return max(ans, max(Solve(L, mid - 1, ql, pos), Solve(mid + 1, R, pos, qr)));
}
int main ()
{
scanf("%d%d", &n, &m);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &a[i]), save[i] = a[i];
for ( int i = 1; i <= m; i ++ )
scanf("%d", &b[i]);
sort(b + 1, b + 1 + m);
reverse(b + 1, b + 1 + m);
sum[0] = 0;
for ( int i = 1; i <= m; i ++ )
sum[i] = sum[i - 1] + b[i];
sort(save + 1, save + 1 + n);
len = unique(save + 1, save + 1 + n) - ( save + 1 );
for ( int i = 1; i <= n; i ++ )
a[i] = lower_bound(save + 1, save + 1 + len, a[i]) - save;
nowl = 1, nowr = 0;
Tree.Build(1, 1, len);
printf("%lld\n", Solve(1, n, 1, n));
return 0;
}
T3 寻宝
由于给定的图是一张二分图，因此考虑对其进行二分图染色，一个比较暴力的想法是让每层之间的边指向藏宝点，于是可以得到一个 \(O(n)\) 的暴力做法，正解考虑随机化，设置阈值 \(B\) ，如果我们找到了一个深度位于 \(B\) 以内的点，复杂度可以做到 \(O(B)\) ，同时期望在 \(\tfrac{n}{B}\) 次随机得到这个点，因此考虑判断当前点深度是否小于 \(B\) ，可以得到一个想法是（我也不知道怎么想到的）， \(B\) 层以内的点指向藏宝点， \(B\) 层以外的点交替指向藏宝箱和与藏宝点所在方向相反，容易发现 \(B\) 层以外的点满足出度或入度为 \(0\) ，可以直接判断。
T4 字符树
这显然是一道暴力题。
首先对整棵树树剖，维护线段树，树上每个节点维护 unordered_map 记录这个区间内所有长度为 \(X\) 的子串的哈希值，合并区间时可以取出两个区间的长度为 \(X\) 的前后缀暴力合并，复杂度 \(O(n\log^2n)\) 。（真正考试我大概一定调不出来吧）