本文为第二届你要魔怔杯鲜花大赛！！！投稿作品。前言这是一个\(\bmod\11\)的世界。假设这个世界与地球类似（不妨称它为E球），但是所有的数都是\(\bmod\11\)意义下的。在正文和注解部分书写一个十进制数时我会用0d作为前缀。下文用\(A\)代替\(10\)。人名都是随机找的。

我让cz搬这道题，cz给搬了，于是来写个题解（考虑一个朴素的贪心：每次选择一个到根路径价值和最大的叶子，将价值和累加进答案，并把这条链价值清零。这个贪心的正确性显然（可以交换法证明），很容易用数据结构维护做到\(O(n\logn)\)。但是这样太不优美了，而且数据结构比较难写，于是考虑一个

区间最值操作基础题，但是有点码农。依然考虑势能线段树，维护区间和\(\textrm{sum}\)、最大值\(\textrm{M1}\)、次大值\(\textrm{M2}\)、最大值个数\(\textrm{Mcnt}\)、最小值\(\textrm{m1}\)、次小值\(\textrm{m2}\)、最小值个数\(\textrm{mcnt}\)，另外需要区间加标记\(\tex

场切了1E，第一次上IGM，纪念一下。多图警告。我们称题目中的一个方块为“某色混凝土”。感受一下，发现本题主要的难点在于这些混凝土方块排布得太紧密了，导致容易出现互相遮挡的现象，进而难以构造。于是，我们先思考能否通过一些操作使得这些混凝土互相分离。如下图的方式可以将每两

前置知识https://www.cnblogs.com/caijianhong/p/template-crt.htmlhttps://www.cnblogs.com/caijianhong/p/template-fft.html题目描述任意模数多项式乘法solution首先我们打开https://blog.miskcoo.com/2014/07/fft-prime-table这篇文章找到\(998244353\)附近的几个质

萌萌F题，上大分。首先，如下定义\(g(i)\)：\(g(1)=\lfloor\sqrt{a_1}\rfloor\)；对于所有\(i>1\)，\(g(i)=\lfloor\sqrt{g(i-1)+a_i}\rfloor\)。也就是将\(f(i)\)的每一步运算后都向下取整。注意到\(\lfloorf(i)\rfloor=g(i)\)恒成立，于是我们只需要转而求每次修改后\(g(n

先不考虑构造字典序最小的方案，只考虑求出最小的\(\sum\limits_{i=1}^{N-1}|A_{i+1}-A_i|\)。设定义域为\([L_i,R_i]\)的函数\(F_i(x)\)表示考虑后缀\([i,N]\)，令\(A_i=x\)时上式最小的值。初值为\(F_N(x)=0,(x\in[L_N,R_N])\)。显然有转移方程：\[F_i(x)=\min\limits_{y

非常精彩的转化！显然，树是二分图。由König定理，我们知道：二分图最小点覆盖等于最大匹配。因此枚举点覆盖\(S\)，则一条边\((u,v)\)可以被选择，当且仅当\(u\inS\lorv\inS\)，在所有可以选择的边上跑最小生成树即可。我采用的是Kruskal算法，时间复杂度为\(O(2^nn^2\logn)\)，可

初三多项式的运算练习题解美好的下午时光要拿来写题解呜呜呜，一篇一篇地鸽得了。有些题要用到GF的知识，或许我可以找时间讲一下？贴一份我的FFT和NTT的板子。FFT：#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intn,m,limit,f[1<<22],g[1

对于每个询问，可以把这\(r-l+1\)个袋子包合并成一个有\(\sum\limits_{i=l}^ra_i\)个金币和\(\sum\limits_{i=l}^rb_i\)个银币的袋子。\([l,r]\)外的袋子同理也可以这样合并。假设\(sum_a=\sum\limits_{i=1}^na_i,sum_b=\sum\limits_{i=1}^nb_i\)，\(

A.多项式推柿子：\[\begin{aligned}&\sum\limits_{k=0}^{n}b_{k}(x-t)^{k}\\=&\sum\limits_{k=0}^{n}b_{k}\sum\limits_{i=0}^{k}\binom{k}{i}x^{i}(-t)^{k-i}\\=&\sum\limits_{0\leqslanti\leqslantk\leqslantn}\binom{k}{i}b_{

好像比题解劣一个\(n\)，但是也跑的很快。首先说明，问题等价于计算有多少种本质不同的方案使得整个序列被删完，证明省略。考虑用区间的方式表述这些操作，具体的，忽略删除后的移位操作，将每次删除的左右段点视为一个区间，则一定会有：区间的并是\([1,n]\)。区间之间要么不交，要么包含。

总算铂金组场切一题。似乎做麻烦了，而且常数蛮大的，但是没啥思维难度，记录一下。对于每一个需求，我们将其放置在平面直角坐标系的\((m_i,b_i)\)位置。另外，自然有一个\((0,0)\)需求，也同样处理这个点。我们需要支持插入一个点的操作，并维护出答案。先考虑不需要动态插点，只在最后求

Namid[A]me好听呢。可惜了。今天DP专题感觉laofu选的题有点经典，导致我有一半时间在摸鱼，不过还是写了点题的。怎么西工大附中有糖醋茄子这种神秘菜啊。ICPC2020MacauBBoringProblem其实不一定懂完了，试着说一说。显然询问没什么用，问题本质是要求解一个AC自动机上游

SlopeTrick总结注意：SlopeTrick并不是斜率优化，斜率优化的英文是ConvexHullTrick。算法适用性SlopeTrick通常用于维护具有如下性质的函数：连续。是分段一次函数。是凸函数。每一段的斜率较小（通常为\(O(n)\)），且均为整数。常常用于优化动态规划。不失一般性，约定本

本文中点的编号从\(0\)开始。显然，题目中要求橙色的边构成极大的二分图。枚举二分图左右部分别有哪些点。特别地，钦定\(0\)号点是左部点。将所有跨左右部的边染为橙色，如果所有点通过橙色的边连通，就得到了一组合法的解；如果不连通，显然可以将更多的边染成橙色，使得所有点连通。//

萌萌BEST定理练习题。赛时几乎做出来了，但写挂了，现在在火车上没事干就给补了。考虑建图，图中共有\(8\)个节点，节点的编号是\((\mathbb{Z}/2\mathbb{Z})^3\)的每个元素。对于每个四元组\((i,j,k,l)\in(\mathbb{Z}/2\mathbb{Z})^4\)，在图中连\(X_{i,j,k,l}\)条\((i,j,k)\to(j

设\(P_b(k),P_w(k)\)表示已经吃了\(k\)块巧克力，把所有黑/白巧克力都吃光了的概率。枚举最后一块黑/白巧克力被吃的时间，容易得到：\[\begin{aligned}P_b(k)&=\sum_{i=1}^k\frac{\binom{i-1}{b-1}}{2^i}\\P_w(k)&=\sum_{i=1}^k\frac{\binom{i-1}{w-1}}{2^i}\\\end{aligned}\]

来补题了。昨天赛时想法是对的，代码写错了，没调过太可惜了。显然\(P>n\)时必定有解。设前缀\([1,i]\)的哈希值为\(s_i\)，显然\([l,r]\)的哈希值不为\(0\)的充要条件是\(s_{l-1}\nes_r\)。建立一个点的编号为\(0\simn\)的图，对于每个输入的区间\([l,r]\)，连接一条边

每棵子树内只可能有至多一个外来的数，且外来的数是多少并不影响方案数，因此考虑设\(f_{u,i,0/1}\)表示考虑以\(u\)为根的子树，与\(u\)相连的所有边中断了\(i\)条，且\(u\)与其父亲之间的边有没有断的方案数。设\(g_{u,c}=\sumf_{u,i,c}\)。每个节点的初始状态是\(f_{u,0,

考察题面中的操作究竟做了什么，不难发现其实是将所有满足\(P_i>i\)的\(i\toP_i\)连边，得到若干条链，然后\(B_i\)即为\(i\)所在链的最后一个节点。显然，存在\(A_i<i\)时无解，存在\(A_i\nei\)但\(A_j=i\)时也无解。否则，每个\(A_i\nei\)的位置填的数都唯一确定

#include<bits/stdc++.h>usingnamespacestd;#ifdefLOCAL#definedebug(...)fprintf(stderr,##__VA_ARGS__)#else#defineendl"\n"#definedebug(...)void(0)#endiftypedeflonglongLL;template<unsignedumod>structmodint{

就硬把线段树3和数列分块入门2揉到一起出。维护原数组\(a\)及其历史最大值\(hist\)，对每个块，维护块内\(a\)升序排序后结果\(p\)、块内\(a\)升序排序后历史最大值前缀和\(prehist\)、块加标记\(add\)、块历史和加标记\(histadd\)。下传标记和区间修改操作仿照线

先求出初始时绿连通块数量。将一个绿色格子染成红色，会改变绿连通块数量，当且仅当这个绿色格子是孤点或割点。如果是孤点，会使得绿连通块数量减少一；如果是割点，会使得绿连通块数量增加它所在的点双数量减一。根据上述规则可以求出每个绿色格子染红后的绿连通块数量，求平均值即可。时

设\(f_i\)表示假设只有编号为\(1\simi\)的点，此时的答案。\(f_n\)即为所求。显然有：\[f_i=\min\limits_{i-k\lej<i}\{f_j+dis(s\toj+1\toj+2\to\cdots\toi)\}+dis(i\tos)\]当\(i\toi+1\)时，大括号内部全局增加\(dis(i\toi+1)\)，可以全局打标记后单调队列维护。