Posts with tag 241116

课堂计划

2024-11-16
241116julyfunnoteswilliam工作

# P5194 [USACO05DEC] Scales S这道题是一道搜索题,一种思路是直接对每一个数做出选与不选的判断,时间复杂度 O(2n)O(2n) 。在这种时间复杂度下,只能通过 n≤30n≤30 的数据。如何进行优化呢?改变搜索顺序。这一道题的输入数据是一个不下降序列,如果我们把小的数放在前面,而 CC 又比较大的话,前面的小数就会有很多的空间进行选择,极限数据下甚至可以卡死代码。为了避免这种情况,我在读入的时候从 anan​ 开始倒着读,这样 a 数组中就是一个不上升子序列,前面的大数很容易就因为 CC 的限制失去很多选择,节省了很多的时间。其中 a 数组是我存放数的数组。模拟可行性剪枝,我们不妨这么想:如果说当前所选的数的总和加上后面的数的总和,即后缀和都没有超过 CC 的话,那么当前的和就是在这种选择下可以达到的最大值。既然我们已经知道了最大值,并且题目所求的就是最大值,此时我们可以直接去更新答案, 然后退出这一层搜索。面对数很多的时候,这个剪枝会发挥出极大的威力。from collections import deque n, c = map(int, input().split()) a = [] for _ in range(n): a.append(int(input())) a.sort(reverse=True) suf = [0] * (n + 1) for i in range(n - 1, -1, -1): suf[i] = suf[i + 1] + a[i] ans = 0 def dfs(pos, t): global ans if t > c: return if suf[pos] + t <= c: ans = max(suf[pos] + t, ans) return ans = max(ans, t) for i in range(pos, n): dfs(i + 1, t + a[i]) dfs(0, 0) print(ans) P2997 [USACO10NOV] Banner Shttps://www.luogu.com.cn/problem/P2997平面上有(0,0)到(n,m)的(n+1)*(m+1)个点。问有多少点对所连的线段不过其他点,且长度在[l,h]范围内枚举 dx, dy, dx 与 dy 互质即可。def gcd(a: int, b: int): return b if a % b == 0 else gcd(b, a % b) n, m, l, r = map(int, input().split()) answer = 0 for i in range(1, n + 1): for j in range(1, m + 1): if gcd(i, j) == 1 and l * l <= i * i + j * j <= r * r: answer += 2 * (n - i + 1) * (m - j + 1) if l == 1: answer += n * (m + 1) + (n + 1) * m print(answer)做题技巧3:想到了算法或者找到了规律,但是实现之后还是超时,有三种方法加快速度: 1.预处理 (先得到一些简单的结论,再利用结论去解决更复杂的情况) 2.二分查找 (例如,在2组数字中各找一个数字使得差值最小,遍历第一组数,利用二分去第2组找到离它最近的数) 3.数学公式或者数学思想 (例如,可以利用求和公式代替1-n的for循环,或者抽屉原理,排列组合,容斥原理等等)USACO 2022 US Open Contest, Silver Problem 2. Subset Equality https://usaco.org/index.php?page=viewproblem2&cpid=1231#include <bits/stdc++.h> using namespace std; string s1, s2; bool can[30][30]; //char t1[100010], t2[100010]; string t1,t2; bool check(string s) { int len = s.size(); for (int i = 0; i < len; i++) { for (int j = i; j < len; j++) { if(!can[s[i]-'a'][s[j]-'a']) { return false; } } } return true; } /* ���Է���һ�����ʣ��������ab��ac��bc��������ôabcҲ�ǿ��е�, ����Ԥ��������ѯ�ʳ�Ϊ1����2�Ϳ����� */ int main() { // ios::sync_with_stdio(false); // cin.tie(0), cout.tie(0); cin >> s1 >> s2; int len1 = s1.size(), len2 = s2.size(); for (int i = 0; i < 18; i++) for (int j = i; j < 18; j++) { t1=""; t2=""; for (int k = 0; k < len1; k++) if ((s1[k] == 'a' + i) || (s1[k] == 'a' + j)) { t1+=s1[k]; } for (int k = 0; k < len2; k++) if ((s2[k] == 'a' + i) || (s2[k] == 'a' + j)) { t2+=s2[k]; } can[i][j] = t1==t2; } int q; cin >> q; string s; for (int i = 0; i < q; i++) { cin >> s; if (check(s)) cout<<'Y'; else cout<<'N'; } return 0; } USACO 2021 December Contest, Silver Problem 1. Closest Cow Wins https://usaco.org/index.php?page=viewproblem2&cpid=115

No more posts to load.