• 等级
  • 33031 访问
  • 458 原创
  • 0 转发
  • 9285 排名
  • 50 评论
  • 10 获赞

欢乐纪中某B组赛【2019.1.19】

前言 有回来做BBB组了,话说第3道题就是AAA组第一道。 成绩 RankRankRank是有算别人的 今天XJQXJQXJQ不在 RankRankRank PersonPersonPerson ScoreScoreScore AAA BBB CCC 111 2017wyc2017wyc2017wyc 270270270 100100100 100100100 707070 ...

2019-01-20 14:43:39

jzoj4231-寻找神格【线段树,数学】

正题 题目大意 4个操作 单点修改,区间修改,区间求和,区间求方差 方差为:∑(xi−ave)2n\frac{\sum(x_i-ave)^2}{n}n∑(xi​−ave)2​ aveaveave为平均值 解题思路 我们将方差的式子分解一下 ∑(xi−ave)2n\frac{\sum(x_i-ave)^2}{n}n∑(xi​−ave)2​ ∑(xi2−2∗x∗ave+ave2)n\frac{\s...

2019-01-20 14:30:55

jzoj4230-淬炼神体【0/1分数规划】

正题 题目大意 nnn个东西,有ai,bia_i,b_iai​,bi​。选择kkk个,使得∑ai/∑bi\sum a_i/\sum b_i∑ai​/∑bi​最大。 解题思路 ∑ai/∑bi=k\sum a_i/\sum b_i=k∑ai​/∑bi​=k ∑ai/∑bi/k=1\sum a_i/\sum b_i/k=1∑ai​/∑bi​/k=1 ∑ai/k=∑bi\sum a_i/k=\sum ...

2019-01-20 14:17:38

jzoj4229-学习神技【逆元,费马小定理】

正题 题目大意 求 (∑i=1na∗qi) mod (109+7)(\sum_{i=1}^na*q^i)\ mod\ (10^9+7)(i=1∑n​a∗qi) mod (109+7) 解题思路 题目里都给出公式 ∑i=1na∗qi=a∗(1−qn)1−q\sum_{i=1}^na*q_i=\frac{a*(1-q^n)}{1-q}i=1∑n​a∗qi​=...

2019-01-20 14:10:23

P3806-【模板】点分治1

正题 评测记录:https://www.luogu.org/recordnew/lists?uid=52918&pid=P3806 题目大意 一颗树,k个询问,求是否存在长度为lil_ili​的路径。 解题思路 开个桶就好了,点分治不解释。 codecodecode #include<cstdio> #include<algorithm> #include&l...

2019-01-20 07:54:36

欢乐纪中某A组赛【2019.1.19】

前言 因为BBB有一堆(两道)题都做过,于是就来做A组了。 成绩 RankRankRank是有算别人的 RankRankRank PersonPersonPerson ScoreScoreScore AAA BBB CCC 333 2017myself2017myself2017myself 210210210 100100100 100100100 101010 22222...

2019-01-19 16:17:05

jzoj3771-小Z的烦恼【高精度,数学】

正题 题目大意 mmm个盒子, 当第iii个盒子中放了xxx,那么i+1i+1i+1个盒子中就必须放2x2x2x(i<=mi<=mi<=m)。 求1∼n1\sim n1∼n,mmm个盒子,求第一个盒子中可以放多少个 解题思路 1号盒子中的肯定越小越好。 要求满足条件那么首先x∗2m≤nx*2^m\leq nx∗

2019-01-19 16:08:54

jzoj2940-生成输入数据【最小生成树,并查集】

正题 题目大意 给一个完全图的唯一一颗最小生成树,求完全图最小边权之和。 解题思路 我们考虑在计算最小生成树的时候,将两个联通块合并时,我们会选择连接这两个联通块的最小的边。 那么我们就可以让每个联通块合并时,让其他边都是比这个给出的边边权+1的就好了。 codecodecode #include<cstdio> #include<algorithm> #define...

2019-01-19 15:57:43

jzoj2941-贿赂【数学期望,dfs】

正题 题目大意 nnn个人,有投票几率aia_iai​和级别bib_ibi​,kkk个糖,每个可以让一个官员增加0.10.10.1的投票几率。 然后如果有超过一半的人投你,你就可以成功。 不然成功概率就是A/(A+∑i∈Sbi)A/(A+\sum^{i\in S}b_i)A/(A+∑i∈S​bi​) 求最大的成功概率 解题思路 由于数据小的可怜,所以我们直接dfsdfsdfs枚举给糖,然后枚举...

2019-01-19 15:53:49

欢乐纪中某B组赛【2019.1.18】

前言 新年新气象,我们又一度迎来新一年的模拟赛(谁想迎来) 总之,有来到了熟悉的地方——纪中。 成绩 RankRankRank是有算别人的 RankRankRank PersonPersonPerson ScoreScoreScore AAA BBB CCC DDD 222 2017myself2017myself2017myself 300300300 100100100 10...

2019-01-18 15:57:22

P1315,jzoj3029-观光公交【费用流】

前言 你绝对想不到,我用费用流神仙构图做了一道 的题 正题 评测记录:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1315 题目大意 有nnn个地方,iii到第i+1i+1i+1的长度为did_idi​。 有mmm个人,从tit_iti​出发,从lil_ili​到rir_iri​。 有kkk个氮气,可以让一条路变短。 求所...

2019-01-18 15:39:36

P1314,jzoj3028-聪明的质监员【二分答案,前缀和】

正题 评测记录:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1314 题目大意 有nnn个石头,mmm个区间,对于每个WWW有一个YYY。 Y=∑i=0n((∑j=liri(wi>=w)∗vi)∗(∑j=liri(wi>=w)))Y=\sum_{i=0}^n((\sum_{j=l_i}^{r_i}(...

2019-01-18 15:23:03

P1311,jzoj3025-选择客栈【统计】

正题 评测记录:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1311 题目大意 如果两个客栈是同样颜色且中间有客栈消费不超过p那么久算为一种方案,求方案总数 解题思路 先枚举颜色,然后枚举右边的,对于左边,记录两个数据:一个是有多个同样颜色的k,一个是有多少个选择方案y。 当枚举到一家消费不超过p的时,让y=k。 然后枚举到...

2019-01-18 15:17:44

P3391-[模板]文艺平衡树【Splay】

正题 题目连接:https://www.luogu.org/problemnew/show/P3391 题目大意 一个序列,m个操作翻转[l..r][l..r][l..r]区间。求最终序列 解题思路 节点维护编号,然后答案就是中序遍历。然后翻转的话我们先考虑一个性质。 若这是初始状态(l-1和r+1反了) 然后将l-1旋到根节点,将r+1选到根的右节点, 然后l∼rl\sim rl∼r就是...

2019-01-05 15:40:27

jzoj3059-雕塑【容斥,数论】

正题 题目大意 n∗nn*nn∗n的矩阵,要求放nnn个雕塑,要求每行每列都只有一个雕塑,且不可以放在障碍物上。求方案总数。 解题思路 首先没有障碍物答案就是n!n!n!。 之后障碍物很少,考虑容斥。 设fif_ifi​为选iii个障碍物且这些障碍物的位置必须放雕塑的方案总数。 然后答案显然 ans=∑i=0mfi∗(1−i%2∗2)ans=\sum_{i=0}^mf_i*(1-i\%2*2)...

2019-01-05 13:16:04

jzoj3058-火炬手【高精度,暴力】

正题 题目大意 对于一个nnn,求一个mmm,使得n∗mn*mn∗m只有0或1 解题思路 暴力枚举n∗mn*mn∗m,然后高精度求答案。 codecodecode #include<cstdio> #include<cmath> #define ll long long using namespace std; ll n,xans; int a[151],ans[15...

2019-01-05 13:09:53

P3369-[模板]普通平衡树【Splay】

正题 评测记录:https://www.luogu.org/recordnew/lists?uid=SSL_WYC_zombieeeeee&pid=P3369&status=&sort=0 题目大意 要求支持查询一个数字的排名,查询该排名的数字,插入数字,删除数字,求前驱后继。 解题思路 Splay不解释。 codecodecode #include<cstdi...

2019-01-05 13:06:31

P3369-[模板]普通平衡树【替罪羊树】

正题 评测记录:https://www.luogu.org/recordnew/lists?uid=SSL_WYC_zombieeeeee&pid=P3369&status=&sort=0 题目大意 要求支持查询一个数字的排名,查询该排名的数字,插入数字,删除数字,求前驱后继。 解题思路 替罪羊树 codecodecode #include<cstdio>...

2019-01-05 07:26:49

P3369-[模板]普通平衡树【有旋Treap】

正题 评测记录:https://www.luogu.org/recordnew/lists?uid=SSL_WYC_zombieeeeee&pid=P3369&status=&sort=0 题目大意 要求支持查询一个数字的排名,查询该排名的数字,插入数字,删除数字,求前驱后继。 解题思路 有旋Treap不解释。 codecodecode #include<cst...

2019-01-04 20:43:10

POJ3348-Cows【凸包,计算几何】

正题 题目大意 凸包的面积S,求⌊S/50⌋\lfloor S/50\rfloor⌊S/50⌋ 解题思路 求凸包,然后求面积,然后求答案。 codecodecode #include<cstdio> #include<algorithm> #include<cmath> #define N 10010 using namespace std;

2019-01-04 19:22:37

ssl_wyc

蒟蒻OIer
关注
  • 中国
奖章
  • 持之以恒