M   r   .   Y   o   u   n    g   ′    s       P   i   c   t   u   r   e       P   e   r   m   u   t   a   t   i   o   n   s    Mr.Young's  Picture  Permutations   Mr.Young′s Picture Permutations  题目描述 链接    Solution 根据其要求的单调性, 可以按从高到矮, 从左向右, 从上向下放人, 这样既即可保证都为合法 因为数据很小, 所以可以将每行状态保存在     d   ...

链接      雨   天   的   尾   巴    雨天的尾巴   雨天的尾巴   题目描述 给出一棵     N    N   N个结点的树, 有     M    M   M次修改操作, 每次操作要求将     a   ,   b    a,b   a,b之间最短路径所有点加上类型为     c    c   c的粮食     1    1   1次, 到最后输出每个点所储存的最多的粮食类型, 如果有相等数量的, 则输出类型编号最小的.        N   ,   M   ,   c   <   =   1    0   5     N, M, c <=...

P1383 高级打字机   题目描述 早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。 请为这种高级打字机设计一个程序，支持如下3种操作： 1.T x：在文章末尾打下一个小写字母x。(type操作) 2.U x：撤销最后的x次修改操作。（Undo操作） （注意Query操作并不算修改操作） 3.Q x：询问当前文章中第x个字母并输出。（Query操作） 文章一开始可以视为空串。   Solution 将每个T操作和U操作建一个节点, 对于Q操作, 使用     v   e   c   t   o   r   [   ]    vector[]   ve...

P3723 [AH2017/HNOI2017]礼物  题目描述 给出两个数列     x   ,   y    x, y   x,y, 长度都为     N    N   N; 定义差异值为      <munderover>  ∑    i   =   1    N  </munderover>  (    x   i    −    y   i     )   2     \sum_{i=1}^N(x_i-y_i)^2   i=1∑N​(xi​−yi​)2  可以将任意数列加上任意自然数     d    d   d, 求最小差异值    数据范围 30%的数据满足...

P   3338   [   Z   J   O   I   2014   ]   力    P3338 [ZJOI2014]力   P3338[ZJOI2014]力 给出n个数qi，给出Fj的定义如下：        F   j    =  <munder>  ∑    i   <   j   </munder>     q   i     q   j      (   i   −   j    )   2      −  <munder>  ∑    i   >   j   </munder>     q   i ...

P2597 [ZJOI2012]灾难  题目描述 见链接    Solution 建立支配树即可    Addition 步骤:  反向建边 拓扑排序 按反拓扑序依次加入支配树节点  加入节点时, 取其所有原图父亲的     L   C   A    LCA   LCA作新树的父亲    Attention 两个字符     1   ,   0    1,0   1,0调了      6   −   h   o   u   r   s    6-hours   6−hours !!! 要时刻注意循环边界 !!!   Code #include<bits/stdc++.h> #def...

书   架    书架   书架 题目描述见链接 .      <mstyle mathcolor="grey">   最   初   想   法   </mstyle>   \color{grey}{最初想法}   最初想法 使用     S   p   l   a   y    Splay   Splay维护  Input: 依次插入节点, 不断 初始插入 到上个节点的右子树中  Top : 将权值为     S    S   S的点 删去 , 再插入作为到     S   p   l   a   y    Splay   Splay的最左边儿子...

十   进   制   快   速   幂    十进制快速幂   十进制快速幂  使用快速幂求      a   b     a^b   ab, 当     b    b   b很大的时候, 就需要使用十进制快速幂   十进制快速幂       a   b     a^b   ab中     b    b   b可以分解为       k   n    1    0   n    +    k    n   −   1     1    0    n   −   1     +   .   .   .   +    k   1     k_n 10^n + k_{n-1}10^{n-1} +...

题   目   名   称   :   凑   硬   币    题目名称: 凑硬币   题目名称:凑硬币   题目描述 jyb 想给他的女朋友买一块很贵的巧克力，jyb 有 n个硬币，第 i 个硬币的价值为 ci 元，巧克力的价格为 k。jyb 想用一些硬币凑出恰好 k元为他的女朋友买一块巧克力。        看着他的硬币，他想到了一个问题，假设他不给女朋友巧克力，而是给她 k元的硬币，她用这恰好 k元的硬币可以凑出哪些价值呢？他想不出来，于是请你帮他解答这个问题。        更准确地说，jyb 想要知道所有的价值 x，在 jyb 的硬币中能够找出一个恰好 k 元的子集 S，使得存在 ...

P3391 文艺平衡树  题目描述 维护序列, 有若干翻转操作, 输出最后序列    Solution 带翻转标记的平衡树模板 在翻转时, 查询第L-1大, 和R+1大的元素 (此时下标为权值) ( 考虑到交换左右子树对查找树性质的影响, 所以不能直接查询前驱后继 ) 在     r   o   t   a   t   e    rotate   rotate操作, 和查询     k    k   k大操作下传标记即可 因为每个元素固定只有一个, 所以不用开cnt数组 输出时直接输出中序遍历即可   Code  #include<bits/stdc++.h> #define re...

隔离村庄  题目描述 有 n 个村庄，通过 n-1 条双向路连通。Jyb 同学财大气粗，想要买其中的恰好 k 个村庄。为了做一些秘密的事情，他想要通过破坏原来的路，在保证自己的 k 个村庄相互连通的情况下，把这 k 个村庄与其他村庄隔离开。请问他应该买哪 k 个村庄，最少破坏多少条路    Solution      d   p   [   i   ]   [   j   ]    dp[i][j]   dp[i][j]表示以     i    i   i结点为子树, 制造大小为     j    j   j联通块所需要断的最少数目边数 则      d   p   [   i   ]   [...

P4768 [NOI2018]归程  题目描述 给出     N   ,   M    N, M   N,M的无向图, 每条边有海拔和长度两个权值, 每次询问给出水位线,起点, 问从起点出发到     1    1   1号节点的最小步行距离  路程 = 开车路程+步行路程 经过海拔不大于水位线的边需要弃车   Solution   以 海拔 建克鲁斯卡尔重构树 其中使用     n   s   t   [   ]    nst[]   nst[]表示每个树节点上方的重构树节点  预处理出     1    1   1节点到每个节点的最短路 预处理出重构树中每个节点子树中离     1    ...

D   y   n   a   m   i   c  <mtext>   </mtext>  R   a   n   k   i   n   g   s    Dynamic\ Rankings   Dynamic Rankings 给出一个长度为      N    N   N 的数列       A   i     A_i   Ai​, 要求支持  区间查询第      K    K   K 大 . 单点修改 .       N   ≤   1    0   5     N \le 10^5   N≤105  普通主席树是使用每个位置 (设为     i    i ...

P4127 [AHOI2009]同类分布  题目描述 给出两个数     a   ,   b    a,b   a,b，求出     [   a   ,   b   ]    [a,b]   [a,b]中各位数字之和能整除原数的数的个数。    Solution  发现题目有两个变量  数位之和 原数  于是必须想办法设计一个只有一种变量的数位dp, 发现唯有固定数位之和才可以在DFS中将取模作为状态方便地转移 记搜元素:  当前数位 数位之和 原数的模值   Code #include<bits/stdc++.h> #define reg register #define pb ...