前言米奇妙妙\(\rm{dp}\),也是高端计数这种题看得懂想不出,还是非常难蚌能不能多想想再去看\(\rm{TJ}\)啊算法注意到除了割边,其他的边都没有影响,显然可以缩\(\rm{e}\)-\(\rm{DCC}\)再进行处理这里发现缩完之后形成一棵树,考虑树形\(\rm{dp}\)这里我有一个误

题意给定排列\(a,b\)，\(q\)次询问\(l,r\)，你需要求出\(\sum_{l\lel'\ler'\ler}(\max_{i=l'}^{r'}a_i)(\max_{i=l'}^{r'}b_i)\)对\(2^{64}\)取模的值。\(n,q\le2.5\times10^5\)分析根据经典套路，按\(r\)扫描线，维护两个单调栈，那么加入一个数就相当于进行若干段区

洛谷。题目简述给定两个数列\(a,b\)，有\(q\)次询问，每次询问\([L,R]\)的所有子区间\([l,r]\)的\(\max_{i=l}^ra_i\times\max_{i=l}^rb_i\)之和。其中，\(n,q\le2.5e5\)。分析这很像历史版本和，但是我们写过的只有一个数组\(a\)的。那么先从部分分开始。对于\(n,

由于本人NOIP2023做的太烂了，被教练拉去做NOIP2022了qwqfirsthour:这t1看上去还行，先写了secondhour:t2看上去有些难度，让我想一想thirdhour:快想出来了，先写一写吧fourthhour:写写写写写.....最后100pts遗憾离场......赛后有了深刻的认识，很多题是不能一步到位的，只能拼暴力

看到最大值，考虑使用单调栈搞出\([la_i,ra_i],[lb_i,rb_i]\)表示这一段区间\(i\)是\(a,b\)的最大值。预处理是简单的。inlinevoidinit(){staticautof=[](inta[],intl[],intr[])->void{staticintstack[N],top;top=0,a[n+

树形\(dp\)好题。观察题目发现，如果B国袭击后，导致A国两个军营不联通，那么B国袭击的一定是一条割边，反之，如果袭击的不是割边，那么不会导致任何影响。所以先进行边双缩点，变成一棵树，记每个联通块（缩完后）内的点数为\(wa\)，边数为\(wb\)，不妨先考虑对于树的情况如何处理。将问题进行转

NOIP2022游记突然想起来两年前的一篇游记没写，现在好像也已经很难再回忆起什么了，但我的OI生涯中也就这两场比赛，总得留下点什么来让日后回味这段充满热血的时光。Background坐标sc弱校，文化课不顶尖，但在年级上还算比较强，停课之前大概能维持在年级前\(25\)的样子。不是那种

P8866[NOIP2022]喵了个喵构造模拟题，思路很简洁，但是代码不好写。首先看到数据范围，发现\(k\)的数据范围很特殊，种类少一种就是部分分，所以\(k\)一定是关键的，先思考\(k=2n-2\)的情况。\(k=2n-2\)观察两种操作，对于即将进入的牌\(x\)，若某个栈顶或栈底有相同的\(x\)，我们都可

题目描述小C决定在他的花园里种出\(\texttt{CCF}\)字样的图案，因此他想知道\(\textttC\)和\(\textttF\)两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。花园可以看作有\(n\timesm\)个位置的网格图，从上

before\(\text{inf}\)days据说今年GD参赛的人数特别多，很慌。8.01按照往年的惯例，又是一年集训时。去年没学好，只好重头开始。今年这一届的队友tql。算是基本上把深进给复习了一遍吧。8.22集训终于结束了。烦人的初赛又来了。CSP模拟套题接连不断。平均分\(70\)左

去年今时，我得了100+0+0+8分，太抽象了QwQ所以为什么今天才写这个东西？因为今天才做完了T2……[NOIP2022]种花简单前缀和优化DP，不谈。[NOIP2022]喵了个喵非常高级的构造题。看到\(k=2n-1/2\)，我们可能会想到每一个栈内放两个即可，留一个辅助栈，即可完美过掉\(k

[NOIP2022]比赛0.问题转化首先需要转化为区间历史和问题。具体上来讲，就是将询问离线后，扫描线维护对于\(r\)来说，每一个\(l\)的\(\sum_{i=l}^{r}(\max_{j=l}^{i}a_j\\cdot\\max_{j=l}^{i}b_j)\)那么答案就是区间和。1.构造信息与标记接下来就是如何维护区间历史和。

补一下往年的构造题。。。\(k\)大概是\(n\)的两倍往下，这启示我们每个栈最多只放两个元素。首先考虑\(k=2n-2\)的分，容易得到一个策略：留一个空栈不放，每个栈最多放两个。如果当前卡牌存在一个栈顶/栈底和它一样，那当前牌总是可以消掉的。否则当前栈中的卡牌一定两两不同，那一定

传送门我们容易想到预处理区间\([l,r]\)中的\(m_a\timesm_b\)。这样算出来的是一个二维的矩阵，每次的答案就是红色部分：但是这样的问题是二维的，无论如何都不是正解。考虑把列这一维压掉，也就是令\(w'_i\leftarroww_{i,i}+w_{i,i+1}+...+w_{i,r}\)。这样询问的

题解：「NOIP2022提高组」种花题目大意：给定一个\(n\timesm\)的01矩阵，0表示可以种花，1表示土坑（无法种花），现在要在图上种出一个C型或F型（C,F横着的两条线的长度都可以不同，但一定是面向右边的），现在问你种C和F分别有多少种方案（除了这个形状外不能在任何地方种花），多组数据，\(T\leq5\)。

前言临近NOIP，打算把往年的能做的题目尽量做做。以后的就都发布到文章里了，都挤在随笔里有点难看。22年的不改是因为我懒2022P8865[NOIP2022]种花题解P8867[NOIP2022]建造军营2021

前言去年多测不清空导致即便CCF放过了我的\(O(n^2m)\)的代码但依然挂成了\(0pts\)。当时看清空数组后能过CCF数据就没再管。时隔\(1\)年，重做这道题写了\(O(nm)\)的正解，终于完成了当年的心愿。\(O(n^2m)\)思路想到计算方案的话可以维护两个数组\(c1_{i,j}\)表

主要写一写标记的推导。理论大概在关于线段树上的一些进阶操作回忆一下普通历史和。是对两个合并队列做前缀和，然后利用往后插的贡献来计算。\(ht'+add*upd\toht\)\(s*upd+ht'*len\tohs\)下文：\(x\toadda,y\toaddb\)不带历史和的点积：\((a+x)(b+y)

面对他。题面：求选择关键点和不会被割的边，使得任意割去一条边关键点不会有不连通的方案。考虑缩边双，然后这样边双内随便选。你考虑画出一颗树，考虑分类情况，容易发现就是三种：1.没有选。2.全部连通上\(x\)。(即一个尚未孤立的连通块)。3.有不联通到\(x\)的点。(即孤立的一

Day\(2^2+3^2+4^2\)。HNOI2016序列的加强版。我去年怎么这么菜啊，虽然现在也是就是了。\[\sum\limits_{[l,r]\in[L,R]}\left(\max\limits_{i\in[l,r]}a_i\right)\left(\max\limits_{i\in[l,r]}b_i\right)\]考虑离线，对右端点\(r\)扫描线，对每个左端点\(l\)维护\(S_l=\le

这道题想了很久，终于想出来了，非常抽象。经过一番无脑推导，我们发现u里面有没有军营，是否与根连通，u的子树有没有军营，……都对方案数有影响，然后我就一直修修改改，事实证明，当发现越来越多题目条件中被忽略的细节时，一定不要嫌麻烦，要从头开始设置状态。首先我们发现，子树中有没有军营对于

https://www.luogu.com.cn/problem/P8868我学会了历史和！在一阵扫描线过后，你会发现，\([l,r]\)的所有子区间的答案，就一定是扫到\(i\)的时候，加上\([k,i]\)的答案，\(k\lei,i\in[l,r]\)，然后又因为只有当\(i\gel\)的时候，才能对左端点在\([l,r]\)的答案贡献，因此，你会发现这个东

怎么看T3也不是那么难，可是为啥赛时就是被卡死了[难过]不补\(B\)题了，ad-hoc。A.种花题目描述：小C决定在他的花园里种出\(\texttt{CCF}\)字样的图案，因此他想知道\(\textttC\)和\(\textttF\)两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种

今年是最后一年了，真的是来划水的了已经无欲无求了，只是最好能有个七级吧，要是没有也无所谓，反正我自始至终都是个OI废物已经完全回归whk咯谢幕之战，你会变好，还是更烂？冷知识：从去年CSP结束至今，Bosun在LG上只做了9题初赛前一天住了旅馆，周边玩了一下，感觉苏州古城区真的是一点意思也