赛中过3题...最后一题应该是拓扑排序，但是我当时是往这方面想的，但是用的是dfs不知道为什么错... 比赛链接 T1.和有限的最长子序列 题意：给一个长度为n的序列，以及q次询问x，返回序列中满足和小于等于x的最大子序列长度 思路：子序列不要求连续，就是选或不选的概念，直接sort一遍进行二分即可。 我还是不习惯0下标的前缀和。 代码： class Solution { public: int a[1100]; vector<int> answerQueries(vector<int>&a…
垃圾场... 比赛链接："蔚来杯"2022牛客暑期多校训练营8 F.Longest Common Subsequence（签到） 题意：给你n,m,p,x,a,b,c表示的是给你两个序列s,t分别长度为n和m，序列不是直接输入给你的，而是需要进行计算： $$ x:=ax^2+bx+c $$ 求两个序列的最长公共子序列 思路：既然是给出规定的，那么就是找循环节，如果出现过一样的那么就进行更新答案，如果没有出现过那么当然是0。 那么如何找呢，我发现两种情况都可以用一个式子表示，主要是有循环节在s上以及一部分在s上一部分…
越来越菜了，想当年我第一把abc是在去年的暑假，那时候就是一千名...F是个DP，稍后补一下。 比赛链接：Tasks - freee Programming Contest 2022（AtCoder Beginner Contest 264） A - "atcoder".substr() （签到） 题意： 给你字符串atcoder以及两个数L,R，求第[L,R]的字符串 思路：for循环输出即可，记得先-1或者在前面加上一个空格 代码： inline void Case_Test() { s = " atcoder…
题目链接：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…
签到签慢了，四题中间的样子吧，然后难题也没有写出来，补了两题，好像02也能补，再说吧哈哈。 1004.Quel'Thalas（签到） 题意：给你一个$[0,n]\times [0,n]$的二维点，用一条直线去划，最少用多少条线通过区域内除了$(0,0)$的点。 思路：我的想法是划斜线，队友的想法是横竖，结果都是一样的——$2\times n$ 1001.Theramore（思维+签到） 题意：给你一个01字符串，你可以选择一个奇数区间 $[l,r]$ 使得区间内的01反转过来，可以使用无限次，求最后的字典序最小的字…
比赛链接：第 63 场周赛 - AcWing 这场打得很烂hh，也没有认真打，题目还可以，写一下总结吧。B是一个栈就可以，我用上次惯性思维用链表去做也写错了，还是栈比较好，后面在一场的多校里面也是出现过，就一下做出来了。C是一个卡我常数，这里需要手写哈希（Hash） A.数对数量 题意：请计算，共有多少个整数数对 $(x,y)$ 同时满足： 1.$0≤x≤a$ 2.$0≤y≤b$ 3.$x+y=n$ 思路：枚举即可。 代码： inline void Case_Test() { cin>>a>>…
迟到两周的总结（一直在补多校...） 过题数：3/3 排名：26/2341 过题数 罚时 A(906) B(533) C(139) 3 0:52:17 0:04:17 0:11:09 0:36:51 C我写的是一个三分，调好久，他们写的二分好像也可以，还有其他做法，B我赛中用的线段树...实际上不用这么麻烦。 比赛链接：第 62 场周赛 - AcWing A.三个元素（签到） 题意：给定一个长度为 $n$ 的数组 $r_1,r_2,…,r_n$。 请你找到其中的三个元素 $r_a,r_b,r_c$，使得 $r_…
最后过了一题，让排名达到了229，不错不错，一开始还以为我们都要一题寄了。 06数位DP，待补2022 杭电多校7 个人题解 更新至5题 - 严格鸽 1004.Black Magic（思维+签到） 题意：给你$n$个砖块，每块有左右两种颜色（黑或白），现在有一种魔法可以使得两个左右砖块进行合并变成一个砖块，当左砖块的右面和右砖块的左面都为黑的时候。 现在有四种砖块，分别是E,L,R,B分别表示(0,0),(1,0),(0,1),(1,1)，1,0分别表示的是黑和白。你会得到每种个数，求对砖块进行摆放成一排，求使用魔…
周一有robocom，所以这场比赛就随便乱打了，前一个小时签到，打完回来再写一个走人。 不过其他题还是挺不错的，例如本场的J,K，待补，这里先放上ygg的题解：2022牛客暑期多校训练营7 个人题解 更新至5题。 C.Constructive Problems Never Die（构造） 题意：给你一个长度为$n$的数组$a$，求构造一个$1...n$的排列$P$使得对于任意的$i$都满足$a_i\neq P_i$，不能则输出NO。 思路：经过长期cf的训练，这个题还是能秒的，不过有点乱一直在debug... 首先…
