凡尔赛卷卷

分类

做题笔记(85) 学习笔记(16)

/ 注册

全部文章（共101篇）

洛谷多校A T122393 À la Volonté du Peuple

T122393 À la Volonté du Peuple 题目链接题目大意：给一个有边权的无向图，有自环，有重边。一个火从1点开始烧，烧完之后就变成了灰烬（也就是火不能两次到达1点）火会延续到没有烧过的边，两个火苗相遇的时候会爆炸，问爆炸的次数。这个题，，哎我又菜了。想到了最短...

2020-09-15

0 555

cf 528 div2 D 图论思维

D. Minimum Diameter Tree 题目链接题目大意给一棵树和一个s ，s代表树上的边权和。边权为非负数。让给所有边赋边权，使得树的直径最小。怎么做，，，我不会太菜了。。感受到了思维的力量。题解给所有叶子节点（度数为1的点）所连的边赋值，其他边赋值0，也就是任...

2020-09-15

0 423

判断图是不是连通同构。

洛谷多校2场E 题目链接题就是给两个无向图。往图里加边，问是不是两个可以在第一个图中相互到达并且在第二个图中也可以相互到达。第二个图中可以相互到达的在第一个图中也要相互到达。。用讲题大佬的话说就是是不是连通同构。连通性是不是一样的/ 题解起初想到了并查集，但是不会处理。大佬给的题解： ...

2020-09-15

0 366

acwing 239.奇偶游戏

acwing 239.奇偶游戏题目链接题目大意：有长度为n的01序列，给出m个描述 l , r ,奇/偶。表示l~r区间里的1的个数有奇数个或偶数个。问第几个描述与前面的矛盾。输出k - 1； n：1e9； m：1e4；我还是太菜了做的时候一下就想到了并查集。奇数为1，偶数为0...

2020-09-15

0 978

cf div 2 Bicolorings dp

Bicolorings 题目链接题意有一个2*n的格子，每个格子可以涂成白色或黑色，然后根据涂完的颜色可以分成连通块（白色跟白色连通，黑色跟黑色联通）然后问连通块的数量是k的时候有多少种涂法。。我还是菜了啊想不到dp数组表示啥，想到了这个题就很简单了。题解： dp[1000]...

2020-09-15

0 332

树 dp div2 D - GCD Counting

D - GCD Counting 题目链接题目大意给一棵树，每个点的点权，然后问路径上的所有点权的gcd > 1的最长路径是多大。这个感觉就树形dp了。。但是菜鸡L不会写。。。点的个数n 1e5. 点权是小于2e5的刚开始想到了先把点权的质因子弄出来。然后dfs的时候对每个质...

2020-09-15

0 474

树上启发式合并洛谷多校4 A

题目链接题目大意给一棵有点权的树。根节点是1号节点，让找两个点，然后保留这两个点到根节点的路径，把其他的点删了。使得图上剩余点的权值异或和最大。怎么说呢？没干出来，，想到了字典树求一对异或值最大的点。然后求一个树上点的前缀和想着枚举一个lca然后再枚举每一个子树，，但是这个肯定是...

2020-09-15

0 470

洛谷多校补题图

Voluntary Hotel 题目链接题意: 有点乱。。。有n(1e4)个点。共有m(1e4)条无向边边。有边权，边权是两个点的距离（1e9）,其中有p（100）个点是医院，第 i 个点在点 yi[i] 处，q个宾馆，第 i 个馆在点 y[i] 处，可以最多容纳 h[i] 个人，有 r...

2020-09-15

0 481

CF div1+2 E.Trips

Trips 题目链接题目大意: 共有n（2e5）个人，刚开始都不认识，有m（2e5）天，第 i 天xi和yi认识了，认识不会传递，也就是a认识b，b认识c，a不一定认识c。这些人每天都想去旅游，如果每个人有他的k个朋友去旅游他才去。问每天最多去多少人。分析一下。。可以看成一个图，刚开始是...

2020-09-15

0 443

洛谷多校补题 5 B

Bolshevik 题目链接题目大意有n（1e6）个人你是第m个人第i个人有ai块钱，其中bi块钱在钱包里，如果偷了第i个人的钱，他的钱就会变为ai - bi 你是一个小偷，至少投多少个人的钱才能变成这n个人里最有钱的人（可以有人跟你一样有钱）怎么做？贪心。。先按ai排序，为什...

2020-09-15

0 483