【题解】SolutionSet-NOIP2024集训Day36dp优化+状态设计https://www.becoder.com.cn/contest/5550最后一题较难。「NOIP2023」天天爱打卡考虑dp。\(f_{i,j}\)：前\(i\)天，到第\(i\)天为止连续打卡\(j\)天。有转移：\[f_{i,0}=\max(f_{i,j})\\f_{i,j}=\max(f_{i......

【2024.09.15】NOIP2024赛前集训（2）A最大的难点戏剧性地变成了二叉搜索树是什么。先根据已知序列把二叉树建出来，忘了二叉搜索树的移步二叉搜索树&平衡树-OIWiki(oi-wiki.org)根据题意，想到dp计数，\(f[u]\)表示\(u\)子树内的答案，则有转移：\[f[u]=f[lson]\timesf[r......

前言若巅峰不在，那就重踏来时之路。今天是\(\texttt{DP}\)优化专题，感觉只要写出了暴力，剩下的部分都挺典的。怎么说，感觉今天状态不太好，老是细节上出现一些很逆天的错误。例如：for(autoi=dp.begin();i!=dp.end();++i){pair<ll,ll>j=*i;ans=j.first......

【题解】SolutionSet-NOIP2024集训Day32数位dphttps://www.becoder.com.cn/contest/5537order：1,3,5,6,2,4「SDOI2013」淘金就是要算前\(k\)大的和。考虑一个位置\((i,j)\)在变化完了之后的金子个数。（也即逆变换。设：\(f^\prime(x)\)表示在\(1\simN\)范围内，数位......

[清华集训2012]串珠子题意给定\(n\)个点和\(n\timesn\)的矩阵\(c\)。有\(c_{i,j}\)种方案把点\(i\)和点\(j\)连接起来。求有多少种方案使得整张图连通。思路注意到\(1\len\le16\)，考虑状压。定义\(g_i\)为集合\(i\)的连边方案数，有\[g_i=\prod_{u,v\i......

[国家集训队]Crash的数字表格/JZPTAB题目描述今天的数学课上，Crash小朋友学习了最小公倍数（LeastCommonMultiple）。对于两个正整数\(a\)和\(b\)，\(\text{lcm}(a,b)\)表示能同时被\(a\)和\(b\)整除的最小正整数。例如，\(\text{lcm}(6,8)=24\)。回到家后，Crash还在想......

从阶乘幂到斯特林数-caijianhong-博客园(cnblogs.com)题目描述Crash小朋友最近迷上了一款游戏——文明5(CivilizationV)。在这个游戏中，玩家可以建立和发展自己的国家，通过外交和别的国家交流，或是通过战争征服别的国家。现在Crash已经拥有了一个\(n\)个城市的国家，这......

NOIP2024集训Day27DP常见模型4-树形E.[COCI2014-2015#1]Kamp首先只考虑一个点，发现如果回到原来位置是比较好搞的，就每次走完子树的里面要的就上来，如果子树里面没有要走的就不走。（大概是\(f_x=\sumf_y+2\cdote_x\)，因为要走过去走回来，注意\(y\)要保证子树里面有人）......

【题解】SolutionSet-NOIP2024集训Day27树形dphttps://www.becoder.com.cn/contest/5521「HDU4661」MessagePassing「BZOJ3935」Rbtree「ARC101E」RibbonsonTree「AGC034E」CompleteCompress「COCI2014.10」Kamp「SCOI2015」小凸玩密室「AGC008F」Black......

【五一省选集训day4】GridGame首先发现\(n,m\le2000\)，可以考虑枚举正方形左上端点\((x_0,y_0)\)。对于一个边长为\(len\)的合法的正方形，如果\(len=k\)这个正方形全黑，需要特判，否则它至少有一个白点。我们惊奇地发现，对于这样的其中一个白点，它所在的那一列一定存在恰好\(......