- 博客(480)
- 收藏
- 关注
RSS订阅原创 2021-05-19 退役啦
哈哈，上次发博客已经是八个月之前啦，算起来有小一年啦。 看着刘爷又燃起了打比赛的欲望，看着杨大佬这么卷，我就放心啦。 （一）
2021-05-19 22:56:37
1016
12
原创 石油大--2020年秋季组队训练赛第十三场---- F、Historical Maths（二分）
题面：题意：给定三个数 A,B,CA,B,CA,B,C每个数以以下的形式给出。先给出一个正整数 nnn，表示这个数有 nnn 位，然后给出 nnn 个十进制非负整数，表示该数从高位到低位每个数位上的数的十进制表示。若在某一进制下 A∗B=CA*B=CA∗B=C，输出符合要求的进制。题解：考虑当前 kkk 进制下，如果 A∗B>CA*B>CA∗B>C ，那么说明 kkk 进制较小，A∗BA*BA∗B 产生了较多的进位，说明符合要求的进制要比 kkk 大。如果 A∗B<
2020-09-28 14:05:47
255
1
原创 石油大--2020年秋季组队训练赛第十三场----G、Insertion Order（构造）
题面：题意：给定 nnn， kkk 。需要构造一个 1−n1-n1−n 的全排列，使得按这个顺序插入搜索二叉树，使得二叉树的树高为 kkk。这里的树高定义为，从根节点到叶子节点经过的最多的节点个数。题解：先构造一棵可行的树。可以先构造一个节点数为 kkk，树高为 kkk 的树，我们可以让每个节点只有左儿子从而构造。然后分层添加节点，使得树上的节点为 nnn。然后 dfsdfsdfs 填值即可。#include<iostream>#include<cstdio>
2020-09-28 13:54:58
310
原创 石油大--2020年秋季组队训练赛第十三场---- C、Colourful Chameleons（思维）
题面：题意：有 nnn 种颜色的变色龙，其中第 iii 种颜色的变色龙有 ai,(ai>=n−1)a_i ,(a_i>=n-1)ai,(ai>=n−1) 只。我每次可以选择 n−1n-1n−1 只不同颜色的变色龙，让他们变成 y,y>=n−1y,y>=n-1y,y>=n−1 未选择的那种颜色的变色龙。现在我想让所有的变色龙都变为第 ccc 种颜色，至少需要经过几次操作。题解：我们发现变化时，两个颜色之间的变色龙数量之间的差值只会变化 (y+1)(y+
2020-09-28 13:45:15
258
原创 石油大--2020年秋季组队训练赛第十三场----B、Bouldering（最短路）
题面：题意：给定一个 h∗wh*wh∗w 点阵，其中某一些点是可以走的。这些点都有一个权值，表示如果经过当前点，则会花费的力气。给定一个 rrr，你只能从当前点到达与你欧几里得距离不超过 rrr 的点。问在花费的总力气不超过 sss 的情况下，从最下层的那个点（保证唯一），走到最上层的那个点（保证唯一）距离的最小值。题解：对于花费的力气的总值为：w∗h∗9w*h*9w∗h∗9，是一个较小的值。我们可以设 dp[x][j]dp[x][j]dp[x][j] 为当前走到 xxx 号节点，花费力
2020-09-28 13:23:23
475
原创 石油大--2020年秋季组队训练赛第十二场----J、Greedy Termite（线段树）
题面：题意：给定正整数 nnn 和起始位置 sss。nnn 表示有 nnn 个杆子，每个杆子由属性 (xi,hi)(x_i,h_i)(xi,hi) 构成，表示在 xix_ixi 处有一根高度为 hih_ihi 的杆子。初始时在 sss 杆子处。每爬到一个杆子（途径不算）我就会把这个杆子扔掉。从当前位置要去的下一个杆子符合以下条件：加上当前在杆子 iii 处。（1）当前还在场上的杆子。（2）选择hj−∣xi−xj∣h_j-|x_i-x_j|hj−∣xi−xj∣ 最大的杆子。（3
2020-09-28 12:56:53
168
原创 石油大--2020年秋季组队训练赛第十二场---- L、The Assembly Code（模拟）
题面：题意：就是题目有点长，写起来直接写就好啦。有一个长度为 232，0≤i<2322^{32}，0\le i <2^{32}232，0≤i<232 数组 MMM ， MiM_iMi 是一个 323232 位的无符号整数。有以下三种地址表示形式：#(number) 立即寻址：表示 numbernumbernumber 是一个常量。$(index) 直接寻址：即下标为 index 的存储单元，即 M(index)。@(index) 间接寻址：即下标为 M(index) 的存
2020-09-28 12:39:36
160
原创 石油大--2020年秋季组队训练赛第十一场----E、Give-a-Gnocchi（打表）
题面：题意：给定 n,kn,kn,k ，求不能被 ≤n\le n≤n 的质数整除的第 kkk 小的合数。其中 n≤1000，k≤1000n\le 1000，k\le1000n≤1000，k≤1000题解：假设 prime[i]≤n and prime[i+1]>nprime[i]\le n\ and\ prime[i+1]>nprime[i]≤n and prime[i+1]>n本题其实要求，由 prime[i+1]−−prime[i+
2020-09-28 12:22:02
257
原创 2020中国大学生程序设计竞赛（CCPC） - 网络选拔赛----HDU--6900、Residual Polynomial（分治、FFT）
题目链接题面：题意：给定函数： f1(x)=∑i=0naixif_1(x)=\sum_{i=0}^na_ix^if1(x)=∑i=0naixi给定 b2,b3,...,bnb_2,b_3,...,b_nb2,b3,...,bn 和 c2,c3,...,cnc_2,c_3,...,c_nc2,c3,...,cn对于 i∈[2,n]，fi(x)=bi(fi−1(x))′+cifi−1(x)i\in[2,n]，f_i(x)=b_i(f_{i-1}(x))'+c_if_{i-1}(x)
2020-09-22 19:57:00
659
1
原创 2020中国大学生程序设计竞赛（CCPC） - 网络选拔赛----HDU--6899、Xor（数位dp）
题目链接题面：题意：求解符合 x∈[0,a],y∈[0,b]x\in[0,a],y\in[0,b]x∈[0,a],y∈[0,b] 且 ∣x−y∣≤k|x-y|\le k∣x−y∣≤k 且 x xor y≤wx\ xor\ y \le wx xor y≤w 的 (x,y)(x,y)(x,y) 的数对数量。题解：①、官方题解：将∣x−y∣≤k|x-y|\le k∣x−y∣≤k 拆为 y−x≤k且x−y≤ky-x\le k且x-y\le ky−x≤k且x−y≤
2020-09-22 19:09:02
790
原创 石油大----Contest2003 - 2020年秋季组队训练赛第七场--Problem L、Largest Quadrilateral （平面找四点组成面积最大的四边形，旋转卡壳）
题面：题意：平面上给定 nnn 个点，这 nnn 个点中选四个点组成一个四边形，问这个四边形的面积最大是多少。题解：很明显，最优解的四个点一定都在凸包上。先求解凸包。若凸包上面的点 ≤2\le2≤2 ，那么说明这些点共线或者重合。面积为 000。若凸包上面的点 =3=3=3，则四边形的三个顶点为这三个点，剩余的那一个点选自凸包内部。枚举即可。若凸包上面的点 >=4>=4>=4，我们枚举凸包上面的任意两点，在这两点的两侧分别求解一个面积最大的三角形，两个三角形相加即为在当前
2020-09-12 17:13:00
304
1
原创 HDU-5514、Frogs （容斥）
题目链接题面：题意：有一个长度为 mmm 的环，编号为 [0,m−1][0,m-1][0,m−1]，有 nnn 只青蛙在 000 号点处，第 iii 只青蛙每次可以从 kkk 号点跳到 k+a[i]k+a[i]k+a[i] 号点，现在这 nnn 只青蛙可以跳跃无穷次，问最后哪些点被青蛙曾经跳进去过。题解：很明显，第 iii 只青蛙只会跳 gcd(a[i],m)gcd(a[i],m)gcd(a[i],m) 那些点，我们令 a[i]=gcd(a[i],m)a[i]=gcd(a[i],m)a[i]=g
2020-09-11 12:28:19
175
1
原创 Educational Codeforces Round 81 (Rated for Div. 2) D. Same GCDs （容斥）
题目链接题面：题意：给定两个整数 aaa，mmm。询问满足 gcd(a,m)=gcd(a+x,m)gcd(a,m)=gcd(a+x,m)gcd(a,m)=gcd(a+x,m) 且 0≤x<m0\le x<m0≤x<m 的不同xxx 的个数。题解：我们设 g=gcd(a,m)g=gcd(a,m)g=gcd(a,m)，那么我们有 gcd(k1∗g+x,k2∗g)=ggcd(k1*g+x,k2*g)=ggcd(k1∗g+x,k2∗g)=g，即 x=k3∗gx=k3*gx=k3∗g
2020-09-11 09:00:37
161
1
原创 2020 Multi-University Training Contest 6---- HDU--6828、Little Rabbit‘s Equation（模拟）
题目链接题面：题意：判定给定等式在 2−162-162−16 进制，最低几进制下成立。题解：模拟即可，注意进制最低为2。代码：#include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>#include<cmath>#include<string>#include<queue&
2020-09-05 10:22:05
112
原创 POJ -- 3046、Ant Counting （多重集组合数，计数类dp）
题目vj链接题面：题意：有 TTT 种物品，第 iii 种物品有 nin_ini 个。从中选出若干个物品组成一个集合，问集合大小位于区间 [S,B][S,B][S,B] 的不同的集合有多少个。两个集合相同当且仅当两个集合相同种类的物品个数一样。题解：我们设 dp[i][j]dp[i][j]dp[i][j] 为选择了前 iii 种物品且集合大小为 jjj 时不同的方案数。转移方程显然： dp[i][j]=∑k=0min(j,ni)dp[i−1][j−k]dp[i][j]=\sum\limi
2020-09-05 09:00:21
151
原创 HDU--4248、A Famous Stone Collector （计数类dp）
题目链接题面：题意：有 nnn 种颜色的石子，第 iii 种颜色的石子有 aia_iai 个。我现在要从里面选出若干个石子拍成一排，问有多少种不同的序列。两个序列不同当且仅当长度不同或者至少有某个位置的对应颜色不同。题解：考虑 dp[i][j]dp[i][j]dp[i][j]，表示我考虑的前 iii 种颜色的石子，现在构成的长度为 jjj 的序列的不同排列的方案数。转移方程显然 dp[i][j]=∑k=0min(sum[i],j)dp[i−1][j−k]∗Cjkdp[i][j]=\sum
2020-09-05 08:08:43
164
原创 2020 Multi-University Training Contest 5---- HDU--6822、Paperfolding （期望）
题目链接题面：题意：给定一张纸，等概率的左右对折或者上下对折，对折 nnn 后，我沿着垂直轴剪一刀，沿着水平轴剪一刀，会分为多个碎片，问碎片个数的期望 。题解：我们转换一下模型，如果一次也不折叠，相当于竖着剪了一刀，横着剪了一刀。每左右折叠一次，都相当于竖着剪的次数翻倍；每上下折叠一次，相当于横着剪得次数翻倍。如果 nnn 次中有 iii 次是左右折叠的，那么最终的碎片总数应该为 (2i+1)∗(2n−i+1)(2^i+1)*(2^{n-i}+1)(2i+1)∗(2n−i+1)所以，期望
2020-09-04 15:33:26
126
原创 2020 Multi-University Training Contest 5---- HDU--6816、Boring Game （模拟）
题目链接题面：题意：nnn 张纸从上到下放置，从左往右折叠 kkk 次，折叠后，给 n∗2∗(1<<k)n*2*(1<<k)n∗2∗(1<<k) 个面都标上数字。每张纸每个面上都有 (1<<k)(1<<k)(1<<k) 个数字，按照从左到右，从上到下的顺序输出这些数字。题解：模拟即可。代码：#include<iostream>#include<cstdio>#include<cstdl
2020-09-04 12:09:19
99
原创 UVALive - 7501、Business Cycle （二分、思维）
题目vj链接题面：题意：给定一个有 nnn 个节点的环，每个节点有一个权值 viv_ivi，初始时我有一个权值 valvalval，且我在 000 号节点以外（走一步到达 000 号节点）。n−1n-1n−1 号节点的下一步是 000 号节点。我每到达一个节点，val=max(val+vi,0)val=max(val+v_i,0)val=max(val+vi,0)，即我每到一个节点都加上这个节点的权值，如果当前我的权值为负数，那么就变为 000。问，我的初始权值至少为多少，才能保证我在 pp
2020-09-04 11:24:41
118
原创 2020 Multi-University Training Contest 5---- HDU--6814、Tetrahedron （数学，推式子）
题目链接题面：题意：有一个四面体，已知某一个顶点上的三条边相互垂直，同时知道这三条边长度在 111 到 nnn 的正整数中均匀分布，且相互独立，令这个点到对应底面的距离为 hhh，求 1h2\frac{1}{h^2}h21 的期望。题解：可以以该点为原点，三条边为轴，建立直角坐标系。那么显然可以得到四面体所有点的坐标。用叉积算出底面面积，运用体积公式列方程求解即可。V=16abc=13ShV=\dfrac{1}{6}abc=\dfrac{1}{3}ShV=61abc=31Sh可解得
2020-09-03 16:47:45
127
原创 2020 Multi-University Training Contest 4---- HDU--6813、 Last Problem （构造）
题目链接题面：题意：给定一张无限大的坐标平面，你可以在节点 (x,y)(x,y)(x,y) 处填写数字，填写数字需要遵守一定的规则，输出在1e51e51e5 步之内可以让数字 nnn 出现的一个构造方法。规则：如果当前要填写一个数字 xxx ，对于 1≤i≤41\le i \le41≤i≤4，x−ix-ix−i 要么非正，要么 xxx 上下左右四个点种的某个点为 x−ix-ix−i 。题解：即我们让 x−1x-1x−1 出现在 xxx 的上方，x−2x-2x−2 出现在 xxx 的左方，x
2020-09-03 15:57:14
113
原创 2020 Multi-University Training Contest 4---- HDU--6810、Imperative Meeting（组合数学）
题目链接题面：题意：有一棵 nnn 个节点的树，边权均为 111，从上面选 mmm 个点的方案为 CnmC_n^mCnm。对于每一种方案，该方案的权重定义为这 mmm 个点到树上某一点的距离和的最小值。我们定义这一点为最优点。求 CnmC_n^mCnm 种方案的权重的和。题解：我没枚举每一条边，假设这条边两侧的节点数分别为 sss，n−sn-sn−s。我们在这条边两侧选的节点数为 iii，m−im-im−i，我们可以知道，最优点一定在选的点数较多的一侧。那么对于某条边来说较为容易得到公
2020-09-03 14:54:13
160
原创 HDU--5575、Discover Water Tank （思维、优先队列）
题目链接题面：题意：有一个 1∗n1*n1∗n 的水箱，水箱的四周的高度为无穷大。现在用 n−1n-1n−1 高度为 hih_ihi 的隔板将水箱分为 nnn 个 1∗11*11∗1 的部分。隔板不透水，但是水的流动遵循一般的物理规律，即如果当前水位如果比某一侧的隔板要高，谁就会从一个部分流向另一个部分。现在已知这 nnn 个部分某些部分可能有一定高度的水，进行 mmm 次探测，第 iii 次探测以 xxx yyy zzz 的形式给出，如果 z=0z=0z=0 ，说明第 xxx 个部分高度为
2020-09-02 11:16:31
276
原创 2020 Multi-University Training Contest 2---- HDU--6770、Dynamic Convex Hull （离线、分治）
题目连接题面：题意：有一个四次函数的集合 fi(x)=(x−ai)4+bif_i(x)=(x-a_i)^4+b_ifi(x)=(x−ai)4+bi。有以下三种操作（1）111 aaa bbb ，往集合中添加新的四次函数 fn+1=(x−a)4+bf_{n+1}=(x-a)^4+bfn+1=(x−a)4+b，然后n=n+1n=n+1n=n+1（2）222 ttt ，从集合中删除 ft(x)f_t(x)ft(x)（3）333 xxx ，在当前集合中询问 fi(x)f_i(x)fi
2020-09-01 14:27:06
332
原创 2020 Multi-University Training Contest 2---- HDU--6766、Diamond Rush（dp、思维）
题目连接题面：题意：给定一个 n∗nn*nn∗n 的矩阵，每个点都有一个权值 (n2)ai,j(n^2)^{a_{i,j}}(n2)ai,j，左上角为 (1,1)(1,1)(1,1) ，右下角为 (n,n)(n,n)(n,n)。从(1,1)(1,1)(1,1) 出发，每次只能往右或者往下走。有 qqq 次查询，每次查询给出一个子矩阵 (xl,xr,yl,yr)(xl,xr,yl,yr)(xl,xr,yl,yr)，问如果子矩阵中的点不能走，从 (1,1)(1,1)(1,1) 到 (n,n)(n,
2020-09-01 10:42:27
239
原创 2020 Multi-University Training Contest 1---- HDU--6753、Cookies （分块打表）
题目连接题面：题意：给定函数 f(i)=∑j=1idivmed(j)f(i)=\sum\limits_{j=1}^idivmed(j)f(i)=j=1∑idivmed(j)。divmed(x)divmed(x)divmed(x) 表示 xxx 所有的因子从小到大排序后第 cnt+12\frac{cnt+1}{2}2cnt+1 个因子。cntcntcnt 表示 xxx 因子的个数。给定 fff 函数的前 nnn 项，然后给个 mmm 个操作 pip_ipi。按顺序进行 mmm 个操作，
2020-08-31 22:47:21
279
原创 哈希算法在判定树同构方面的应用（下）
哈希算法在判定树同构方面的应用在上一篇文章中我们介绍了 枚举根节点哈希 和 求重心哈希 两种方法来判断两棵无根树是否同构。但是如果有些题目中我必须要计算出每个根节点的 fff 值，且 n≤1e5n\le 1e5n≤1e5，我们要怎么办呢？考虑以下问题。（一）：洛谷–P4323 [JSOI2016]独特的树叶题解：考虑如下解法。我们求解 AAA 树中，以每一点 xxx 为根的 f[x]f[x]f[x] 值并保存。我们枚举 BBB 树中的叶子节点，计算删去这个叶子节点后，这个叶子节点的父亲的
2020-08-31 17:16:54
246
1
原创 哈希算法在判定树同构方面的应用（上）
哈希算法在判定树同构方面的应用（上）（一）需要掌握的前置知识：（1）素数筛法：埃氏筛或者欧拉筛均可以。以下为欧拉筛：const int maxn=100100;int p[maxn],cnt=0;bool ha[maxn];void Prime(void){ ha[1]=true; for(int i=2;i<maxn;i++) { if(!ha[i]) p[++cnt]=i; for(int j=1;j<=cnt&
2020-08-31 17:16:45
457
原创 石油大--Contest2022 - 2020年秋季组队训练赛第二场--17102 Problem F、Regular Forestation （树同构、剪枝）
题面：题意：给定一棵无根树，如果去掉点 xxx 且去掉与点 xxx 相连的边，剩下的部分是由 kkk 棵树组成的森林，且这 kkk 棵树同构，且k>1k>1k>1 。那么称 xxx 是一个好的切分点。输出去掉某一个好的切分点后最大的 kkk。题解：数据量只有 400040004000，很容易想到解决方案可能是 O(n2)O(n^2)O(n2) 复杂度的算法。我们枚举每个点 xxx，判定这个点是否是好的切分点，同时用 kkk 更新答案。在判断两棵树是否同构的时候，我们需要求出
2020-08-31 08:33:29
230
原创 石油大--Contest2022 - 2020年秋季组队训练赛第二场--17101 Problem E、Songwriter（思维）
题面：题意：给定一个长度为 nnn 的数组 aaa，你需要构造一个数组 bbb，使得数组 bbb 中的单调性与 aaa 中的单调性一致，且数组 bbb 中的元素均在 [L,R][L,R][L,R] 区间内，且 abs(bi−bi−1)≤kabs(b_i-b_i-1)\le kabs(bi−bi−1)≤k输出字典序最小的 bbb 数组。题解：我们设两个数组 l,rl,rl,r，其中[li,ri][l_i,r_i][li,ri] 表示 bib_ibi 限制在区间 [li,ri][l_i,
2020-08-30 21:59:13
123
原创 石油大--Contest2022 - 2020年秋季组队训练赛第二场--17107 Problem K、Addition Robot（线段树）
题面：题意：给定一个仅由 A,BA,BA,B 组成的字符串，支持两种操作。（1）111 lll rrr，对 [l,r][l,r][l,r] 区间的字符进行翻转处理，即 AAA 变为 BBB ，BBB 变为 AAA。（2）111 lll rrr aaa bbb ，利用 [l,r][l,r][l,r] 区间的字符对 a,ba,ba,b 进行操作，如果 s[i]=As[i]=As[i]=A，那么 a=a+ba=a+ba=a+b，如果 s[i]=Bs[i]=Bs[i]=B ，那么 b=a+bb=a+
2020-08-30 20:42:48
154
原创 石油大--Contest2022 - 2020年秋季组队训练赛第二场--17100 Problem D、Find String in a Grid （AC自动机）
题面：题意：给定一个 R∗CR*CR∗C 的字符矩阵，由大写字母构成。有 qqq 个询问，每次给定一个由大写字母构成的字符串，问这个字符串在这个字符矩阵中出现了多少次。某个字符串在矩阵中出现定义为：这个字符串在矩阵中的存在形式是先往右匹配再往下匹配。其中往右往下的长度均可以为0。题解：考虑离线 qqq 个查询，将这 qqq 个查询建立 AC自动机。然后将 R∗CR*CR∗C 的字符矩阵中的每个往右往下的串（枚举第 iii 行，枚举拐点 jjj）在 AC自动机上匹配，最后在 failfail
2020-08-30 20:24:49
388
原创 2020 Multi-University Training Contest 8---- HDU--6860、 Fluctuation Limit （思维）
题目连接题面：题意：现在有 nnn 个区间 [li,ri][l_i,r_i][li,ri]。现在要组成一个序列。第 iii 个数 aia_iai 从区间 [li,ri][l_i,r_i][li,ri] 中选择，要保证 abs(ai−ai−1)≤kabs(a_i-a_{i-1})\le kabs(ai−ai−1)≤k 。如果存在这样的序列，求解任意这样的序列。题解：代码：#include<iostream>#include<cstdio>#inc
2020-08-30 19:51:53
117
原创 2020 Multi-University Training Contest 9---- HDU--6867、Tree （树形dp）
题目连接题面：题意：给定一棵根为 111 号节点的有向树，你可以添加一条边，使得形成的有向图中的可达点对 (x,y)(x,y)(x,y) 最多。可达点对 (x,y)(x,y)(x,y) 是指能从 xxx 走到 yyy，其中 (x,x)(x,x)(x,x)也算合法的可达点对。题解：因为是有向有根树，那么根节点可以到达所有的节点，那么最优的连接方式一定是从某个叶子节点连接到根节点，这样根节点到叶子节点这条链就都变成可达所有的节点。对于根节点到叶子节点这条链上面的一点 xxx，连接叶子结点之后其增
2020-08-30 08:36:10
176
原创 2020 Multi-University Training Contest 5---- HDU--6824、Exam （2-sat，线段树优化建图）
题目链接题面：题意：有 nnn 门考试，每门考试有两个时间段可以进行 [a,a+at],[b,b+bt][a,a+at],[b,b+bt][a,a+at],[b,b+bt]，每门考试必须选择其中的一个时间段进行，且两门考试的时间严格不相交。即 [3,5],[5,7][3,5],[5,7][3,5],[5,7]进行两门考试是不合法的。问完成 nnn 门考试的最短时间。题解：上面是官方题解：我们把考试转换为 2−sat2-sat2−sat 问题（显然要转化为2−sat2-sat2−sat）。
2020-08-29 21:23:02
193
原创 Codeforces Round #406 (Div. 1)--B. Legacy （线段树优化建图，最短路）
题目链接题面：题意：给定一张图，求 SSS 点到其他点的最短路。图以以下形式给出：（1） 111 xxx yyy www ，有一条从 xxx 到 yyy 的边权为 www 的有向边。（2） 222 xxx lll rrr www，xxx 向区间 [l,r][l,r][l,r] 中的点每个点都连接一条边权为 www 的有向边。（3） 333 yyy lll rrr www，区间[l,r][l,r][l,r] 中的点每个点都向 xxx 连接一条边权为 www 的有向边。题解：直接连边是行不
2020-08-29 09:29:28
129
原创 2020 Multi-University Training Contest 6---- HDU--6827、Road To The 3rd Building（期望）
题目链接题面：题意：求 1j−i+1∑k=ijsk\frac{1}{j-i+1}\sum_{k=i}^js_kj−i+11∑k=ijsk 的期望，其中 1≤i≤j≤n1\le i\le j\le n1≤i≤j≤n。我们可以先求出 ∑all1j−i+1∑k=ijsk\sum_{all}\frac{1}{j-i+1}\sum_{k=i}^js_k∑allj−i+11∑k=ijsk 然后再除以区间个数 n∗(n+1)/2n*(n+1)/2n∗(n+1)/2 即可。题解：参考 另一篇
2020-08-28 20:45:48
116
原创 2020 Multi-University Training Contest 2---- HDU--6765、Count on a Tree II Striking Back（随机化算法）
题目链接题面：题意：给定一棵 nnn 个节点的树。每个节点都有颜色。每次询问 a,ba,ba,b 路径上的颜色种类数是否大于 c,dc,dc,d 路径上的颜色种类数。带单点颜色修改且强制在线。数据保证每次询问 2f(a,b)≤f(c,d)2f(a,b)\le f(c,d)2f(a,b)≤f(c,d) 或者 2f(c,d)≤f(a,b)2f(c,d)\le f(a,b)2f(c,d)≤f(a,b)题解：kkk 个 [0,1][0,1][0,1] 的随机实数的最小值的期望为 1k+1\frac
2020-08-28 20:31:22
184
原创 2020 Multi-University Training Contest 8---- HDU--6865、Kidnapper‘s Matching Problem（线性基）
题目链接题面：题意：有两个长度分别为 nnn 和 mmm 的数组 aaa 和 bbb，以及一个线性基 SSS，我们定义两个数组 xxx和 yyy 匹配当且仅当这两个数组长度相等且∑i=1len[xi⨁yi∈S]=len\sum\limits_{i=1}^{len}[xi⨁yi∈S]=leni=1∑len[xi⨁yi∈S]=len，即两个数组相对应的数异或之后的结果在线性基 SSS 中。求出a中所有与b匹配的区间。官方题解：考虑满足 ai⨁bi∈Sai⨁bi∈Sai⨁bi∈S 的条件，令 xx
2020-08-28 18:09:27
125
原创 2020 Multi-University Training Contest 8---- HDU--6858、Discovery of Cycles（LCT）
题目链接题面：题意：给定一张图，给定 mmm 条边，有重边但没有自环。问区间 [l,r][l,r][l,r] 的边所构成的图中有没有环。这里的环包括二元环。题解：我们对于任意一条边 lil_ili，求出这条边往右至少到哪一条边才能让图中存在环，记这条边为 rir_iri。如果当前边往右不能再形成一个环，我们就记这条边的能形成环的右端点为 m+1m+1m+1我们可以发现 rir_iri 是不减的。于是我们可以来维护左端点和右端点。对于当前左端点的边来说，如果加上当前右端点这条边还不会形成
2020-08-28 16:02:07
134
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人