ABC161 E - Yutori 题意 给你一个长度为n的字符串s（仅由’x’和’o’组成），要求你选出k个’o’且满足两个’o’中间相隔至少c个字符。 输出无论怎么选一定要选的位置。 思路 贪心 正序遍历贪心求最小位置记录在数组a中，倒序遍历贪心求最大位置记录在数组b中，当a[i]+b[i]=k+1的时候，无论何种方法选择到第k个选择时两种方法都会选到这个位置，输出这个位置。 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>P; const...

学军信友队趣味网络邀请赛 B.齐心抗疫 题意  给你一棵每条边均为1的树，求任意两点距离乘两端点中大的那个数的乘积最大为多少？ 思路 题意转化为公式就是求     d   i   s   [   x   ]   [   y   ]   ∗   m   a   x   (   a   [   x   ]   ,   a   [   y   ]   )    dis[x][y]*max(a[x],a[y])   dis[x][y]∗max(a[x],a[y]) 那么难点就在于求任意两点间的距离了。 这时候要抓住条件：这是一棵树！ 利用树的直径的性质DFS三次即可。 树的直径：若树上两点     u...

Dijsktra  适用条件：边权为正 相关应用：求最短路，打印最短路路径   初始化（如果求最短路求初始化所有节点为INF，所求的起点的为0） 找出一个未被标记的、     d   [   x   ]    d[x]   d[x]最小的节点     x    x   x，然后标记结点     x    x   x。 扫描节点     x    x   x的所有出边     (   x   ,   y   ,   z   )    (x,y,z)   (x,y,z)，若     d   [   y   ]   >   d   [   x   ]   +   z    d[y]>d[...

B. Dreamoon Likes Permutations 题意 给出一串     n    n   n个数字，定义如果一个数列中     [   1   ,   k   ]    [1,k]   [1,k]都存在且只出现一次，则它为一个“长度为     k    k   k排列”，问如何把给定数列划分成两段，使得两边都为一个排列。 思路 有一段一定为数组     a    a   a中最大值     m   x    mx   mx，另一段则是     n   −   m   x    n-mx   n−mx，对两种情况予以验证即可。 #include<bits/stdc++.h&g...

C. Eugene and an array 题意 给你一个长度为n的数组，求不含和为0的子串的个数。 思路 前缀和 思维 前缀和     p   r   e   [   i   ]   =   p   r   e   [   j   ]    pre[i]=pre[j]   pre[i]=pre[j]意味着      a    i   +   1     ∼    a   j     a_{i+1} \sim a_j   ai+1​∼aj​这一段的和为0，则所求字符串不应该包含这段，令     p    p   p为     p   r   e   [   i   ]    pre[i]  ...

NC13249 题意 给你一棵树，每个节点     i    i   i上有一个值     k   [   i   ]    k[i]   k[i]，一开始树上所有节点均为白色，要求你每次选择一个白色节点染色，从该节点往根的链上小于     k   [   i   ]    k[i]   k[i]的均被染色，求最小染色次数为多少？ 思路 DFS 贪心 首先叶子结点是一定要染色的，我们考虑如何返回的时候构造最优方案，我们维护两个数组。 回溯路径所能染色到的最远距离     k   [   x   ]   =   m   a   x   (   k   [   x   ]   ,   k   [ ...

NC13611 题意 一棵有n个结点的树，我们有k种不同颜色的染料给树染色。当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同时，染色方案是合法的。请统计方案数。 思路 把题目转化为给你一颗n结点的树，将其分成     i  <mtext>   </mtext>  (   1   ≤   i   ≤   k   )    i ~ (1\leq i \leq k)   i (1≤i≤k)个连通块涂上不同的颜色，此时发现染色方案的数量与这棵树的形状无关，仅与k和n有关，将其看为一个点集，每个点集可以涂一种颜色。        D   P ...

D. Minimum Euler Cycle 题意 给你一个     n    n   n个结点的完全有向图，求其字典序最小的欧拉回路，输出     l    l   l到     r    r   r之间的结点为多少。 思路 构造 找规律 前缀和 二分 结合样例找规律容易发现路径为 1 2 1 3 1 4 1 5 … 1 n 2 3 2 4 2 5 … 2 n 3 4 3 5 3 6 … 3 n … 1 比赛的时候由于我没有注意样例中99995 9998900031 9998900031这一组数据，直接构造是不行的，会TLE。 这里要用到前缀和+二分了，先前缀和到每个区间末尾有多少个数，然后...

NC5026E 题意 把原题意转化为给你一个长为     n    n   n的字符串，求至少有     k    k   k个相同且不相交的长为     x    x   x(可为     0    0   0)的子串，      x    m   a   x      x_{max}   xmax​为多少？ 思路 二分+哈希字符串 时间复杂度     O   (   n   l   o   g   n   )    O(nlogn)   O(nlogn) 这道题不要求得到所求子串为什么，而要求子串所能取得最大长度，且答案具有严格单调性，故可以二分答案。 那么如何验证？首先预处理字符串Has...

F - Select Half 题意      n    n   n个数里选     ⌊    n   2    ⌋    \lfloor\frac{n}{2}\rfloor   ⌊2n​⌋个数，求最大值为多少？ 思路 我想不到下面的DP是因为我菜，我刷的DP题太少了，那就多刷一点就能想到了。 DP 令     f   [   i   ]    f[i]   f[i]表示     i    i   i个数里选     ⌊    i   2    ⌋    \lfloor\frac{i}{2}\rfloor   ⌊2i​⌋里最大的数为多少。 预处理     s   u   m   [   i  ...

E - Sum of gcd of Tuples (Hard) 题意       ∑     a   1    =   1    K     ∑     a   2    =   1    K    .   .   .    ∑     a   N    =   1    K    g   c   d   (    a   1    ,    a   2    ,   .   .   .   ,    a   N    )  <mtext>   </mtext>  (   m   o   d   1   e   9   +   7   )    \sum_{a_{1}=...

NC14247 题意 给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。      1   ≤   n   ≤   1000   ,  <mtext>     </mtext>  0   ≤   数   组   元   素   <   100000    1\leq n\leq1000,~~~0\leq数组元素<100000   1≤n≤1000,   0≤数组元素<100000 思路 枚举 预处理异或前缀和 为了便于我们求任意区间的异或和，预处理异或前缀和。 为了避免区间重叠，我们枚举两个区间的分界点     ...

NC14248 题意 给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同 思路 DFS 树 数据结构 这道题和CF1339D十分相像，有兴趣的可以做一下。 把题意转化为给你一颗n个结点的树，树上所有的边权值为1，求树上任意两点距离为偶数的点的个数。 问题就转化为了如何获取树上任意两点的距离是否为偶数呢？ 图论相关的问题离不开画图，所以我们简单画个图。 受CF1339D给我的启发，无根树可以找一个根先固定，而根如果找任意点会带来讨论的麻烦，所以找一个叶子节点最合适不过。 令任意一片叶子为根节点，并及以叶子结点为...

CF1338 B. Edge Weight Assignment 题意 一棵n个结点的树，求最小和最大需要多少个不同的路径来构造树的路径权值，使得任意两片叶子的路径异或和为0。 思路 首先这是一棵无根树，以其任意一个叶子结点为根。（避免讨论） 首先考虑最小，最小要么为1要么为3。 为1的情况是任意结点到根节点的距离为偶数。 为3的情况是只要有一个结点到根结点的距离为奇数。 这里仅判断奇偶有两种写法，1是记录深度，2是利用异或。 1^1=0 0^1=1 接着考虑最大，我们发现当一个父节点直接与＞1个叶子结点相连，则由于那些叶子结点到父节点的距离为1，所以他们的边权值一定相等，故这些边视为一样的。...