P5687[CSP-S2019江西]网格图简单来说题目就是给定一个\(n\timesm\)的网格图，同行边权相同，同列边权相同，求该网格图的最小生成树。根据Kruskal算法的贪心思想，我们要优先选择权值尽可能小的行，并将这条边应用于尽可能多的列。列方向同理。为了保证最终生成树的连通性，我们显然要

[CSP-S2019]格雷码很简单的规律题。考虑决策每一位的\(0/1\)，从高位往低位决策。将\(k\)可以看作当前的排名。第\(i\)位若\(2^{i-1}<k\)，说明当前位为\(0\)。否则当前位为\(1\)，并将排名更新为\(k=2^i-k-1\)然后继续决策即可。时间复杂度\(O(n)\)，递归或循环实现都可

今天继续懒惰，继续三合一！！！[CSP-S2019江西]日期题目背景CSP-SJX2019T1题目描述Alice在纸上写下了一个日期，形式为\(\text{MM-DD}\)，其中\(\text{MM}\)与\(\text{DD}\)都是两位数字，分别表示月和天，然而这个日期并不一定存在。Alice找来了Bob要他更改若干位上的数字，使得这个

括号树题意：给定一棵树，以\(1\)为根，每个点有字符(或)。定义\(s_i\)为\(i\)到根的路径的子串中合法括号序列的个数，求\(\bigoplus_{i=1}^ni\timess_i\)，\(1\len\le5\times10^5\)。记\(p_i\)为\(i\)的父亲，\(a_i\)为\(i\)到根的路径以\(i\)结尾的合法括

算法特殊性质显然链的情况就是括号匹配因此显然有代码代码#include<bits/stdc++.h>#defineintlonglongconstintMAXN=5e5+20;intn;std::stringBraket;intfa[MAXN];boolCheck_Special_Quality(){for(inti=2;i<=n;i++){if(f

洛谷P5658[CSP-S2019]括号树题意给定一棵树，每个点有一个括号(或)。定义\(s_i\)表示根节点到\(i\)每个点的括号组成的序列。求每个\(s_i\)中合法括号子串的个数\(f_i\)。思路定义\(g_i\)表示\(s_i\)中以\(i\)结尾的合法括号子串的个数。有\(f_i=f_{fa_

[CSP-S2023]密码锁[CSP-S2022]策略游戏[CSP-S2020]儒略日P7913[CSP-S2021]廊桥分配P7915[CSP-S2021]回文P7914[CSP-S2021]括号序列P5687[CSP-S2019江西]网格图P5689[CSP-S2019江西]多叉堆P9755[CSP-S2023]种树P8819[CSP-S2022]星战

思路：首先求出\(a\)的前缀和数组\(s\)。考虑动态规划，令\(dp_{i,j}\)表示以\(i\)结尾，末尾有\(j\)个为一组的最小答案，则状态转移方程为：\[dp_{i,j}=\min[s_{i-j}-s_{i-j-k}\les_i-s_{i-j}]dp_{i-j,k}+(s_i-s_{i-j})^2\]朴素直接转移是\(O(N^3)\)的，可以得到

题意简述有\(n\)种方法和\(m\)种食材，第\(i\)种方法第\(j\)种食材做出来的菜有\(a_{i,j}\)种。有以下限制：至少做一盘菜。每种方法做出来的菜品数至多为\(1\)。所有以第\(i\)种食材做出来的菜品数不超过菜品种数的一半。求方案数。\(n\le100,m\le2\times10^

这里写目录标题updata20232022202120202019updata2023P9752[CSP-S2023]密码锁P9753[CSP-S2023]消消乐P9754[CSP-S2023]结构体P9755[CSP-S2023]种树2022P8817[CSP-S2022]假期计划P8818[CSP-S2022]策略游戏P8819[CSP-S2022]星战P8820[

#include<iostream>#include<stdio.h>#include<algorithm>#include<string>#include<cmath>#defineFor(i,j,n)for(inti=j;i<=n;++i)usingnamespacestd;typedefunsignedlonglongUll;constunsignedlonglo

有时根据题目的意思感觉看不懂时可以直接抽象一点的根据实际数组来看P5664[CSP-S2019]Emiya家今天的饭多考虑正难则反。反方向比如容斥之类的多考虑猜结论，遇到有多种操作的可以尝试只进行其中部分操作，看能否取得类似结果P1129[ZJOI2007]矩阵游戏

为什么有\(5\)道题？[CSP-S2019江西]和积和简单化一下式子：\[(n+1)\times\sumA_i\timesB_i-(\sumA_i)\times(\sumB_i)\]其中\(A,B\)都是前缀和。[CSP-S2019江西]网格图naive的kruskal是很naive的，所以需要一点简单的优化。考虑其本质过程就是按照

做了这套题，如果是让现在的我当时去考的话应该一共可以有450分，格雷码，括号树，树的重心都可以做，树上的数可以有10分，Emiya至少可以有76分，划分也可以有64分。看OIerDB上可以有166名的好成绩。我的代码合集：洛谷/云剪贴板[CSP-S2019]格雷码首先是格雷码有一个很好的生

相信大家都看过题，但还请搞清楚是数对应结点编号。这里用\(a_i\)表示\(i\)号结点对应的数。对于\(n\leq10\)的数据，全排列出删边的顺序然后模拟，取字典序最小的方案。对于菊花，仍然考虑删边的顺序，假设删边依次是\(rt\tov_1,rt\tov_2,\cdots,rt\tov_{n-1}\)。因为每删一

考虑一个结点在什么情况下会成为重心。随便钦定一个根结点。对于结点\(u\)，假设割掉了其子树\(v\)中的某条边或连接\(u\)和\(v\)的边，形成了一棵大小为\(k\)的新树。令\(mx\)表示除\(v\)子树外最大的子树大小（或\(n-siz_u\)）。如果\(u\)成为了重心根据定义有\(2\ti

[CSP-S2019]树的重心因为这道题令我十分兴奋，所以来写一下做完后的思考。这道题用到了树的重心的种种性质，在写解法的时候会一一点出其用处。首先，枚举每一条边，然后各自\(O(n)\)扫一次的\(O(n^2)\)做法是简单的。那么接下来，就会出现不同的解法了：优化\(O(n)\)求解的过程

P5659[CSP-S2019]树上的数前言被队友（大爹）易giegie要求做这道题，一天一夜绞尽脑汁终于写出来了。（下了样例test1调试）然后被要求写博客虽然我觉得没啥用，但是写一下吧一些说明1.把数在删边时交换的过程看做移动，停留过的点和相关的边认为是经过这些点和边2.把一条边看做两条有

原题之前做过，后来忘了，回顾&复习首先这题容易想到是容斥，因为保证所有他要求每种主要食材至多在\(\lfloor\frac{k}{2}\rfloor\)道菜中被使用(注意，这里是主要食材，不是菜的个数，别问我为什么强调这个)，这说明不满足这个条件的情况最多只有一列会出现\(>\lfloor\frac{k}{2}\rfloor

题目传送门题目描述2048年，第三十届CSP认证的考场上，作为选手的小明打开了第一题。这个题的样例有\(n\)组数据，数据从\(1\simn\)编号，\(i\)号数据的规模为\(a_i\)。小明对该题设计出了一个暴力程序，对于一组规模为\(u\)的数据，该程序的运行时间为\(u^2\)。然而这个程序

一.6.由数字 1,1,2,4,8,8 所组成的不同的 4 位数的个数是（）A.104  B. 102  C. 98  D. 100错误原因：遗漏答案正解：使用穷举法，第一种ABCD型，共有A(4,4)=24种,第二种AABC型，共有A(4,2)*C(3,2)*2=72种，第三种AABB型，共有6种，总共是102种。 8.G 是一个非连通无向图（

题解P5664这道题非常水,段誉初二就切了,但是我初中DP学的非常差,基本什么都不会,见到的小套路能会一个算一个吧。直接计算比较困难,尝试使用DP求出不合法的方案数即

题目分析：（我竟然可以独立做出来正赛的题，表示震惊）这个题面显然就很神仙，不好分析，我们进行转化一下题意：给定一个\(n\timesm\)的矩阵，对于每一行我们可以选择一个数也可以

感觉对重心的理解更直观了一点。题意求一棵树上删去每一条边后两侧子树重心的编号和。\(n\leq3\times10^5\)思路神奇的清真数论。首先这里有一步很妙的操作：把整

P5658CSP-S2019括号树先考虑线性的情况.....(....)如果是(则将其左边的答案加入栈,这个点的答案为0如果是)则将栈顶左边的答案+1作为贡献(答案)每个点的答案为以这个