Sum of Paths CodeForces - 1467DTagscombinatorics dp math *2200 题意： 定义一条好的路径，当且仅当从任意点出发之后恰好经过了 k 次移动，定义这条路径的权值为经过点权值的总和(可重)，进行 q 次修改，每次将ak 改为 x ,询问此时所有‘好’路径的权值总和.例如样例： 5 1 5 3 5 1 4 2 1 9 2 4 3 6 4 6 5 2 将第一位换成9就成了9 5 1 4 2 ，对应的答案就是62 题解： dp动态规划根据题目，我们要计算每个格子的贡献，设dp[i][j]表示走了j步当前在i点的路径总数i点可能是从i-1来的也可...

题意： 三堆石子，你可以取两堆石子各一个石头a,b。然后消掉a，使得b=b-a再放入b的那一堆。这样操作直到只剩下一个石子，求该石子价值最大。 题解： 构造题可以构造出两者情况： 其中两堆都是正的，一堆都是负的 一个背包都是正的，另两个背包的最小值是负的，其他都是正的为什么是这样构造出来的呢？参考题解对于一个数如果进行奇数次操作，那么就是负贡献，偶数次操作就是正贡献假设最后一个数在数组a，那么a中剩下n-1个数，可以在最后先与其他数组合并，再和最后一个数合并，这样就都是正贡献。同理应用到b和c数组，就相当于b，c中只有一个数的负贡献，其他都是正，我们取b，c中最小的为负贡献或者我们直接选b，...

Hills And Valleys CodeForces - 1467B 题意： 修改数列中的 一个 数字 使得峰(波峰、波谷)的数量最少 题解： 修改一个数，最多只能影响左右两个数，所能减少的峰的数量为1,2，3三种分类讨论，对于当前位置i，如果我们将a[i]变成比左右两边都小的情况，比左右两边都大的情况，位于两者中间的情况，等于左边的情况，等于右边的情况，以上所有情况均取最大的到temp然后用总数量减去temp 代码: #include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 10; #define...

Wizard of Orz CodeForces - 1467A 题意： 有个长度为n初始状态下各元素均为0的数组，没过一秒数组中所有元素都会+1，如果是9则会变成0，即0-9不断循环。现在你能够在开始后的任意时间点选取任意一个位置，改位置上的数字立刻停止增加，与其距离为x的位置上的元素则在x秒后暂停（这x秒内还是数字会继续增加）。给定你长度n，求出由n个元素构成的最大数字（包含前导零） 题解： 规律题，通过找规律不难发现前三位是989，从第四位开始就是0~9的循环 代码： #include<bits/stdc++.h> typedef long long ll; using n...

Codeforces Round #696@[toc] CF1474A Puzzle From the Future 题意： 在2022年，Mike发现了两个长度为n的二进制整数a和b(它们都只由前导有0的数字(和1)表示)。为了不忘记它们，他想用以下方式构造整数d: 他将a和b按位加和而不进行进位转换，从而得到一个整数c，所以c可能有一个或多个2。例如，0110和1101按位求和的结果是1211，011000和011000按位加和的结果是022000；之后，Mike将c中相等的连续数字折叠为1位，因此得到d。经过这个操作，1211变成121,022000变成020(所以，d不会有相等的连续数...

Codeforces Round #695 (Div. 2) 1467A Wizard of Orz1467B Hills And Valleys1467C Three Bags1467D Sum of Paths1467E Distinctive Roots in a Tree1468A LaIS Codeforces Round #696 (Div. 2) 1474A Puzzle From the Future1474B Different Divisors1474C Array Destruction1474D Cleani...

CF613D Kingdom and its Cities 题目： 给定一棵有n 个节点的树，树上有一些关键点(key)。接下来有q组询问，每次给出ki 个key，要求删去一些点，使得这些key不相连。要求删去的最少的点数。 1<=n<=100000 1<=q<=100000 The sum of all ki 's does't exceed 100000 题解： 这篇文章讲的很详细第一反应肯定是树形dp，但是如果每个q都要跑一次完整的树，很俨然O(n * q)肯定会超时，所以肯定要用到虚树虚树题目的一般套路，先不考虑超时写出树上dp转移方程，然后根据题意构建虚树，多...

Infinite Tree 题意： 题解： 参考博客看了好一阵子才明白。。。emm。我们先按照题意画出一部分树我们先不考虑复杂度，这题应该怎么做？题目给了每个点的权值w[i]，问一个点到所有的节点路径长度*点权之和最小是多少，很明显是树形dpdp[i]表示以i为根的子树到i的w和sum[i]表示乘上距离之后的答案dep[i]表示深度，now为当前节点，son为子节点则有： dp[now]= w[now] sum[now]=0 dp[now]+=dp[son] sum[now]+=sum[son]+(dep[son]-dep[now])*sum[son] 但是以now为根并不一定是最佳答案，所...

题号 题目 通过率 A Permutation 1234/3361 B KMP Algorit***> 23/84 C Decrement on the Tree 288/735 D Hearthstone Battlegrounds 197/805 E Game 1110/2816 F Parenthesis sequence 4/63 G Math Test 22/159 H Heyawake 2/1333 I Tournament 324/1838 J Identical Trees 460/2154

题号 题目 通过率 A Groundhog and 2-Power Representation 1282/1950 B Groundhog and Apple Tree 399/2305 C Groundhog and Gaming Time 80/211 D Groundhog and Golden Apple 25/100 E Groundhog Chasing Death 825/3719 F Groundhog Looking Dowdy 1203/3162 G Groundhog Playing Scissors 32/297 H Groundho...

题号 题目 通过率 A All-Star Game 209/726 B Bon Voyage 7/22 C Cinema 28/245 D Disgusting Relationship 10/25 E Enigmatic Partition 353/930 F Factorio 4/41 G Game SET 758/2192 H Hard String Problem 88/533 I Interesting Computer Game 1336/7991 J Jumping Points 9/66 K Kabaleo Lite 1204/66...

题号 题目 通过率 A Social Distancing 244/1518 B Mask Allocation 1084/3218 C A National Pandemic 541/2666 D Fake News 1400/3995 E NeoMole Synthesis 5/27 F Tokens on the Tree 24/49 G Topo Counting 62/100 H Dividing 1147/5328 I Valuable Forests 199/345 J Pointer Analysis 339/1342

题号 题目 通过率 A African Sort 103/167 B Binary Vector 1006/2386 C Combination of Physics and Maths 1307/4017 D Data structure 47/300 E Easy Construction 1315/3574 F Fibonacci Partition 9/27 G Grid Coloring 610/2832 H Harmony Pairs 579/1116 I Interesting Stiriling 13/74 J Josephus Tra...

题号 题目 通过率 A Portal 325/770 B Graph 675/2240 C Easy 179/307 D Drop Voicing 940/2109 E Bogo Sort 1154/5052 F DPS 1413/3687 G Greetings Souvenir 40/364 H Interval 230/790 I Hard Math Problem 1210/4750 J Cone walker 14/54 K Git Merge 38/320