💻技术

算法笔记（五）——DP（Python实现） DP 数字三角形 f=[] n=int(input()) for _ in range(n): f.append([int(x) for x in input().split()]) for i in range(n-2,-1,-1): for j in range(i+1): f[i][j]=max(f[i+1][j], f[i+1][j+1])+f[i][j] print(f[0][0]) 背包 空间优化成1维之后，只有完全背包问题的体积是从小到大循环的 01背包 N = int(1e3+10) f=[ 0 for _ in range(N) ] n,v=map(int,input().split()) for i in range(n): vi,wi=map(int,input().split()) for j in range(v, vi-1,-1): f[j]=max(f[j],f[j-vi]+wi) print(f[v]) 多重背包 单调队列 MN = int(2e4+10) f=[0 for _ in range(MN)] q=[0 for _ in range(MN)] g=[0 for _ in range(MN)] N,V = map(int, input().split()) for i in range(N): v,w,s=map(int, input().split()) g=f[:] for j in range(v): hh,tt=0,-1 for k in range(j,V+1,v): while hh<=tt and q[hh]<k-s*v: hh+=1 while hh<=tt and g[q[tt]]+(k-q[tt])//v*w <= g[k]: tt-=1 tt+=1 q[tt]=k f[k]=g[q[hh]]+(k-q[hh])//v*w print(f[V]) 二维费用背包 N = int(1e2+10) f=[[0]*N for _ in range(N)] n,V,M = map(int , input().split()) for i in range(n): v,m,w=map(int , input().split()) for j in range(V,v-1,-1): for k in range(M, m-1, -1): f[j][k]=max(f[j][k], f[j-v][k-m]+w) print(f[V][M]) 宠物小精灵 题目大意：小智在野外捕捉宠物小精灵，他带了一些精灵球和皮卡丘，精灵球可以捕捉小精灵，但每捕捉一个小精灵都会消耗精灵球和减少皮卡丘的体力。现在给定小智拥有的精灵球数量、皮卡丘的初始体力值以及每个小精灵需要的精灵球数量和对皮卡丘造成的伤害数目，问小智最多能捕捉多少个小精灵，并且在这种情况下，皮卡丘的剩余体力值最多是多少。 ...

算法笔记（一）——基础+杂项（Python实现） 基础+杂项 快速排序 def quick_sort(q, l, r): if l>=r: return i,j,x=l-1,r+1,q[(l+r)>>1] while i<j: i+=1 while q[i]<x: i+=1 j-=1 while q[j]>x: j-=1 if i<j: q[i], q[j] = q[j], q[i] quick_sort(q, l, j) quick_sort(q, j+1, r) n=int(input()) arr=list(map(int, input().split())) quick_sort(arr,0,n-1) print(" ".join(map(str, arr))) 随机选择pivot import random class Solution: def sortArray(self, nums: List[int]) -> List[int]: def quick_sort(q, l, r): if l >= r: return # 随机选择 pivot i, j = l, r rand_idx = random.randint(l, r) x = q[rand_idx] while i <= j: while q[i] < x: i += 1 while q[j] > x: j -= 1 if i <= j: q[i], q[j] = q[j], q[i] i += 1 j -= 1 quick_sort(q, l, j) quick_sort(q, i, r) quick_sort(nums, 0, len(nums) - 1) return nums 归并排序 j = mid+1 !!! ...

周赛240407 出师不利，第一题变量名能写错，慢就是快，少就是多，提交之前一定要有万全的检查。 第二题100242. 满足距离约束且字典序最小的字符串 纯思维题，先花时间想清楚基础问题再想后面的问题。吸取教训，代码一定要写的清晰明了，自己才能更好的看懂并写下去。 ...

VP 周赛 第 389 场周赛 第三题3085. 成为 K 特殊字符串需要删除的最少字符数 双指针优化$O(n)$ 第三题做出来了但做法不优并且错的次数太多了。 题目大意：给定一个字符串word和一个整数k，定义特殊字符串为满足|freq(word[i]) - freq(word[j])| <= k对于字符串中所有下标i和j都成立的字符串。其中，freq(x)表示字符x在word中的出现频率，|y|表示y的绝对值。要求计算使word成为k特殊字符串所需删除的字符的最小数量。 ...

周赛240331 第四题 100240 最小化曼哈顿距离 题目大意：给定一个二维平面上的点集，求移除其中一个点后，剩余点集中任意两点之间的最大曼哈顿距离的最小值。 实现思路：首先，对于曼哈顿距离而言，它的定义是两点在各个坐标轴上的差的绝对值之和。所以移除一个点后，影响到最大曼哈顿距离的主要是距离移除点最近的点。我们可以将点的坐标进行转换，将其转换为(x+y)和(x-y)的形式，这样在平面上的曼哈顿距离就可以等效为在转换后的坐标系下的欧几里得距离。然后我们用两个有序集合分别维护x+y和x-y的坐标轴上的值，分别为xset和yset。然后遍历每个点，从点集中移除一个点，更新最大距离，找到最小值。 ...

周赛 24/3/24 第三题 100258 3092. 最高频率的 ID 题目大意：给定两个长度为n的整数数组nums和freq，nums中的每个元素表示一个ID，对应的freq中的元素表示这个ID在集合中此次操作后需要增加或者减少的数目。现要求在每一步操作后，返回出现频率最高的ID数目，若集合为空则为0。 SortedList实现 ...

机器学习简介 Different types of Functions Regression : The function outputs a scalar(标量）. predict the PM2.5 Classification ： Given options (classes), the function outputs the correct one. Spam filtering Structured Learning ： create something with structure(image, document) Example : YouTube Channel 1.Function with Unknown Parameters. $$ y=b+wx_1 $$ 2.Define Loss from Training Data Loss is a function of parameters $$ L(b,w) $$ ...

PyTorch PyTorch Tutorial Python3中机器学习框架 dataset = MyDataset(file) dataloader = DataLoader(dataset, batch_size = size , shuffle = True) Training : True Testing : False self.data = ... 处应实现数据读取与预处理，常见方式： 从文件读取：pd.read_csv(file).values 或 np.load(file) 从 PyTorch tensor：torch.FloatTensor(data) 或 torch.from_numpy(data) 需统一转为 torch.Tensor，否则 DataLoader 无法正确处理 from torch.utils.data import Dataset, DataLoader class MyDataset(Dataset): def __init__(self, file): # read data & preprocess self.data = ... def __getitem__(self,index): #return one sample at a time return self.data[index] def __len__(self): #return the size of the dataset return len(self.data) dataset = MyDataset(file) dataloader = DataLoader(dataset, batch_size, shuffle = True) shuffle : Training -> true Testing -> false Tensors High-dimensional matrices(arrays) ...

Officially begin Deep = Many hidden layers Neural Network Find a function in function set. Goodness of function Pick the best function Backpropagation - Backward Pass(反向传播) 反向的neural network Regression Stock Market Forecast Self-driving Car Recommendation Step 1 : Model A set of function Step 2 : Goodness of Function $$ \hat{y}^1代表x^1对应的确切值 $$ ...

Convolutional network (CNN) Network的架构调整 1、All the images to be classified have the same size. Receptive field Simplification 1 - Typical Setting all channels : 会看所有的channels kernel size : 长和宽 （e.g., 3*3) Stride : 移动的步长,希望有高度的重叠 ...

Spatial Transformer（STN） 处理旋转和放大图形的CNN分类 interpolation 插值法 Self-attention Sequence Labeling consider the context -> 参数很大并且容易Overfitting Self-attention会持有整个sequence的信息 ...

Android开发 前面 在无形中已经被很多不如你的人打败。 移动生态 产品经理 衡量app : 使用时长 Android知识图谱 对外 为用户创造价值 页面 逻辑 数据 架构师 第一层交付：满足交付的基本技能 ...

竞赛编程极致优化技巧完全指南 基于 Apple M4 ARM64 + clang++ 21.0.0 实测验证，16 道 Codeforces 真题实战，100+ 源文件，38 个编译二进制全面基准测试。 目录 核心原则：正确性第一，算法为王 运行时优化 内存优化 代码长度优化 (Code Golf) 跨维度权衡与实测数据 最佳实践清单 1. 核心原则 1.1 三层优化金字塔 ┌──────────────┐ │ 算法替换 │ ← 最大收益 (10×-100×) │ (O(n²)→O(n log n)) │ ├──────────────┤ │ 数据结构优化 │ ← 中等收益 (2×-10×) │ (SoA, 扁平化)│ ├──────────────┤ │ 微优化 │ ← 边际收益 (5%-50%) │ (内联, 分支) │ └──────────────┘ 铁律：先换算法，再调实现。 用 __builtin_prefetch 优化一个 O(n²) 算法永远不如换成 O(n log n)。 ...