B. Xenia and Colorful Gems 题意 给你三个数组长度分别为     r   ,   g   ,   b   (   1   ≤   r   ,   g   ,   b   ≤   1   e   5   )    r,g,b(1\leq r,g,b\leq1e5)   r,g,b(1≤r,g,b≤1e5)，从中分别选出一个数     x   ,   y   ,   y    x,y,y   x,y,y，问     (   x   −   y    )   2    +   (   y   −   z    )   2    +   (   z   −   x    ) ...

A. Linova and Kingdom 题意 给你一颗     n    n   n个节点根为1号节点的树，选     k    k   k个城市作为工业城市，其余为旅游城市，工业城市的使节每经过旅游城市开心值+1，求所有工业城市的使节到1号节点的开心值的和最大为多少？ 思路 贪心 dfs  很容易看出来如果只选一个，一定选距离根节点最远的叶子，我们思考第四个为什么选2而不是3和4，因为选3和4，会减少其子树节点的开心值。（因为我们选这个点，根据贪心我们肯定已经选了所有他子树的节点）      每   个   结   点   的   贡   献   值   =   到   根   节   ...

POJ3585 题意 给定一棵     n    n   n个节点的无向带权树，要你找出一个节点作为根，向叶子节点流水，使流水量最大。 思路 换根DP 这种题往往都是先从某个点出发     D   F    S   1     DFS_1   DFS1​，求出以这个节点     t    t   t为根的答案，并记录与答案相关的数据到数组中。 然后     D   F    S   2     DFS_2   DFS2​从     t    t   t节点出发，记录换根的答案，其中所有根的最大值就为所求值。 难点在于该如何去找寻其中的递推关系式。      d    d   d数组表示该点的最...

D. Constant Palindrome Sum Question 给定一个长度为      n    n   n 的数列，     n    n   n 为偶数，保证每个元素在      [   1   ,   k   ]    [ 1 , k ]   [1,k] 之间。 每次操作可以把某个位置的数字变成      [   1   ,   k   ]    [ 1 , k ]   [1,k] 内的任意数字。 要求让这个数列满足：对于所有的     i   ∈   [   1   ,    n   2    ]   ，   a   [   i   ]   +   a   [   n   −...

E. Weights Distributing Question 给定由     n    n   n个点，     m    m   m条边构成的无权无向图和     m    m   m个权值以及三个点     a   ,   b   ,   c    a,b,c   a,b,c。问如何分配这     m    m   m个权值才能使      l   e    n    a   →   b     +   l   e    n    b   →   c      len_{a→b}+len_{b→c}   lena→b​+lenb→c​最小 Solution 有两种情况：       a...

ABC163 E - Active Infants Question 将一个数组重新排序，每个元素的收益为      a   [   i   ]   ×   l   e    n    m   o   v   e      a[i]\times len_{move}   a[i]×lenmove​，求排序后的最大收益。 Solution DP 容易想到一个大的值无非放到左边和右边，哪边增加的多放到哪边，但是可能存在放到两边值一样的情况，那么这个时候的选择会影响到之后的选择，所以贪心是不对滴，这里要用到DP。 先排个序，从大到小，然后每次先选未选过的最大的，枚举其在左右的两种情况。      d...

Question 一个n个数码位的分数板，每一个数码位都是一个七段数码管，现在给出每个数码位的显示情况，问再点亮k段数码管的话能显示的最大的数是多少，如果不能构成一串数字，就输出-1. Solution  贪心+DFS+剪枝 我们要构造的数最大，那就是高位尽可能大。直接爆搜TLE，考虑优化加入数组     v   [   i   ]   [   j   ]    v[i][j]   v[i][j]表示到第     i    i   i个点，还剩     j    j   j次操作的时候是否能找到可行解，若为true代表找不到可行解。      O   (   n   ∗   10   ∗   ...

D.Multiple of 2019 Question 给一个字符串S，求有多少个子串在十进制下为2019的倍数。  Solution 前置知识：      S   [   l   ]   [   r   ]   ×   1    0    l   −   r     =   s   [   l   ]   [   k   ]   −   s   [   r   ]   [   k   ]    S[l][r]\times10^{l-r}=s[l][k]-s[r][k]   S[l][r]×10l−r=s[l][k]−s[r][k] 若     S   [   l   ]   [   k   ...

D - Multiple Testcases Question 给定      n    n   n 个数      m   [   i   ]    m[i]   m[i]，每个     m   [   i   ]    m[i]   m[i]都在      [   1   ,   k   ]    [1,k]   [1,k]的范围内 再给定     k    k   k个数     c   [   i   ]    c[i]   c[i] 要求将所有的     m   [   i   ]    m[i]   m[i]进行分组      c   [   i   ]    c[i]   c[i...

CF1348 C. Phoenix and Distribution Question 给你n个字符，要求你将其分为k份，每份个数至少有1个，使得新组合的字符串中字典序最大的字符串的字典序尽可能小，打印这个字符串。 Solution 分类讨论 字典序最小，先排序。        s   1    ≠    s   k     s_1\neq s_k   s1​​=sk​，答案为      s   k     s_k   sk​，此时剩余部分直接放在      s   1     s_1   s1​后面所得解最优。       s   1    =    s   k   <mtext&g...

CF1348 D. Phoenix and Science Question 一开始有1个细菌，他的权值为1。白天的时候1个细菌可以分裂成2个，也可以不分裂，晚上的时候1个细菌会增加权值1，求最少要多少天能够到达所有权值的和恰好为n，并且给出对应n天每天有几个细菌要分裂。 Solution 设需要     T    T   T天。 最快的增加方法为每次所有细菌分裂为     2    2   2个，晚上加上分裂后细菌的数量，那么     T   =   l   o    g   2    (   n   )    T=log_2(n)   T=log2​(n)。 我们构造一个满足     T ...

ABC 165 D - Floor Function Question      f   (   x   )   =   f   l   o   o   r   (   A   x   /   B   )   −   A   ×   f   l   o   o   r   (   x   /   B   )    f(x)=floor(Ax/B) - A × floor(x/B)   f(x)=floor(Ax/B)−A×floor(x/B) 求     x   ≤   n    x\le n   x≤n使得     f   (   x    )    m   a   x      f(x)_...

AtCoder Beginner Contest 166 D - I hate Factorization Question 求任意一组满足      A   5    −    B   5    =   X    A^5-B^5=X   A5−B5=X的      A    A   A 和      B    B   B。 保证必有解。     1   ≤   X   ≤   1    0   9     1\le X\leq 10^9   1≤X≤109 Solution 暴力出奇迹，由于     10    0   5    >   1    0   9     100^5>...

CF180 D. Name Question 给定两个字符串     s    s   s和     t    t   t，若重新排列     s    s   s之后能使得     s   >   t    s>t   s>t，则输出字典序尽可能小且满足条件的     s    s   s，否则输出     −   1    -1   −1。 Solution 贪心+分类讨论+DFS 这里思路应该是十分清晰的，主要我在想如何实现会比较方便，看了一下当时比赛第一个交的人，交的是一份DFS，一个一个字符往下去遍历，挺适合这里的，而且也好写。      s    s   s的前缀...