题目链接CF1354EGraphColoring(*2100)解题思路发现这个东西就是类似于二分图染色的东西。因为\(2\)只能和\(1,3\)链接。其余种类的点都不能连接。不妨把\(1,3\)都看成同一个点放到最后处理。那么我们就相当于是要找到一种方案使得选择每个联通快的黑点或白点，使得最

题目大意（翻译来自luogu）给定两个正整数\(n\)和\(m\)，以及一个长度为\(n\)的数组\(r\)。保证\(-m\ler_i\lem\)，并且恰好有\(m\)个\(r_i\)为\(0\)。你有两个初始值均为\(0\)的变量\(I\)和\(S\)，接下来在第\(i\)秒中（\(1\lei\len\)）将发生如下事件：如果\(r

挺有意思的树型dp。思路发现直接求解很难对限制下手。但我们可以注意到答案最多为\(n\)。考虑将答案记录dp状态。我们可以记\(dp_{i,j}\)为子树\(i\)合法并且断了\(j\)条边的状态。由于合法状态有两种，并且不好一起考虑，所以可以再在dp状态中加一维。令\(dp_{i,

题目传送门前置知识预设性DP解法考虑统计每个数单独的贡献，然后进行预设性DP。设\(f_{i,j}\)表示当前填了\([1,i]\)时有\(j\)个连续段的最小权值，边界为\(f_{0,0}=0\)。对\(i(i\nes,i\nee)\)填入的位置进行分讨。新开一段后面填入的数都比\(i\)大（如果存

普通#include<iostream>usingnamespacestd;#include<algorithm>#include<cstring>constintN=5010;intn,f[N];inta[N];intmain(){ cin>>n; for(inti=1;i<=n;i++)cin>>a[i]; for(inti=1;i<=n;i++

7月21号模拟赛赛后总结\[7月\21号\模拟赛\\赛后总结\\2024年7月21日\\by\\\hcy\]一、做题情况第一题比赛\(10pts\)，赛后\(AC\)第二题比赛\(0pts\)，赛后\(AC\)第三题比赛\(30pts\)，赛后\(AC\)第四题比赛\(0pts\)，赛后\(AC\)比赛得分\(40pts\)

（一）非常妙的DP题，可惜被翻译毁了。题意：你有一堆零食，每个零食有两个值\(a_i\)和\(b_i\)。要求选出集合\(S\)，使\(\sum_{i\inS}a_i-\min_{i\inS}a_i\lep\)，求最大的\(\sum_{i\inS}b_i\)。一眼DP。先将\(a_i\)从小到大排序，每次循环更新\(dp_0\)的值为\(\max

CF13CSequence给定\(N\)个数，每次操作可以选其中一个数\(+1\)或\(-1\)。请问要让这个数列不降，最少需要多少次操作？我们用DP解决。对\(a\)从小到大排序，存在\(c\)中。我们用\(f[i][j]\)表示让前\(i\)个元素满足条件，而且这些元素最大值不超过\(c[j]\)的最小操作次数。状态转移方

暴力直接暴力枚举区间，并且逐个判断#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#include<string>#include<cmath>#defineR(x)x=read()#defineFor(i,j,n)for(inti=j;i<=n;++i)using

题目传送门前置知识后缀数组简介解法一个子串出现至少\(2\)次等价于有至少连续\(2\)个后缀以这个子串作为公共前缀。进行一次后缀排序后，有\(\max\limits_{i=1}^{|s|}\{height_{i}\}\)即为所求。代码#include<bits/stdc++.h>usingnamespacestd;#definelllong

P2516[HAOI2010]最长公共子序列总的来说，这道题确实很精妙，难度也不小，耗费了不少时间去调。本来想过用容斥的思想，却因为当时理解不深没有继续思考就放弃了。学会了思路后对\(LCS\)有了更深层次的理解。题意简述给定\(A,B\)两个字符串（以.结尾），求它们的最长公共子序列的长度和个数

P5858「SWTR-3」GoldenSword第一道自己想出递推公式并且成功\(AC\)的\(dp\)绿题。题意简述有\(n\)种原料，每个原料有一个耐久度\(a[i]\)，必须按照\(1,2,…,n\)的顺序放入炼金锅。但是炼金锅的容量是有限的，只有\(w\)，所以在每次放入原料之前，都可以选择取出\(0\sims\)个原料再放

题目传送门前置知识概率DP|树形DP|RMQ解法观察到区间只有相离或包含关系，类似线段树的管辖区间，考虑将其构成树形关系。为方便代码书写，将原来的森林构成一棵树，即增加一个区间\(l_{q+1}=1,r_{q+1}=n,p_{q+1}=0\)。由于对于一个区间\([l,r]\)的最大值在经历任意次操作后，

不是很裸的01背包但是被卡了半天，所以记一下思路（？）对环的计算一般是从0-n-1，这样子转完一圈%n原位置就还是0，方便计算。然后二维dp，第一维表示第几次，第二维表示多少度。 #include<iostream>usingnamespacestd;intn,m;inta[5010];intf[5010][5010];intmain(){cin>

P4563[JXOI2018]守卫更好的阅读体验这道题让我充分认识了我一点不会dp。首先可以预处理一个点能看到的左边的所有点。注意到一个区间一定会选择右端点，设右端点不能看到的所有极长区间为\([l_1,r_1],[l_2,r_2]\dots[l_k,r_k]\)，区间\([L,R]\)的答案即为\(1+\sumf_{l_i,r_

更好的阅读体验CF1730FAlmostSorted挺有意思的一道题。刚看到可能有好几种思路，按照\(p\)的大小填\(q\)，或者按照下标顺序填等等。试了几次之后考虑按照\(i\)从小到大填入\(q_i\)，设\(pos\)为当前填了的最大的\(p_{q_i}\)，由于题目的要求，\(1\sim(pos-m-1)\)的所有数

postedon2022-08-1500:08:56|under题解|sourceproblem一个长为\(n\)的排列\(P\)，每次可以选择一个\(i\)，令\(v=\max(P_i,P_{i+1})\)，使\(P_i=P_{i+1}=v\)，求若干次操作后有多少种不同的序列。\(1\leqn\leq5000\)。solution显然地，对于一个\(P_i\)，它要么被完全覆盖

迷惑，开三道题发现T3见过原题没做。然后在kai586123老师课件里边找到了这题题号。震撼，震撼。不知道NJU营春测卡多少分。第一题正解是把询问对列分治，然后考虑跨过中间列的询问。暴力\(O(\dfrac{n^4}w+q)\)的方法是显然的，可以获得\(50-100\)分不等，略微卡常后通过。#in

PalindromeTimeLimit:4000/2000ms(Java/Other)   MemoryLimit:65536/32768K(Java/Other)TotalSubmission(s):72   AcceptedSubmission(s):19ProblemDescriptionApalindromeisasymmetricalstring,thatis,astringreadidenticallyfromle

postedon2022-09-2414:33:29|under题解|sourceproblem一个黑白矩阵，求以每个点为右下角，能围出的周长最大的全白矩形的周长。\(n\leq2000\)。solution试图进行

P5022[NOIP2018提高组]旅行我只想出了部分分的解法。。。https://fzy.blog.luogu.org/solution-p5022#include<bits/stdc++.h>#definefor1(i,a,b)for(inti=a;i

据joke3579说明，lyin做过今天的题但是给机会了。而且题目名称不管怎样都很吊。T1三分理论不对但是能过。但是场上把所有端点扒下来排序三分炸了。#include<cstdio>#inc