HLAIA-光子

背包 01背包 01背包问题通常为：给定 nnn 种物品和一个背包，第 iii 个物品体积为 cic_ici​ ，价值为 wiw_iwi​ ，背包地容量为 CCC 。如何选择装入背包的物品，使装入背包中的物品的总价值最大？ 以 HDU 2602 为例 题目 用自底向上的递推完成转移过程， dp[i][j]dp[i][j]dp[i][j] 表示把前 iii 个物品(从第 111 个到第 iii 个)装入容量为 jjj 的背包中获得的最大价值。假设现在递推到 dp[i][j]dp[i][j]dp[i][j] ，分两种情况： (1) 第 iii 个物品的体积比 jjj 还大，则不能装入当前背包，直接继承前 i−1i-1i−1 个物品装入容量为 jjj 的背包，即 dp[i][j]=dp[i−1][j]dp[i][j] = dp[i-1][j] dp[i][j]=dp[i−1][j] (2) 第i个物品体积比j小，能装进背包，又分为两种：装或不装 ①装 dp[i][j]=dp[i−1][j−c[i]]+w[i]dp[i][j] = dp[i-1][j-c[i]] + w[i] ...

ITA练习赛 F 小d是一个搞房地产的土豪。每个人经商都有每个人经商的手段，当然人际关系是需要放在首位的。 小d每一个月都需要列出来一个人际关系表，表示他们搞房地产的人的一个人际关系网，但是他的精力有限，对应他只能和能够接触到的人交际。比如1认识2,2认识3，那么1就可以接触3进行交际，当然1和2也可以交际。 小d还很精明，他知道他和谁交际的深获得的利益大，接下来他根据自己的想法又列出来一个利益表，表示他和这些人交际需要耗用多少精力，能够获得的利益值为多少。 小d想知道，他在精力范围内，能够获得的利益值到底是多少。 设定小d自己的编号为1.并且对应一个人的交际次数限定为1. 本题包含多组输入，第一行输入一个数t，表示测试数据的组数 每组数据的第一行输入三个数，N,M，C，表示这个人际关系网一共有多少个人，关系网的关系数，以及小d的精力值 接下来N-1行，每行两个数ai，bi。这里第i行表示和编号为i+1的人认识需要花费ai的精力，能够获得的利益值为bi。 再接下来M行，每行两个数x，y，表示编号为x的人能够和编号为y的人接触 t<=50 2<=N<=1000...

2025年7月21日~7月23日(实际上要算上24日)，我们小队选择2022年数模国赛B题实战演练。 我们VP的规则是 答题过程中，不看当年的国赛获奖论文。 可以借助各种工具找资料，但是最开始的几个小时不要去找，只凭自己想。这样做是为了防止我们自己的思路在一开始就被网上的资料和思路牵头走。 完成论文并交给评委老师审阅后，去中国大学生在线上找当年国赛论文展示，比对自己的不足。看论文有个原则：辩证看待，即使是国一论文，也可能有错误和欠缺。 论文、源码和附录材料我已上传到github。 在第一天上午，老杨就迅速把问题1的第1、2问的数学模型建立出来了，并附带有第3小问的思路。我随之实现第一、二小问的代码，并把支撑材料的图给绘制出来，发给老陈。老杨数学功底很扎实，建模快；我不熟悉numpy、pandas和matplotlib，编程上花的时间多了些。 编程手在编程时，需要把建模手的思路完全摸清，然后对着题目描述进行编程规划，再开始敲代码。因此，我发现我们第三小问的思路有误，会错题意。我们原本的思路是用第一小问提出的数学架构去解决第三小问的问题，但是题目背景有变，仅凭纯数学方法无法解决...

牛客暑期多校4 开赛以来最难的一场，牢底坐穿。验题组用o3对最简单的题CF估分为1600~1700，且只有这道题估分在2000以下。不是，这给开了一场WF？ 可惜了，这周没多少时间补 Problem F. For the treasury! 公元11世纪初，有一些被称为维京人的丹麦入侵者在英格兰活动。 Askeladd是一群维京海盗的领袖，他在这片肥沃的土地上寻找宝藏。在一夜袭击了1个村庄后，他们共收集了nnn个宝藏，按顺序排列，价值分别为a1,a2,…,ana_1,a_2,\ldots,a_na1​,a2​,…,an​。Askeladd的团队有一项关于如何分配这些宝藏的协议：作为领袖的Askeladd将取走前面的kkk个宝藏，即价值为a1,a2,…,aka_1,a_2,\ldots,a_ka1​,a2​,…,ak​的宝藏，而其余海盗将分配其余的宝藏。但是，由于时间太晚，他们决定在第二天早上进行这个分配。 Askeladd非常聪明且狡猾，他在夜间偷偷摸摸地试图重新安排宝藏，以便他可以获得更多的宝藏总价值。然而，由于某种原因，他只被允许交换两个相邻的宝藏。此外，考虑到被其他...

差分 差分是前缀和的逆运算，运用于区间修改和询问。当对数据集A的某个区间做修改时，引入差分数组D，只需要修改这个区间的端点，就能记录整个区间的修改，这个修改的复杂度为O(1) 。当所有修改都完成后，再利用差分数组计算出新的A。 差分数组D[]的定义是：D[k] = a[k] - a[k-1]，a[]是原数组 显然，a[i] = D[1]+D[2]+...+D[i]，a[]是D[]的前缀和 例如，把数组区间[L,R]内的每个元素都加上d，只需要对应的差分数组D[]做以下操作： 把D[L]加上d：D[L] += d; 把D[R+1]减去d:D[R+1] -= d; D[]只会修改区间[L,R]内的值，不会修改到区间外的，要查询a[i]时，做一个D[i]的前缀和即可 以HDU 1556 为例 题目 代码 1234567891011121314151617181920212223242526#include <bits/stdc++.h>using namespace std;const int maxn = 1e6+1;int a[maxn],D[maxn];int ...

2025牛客暑期多校1 E. 无尽的梯子 Time limit: 2 seconds Memory limit: 512 megabytes 在古老的平方王国，居民ccc (c=1,2,3,…)(c = 1,2,3,\ldots)(c=1,2,3,…)住在离地面c2c^2c2单位高的石柱上。 为了方便大家串门，平方国王打造了不同长度的梯子，长度为ddd的梯子可以让高度差的绝对值恰好为ddd的两个居民互相拜访。由于预算有限，长度为ddd的梯子被打造当且仅当存在两个居民的高度差的绝对值恰好为ddd，且同一长度的梯子仅会打造一架。 这些梯子按长度从小到大依次编号1,2,3,…1,2,3,\ldots1,2,3,…。这天居民aaa想要拜访居民bbb，你需要找出他们所用梯子的标号。 Input 输入的第一行包含一个整数TTT (1≤T≤104)(1 \leq T \leq 10^4)(1≤T≤104)，表示测试数据的组数。对于每组测试数据： 仅有的一行包含两个整数aaa和bbb (1≤a,b≤109,a≠b)(1 \leq a, b \leq 10^9, a \neq b)(1≤a,b...

欧几里得算法(辗转相除法) 求最大公约数 C++的库有 __gcd()函数，赛时推荐直接用这个。博文里讲讲原理和实现 原理是：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数 gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a\%b) gcd(a,b)=gcd(b,a%b) 用递归来实现 123int gcd(int a,int b){ return b==0 ? a : gcd(b,a%b);} 最小公倍数 先求最大公约数gcd(a,b) 123int gcd(int a,int b){ return b==0 ? a : gcd(b,a%b);} 最小公倍数 lcm(a,b)lcm(a,b)lcm(a,b) 与其的关系为: gcd(a,b)∗lcm(a,b)=a∗bgcd(a,b)*lcm(a,b)=a*b gcd(a,b)∗lcm(a,b)=a∗b 因此 lcm(a,b)=(a∗b)/gcd(a,b)lcm(a,b)=(a*b)/gcd(a,b) lcm(a,b)=(a∗b)/...

Python学习笔记 python是最好的语言.cpp 本篇文章用来记录py基本语法的概览。 可以去菜鸟教程上学习py的语法，菜鸟上有详细且免费的文本教程。 基本语法 标识符 python的标识符命名规则和C++相差无几，略有不同的是，py标识符长度没有限制，但还是以简洁性和区分性为原则。 关键字 py标准库提供了一个keyword模块，可以输出当前版本的所有关键字。 1234import keywordprint(keyword.kwlist)['False', 'None', 'True', 'and', 'as', 'assert', 'async', 'await', 'break', 'class', 'continue', 'def', 'del', 'elif', 'els...

概念与公式 完全图 完全图（Complete Graph）是一个简单的无向图，其中每一对不同的顶点之间都恰好有一条边相连。换句话说，完全图是一个所有顶点都相互连接的图。 完全图的性质包括： 顶点数为(n)的完全图有(n(n−1)2)(\frac{n(n-1)}{2})(2n(n−1)​)条边。 完全图中的每个顶点的度数都是(n-1)。 完全图是连通的，且是((n-1))-连通的。 完全图是((n-1))-正则的。 完全图(K_n)的色数是(n)，即需要(n)种颜色才能给图中的顶点着色，使得任何两个相邻的顶点颜色不同。 图的储存 邻接矩阵 用矩阵graph[N][N]储存边，N为节点总数。若 i 和 j 是直连的邻居，则用graph[i][j]表示边(i,j)的权值；若 i 和 j 不直连，一般把graph[i][j]复制无穷大。 邻接矩阵适合稠密图(大部分边都有权值)，不适合稀疏图(大部分边都无穷大)。 邻接矩阵的空间大小是N2。能表示有向边或无向边，若是无向图，那么边 i -> j 的权值是graph[i][j]=graph[j][i]；若是有向图，那么graph...

快速幂 以下是快速幂的模板 123456789int fastPow(int a,int n){//计算aⁿ int ans=1; //用ans返回结果 while(n){ //把n看成二进制数，逐个处理它最后一位 if(n&1) ans*=a; //&按位与操作，如果n的最后一位是1，表示这个地方需要参与计算 a*=a; //递推：2次方--4次方--八次方··· n>>=1; //n右移一位，把刚处理过的n的最后一位去掉 } return ans;} 通常题目都会要求模p，根据模的性质： (a+b) % p=(a%p + b%p) %p(a+b)\ \% \ p = (a \% p \ + \ b \% p)\ \% p (a+b) % p=(a%p + b%p) %p (a×b) % p=(a%p ×b%p) %p(a \times b)\ \% \ p = (a \% p \ \times b \% p) \ \% p (a×b) % p...