这个暑假跟着灵神（0x3f）做每日一题，一周的周一到周五下午三点是有每日一题的，大概是cf上面1700或者1800难度，这周因为最近力扣出一些dp题目，灵神在cf上也找了一些比较相似的写。在我之前的博客文章中也有很多出自灵神的每日一题里面。 CF166E. Tetrahedron (1500) 题意 题目链接：Problem - 166E - Codeforces 给你一个$n(1\leq n\leq 10^7)$，你一开始在顶点$D$上，你需要去走$n$步并且回到$D$点，求这样的方案数是多少（对mod取模）。 …
题意 给你一个字符串$s$，有$q$次询问，每次询问格式有两种： 1) 1 pos c：将字符串中位置为pos的字符改为c 2） 2 x y：询问区间$[x,y]$中有多少个不一样的字符 数据范围： $|s|\leq 10^5,q\leq 10^5$ 思路 我是先会做了另外一道线段树的题（线段树-单点修改+区间求最大连续子段和 - CarryNotKarry）才会秒这个题的。 这个题很明显是单点修改，然后区间查询，这里设置一个结构体，有普通的存当前结点的l,r以及如果是叶子节点的字符ch，也存上一个num[26]数…
题意 题目链接：Problem - C - Codeforces 题意：给你一个$n(n\leq 100)$，以及$2n-2$个字符串，包括了不含本身的所有前缀和后缀，例如carry则有： c ca car carr y ry rry arry 请按照原来顺序输出字符串是前缀('P')还是后缀('S')，如果有多种符合的，输出任意一种，但是如果相同长度，哪怕都相等，例如都为'a'和'a'，也只能存在一个前缀一个后缀。 思路 这个题wa麻了，主要难点在于 - 相同长度二者必须不同，一个为P一个为S。 - 如何求出这个…
题意 题目链接：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)$…
写在前面 比赛链接：Dashboard - Codeforces Round #803 (Div. 2) - Codeforces 这场是手速场，提前回寝室睡觉，然后起床打比赛状态贼好，一开始本来打算放弃D的，但是突然有了灵感！ 小号加了121分，准备先把小号打上蓝，然后不分大小号了，每次拿分最低的打。 A. XOR Mixup（位运算） 题意 给你一个长度为n的数组，告诉你其中有一个数字是由其他三个异或构成的，问你是哪一个被其他构成。例如： 4 4 3 2 5 这样来看4 xor 2 xor 5 = 3，所以输出…
题意 题目链接：Problem - 1042C - Codeforces 给你一个长度为n的数组a，你需要进行n-1个操作，使得最后的值最大： - 1 i j 表示将$a_i$删除，$a_i\times a_j$重新赋值给$a_j$ - 2 i 将$a_i$删除 （最多只能用一次） 例如样例，只需要将0删除，其他进行1操作，任意符合操作的都可以。 思路 这种题做多了，首先想到如果有-1,-2,-3的时候，什么时候要删，要删什么？ 首先需要判断负数的个数，例如是-2,-3那么就不需要删除了，因为负负得正。 然后如果要…
题意 题目链接：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]：不能…
题意 题目链接：Problem - E - Codeforces 给你一个长度为n的数组a，每个元素都可以+1或者-1，但只能一次。问最后不同元素的最小值和最大值分别是多少。例如： 7 4 3 7 1 4 3 3 嗯，我先sort一下，这样好看，变成: 7 1 3 3 3 4 4 7 然后通过操作可以变成 2 4 4 4 4 4 8 ->3 1 2 3 4 5 5 6 ->6 思路 看我构造的已经能够看出来了，分为两种情况 1）最小值 最小值可以看出，每次如果能与前面够着（指操作能够相等）那么就尽量去够，比如i=3…
题意 题目链接：Problem - A - Codeforces 给出一个$n$，需要构造一个长度为$n$的数组，然后又$m$个区间$\lbrack l_i,r_i\rbrack$，要满足这若干个区间中最小值最大，并且输出这个值。 数据范围$1\leq n,m\leq 10^5$。 5 3 1 3 2 5 4 5 可以构造出$a=\lbrace 1,0,2,1,0\rbrace$，在三个区间的mex分别是$3,3,2$，所以输出是$2$以及这个a数组。 思路 可以贪心构造出，我们需要的值就是区间长度的最小值$ans…
写在前面 这回刚忙完UML大家一起打cf，才有紧张感，确实那时候有点紧张，打了几个嗝，然后这回是第一次打div4（之前那场太久远了），目标就是冲着AK去的，并且也需要手速。出题当然还算可以，ak了，但是有些题目实在是做得慢hhh。 不过最近水平确实越来越有突破了，最近补了ABC的F，还有div3AK，这回现场AKdiv4，感觉越来越好起来了，虽然是ak，但是时间也没有落下，还是跟上了大部队（脱老师，易老师，龙老师），可惜龙龙最后的F爆int挂了，最后榜单出来了我还往前走了几十名。希望自己下次再接再厉，多多补题！ 比…
