# A

超级无敌水题

c++

void solve () {
    cin >> a >> b;
    
    if (a == "fine" && b == "fine")
        cout << 4 << endl;
    else if(a == "fine" && b != "fine")
        cout << 3 << endl;
    else if(a != "fine" && b == "fine")
        cout << 2 << endl;
    else
        cout << 1 << endl;
}

# B

暴力中的暴力题，字符串长度最大只有 $100$ ，暴力遍历即可

python

s = input()

res = 0

for i in range(len(s) - 2):
    if s[i] == 'A':
        for j in range(i + 1, len(s) - 1, 1):
            if s[j] == 'B':
                for k in range(j + 1, len(s), 1):
                    if s[k] == 'C' and k - j == j - i:
                            res += 1

print(res)

# C

也是大水题，给你一个无向图，问你要删多少条边，才能把这个图删成没有重边和自环的图。

开始时总想成搜索，搜出一条路之后看边数，想太复杂了，开个 map<PII, bool> mp 用作标记就行

c++

void solve () {
    cin >> n >> m;
    int t = 0;
    map<PII, bool> mp;

    for (int i = 1, a, b; i <= m; i++) {
        cin >> a >> b;

        if (a == b)
            t++;
        else if (mp[{min(a, b), max(a, b)}])
            t++;
        
        mp[{min(a, b), max(a, b)}] = true;
    }

    cout << t << endl;
}

# D

# 题目大意

给你一个由 $0$ 和 $1$ 组成的字符串，你可以进行一种操作：交换相邻字符
问，若想要让所有 $1$ 都相邻，最少的操作次数是多少

# 解题思路

贪心贪心贪心，这题本质就是货仓选址，但是与货仓选址不同的是，需要考虑到，每个需要移动的 $1$ 并不是移动到中间的 $1$ 的位置，而挪到距离中间的 $1$ 可能有一些距离

cpp

void solve () {
    cin >> n >> s;
    vector<int> v;
    for (int i = 0; i < s.size(); i++)
        if (s[i] == '1')
            v.push_back(i);

    int t = v.size() / 2;
    int res = 0;

    for (int i = 0; i < t; i++)
        res += (v[t] - v[i] - 1), res -= t - i - 1;

    for (int i = t + 1; i < v.size(); i++)
            res += (v[i] - v[t] - 1), res -= i - t - 1;

    cout << res << endl;
}

# E

# 问题大意：

我们有一个数组 $A$ 和一个整数 $K$ ，要求对于数组中的每个元素 $A_i$ ，找到它的最大公约数 $GCD$ ，且满足以下两个条件：

$A_i$ 可以被 $GCD$ 整除
在数组中至少有 $K$ 个元素能够被这个 $GCD$ 整除
我们需要找出最大的 $GCD$ ，即对于每个 $A_i$ ，找出一个能使 $A_i$ 与 $K$ 个元素的 $GCD$ 最大的值

# 解题思路

# 统计每个数的出现次数

首先，定义一个数组 s[] 来记录每个数在数组 $A$ 中的出现次数。假设最大元素为 $M$ ，即 M = max(A)
通过一次遍历 $A$ ，我们可以完成这个统计操作，时间复杂度为 $O(N)$ ，其中 $N$ 是数组 $A$ 的长度

# 计算每个数的倍数出现次数

接下来，我们要计算每个数在数组中所有倍数的元素个数。我们定义一个数组 t[] ，其中 t[d] 表示所有能够被 $d$ 整除的元素的个数，即：

$t_d = \sum_{d \mid n} s_n$

具体的做法是，对于每个数从 $1$ 到 $M$ ，遍历它的倍数 $( d, 2d, 3d, \dots )$ ，将 s[j] 加到 t[d] ，其中 $j$ 是 $d$ 的倍数

# 时间复杂度

这个过程的时间复杂度是 $O(M \log M)$ ，因为我们遍历每个数的倍数，而倍数的个数是按对数增长的

# 一个 TLE 的代码

c++

int n, k, a[N], cnt[N], s[N], maxx = 0;
void solve () {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i], s[a[i]]++, maxx = max(maxx, a[i]);
    
    // 初始化 t 数组
    for (int i = 1; i <= maxx; i++) {
        int t = i;
        
        while (t <= maxx)
            cnt[i] += s[t], t += i;
    }

    for (int i = 1; i <= n; i++)
        for (int j = a[i]; j >= 1; j--)
            if (a[i] % j == 0 && cnt[j] >= k) {
                cout << j << endl;
                break;
            }
}

这样写的话，其实复杂度达到了

O(a_i \times n)

，

a_i

最大到

1e6

了，这个复杂度是不可接受的

# 优化代码

cpp

int n, k, a[N], cnt[N], s[N], res[N], maxx = 0;
void solve () {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i], s[a[i]]++, maxx = max(maxx, a[i]);
    
    // 初始化 t 数组
    for (int i = 1; i <= maxx; i++) {
        int t = i;
        
        while (t <= maxx)
            cnt[i] += s[t], t += i;
    }

    for (int i = maxx; i >= 1; i--)
        if (cnt[i] >= k)
            for (int j = i; j <= maxx; j += i)
                if (!res[j])
                    res[j] = i;

    for (int i = 1; i <= n; i++)
        cout << res[a[i]] << endl;
}

我们不妨遍历每个

GCD

，如果当前这个数

\ge k

的话，那么代表它能做被选出来的那个数，则从

i

开始往最大的数找，如果当前数没有找到过更大的

GCD

过，则我们当前遍历到的数就是最优的，每次递增的时候是 j += i ，因为首先要满足

a_i

能整除

GCD

这个条件

贪心图论 ABC 小学数学暴力预处理

# A

# B

# C

# D

# 题目大意

# 解题思路

# E

# 问题大意：

# 解题思路

# 统计每个数的出现次数

# 计算每个数的倍数出现次数

# 时间复杂度

# 一个 TLE 的代码

# 优化代码

货仓选址

数据库建模与E-R图