codeforces
- 1401F 线段树题 我们可以考虑为反转 子树
- 1579g 可以二分 因为会有负数 所以我会把 开始的位置 为 0-mid 然后dp
- 459e 边权从小到大加入 没有后效性 直接dp
- 372b 前缀和
- 1151e 点=边+连通块 见了两次了 这下记住了
- 505C 直接dp复杂度不对 我们优化一下 dp[i][j] 表示目前到了i 和d偏移了j的总权值
因为j有可能小于0 所以我们把原点改一下 - 1109b 大力分类讨论 注意偶数 回文串要递归讨论
或者直接暴力 - 1527e
dp[i][j]=max(dp[k][j-1]+val(k+1,i));
前i个数分为j段的最大值
维护每个数前一次出现的位置
滚动优化一维 更新的时候 (0,la[a[i]]-1)都加上 i-last[a[i]]
然后线段树查询 (0,i-1)最大值即可 - 1324f
黑点权值赋值为-1 先统计出1号点的答案 然后转移的时候
如果dp[v]>0 dp[v]=max(dp[v],dp[u]) 否则 dp[v]=max(dp[v],dp[u]+dp[v]) - 1209d
转化为连通块数量即可 - 1304e
lca板子只要 询问的距离和他们的距离之间的奇偶性相同即可 - 1401d
非常经典的题目 我们只需要考虑每条边会有多少贡献即可 - 346 b kmp优化dp lcs的加强版
- 817d 单调栈 统计出每个数字向左向右的最大最小值 主要是会有相同的数 所以左开右闭或
者左闭右开即可 - 710e 考虑到每个状态虽然可能由后面转移过来 其实都是可以和前面的某些状态等价的
0 dp[i]=min(dp[i-1]+x,dp[i/2]+y)
1 dp[i]=min(dp[i-1]+x,dp[(i+1)/2]+x+y) - 1343e 先bfs 或者dij 跑出最短路 然后枚举中间点贪心
- 914e 点分治板子 状压出状态 然后 i^j=1<<k i^j=0 细节比较多
- 1009f 长链剖分优化dp板子题
- 1430b 贪心考虑就是前k+1大的和
- 1180b 发现变为负数会增大 那么我们就贪心把所有数变成负数 最后再看贡献是负数 就把最小的负数变回正数即可
- 1157c2 贪心考虑 主要判断相等时候 看谁的上升长度最长就选谁
- 1165e 算出每个数的贡献 差值越大值越小 然后算一下每个的次数 ×一下就行
- 1185d 我们可以先算一下第一个数和最后一个数 如果没问题的话我们的公差就有了 然后就挨个判断就行了
- 1311d 暴力nlgnlgn 注意需要加常数 比如 3500 9999 9999 那么我们就超过1e4了
- 274a 把他们的倍数当成一条链 那么每条链就可以取 (len+1)/2 加起来就行
- 926b 算出最大公约数 就是两两之间的距离
- 1064 b cout<<(1ll<<(__builtin_popcount(x)))<<endl;
- 1085b 我们只要保证mod 的值最大即可
- 1791d 统计出前后缀 直接遍历 乱搞就行
- 1791e 先把他们的绝对值全部相加 如果负数为偶数就是答案 否则把一个变成负数就行
- 1791f 分析到修改到1-9就是原数所以我们直接暴力就行
- 1085d 其实中间的结点都是可以直接缩点的 我们考虑度数为1的结点即可
- 1355d K>=2N 输出1 小于无解
- 1826d 枚举中间的数 我们发现相邻两个数的差如果为1的话就没有贡献了 所以我们统计一边前缀和后缀 pre[i]=max(pre[i-1],a[i]) suf[i]=max(suf[i+1],a[i]) 计算出前缀和后缀的最大贡献即可
牛客
- 智乃酱的子树查询类问题-： 将询问离线 用动态开点权值线段树维护
考虑长链剖分 +线段树 multiset 维护同一深度的点 - DongDong数颜色 ： dsu板子题 或者线段树合并
- 小 Q 与树 ： 树链剖分喵喵题 我们按照权值从大到小排序 简化一下式子发现最难维护的
是加入的点 和所有的点的lca dep之和 其实有个tag就是 每次加入的时候1-u
全部+1 然后查询1 -x 的权值和就行了 很经典 - 小睿睿的伤害 ：
dsu on tree 预处理出每个结点的所有因子 暴力合并
首先处理 该节点与重儿子的关系 然后将该结点贡献加入 然后处理轻儿子 - 旗鼓相当的对手 ：
长链剖分 on ans[u]+=cnt[l[u]+K-k]sum[x]+cnt[x]sum[l[u]+K-k];
dsu on tree 和上一个题做法一样都是维护lca的贡献
d[a]+d[b]-2d[t]=k
d[a]=2d[t]+k-d[b]
atc
- abc 235e 判断两点之间的最大值是否大于等于k lca即可
- abc252d 正难则反 我们可以选三个 然后减去选两个相同和选三个相同的情况
或者直接枚举三元组中间的那个 - abc028d 分情况 第一个小于k第二个等于第三个等于 然后就是固定两个其他一个随机 加起来就行
- abc178e 曼哈顿切比雪夫距离 然后我们把转化后的x 和y 排序 那么就是max(x的差值 y的差值)
- abc166e a[i]-i=-a[j]-j 之间遍历计算贡献就行就行
- abc134e 转化为最长严格下降子序列
- abc253e dp[i][j] 前i个数最后一个为j的方案数 推出式子后发现可以前缀和优化dp
- abc233h 曼哈顿距离转换为切比雪夫距离二分 二维数点即可
- abc247e 求最大值为x最小值为y的区间个数 容斥 f(l,r)表示 l<=a[i]<=r的区间个数 答案为 f(l,r)-f(l+1,r)-f(l,r-1)+f(l+1,r-1)
- arc 090e 正难则反 用总的最短路的条数 减去在断点处和边上相遇的次数即可
注意在边上相遇的话应该是 d1[u]+w+d2[v]=mindist &&d1[u]+w>d2[v] - abc237d
- arc140b 贪心好题 我们发现aaaarccccc可以通过消除ac一直消除 但是我们还需要找到偶数次消除r的 我们把每个r可扩展长度扔到multiset 然后贪心的模拟即可
hdu
- 5977 点分治 k=1的时候特判一下
状压+子集和dp 容斥这种写法比较无脑 统计贡献的实现直接从重心开始
还有就是直接计算贡献 从重心儿子开始记录 然后主要考虑到重心是端点的情况 最后还需要×2
gym
- gdcpc I 二分答案然后按照行排序 再按照列排序最后check
文章来源地址https://www.toymoban.com/news/detail-480232.html
文章来源：https://www.toymoban.com/news/detail-480232.html
到了这里，关于日常刷题 无代码（长期更新的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
