CoolGuang!

题解

atcoder(4) kuangbin刷题记录(9) Task In College(1) 二分查找(5) 位运算(2) 动态规划(10) 博弈论(1) 图论(27) 备忘录(2) 大模拟(7) 字符串算法(3) 思维锻炼(14) 搜索(9) 数据结构(10) 数论(6) 暴力与随机数(3) 未归档(8) 矩阵练习(6) 组合数学(3) 计算几何(1) 计算机知识/辅助工具(1) 贪心算法(4) 路漫漫其修远兮(2)

/ 注册

全部文章 / 题解（共21篇）

[CQOI2007]涂色PAINT | 区间dp

考虑区间dp即可我们可以发现在左右端点颜色相同的时候越在外面的颜色越早涂是最好的例如：RGR先涂R比先涂G好根据上述情况很容易发现：当左右端点颜色一致时只需要扩充即可不需要在涂色了因为涂的颜色已经早涂了如果颜色不一致，就是区间dp的套路，枚举从哪个中间点分开 Code: /*** ...

每日一题题解

2020-07-29

0 562

区间权值 | 前缀和

题目思路首先注意到这个式子表示的含义即为，所有区间的区间和*区间长度的累加和把式子拆开: 设a数组的前缀和是fa,b数组的前缀和是fb ( fb(r)-fa(l) )* b_(r-l) = fa(r)*b_(r-l) - fa(l)*b_(r-l) 所以说我们...

每日一题

2020-07-23

1 617

点权和 | 思维统计

题解：我试图去遍历邻接表（以为是水题），结果T飞了呀——m1e7，随便出点数据就可以卡了。看一下正解：用一个数组表示，当前这个点操作了几次，那么就如上图所示，绿色的点操作x次对此次操作的贡献即为2x，蓝色的点为1x。很显然x的操作次数的贡献为：x的度数+1。所以显然需要维护邻接点，但是...

每日一题题解

2020-07-15

2 720

矩阵取数游戏 | 区间dp

链接：https://ac.nowcoder.com/acm/problem/16645 来源：牛客网题目描述帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下： 1.每次取数时须从每行各取走一个元素，共n个。...

每日一题题解

2020-07-11

0 535

Alliances | LCA、dfs序

题意简化：首先给出一棵树，其次询问一个点集，求包含这个点集的最小生成树与询问点x的最短距离题目思路首先考虑，如何确定这个点集的最小生成树：首先跑一个LCA，找出所有点公共的LCA，那么这个最小生成树的点集根节点(也就可以确定了) 之后就可以考虑这两种情况： 1.如果询问点，不在这个子树内...

每日一题题解

2020-07-09

1 691

牛客每日一题 [SCOI2005]最大子矩阵

好久没更新牛客的博客了更新一下下链接：https://ac.nowcoder.com/acm/problem/20242来源：牛客网 [SCOI2005]最大子矩阵时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: ...

每日一题

2020-06-08

1 948

牛客每日一题华华给月月准备礼物二分

链接：https://ac.nowcoder.com/acm/problem/23049 来源：牛客网华华给月月准备礼物时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld...

每日一题题解

2020-04-16

0 668

牛客每日一题逆序对组合数学

这题思路非常巧妙求有多少个逆序对不妨转换为求每个逆序对的贡献每个逆序对的贡献即为这个逆序对在多少个串中出现所以总逆序对的个数：n*(n-1)/2 对于每个逆序对而言，它可以在:2^(n-2)个子串里出现 ...

每日一题题解

2020-04-15

0 562

每日一题 TreePath 树形dp+合并

链接：https://ac.nowcoder.com/acm/problem/14248 来源：牛客网 Treepath 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32768K，其他语言65536K 64bit IO Form...

每日一题题解

2020-04-14

0 567

牛客树形dp —— 黑白树

链接：https://ac.nowcoder.com/acm/problem/13249 来源：牛客网题目描述一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。你需要通过一系列操作使得最终...

每日一题题解

2020-04-07

0 841