好久没写算法题了，一写才发现自己真忘光了。还好这几题基本上都是暴力题（

头好痛好想睡觉啊

A-子串分值

第一题一看就有点蒙，读完题发现不难，然后写了个暴力，过了样例，然后很当然的 TLE 了

于是写了个简单的记忆优化，但复杂度还是 O(n2logn)O(n^2logn) ，所以又爆了

爆两次之后仔细分析了一下，他要求的字符串中总共就 26 个字母，我们不妨从字符出发，求每个字符的贡献度。例如样例是ababc的话，对于第一个a贡献度就是 2，第二个b贡献度就是 4，以此类推。

因为该字符能做出贡献的 substr 中一定只包含一个它，所以我们往左右两边找上一个和下一个它即可。而贡献度 DiD_i 的计算方式可由乘法原理得：

Di=(i−l)(r−i)D_i=(i-l)(r-i)

也就是左边字符数+1 乘右边字符数+1。而把两个乘数算出来再相乘的复杂度应该是O(n)O(n)，按理说是可以过的

那为什么没过呢，因为我忘记开long long了 XD
代码如下

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
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
using namespace std;
long long ans, l[114514], r[114514], c[32];
string s;
// map<string, long long> memory;
// long long count(string str)
// {
// if (memory.find(str) != memory.end())
// return memory[str];
// long long res = 0, a[256];
// for (long long i = 0; i < 256; i++)
// a[i] = 0;
// for (long long i = 0; i < str.length(); i++)
// a[str[i]]++;
// for (long long i = 0; i < 256; i++)
// if (a[i] == 1)
// res++;
// memory[str] = res;
// return res;
// }
//  O(n^2logn) -> O(n)
signed main()
{
    ios::sync_with_stdio(false);
    cin >> s;
    for (long long i = 0; i < 32; i++)
        c[i] = -1;
    for (long long i = 0; i < s.length(); i++)
        l[i] = i - c[(long long)(s[i] - 'a')], c[(long long)(s[i] - 'a')] = i; // find pre char
    for (long long i = 0; i <= 26; i++)
        c[i] = s.length();
    for (long long i = s.length() - 1; i >= 0; i--)
        r[i] = c[(long long)(s[i] - 'a')] - i, c[(long long)(s[i] - 'a')] = i;
    for (long long i = 0; i < s.length(); i++)
        ans += l[i] * r[i];
    // for (long long i = 2; i <= s.length(); i++)
    // for (long long j = 0; j < s.length() - i + 1; j++)
    // {
    // string subs = s.substr(j, i);
    // sort(subs.begin(), subs.end());
    // ans += count(subs);
    // }
    cout << ans;
    return 0;
}

B-成绩分析

直接贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
    int n, sum = 0, minn = 114514, maxx = -1919810;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;
        maxx = max(maxx, a);
        minn = min(minn, a);
        sum += a;
    }
    printf("%d\n%d\n%.2lf", maxx, minn, sum * 1.0 / n);
    return 0;
}

C-画中漂流

这道题一看就像 DP，再一看确实是的，找一下它的状态转移方程。由于距离大于等于 D 就寄了，所以变量应该找时间和体力，列关于时间ii和体力jj的转移方程。当前状态应该等于上一状态用体力和不用体力的方案数之和，即

F(i,j)=F(i−1,j)+F(i−1,j+1)F(i,j)=F(i-1,j)+F(i-1,j+1)

然后我们又知道时间为 0 时只要游了就不会似，所以初始化ans[0][m]=1。注意，每次还需要检查似了没，也就是step=D+(m-j)-(i-m+j)。（花一点体力就游 1 米，共 D 米）

输出ans[t][0]，也就是时间为 t 时，用完 m 点体力的总方案数，别忘了long long和取模。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
int ans[3072][3072], d, t, m;
signed main()
{
    ios::sync_with_stdio(false);
    cin >> d >> t >> m;
    ans[0][m] = 1;
    for (int i = 1; i <= t; i++)
        for (int j = 0; j <= m; j++)
        {
            int step = d + (m - j) - (i - (m - j));
            if (step > 0)
                ans[i][j] = (ans[i - 1][j] + ans[i - 1][j + 1]) % mod;
        }
    cout << ans[t][0];
    return 0;
}

D-乘法表

这题我们理解了进制转换的方法就行，注意大于等于 10 的数字用 ascii 字母表示。

代码如下

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
#include <iostream>
using namespace std;
int n;
string ch4nge(int x, int y)
{
    string str, res;
    while (x)
    {
        int add = x % y;
        if (add >= 10)
            str += add - 10 + 'A';
        else
            str += add + '0';
        x /= y;
    }
    for (int i = 0; i <= (str.length() / 2); i++)
        res += str[str.length() - i - 1];
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j <= i; j++)
            cout << ch4nge(i, n) << '*' << ch4nge(j, n) << '=' << ch4nge(i * j, n) << ' ';
        cout << '\n';
    }
    return 0;
}

E-日期识别

纯纯大模拟，代码如下

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
#include <cstdio>
using namespace std;
short solve(char mon[])
{
    if (mon[0] == 'J' && mon[1] == 'a' && mon[2] == 'n')
        return 1;
    else if (mon[0] == 'F' && mon[1] == 'e' && mon[2] == 'b')
        return 2;
    else if (mon[0] == 'M' && mon[1] == 'a' && mon[2] == 'r')
        return 3;
    else if (mon[0] == 'A' && mon[1] == 'p' && mon[2] == 'r')
        return 4;
    else if (mon[0] == 'M' && mon[1] == 'a' && mon[2] == 'y')
        return 5;
    else if (mon[0] == 'J' && mon[1] == 'u' && mon[2] == 'n')
        return 6;
    else if (mon[0] == 'J' && mon[1] == 'u' && mon[2] == 'l')
        return 7;
    else if (mon[0] == 'A' && mon[1] == 'u' && mon[2] == 'g')
        return 8;
    else if (mon[0] == 'S' && mon[1] == 'e' && mon[2] == 'p')
        return 9;
    else if (mon[0] == 'O' && mon[1] == 'c' && mon[2] == 't')
        return 10;
    else if (mon[0] == 'N' && mon[1] == 'o' && mon[2] == 'v')
        return 11;
    else
        return 12;
}
int main()
{
    char mon[4], day[3];
    mon[0] = getchar();
    mon[1] = getchar();
    mon[2] = getchar();
    mon[3] = day[2] = '\0';
    day[0] = getchar();
    day[1] = getchar();
    if (day[0] != '0')
        printf("%d %s", solve(mon), day);
    else
        printf("%d %c", solve(mon), day[1]);
    return 0;
}

F-Fibonacci 集合

又不是不能用本地（

感觉是维护一个集合依次算或维护一个堆 or 栈然后弹出较小的值，再迭代得到第 2020 个，但我懒得写了

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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int nocode()
{
    vector<int> num;
    num.push_back(1);
    num.push_back(2);
    num.push_back(3);
    num.push_back(5);
    num.push_back(8);
    int cnt = 5, a, b, c, x;
    while (cnt < 2020)
    {
        for (int i = 0; i < 2021; i++)
        {
            x = num[i];
            a = 3 * x + 2, b = 5 * x + 3, c = 8 * x + 5;
            if (find(num.begin(), num.end(), a) == num.end())
            {
                num.push_back(a);
                cnt++;
            }
            if (find(num.begin(), num.end(), b) == num.end())
            {
                num.push_back(b);
                cnt++;
            }
            if (find(num.begin(), num.end(), c) == num.end())
            {
                num.push_back(c);
                cnt++;
            }
            sort(num.begin(), num.end());
        }
    }
    cout << num[2019];
    return 0;
}
int main()
{
    cout << 41269;
    // 你说的对，但是我在本地暴力了
    return 0;
}

G-互质

计算器都行，也是面向答案，答案好像是1008（代码没留）

H-数青蛙

6，这个我用记事本写的

1
2
3
4
5
6
7
8
#include <iostream>
using namespace std;
int main()
{
    // o.O
    cout << 14 * 2 + 15 * 3 + 16 + 17 * 4 + 18 * 2 + 20 * 8;
    return 0;
}

J-蛇形填数

没找到代码（

找规律，分奇偶层，每一层的数字填充方向奇数层从右到左，偶数层从左到右，第 n 行第 n 列的数位于第 2n-1 层。对于第 n 行第 n 列的数，所在的层数为 2n-1 层，该层的起始数字 S(m)=1+(2n+1)(n−1)，其中 m 为层数 2n-1，而第 n 行第 n 列的数是该层的第 n 个位置，因此其值为 S(m)−(n−1)，即1+2n(n−1)1+2n(n−1)。代入 n=20：1+2×20×19=1+760=761

K-既约分数

若一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。问有多少个既约分数分母是 1 到 2020 之间的整数（包括 1 和 2020）？

没看完问题就脑抽写了个欧拉函数，然后发现不太对（第一遍甚至交了个整除上去，脑子昏了）

看完发现就是枚举和各数字对应的在区间[1,2020][1,2020]内互质的数，然后统计

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int euler_ex(int a) // o.o
{
    int cnt = 0;
    for (int n = 1; n <= 2020; n++)
        if (gcd(n, a) == 1) //&& ((n > a) ? (n / a * a == n) : (a / n * n == a)))
            cnt++;
    return cnt;
}
int main()
{
    int ans = 0;
    for (int i = 1; i <= 2020; i++)
        ans += euler_ex(i);
    cout << ans;
    return 0;
}

End

A 题想完头就炸了…因为真的好久没写题，连 cpp 都很久没用过，一时间啥也想不起。甚至连开 vector、bitset 我都差点忘记怎么开了。很多高中时期会的优化技巧也忘干净了，然后一些基本算法我也感觉很陌生（说真的现在让我写个高精减法我都不一定能写出来，快排也是，并查集，堆，图之类的数据结构也不记得了）。如果出个图论我恐怕只会用邻接矩阵存。然后那天听说考 KMP，也不会。

所幸这次啥也没考，纯暴力（

以前做梦都想搞台电脑，然后写一天算法题，现在怎么就只会打游戏了呢

打 ACM 感觉自己的脑子还是不够用，还是老老实实继续学CTF吧。目前还是想让自己的技术面尽量拓宽一点，等我对计算机学科整体有了自己的认知以后再精进