传送门 极其神仙的一道题 神仙就神仙在一个人可以对一段区间造成贡献 解题用到的主要是很神仙的建图方法     (    (   (看了题解     )    )   ) 我们以天数为点,然后第     i    i   i天向第     i   +   1    i+1   i+1天连     I   N   F   −   w   [   i   ]    INF-w[i]   INF−w[i]      (    (   (第     i    i   i天需要人数     )    )   )容量，     0    0   0价值的边 源点向第一天，第     n   +   1   ...

博弈论题题都是神仙 这题怎么考虑？我们发现石子时刻满足从左到右递增，感觉没什么思路，那么根据博弈论的套路，我们开始。。天马行空地乱想。 先考虑     S   G    SG   SG函数，发现这题取石子的限制是时刻在变的，显然不行。 然后，这题多堆石子且并不相互独立，没什么表打，打表也滚粗了。 石子个数递增？？是不是长得像阶梯？？(大雾 顺着这个瞎想的思路，再康一康题目，发现移走一堆石子，它两边石子与它的差值会变。 怎么变呢？设一堆石子移走     x    x   x，显然左边与它的差值     −   x    -x   −x，右边与它的差值     +   x    +x   +x，这...

博客地址

传送门 看到     n   <   =   12    n<=12   n<=12的数据范围，一眼状压     d   p   ​    dp​   dp​？随便开始敲了敲，一晚上就没了？ 看到题解还有一篇状压，感觉挺麻烦的。这里给出可能稍微方便一点的。 状压状态和方程应该很好想，     f   [   i   ]   [   j   ]    f[i][j]   f[i][j]表示状态     i    i   i下，最后的字符串是     j    j   j的最短长度，因为要输出方案，再来一个     g   [   i   ]   [   j   ...

传送门 首先很容易发现答案就是     26   ​    26​   26​的“空位个数”次方。空位的个数很显然能够通过极其方便的差分处理出来，我们要处理的仅仅只有判断是否无解。 分两种情况： 第一种，两个串不相交，显然什么关系都没有。 第二种，两个串相交，我们要判断相交部分是不是相同。发现相交的是第一个字符串的后缀，和第二个字符串的前缀，判断这两段是否相同，那么最容易想到的就是     H   a   s   h    Hash   Hash了。     H   a   s   h    Hash   Hash在     c   f    cf   cf上极其危险，有人会对着你卡。所以尽量...

经过多次爆蛋，还是秒切了此题。 一道少数没看题解做的题，哇居然是紫题我好牛逼。 开始不正经的讲题目：很显然发现这是一道动态规划题，先考虑设计状态。 很容易想到的状态是     d   p   [   i   ]   [   j   ]    dp[i][j]   dp[i][j]表示前     i    i   i行放上     j    j   j个炮的方案数。但转移时我们就发现，这个状态所包含的信息太少了，从第     i   −   1    i-1   i−1行转移到第     i    i   i行，好像根本无法判断第     i    i   i行怎么放，辣怎么办哩？ 观察到炮的性...

这题真喵喵的毒瘤，写的时候被时空双卡。 为了发泄愤怒，我来水一篇题解 题意：求      1   −   n   !    1-n!   1−n! 中与      m   !    m!   m! 互质的数的个数      (   m   <   =   n   )    (m<=n)   (m<=n) 我们发现小于      m   !    m!   m! 的数中，与      m   !    m!   m! 互质的数有     φ   (   m   !   )    φ(m!)   φ(m!)个，那如何求大于      m   !    m!   m...

好水的蓝题啊，少数没有看题解做的题 题面简洁明了：求      ∑    i   =   1    n    g   c   d   (   i   ,   n   )    \sum\limits_{i=1}^{n}gcd(i,n)   i=1∑n​gcd(i,n) 设     g   c   d   (   i   ,   n   )   =   d    gcd(i,n)=d   gcd(i,n)=d，则     g   c   d   (   i   /   d   ,   n   /   d   )   =   1    gcd(i/d,n/d)=1   gcd(i/d,n/d)=1...

很好的一道思维题。警告：文字较多，没有耐心者勿入。 首先我们命名      a   1    ,    a   3    ,   .   .   .   ,    a    2   n   −   1      a_1,a_3,...,a_{2n-1}   a1​,a3​,...,a2n−1​为奇数位，其余为偶数位。观察题目条件：奇数位与偶数位上的数字都满足从左到右递增，相邻的      a    2   i   −   1     ,    a    2   i      a_{2i-1},a_{2i}   a2i−1​,a2i​满足      a    2   i   −   1     ...

传送门 给你一个数     S    S   S，求约数和等于     S    S   S的数。 好像也没什么好说的，主要就两个式子： 1、整数的唯一分解定理     x   =    ∏    i   =   1    k      p   i     a   i      x=\prod\limits_{i=1}^{k}{{p_i}^{a_i}}   x=i=1∏k​pi​ai​ 2、一个数的所有约数和     S   =    ∏    i   =   1    k     (    ∑    j   =   0     a   i       p   i    j    )     ...

众所周知，网络流可以求最小割，但割的是割边。本题一眼看就可以知道，题意要求割掉最少的点使起点到终点不连通。 最小割怎么处理点呢？我们想，只要把点取不取转化到边权就好办了。 考虑拆点，把一个点     i    i   i拆成     i    i   i和     i   +   n    i+n   i+n。     i    i   i向     i   +   n    i+n   i+n连一条边权为     1    1   1的边，再把连向这个点的边都连到     i    i   i上，这个点连向其他点的边都连到     i   +   n    i+n   i+n上。那么只要割掉...

题目要求一个序列中的两个子段，使这两个子段每段的异或和加起来值最大。 说到异或，我就想到开花     T   r   i   e    Trie   Trie字典树。 先考虑怎么求一个     l    l   l到     r    r   r子段的异或和     (    (   (异或和：所有数异或起来的值     )    )   )：       a   l    ⊕    a    l   +   1     ⊕   .   .   .   ⊕    a    r   −   1     ⊕    a   r    =   (    a   1    ⊕    a   2    ⊕...

这是一道很好的套路题。助你掌握新套路。 第一问太愚蠢了，求最小割，学过网络流应该都会。 重点是第二问，求最小割割的最少边数。太难了，默默打开题解，     g   e   t    get   get到新套路。 建图时，我们将边的权值乘以     (   (    ((   ((一个较大的数     a   )   +   1   )    a)+1)   a)+1)，设新的图的最小割为     n   e   w   a   n   s    newans   newans，那么原图最小割为     n   e   w   a   n   s   /   a    newans/a   ne...

首先发现是一张连通图，而且只有     100    100   100条边，那么点也很少 编号是乱的，先进行一波离散化，上     m   a   p    map   map即可(STL大法好) 离散化后，转化成邻接矩阵，这个矩阵实际上表示的是     i    i   i到     j    j   j只经过     1    1   1条边的最短路矩阵。这时发现，我们要求的答案是一个     s   t    st   st到     e   d    ed   ed且只经过     n    n   n条边的最短路矩阵。 考虑如何从小矩阵推向大矩阵：设矩阵     A    A   ...