ACGO欢乐赛#23 官方题解 T1、ASCII 值奇偶判断 T2、数字出现的次数 T3、ZXC的加法验证 T4、删除重复的字符 T5、ZXC画图形 T6、Echo T7、ZXC编织图形 T8、换座位

窒 suffocating poor early grave - Audiomachine Someone's behind you - Bonesaw577 dead inside Ginshin impact start Judgment Day star eater fainted Priest fake Teeth Rosable experience show me your back NEON BLADE 70K time to pretend x memory reboot Z com falls alarm boys noize dans LA maison Graveyard Phonk dusk till down badboy giga Chad phonk underground aftermath cornfield chase the best of me white lines anatomy unwelcome school move your body drama murder in my mind in the end 听完打开新世界大门

哈哈被我抢到AC力

太难了！ <a href="bilibili.com"></a>

背包入门\COLOR{ORANGE}{\TEXTBF{背包}}\COLOR{SKYBLUE}{入门}背包入门 > C++ 中的 0/10/10/1 背包和完全完全完全背包问题。这两个问题都是经典的动态规划问题，涉及到如何在给定背包容量和物品重量、价值的情况下，选择最优的物品放入背包以获得最大的总价值。 0/1背包问题\COLOR{BLUE}{0}/\COLOR{RED}{1} \COLOR{ORANGE}{\TEXTBF{背包问题}}0/1背包问题 问题描述 0/1背包问题\color{blue}{0}/\color{red}{1} \color{orange}{\textbf{背包问题}}0/1背包问题是一个经典的动态规划问题，指的是有 n 个物品和一个容量为 W 的背包，每个物品只能选择装入一次或不装入。目标是在不超过背包容量的前提下，选择物品使得背包中物品的总价值最大。 解法思路 1. 定义数组元素含义： 我们定义一个二维数组 dp[i][j]，表示在前 i 个物品中任取物品，放进容量为 j 的背包中，背包所能装的最大价值。 2. 递推关系式： 对于每个物品 i，有两种选择：放入背包或不放入背包。因此递推公式如下： * 不放第 i 个物品：dp[i][j] = dp[i-1][j] * 放第 i 个物品：dp[i][j] = dp[i-1][j-w[i]] + v[i] * 最终结果：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) 3. 初始化： 初始化第一行和第一列为 0。 4. 填表格： 根据递推公式填充整个二维数组。 5. 求解最终结果： 最终结果为 dp[n][W]，其中 n 是物品数量，W 是背包容量。 代码实现 以下是 C++ 中 0/1背包问题\color{blue}{0}/\color{red}{1} \color{orange}{\textbf{背包问题}}0/1背包问题的代码示例： 完全背包问题\COLOR{PURPLE}{\TEXTBF{完全}} \COLOR{ORANGE}{\TEXTBF{背包问题}}完全背包问题 问题描述 完全背包问题与 0/1背包问题\color{blue}{0}/\color{red}{1} \color{orange}{\textbf{背包问题}}0/1背包问题类似，但不同之处在于每种物品的数量是无限\textbf{无限}无限的。也就是说，每个物品可以选择装入多次。 解法思路 1. 定义数组元素含义： 我们仍然定义一个一维数组 dp[j]，表示在前 i 个物品中任取物品，放进容量为 j 的背包中，背包所能装的最大价值。 2. 递推关系式： 对于每个物品 i，有两种选择：放入背包或不放入背包。因此递推公式如下： * 不放第 i 个物品：dp[j] = dp[j] * 放第 i 个物品：dp[j] = max(dp[j], dp[j-w[i]] + v[i]) 3. 初始化： 初始化一维数组 dp[j] 为 0。 4. 填表格： 从前向后遍历背包容量，根据递推公式更新 dp[j]。 5. 求解最终结果： 最终结果为 dp[W]，其中 W 是背包容量。 代码实现 以下是 C++ 中完全背包问题\color{purple}{\textbf{完全}} \color{orange}{\textbf{背包问题}}完全背包问题的代码示例： 这段代码中，我们使用了一维数组 dp[j] 来记录背包容量为 j 时的最大价值。通过遍历物品和背包容量，不断更新 dp[j] 的值，最终得到完全背包问题\color{purple}{\textbf{完全}} \color{orange}{\textbf{背包问题}}完全背包问题的最优解。

背包入门 0/1背包模型 有一个容量V的背包，在K个物品中选择一些物品装入，每个物品只有装/不装两个状态， 怎样能保证所撰的物品价值最大； 思路 设dp[i][j]表示前i个物品已经选好了最佳方案，且容量不超j，所能获取的最大值 对于第i个物品 选择不装，则的dp[i][j]=dp[i-1][j] (不装不影响所装的价值) 选择装，则dp[i][j]=dp[i-1][j-v[i]]+w[i];（拿一个物品，占用对应空间，加上对应价值） 所以两者取最大 dp[i][j]=max(dp[i][j]=dp[i-1][j],dp[i-1][j-v[i]]+w[i]); 初始化dp[0][V]=0; 答案：dp[K][V]; 无限背包模型 有个容量为V的背包，在K个物品中选择物品放入。 每个物品有一定价值，占用一定空间，且可以无限装入； 怎样在能保证在背包装满之前保证装的物品价值最大。 思路 设dp[i][j]

0-1背包 完全背包

DP-背包 题！ 优化！ 在优 一个dp，一个滚动数组，一个压缩维度，9，因为6翻了

#背包 0/1背包 容量为V的背包 需要在k个物品中选取并装入 只有装/不装两种状态 v[i] w[i] dp[i][j] 求解dp[i][j] 必然已求得dp[1i-1][1j-1] 不装入：dp[i][j] = dp[i-1][j] 选择装入dp[i][j] = dp[i-1][j-v[i]]+w[i]; 初始化：dp[0][0~v] = 0; 答案:dp[k][v] 滚动数组优化 压成一维 #无限背包 容量为V的背包 需要在k个物品中选取并装入 每种物品可以选取任意个数 每个物品占用空间v[i],价值w[i]; 不装入 dp[i][j] = dp[i-1][j] 装入 dp[i][j] = dp[i][j-v[i]]+w[i]; j的循环从小到大 一个int4个字节 32位一个int

背包 01背包 设 dp[i][j] 表示在前 i 个物品中已经选好了最佳方案，并且容量不超过 j 时，所能获取的最大价值。 （对于任意一个 dp[i][j] ，已知 dp[1 ~ i - 1][1 ~ j - 1]） 对于 i 物品，如果选择不装入，则有 dp[i][j] = dp[i - 1][j]。 如果选择装入，则有 dp[i][j] = dp[i - 1][j - v[i]] + w[i]。 两者取最大，则有 dp[i][j] = max(dp[i - 1][j], dp[i][j] = dp[i - 1][j - v[i]] + w[i])。 初始化 dp[0][0 ~ V] = 0，答案为 dp[T][V]。 例题： P1048 [NOIP2005 普及组] 采药 AC 完全背包 状态设计同 01 背包 对于 i 物品，如果选择不装入，则有 dp[i][j] = dp[i - 1][j]。 如果选择装入，则有 dp[i][j] = dp[i][j - v[i]] + w[i]。 两者取最大，则有 dp[i][j] = max(dp[i - 1][j], dp[i][j] = dp[i][j - v[i]] + w[i])。 初始化 dp[0][0 ~ V] = 0，答案为 dp[T][V]。 例题： P1616 疯狂的采药 AC（滚动数组优化） AC（一维优化） 优化 滚动数组优化 对于状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i][j] = dp[i - 1][j - v[i]] + w[i])。 可以发现只会使用到 dp[i] 和 dp[i - 1]。 即可以将 dp[MAXM][MAXN] 优化为 dp[2][MAXN]。 一维 对于上述滚动数组优化，可以注意到 dp[now][j] 的影响因素只有 dp[last][j] 和 dp[last][j - v[i]] + w[i]。 所以只要更改 j 的枚举方向，便可以再次优化一维。

动态规划 其思想与分治法类似，是将待求解问题分为若干个小问题 通过局部最优求出全局最优 动态规划类问题主要的求解步骤： 1. 划分阶段 斐波那契数列的每一项作为一个阶段 2. 确定状态 第iii项的值用第iii位表示a[i]a[i]a[i] 3. 确定决策并写出状态转移方程式 每一项的值都是前两项的和a[i]=a[i−1]+a[i+2]a[i] = a[i - 1] + a[i + 2]a[i]=a[i−1]+a[i+2] 结尾法：dp[i]dp[i]dp[i]就表示以下标iii结尾的答案 性质 1. 最优化原理：（最优子结构） * 如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理 2. 无后效性： * 即某一阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。 3. 子问题重叠： * 即子问题之间是不独立的，一个子问题在下一阶段决策中可能多次被使用到。（该性质并不知动态规划适用的必要条件，但是如果没有这条性质，动态规划算法问题同其他算法相比就不具备优势） 前缀法 dp[i]dp[i]dp[i] 表示 1 i1~i1 i 处理完毕的结果，dp[n]dp[n]dp[n] 就是答案 有向无环图 背包 0/1背包 想象一个容量为VVV的背包，你需要在KKK个物品中选择一些物品转入，每个物品只有装/不装两个状态，并且每个物品占用空间为viv_ivi ，价值为wiw_iwi ，求不超过容量VVV能装进物品的最大价值 我们设dp[i][j]dp[i][j]dp[i][j]表示在前iii个物品中已经选好了最佳方案，并且容量不超过jjj时，所能获取的最大值 对于iii物品，如果选择不装入，则有dp[i][j]=dp[i−1][j]dp[i][j]=dp[i - 1][j]dp[i][j]=dp[i−1][j]（继承之前的状态） 如歌选择装入，则有dp[i][j]=dp[i−1][j−v[i]]+w[i]dp[i][j]=dp[i - 1][j - v[i]] + w[i]dp[i][j]=dp[i−1][j−v[i]]+w[i]（表示拿这个物品，占用对应背包空间，并且获取对应价值） 两者取最大，则有dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i])dp[i][j]=max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]]+w[i]) 滚动数组 压缩为1维 无限背包 想象一个容量为VVV的背包，你需要在KKK个物品中选择一些物品转入，每个物品可以任意选个数，并且每个物品占用空间为viv_ivi ，价值为wiw_iwi ，求不超过容量VVV能装进物品的最大价值 我们设dp[i][j]dp[i][j]dp[i][j]表示在前iii个物品中已经选好了最佳方案，并且容量不超过jjj时，所能获取的最大值 对于iii物品，如果选择不装入，则有dp[i][j]=dp[i−1][j]dp[i][j]=dp[i - 1][j]dp[i][j]=dp[i−1][j]（继承之前的状态） 如歌选择装入，则有dp[i][j]=dp[i][j−v[i]]+w[i]dp[i][j]=dp[i][j - v[i]] + w[i]dp[i][j]=dp[i][j−v[i]]+w[i]（表示拿这个物品，占用对应背包空间，并且获取对应价值） 两者取最大，则有dp[i][j]=max(dp[i−1][j],dp[i][j−v[i]]+w[i])dp[i][j]=max(dp[i - 1][j], dp[i][j - v[i]] + w[i])dp[i][j]=max(dp[i−1][j],dp[i][j−v[i]]+w[i])（注意j的循环一定要从小到大） 一维 任务 1. 完成题目时间 黄题20min 绿题40min 蓝题100min 2. 手搓3组数据 3. 每次提交WA之后 记录WA的原因

666

背包问题 0/1背包模型 有一个容量为VVV的背包，在kkk个物品中选择一些物品装入 每一个物品有一定的价值，同时占用一定的空间 问如何选取才能保证在背包装满之前使物品总价值最大 求解思路 用v存储各个物品的占用空间，w存储各个物品的价值 设dp[i][j]表示在前i个物品中容量不超过j时的最大价值 对于dp[i][j]的求解方式： 有两种选择：装或不装 要是不装，则有dp[i][j]=dp[i-1][j]（继承之前的状态） 要是装，则有dp[i][j]=dp[i-1][j-v[i]]+w[i]（表示用这个物品占用对应的空间，并取得相应的价值） 二者取最大，则可推出状态转移方程式为： dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]) 初始化：全部初始化为0即可 答案：dp[k][V] 另提一嘴：滚动数组优化 一种空间优化策略 观察可得，状态转移方程式只需要用到上一行 所以不妨用两行数组交替求解 代码如下： 还没完！降维打击听说过没？ 直接用一维数组解决二维！ 关键在于从右向左滚，此时左边是last，右边是now 答案是dp[t] 无限/完全背包模型 有一个容量为VVV的背包，在kkk个物品中选择一些物品装入 每一个物品有一定的价值，同时占用一定的空间，且可以任意选取数量 问如何选取才能保证在背包装满之前使物品总价值最大 求解思路 用v存储各个物品的占用空间，w存储各个物品的价值 设dp[i][j]表示在前i个物品中容量不超过j时的最大价值 对于dp[i][j]的求解方式： 有两种选择：装或不装 要是不装，则有dp[i][j]=dp[i-1][j]（继承之前的状态） 要是装，则有dp[i][j]=dp[i][j-v[i]]+w[i]（表示用这个物品占用对应的空间，并取得相应的价值） 二者取最大，则可推出状态转移方程式为： dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]) 初始化：全部初始化为0即可 答案：dp[k][V] 区别：是dp[i]不是dp[i-1]啊！ 滚动数组优化代码 两行： 单行：从左往右滚就行

#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } char s1[60],s2[60],s3[60]; int dp[100],l1,l2,l3; int x,y,num = 0; int ans1,ans2,ans3,ans; int main() { read(l1); scanf("%s",s1); read(l2); scanf("%s",s2); read(l3); scanf("%s",s3); duke(i,0,min(l1,l2) - 1) { if(s1[i] == s2[i]) ans1++; else break; } duke(i,0,min(l1,l3) - 1) { if(s1[i] == s3[i]) ans2++; else break; } duke(i,0,min(l2,l3) - 1) { if(s2[i] == s3[i]) ans3++; else break; } if(ans1 >= max(ans2,ans3)) { num = (l1 + l2 - 2 * ans1); num += (l3 + ans1 - ans2 * 2); } else if(ans2 >= max(ans1,ans3)) { num = (l1 + l3 - 2 * ans2); // cout<<ans2<<endl; num += (l2 + ans2 - ans3 * 2); } else { num = (l2 + l3 - 2 * ans3); num += (l1 + ans3 - ans1 * 2); } printf("%d",num); return 0; }

rt

公元2070年，人类在火星上建造的数个太空基地，人类开始了太空生活。公元2073年，人类的太空基地间出现了大量的时空隧道。时空隧道可以看作是一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对于你进入时空隧道之前）。（从1到N标号）个太空基地由M条小路连接着，并有W个时空隧道。 现在小码君想要借助这些时空隧道回到过去，请你告诉他能办到吗？没有小路会耗费小码君超过104秒的时间，当然也没有时空隧道可以帮你回到104秒之前。 提示 1 ≤ M, W ≤ 500 用时T不超过1e9 输入格式 第一行，三个整数 N,M,W（N，M<500）； 接下来M行，每行三个数S,E,T,表示在标号为S的地与标号为E的太空基地中间有一条用时T秒的道路； 接下来W行，每行三个数S,E,T,表示在标号为S的地与标号为E的地中间有一条可以使 John 到达T秒前的时空隧道。 输出格式 如果小码君能实现他的目标，就输出YES，否则输出NO。 样例组输入#1 3 3 1 1 2 2 1 3 4 2 3 1 3 1 3 样例组输出#1 NO 样例组输入#2 3 2 1 1 2 3 2 3 4 3 1 8 样例组输出#2 YES

最短路算法 单源最短路算法 一个起点到达其他所有顶点的 最短距离 多源最短路算法 任意两点之间的最短距离 DIJKSTRA 单源最短路算法 缺点:假如出现负权值的边，那么就无法求得正确的答案。 核心思想:贪心原则，从起点出发，优先选择距离起点最近的顶点来作为下一个松弛的顶点，最终松弛完所有顶点。 松弛:某个顶点作为中转站，使得起点到达这个点相邻顶点的距离变得更短。 DIJ基本代码框架 BELLMANFORD 单源最短路算法 时间复杂度为O(N∗M)O(N*M)O(N∗M) **缺点:**他会对每一个顶点进行M−1M-1M−1的松弛操作，因此时间消耗巨大。 **优点:**能够处理负数 策略: 按照路径步数来进行遍历，类似于广搜，他会先去遍历第一步能够到达的所有边，以第一步到达的所有边的终点作为松弛的顶点，开始遍历第二步都能到达的所有边，重复一直遍历，每当遍历的时候产生最短路径的数值变化后，继续遍历。 终止条件: 当再一次从头遍历完所有顶点之后，没有任何顶点的最短距离发生变化后，那么才会停止。 PS: 我们可以保证，在N∗MN*MN∗M次遍历之前，一定可以得到不会发生变化的最短距离数组。 核心思想:枚举所有情况，堪称单源最短路的floyd

#include<bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; int s[105]; for(int i=1;i<=n;i++){ cin>>s[i]; } int c,num=0; for(int i=1;i<=m;i++){ cin>>c; int g=0; for(int j=2;j<s[c];j++){ if(s[c]%j0){ g=1; } } if(g0){ num+=s[c]; } } cout<<num; return 0; }