__故人__

题解

CF(8) UOJ(1) 每日一题(3) 牛客小白月赛27(10) 算法模板(10) 随笔(20)

/ 注册

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

题解2023牛客寒假算法基础集训营3

A 不断减损的时间简单题，直接贪心，对于正整数那便是能除就除。负数不操作就行。 ">using namespace std; #define pii pair<int,int> #define ll long long int read() { int x = 0,f = 0;cha...

2023-01-20

8 915

题解2023牛客寒假算法基础集训营2

A Tokitsukaze and a+b=n (easy) 简单题，做法很多。 ">using namespace std; #define pii pair<int,int> #define ll long long int read() { int x = 0,f = 0;cha...

2023-01-19

7 1015

[JLOI2016]侦察守卫

分析比较奥秘重重的状态设计。定义为覆盖以为根的全部子树，而且向上覆盖了层节点。表示，覆盖了以为根，子树节点深度的全部节点。初始化对于任何情况。选择这个节点的转移。如果当前点是关键点，那么。由于必须要覆盖这个节点，那么初始化为必选状态。如果当前点不是关...

2020-12-03

7 937

[AHOI2009]CHECKER

分析对于两个问题，我们可以分开讨论。我们发现如果有两个相邻的红色的砖块（不包括节点），那么在开始之后就可以使棋子到达任意一个地方，那么我们就根据是否有两个相邻的红色砖块来讨论。无相邻的情况，我们可以发现，直接把棋子放在偶数位置是最优的。那么第一问的答案就是偶数位置的个数，而第二问就是偶...

2020-12-03

8 911

生涯回忆录

题意求出所以子集中最小没有出现的正整数之和。分析我们可以考虑一个元素的贡献，我们先考虑如果这个数可以作为答案，那么的每个元素至少选取了一次。那么根据乘法原理，的总方案为。表示这个数出现的次数。那么的元素，可以选也可以不选总的方案数为。上面的指数也可以通过前缀和维...

2020-11-23

8 807

离别

分析欢迎私聊，感觉说的不太清晰。我们考虑如何保证每个区间的某一个种类个数达到。这个我们可以考虑离线询问，将的询问差分成的答案。那么我们先把一个询问拆分成两个，再来考虑前缀的做法。我们对于每个数，保留它的前一个和他相同相同的元素。那么枚举的右端点到了，那么左端点在都是可以...

2020-11-23

16 883

Network

分析考虑求出边双连通分量，那么题目其实就是在问，有多少个桥。那么由于边双缩点之后，整个图变为树。那么树的边数就是答案。考虑新加一条边之后的贡献。那么就是树上距离，在将这个链上的权值变为。这个考虑树链剖分或者维护，写完才发现，好像直接并查集时间复杂度好像还要更优。这里采用了实现，时间总复...

2020-11-20

8 990

Tree with Small Distances

题意你有一颗个节点的有根树 (以号节点为根) ，求最少加入多少条边之后使得根节点（即 11 号节点）到这棵树上任意一点的距离不大于。分析我们考虑覆盖一个节点有多少种方法。在父亲节点连一条边。在儿子节点上连一条边。在当前节点上连一条边。这样我们发现并不是很好做，考虑叶子...

2020-11-19

7 978

Bookshelves

题意要求分成恰好组，每组的权值为。要求最大化。分析和位运算有关系，我们就要想到拆位。由于是要最大化权值，所以我们肯定是要优先满足高位。而每一位独立，所以我们可以直接枚举位数。定义表示前个已经分成了组，是否可以组成当前答案，表示现在枚举的答案。那么转移为。那么最后是...

2020-11-16

8 964

Qtree4

题意给出一棵边带权的节点数量为的树，初始树上所有节点都是白色。有两种操作：：改变节点x的颜色，即白变黑，黑变白。：询问树中最远的两个白色节点的距离，这两个白色节点可以重合 (此时距离为 ) 。分析无脑上点分树，每个节点维护两个堆维护子树中最大的长度，自己对父亲的贡献...

2020-11-16

7 608