Posts with tag 工作

数组

2025-05-27
julyfunkedayanotes工作

C++数组基础知识用法表格| 操作 | 代码示例 | 说明 | | --------------- | -------------------------------------- | ------------------------------------ | | 声明数组 | int a[5]; | 创建一个长度为5的整型数组,未初始化。 | | 初始化数组 | int b[3] = {1, 2, 3}; | 声明时直接赋值,长度可省略:int b[] = {1, 2, 3}; | | 访问元素 | cout << b[0]; | 输出下标为0的元素(第一个元素,值为1)。 | | 修改元素 | b[1] = 5; | 将下标为1的元素改为5。 | | 遍历数组(for循环) | for(int i=0; i<3; i++) cout << b[i]; | 输出所有元素,注意下标从0开始到长度-1。 |应用题及数组写法题目1:输入5个数,输出它们的和#include <iostream> using namespace std; int main() { int a[5], sum = 0; // 输入 for(int i=0; i<5; i++) { cin >> a[i]; sum += a[i]; // 累加 } // 输出 cout << "Sum: " << sum; return 0; }题目2:输出数组中的最大值#include <iostream> using namespace std; int main() { int a[5] = {3, 9, 2, 7, 5}; int max = a[0]; // 假设第一个是最大值 for(int i=1; i<5; i++) { if(a[i] > max) max = a[i]; // 更新最大值 } cout << "Max: " << max; return 0; }题目3:逆序输出数组#include <iostream> using namespace std; int main() { int a[] = {1, 2, 3, 4, 5}; for(int i=4; i>=0; i--) { // 下标从大到小 cout << a[i] << " "; } return 0; }题目4:统计数组中某个数的出现次数#include <iostream> using namespace std; int main() { int a[6] = {2, 3, 2, 5, 2, 1}; int target = 2, count = 0; for(int i=0; i<6; i++) { if(a[i] == target) count++; } cout << "Count of " << target << ": " << count; return 0; }题目5:数组元素翻倍(修改原数组)#include <iostream> using namespace std; int main() { int a[4] = {1, 2, 3, 4}; for(int i=0; i<4; i++) { a[i] *= 2; // 每个元素乘2 } // 输出结果 for(int i=0; i<4; i++) { cout << a[i] << " "; } return 0; }关键提示下标从0开始:a[0]是第一个元素,a[n-1]是最后一个。越界检查:避免访问a[-1]或a[n],可能导致程序崩溃。初始化习惯:局部数组未初始化时值是随机的,建议显式赋值(如int a[5] = {0};)。通过这些例题,学生可以掌握数组的声明、遍历、修改和基本应用。后续可逐步过渡到二维数组或字符串(字符数组)

题解

2025-02-22
feb25julyfunnotesusaco工作

题意概述给定偶数 n 和一个 n * n 的 01 网格,将其平分为上下左右四个象限,每次操作可以翻转一个网格的元素。求最少需要多少次操作使得四个象限镜像对称(每两个相邻的象限中的 01 网格关于它们相邻的那条轴对称). 此外还会有 m 次询问,每次询问翻转一个坐标,求翻转后的最少操作次数。解题思路我们找到成对的镜像对称格子,每对是 4 个格子(例如整个网格左上角,左下角,右上角,右下角就是一对),我们的目标是将每对格子变为全 0 或全 1。可以统计每对格子当前有多少个 0 和 1,然后取最小值即可。对于询问,我们可以直接更新对应的网格对,然后重新计算即可。复杂度 O(n^2)。题意概述给定 N 个数(N 不超过 200000,每个数范围 0 ~ N),每次操作可以将其中一个数修改为任意非负整数。对 0 ~ N 中的每一个 i,求最少操作几次可以使整个数列的 mex 为 i。一个数列的 mex 指的是最小的未出现过的非负整数.解题思路如果数列 mex 为 i,则 0 ~ i - 1 的每一个数都出现过,且 i 没有出现过. 对于每个 i,我们统计 0 ~ i - 1 中有几个数没有出现过(表示有几个空位需要填),再统计 i 出现了几次(这几个 i 都必须修改为其他数)。由于可以拿 i 来填充前面空位,所以两者的较大值就是答案.题意概述一种编程语言有 REP 和 PRINT 两种语句,其中 PRINT X 可以输出 X,REP 可以重复执行一系列语句,也可以嵌套,类似于 C++ 和 Python 的 for 循环。给定 N <= 100, K <= 3,以及 N 个 1 ~ K 的整数,求是否可以使用 K 个以内的 PRINT X 语句 (1 <= X <= K) 和任意多个 REP 语句组成程序来输出这 N 个数。共有 T 组询问 (T <= 100)。解题思路如果 K = 1,必可以输出。否则我们可以先判断整个序列是否有循环节,找到其中最短的循环节 S,则 S 中不含任何循环节。接下来如果循环节内部有 3 种数字,则 1,2,3 中必然有一个数只存在于 S 前面连续的一段或者后缀连续的一段。我们将连续的一段排除,递归判断剩下的部分(剩下部分只有两个数)。如果循环节内部有 2 种数字,则需要分类讨论。如果 K = 2,则 S 必然是 111222... 或者 222111.. 这种形式。如果 K = 3,则可能有 1212222 这种形式(即包含两个循环节 12 和额外输出的 222,这也满足 3 个 PRINT)。我们可以暴力删除连续 1 或 2 的前缀或后缀,再递归判断剩下部分即可

250112

2025-02-09
julyfunnoteswilliam工作

https://usaco.org/index.php?page=viewproblem2&cpid=1303思路: 题目中有提到,一头牛总是有可能在所有牧场之间穿梭,也就是说一头牛从任意一个放牧地点出发,都能在所有牧场之间穿梭。 那么考虑将每次吃草事件按 t 从小到大排序。一头牛的不在场证明成立,仅当它无法在所有牧场与自己的不在场证明地点之间穿梭。假设某头牛在第 $t_i$ 时刻有不在场证明,离 $t_i$ 最近且早于 $t_i$ 的吃草事件的时刻为 $k_1$,离 $t_i$ 最近且晚于 $t_i$ 的吃草事件的时刻为 $k_2$。分析一下会发现,只要它不可能在 $(t_i-k_1)$ 的时间内从上一次吃草事件发生地点赶到不在场证明地点,或不可能在 $(k_2-t_i)$ 的时间内从不在场证明地点赶到下一次吃草事件发生地点,它的不在场证明就成立。 那么问题就变成了,找到比不在场证明时间早的最晚发生的吃草事件。因为吃草事件已经按发生顺序排序,所以这次吃草事件的下次吃草事件就是比不在场证明时间晚的最早发生的吃草事件。该如何找到这次吃草事件呢?可以很容易地想到二分。那么问题也就迎刃而解了。参考 C++ 版本#include <bits/stdc++.h> using namespace std; typedef long long ll; int g,n,ans; struct point { ll x,y,t; friend bool operator <(const point tmp1,const point tmp2) { return tmp1.t<tmp2.t; } }; point p[100005]; ll tim[100005]; bool check(int i,ll t,ll x,ll y) { return (x-p[i].x)*(x-p[i].x)+(y-p[i].y)*(y-p[i].y)<=(t-p[i].t)*(t-p[i].t); } int main() { scanf("%d%d",&n,&g); for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].t); sort(p+1,p+1+n); for(int i=1;i<=n;i++) tim[i]=p[i].t; for(int i=1;i<=g;i++) { ll x,y,t; scanf("%lld%lld%lld",&x,&y,&t); int pos=lower_bound(tim+1,tim+1+n,t)-tim; if(pos==1) ans+=check(pos,t,x,y)?1:0; else if(pos-1==n) ans+=check(pos-1,t,x,y)?1:0; else ans+=(check(pos,t,x,y)&&check(pos-1,t,x,y))?1:0; } printf("%d\n",g-ans); return 0; }https://usaco.org/index.php?page=viewproblem2&cpid=1087由于每次询问都会不染其中的一段区间,可以考虑使用前缀、后缀记录答案的方法来预处理数据。 预处理方法: 使用数组 ans(i) 记录第 i 位需要多少次染色。 使用数组 v[i] 记录之前是否有第 i 个字母出现。 假设当前字符串为 "ABAB"。 对于每个位置 i 进行处理: 当 i = 1 时,v('A') == 0,ans(1)++,v('A') = 1 (赋值)。 当 i = 2 时,v('B') == 0,ans(2)++,v('B') = 1。 当 i = 3 时,v('A') == 1,ans(3) 不变(可以从上一个 'A' 继续延伸)。 当 i = 4 时,发现一个问题,上一个 'B' 不能延续下来,因为中间有一个 'A'。https://usaco.org/index.php?page=viewproblem2&cpid=1351首先没有出现过的编号是一定可以分配相同的,这一部分要先记上。 之后问题转化为一个环可以移动若干位,求和另一个环对应位置相同的最多个数。 直接枚举环移动的位数暴力判断是 O (n²) 的,考虑优化这个过程。 编号是一个排列,所以环内元素两两不同,则第一个环内一个数至多对应第二个环中的一个数。求出第一个环的每个数要向右平移多少位才能和第二个环对应相同,取最大值即可。 要正反做一遍,因为可以翻转方向

枚举每个二维点

2025-01-04
julyfunnoteswilliam工作

# [USACO19JAN] Icy Perimeter S冰淇淋的面积用dfs很好求只要算出每个联通块中'#'的个数即可难点在于求联通快的周长观察一下样例 发现周长就是每个'#'周围'.'或超过边界的方块个数解决这一问题后这道题几乎就是一道dfs裸题了Part 1 求出最大连通块面积读入 n dir = [(0, 1), (0, -1), (1, 0), (-1, 0)] a 数组从 1, 1 开始,存储 (i, j) 是 '#' 还是 '.' 二维数组 vis = (n + 10) * (n + 10) 的数组表示 i, j 是否访问过 q = deque() # 枚举每个二维点 for i in range(1, n + 1): for j in range(1, n + 1): if i, j 没有访问过, # [todo] 还需要求出最大联通块的面积 area = 0 q.append((i, j)) while len(q): u = q.popleft() # 例如 u = (5, 7) area += 1 for d in dir: # 怎么拿出 d 里面的第一个元素和第二个元素? v = (u[0] + d[0], u[1] + d[1]) if 1 <= v[0] <= n and 1 <= v[1] <= n and a[v[0]][v[1]] == '#' and not vis[v[0]][v[1]]: q.append(v)读入 n dir = [(0, 1), (0, -1), (1, 0), (-1, 0)] a 数组从 1, 1 开始,存储 (i, j) 是 '#' 还是 '.' a = [] for i in range(n): a.append(' ' + input()) vis = [[0] * (n + 1) for _ in range(n + 1)] q = deque() # 枚举每个二维点 for i in range(1, n + 1): for j in range(1, n + 1): if not vis[i][j]: # [todo] 还需要求出最大联通块的面积 area = 0 q.append((i, j)) while len(q): u = q.popleft() # 例如 u = (5, 7) area += 1 for d in dir: # 怎么拿出 d 里面的第一个元素和第二个元素? v = (u[0] + d[0], u[1] + d[1]) if 1 <= v[0] <= n and 1 <= v[1] <= n and a[v[0]][v[1]] == '#' and not vis[v[0]][v[1]]: q.append(v) n = 读入整数 a = [] for _ in range(n): a.append(input()) vis = 全是 False 的 n * n 的二维数组 dir = [(0, 1), (1, 0), (-1, 0), (0, -1)] def dfs(x, y): global area area += 1 vis[x][y] = True # 走过了 for dx, dy in dir: tx, ty = x + dx, y + dy # 要到达的点 # tx, ty 必须没走过 if 0 <= tx <= n - 1 and 0 <= ty <= n - 1 and a[tx][ty] == '#' and not vis[tx][ty]: # 合法 dfs(tx, ty) max_area = 0 for i in range(n): for j in range(n): if not vis[i][j]: area = 0 dfs(i, j) print(area)Problem 3. Problem 1. Marathon这道题目是一道动规的题目。令f[i][j]代表到了第i个检查点,跳过了j个的最短距离。f[i][j]=min(f[i-l-1][j-l]+dis(i,i-l-1))复杂度为 O(n^3)课堂总结dfs 完

课堂总结

2024-12-28
241224julyfunnoteswilliam工作

博弈论:博弈双方都试图最大化自己的分数,先手在进行决策时,要考虑后手的所有可能操作,后手将会最小化先手的分数,而先手 要从最小化的各种方案中选择最大的。 部分博弈论可转换为贪心问题,在已知先手 / 后手策略必定满足某些条件的情况下,比如第一题先手必然选择连续的一段,则后手最小化这连续的一段即可。第三题思路: 我们放上所有强制放的传送带 然后判断最后一天有哪些活格子 首先让整个网格周围的一圈设为活格子 然后从这些活格子开始进行 bfs x -> y 其中 y 是活格子 必须满足 x 上的传送带是 R 所以想从 y 搜到 x,必须要 x 上的传送带是 y -> x 的反方向 每天拿走一个传送带 判断这个传送带是死格子且四周有活格子 如果成立,我们就从这个传送带反向 bfs, 把 bfs 到的格子全部设置为活格子 输出活格子数量

Cow Frisbee S

2024-12-21
241221julyfunnoteswilliam工作

Cow Frisbee S维护一个单调栈,每进入一个数 ai​,就向前扫描直到遇见一个 s_top​>ai​,由于有 ai​ 挡着,所以之后的我们全部都看不见,此时最终答案加上 (i−stop+1)。from collections import deque MAXN = int(1e6) n = 0 ans = 0 a = [0] * (MAXN + 1) s = deque() n = int(input()) for i in range(1, n + 1): a[i] = int(input()) for i in range(1, n + 1): while s and a[s[-1]] < a[i]: ans += i - s[-1] + 1 s.pop() if s: ans += i - s[-1] + 1 s.append(i) 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)# [USACO19JAN] Icy Perimeter S冰淇淋的面积用dfs很好求只要算出每个联通块中'#'的个数即可难点在于求联通快的周长观察一下样例 发现周长就是每个'#'周围'.'或超过边界的方块个数解决这一问题后这道题几乎就是一道dfs裸题了2, 3 is ok(0 , 0) (6, 9) 判断所有的 dx, dy 是否满足互质,如果是互质就可以选择W * H 插满杆子 dx = 2, dy = 3def gcd(a, b): if b == 0: return a return gcd(b, a % b) gcd(a=60, b=24) return 12 -> gcd(24, 12) return 12 -> gcd(12, 0) return 12(2, 3)for dx in range(0, W): for dy in range(0, H): 判断 dx, dy 是否互质 即 gcd(dx, dy) == 1 如果是互质就 continue w = W - dx + 1 h = H - dy + 1 ans += w *

P6002 [USACO20JAN] Berry Picking S

2024-12-14
241214julyfunnoteswilliam工作

P6002 [USACO20JAN] Berry Picking S所以有前 k / 2号元素都是一个相同值枚举这个值m,有三种情况最多能取出k个m,则前所有元素均为 m最多能取小于 k / 2 个 m,无解否则尽可能取多个 m,剩下部分取最大的即可._, k = map(int, input().split()) a = list(map(int, input().split())) ans = 0 for m in range(1, 1001): num = 0 res = 0 rest = [] for x in a: num += x // m rest.append(x % m) if num >= k: res = m * k // 2 elif num >= k // 2: res = (num - k // 2) * m + sum(sorted(rest, reverse=True)[:(k - num)]) ans = max(ans, res) print(ans)Cow Frisbee S维护一个单调栈,每进入一个数 ai​,就向前扫描直到遇见一个 s_top​>ai​,由于有 ai​ 挡着,所以之后的我们全部都看不见,此时最终答案加上 (i−stop+1)。from collections import deque MAXN = int(1e6) n = 0 ans = 0 a = [0] * (MAXN + 1) s = deque() n = int(input()) for i in range(1, n + 1): a[i] = int(input()) for i in range(1, n + 1): while s and a[s[-1]] < a[i]: ans += i - s[-1] + 1 s.pop() if s: ans += i - s[-1] + 1 s.append(i) print(ans)# [USACO19JAN] Icy Perimeter S冰淇淋的面积用dfs很好求只要算出每个联通块中'#'的个数即可难点在于求联通快的周长观察一下样例 发现周长就是每个'#'周围'.'或超过边界的方块个数解决这一问题后这道题几乎就是一道dfs裸题

P3142 [USACO16OPEN] Field Reduction S

2024-12-04
241201julyfunnoteswilliam工作

P7148 [USACO20DEC] Cowntagion S1号点有一头牛节点的牛的来源只能来自于父亲节点现在如果要给2号牛,1号节点给一只牛就是最优选择 为什么呢?因为翻倍和给一头牛代价一样,所以给2头牛和给1头牛再翻倍是一样的以此类推,多头牛时,翻倍是更优的一种选择,并且只需给每个子节点1头牛读一个 n 统计每个点儿子数量 son 每次读一条边 x, y son[x] += 1 son[y] += 1 for i in range(2, n + 1): son[i] -= 1 ans = 0 for i in range(1, n + 1): 假设到达这个点的时候它的感染数量一定是 1 (x = 1) while x 还没到 (i 的儿子数量 + 1): x *= 2 ans += 1 ans += i 的儿子数量 print(ans)sum_counts = [0] * 100001 # Initialize an array to keep track of the number of edges total = 0 n = int(input()) # Read the number of nodes for _ in range(1, n): x, y = map(int, input().split()) # Read edges sum_counts[x] += 1 # Record the number of edges sum_counts[y] += 1 for i in range(1, n + 1): if i != 1: # Exclude the root node sum_counts[i] -= 1 # Subtract 1 from the edge count for the subtree x = 1 while x <= sum_counts[i]: # While the required count is not reached total += 1 x *= 2 # Double the growth total += sum_counts[i] # Allocate the remaining edges print(total)P3142 [USACO16OPEN] Field Reduction S想要求出最终围栏围起来的面积,只需要计算 (maxx−minx)(maxy−miny)(maxx−minx)(maxy−miny) 的值即可。首先,我们先用 Xi​ 排序,求得最大的 3 个点和最小的 3 个点。同样的方法给 Yi​ 排序,求得最大的 3 个点和最小的 3 个点。我们要暴力的答案中必定包含这 12 个点(当然有重复的点要去重)。接下来就是暴力的核心,用 dfs 每一次选择 3 个点,然后最后计算它的面积,取最小值即可。class Node: def __init__(self, x, y, down): self.x = x self.y = y self.down = down def check(r1, r2, r3): global ans min_x = float('inf') max_x = float('-inf') min_y = float('inf') max_y = float('-inf') for i in range(1, n + 1): if b[i].down == r1 or b[i].down == r2 or b[i].down == r3: continue min_x = min(min_x, b[i].x) max_x = max(max_x, b[i].x) min_y = min(min_y, b[i].y) max_y = max(max_y, b[i].y) ans = min(ans, (max_x - min_x) * (max_y - min_y)) # Update the answer with the minimum value n = int(sys.stdin.readline().strip()) b = [None] * (50005) ans = 1e18 g = [0] * (50005) cnt = 0 for i in range(1, n + 1): x, y = map(int, sys.stdin.readline().strip().split()) b[i] = Node(x, y, i) b[1:n + 1] = sorted(b[1:n + 1], key=lambda node: node.x) for i in range(1, 4): cnt += 1 g[cnt] = b[i].down for i in range(n, n - 3, -1): cnt += 1 g[cnt] = b[i].down b[1:n + 1] = sorted(b[1:n + 1], key=lambda node: node.y) for i in range(1, 4): cnt += 1 g[cnt] = b[i].down for i in range(n, n - 3, -1): cnt += 1 g[cnt] = b[i].down g = sorted(g[1:cnt + 1]) m = len(set(g[1:cnt + 1])) # Unique values to prevent duplicate contributions. for i in range(1, m + 1): # Enumerate the nodes for j in range(1, m + 1): for k in range(1, m + 1): if k == j or i == j or i == k: continue check(g[i], g[j], g[k]) print(int(ans))P5198 [USACO19JAN] Icy Perimeter S种子填充算法可以简单的解决。这道题就是让我们求最大连通块的面积和周长。面积很简单,就是这个冰激凌球中'#'的数量。而周长我们可以轻而易举地推出是这个冰激凌球中'#'上下左右四个方向‘.’的个数。对于递归中的每个点,如果周围是未编号节点,大小加一并且进入该点,如果周围是空地,周长加一

课堂计划

2024-11-27
241123julyfunnoteswilliam工作

P10135 [USACO24JAN] Potion Farming S每个叶子恰好走一次,若叶子个数为 $v$,则只需考虑前 $v$ 次遍历。若一个子树中有 $n$ 次药水出现,$m$ 个叶子,则其对答案的贡献为 $min(n, m)$N = int(1e5 + 19) p = [0] * N cnt = [0] * N dep = [0] * N tot = 0 mx = 0 f = [0] * N fa = [0] * N g = [[] for _ in range(N)] depid = [[] for _ in range(N)] def dfs(node, parent): global mx, tot dep[node] = dep[parent] + 1 fa[node] = parent mx = max(dep[node], mx) depid[dep[node]].append(node) flag = False for neighbor in g[node]: if neighbor != parent: dfs(neighbor, node) flag = True if not flag: tot += 1 f[node] += 1 def read(): return int(input().strip()) def write(value, end_char): print(value, end=end_char) n = read() for i in range(1, n + 1): p[i] = read() for _ in range(1, n): a, b = read(), read() g[a].append(b) g[b].append(a) dfs(1, 1) for i in range(1, tot + 1): cnt[p[i]] += 1 ans = 0 while mx: for i in depid[mx]: if f[i]: if cnt[i] <= f[i]: f[i] -= cnt[i] ans += cnt[i] else: ans += f[i] f[i] = 0 f[fa[i]] += f[i] mx -= 1 write(ans, '\n')P5197 [USACO19JAN] Grass Planting S一个点的相邻的点都不能是同一颜色,如果算上自己有 $n$ 个颜色,那就至少要 $n$ 个颜色。定义每个点的度为 d[i],取 d[i] + 1 的最大值就是答案吗?答案是肯定。设最大值为 $t$,则先随便涂一个点 $i$ 的相邻点,以它为根继续考虑孩子颜色,发现对于每个孩子来说只有 $2$ 个颜色被确定了,从剩下 $t - 2$ 个颜色中任意选一些不同的颜色来涂孩子,以此递归就可以。x = 0 y = 0 ans = 0 n = 0 deg = [0] * 100007 n = int(input()) for i in range(1, n): x, y = map(int, input().split()) deg[x] += 1 # 统计度数 deg[y] += 1 if deg[x] > ans: ans = deg[x] + 1 if deg[y] > ans: ans = deg[y] + 1 print(ans + 1)P7148 [USACO20DEC] Cowntagion S首先,对于每一个节点,如果它的感染者数目已经超过了儿子数,则进行的一定是儿子个数次 (2) 操作。反之,如果在还没有足够的感染者个数的情况下就开始分,显然是不优的。所以对于每一个节点都进行贪心:如果还不够分,就执行若干次 (1) 操作,直到够分了为止。如果已经够分了,就花若干天,每天执行一次 (2) 操作直到所有儿子都有感染者为止。很容易证明这是最优的。于是我们记录每一个节点的儿子个数,记为 cson[u]cson[u],每次 dfsdfs 到一个点,我们就先计算 log⁡cson[u]+1logcson[u]+1,表示自增至足够感染者的天数(注意不是 ceil),然后进行分发,即花 cson[u]cson[u] 天给所有儿子都发一个感染者,最后注意根节点本身就有一只感染者,处理一下即可

课堂计划

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

读取奶牛数量

2024-11-09
241109julyfunnoteswilliam工作

P3416 [USACO16DEC] Moocast Shttps://usaco.org/index.php?page=viewproblem2&cpid=668约翰农场主的 $N$ 头奶牛需要建立一个广播系统,每头奶牛有一个对讲机,具有一定的传输半径 $P$。一头奶牛可以通过直接或中继的方式,将信息传递给其他奶牛。目标是找到从某头奶牛开始广播时,能够到达的奶牛的最大数量。算法分析图的构建:每头奶牛看作一个节点。如果奶牛 $i$ 的对讲机能直接覆盖奶牛 $j$,则在图中从 $i$ 到 $j$ 添加一条有向边。广度优先搜索 (BFS):从每个节点开始,使用 BFS 遍历可达的所有节点。记录从某个节点开始可以到达的最大节点数。代码注释# 读取奶牛数量 n = int(input()) # 初始化邻接表,用于存储每头奶牛可以直接发送信息到达的奶牛 e = [[] for _ in range(n)] # 初始化位置和能量列表 pos, p = [], [] # 读取每头奶牛的位置和能量 for _ in range(n): x1, y1, p1 = map(int, input().split()) pos.append((x1, y1)) p.append(p1) # 计算两头奶牛之间的距离平方 def dis(a, b): return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 # 构建图,确定每头奶牛可以直接向哪些奶牛发送信息 for i in range(n): for j in range(n): if i == j: continue # 跳过自己 # 如果奶牛 j 在奶牛 i 的传输范围内,则添加到邻接表 if dis(pos[i], pos[j]) <= p[i] ** 2: e[i].append(j) from collections import deque # 初始化最大可到达奶牛数量 ans = 0 # 对每头奶牛执行广度优先搜索(BFS) for i in range(n): # 用于记录访问过的奶牛 vis = [False] * n # 创建队列进行 BFS q = deque() q.append(i) tot = 0 vis[i] = True while len(q) > 0: tot += 1 u = q.popleft() # 遍历当前奶牛可以直接到达的奶牛 for v in e[u]: if not vis[v]: # 如果奶牛 v 未访问过 q.append(v) vis[v] = True # 更新最大可到达奶牛数量 if tot > ans: ans = tot # 输出最大可到达奶牛数量 print(ans)程序填空版n = int(input()) e = [[] for _ in range(n)] pos, p = [], [] for _ in range(n): x1, y1, p1 = map(int, input().split()) pos.append((x1, y1)) p.append(p1) def dis(a, b): # 计算两头奶牛之间的距离平方 return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 for i in range(n): for j in range(n): if i == j: continue # 如果奶牛 j 在奶牛 i 的传输范围内,则添加到邻接表 if dis(pos[i], pos[j]) <= ________: e[i].append(j) from collections import ________ ans = 0 for i in range(n): # 用于记录访问过的奶牛 vis = [False] * n # 创建队列进行 BFS q = deque() q.append(i) tot = 0 vis[i] = ________ while len(q) > 0: tot += 1 u = q.________() # 遍历当前奶牛可以直接到达的奶牛 for v in e[u]: if not vis[v]: q.append(v) vis[v] = ________ # 更新最大可到达奶牛数量 if tot > ans: ans = tot # 输出最大可到达奶牛数量 print(______)该算法使用图的表示和 BFS 来计算每头奶牛作为起点时,最多可以到达多少头奶牛。通过遍历每个节点并执行 BFS,我们可以找到最大的可达节点数。复杂度主要受 BFS 和图的构建影响,为 $O(N^2)$。P6111 [USACO18JAN] MooTube Shttps://usaco.org/index.php?page=viewproblem2&cpid=788树的性质:由于是树形结构,任意两个节点之间有且仅有一条路径。 任意两个视频间的相关性是路径上所有边中相关性最小的那一条。 解题思路 深度优先搜索 (DFS): 我们可以从给定的视频节点出发,使用 DFS 遍历整棵树。 在遍历过程中,只访问那些与当前节点相关性大于等于 K 的节点。 计数满足条件的节点。def dfs(u, fa, k): global cnt # 遍历当前节点 u 的所有邻接节点 for v, w in G[u]: # 如果该节点不是父节点且相关性 w 大于等于 k if v != fa and w >= k: cnt += 1 # 满足条件的节点计数加一 dfs(v, u, k) # 递归调用 DFS import sys # 增加递归深度限制,确保 DFS 不会因深度过大而失败 sys.setrecursionlimit(10000) n, Q = map(int, input().split()) G = [[] for _ in range(n + 1)] # 初始化邻接表 # 读取 N-1 条边的信息 for _ in range(n - 1): p, q, r = map(int, input().split()) G[p].append((q, r)) # 添加边 p -> q G[q].append((p, r)) # 添加边 q -> p (无向图) # 处理每个查询 for _ in range(Q): k, v = map(int, input().split()) cnt = 0 # 初始化计数 dfs(v, -1, k) # 从节点 v 开始 DFS,父节点设为 -1 表示无父节点 print(cnt) # 输出满足条件的视频数量填空:def dfs(u, fa, k): global cnt # 遍历当前节点 u 的所有邻接节点 for v, w in G[u]: # 如果该节点不是父节点且相关性 w 大于等于 k if ___ and ___: cnt += 1 # 满足条件的节点计数加一 dfs(___) # 递归调用 DFS import sys # 增加递归深度限制,确保 DFS 不会因深度过大而失败 sys.setrecursionlimit(10000) n, Q = map(int, input().split()) G = [[] for _ in range(___)] # 初始化邻接表 # 读取 N-1 条边的信息 for _ in range(n - 1): p, q, r = map(int, input().split()) G[p].append((q, r)) # 添加边 p -> q G[q].append((___, ___)) # 添加边 q -> p (无向图) # 处理每个查询 for _ in range(Q): k, v = map(int, input().split()) cnt = ___ # 初始化计数 dfs(v, ___, k) # 从节点 v 开始 DFS,父节点设为 -1 表示无父节点 print(___) # 输出满足条件的视频数量作业题 # P2997 [USACO10NOV] Banner Shttps://www.luogu.com.cn/problem/P2997平面上有(0,0)到(n,m)的(n+1)*(m+1)个点。问有多少点对所连的线段不过其他点,且长度在[l,h]范围内枚举 dx, dy, dx 与 dy 互质即可

读取每篇论文的引用次数,并按降序排序

2024-11-06
241102julyfunnoteswilliam工作

## USACO 2021 US Open, Silver Problem 3. Acowdemiahttps://usaco.org/index.php?page=viewproblem2&cpid=1136我们需要找到最大的 h 指数,即至少有 h 篇论文,每篇至少有 h 次引用。Bessie 可以通过调查文章增加引用次数,每篇调查文章最多引用 L 篇论文,总共可以写 K 篇调查文章。首先,将论文的引用次数降序排序,这样可以优先处理引用次数高的论文,减少需要增加的引用次数。然后使用二分查找来确定最大可能的 h 值。我们在 0 到 n 之间查找,通过中间值来验证是否能达到某个 h 指数。检查函数 ok(h) 用于验证是否能通过增加引用次数达到某个 h 指数。它统计当前已经有至少 h 次引用的论文,对于不足 h 次引用的论文,计算需要补充的引用次数,并检查总的可用引用次数是否足够。这种方法通过二分查找高效地逼近最大可能的 h,并确保找到了在给定约束下的最大 h 指数。n, k, L = map(int, input().split()) # 读取每篇论文的引用次数,并按降序排序 c = sorted(list(map(int, input().split())), reverse=True) # 定义一个函数来检查是否可以达到给定的 h 指数 def ok(h): cnt = 0 # 记录至少有 h 次引用的论文数量 tot = k * L # 可以分配的总额外引用次数(k 篇调查,每篇 L 次引用) # 遍历每篇论文的引用次数 for x in c: if x >= h: cnt += 1 # 如果该论文引用次数已经至少是 h,计入满足条件的论文数 continue # 计算该论文需要的额外引用次数以达到 h 次引用 if h - x <= tot and h - x <= k: tot -= h - x # 使用额外的引用次数 cnt += 1 # 计入满足条件的论文数 # 返回是否有至少 h 篇论文满足条件 return cnt >= h # 二分查找来确定最大可能的 h 指数 l, r, ans = 0, n, -1 while l <= r: mid = (l + r) // 2 if ok(mid): ans = mid # 如果当前的 h 可行,尝试更大的 h l = mid + 1 else: r = mid - 1 # 如果当前的 h 不可行,尝试更小的 h # 输出最大可能的 h 指数 print(ans)程序填空:n, k, L = map(int, input().split()) # 读取每篇论文的引用次数,并按降序排序 c = ___ # 定义一个函数来检查是否可以达到给定的 h 指数 def ok(h): cnt = 0 # 记录至少有 h 次引用的论文数量 tot = ___ # 可以分配的总额外引用次数(k 篇调查,每篇 L 次引用) # 遍历每篇论文的引用次数 for x in c: if x >= h: ___ # 如果该论文引用次数已经至少是 h,计入满足条件的论文数 continue # 计算该论文需要的额外引用次数以达到 h 次引用 if h - x <= tot and h - x <= k: tot -= ___ # 使用额外的引用次数 cnt += 1 # 计入满足条件的论文数 # 返回是否有至少 h 篇论文满足条件 return cnt >= h # 二分查找来确定最大可能的 h 指数 l, r, ans = 0, n, -1 while l <= r: mid = ___ if ___: ans = mid # 如果当前的 h 可行,尝试更大的 h ___ else: r = mid - 1 # 如果当前的 h 不可行,尝试更小的 h # 输出最大可能的 h 指数 print(ans)P6282 [USACO20OPEN] Cereal Shttps://usaco.org/index.php?page=viewproblem2&cpid=1039如果我们增加奶牛,即倒着求每个答案,最后倒着输出就行了。如果增加一头奶牛,又会出现什么情况呢?如果它最喜欢的麦片没有被选择,那么它就会选它,且不影响其他奶牛;如果它最喜欢的麦片被选择,因为它的优先级比其他牛都高,所以会把其他牛的麦片“抢”过来,其他牛只能“退而求其次”。递归求解即可,因为所有奶牛最多选两次,所以 solvesolve 函数的复杂度是 Θ(1)Θ(1) 的,整个代码的时间复杂度为 Θ(N)Θ(N)。实现方法见代码注释:cici​ 表示第 ii 头奶牛的喜好,hihi​ 表示拿走第 ii 种麦片的牛的编号,resiresi​ 表示移走 i−1i−1 头牛的答案,curcur 是计算答案的计数器。因为领麦片的牛越多,领到麦片的牛就越多,所以越往后面,curcur 就越大,故每次计算的时候 curcur 不需要清零。N = 123456 class Cow: def __init__(self, f, s): self.f = f self.s = s c = [Cow(0, 0) for _ in range(N)] h = [0] * N res = [0] * N cur = 0 def solve(x, y): global cur if h[y] == 0: h[y] = x cur += 1 elif h[y] > x: z = h[y] h[y] = x if y == c[z].f: solve(z, c[z].s) def main(): global cur n, m = map(int, input().split()) for i in range(1, n + 1): f, s = map(int, input().split()) c[i] = Cow(f, s) for i in range(n - 1, -1, -1): solve(i + 1, c[i + 1].f) res[i + 1] = cur for i in range(1, n + 1): print(res[i]) if __name__ == "__main__": main() 作业题 # P2997 [USACO10NOV] Banner Shttps://www.luogu.com.cn/problem/P2997平面上有(0,0)到(n,m)的(n+1)*(m+1)个点。问有多少点对所连的线段不过其他点,且长度在[l,h]范围

课堂计划

2024-10-19
241020julyfunnoteswilliam工作

Problem 1. MooBuzz - Shttps://usaco.org/index.php?page=viewproblem2&cpid=858二分法复习题。当确定等待上限为 $t$ 时,需要多少辆车可以模拟出来:即时间轴从左往右依次加入奶牛,记录奶牛数量和第一头奶牛的时间,若超时或满载则加一辆。因此可以二分找到最小的等待上限,若该上限可行则考虑变小,否则变大。伪代码:读入 n, m, c 和奶牛时间 li li 排序 def ok(t): 初始化变量(自行设计) 枚举第二头到最后一头奶牛: 如果超时或者满载: 换一辆新车 否则: 奶牛上车 返回车数量 <= 车限制 l, r = 0, int(1e9) while l < r: mid = l 和 r 的中点 如果 mid 可以 减小 r 否则 增大 ln, m, c = map(int, input().split()) li = list(map(int, input().split())) l, r = 0, int(1e9) li.sort() def ok(t): cnt = 1 st = li[0] cow = 1 for i in range(1, n): if li[i] - st > t or cow == c: cnt += 1 st = li[i] cow = 1 else: cow += 1 return cnt <= m while l < r: mid = (l + r) // 2 if ok(mid): # could be smaller r = mid else: l = mid + 1 print(l)Problem 2. MooBuzz - Shttps://usaco.org/index.php?page=viewproblem2&cpid=966找规律。每隔 15 个数中,被替代的数字形成一个循环,导致每 15 个数才会报出 8 个数。 最终报的数每过 8 个会增加 15,在 8 个以内则按照下表循环:0 1 2 3 4 5 6 7 1 2 4 7 8 11 13 14n = int(input()) - 1 g = n // 8 # 属于第几组 li = [1, 2, 4, 7, 8, 11, 13, 14] print(g * 15 + li[n % 8])Problem 3. Problem 1. Marathon这道题目是一道动规的题目。令f[i][j]代表到了第i个检查点,跳过了j个的最短距离。f[i][j]=min(f[i-l-1][j-l]+dis(i,i-l-1))复杂度为 O(n^3

GGHH ; G + H 必须 H 包含所有 H

2024-10-09
241013julyfunnoteswilliam工作

解救小哈 - BFS 版本讲解使用队列存储到达过的点,对队列中的每一个点再向四个方向拓展。最优性:最近的点会最早进入队列程序填空:from collections import deque q = deque() n, m, t = map(int, input().split()) sx, sy, tx, ty = map(int, input().split()) a = [[0 for _ in range(m + 1)] for _ in range(n + 1)] step = [[-1 for _ in range(m + 1)] for _ in range(n + 1)] for _ in range(t): x, y = map(int, input().split()) a[x][y] = 1 def ok(x, y): return 1 <= x <= n and 1 <= y <= m and a[x][y] == 0 and step[x][y] == -1 d = ((0, 1), (0, -1), (1, 0), (-1, 0)) q.append((sx, sy)) step[sx][sy] = 0 while len(q) > 0: x, y = q.popleft() for i in range(4): nx, ny = x + d[i][0], y + d[i][1] if ok(nx, ny): q.append((nx, ny)) step[nx][ny] = step[x][y] + 1 print(step[tx][ty]) 3 3 2 1 1 3 1 2 1 2 2Leadershttps://usaco.org/index.php?page=viewproblem2&cpid=1275观察规律:若 G + H 组合,则 H 必须包含后面全部 H,且前面的 G 是第一个且包含全部 G,或 G 包含此 H。判断时,使用最早出现的 H 和 G 判断n = int(input()) s = input() p = list(map(int, input().split())) p = [(x - 1) for x in p] fh, fg = -1, -1 lh, lg = -1, -1 for i in range(n): if s[i] == 'H': lh = i if fh == -1: fh = i else: lg = i if fg == -1: fg = i ans = 0 # GGHH ; G + H 必须 H 包含所有 H if p[fh] >= lh: # fh and some g before that for i in range(fh): if p[i] >= fh or (i == 0 and p[i] >= lg): ans += 1 if p[fg] >= lg: for i in range(fg): if p[i] >= fg or (i == 0 and p[i] >= lh): ans += 1 print(ans)n = int(input()) s = input() p = list(map(int, input().split())) p = [___ for x in p] fh, fg = -1, -1 lh, lg = -1, -1 for i in range(n): if s[i] == 'H': ___ if fh == -1: ___ else: ___ if fg == -1: ___ ans = 0 # GGHH ; G + H 必须 H 包含所有 H if p[fh] >= lh: # fh and some g before that for i in range(fh): if ___ ans += 1 if p[fg] >= lg: for i in range(fg): if p[i] >= fg or (i == 0 and p[i] >= lh): ans += 1 print(ans)# P2385 [USACO07FEB] Bronze Lilypad Pond Bhttps://www.luogu.com.cn/problem/P2385经典的 bfs 题目,但此题每个拓展点有八个方向进行选择,类似于象棋马步创建空队列 将起点放入队列 while 队列不空: 取出并弹出队首 u 将 u 的八个方向判断是否在边界内且为莲花或终点 将可行且没走过的点加入队列 输出终点距离 python deque: push: d.append(4) / a.appendleft(4) front: d[0] pop: d.popleft() / d.pop(

教学计划-找规律II

2024-09-29
240929julyfunnoteswilliam工作

Circular Barnhttps://usaco.org/index.php?page=viewproblem2&cpid=1255首先考虑一个房间内如果一直拿,谁会赢。从 1 开始推导,发现当数量为 4k 时,后手赢,其他先手赢。需要拿几次可以取完?如果后手赢,那么先手要尽可能让对方赢所需拿的次数多一点。如果先手赢,每个房间遵循尽快赢的策略。有,若偶数,则次数为 i // 2,否则若为 4k + 1,则取最大质数满足取完后为 4k,而 4k + 3 类似: if i % 2 == 0: towin[i] = i / 2 elif i % 4 == 1: if once[i]: m1 = i towin[i] = 1 else: towin[i] = (i - m1) / 2 + 1 elif i % 4 == 3: if once[i]: m3 = i towin[i] = 1 else: towin[i] = (i - m3) / 2 + 1首先用质数筛筛出质数。对于取完次数为 k 的房间,需要第 k / 2 + 1 轮到这个房间才能有人输。N = int(5e6) once = [True] * (N + 1) prime = [] for i in range(2, N + 1): if once[i]: prime.append(i) for j in range(len(prime)): v = prime[j] if v * i > N: break once[v * i] = False if i % v == 0: break m3 = 3 # largest i: 4i + 3 prime m1 = 1 towin = [0, 1, 1, 1] + [0] * int(N + 10) for i in range(4, int(N + 1)): if i % 2 == 0: towin[i] = i // 2 elif i % 4 == 1: if once[i]: m1 = i towin[i] = 1 else: towin[i] = (i - m1) // 2 + 1 elif i % 4 == 3: if once[i]: m3 = i towin[i] = 1 else: towin[i] = (i - m3) // 2 + 1 t = int(input()) for _ in range(t): n = int(input()) a = [0] + list(map(int, input().split())) firstmin = 1e9 win = 0 for i in range(1, n + 1): rd = towin[a[i]] // 2 + 1 if rd < firstmin: firstmin = rd win = towin[a[i]] % 2 if win == 1: print("Farmer John") else: print("Farmer Nhoj")Sleepy Cow Herdinghttps://usaco.org/index.php?page=viewproblem2&cpid=918最少的步数:假设最后所有奶牛集中到 p ~ q,显然有 a[0] <= p < q <= a[n - 1],长度为 n,那么发现任意指定一个 p ~ q,每一步都可以把一头在外面的奶牛移进来。只需要双指针法找到长度为 n 的包含奶牛个数最多的区间就行。最多的步数:定义总距离为每对相邻奶牛之间距离 - 1 的和。如果边缘有两头奶牛相邻,发现每步一定可以只让距离减 1,而第一步一定会把两端移到中间某个位置,故最优方案就是两端先造成一个相邻,之后不断减 1n = int(input()) a = [int(input()) for _ in range(n)] a.sort() t = 0 minans = 1e9 for s in range(n): while t + 1 <= n - 1 and a[t + 1] - a[s] + 1 <= n: t += 1 minans = min(minans, n - (t - s + 1)) print(minans) totdis = a[n - 1] - a[0] - (n - 1) print(totdis - min(a[2] - a[1], a[n - 1] - a[n - 2]) + 1)作业题:COW Operationshttps://usaco.org/index.php?page=viewproblem2&cpid=123

教学计划-找规律

2024-09-21
240921julyfunnoteswilliam工作

Problem 3. Spaced Outhttps://usaco.org/index.php?page=viewproblem2&cpid=1088从小规模数据开始绘制,发现要么第一行确定后,每一行与上一行相反。要么第一列确定后,每一行与上一行相反。证明:首先考虑第一行存在连续的 11 或者 00 情况我们用 f[j][0] 表示第一行第 j 列为 0 时,整个第 j 列的收益,f[j][1] 相反。n = int(input()) f = [[0, 0] for _ in range(n)] v = [[0, 0] for _ in range(n)] for i in range(n): s = list(map(int, input().split())) for j, x in enumerate(s): f[j][(i + 1) % 2] += x v[i][(j + 1) % 2] += x ans1 = 0 for x, y in f: ans1 += max(x, y) ans2 = 0 for x, y in v: ans2 += max(x, y) print(max(ans1, ans2))程序填空:n = int(input()) f = [[0, 0] for _ in range(n)] v = [[0, 0] for _ in range(n)] for i in range(n): s = list(map(int, input().split())) for j, x in enumerate(s): f[___][___] += x v[___][___] += x ans1 = 0 for x, y in f: ans1 += __ ans2 = 0 for x, y in v: ans2 += ___ print(max(ans1, ans2))Problem 3. Moo Route大胆猜测如果能不改方向就不改。往右走如果遇到剩余次数为 0 就掉头。往左走如果左边剩余次数 <= 2 且右边还有可以走的就掉头。否则就回不来了。n = int(input()) a = list(map(int, input().split())) + [0] s = sum(a) p = 0 d = 1 for _ in range(s): if (d == 1 and a[p] == 0) or (d == -1 and a[p - 1] <= 2 and a[p] > 0): d = -d if d == 1: print("R", end='') a[p] -= 1 else: print("L", end='') a[p - 1] -= 1 p += d读题 + 思考USACO 2022 December Contest, SilverProblem 2. Circular Barnhttps://usaco.org/index.php?page=viewproblem2&cpid=125

教学计划-差分与离散化

2024-09-17
240914julyfunnoteswilliam工作

差分与离散化https://www.luogu.com.cn/record/176971240 火烧赤壁前缀和思想:在起火的左端点标注 +1,右端点标注 -1,则做前缀和以后,大于 0 的线段都是起火的,例如:[ 0 0 +1 +1 0 -1 -1 0] [ 0 0 1 2 2 1 0 ]这里就有长度为 4 的起火段。由于坐标太大,无法直接前缀和,可以离散化,将大坐标映射到小坐标,即排序 + 去重后用 map 标号,在做前缀和即可。n = int(input()) x = [] y = [] for _ in range(n): xx, yy = map(int, input().split()) x.append(xx) y.append(yy) a = sorted(x + y) b = [a[0]] for i in range(1, len(a)): if a[i] != a[i - 1]: b.append(a[i]) di = {} for i in range(len(b)): di[b[i]] = i pre = [0] * len(b) for i in range(n): pre[di[x[i]]] += 1 pre[di[y[i]]] -= 1 ans = 0 for i in range(1, len(b)): pre[i] += pre[i - 1] if pre[i - 1] > 0: ans += b[i] - b[i - 1] print(ans)n = int(input()) x = [] y = [] for _ in range(n): xx, yy = map(int, input().split()) x.append(xx) y.append(yy) a = sorted(___) b = [a[0]] for i in range(1, len(a)): if ___: b.append(a[i]) di = {} for i in range(len(b)): ___ = i pre = [0] * len(b) for i in range(n): ___ += 1 ___ -= 1 ans = 0 for i in range(1, len(b)): pre[i] += pre[i - 1] if pre[i - 1] > 0: ans += ___T2 # P3029 [USACO11NOV] Cow Lineup Shttps://usaco.org/index.php?page=viewproblem2&cpid=89i 表示当前取的左端点,j 表示右端点。用 map 离散化存储不同品种的奶牛数量。当 i 变动时,向右移动 j 保证奶牛品种数必须为全部品种即可。作业题 P1904 天际线https://www.luogu.com.cn/problem/P1904由于坐标范围很小,可以用 h[i] 表示 i 开始的单位线段所占据的最高楼栋。初值均为 $0$,随后查找 h[i] 变化处输出横纵坐标即可。H = [0] * 10005 while True: try: a, h, b = map(int, input().split()) except EOFError: break for i in range(a, b + 1): H[i] = max(H[i], h) h = 0 for i in range(1, int(1e4)): if h != H[i]: h = H[i] print(i, H[i], end=' '

jfmfoi

2024-08-17
24.08.17jfmfoijulyfunnotes工作

快速幂: https://www.luogu.com.cn/problem/P1226分治最大字段和:#include<cstdio> int n , arr[200200]; //arr存储该序列 const int minn = -19260817; // 定义最小值 inline int Max( int a , int b) { return a > b ? a : b ;} //自定义 Max 函数(好像比stl的快一点) int rec( int l , int r ) { //分治函数 if ( l == r ) { // l=r时,直接返回该位置的值 return arr[l]; } int mid = ( l + r ) >> 1; int sum = 0 , ret1 = minn , ret2 = minn; //ret1为[l..mid]区间内包含mid的最大子段和,ret2为[mid+1..r]区间内包含(mid+1)的最大子段和 for( int i = mid ; i >= l ; i-- ) { sum += arr[i]; ret1 = Max( ret1 , sum ); } //求出[i..mid]区间最大值 sum = 0; for( int i = mid+1 ; i <= r ; i++ ) { sum += arr[i]; ret2 = Max( ret2 , sum ); } //求出[mid+1..r]区间最大值 return Max( Max( rec( l , mid ) , rec( mid + 1 , r ) ) , ret1 + ret2 ); //返回可能一 可能二 可能三 中的最大值 } int main() { // 以下主函数 scanf("%d", &n ); for( int i = 1 ; i <= n ; i++ ) { scanf("%d" , &arr[i] ); } printf("%d" , rec(1 , n) ); return 0; }作业 - 简单st 表: https://www.luogu.com.cn/problem/P3865(数学)集合求和: https://www.luogu.com.cn/problem/P2415(st 表) 忠诚: https://www.luogu.com.cn/problem/P1816附加作业(可选)麦森数: https://www.luogu.com.cn/problem/P1045逆序对: https://www.luogu.com.cn/problem/P1908喷泉: https://www.luogu.com.cn/problem/solution/P716

No more posts to load.