2013暑期规划
数学建模暑期集训27：粒子群+遗传算法求解多目标规划问题
多目标规划问题定义 在实际问题中大都具有多个目标且需要同时满足，即在同一问题模型中同时存在几个非线性目标，而这些目标函数需要同时进行优化处理，并且这些目标又往往是互相冲突的
日期 2023-06-12 10:48:40
数学建模暑期集训15：matlab求解多目标规划模型
多目标规划模型的求解方法 1.传统优化算法 1.1主要目标法 1.2分层序列法 1.3加权法 1.4理想点法 2.智能优化算法 遗传算法等… 例题实战：MATLAB中多目标遗
日期 2023-06-12 10:48:40
数学建模暑期集训4：线性规划&整数规划&01规划（Lingo求解）
线性规划问题比较简单，初高中就学过。 列一堆方程式，然后通过Lingo求解。 Lingo语法不难，看看案例就可以。 这里看到一篇写得不错的文章，特此放置链接ÿ
日期 2023-06-12 10:48:40【 【henuacm2016级暑期训练】动态规划专题 P】Animals
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 第i只动物如果饲养它的话。 代价是固定的就是(n-i+1)*a[i] 所以相当于给你n个物品,每个物品的重量为(n-i+1)*a[i],价值为1 背包容量为x 问你最大价值是多少。 但因为价值是单位价值。 所以直接重量小的优先选就好了。 不够了就停止。 【代码】 #include <bits/stdc+
日期 2023-06-12 10:48:40【【henuacm2016级暑期训练】动态规划专题 O】Robot Rapping Results Report
【链接】 我是链接,点我呀:) 【题意】 让你确定一个最小的k 使得1..k这些比赛的结果能够推导出所有人之间的实力大小 【题解】 如果关系越多。那么就越能确定所有人之间的大小关系。 (多一点也能唯一确定。不嫌多 那么就二分一下k. 做一个拓扑排序。 如果能做唯一的拓扑排序。那么就ok 否则返回false. 【代码】 #include <bits/stdc++.h>
日期 2023-06-12 10:48:40
【【henuacm2016级暑期训练】动态规划专题 N】Valid Sets
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 给你一棵树。 让你统计其中子树T的数量。 这个子树T要满足最大值和最小值之差小于等于d 树形DP 可以枚举点root为子树的根。 统计以root为根的子树的个数。 根据每个儿子节点选或者不选。 如果选。则看看它是否满足以下条件: 权值小于等于根节点的权值。 (等于根节点的时候,要求该节点的标号<根节点的标号
日期 2023-06-12 10:48:40
【【henuacm2016级暑期训练】动态规划专题 M】Little Pony and Harmony Chest
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 每一位显然只要取1..60这些数字。 然后需要保证每个这些数字里面,每个数字所用到的质因子都它所唯一拥有的。别人不能用 因为如果别人用了的话。gcd就不为1了。 因此我们肯定需要记录这些数字的质因子使用情况。 如果第i个位置枚举的数字,它里面的某个质因子,之前用过了。那么这个数字就不能用。 否则还可以用。 只需取
日期 2023-06-12 10:48:40
【【henuacm2016级暑期训练】动态规划专题 L】Civilization
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 给一个森林。 就是由很多棵树组成。。 然后会询问你其中一棵树的最长链。 初始状态的最长链可以用两遍dfs分别找最长路得到。 然后要求你支持合并。 且合并过后。 新的树的最长链尽可能短。 这个合并的过程可以用并查集来表示。 给并查集添加一个变量value 表示这个并查集形成的树的最长链。 两个树合并。 最优的方法就
日期 2023-06-12 10:48:40【 【henuacm2016级暑期训练】动态规划专题 K】 Really Big Numbers
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 会发现如果x是reallynumber那么x+1也会是reallynumber.... (个位数+1,各位数的和+1了但是整个数也+1了。而且如果发生了进位的话,各个数码的和只会更小。。 因此这个reallynumber肯定有一个下界的。。 二分得到这个下界就好。 然后用n-下界+1就是答案了。 【代码】 #
日期 2023-06-12 10:48:40【【henuacm2016级暑期训练】动态规划专题 J】Red-Green Towers
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 显然最多1000行的样子。 从上到小做dp 设f[i][j]为前i行,使用了j个红色方块的方案数。 f[1][r] = 1;如果r>0且g>0则f[1][r-1]=1; 然后如果第i+1行不用红色的话。->就只能用绿色了。。 算算绿色够不够填i+1个。。 够得话 f[i+1][j] = f[i+
日期 2023-06-12 10:48:40【【henuacm2016级暑期训练】动态规划专题 I】Gargari and Permutations
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 注意这k个序列每个都是排列。 如果在每个序列中都满足y出现在x之后的话。 那么我们从x连一条有向边至y (有一个序列不满足就不连 (这就表明最后的序列中x可以紧接着y 最后显然会形成一个有向无环图。 在这个图上求最长链就好了。 可以在做拓扑排序的时候边做这个dp. 【代码】 #include <bits
日期 2023-06-12 10:48:40【【henuacm2016级暑期训练】动态规划专题 H】Greenhouse Effect
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 原题意等价于:给你一个序列(实数的位置没用!)。。你可以改变其中某些元素的位置(插入到某些位置中间。 然后让他变成有序的。 (有序的话,相同的数字就连在一起了 那么求出原序列的一个最长上升子序列。 把除了这个子序列之外的数字再分别插入到这个最长上升序列中就可以变成升序了。 这样是执行插入次数最少的做法。 答案就是
日期 2023-06-12 10:48:40【 【henuacm2016级暑期训练】动态规划专题 G】 Palindrome pairs
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 先用枚举回文串中点的方法。 得到这个字符串中出现的所有的回文。 得到他们的左端点以及右端点。 整理成一个pair数组 然后排序。 对于每一个回文串。 查找起点比这个回文串的终点大的所有回文串的个数。 【代码】 #include <bits/stdc++.h> #define LL long lon
日期 2023-06-12 10:48:40【【henuacm2016级暑期训练】动态规划专题 F】Physics Practical
【链接】 我是链接,点我呀:) 【题意】 给你n个数字 让你删掉最小的数字 使得: 剩余的数字中 "最大的数字"小于等于"最小的数字*2" 【题解】 把数据从小到大排序。 显然只有删掉最小的数字或者最大的数字才可能改变最大数字和最小数字的比例 那么我们枚举最后的结果产生的那一刻最小的数字是什么。 设为x 则在数组中找到最大的一个位置i且a[i]<=2*x 则我们只需要把比x
日期 2023-06-12 10:48:40【【henuacm2016级暑期训练】动态规划专题 E】Destroying Roads
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 首先。 这张图是无向无权图。 因此任意两点之间的最短路可以通过N^2的bfs轻易算出来。 即得到d[N+10][N+10] 考虑s[0]->t[0]的最短路以及s[1]->t[1]的最短路 如果d[s0][t0]>l0或d[s1][t1]>l1那么直接输出无解 假设他们俩的最短路之间没有重
日期 2023-06-12 10:48:40【【henuacm2016级暑期训练】动态规划专题 D】Writing Code
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 二维费用背包。 f[i][j][k] 前i个人,写了j行,bug不超过k的方案数。 可以把每个人看成是一个物品。 它可以无限拿。然后花费为 1行代码和a[i]个bug (拿几个第i个人就相当于v[i]等于几. 就变成一个二维的完全背包了 直接用二维费
日期 2023-06-12 10:48:40【henuacm2016级暑期训练-动态规划专题 C】Little Girl and Maximum XOR
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 考虑r最后的二进制形式为 1xxxxx 那么我们肯定想让第一个最高位的1保留。 因此我们选取的另外一个数字 一定是 0xxxxx的形式。 那么我们贪心地选取数字b=01111..1 然后看看这个数字b是否大于等于L 如果满足,显然它也是满足小于等于R的。 那么我们选取的a=100000..0 那么结果显然就是最大
日期 2023-06-12 10:48:40【henuacm2016级暑期训练-动态规划专题 B】Coloring Trees
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 f[i][j][k]前i个位置,第i个位置放j这个颜色,然后形成了k个联通块的最小花费 分第i个位置有没有已经放颜色两种情况考虑。 如果有放的话。枚举前一个位置的颜色以及前i-1个位置形成的联通块的数目 如果没有放的话。枚举当前以及前一个的颜色以及前i-1个位置形成的联通块数目 有放不用加代价。 没有放的话加上放
日期 2023-06-12 10:48:40【 henuacm2016级暑期训练-动态规划专题 A 】Cards
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 很显然只要维护B,R,G的数量就好了。 可以很容易想到一个dfs(int a,int b,int c) 然后如果a+b+c==1,那么让其中为1的对应的颜色标记为可以得到就好 变换就是a-1,b-1,c+1和a-1,c-1,b+1以及b--,c--,a++以及a-1,b,c和a,b-1,c和a,b,c-1 然后加
日期 2023-06-12 10:48:40