题目链接：ABC262D 题意： 给出$n$个正整数，选出若干个数字，求这若干个数字的平均值是正整数的方案数，答案对998244353取模。 思路： 一开始想着的是dp[i][j][k]表示前i个数选择j个数其中和为k的方案数。 k会很大，所以需要考虑取模，存储和对j取模。 不选a[i]的转移方程有dp[i][j][k] = dp[i-1][j][k]，但是如果选a[i]的时候有些难办，现在sum=k那上一个状态如何得来？(sum-a[i])%(j-1)=?这个不好办。所以这个$O(n^3)$方法不太行。 定义dp…
又是迟到的一篇，这场是教主说第三场之后要加大难度的第一场只过了三体...有时间补一下其他的吧，先把做的三题写了。 比赛链接：2022“杭电杯”中国大学生算法设计超级联赛（3） 1003.Cyber Language（签到） 题意：给出一行字符串（包括空格），输出每个单词的第一个字母的大写字母 思路：我是getline()读入一行，然后添加一个' '，然后输出，实际上可以用到stringstream，第二次见这个，具体该题用法如下： 代码： inline void Case_Test() { string in; g…
鸽了好久，最近几天多校，今天才抽出时间来补这场总结，还有一场cfdiv2没补总结呢，如果今晚不打edu的话就有两场div2还有一场abc堆积了... 比赛链接 第60场周赛 - AcWing 过题数：3/3 排名:30/1139 这场手速还算快（从排名来看），但是我觉得还是不够快hhh 过题数 罚时 A(1139) B(786) C(341) 3 0:23:40 0:00:52 0:08:12 0:14:36 又一次在1min内过题hhh，锻炼锻炼速度。 A-吃饭（签到） 超级简单的签到 inline void C…
2022“杭电杯”中国大学生算法设计超级联赛（1） 本场比赛最后压哨绝杀4:59:16过掉1002的搜索成功达到五题，最后成绩在164名，1002罚时太高（被某人演了）...总体来说还是比较满意的，打败了武地的所有队，在本校也排在前三，距离第四还多了三题。希望再接再厉，后天又有一场牛客！ 本场手速两题，前两题都是题目只有三十多个队时候出的，还比较快，小小纪念一下： 依旧是按照做题顺序来写的。 1011.Random（签到） 题意：给你$N$个数字，每个都是在$[0,1]$中随机，做$M$次操作，$\frac{1}{…
比赛链接：牛客小白月赛53 好久没有打小白月赛了，这回算半个四题首吧，E题怎么也写不出，代码又臭又长，结果是一个地方忽略掉了，第二天把F补了。经过上一次牛客练习赛，这回还是没有能升到1500...下次再来。 A.Raining（水题） B.Kissing 打表发现其实就是$1+3+...+2n-1$，根据等差数列公式$\frac{(1+2n-1)\times n}{2}=n^2$，注意取模 C.Missing 这里wa了一发，一味的求快导致没看清题目，如果一个匹配的也没有就全部按字典序输出即可 前三题都太简单了不详…
写在前面 这四题都很有分量，这是我第一次觉得力扣周赛原来这么有含金量，以后又要认真对待一场比赛了。后面三个题是真的好！ 比赛链接：第 300 场周赛 - 力扣（LeetCode） 2.螺旋矩阵 IV（模拟题/技巧） 题意 给一个头指针为head的链表，从左上角开始填写螺旋矩阵，如果没有填满则写-1. 思路 模拟题，但是这里有一个技巧是我以前从来没有用的，要我自己写我会写的很麻烦很麻烦，但是y总这个方法就很好。 用一个dx[],dy[]表示上下左右，用d=0,1,2,3表示dx[],dy[]的下标，每次判断如果越界，…
题意 题目链接：Problem - 1446B - Codeforces 前置知识——LCS（最长公共字串），给你两个字符串$A,B$，你需要分别在其中选择两个字串$C,D$，使得得分最大，得分计算如下： $$ 4\times LCS(C,D) - |C| - |D| $$ $LCS(C,D)$指的是字符串$C,D$最长公共子串的长度。数据范围$1\leq n,m\leq 5000$。 思路 一开始是没有思路的，看了题解才恍然大悟，对于得分可以这么理解: - 如果我在原有基础上，多匹配一个，那么$LCS(C,D)$…
题意 题目链接：Problem - D - Codeforces 给你一个字符串$s$，每个位置都有一个权值$a_i(1\leq n\leq 10^5)$，这个权值是删除代价，请问删除若干个字符最后没有"hard"字符的子序列的最小代价是多少？ 思路 看到子序列就要往DP方面想 这是一道DP题，首先定义一个二维数组dp[i][j]。表示是到第i个字符j状态的最小值。 - dp[i][1]：不能有h - dp[i][2]：不能有ha,可以有h - dp[i][3]：不能有har,可以有ha - dp[i][4]：不能…
写在前面 这是去年ICPC上海站，我们队伍获得铜尾的比赛，曹佬手撕三维DP怒秀我和郎队，现在来看，好像也没有那么难嘿嘿，可能是自己刷了一些DP题。 题意 题目链接：I-Steadily Growing Steam 给你一个$n$个物品，每个物品有$v,t$两个属性，$v$是值，$t$是点数，现在你需要从里面取出若干份分成两堆（也就是说有的可以不选），求两堆的点数相等的时候的两堆的值的最大值。嘿嘿，没这么简单，还有一个条件，你最多有$k$次操作，可以使其中一个点数翻倍，也就是说，有可能让其翻倍之后正好两堆相同，这个时…
