2 _Shmily

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 4w+

2020中国大学生程序设计竞赛(CCPC) - 网络选拔赛----HDU--6900、Residual Polynomial(分治、FFT)

题目链接题面:题意:给定函数: f1(x)=∑i=0naixif_1(x)=\sum_{i=0}^na_ix^if1​(x)=∑i=0n​ai​xi给定 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

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

石油大----Contest2003 - 2020年秋季组队训练赛第七场--Problem L、Largest Quadrilateral (平面找四点组成面积最大的四边形,旋转卡壳)

题面:题意:平面上给定 nnn 个点,这 nnn 个点中选四个点组成一个四边形,问这个四边形的面积最大是多少。题解:很明显,最优解的四个点一定都在凸包上。先求解凸包。若凸包上面的点 ≤2\le2≤2 ,那么说明这些点共线或者重合。面积为 000。若凸包上面的点 =3=3=3,则四边形的三个顶点为这三个点,剩余的那一个点选自凸包内部。枚举即可。若凸包上面的点 >=4>=4>=4,我们枚举凸包上面的任意两点,在这两点的两侧分别求解一个面积最大的三角形,两个三角形相加即为在当前

2020-09-12 17:13:00

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

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

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

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

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

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

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

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

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=61​abc=31​Sh可解得

2020-09-03 16:47:45

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

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

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

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

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

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∑i​divmed(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

哈希算法在判定树同构方面的应用(下)

哈希算法在判定树同构方面的应用在上一篇文章中我们介绍了 枚举根节点哈希 和 求重心哈希 两种方法来判断两棵无根树是否同构。但是如果有些题目中我必须要计算出每个根节点的 fff 值,且 n≤1e5n\le 1e5n≤1e5,我们要怎么办呢?考虑以下问题。(一):洛谷–P4323 [JSOI2016]独特的树叶题解:考虑如下解法。我们求解 AAA 树中,以每一点 xxx 为根的 f[x]f[x]f[x] 值并保存。我们枚举 BBB 树中的叶子节点,计算删去这个叶子节点后,这个叶子节点的父亲的

2020-08-31 12:59:06

哈希算法在判定树同构方面的应用(上)

哈希算法在判定树同构方面的应用(上)(一)需要掌握的前置知识:(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 11:28:52

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。