Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

test/2022/11/8

Posted on Edited on

感觉考了个寂寞。

还有$18$天就是$noip$了啊，调整状态啊，这段时间状态太差了！！！

T1

感觉很难受，每次对着这种啥都没有的题写一堆分类讨论真的很$shit$，最后只想了个大概就跑路了，感觉细节一堆。

T2

比较大的败笔吧，感觉自己想的做法非常常规，但是代码能力这段时间下降挺快的，思路也明显不行，导致浪费了很多时间最后因为实现不精细变成了$n \log^2 n$（没人和我说边权只有$0$和$1$的图跑最短路可以只用$deque+bfs$解决啊，具体的，当前加入点权值不变放最前面，否则放最后面即可），中途写挂一堆细节，要做点大码量题练练手了。

题目

image

Solution

个人做法比较丑陋，首先考虑将整个值域图建出来，发现完全建出来的话复杂度无法承受，所以我们考虑线段树优化建图的思路，让这张图仅仅作为一个流通图（整张图的边都没有权值），然后我们想办法将原图中的点加入到流通图中，首先先将原图中的每一个点和自己对应的$v_x$连边，由于连了边之后就会进入流通图，所以这条边的权值为$1$，然后由于需要从流通图流到目的地而且一开始就给过费用了，所以$v_x$对$x$的连边的权值为$0$，整个图的大小是$O(n\log n)$级别的，使用前文的搜索思路（序言）可以做到$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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#pragma GCC optimize("O2,O3,Ofast")
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<vector>
#include<queue>
#define LL long long
#define PII pair<int, int>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9'){ if(c == '-') flag = 1; c = getchar(); }
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
// template <>
inline void write(char c) { putchar(c); }
// template <>
inline void write(const char *s){ while(*s) putchar(*s ++); }
template <class T>
inline void write(T res)
{
    if(res < 0) res = -res, putchar('-');
    if(res > 9) write(res / 10);
    putchar(res % 10 + '0'); 
}
template <class T, class ...ARC>
inline void write(T res, ARC ...com){ write(res), write(com...); }
const int N = 2e5 + 5, M = 2.2e7 + 5, K = 1.5e6 + 5, Inf = 1e9;
int n, m;
int idx;
int e[M], ne[M], h[K], w[M];
int v[K];
inline void add(int x, int y, int z)
{
    idx ++;
    e[idx] = y, ne[idx] = h[x], h[x] = idx, w[idx] = z;
}
int a[N];
int flag[M], id[N], cnt;
int q[K << 1], hh, tt;
int main()
{
    memset(h, -1, sizeof(h));
    read(n, m);
    int maxn = 0;
    for(int i = 1;i <= n;i ++) read(a[i]), maxn = max(maxn, a[i]);
    for(int i = 1;i <= 20;i ++) 
        if((1 << i) > maxn) 
        {
            maxn = (1 << i) - 1;
            break;
        }
    cnt = maxn;
    for(int i = 1;i <= n;i ++) id[i] = ++ cnt, add(id[i], a[i], 1), add(a[i], id[i], 0); 
    for(int i = 1, o, u;i <= m;i ++) read(o, u), add(id[o], id[u], 1);
    for(int i = maxn;i >= 0;i --)
    {
        for(int j = 0;j < 20;j ++)
            if(i >> j & 1) add(i, i ^ (1 << j), 0);
    }
    memset(v, 0x3f, sizeof(v));
    hh = tt = cnt;
    hh ++;
    q[++ tt] = id[1];
    v[id[1]] = 0;
    while(hh <= tt)
    {
        int o = q[hh ++];
        if(flag[o]) continue;
        flag[o] = 1;
        for(int i = h[o], j; ~i;i = ne[i])
        {
            j = e[i];
            if(v[j] > v[o] + w[i])
            {
            	v[j] = v[o] + w[i];
                if(w[i]) q[++ tt] = j;
                else q[-- hh] = j;
            }
        }
    }
    for(int i = 1;i <= n;i ++)
    {
        if(v[id[i]] > n) write(-1, '\n');
        else write(v[id[i]], '\n');
    }
    return 0;
}

T3

题目

image

Solution

这类题要首先考虑设未知数解方程，首先考虑树的情况，设$1$号节点的期望距离为$x$，那么由于这个期望是线性相关的，所以从每一个点出发的期望都可以表示为$kx+b$的形式，最后统计回$1$时就可以写出一个方程$x=ax+b$求解即可。

拓展到本题，对于每一个环，可以再设一个未知数，然后由于没有大环所以可以用$x$来表示出这个新未知数，做法大概相似。