赛题题解

Problem - C - Codeforces

先给每一圈赋一个权重dis

算该点具体在那一个圈权值多少 就用dis[min(min(i, j), min(n-i, n-j))]

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

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/
int dis[5] = {1, 2, 3, 4, 5};
void solve()
{
    vector<string> nums;
    int n = 10;
    while (n--)
    {
        string s;
        cin >> s;
        nums.emplace_back(s);
    }
    ll res = 0;
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            if (nums[i][j] == '.')
                continue;
            else
            {
                res += dis[min(min(i, j), min(9 - i, 9 - j))];
            }
        }
    }
    cout << res << endl;
}

int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

Problem - E - Codeforces

赛时调了半天没调出来，寄，害的F也没调出来/kk

二分的板子没问题啊，主要是r的范围错了，r是要超过x很多的，而且还要同时注意 开ll 如果太大的话mid的范围也要注意

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

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/
const int N = 2e5 + 10;
int nums[N];
int n, m;
bool check(int mid)
{
    ll res = 0;
    for (int i = 0; i < n; i++)
    {
        if (mid - nums[i] >= 0)
            res += (mid - nums[i]);
        if (res > m)
            return false;
    }
    return true;
}

void solve()
{

    cin >> n >> m;
    memset(nums, 0, sizeof(nums));
    ll l = 1, r = 2e9 + 1;
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    int res = 1, mid;

    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (check(mid))
        {
            res = mid;
            l = mid + 1;
        }
        else
        {

            r = mid - 1;
        }
    }
    cout << res << endl;
}

int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

Problem - G - Codeforces

AB->BC BA->CB

那么只要有B就可以把所有的A都消除掉（只能消除一边）分几种情况来讨论 首先B在首或尾的时候如果中间没有B 可以全部消除完

如果有两个B连在一起的话只可能是B..BB…B 中间的..可能是A也可能是B 都可以把所有A消除（左边的B消掉左边的A 右边的B消除右边的B

如果没有两个B连在一起的话那么中间必然会有空缺 AABABAA那么只能消掉三个中的两个 所以最后要减去A最少的一段

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

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/

int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int n;
    cin >> n;
    while (n--)
    {
        string s;
        cin >> s;
        bool flag = false;
        ll sum = 0;
        int n = s.size();
        int cnt = 0;
        int minn = 1e9 + 7;
        if (s[0] == 'B' || s[n - 1] == 'B')
            flag = true;
        for (int i = 0; i < n; i++)
        {
            if (s[i] == 'A')
                sum++, cnt++;
            else if (s[i] == 'B')
            {
                minn = min(minn, cnt);
                cnt = 0;
                if (i + 1 < n && s[i + 1] == 'B')
                    flag = true;
            }
        }
        minn = min(minn, cnt);
        if (flag)
        {
            cout << sum << endl;
        }
        else
        {
            if (minn != 1e9 + 7)
                cout << sum - minn << endl;
            else
                cout << 0 << endl;
        }
    }

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

Problem - H - Codeforces

寻找基环树（套路）因为这个题不仅要判断环 而且需要储存

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/

void solve()
{
    int n, a, b; // a is M b is V
    cin >> n >> a >> b;
    vector<vector<int>> graph(n + 1);
    // 存无向图
    for (int i = 0; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    if (a == b)
    {
        cout << "NO" << endl;
        return;
    }
    vector<int> incircle(n + 1, 0), vis(n + 1, 0), pre(n + 1, 0);
    bool ok = false;
    
    function<void(int, int)> dfs = [&](int u, int fa)
    {
        for (int v : graph[u])
        {
            if (ok)
                return;
            if (v == fa)
                continue;
            if (vis[v]) // 第二次经过代表有环
            {
                ok = true;
                incircle[v] = 1; // 标记在环上
                int x = u;
                do
                {
                    incircle[x] = 1;
                    x = pre[x];
                } while (x != v); // 标记环上的所有点
            }
            else
            {
                vis[v] = 1;
                pre[v] = u;
                dfs(v, u);
            }
        }
    };
    vis[1] = 1;
    dfs(1, 0);
    // 如果已经在环上了
    if (incircle[b]) 
    {
        cout << "YES" << endl;
        return;
    }
    int goal = -1, gdis = -1;
    queue<PII> q;
    // 清空vis数组
    vis.assign(n + 1, 0);
    q.push({b, 0});
    vis[b] = 1;
    while (!q.empty())
    {
        int u = q.front().first;
        int dis = q.front().second;
        q.pop();
        for (int v : graph[u])
        {
            if (vis[v])
                continue;
            if (incircle[v])
            {
                goal = v;
                gdis = dis + 1;
                goto end;
            }
            else
            {
                q.push({v, dis + 1});
                vis[v] = 1;
            }
        }
    }
end:;
    if (goal == a)
    {
        cout << "NO" << endl;
        return;
    }

    while (!q.empty())
    {
        q.pop();
    }
    int tdis = -1;
    vis.assign(n + 1, 0);
    q.push({a, 0});
    vis[a] = 1;
    while (!q.empty())
    {
        int u = q.front().first;
        int dis = q.front().second;
        q.pop();
        for (int v : graph[u])
        {
            if (vis[v])
                continue;
            if (v == goal)
            {
                tdis = dis + 1;
                if (tdis <= gdis)
                    cout << "NO" << endl;
                else
                    cout << "YES" << endl;
                return;
            }
            else
            {
                q.push({v, dis + 1});
                vis[v] = 1;
            }
        }
    }
}

int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

5153. 删除 - AcWing题库

一位数 两位数 三位数 分别表达 而四位数及以上时 不需要 因为1000 可以被8 整除 而所有的四位数 如1000 2000 3000 等都可以被8整除
而所有的四位数都可以被表示为 1000 * k + x （x为一位数或者两位数 或者三位数 ） 更高位的以此类推
所以只需要枚举1 2 3 位数

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

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/

int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '8')
        {
            cout << "YES" << endl;
            cout << "8" << endl;
            return 0;
        }
        if (s[i] == '0')
        {
            cout << "YES" << endl;
            cout << "0" << endl;
            return 0;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int a = ((s[i] - '0') * 10 + s[j] - '0');
            if (a % 8 == 0)
            {
                cout << "YES" << endl;
                cout << a << endl;
                return 0;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            for (int k = j + 1; k < n; k++)

            {
                int a = ((s[i] - '0') * 100 + (s[j] - '0') * 10 + s[k] - '0');
                if (a % 8 == 0)
                {
                    cout << "YES" << endl;
                    cout << a << endl;
                    return 0;
                }
            }
        }
    }
    cout << "NO" << endl;

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

Problem - D - Codeforces

给出区间 然后反转 可以用差分 当这个下标被旋转奇数次的时候就需要旋转 被旋转偶数次的时候 就相当于没动 不用旋转

每次旋转要找到唯一一个i 使得a[i] <= x && b[i] >= x 然后旋转a[i] b[i] 的元素

可以用cnt（类似差分数组）记录x出现的次数 并且不需要根据x寻找第二行所说的那个区间 而是遍历区间 找到这个区间的x

遍历区间 然后取出子串 从left到mid依次与right到mid交换 （根据sum的奇偶来判断）sum就是当前位置和对称位被交换次数之和（累计 因为是差分）然后输出子串

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

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/

void solve()
{
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;
    vector<int> a(k), b(k);
    vector<int> cnt(n);
    for (int i = 0; i < k; i++)
        cin >> a[i], a[i]--;
    for (int i = 0; i < k; i++)
        cin >> b[i], b[i]--;
    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        int x;
        cin >> x;
        cnt[x - 1]++;
    }

    for (int i = 0; i < k; i++)
    {
        string s1 = s.substr(a[i], b[i] - a[i] + 1);
        int sum = 0;
        int l = a[i];
        int r = b[i];
        for (int j = l; j <= (l + r) / 2; j++)
        {
            sum += cnt[j] + cnt[r - j + l];
            if (sum % 2)
                swap(s1[j - l], s1[r - j]);
        }
        cout << s1;
    }
    cout << endl;
}

int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int T;
    cin >> T;
    while (T--)
        solve();

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

100019. 将数组分割成最多数目的子数组 - 力扣（LeetCode）

按位与的结果只能越来越小 因此要求最小的按位与的子数组的和 就是全部与在一起的和 就是最小的 但是又特殊情况 就是 当全部的与为0时 可能中间有一部分已经为0了 这样就可以拆成很多个与为0的子数组 如果不为0 那必然整个数组的与就是最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxSubarrays(self, nums: List[int]) -> int:
        t = nums[0]
        n = len(nums)
        cnt = 0
        for i in range(1, n):
            if t == 0:
                cnt += 1
                t = nums[i]
            t&=nums[i]
        if t == 0:
            cnt += 1
        return cnt if cnt != 0 else 1

2872. 可以被 K 整除连通块的最大数目 - 力扣（LeetCode）

由于题目说了 整棵树所有结点的和一定为k的倍数 那么从中取出一棵节点和为k的倍速的子树 剩下的部分的结点和一定也为k的倍数

因此可以自底向上递归 每次找到一棵节点和为k的倍数的子树 就直接加入答案 

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
class Solution:
    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:
        # 建树
        self.link = [[] for _ in range(n)]
        for s, e in edges:
            self.link[s].append(e)
            self.link[e].append(s)
        self.res = 1
        # 递归
        self.dfs(0, -1, values, k)
        return self.res
	
    
    	def dfs(self, node, parent, values, k):
            node_sum = values[node]
            for child in self.link[node]:
                # 因为建的是无向图 要去掉父节点
                if child == parent:
                    continue
                child_sum = dfs(child, node, values, k)
                if child_sum % k == 0:
                    self.res += 1
                else:
                    node_sum += child_sum
            return node_sum

100086. 有序三元组中的最大值 II - 力扣（LeetCode）

遍历j 算出j的前缀的最大值和j的后缀的最大值 因为求得是(nums[i] - nums[j]) * nums[k] 所以i k要尽量大

后缀就是从n - 1往前 求出每一个j值所对应的最大后缀 前缀同理

最后直接计算

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        surmax = [-1] * (n + 1)
        for i in range(n - 1, -1, -1):
            surmax[i] = max(surmax[i + 1], nums[i])
        premax = nums[0]
        ans = 0
        for i in range(n - 1):
            ans = max(ans, (surmax[i + 1] * (premax - nums[i])))
            premax = max(premax, nums[i])
        return ans

100076. 无限数组的最短子数组 - 力扣（LeetCode）

滑动窗口

子数组是连续的 要求最短的就是先看看 能凑成几个完整的原序列 然后再两个序列间 凑出剩余的

剩余的就用滑动窗口来算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minSizeSubarray(self, nums: List[int], target: int) -> int:
        n = len(nums)
        total = sum(nums)
        nums = nums + nums
        x = target // total
        target %= total
        s = l = 0
        ret = 10 ** 9
        for i in range(n * 2):
            s += nums[i]
            while s > target:
                s -= nums[l]
                l += 1
            if s == target:
                ret = min(ret, i - l + 1)
        return ret + x * n

8028. 执行操作使两个字符串相等 - 力扣（LeetCode）

O(n^2)

首先 1的个数的奇偶不同就不能变成一样的 返回-1

用dfs计算加上@cache变为记忆化搜索

每次变都是两个一起变 操作1 第一个变的时候就记录这次变化的消耗 然后另一个就相当于可以免费变化 记录免费变化的次数

操作2 不能像操作1那样在任意位置变 而是 只要用了操作2 必定是连续的两个变

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
class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        if s1.count('1') % 2 != s2.count('1') % 2:
            return -1

        n = len(s1)
        # 从前往后遍历 
        @cache
        def dfs(i: int, j: int, pre_rever: bool) -> int:
            # 到头了
            if i == n:
                return inf if j or pre_rever else 0
            # 不需要反转
            # 当前不相等 但是前面有反转了 导致这两个相等
            if s1[i] != s2[i] and pre_rever:
                return dfs(i + 1, j, False)
            # 当前相等 并且前面没反转 这两个仍然相等
            if s1[i] == s2[i] and not pre_rever:
                return dfs(i + 1, j, False)
            
            # 需要反转 分别用操作1 和 操作2 取最小值 记得加上反转的代价 操作1为x 操作2为1
            res = min(dfs(i + 1, j + 1, False) + x, dfs(i + 1, j, True) + 1)
            
            # 操作1的免费反转（操作2的免费反转在上面）
            if j:
                res = min(res, dfs(i + 1, j - 1, pre_rever))
            
            return res

        return dfs(0, 0, False)

O(n)

dp做法

把所有需要变的位置先写出来 然后每次消除 通过操作1 每次消除一个 消耗x/2（最后必定是可以消完的因为不行的情况已经返回-1了）或者用操作2 每次消除两个 比如1，4位置需要变化 那就需要3次操作12 23 34 这样 需要消耗 p[i] - p[i - 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        if s1 == s2:
            return 0
        p = [i for i, (x, y) in enumerate(zip(s1, s2)) if x != y]
        if len(p) % 2:
            return -1
        m = len(p)

        @cache
        def dfs(i: int) -> int:
            # 递归出口  到-1 说明是正常退出 （操作1 的0 - 1  操作2 的1 - 2）
            if i == -1:
                return 0
            # 到-2说明有问题 返回inf代表这个答案不能用
            if i == -2:
                return inf
            return min(dfs(i - 1) + x, dfs(i - 2) + (p[i] - p[i - 1]) * 2)
        return dfs(m - 1) // 2

再翻译成递推 dfs(i) -> f[i] 注意翻译的时候 i - 1和i - 2 如果是f[i - 1] 和 f[i - 2] 会导致最后 i == -1 和i == -2 无法表示 所以 每个下标加上2

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        f = [0] * (m + 1)
        f[0] = 0
        f[1] = x
        for i in range(1, m):
            new_f = min(f[i] + x, f[i - 1] + (p[i] - p[i - 1]) * 2)
           	f[0] = f[1]
            f[1] = new_f
        return f[m] // 2

​ 然后空间优化 

1
2
3
4
5
6
class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
    	f0, f1 = 0, x
        for i in range(1, m):
            f0, f1 = f1, min(f1 + x, f0 + (p[i] - p[i - 1]) * 2)
        return f1 // 2

2897. 对数组执行操作使平方和最大 - 力扣（LeetCode）

与 越与越小 或越或越大 而x^y + y ^ 2 < (x - d)^2 + (y + d)^2 所以 要尽量做或操作 直到最大

用位运算思考 先记录所有数每个比特位上有多少个1 然后构造尽量大的数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxSum(self, nums: List[int], k: int) -> int:
        m = max(nums).bit_length()
        cnt = [0] * m
        for x in nums:
            for i in range(m):
                cnt[i] += x >> i & 1
        ans = 0
        # 构造出k个尽可能大的数
        for _ in range(k):
            x = 0
            for i in range(m):
                if cnt[i]:
                    # 消耗该比特位上的一个1
                    cnt[i] -= 1
                    # x |= 就是直接把该位变成1 而1<<i就是对应位
                    x |= 1 << i 
            ans += x * x
        return ans % (10 ** 9 + 7)

8026. 构造乘积矩阵 - 力扣（LeetCode）

前后缀优化

类似的还有238. 除自身以外数组的乘积 - 力扣（LeetCode）

不能用乘积全部乘起来再除的方法 因为首先可能有0的情况 会导致错误 然后就是复杂度太高了

虽然说没有写循环 但是 乘积是高精度乘法 复杂度非常高所以会超时

同理 在每次计算前后缀的时候也需要取模防止数据过大超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        pre = suf = 1
        m = len(grid)
        n = len(grid[0])
        ans = [[0] * n for i in range(m)]
        mod = 12345

        for i in range(m):
            for j in range(n):
                ans[i][j] = pre % mod
                pre = pre * grid[i][j] % mod

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                ans[i][j] = ans[i][j] * suf % mod
                suf = suf * grid[i][j] % mod
        return ans

100101. 找出满足差值条件的下标 II - 力扣（LeetCode）

这种题目 下标差 然后再找满足另一个条件的 就需要 储存前缀（或后缀）的最大值和最小值

类似于股票的第一题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
        n = len(nums)
        max_idx = 0
        min_idx = 0
        for i in range(indexDifference, n):
            j = i - indexDifference
            if nums[j] > nums[max_idx]:
                max_idx = j
            elif nums[j] < nums[min_idx]:
                min_idx = j

            if abs(nums[i] - nums[max_idx]) >= valueDifference:
                return [i, max_idx]
            if abs(nums[i] - nums[min_idx]) >= valueDifference:
                return [i, min_idx]
        return [-1, -1]

100077. 最长相邻不相等子序列 II - 力扣（LeetCode）

100077. 最长相邻不相等子序列 II - 力扣（LeetCode）

100084. 最短且字典序最小的美丽子字符串 - 力扣（LeetCode）

滑动窗口

一开始写的时候 出了好多错ww 下标什么的 while循环的条件带不带等号 还有最后更新忘记判断字典序

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
class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        n = len(s)
        ans = ""
        
        l = 0
        cnt = 0
        i = 0
        for i in range(n):
            if s[i] == '1':
                cnt += 1
            while cnt > k:
                if s[l] == '1':
                    cnt -= 1
                    l += 1
            while l < n and s[l] == '0':
                l += 1
            if cnt == k:
                if len(ans) == 0:
                    ans = s[l:i + 1]
                if i - l + 1 < len(ans):
                    ans = s[l: i + 1]
                elif i - l + 1 == len(ans):
                    if s[l: i + 1] < ans:
                        ans = s[l:i + 1]

        
        return ans

6920. 得到 K 个半回文串的最少修改次数 - 力扣（LeetCode）

思路是枚举每一个串看他们是否可以分成符合要求的子串

主要分成三个部分 首先就是求 一个子字符串变成半回文串的最小修改次数

需要先预处理出每个长度n的真因子

然后用modify数组来存储每个子字符串的最少修改次数

最后用划分DP来求整个串需要的最少修改次数

dfs(i, j ) 表示把s[0]到s[j] 的字符串划分成i + 1 个子字符串

i 表示还需要分割的次数 i + 1 表示切出来i + 1段

j表示 s[0] ~ s[j]为当前需要切割的部分 （右端点）

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
# 预处理n的所有的真因子(类似于埃式筛的做法 先求出i是那几个数的真因子)
MX = 201
divisors = [[] for _ in range(MX)]
for i in range(1, MX):
    for j in range(i * 2, MX, i):
        divisors[j].append(i)

# 先求单个字串s变成半回文串的最少修改次数
def get_modify(s:str) -> int:
    
    n = len(s)
    ans = inf
    for d in divisors[n]:
        ret = 0
        for i0 in range(d):
            i, j = i0, n - d + i0
            while i < j:
                ret += s[i] != s[j]
                i += d
                j -= d
        ans = min(ans, ret)
    return ans

class Solution:
    def minimumChanges(self, s: str, k: int) -> int:
        """
        划分型DP
        dfs(i, j)
        i 为 剩余需要分割的个数
        那么i + 1 就是切出来的子串的个数
        j s[0] ~ s[j] 为当前需要切割的部分
        返回修改最少的次数
        枚举当前这一段的左端点
        L的最小值就是2i 因为 剩下i段要切 每段至少是2（因为1<=d<=len len至少是2）
        L的最大值为j - 1
        设modify[i][j] 为s[i] ~ s[j]最小修改次数
        dfs(i, j) = dfs(i - 1, L - 1) + modify[i][j]
        终点 i = 0 return modify[0][j]
        入口dfs(k - 1, n - 1)
        """
        n = len(s)
        # 预处理出每个子串 成为半回文串的最小修改次数
        modify = [[0] * n for _ in range(n)]
        for left in range(n - 1):
            for right in range(left + 1, n):
                modify[left][right] = get_modify(s[left:right + 1])

        @cache
        def dfs(i, j):
            # i为0 的时候 即 不需要再划分了
            if i == 0:
                return modify[0][j]
            ret = inf
            # 枚举左端点 左端点从i* 2开始 最大为j - 1 右端点为j
            for L in range(i * 2, j):
                ret = min(ret, dfs(i - 1, L - 1) + modify[L][j])
            return ret
        return dfs(k - 1, n - 1)

100097. 合法分组的最少组数 - 力扣（LeetCode）

首先思路就错了。。其实是从大（最少出现次数）到小（1） 枚举最小分割的k 一旦满足要求就可以直接返回 而不是先从最小出现次数 计算不对之后 再去拆分每一个数。。因为只要不是k 和k + 1 就不行 k - 1 会与k + 1 冲突

为什么q < r 的时候不行呢 因为 k = 10的时候 比如30分成3个10 可以31 分成10 10 11 ；32 分成10 11 11 ；33分成11 11 11 ；但是到了34 r = 4 q = 3 此时不能把r均摊到q上 所以说这种分法是不行的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minGroupsForValidAssignment(self, nums: List[int]) -> int:
        nums = Counter(nums)
        m = min(nums.values())
        for i in range(m, 0, -1):
            ans = 0
            for v in nums.values():
                q, r = divmod(v, i)
                if q < r:
                    ans = 0
                    break
                else:
                    ans += math.ceil(v / (i + 1))
            else: # for else 结构  没有break运行 （也可以 if ans:）
                return ans

100114. 元素和最小的山形三元组 II - 力扣（LeetCode）

求出前缀的最小值 后缀的最小值

然后遍历每个i 如果是山状的 取i i-1的最小值 i + 1 的最小值即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        left_min = [0] * n
        left_min[0] = nums[0]
        right_min = [0] * n
        right_min[-1] = nums[-1]
        
        
        for i in range(1, n):
            left_min[i] = min(left_min[i - 1], nums[i])
        for i in range(n - 2, -1, -1):
            right_min[i] = min(right_min[i + 1], nums[i])
        
        ret = inf
        for i in range(1, n - 1):
            if nums[i] > left_min[i - 1] and nums[i] > right_min[i + 1]:
                ret = min(ret, nums[i] + left_min[i - 1] + right_min[i + 1])
        return -1 if ret == inf else ret

容器multiset

Problem - D - Codeforces

用multiset可以自动排序 并且存储多个重复的数

注意erase的时候 要用s.erase(s.lower_bound(x))不然会删掉所有的x

本题只需要有一个不相交就行 那也就是 最大的left 和最小的right比较

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

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/

multiset<int> s1, s2;

void solve()
{
    int l, r;
    char c;
    cin >> c >> l >> r;
    if (c == '+')
    {
        s1.insert(l);
        s2.insert(r);
    }
    else
    {
        s1.erase(s1.lower_bound(l));
        s2.erase(s2.lower_bound(r));
    }
    if (s1.empty())
    {
        cout << "NO" << endl;
        return;
    }
    auto s = s1.end(), e = s2.begin();
    s--;
    if (*s > *e)
    {
        cout << "YES" << endl;
    }
    else
        cout << "NO" << endl;
}
int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int T;
    cin >> T;
    while (T--)
        solve();

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

Problem - C - Codeforces

模拟 每次循环比较两个位置的值 然后把小的数变成大的数（题目要求只能增大）计算出差值就是一共要走的步数 并且直接将两个位置的值都修改为较大的值（表示变换了

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

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/

void solve()
{
    int n;
    cin >> n;
    vector<vector<char>> v(n + 5, vector<char>(n + 5));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> v[i][j];
        }
    }
    ll ans = 0;
    while (true)
    {
        ll ii = 1, jj = 1;
        ll tot = 0;
        for (int col = n; col >= 1; col--)
        {
            for (int row = 1; row <= n; row++)
            {
                tot += abs(v[ii][jj] - v[row][col]);
                ans += abs(v[ii][jj] - v[row][col]);
                v[row][col] = max(v[ii][jj], v[row][col]);
                v[ii][jj] = max(v[ii][jj], v[row][col]);
                jj++;
            }
            ii++;
            jj = 1;
        }
        if (!tot)
            break;
    }
    cout << ans << endl;
}
int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int T;
    cin >> T;
    while (T--)
        solve();

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

Problem - D - Codeforces

n个数 能不能最后变成相同的n个数 注意到 x / x 最终的乘积是不变的 所以可以算出每个数的因子 这些因子乘起来 就是总乘积 然后除了1以外 看看这些因子是否能被n整除 比如 3个5 6个8 肯定是能被分成3个一样的数的 5 * (2 8) 用哈希表记录每个因数的个数

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

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/

void solve()
{
    map<int, int> mp;
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        for (int j = 2; j<=x/j; j++)
        {
            while (x % j == 0)
            {
                mp[j]++;
                x /= j;
            }
        }
        mp[x]++;
    }

    for (auto x : mp)
    {
        if (x.first == 1)
            continue;
        if (x.second % n != 0)
        {
            puts("NO");
            return;
        }
    }
    puts("YES");
}
int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int T;
    cin >> T;
    while (T--)
        solve();

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

Problem - B - Codeforces

CF–记录傻逼瞬间

简单的暴力 maxnum范围开小了 从头WA到尾。。

前缀和 的范围 是远超过1e9的单个数字的范围的。。

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

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/
const int N = 2e5;

void solve()
{
    int n;
    cin >> n;
    vector<ll> nums(n + 5);
    vector<ll> qzh(n + 5);
    ll minn = 1e9 + 10, maxn = -1;
    for (int i = 1; i <= n; i++)
    {
        cin >> nums[i];
        maxn = max(maxn, nums[i]);
        minn = min(minn, nums[i]);
        qzh[i] = qzh[i - 1] + nums[i];
    }
    ll ret = maxn - minn;
    if (ret == 0)
    {
        cout << 0 << endl;
        return;
    }
    for (int i = 1; i < n; i++)
    {
        maxn = 0, minn = 1e18;
        if (n % i != 0)
            continue;
        for (int j = i; j <= n; j += i)
        {
            maxn = max(maxn, qzh[j] - qzh[j - i]);
            minn = min(minn, qzh[j] - qzh[j - i]);
        }
        ret = max(ret, maxn - minn);
    }
    cout << ret << endl;
}
int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int T;
    cin >> T;
    while (T--)
        solve();

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

Problem - C - Codeforces

C也是懒得喷。。我艹 vector开在局部 还每次都开2e5赋值0的是什么傻逼 T了一次

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

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/

const int N = 3e5;
void solve()
{
    int nums[N] = {0};
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    ll ret = nums[0];
    ll l = 0;
    ll sum = 0;
    if (nums[l] > 0)
    {
        ret = nums[l];
        sum = nums[l];
    }
    l++;
    while (l < n)
    {
        if (abs(nums[l] % 2) != abs(nums[l - 1] % 2))
        {
            sum += nums[l];
            while (sum < 0 && l < n)
            {
                l++;
                sum = nums[l];
                ret = max(ret, sum);
            }
            ret = max(ret, sum);
        }
        else
        {
            if (nums[l] > 0)
            {
                sum = nums[l];
                ret = max(sum, ret);
            }
            else
                sum = 0;
        }
        l++;
    }
    cout << ret << endl;
}
int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int T;
    cin >> T;
    while (T--)
        solve();

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

100138. 最大化网格图中正方形空洞的面积 - 力扣（LeetCode）

emm 感觉这两场状态都很差，题目没看明白 浪费了很多时间。

其实求最大的正方形 不是去整个里面删除 而是在可以删除的线（vBars和hBars）里面找 最长的连续的是多少 画个图 就能看出来 (最后要加一，，也是画图)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) -> int:
        def f(a):
            l = len(a)
            cnt = 1
            ret = 0
            for i in range(1, l):
                if a[i] == a[i - 1] + 1:
                    cnt += 1
                else:
                    ret = max(ret, cnt)
                    cnt = 1
            ret = max(ret, cnt)
            return ret

        hBars.sort()
        vBars.sort()
        x = min(f(hBars), f(vBars)) + 1
        return x * x

100139. 循环移位后的矩阵相似检查 - 力扣（LeetCode）

看清题目！其实就是直接比较两列是否相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool:
        row = len(mat)
        col = len(mat[0])
        if k % col == 0:
            return True
        k %= col
        
        now = [[0] * col for _ in range(row)]
        print(mat)
        for i in range(col):
            for j in range(row):
                now[j][i] = mat[j][(i + k) % col]
                
        print(now, mat)
        if now == mat:
            return True
        return False

100142. 交换得到字典序最小的数组 - 力扣（LeetCode）

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
class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        """
        3 1 2 limit = 1 那么1 3 的差大于limit 是不是就不能换了呢？
        不是 可以借助2来换 2 1 3 -> 1 2 3 
        3 5 1 7 limit = 2 可以换到1 3 5 7 
        这说明limit限制内的所有数 都可以被换成从小到大的数
        这被称为一个连通块（类似图论的概念）
        再看 2 4 22 20 3 21 1 
        这组数有两个连通块 1 2 3 4 可以按顺序 20 21 22 可以按顺序 但是 他们只能在各自的块内交换 即 1 2 20 21 3 22 4
        用 排序+分组循环
        """
        # 注意排序不能直接排  会丢失下标
        n = len(nums)
        a = sorted(zip(nums, range(n)))
        # 现在a 是带下标的 排序的nums值 如(6,1)(0,2)(4,3)(1,4)(3,20)(5,21)(2,22) 需要把他们分别放到各自的空里
        # 分组循环 每次排一个连通块
        i = 0
        ans = [0] * n
        while i < n:
            st = i
            i += 1
            while i < n and a[i][0] <= a[i - 1][0] + limit:
                i += 1
            # 出来的这个i 就是下一组的了
            # 现在要把前面这几个 按下标排序 排完之后把a分别放到这些下标里（因为a是数从小到大 刚好放到下标的从小到大）
            sub = a[st:i]
            sub_idx = sorted(i for _, i in sub)
            # 排好了 放回去
            for j, (x, _) in zip(sub_idx, sub):
                ans[j] = x
            
        return ans
algorithm
#Ans
赛题题解
https://brtulien.github.io/2023/09/24/赛题题解/
作者
Brtulien
发布于
2023年9月24日
更新于
2024年7月1日
许可协议