课堂计划

# P5194 [USACO05DEC] Scales S

这道题是一道搜索题，一种思路是直接对每一个数做出选与不选的判断，时间复杂度 O(2n)O(2n) 。在这种时间复杂度下，只能通过 n≤30n≤30 的数据。

如何进行优化呢？

改变搜索顺序。这一道题的输入数据是一个不下降序列，如果我们把小的数放在前面，而 CC 又比较大的话，前面的小数就会有很多的空间进行选择，极限数据下甚至可以卡死代码。为了避免这种情况，我在读入的时候从 anan 开始倒着读，这样 a 数组中就是一个不上升子序列，前面的大数很容易就因为 CC 的限制失去很多选择，节省了很多的时间。其中 a 数组是我存放数的数组。
模拟可行性剪枝，我们不妨这么想：如果说当前所选的数的总和加上后面的数的总和，即后缀和都没有超过 CC 的话，那么当前的和就是在这种选择下可以达到的最大值。既然我们已经知道了最大值，并且题目所求的就是最大值，此时我们可以直接去更新答案，然后退出这一层搜索。面对数很多的时候，这个剪枝会发挥出极大的威力。

1
from collections import deque
2
n, c = map(int, input().split())
3
a = []
4
for _ in range(n):
5
    a.append(int(input()))
6
a.sort(reverse=True)
7

8
suf = [0] * (n + 1)
9
for i in range(n - 1, -1, -1):
10
    suf[i] = suf[i + 1] + a[i]
11
ans = 0
12
def dfs(pos, t):
13
    global ans
14
    if t > c:
15
        return
8 collapsed lines
16
    if suf[pos] + t <= c:
17
        ans = max(suf[pos] + t, ans)
18
        return
19
    ans = max(ans, t)
20
    for i in range(pos, n):
21
        dfs(i + 1, t + a[i])
22
dfs(0, 0)
23
print(ans)

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

1
平面上有(0,0)到(n,m)的(n+1)*(m+1)个点。问有多少点对所连的线段不过其他点，且长度在[l,h]范围内

枚举 dx, dy, dx 与 dy 互质即可。

1
def gcd(a: int, b: int):
2
    return b if a % b == 0 else gcd(b, a % b)
3

4
n, m, l, r = map(int, input().split())
5
answer = 0
6
for i in range(1, n + 1):
7
    for j in range(1, m + 1):
8
        if gcd(i, j) == 1 and l * l <= i * i + j * j <= r * r:
9
            answer += 2 * (n - i + 1) * (m - j + 1)
10
if l == 1:
11
    answer += n * (m + 1) + (n + 1) * m
12
print(answer)

1
做题技巧3:想到了算法或者找到了规律，但是实现之后还是超时，有三种方法加快速度：
2
1.预处理
3
（先得到一些简单的结论，再利用结论去解决更复杂的情况）
4
2.二分查找
5
（例如，在2组数字中各找一个数字使得差值最小，遍历第一组数，利用二分去第2组找到离它最近的数）
6
3.数学公式或者数学思想
7
（例如，可以利用求和公式代替1-n的for循环，或者抽屉原理，排列组合，容斥原理等等）

USACO 2022 US Open Contest, Silver Problem 2. Subset Equality https://usaco.org/index.php?page=viewproblem2&cpid=1231

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
string s1, s2;
5
bool can[30][30];
6
//char t1[100010], t2[100010];
7
string t1,t2;
8

9
bool check(string s) {
10
    int len = s.size();
11
    for (int i = 0; i < len; i++) {
12
        for (int j = i; j < len; j++) {
13
            if(!can[s[i]-'a'][s[j]-'a']) {
14
                return false;
15
            }
45 collapsed lines
16
        }
17
    }
18
    return true;
19
}
20

21
/*
22
���Է���һ�����ʣ��������ab��ac��bc��������ôabcҲ�ǿ��е�,
23
����Ԥ��������ѯ�ʳ�Ϊ1����2�Ϳ�����
24
*/
25
int main() {
26
//    ios::sync_with_stdio(false);
27
//    cin.tie(0), cout.tie(0);
28
    cin >> s1 >> s2;
29
    int len1 = s1.size(), len2 = s2.size();
30
    for (int i = 0; i < 18; i++)
31
        for (int j = i; j < 18; j++) {
32
             t1="";
33
             t2="";
34
            for (int k = 0; k < len1; k++)
35
                if ((s1[k] == 'a' + i) || (s1[k] == 'a' + j)) {
36
                    t1+=s1[k];
37
                }
38

39
            for (int k = 0; k < len2; k++)
40
                if ((s2[k] == 'a' + i) || (s2[k] == 'a' + j)) {
41
                    t2+=s2[k];
42
                }
43

44

45
            can[i][j] = t1==t2;
46
        }
47

48
    int q;
49
    cin >> q;
50
    string s;
51
    for (int i = 0; i < q; i++) {
52
        cin >> s;
53
        if (check(s))
54
      cout<<'Y';
55
        else
56
      cout<<'N';
57
    }
58

59
    return 0;
60
}

USACO 2021 December Contest, Silver Problem 1. Closest Cow Wins https://usaco.org/index.php?page=viewproblem2&cpid=1158

# P5194 [USACO05DEC] Scales S

P2997 [USACO10NOV] Banner S