标签 - BZOJ

? 解题记录 ? ? BZOJ ? ? 群论 ?    2019-01-05 11:59:18    524    0    0
Description Input 输入三个整数N,M,P 1< = N <= 53 1< = M < = 1000 N< P < = 10^ 9 Output 即总数模P后的余数 Sample Input 3 2 97 Sample Output 4 论文里写的很好,觉得自己也写不出比它好的题解了qwq。 https://wenku.baidu.com/view/284648d7c1c708a1284a4425.html
? 解题记录 ? ? BZOJ ? ? 期望概率 ?    2019-01-05 11:50:47    647    0    0
Description 小Q的工作是采摘花园里的苹果。在花园中有n棵苹果树以及m条双向道路,苹果树编号依次为1到n,每条道路的两 端连接着两棵不同的苹果树。假设第i棵苹果树连接着d_i条道路。小Q将会按照以下方式去采摘苹果: 1.小Q随机移动到一棵苹果树下,移动到第i棵苹果树下的概率为d_i/(2m),但不在此采摘。 2.等概率随机选择一条与当前苹果树相连的一条道路,移动到另一棵苹果树下。 3.假设当前位于第i棵苹果树下,则他会采摘a_i个苹果,多次经过同一棵苹果树下会重复采摘。 4.重复第2和3步k次。 请写一个程序帮助计算小Q期望摘到多少苹果。 Input 第一
? 解题记录 ? ? BZOJ ? ? 整体二分 ? ? 树状数组 ? ? 树链剖分 ?    2019-01-05 11:01:15    706    0    0
【题目描述】风见幽香非常喜欢玩一个叫做 osu!的游戏,其中她最喜欢玩的模式就是接水果。 由于她已经DT FC 了The big black,  她觉得这个游戏太简单了,于是发明了一个更加难的版本。首先有一个地图,是一棵由 n 个顶点、n-1 条边组成的树(例如图 1给出的树包含 8 个顶点、7 条边)。这颗树上有 P 个盘子,每个盘子实际上是一条路径(例如图 1 中顶点 6 到顶点 8 的路径),并且每个盘子还有一个权值。第 i 个盘子就是顶点a_i到顶点b_i的路径(由于是树,所以从a_i到b_i的路径是唯一的),权值为c_i。接下来依次会有Q个水果掉下来,每个水果本质上也是一条
? 解题记录 ? ? LCT ? ? BZOJ ?    2019-01-05 10:49:14    553    0    0
【题目描述】小强要在N个孤立的星球上建立起一套通信系统。这套通信系统就是连接N个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻,一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。 例如,在上图中,现在一共有了5条边。其中,(3,8)这条边的负载是6,因为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8)。 现在,你的任务就是随着边的添加,动态的回答小强对于某些边的负载的询问。 【输入】第一行包含两个整数N,Q,表示星球的数量和操作的数量。星球从1开始编号。 接下来的Q行,每行是如下两种格式之一: A x y 表示
? 解题记录 ? ? BZOJ ? ? 高斯消元 ? ? 斯特林数 ?    2018-12-26 09:56:03    746    0    0
Description 定义两个结点数相同的图 G1 与图 G2 的异或为一个新的图 G, 其中如果 (u, v) 在 G1 与 G2 中的出现次数之和为 1, 那么边 (u, v) 在 G 中, 否则这条边不在 G 中. 现在给定 s 个结点数相同的图 G1...s, 设 S = {G1, G2, . . . , Gs}, 请问 S 有多少个子集的异 或为一个连通图? Input 第一行为一个整数s, 表图的个数. 接下来每一个二进制串, 第 i 行的二进制串为 gi, 其中 gi 是原图通过以下伪代码转化得 到的. 图的结点从 1 开始编号, 下面设结点数为 n.
? 解题记录 ? ? 亚线性筛 ? ? BZOJ ?    2018-12-19 20:53:45    504    0    0
Description 给定n,m,求 模10^9+7的值。 Input 仅一行,两个整数n,m。 Output 仅一行答案。 Sample Input 100000 1000000000 Sample Output 857275582 数据规模: 1&lt;=n&lt;=105&#xFF0C;1&lt;=m&lt;=109" role="presentation" style="position: relative;">1<=n<=105,1<=m<=109
? 解题记录 ? ? BZOJ ? ? 模拟 ?    2018-12-19 12:10:04    436    0    0
【题目描述】给出一个N个顶点、M条边的无向图,边(u,v)有权值w(u,v),顶点i也有权值p(i), 并且对于每条边(u,v)都满足p(u)+p(v)>=w(u,v)。 现在要将顶点i的权值减去z(i),其中0≤z(i)≤p(i)。 修改后设顶点i的权值p'(i)=p(i)-z(i),对于每条边(u,v)都满足p'(u)+p'(v)=w(u,v)。 求sum{z(i)}的最小值和最大值。   【输入】第一行两个正整数n,m (n≤500,000, m≤3,000,000)。 第二行n个整数,依次表示p(1),p(2),...,p(n) (0≤p(i)≤10^6)。 下面m行,
? 解题记录 ? ? BZOJ ? ? 动态规划 ?    2018-12-19 11:55:14    375    0    0
【题目描述】IOI铁路是由N+2个站点构成的直线线路。这条线路的车站从某一端的车站开始顺次标号为0...N+1。 这条路线上行驶的电车分为上行电车和下行电车两种,上行电车沿编号增大方向行驶,下行电车沿编号减小方向行驶。乘坐这两种电车的话,移动1站的距离需要T秒。换句话说,乘坐上行电车从车站i走到车站i+1需要T秒,称作下行电车从车站i走到车站i-1也需要T秒。你不能在0号车站乘坐下行电车,或在N+1号车站乘坐上行电车。由于电车发车的频率非常高,你可以无视等待电车消耗的时间。 每个车站设有上行电车的站台和下行电车的站台,连接两个站台的道路上设有邮戳台。 现在,IOI铁路召开了邮戳拉力赛。在拉力赛
? 解题记录 ? ? BZOJ ? ? 二次剩余 ? ? BSGS ?    2018-12-19 10:52:32    589    0    0
Description Fib数列为1,1,2,3,5,8... 求在Mod10^9+9的意义下,数字N在Fib数列中出现在哪个位置 无解输出-1 Input 一行,一个数字N,N < = 10^9+9 Output 如题 Sample Input 3 Sample Output 4 109+910^9+9明示55有二次剩余。 考虑FibFib的通项公式: fn=1√5((1+√52)n−(1−√52)n) f_n=\frac{1}{\sqrt 5}\left (\left (\frac{1+\sqrt 5}{2}\
? 解题记录 ? ? BZOJ ? ? 类欧几里得 ?    2018-12-18 18:57:19    395    0    0
题意: 给定a,b,c" role="presentation" style="position: relative;">a,b,ca,b,ca,b,c,求满足方程Ax+By&#x2264;C" role="presentation" style="position: relative;">Ax+By≤CAx+By≤CAx+By\le C的非负整数解 A,B&#x2264;109,C&#x2264;Min(A,B)&#x2217;109" role="presentation" style="position: relative;">A,B