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) 题解(27)

/ 注册

全部文章（共165篇）

[HAOI2015]树上染色 | 树形dp

题目大意题目思路看到树上问题就来补了没想到还真是个好题开始状态定义，定义代表以为根的子树，选择了个黑点，所达到的最大收益。显然不可以转移，因为不知道其他的点黑点和白点选择情况，这里就有后效性了所以考虑去除后效性【即不能对后面的状态产生影响】显然直接计算距离是不可取的，但是对于两两...

每日一题

2021-03-25

4 741

小G的LY数对 | 思维、容斥

这里是缅甸北部.. 写傻了的D 复杂度: 思路正确，但实现实现的有点傻了首先考虑后恰好有两位是1，怎么用数学语言表示：那么有：那么很显然，只需要保证，然后求相等即可。这样就可以先把一边用哈希存起来(被掉了),遍历另一边所有的结果。这时候得到的结果是包含的，考虑还满足上述式子：相...

题解

2021-02-26

1 844

小G的约数

这是个比较简单的整除分块吧.. 但是我不是数论选手，所以就先去写D了.. 这个题还是比较裸的，如果知道约数和的写法的话首先考虑直接求约数和不太现实，所以我们可以枚举约数，求约数对答案的贡献。首先1~n所有的约数最大值不可能超过n 所以我们可以考虑所有的约数，用f(i)表示i的倍数在n之前有多少个...

2021-02-26

2 874

Dima and Salad | 思维、01背包

题目大意：给出两个序列，询问是否存在一种选下标的方案使得: 也就说a和b要么一起拿要么一起不拿题目思路：因为状态被绑定，所以可以直接考虑他们绑在一起假设: 那么必然有：所以说可以让b序列每个数都,之后令也就说问题转换为了，求取的物品重量为0时，最大权值这样就可以直接01背包了...

每日一题

2021-02-04

0 732

阔力梯的树 | dsu on a tree

emmm.. 题意是计算每颗子树下，标号从小到大排列后，相邻项差值的平方和涉及到静态子数问题，就是经典解决方法了维护了静态子数的信息，所以只需要处理新加入的权值与当前权值的关系就好了记得今年牛客2020多校有个三角形的加入边与删除边，维护最小差值的，与这个思路类似首先把权值全部放入一...

每日一题

2020-12-30

0 742

游戏 | 二分图匹配、并查集

题目大意：每个装备给出两个属性值，每次只能选择一个从1的属性值开始选，每个装备只能选择一次，并且只能选择一个属性，问最多选择几个？题目思路：一个经典的套路因为路径已经确定，所以也就硬性要求了这一步该选什么 1 2 3 1 这个样例来说，假设第一件装备选择了1，那么第二件装备就没法选择，但是你会...

每日一题题解

2020-08-14

0 941

追债之旅 | 最短路变式

n<=1000 其实n<=10000应该也可以做考虑dis[i][k]代表从1出发到达i点经历了k条边的最小花费所以更新的话，也就像最短路那么去更新了 if dis[e][k+1] > dis[i][k] + w : dis[e][k+1] = dis[i][...

每日一题题解

2020-08-06

0 655

蓝魔法师 | 树形dp、组合数学

考虑树形dp与组合数学结合定义dp状态 dp(i,k) 代表 i的子树全部合法且i的连通块大小是k 那么显然对于任意一个节点u来说初始:dp[u][1] = 1 接下来枚举每一条边，对于一条边来言有删除与不删除两种状态： 1.删除：删除此边，那么就意味着当前以u节点连通块大小为k的方案数都可以...

每日一题题解

2020-08-05

6 1102

购物 | 基础dp

题目描述：中文题目思路：考虑前i个物品，满足连续能吃的情况下剩余k个，所需的最小费用。答案即为dp[n][0] 接下来考虑dp状态转移首先枚举第几天、然后今天要买多少个(0~m) 那么买的个数就可以由上一天转移过来此时注意dp的条件：满足连续能吃所以说假设枚举今天要买k个，昨天剩余j个，...

每日一题题解

2020-08-04

0 701

小A的最短路 | LCA

首先题目给出是一棵树我们可以知道树上两点路径唯一其次又有一条额外免费的边所以我们可以这么考虑，x,y之间的路径要么是在原树上由x到y，要么经过额外免费的边对于每个询问，取三种情况最小值即可 ll n,m,p; struct node{ int e,next; }edge[maxn]...

每日一题题解

2020-07-31

2 728