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篇）

兔子的区间密码 | 位运算

这是个结论题，又不是个结论题 —————————————————————————————————————————————————— 显然可以推出来，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

区间权值 | 前缀和

题目思路首先注意到这个式子表示的含义即为，所有区间的区间和*区间长度的累加和把式子拆开: 设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

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

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

题解

2020-07-19

3 631

点权和 | 思维统计

题解：我试图去遍历邻接表（以为是水题），结果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