题目链接 题意：给你一个有根树，假设有k个叶子节点，你可以给每个叶子节点编个号，要求编号不重复且在1-k以内。然后根据节点的     m   a   x   ,   m   i   n    max,min   max,min信息更新节点的值，要求根节点的值最大。 解法：考虑树形dp，若当前节点是     n   o   w    now   now,我们可以假设编号最大的一些数分布在当前节点的子节点中，显然，若当前节点为叶子节点，那么这个这个编号就是最大的。然后往上回溯，假设当前节点取得是     m   a   x    max   max，那么就从子节点中取最大的数为当前节点的答案，如果...

题目链接 题意：给你一棵树，让你尽可能删除多的边使得剩余所有的联通组件都是偶数大小。 思路：考虑dfs，从1出发，若当前节点的子节点和自己的数目是偶数,说明当前节点和父亲节点的边是可以删除的，答案+1，因为最开始的节点没有父节点，所以最后答案-1 #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; LL gcd(LL a,LL b){return b?...

题目链接 分析一下题意可以得到题目要求的是满足下面这个 公式的不同的     i   ，   j    i，j   i，j的方案数; 即     (    i   2    +    j   2    )    m   o   d     <mtext>   </mtext>  m   =   0  <mtext>   </mtext>  (   n  <mtext>   </mtext>  ≤  <mtext>   </mtext>  i  ...

题目链接 大意：给你n个物品和m种优惠方式，让你买k种，问最少多少钱。 思路：考虑     d   p    dp   dp,     d   p   [   x   ]    dp[x]   dp[x]表示买     x    x   x种物品的最少花费，然后遍历     m    m   m种优惠方式就行转移就好了。 #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mp make_pair #define pb push_back using name...

题目链接 大意：给你两个数     X   ,   Y    X,Y   X,Y,让你找两个数     a   ,   b    a,b   a,b，满足     a   +   b   =   X   ,   l   c   m   (   a   ,   b   )   =   Y    a+b=X,lcm(a,b)=Y   a+b=X,lcm(a,b)=Y. 思路：枚举     g   c   d   (   a   ,   b   )    gcd(a,b)   gcd(a,b)，假设     g   c   d   (   a   ,   b   )   =   k   ，   那 ...

题目链接 思路：枚举第一列的可能种数，然后递推即可，中途判断是否满足条件，最后再判断最后一列是否满足条件即可。 #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; LL gcd(LL a,LL b){return b?gcd(b,a%b):a;} LL lcm(LL a,LL b){return a/gcd(a,b)*b;} LL powmod(LL ...

题目链接 题意：给你给无限长的序列     A    A   A，让你求出      ∑    i   =   l    r     A   i     \sum_{i=l}^{r}A_i   ∑i=lr​Ai​. 思路：转化一下，即求      ∑    i   =   1    r     A   i    −    ∑    i   =   1     l   −   1      A   i     \sum_{i=1}^{r}A_i-\sum_{i=1}^{l-1}A_i   ∑i=1r​Ai​−∑i=1l−1​Ai​。那么问题就好解决了，不断的倍增加上当前段的贡献，最后去掉多余的即...

题目 思路：由于数位最大为10，所以我们可以分出所有3出现位置和个数的所有情况，最多也就      2   10     2^{10}   210种情况，然后对每种可行情况进行     d   f   s    dfs   dfs.      d   f   s    dfs   dfs进行的每一层说明，前面     0   −   n   o   w    0-now   0−now都是跟给定的数字相同的，那么当前这一位就有两种取法，一个是小于给定的数字，一个是等于给定的数字。      1.    1.   1.小于给定的数字我们好解决，后面的位置没有被3放的位置我们可以放任意的数字，但是...

题目链接 题意：让你求这个公式的值。 思路：公式中最重要的就是对数，对2取对数并向下取整，那么答案就是一块一块的. 我们遍历每一个左端点      l   i     l_i   li​，对每种可能的取对数得到的值进行讨论。 假设当前对数值是     x    x   x，那么     x    x   x贡献的区间     x   ,   y    x,y   x,y满足一个条件      s   u   m   [   x   ]   −   s   u   m   [    l   i    −   1   ]   >   =    2   x     sum[x]-sum...

题目链接 给你一个     n    n   n，让你构造     n   −   1    n-1   n−1个式子使得最后剩余一个     24    24   24。 首先     24   =   2   ∗   3   ∗   4    24=2*3*4   24=2∗3∗4，当     n   <   4    n<4   n<4时无解。      n   >   4    n>4   n>4时必有解。 我们分奇偶进行讨论。 1.偶数时，我们对     l   ,   l   +   1   ,   (   l  ...

题目链接 大意：给你一系列操作 1：     l   ,   v   a   l   ,   r    l,val,r   l,val,r，添加一个     v   a   l   存   在   于   [   l   ,   r   ]    val存在于[l,r]   val存在于[l,r]区间。 2.      i   n   d   e   x   ,   k    index,k   index,k问你存在于      i   n   d   e   x    index   index这个位置的第     k    k   k小数，若不存在输出-1； 思路：我们可以将1操作的区间...

题意：给你一个数组。 题目定义一个关系。两个数     a   .   b    a.b   a.b，当且仅当     ∣   a   −   b   ∣   ≤   2    |a-b|\leq2   ∣a−b∣≤2时，     a   ,   b    a,b   a,b在一个分组中，让你求出一个最大的分组，输出元素个数。 可以对任一位置的数进行加一或者减一 一次。 思路：考虑     d   p    dp   dp，先对数组进行排序，然后，     d   p    dp   dp数组为     d   p   [   i   ]   [   j   ]    dp[i][j]   d...

题目链接 大意：给你n个区间，第     i    i   i个区间     [    l   i    ,    r   i    ]    [l_i,r_i]   [li​,ri​]表示和第     i    i   i个左括号相匹配的右括号和这个左括号距离的范围。让你输出一种合法的序列。 思路：对于每一个右括号，和他相匹配的左括号肯定是离得最近的左括号。那么我们用栈进行模拟。对每个左括号先压入栈中，然后每次讨论栈顶元素，看是否可以放右括号，即栈顶元素的位置与放置右括号的位置满足这个左括号的区间要求。如果已经超过了范围就显然不成立，若还没到左区间的要求，就break.处理下一个左括号。 细...

题目链接 大意:给你一系列的点和区间，给每个点上一种颜色（共两种颜色），要求每个区间内的两种颜色数量的差不超过1. 思路：先排序从小到大，然后按奇偶这样分布不同的颜色。这样就保证每个区间内的颜色差不超过1. 妥妥的降智题啊。 #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; LL gcd(LL a,LL b){return b?gcd(b,a%b):...