- 2023-12-06ucup hefei 题解
比赛链接B很有意思的题首先题目的要求为可以拆分成\(2\)个不相交的不降子序列根据\(dilworth\)定理,最小链覆盖\(=\)最长反链,所以要求最长反链\(\le2\)即原序列的逆序列的最长不降子序列长度\(\le2\)不难得到一个\(dp\)做法为:令\(f_{i,j}\)为到数\(i\),最长上
- 2023-12-03ucup nanjing 题解
比赛链接D收获很大的一道题首先考虑朴素的\(dp\),令\(f_{x,i}\)为\(x\)子树中的每一个叶子到\(x\)的距离都为\(i\)的最小代价不难列出\(dp\)式子为:\(f_{x,i}=\min\limits_{i\in\{0,1\}}\{cost(u,i)+\sum\limits_{v\inson(u)}f_{v,x-i}\}\),其中\(cost(u,i)\)为把
- 2023-11-10NOIP2023 游记
Day-11~Day-9三连测。场场垫底。过题了不起,有分夸自己。爆零就爆零,天天好心情!起床了不起,呼吸夸自己。开摆就开摆,天天好心情!每天下午快乐羽毛球,发现每天打羽毛球的时间比学习时间长多了。感觉时间过得巨大快,每天早上起床,摆一个上午,中午睡一觉,再摆一个下午,再摆一个晚上,一天
- 2023-10-17ucup 题目乱炖
Season2022#6299.BinaryString如果\(0\)的个数小于\(1\)的个数那么就反转\(01\)以及反转序列,接下来假设\(0\)的个数大于等于\(1\)的个数。称有\(11\)的序列为”未完全展开的“,那么序列的种类数有两个阶段:展开过程中和展开之后的。在展开之后如果知道序列那么用
- 2023-03-192023 ICPC香港区域赛(UCup) D Shortest Path Query
啊对对对,下次题解写详细一点好不好。首先考虑naive的\(O(n^2)\),记\(dp[i][j]\)表示从\(1\)走到\(i\),恰好走了\(j\)条黑边的时候走过白边的最少数量。\(O(nm)\)
- 2023-02-12Ucup 3. Poland E
【题意】求(题意已经经过简化)\(n\le10^{11}\)【分析】这里考虑两个整除分块嵌套的时间复杂度。等于有结论:\(1^k+2^k+3^k+...+n^k\)。当\(k\)是正整数的
- 2023-02-12Ucup 3. Poland K
【题意】给定两个集合\(S,T\),集合里每个元素都是一个二元组\((v_i,s_i)\)。求\(\min\limits_{i\in[1,|S|],j\in[1,|T|]}{\cfrac{s_j-s_i}{v_j+v_i}}\)。