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)

/ 注册

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

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

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

题解

2021-02-26

1 844

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

题目大意：每个装备给出两个属性值，每次只能选择一个从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

兔子的区间密码 | 位运算

这是个结论题，又不是个结论题 —————————————————————————————————————————————————— 显然可以推出来，l,r从高到低前面相同的几位是没有贡献的所以直接异或掉即可ll temp = l^r 最主要的在于如何确定最大值因为l,r的前几位都被异或掉了，也就是...

每日一题题解

2020-07-30

0 502

Xor Path | 思维转换

介绍两种思路，一种被卡掉了注意一下这个异或和是指所有path(i,j)的异或首先从一个根出发，算出跟到点x的路径异或为b[x] 那么对于两点的path(i,j)的答案即为：b[x]^b[y]^a[lca] 由于最终答案又是异或也就是说path(i,j)表示为三个数异或然后在异或显然对于每一个...

每日一题题解

2020-07-29

1 673

[CQOI2007]涂色PAINT | 区间dp

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

每日一题题解

2020-07-29

0 562

【Newcoder】2020牛客暑期多校训练营（第三场） E - Two Matching | dp、结论

题目链接：https://ac.nowcoder.com/acm/contest/5668/E 题目大意：给出一个序列定义一个序列的权值为：，其中p一个全排列问第一小和第二小的序列的权值和其中对p有要求：满足并且并且第一小与第二小的排列任何位置都不相同。题目思路：根据可知： i在全...

题解

2020-07-19

3 631