写在前面 这是去年ICPC上海站，我们队伍获得铜尾的比赛，曹佬手撕三维DP怒秀我和郎队，现在来看，好像也没有那么难嘿嘿，可能是自己刷了一些DP题。 题意 题目链接：I-Steadily Growing Steam 给你一个$n$个物品，每个物品有$v,t$两个属性，$v$是值，$t$是点数，现在你需要从里面取出若干份分成两堆（也就是说有的可以不选），求两堆的点数相等的时候的两堆的值的最大值。嘿嘿，没这么简单，还有一个条件，你最多有$k$次操作，可以使其中一个点数翻倍，也就是说，有可能让其翻倍之后正好两堆相同，这个时…
题意 给你一个$m$($m\in \lbrace 2^k | k=1,2,...,10\rbrace $)，你需要构造一个$m\times m$的矩阵，要求任意两行的内积为$0$，内积也叫点积：对于$a,b$有$a\cdot b=\sum _{i=1}^{n}a_ib_i=a_1b_1+a_2b_2+\cdots +a_nb_n$ 思路 构造，当$n=2$的时候，我们构造出 嗯，然后按照下面方法构造，我问大佬们为什么，感觉是对的，他们说“瞎**构造”就好 就是每个这样的小块往其他方向填： 每次递归，有一个$…
写在前面 这个题是去年打沈阳站我队没有做出来的题目，我觉得算铜牌题吧，当时要是做出来了我们就是铜牌了，差一点做到一赛季都是铜没有铁的“壮举”哈哈。 周日（4.24）的训练我还是避开了这个题，做别的题去了，可能是内心的恐惧吧，现在来赛后补题 题意 题目链接：J-Luggage Lock_第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（沈阳） (nowcoder.com) 给你两个由'0'...'9'组成的长度为$4$的字符串$s1$,$s2$，每次可以选择连续的部分进行$+1$或者$-1$，其实就是类似于我…
题目 2022年天梯赛决赛的前一晚，来几道二叉树的题目(RP++) 给你一个完美二叉树的前N项的后序遍历，求它的层序遍历 我的思考 我的思路是根据每个点往下有多少个子结点，因为给我的最后一个肯定是根，然后递归往下找。 我用一个我自己的样例，就是上图的10个 10 91 83 71 14 2 34 10 15 55 18 这个18肯定是根，前一个肯定是它的右结点，但是每一个数的前一个不一定是右结点，因为有可能不存在，所以我们判断一下： inline void dfs(int x,int p) { if (p<=…
写在前面 这回刚忙完UML大家一起打cf，才有紧张感，确实那时候有点紧张，打了几个嗝，然后这回是第一次打div4（之前那场太久远了），目标就是冲着AK去的，并且也需要手速。出题当然还算可以，ak了，但是有些题目实在是做得慢hhh。 不过最近水平确实越来越有突破了，最近补了ABC的F，还有div3AK，这回现场AKdiv4，感觉越来越好起来了，虽然是ak，但是时间也没有落下，还是跟上了大部队（脱老师，易老师，龙老师），可惜龙龙最后的F爆int挂了，最后榜单出来了我还往前走了几十名。希望自己下次再接再厉，多多补题！ 比…
题意 比赛链接：Problem - F - Codeforces 给你一个长度为$n(3\leq n\leq 2\times 10^5)$序列，问你是否能够将其分成三段使其满足如下条件：第一段Max=第二段Min=第三段Max，如果存在则输出"YES"和每段的长度，否则输出"NO"。 思路 看到这个数据我第一反应是双指针+贪心，但是wa2中的testcase721...最终放弃，去补题了，后来发现是自己贪心的方法不对，这里用二分+贪心过的。 这里枚举第一段的范围（时间复杂度$O(n)$），然后去二分第二个区间的长度…
写在前面 这是一次4.21的vjudge训练，打算认真做一次，出题还算可以不过有点慢，慢慢靠过题数达到了前方，E题我觉得是最难的但是20.12.31补过这个...我打算直接开F，没想到做了2h的F也没写出来，我用的双指针，指针移动的方式错误，我查不到数据，wa2的testcase721... 比赛链接：Dashboard - Codeforces Round #686 (Div. 3) - Codeforces A - Special Permutation（思维+构造） 题意 给你一个长度为$n$的序列，让你输出…
题意 给你一个$N$个点，形成如下的图，求删除$i=\lbrace 1...N-1 \rbrace $条边，$N$个点依然联通的方案数，对$P$取模，数据范围：$2\leq N \leq 3000$ 这样的图是有$N$个点，$3N-2$条边，例如样例$N=3$的时候，当分别删除$1,2$条边的时候的方案数如下： 思路 我们用dp[i][j][0/1]来表示前i个点已经删除了j条边的连通性，0代表没联通，1代表联通的方案数。 注意我这里说的没联通代表前面i个虽然是不连通的，但是在今后的情况下是有可能连通的，比如不存在…
比赛链接：Tasks - UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248） A - Lacked Number（签到） 这个题有很多种做法，可以sort去找，也可以拿容器（如map）存，我这里想讲我的做法：异或 由于我们知道a ^ b ^ a = b，所以我们一开始可以让ans=0 ^ 1 ^ 2 ^ ... ^ 9，然后对读入进行扫一遍。 inline void Case_Test() { cin>>s; n=s.…
题目 题目来源于大连大学2022年4月程序设计竞赛，我和伍老师合砍12题rk23，差两题ak。 题目链接：F-旅行_大连大学2022年4月程序设计竞赛（同步赛） (nowcoder.com) 一句话题意：给你n点m边的有向图，每条边有边权，点没有点权，q次询问，每次询问点x是否在点1到点n的最短路径上，最短路径可能有多条。 如上图，从1到4的话，最短路当然是"1->3->4"，这三个点都是，而2不是。 思路 我们先用一个二维数组dis[i][j]来表示点i到点j之间的最短距离，那么对于起点是1，终点是n来说，询问一…
