「考试总结」ZROI-21-NOIP冲刺-TEST10 总结

发表于 分类于
ZROI-21-NOIP冲刺-TEST10 总结

...too young...too simple,sometimes naive!

#T1 不知道高到哪里去了

Time Limits: 3s | Memroy Limit: 256MiB

#题意简述

比你们不知道高到哪里去了！

一个 \(n(n\leq10^4)\) 个点 \(m(5\times10^5)\) 条边的带权无向图（可能有重边、自环），你处在 \(C\) 点，刺客开始时在 \(I\) 点，你要到 \(T\) 点去，你不知道刺客向哪里走，刺客时刻知道你的位置，问你的速度至少是刺客的多少倍（实数）才能安全到达 \(T\) 点，如果无法到达，则输出 -1。

#大体思路

考虑二分答案，考虑如何判定。显然我们可以得到每次到达任意一点的最小时间，刺客的最小时间可以提前用最短路得到，当我们发现当前边的终点的最小时间比刺客晚，那么我们就不前往，看最终是否能够到达 \(T\) 点即可。时间复杂度为 \(O((m+n)\log^2 n)\).

#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
77
78
79
#define dd double
#define ll long long
#define pdi pair <double, int>
#define mp(a, b) make_pair(a, b)

const int N = 100010;
const int M = 500010;
const int INF = 0x3f3f3f3f;
const dd eps = 1e-7;

template<typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (;!isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (;isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

struct edge {int u, v, nxt, w;} e[M << 1];

int head[N], ecnt(1);
int C, I, T, n, m;

dd d[N], TimeLimit[N];
bool vis[N];

inline void add_edge(int u, int v, int w) {
    e[ecnt].u = u, e[ecnt].v = v, e[ecnt].w = w;
    e[ecnt].nxt = head[u], head[u] = ecnt ++;
}

inline void init() {
    read(n); read(m);
    for (int i = 1; i <= m; ++ i) {
        int u, v, w; read(u), read(v), read(w);
        add_edge(u, v, w); add_edge(v, u, w);
    }
    read(C); read(I); read(T);
    fill(TimeLimit + 1, TimeLimit + n + 1, INF);
}

dd l = 0, r = 10000001;

priority_queue <pdi > q;

inline void dijkstra(int s, dd v) {
    fill(d + 1, d + n + 1, INF);
    fill(vis + 1, vis + n + 1, 0);
    if (TimeLimit[s] <= 0) return;
    q.push(mp(0, s)); d[s] = 0;
    while (q.size()) {
        int now = q.top().second; q.pop();
        if (vis[now]) continue; vis[now] = 1;
        for (int i = head[now]; i; i = e[i].nxt) {
            dd w = (dd)e[i].w / v;
            if (d[e[i].v] <= d[now] + w) continue;
            if (TimeLimit[e[i].v] <= d[now] + w) continue;
            d[e[i].v] = d[now] + w; 
            q.push(mp(-d[e[i].v], e[i].v));
        }
    }
}

inline bool Check(dd mid) {
    dijkstra(C, mid); return d[T] != INF;
}

int main() {
    init(); dijkstra(I, 1);
    for (int i = 1; i <= n; ++ i) TimeLimit[i] = d[i];
    while (r - l > eps) {
        dd mid = (l + r) / 2;
        if (Check(mid)) r = mid;
        else l = mid;
    }
    if (l >= 10000000) {return puts("-1"), 0;}
    else printf("%lf", l);
    return 0;
}

#T2 身经百战

Time Limits: 1s | Memroy Limit: 256MiB

#题意简述

我是身经百战了，见得多了！

身经百战的你要和怪物战斗。有 \(n(n\leq10^6)\) 个怪，每个怪的血量 \(v_i(v_i\leq10^9)\) 都是一个非负整数，当血量变为负数后怪就死了。有 \(m(m\leq10^5)\) 种魔法，第 \(i\) 种用一个三元组 \((a_i,b_i,c_i)\) 表示，魔法可以重复使用。

你有两种操作可以做：

  • 花费 \(1\) 点能量，给一个怪的血量减掉 \(1\)。
  • 如果一个怪的血量是 \(a_i\)，你可以花费 \(c_i\) 的能量把它的血量变为 \(b_i\)。

你希望削弱这些怪，但你不想杀生。请问最少要花费多少能量才能把所有怪的血量都变成 \(1\)。注意：一个血量为 \(0\) 的怪仍然是存活的。

数据保证有解。

#大体思路

不难发现每个怪物都是独立的问题，所以其实可以看作多次询问，同样因为这个原因，我们尝试进行 DP。

\(f_{i,j}\) 表示将第 \(i\) 个怪物的血量变为 \(j\) 所需要的最小代价。注意到这个 DP 的转移具有后效性，所以考虑将所有转移变为边，找最短路，我们发现上面的状态设计有许多的冗余状态，我们只需要保留给出数据中出现的数，将原本 DP 的转移变为边则是 \(a_i\to b_i\) （边权为 \(c_i\)）以及 \(x_i\) 向所有比它小的数连边（边权为差值），但是这样的边的数量仍旧是 \(O(m^2)\) 级别的，不能接受，注意到第二部分的边可以被简化，也就是 \(x_i\) 只需要向比自己小的第一个数连边即可，这样得到的转移图与之前是等价的，边的数量为 \(O(n+m)\)，现在我们只需要建出反向边，以 \(1\) 为源点最短路即可。

时间复杂度为 \(O((n+m)\log(n+m))\).

#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
#define ll long long
#define plli pair <long long, int>
#define mp(a, b) make_pair(a, b)
#define mset(l, x) memset(l, x, sizeof(l))

const int N = 5000010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

struct Magic {int a, b; ll c;} p[N];
struct Edge {int u, v, nxt; ll w;} e[N];

int n, m, v[N], head[N], ecnt(1), a[N];
ll d[N]; int vis[N];

inline void add_edge(int u, int v, int w) {
    e[ecnt].u = u, e[ecnt].v = v, e[ecnt].w = w;
    e[ecnt].nxt = head[u], head[u] = ecnt ++;
}

#define lb(l, len, x) lower_bound(l + 1, l + len + 1, x)

priority_queue <plli > q;

void solve(int s) {
    mset(d, 0x3f); mset(vis, 0);
    d[s] = 0; q.push(mp(0, s));
    while (q.size()) {
        int now = q.top().second; q.pop();
        if (vis[now]) continue; vis[now] = 1;
        for (int i = head[now]; i; i = e[i].nxt)
          if (d[e[i].v] > d[now] + e[i].w) {
              d[e[i].v] = d[now] + e[i].w;
              q.push(mp(-d[e[i].v], e[i].v));
          }
    }
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++ i) read(v[i]);
    for (int i = 1; i <= m; ++ i) {
        read(p[i].a), read(p[i].b), read(p[i].c);
        a[i * 2 - 1] = p[i].a, a[i * 2] = p[i].b;
    }
    for (int i = 1; i <= n; ++ i) a[2 * m + i] = v[i];
    a[2 * m + n + 1] = 1; sort(a + 1, a + 2 * m + n + 2);
    int _m = unique(a + 1, a + 2 * m + n + 2) - a - 1;
    for (int i = 1; i <= m; ++ i) {
        int u = lb(a, _m, p[i].a) - a;
        int v = lb(a, _m, p[i].b) - a;
        add_edge(v, u, p[i].c);
    }
    for (int i = 1; i < _m; ++ i)
      add_edge(i, i + 1, a[i + 1] - a[i]);
    solve((lb(a, _m, 1) - a)); ll ans = 0;
    for (int i = 1; i <= n; ++ i) {
        int pos = lb(a, _m, v[i]) - a;
        ans += d[pos];
    }
    printf("%lld ", ans);
    return 0;
}

#T3 跑得比谁都快

Time Limits: 3s | Memroy Limit: 256MiB

#题意简述

你们有一个好，全世界跑到什么地方，你们比其他的西方记者啊，跑得还快。

这条路上有 \(n(n\leq2\times10^5)\) 个红绿灯，把路分成了 \(n+1\) 个部分。红绿灯的颜色是循环的，一次循环内，在 \([0,g)\) 的时间里它是绿色的，在 \([g,g+r)\) 的时间里它是红色的。一开始，每个红绿灯都处于循环的开始，也就是说都会先绿 \(g(g+r\leq10^9)\) 的时间。

记者团里有 \(q(q\leq2\times10^5)\) 个香港记者。每个记者要从路的开头跑到末端，遇到红灯的话不能穿过，必须等红灯变绿。记者的最大速度是 \(1\)，记者可以瞬间改变自己的速度。告诉你记者出发的时间，问你她什么时候跑到。

本题强制在线，假如输入的第 \(i(1<i\leq q)\) 个记者的出发时间为 \(time_i\)，那么她实际出发的时间是 \(time_i\text{ xor }(ans_{i−1} \bmod 2147483647)\)，其中 \(ans_{i−1}\) 表示第 \(i−1\) 个人的到达时间。

#大体思路

考虑在任意红绿灯出发遇到的第一个红灯的位置，由于 \(m=g+r\) 是周期，所以不妨将时间通过 \(\bmod m\) 将所有时间分为 \(m\) 种，设 \(t_i\) 为到达 \(i\) 号红绿灯前没有任何一个红绿灯阻挡到达 \(i\) 的时间，显然是 \(s_i\bmod m\)（\(s_i\) 为 \(len\) 的前缀和），设 \(j\) 为从 \(i\) 出发后遇到的第一个红灯，由于两者之间没有任何红灯阻拦，考虑到从任意一个红绿灯出发必然是在该红绿灯进行了停顿，但显然不会对到 \(j\) 的时间和到 \(i\) 的时间之间的差值造成影响，且出发时间必然是 \(m\) 的倍数，在 \(i\) 于是两者之间经过的时间必然是 \(t_j-t_i=km+b\)，\(k\in Z,b\in[g,r)\)，于是我们找 \([t_i\bmod m+g,t_i\bmod m+r)\) 区间最小值即可，然后采用 \(j\) 到终点的时间更新 \(i\) 到终点的时间，最后将 \(i\) 插入到 \(t_i\bmod m\) 的位置即可。

再来看查询时，同样考虑第一个遇到的红绿灯，不过上面维护出的都是开始时间为 \(0\) 的情况（循环从头开始），所以我们开始时需要将查询区间进行矫正。

时间复杂度为 \(O(n\log n)\).

#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
#define ll long long

const int N = 10000010;
const ll MOD = 2147483647;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

struct Node {int ls, rs, val;} p[N];

ll n, m, G, R, q, len[N], s[N], sp[N], lst, pcnt, f[N]; int rt;

void insert(int &k, int l, int r, int x, int c) {
    if (!k) k = ++ pcnt; p[k].val = c;
    if (l == r) return; int mid = l + r >> 1;
    if (x <= mid) insert(p[k].ls, l, mid, x, c);
    else insert(p[k].rs, mid + 1, r, x, c);
}

int query(int k, int l, int r, int x, int y) {
    if (!k) return n + 1; if (x <= l && r <= y) return p[k].val;
    int mid = l + r >> 1, res = INF;
    if (x <= mid) res = min(res, query(p[k].ls, l, mid, x, y));
    if (mid < y) res = min(res, query(p[k].rs, mid + 1, r, x, y));
    return res;
}

ll dist(int x, int y) {return y == n + 1 ? s[y] - s[x] : (s[y] - s[x] + m - 1) / m * m;}

int main() {
    read(n), read(G), read(R); m = G + R;
    for (int i = 1; i <= n + 1; ++ i) read(len[i]);
    for (int i = 1; i <= n + 1; ++ i)
      s[i] = s[i - 1] + len[i], sp[i] = s[i] % m; 
    for (int i = n; i; -- i) {
        int l = (sp[i] + G) % m, r = (l + R - 1) % m, pos = 0;
        if (l > r) pos = min(query(rt, 0, m - 1, 0, r), query(rt, 0, m - 1, l, m - 1));
        else pos = query(rt, 0, m - 1, l, r);
        f[i] = dist(i, pos) + f[pos]; insert(rt, 0, m - 1, sp[i], i);
    }
    read(q);
    while (q --) {
        ll x; read(x); x ^= (lst % MOD); s[0] = -x; int pos = 0;
        int l = (0ll + m - x % m + G) % m, r = (l + R - 1) % m;
        if (l > r) pos = min(query(rt, 0, m - 1, 0, r), query(rt, 0, m - 1, l, m - 1));
        else pos = query(rt, 0, m - 1, l, r);
        printf("%lld\n", lst = dist(0, pos) + f[pos]);
    }
    return 0;
}

#T4 人生经验

Time Limits: 1s | Memroy Limit: 512MiB

#题意简述

我作为一个长者，来告诉你们一些人生的经验…

人生经验以 01 字符串的形式存在。

一个长度为奇数的 01 字符串是好的，当且仅当它可以被用下面的办法转化为 1：

  • 选一个奇数 \(i(3\leq i\leq|S|)\)
  • 把 \(S\) 分成两个字符串 \(A,B\) 满足 \(|A|=i,|B|=|S|−i,S=AB\)
  • 通过一个给定的函数 \(f(U)\) 将 \(A\) 的末尾三位数变为一位数，一直重复直到 \(A\) 只剩下一个数
  • 用 \(A+B\) 替代 \(S\)。

现在给定一个字符串，包含 0 1 ? 三种字符，? 可以替换为 0 或者 1，请问有多少种替换方案使得替换的结果是一个好串。

#大体思路

DP 套 DP。

我们考虑如何判断一个串是否合法，不难发现，那些操作都可以转化成下面两个操作：

  • 把两个字符压入栈。
  • 把一个字符压入栈，进行缩字符串，然后再让另一个字符入栈。

虽然栈的情况可能很多，但其实去掉我们不管的，只有 \(4\) 种情况：

  1. 当前栈中序列加入 1 之后能缩成 1。
  2. 当前栈中序列加入 1 之后能缩成 0。
  3. 当前栈中序列加入 0 之后能缩成 1。
  4. 当前栈中序列加入 0 之后能缩成 0。

上面四种情况就是我们所关心的。然后我们就可以设计 DP 状态：

\(f_{i,a}\) 表示考虑前 \(i\) 个字符，第 \(a\) 个放法是否合法，然后考察整个字符串的话，只需要看 \(f_{n−1}\) 即可。

接下来我们考虑计数，通过上面的启发，再加上字符串是不确定的，所以我们设状态 \(g_{a,b,c,d}\) 分别表示上面 \(4\) 种转移是否合法，\(f_{i,S}\) 表示考虑到第 \(i\) 位，合法转移为 \(S\) 的情况的数量。

我们每次考虑两个数，先考虑两个字符压入栈的情况，然后枚举合法情况，转移即可。

#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
#define ll long long
#define mset(l, x) memset(l, x, sizeof(l))

const int N = 100010;
const int MOD = 1e9 + 7;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

int n, t, f[N][16], a[N], ans; char s[N], g[N];

inline int get(int x, int y, int z) {return g[x | (y << 1) | (z << 2)] - '0';}
inline int Madd(int x, int y) {return x + y >= MOD ? x + y - MOD : x + y;}

void MAIN() {
    scanf("%s%s", g, s + 1); n = strlen(s + 1);
    mset(f, 0); ans = 0; f[0][9] = 1;
    for (int i = 2; i < n; ++ i) 
      for (a[i - 1] = 0; a[i - 1] < 2; ++ a[i - 1])
        for (a[i] = 0; a[i] < 2; ++ a[i]) {
            if (s[i - 1] != '?' && s[i - 1] != a[i - 1] + '0') continue;
            if (s[i] != '?' && s[i] != a[i] + '0') continue;
            for (int S = 0; S < 16; ++ S) {
                if (!f[i - 2][S]) continue; int SS = 0;
                for (int p1 = 0; p1 < 2; ++ p1)
                  for (int p2 = 0; p2 < 2; ++ p2) {
                      int p = ((S & (1 << (get(a[i - 1], a[i], p1) << 1) + p2)) > 0);
                      if (get(0, a[i], p1) == p2) p |= ((S & (1 << (a[i - 1] << 1))) > 0);
                      if (get(1, a[i], p1) == p2) p |= ((S & (1 << (a[i - 1] << 1) + 1)) > 0);
                      if (p) SS |= (1 << (p1 << 1) + p2);
                  }
                f[i][SS] = Madd(f[i][SS], f[i - 2][S]);
            }
        }
    for (a[n] = 0; a[n] < 2; ++ a[n]) {
        if ((s[n] != '?') && (s[n] != a[n] + '0'))continue;
        for (int S = 0; S < 16; ++ S)
          if (S & (1 << (a[n] << 1) + 1))
            ans = Madd(ans, f[n - 1][S]);
    }
    printf("%d\n", ans);
}

int main() {
    read(t); while (t --) MAIN(); return 0;
}