路人乙の小窝

我若安好，万事大吉

0%

威海市赛vp

发表于 更新于 分类于 ，

前言

其实之前也vp过很多icpc比赛了，但是感觉对我帮助最大的应该还是这场
题目链接：https://www.luogu.com.cn/contest/234038

B. 抽卡

https://www.luogu.com.cn/problem/P11868

一道猜猜题，读题之前被误差1e-6吓到以为是什么数学题，pyc跟榜看题后发现输出max(a, b) 即可（甚至不需要定义为浮点数）

H. 不是一道简单的构造题

https://www.luogu.com.cn/problem/P11874

一道做出来不敢交的题。pyc和我说B直接输出ab最大值时告诉我不敢交，我和他说H题直接输出Yes就可以……

E. 张灯结彩

https://www.luogu.com.cn/problem/P11871

一道小学数学题。对于前n-1层，每个彩灯会有三条电线与下一层相连，显然前k层共有k^2个彩灯，所以通过这种方式可以得到3 * (n - 1) * (n - 1)个彩灯。
对于第n层，只需要考虑每两个相邻彩灯之间的连线，第n层有2 * n - 1个彩灯，那么有2 * n - 2根电线。

1
2
3
4
5
6
7
int main() {
    int n, t;
    while(t--) {
        cin >> n;
        cout << 3 * (n - 1) * (n - 1) + 2 * n - 2 << endl;
    }
}

G. 最大拟合

https://www.luogu.com.cn/problem/P11873

应该算是模拟题吧

统计字符串每种长度为3的子串的数量，然后根据前两个字母分类讨论子串出现的概率，写一堆if-else就好

简单推导一下，得到最大拟合结果时，每种子串出现的概率等于其出现的次数除以其前缀出现的次数。

本题要求求最大拟合结果的自然对数，由于数值过小，在求乘法时会有很大的精度误差（最后乘到0），可以将问题转化为求自然对数的和

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
#include <bits/stdc++.h>
using namespace std;

string s;
map<string, int> calc;
map<string, double> val;

int main() {
    cin >> s;
    s += "#";
    for(int i = 2; i < s.size(); ++i) {
        string sub = s.substr(i - 2, 3);
        calc[sub]++;
    }

    double ans = 0;
    double sum = 0;
    sum = calc["HHH"] + calc["HHL"] + calc["HH#"];
    if(sum != 0) {	// 这一堆屎山代码应该可以用map或者其他东西优化一下代码风格，但是赛时就这么写过来了，反正种类数也不多。
        val["HHH"] = calc["HHH"] / sum;
        val["HHL"] = calc["HHL"] / sum;
        val["HH#"] = calc["HH#"] / sum;
    }
    sum = calc["HLH"] + calc["HLL"] + calc["HL#"];
    if(sum != 0) {
        val["HLH"] = calc["HLH"] / sum;
        val["HLL"] = calc["HLL"] / sum;
        val["HL#"] = calc["HL#"] / sum;
    }
    sum = calc["LHH"] + calc["LHL"] + calc["LH#"];
    if(sum != 0) {
        val["LHH"] = calc["LHH"] / sum;
        val["LHL"] = calc["LHL"] / sum;
        val["LH#"] = calc["LH#"] / sum;
    }
    sum = calc["LLH"] + calc["LLL"] + calc["LL#"];
    if(sum != 0) {
        val["LLH"] = calc["LLH"] / sum;
        val["LLL"] = calc["LLL"] / sum;
        val["LL#"] = calc["LL#"] / sum;
    } 

    for(int i = 2; i < s.size(); ++i) {
        string sub = s.substr(i - 2, 3);
        // cout << val[sub] << ' ';
        ans += log(val[sub]);
    }

    cout << ans << '\n';
}

L. 城堡中的皇后(鸽)

https://www.luogu.com.cn/problem/P11878

赛时不想做，赛后不想补，看题面就觉得他强的可怕……

学弟赛时一直在做，但赛后才补出来的。

话说校赛我也想出道大模拟但是我自己没写出来代码来着。

D. 找数

https://www.luogu.com.cn/problem/P11870

赛时胡了个假做法wa了几发。其实题意挺简单的，也可以想到是个组合数题，但是具体怎么算一直没想到。

题意：给定1~n，共n个数，选出m个数，要求奇数位置都为奇数，偶数位置都为偶数

解法：直接去求方案数并不好求。注意到可以将排序后的序列的每个位置ai的值增加i，可以得到一个每个位置均为偶数的序列，且值域为2~n+m。所以问题可以转化为从2~n+m中选取m个偶数，直接套模板求即可。

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
#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const int N = 1e6 + 10;
const int mod = 998244353;
std::vector<i64> fac(N + 1, 1), invfac(N + 1, 1);

i64 qmi(i64 a, i64 b) {
    i64 res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    invfac[n] = qmi(fac[n], mod - 2);
    for (int i = n - 1; i >= 0; i--) {
        invfac[i] = invfac[i + 1] * (i + 1) % mod;
    }
}
i64 C(int n, int m) {  // 组合数
    if (m > n || m < 0) {
        return 0;
    }
    return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}

int n, m;
int main() {
    cin >> n >> m;
    init(N);
    cout << C((n + m) / 2, m) << '\n';
}

看题解有人用隔板法直接求出了方案数，我们赛时想到了隔板法，但没能求出来方案数。

J. 收徒

https://www.luogu.com.cn/problem/P11876

本来以为是个网格图dp或dfs板子题，结果数据范围太大，dp会MLE，dfs会TLE。

考虑到$2≤H,W≤2e5$,这个数据范围甚至不能够每个点遍历一遍

注意到小威只能向下或者向右走，我们可以将所有的棋子按照y坐标排序，排序后求出了一串x的值，那么可以问题可以转化为求这一串x的最长不下降子序列，可以用dp来做。

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
#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

int h, w, n;

int main() {
    cin >> h >> w >> n;
    vector<pii> node(n);
    for(int i = 0; i < n; ++i) {
        cin >> node[i].first >> node[i].second;
    }

    sort(node.begin(), node.end(), [](const pii& a, const pii& b) {
        if(a.second != b.second) return a.second < b.second;
        return a.first < b.first;
    });

    vector<pii> vec;
    vector<int> p(n);
    vec.push_back(node[0]);

    for(int i = 1; i < n; ++i) {
        if(vec.back() < node[i]) {
            vec.push_back(node[i]);
            p[i] = vec.size() - 1;
        } else {
            int pos = upper_bound(vec.begin(), vec.end(), node[i]) - vec.begin();
            vec[pos] = node[i];
            p[i] = pos;
        }
    }

    cout << vec.size() << '\n';
    vector<pair<int, int>> ans(vec.size());

    ans.emplace_back(h, w);
    for(int i = n - 1, j = vec.size() - 1; i >= 0; --i) {
        if(p[i] == j) {
            ans.push_back(node[i]);
            j--;
        }
    }

    int x = 1, y = 1;
    reverse(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); ++i) {
        while(y < ans[i].first) {
            y++;
            cout << 'D';
        }
        while(x < ans[i].second) {
            x++;
            cout << 'R';
        }
    }

    return 0;
}

A. 大家的公因数2

https://www.luogu.com.cn/problem/P11867

题意说的挺直接的。

根据题意，我们大概需要实现以下2个功能：

  1. 判断连接。两个点之间有无向边连接当且仅当他们有一个大于1的公因数 -> 可以用质因数分解，将有相同质因数的所有数连边，并用并查集维护；
  2. 判断路径异或和能否为w -> 先判断连接，只有u和v联通时才存在路径，之后可以用线性基判断uv路径能否得到异或和为w

质因数分解：

欧拉筛有一个很好的性质，即每个合数只会被自己最小的质因数筛一次。我们可以维护每个数的lpf（最小质因子），每次去除以当前值的lpf，即可在O(V)复杂度实现预处理，O(nlogV)复杂度质因数分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> lpf(M);
vector<int> primes;
vector<bool> isprime(M, true);

void Init() {
    for(int i = 2; i < M; ++i) {
        if(isprime[i]) {
            primes.push_back(i);
            lpf[i] = i;
        }
        for(int j = 0; j < primes.size() && i * primes[j] < M; ++j) {
            isprime[i * primes[j]] = false;
            lpf[i * primes[j]] = primes[j];
            if(i % primes[j] == 0) break;
        }
    }
}

线性基：

在线性代数中大概学过类似的东西，一组线性无关的向量的线性组合可以表示出其张成空间中每一个向量。在ICPC中，线性基可以维护一组数的异或值的最大最小值、第k大/小值，以及可以判断能否通过异或得到某个数。

假设数据范围为$[0, 2^{BIT - 1}]$，那么可以对于从BIT到0的每一位j可以保存一个值，这个值的最高位的1位于第j位。当需要插入一个最高位为j的数x时，我们需要判断：

  1. 第j位是否保存了值（不为0）。如果保存了一个值y，说明原来的空间可以通过异或求出一个，那么我们将x的值更新为x^y，显然新的值小于原来的x，且第j位不为0，可以继续遍历
  2. 如果在某一位j为0，那么说明原来的空间不能通过异或求出一个最高位1在第j位的值，那么我们将第j位的值保存为x
  3. 如果遍历到最后一位得到x为0，说明原来的空间可以得到x，我们不处理x

判断能否通过异或得到一个值x时，直接将x每一位j判断是否为1，若为1将x与p[j]异或，最后判断能否得到0即可。

说起来有点抽象，但是代码还是比较简单的。

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
class LinearBasic {
private:
    vector<int> p;
public:
    LinearBasic() : p(31, 0) {}
    void insert(int x) {
        for(int i = 30; i >= 0; --i) {
            if(x >> i) {
                 if(p[i] == 0) {
                    p[i] = x;
                    return;
                 }
                 x ^= p[i];
            }
        }
    }

    bool check(int x) {
        for(int i = 30; i >= 0; --i) {
            if(x >> i) {
                if(p[i] == 0) return false;
                x ^= p[i];
            }
        }
        return x == 0;
    }
};

完整代码

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 1;
const int M = 1e7 + 2;
int n, q;

vector<int> lpf(M);
vector<int> primes;
vector<bool> isprime(M, true);

void Init() {
    for(int i = 2; i < M; ++i) {
        if(isprime[i]) {
            primes.push_back(i);
            lpf[i] = i;
        }
        for(int j = 0; j < primes.size() && i * primes[j] < M; ++j) {
            isprime[i * primes[j]] = false;
            lpf[i * primes[j]] = primes[j];
            if(i % primes[j] == 0) break;
        }
    }
}

class DSU {
private:
    vector<int> fa;
public:
    DSU(int n) {
        fa = vector<int> (n + 1);
        iota(fa.begin(), fa.end(), 0);
    }

    int find(int x) {
        if(fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    void merge(int x, int y) {
        int a = find(x), b = find(y);
        if(a == b) return;
        fa[a] = b;
    }
};

int arr[N];

class LinearBasic {
private:
    vector<int> p;
public:
    LinearBasic() : p(31, 0) {}
    void insert(int x) {
        for(int i = 30; i >= 0; --i) {
            if(x >> i) {
                 if(p[i] == 0) {
                    p[i] = x;
                    return;
                 }
                 x ^= p[i];
            }
        }
    }

    bool check(int x) {
        for(int i = 30; i >= 0; --i) {
            if(x >> i) {
                if(p[i] == 0) return false;
                x ^= p[i];
            }
        }
        return x == 0;
    }
};

int main() {
    cin >> n;
    Init();
    DSU dsu(M);

    for(int i = 1, x, y; i <= n; ++i) {
        cin >> arr[i];
        if(arr[i] == 1) continue;
        y = lpf[arr[i]];
        for(x = arr[i] / y; x > 1; x /= lpf[x]) {
            dsu.merge(lpf[x], y);
        }
    }
    

    map<int, LinearBasic> ma;
    for(int i = 1, x; i <= n; ++i) {
        cin >> x;
        ma[dsu.find(lpf[arr[i]])].insert(x);
    }

    cin >> q;
    for(int i = 1, u, v, w; i <= q; ++i) {
        cin >> u >> v >> w;
        u = lpf[u], v = lpf[v];
        if(dsu.find(u) != dsu.find(v)) cout << "No" << '\n';
        else {
            LinearBasic& T = ma[dsu.find(u)];
            if(T.check(w)) cout << "Yes" << '\n';
            else cout << "No" << '\n';
        }
    }

    return 0;
}

后记

迷迷糊糊的过掉了签到题，之后就卡的很头痛。赛后看题解（尤其是收徒和找数两个题），真的有种茅塞顿开的感觉。跟着题解学了线性基，去复习了欧拉筛，补掉了A，也算是暂时心满意足了。

不过我还是讨厌大模拟题……

我很可爱，请给我钱qwq