• 等级
  • 25061 访问
  • 406 原创
  • 0 转发
  • 10552 排名
  • 42 评论
  • 4 获赞

NOIP2018-普及总结

前言 原本说要去提高的,然后市里瞎搞,就去不了了QVQQVQQVQ。 总结 这次一看感觉题目比较难,所以基本凉凉… 首先这次有很多失误,特别是T2T2T2,其实很容易就分析出要用long  longlong\ \ longlong  long的,但是根据我的习惯,会先写用intintint的,然后在全部替换掉,就导致初始化的时候还是214748364721...

2018-11-14 16:43:39

P2468-[SDOI2010]粟粟的书架【主席树,二维前缀和】

正题 评测记录:https://www.luogu.org/recordnew/lists?uid=52918&pid=P2468 题目大意 对于每一个询问,求一个区域内最少取多少个数使它们的和不小于a。 解题思路 我们肯定取最大的 对于前50%的数据,用 sumi,j,ksum_{i,j,k}sumi,j,k​表示(1,1)(1,1)(1,1)到(i,j)(i,j)(i,j)超过kk...

2018-11-03 22:51:40

ssl提高组周四备考赛【2018.11.1】

前言 呆学校呆4天依旧不想复习期中,其中考凉透了。 成绩 RankRankRank PersonPersonPerson ScoreScoreScore AAA BBB CCC 111 2014lyk2014lyk2014lyk 200200200 100100100 707070 303030 222 2017wyc2017wyc2017wyc 180180180 1001...

2018-11-01 13:18:18

nssl1270-创世纪【树形dp,基环树】

正题 题目大意 每个物品有一个可以限制的物品,要求一个集合内所有的物品都有一个不在集合内物品限制。求这个集合可以保护的最多物品 解题思路 类似没有上司的舞会 其实就是在基环树森林,我们可以利用二次树形dp的方法。 先找到环,然后强行将环断开进行一次dp,然后强行连上进行一次dp,两个答案的最小值就得这棵树的最大物品。 其实也可以贪心,这里就不放了。 code #include<cstd...

2018-11-01 13:07:27

nssl1269-射击【贪心,堆】

正题 题目大意 有n个东西,东西必须在ai sa_i\ sai​ s前破坏,破坏后可以获得wiw_iwi​价值,求最大价值。 解题思路 我们可以将时间从大到小排序,然后用堆,每次处理价值最大的就好了。 code #include<cstdio> #include<queue> #include<algorithm> #define ll...

2018-11-01 12:52:21

ssl提高组周三备考赛【2018.10.31】

前言 呆学校呆3天依旧不想复习期中,感觉要凉。话说这次没有IOI 成绩 RankRankRank PersonPersonPerson ScoreScoreScore AAA BBB CCC 111 2017xxy2017xxy2017xxy 210210210 404040 100100100 707070 222 2017wyc2017wyc2017wyc 1901901...

2018-11-01 08:55:51

nssl1259-sequence【组合数,差分】

正题 题目大意 操作(l,r,k)(l,r,k)(l,r,k)表示 l∼rl\sim rl∼r这段区间,对于每个iii,加上Cki+k−lC_k^{i+k-l}Cki+k−l​ 解题思路 我们可以发现对于一个全是1的序列,求kkk次前缀和,就是杨辉三角的第k+1k+1k+1列,那么对于次修改,我们用k阶差分修改。最后取kkk次前缀和 code #include<cstdio> #...

2018-11-01 07:56:20

nssl1258-naive的瓶子【贪心】

正题 题目大意 有n个瓶子,将一个瓶子变成相邻一个瓶子的颜色价值为它们颜色值的乘积,求将所有瓶子变成同一个颜色的最低价值。 解题思路 枚举最后的剩下的颜色,然后对于每个瓶子只有两种可能 1.直接变成那个颜色 2.变成别的颜色在变成那个颜色 若我们要将X变成Z,而中间变成Y更优,我们可以判断 XZ<=XY+ZYXZ<=XY+ZYXZ<=XY+ZY 则Y&...

2018-11-01 07:52:00

nssl1257-A【数论】

正题 题目大意 对于n个数组成的序列,求排好序需要最少交换次数的期望次数。 解题思路 我们可以先求出需要次数总和在乘上n!n!n!的逆元 先打一个表,不难发现 f(n)=f(n−1)∗n+(n−1)(n−1)!f(n)=f(n-1)*n+(n-1)(n-1)!f(n)=f(n−1)∗n+(n−1)(n−1)! 然后我们在考虑插入,对于前面一个序列,我们可以插入一个比前面的数都大的数进去,之后我...

2018-11-01 07:46:01

ssl提高组周二备考赛【2018.10.30】

前言 依旧想去德育基地… 成绩 RankRankRank PersonPersonPerson ScoreScoreScore AAA BBB CCC 111 2017xxy2017xxy2017xxy 210210210 404040 100100100 707070 222 2017wyc2017wyc2017wyc 190190190 202020 100100100 ...

2018-10-30 14:40:38

nssl1256-C(盟主的忧虑)【并查集】

正题 题目大意 n个点的一棵树,增加了m条密道。对于树上每条边(A,B)(A,B)(A,B)被破坏后,要求A∼BA\sim BA∼B经过密道最短。 解题思路 引理:对于每个道路被破坏,最多只会经过一条边。 证明:对于每个答案,被破坏后,所在层数低的点找到一条可以走出他的子树的边就好了,如果要走两条边,中间的点要不在子树中,要不在子树外。在子树中直接那个点走就好了,在子树外就不用再走了。 ...

2018-10-30 14:35:48

nssl1255-B(轻功)【SPFA,分层图】

正题 题目大意 有k中轻功,n个木桩,每种轻功可以消耗wi sw_i\ swi​ s飞过aia_iai​个木桩,有些木桩有不可以被某种轻功飞过的限制,然后切换一次轻功要W sW\ sW s 解题思路 将图分成kkk层,每层表示在不同的轻功状态,然后根据提议建图就好了。 code #include<cstdio> #include<ve...

2018-10-30 14:24:44

nssl1254-A(林下风气)【树形dp】

正题 题目大意 求一棵树上有多少个联通块的最大值和最小值差为k。 解题思路 其实直接用差<=k的减去差<k的就是等于k的答案。 然后枚举一个点为最大值,然后只往小编号扩张就好了(不重)。 code #include<cstdio> #include<cstring> #include<algorithm> #define N 4000 #def...

2018-10-30 14:15:56

ssl提高组周一备考赛【2018.10.29】

前言 想去德育基地… 成绩 RankRankRank PersonPersonPerson ScoreScoreScore AAA BBB CCC 111 2017myself2017myself2017myself 220220220 100100100 606060 606060 222 2017lrz2017lrz2017lrz 210210210 100100100 ...

2018-10-30 08:57:13

nssl1248-B【点分治,平衡树】

正题 题目大意 有一颗树,求一条路径长度k,要求S≤k≤ES\leq k\leq ES≤k≤E,求最小的k。 解题思路 其实对于每个点进行点分治,每次将整棵子树的路径加入平衡树,然后在统计一次答案。时间复杂度O(n2)O(n^2)O(n2)。 之后我们发现其实每次就找该子树的重心继续,不用遍历整棵子树。时间复杂度O(能过)O(能过)O(能过) code #include<cstdio&...

2018-10-30 07:59:09

nssl1249-C【数论】

正题 题目大意 求 ∑a=1n∑b=1a(gcd(a,b)==a xor b)\sum_{a=1}^n\sum_{b=1}^a(gcd(a,b)==a\ xor\ b)a=1∑n​b=1∑a​(gcd(a,b)==a xor b) 解题思路 因为a==ba==ba==b时肯定不成立,所以直接计算a>ba>ba>b 那么g...

2018-10-29 12:57:51

nssl1247-A【dp】

正题 题目大意 将n个相同球放到k个相同的盒子里,求方案数。 解题思路 其实就是将n划分成k份,要求前面份的大于等于后面的,所以我们可以写dp fi,jf_{i,j}fi,j​表示分成i组,分了j。 然后 fi,j=fi−1,j−1+fi,j−if_{i,j}=f_{i-1,j-1}+f_{i,j-i}fi,j​=fi−1,j−1​+fi,j−i​ fi−1,j−1f_{i-1,j-1}fi−...

2018-10-29 12:50:34

ssl提高组周六备考赛【2018.10.27】

前言 高三dalao试图混入其中 成绩 RankRankRank PersonPersonPerson ScoreScoreScore AAA BBB CCC 111 2017myself2017myself2017myself 205205205 252525 808080 100100100 222 2013lyy2013lyy2013lyy 200200200 1001...

2018-10-27 14:05:41

nssl1230-序列【位运算】

正题 题目大意 长度为n的序列,求两个长度大于等于kkk的连续序列,一个位运算“和”后最大的答案,和“或”后最大的答案。 解题思路 首先ororor b=a or xb=a\ or\ xb=a or x的话,b⩾ab\geqslant ab⩾a 所以答案就是所有的或起来 然后andandand b=a and xb=a\ and\

2018-10-27 13:48:01

nssl1232-函数【数论,欧拉函数,莫比乌斯反演】

正题 题目大意 ∑d∣nf(d)=n\sum_{d|n}f(d)=nd∣n∑​f(d)=n 对于n个aia_iai​ 求 ∑i=1nf(ai)\sum_{i=1}^nf(a_i)i=1∑n​f(ai​) 解题思路——莫比乌斯反演 这个方法对于aia_iai​比较大时比较好用,但是事实证明本题过不了。 用莫比乌斯反演可得到此公式 f(n)=∑d∣nμ(d)∗ndf(n)=\sum_{d|n}\m...

2018-10-27 13:40:58

ssl_wyc

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