royzhu

题解

/ 注册

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

除2！

读完题，我先想到贪心。仔细一想我觉得不对，k竟然有1e9.用优先队列做岂不是要T飞了。然后想到用，先排序再用两个队列维护。仔细一想，时间复杂度还不是跟k有关。回想：每个数最多被除31次（ai<=1e9）总共被除nlog（1e9）（底数为2）每次插入or删除要o（logn）总时间复杂度有点慢，但...

2020-12-04

0 590

背包

此题用生成函数解决。思路考虑每一个要求的生成函数。（只选条件中的物品） x的第i次项的系数表示选i个有多少种可能(1看作x^0)("^"看作次方)（0<x<1）；c（m，n）=n！/（m！*（n-m）！）条件一：(肥宅快乐水)1+x条件二：(大盘鸡)1+x+x^2条件三：(啤酒鸡)1...

2020-11-30

8 577

Network

Network题解题意：给一张n个点m条边的无向连通图，然后是q次连边操作（n<=1e5,m<=2e5,q<=1e3）边双连通图：一张无向连通图不存在桥。边双连通分量：无向连通图的极大边双连通子图。思路首先是把桥都给找出来。然后思考怎样连两点会对答案有影响。如果两点都...

2020-11-25

2 758

[SCOI2009]游戏

读完题我们可以分成两部分。第一部分是把n拆成由数字1~n组成的不同排列。如3=1+1+13=2+13=3第二部分是：排列中每个数的最小公倍数。每个排列的最小公倍数去重后的个数是答案。对于第二部分，我们想一想，可以发现，最小公倍数可以分为多个质因数。所以对于第一部分，我们要用n以下的质数组成n的排列。...

2020-09-26

0 601

联合权值

读完题我们会发现此题有树结构。我们以1为根结点。假设我们已经做完了x号节点（x可以是叶子节点）的儿子们（y号节点)，我们就在x号节点的tot加上y的tot。设maxx为与x连边的节点中点权最大值，每次maxx与y的点权的乘积就可能是最大值。设sum为与x连边的节点中点权之和，x的tot加上sum与y...

2020-09-19

0 824