小蒟蒻yyb - 博客园

2017年12月25日

摘要：【BZOJ2588】Count On a Tree（主席树）题面题目描述给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。输入格式：第阅读全文

posted @ 2017-12-25 19:21 小蒟蒻yyb 阅读(419) 评论(0) 推荐(0)

【BZOJ1901】【Luogu2617】Dynamic Ranking（主席树，树状数组）

摘要：【BZOJ1901】【Luogu2617】Dynamic Ranking（主席树，树状数组）题面神TM BZOJ权限题 "Luogu真良心" 题解如果不考虑修改很容易的主席树区间第K大考虑修改那么修改操作复杂度$O(nlogn)$ 因此，将区间的和利用树状数组来维护修改复杂度降为$O( 阅读全文

posted @ 2017-12-25 19:16 小蒟蒻yyb 阅读(473) 评论(0) 推荐(0)

2017年12月24日

【BZOJ3668】【NOI2014】起床困难综合症（贪心）

摘要：【NOI2014】起床困难综合症（贪心）题面 Description 21 世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。作为一名青春阳光好少年，atm 一直坚持与起床困难综合症作斗争。通过研究相关文献，他找到了该病的发病原因：在深邃的太平洋海底中，出现了一条阅读全文

posted @ 2017-12-24 22:27 小蒟蒻yyb 阅读(439) 评论(1) 推荐(0)

2017年12月19日

【Luogu2711】小行星（网络流，最大流）

摘要：【Luogu2711】小行星（网络流，最大流）题面题目描述星云中有n颗行星，每颗行星的位置是(x,y,z)。每次可以消除一个面（即x,y或z坐标相等）的行星，但是由于时间有限，求消除这些行星的最少次数。输入输出格式输入格式：第1行为小行星个数n，第2行至第n+1行为xi, yi, zi，阅读全文

posted @ 2017-12-19 22:12 小蒟蒻yyb 阅读(321) 评论(1) 推荐(0)

【BZOJ1857】传送带（三分）

摘要：【BZOJ1857】传送带（三分）题面 Description 在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在lxhgww想从A点走到D点，他想知道最少需要走多阅读全文

posted @ 2017-12-19 21:56 小蒟蒻yyb 阅读(316) 评论(0) 推荐(0)

【BZOJ1257】余数之和（数论分块，暴力）

摘要：【BZOJ1257】余数之和（数论分块，暴力）题解 Description 给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如j(5, 3)=3 mod 1 + 3 mod 2 + 阅读全文

posted @ 2017-12-19 20:30 小蒟蒻yyb 阅读(1489) 评论(0) 推荐(0)

【BZOJ2005】【NOI2010】能量采集（莫比乌斯反演，容斥原理）

摘要：【BZOJ2005】【NOI2010】能量采集（莫比乌斯反演，容斥原理）题面 Description 栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植物种得非常整齐，一共有n 阅读全文

posted @ 2017-12-19 19:51 小蒟蒻yyb 阅读(426) 评论(1) 推荐(0)

2017年12月9日

【BZOJ3262】陌上花开（CDQ分治）

摘要：【BZOJ3262】陌上花开（CDQ分治）题解 "原来放过这道题目，题面在这里" 树套树的做法也请点上面这回用CDQ分治做的其实也很简单，对于第一维排序之后显然只有前面的对后面的才会产生贡献那么，使用CDQ分治先分，每次递归子问题合并的时候每次考虑前面的对于后面的贡献最后统计一下答阅读全文

posted @ 2017-12-09 16:50 小蒟蒻yyb 阅读(467) 评论(0) 推荐(0)

【Luogu1345】奶牛的电信（网络流）

摘要：【Luogu1345】奶牛的电信（网络流）题面题目描述农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由c台电脑组成的序列a1,a2,...,a(c)，且a1与a2相连，a2与a3相连，等等，那么电脑a1和a(c)就阅读全文

posted @ 2017-12-09 11:38 小蒟蒻yyb 阅读(361) 评论(0) 推荐(0)

【BZOJ2152】聪聪可可（点分治）

摘要：【BZOJ2152】聪聪可可（点分治）题面 Description 聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快阅读全文

posted @ 2017-12-09 08:36 小蒟蒻yyb 阅读(290) 评论(0) 推荐(0)

【Luogu3806】点分治（点分治）

摘要：【Luogu3806】点分治（点分治）题面题目描述给定一棵有n个点的树询问树上距离为k的点对是否存在。输入格式： n,m 接下来n 1条边a,b,c描述a到b有一条长度为c的路径接下来m行每行询问一个K 输出格式：对于每个K每行输出一个答案，存在输出“AYE”,否则输出”NAY”(不包阅读全文

posted @ 2017-12-09 08:32 小蒟蒻yyb 阅读(398) 评论(0) 推荐(0)

2017年12月2日

NOIP2017+停课总结

摘要： yyb的NOIP2017的不堪回首的回忆阅读全文

posted @ 2017-12-02 21:39 小蒟蒻yyb 阅读(577) 评论(6) 推荐(0)

【BZOJ2301】【HAOI2011】Problem B（莫比乌斯反演）

摘要：【BZOJ2301】【HAOI2011】Problem B（莫比乌斯反演）题面 Description 对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。 Input 第一行一个整数n，接下来n行每行阅读全文

posted @ 2017-12-02 16:14 小蒟蒻yyb 阅读(280) 评论(0) 推荐(0)

【Luogu3455】【POI2007】ZAP-Queries（莫比乌斯反演）

摘要：【Luogu3455】【POI2007】ZAP Queries（莫比乌斯反演）题面题目描述 FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x include include include include include include i 阅读全文

posted @ 2017-12-02 15:49 小蒟蒻yyb 阅读(540) 评论(0) 推荐(1)

【HDU1695】GCD（莫比乌斯反演）

摘要：【HDU1695】GCD（莫比乌斯反演）题面题目大意求$a include include include include include include include include include using namespace std; define MAX 101000 inline 阅读全文

posted @ 2017-12-02 15:26 小蒟蒻yyb 阅读(647) 评论(3) 推荐(0)

【BZOJ2816】【ZJOI2012】网络（Link-Cut Tree）

摘要：【BZOJ2816】【ZJOI2012】网络（Link Cut Tree）题面题目描述有一个无向图G，每个点有个权值，每条边有一个颜色。这个无向图满足以下两个条件：对于任意节点连出去的边中，相同颜色的边不超过两条。图中不存在同色的环，同色的环指相同颜色的边构成的环。在这个图上，你要支持以阅读全文

posted @ 2017-12-02 15:03 小蒟蒻yyb 阅读(256) 评论(0) 推荐(0)

莫比乌斯反演

摘要：莫比乌斯反演初学莫比乌斯反演先膜一发高神：orz Gay神莫比乌斯反演有两种形式。。。第一种：如果我们有函数$f(x)$，以及$g(x)$，并且有： $$g(x)=\sum_{d|x}f(d)$$ 那么，我们就有： $$f(x)=\sum_{d|x}\mu(\frac{x}{d})g(d 阅读全文

posted @ 2017-12-02 11:44 小蒟蒻yyb 阅读(1123) 评论(5) 推荐(2)

【Luogu3398】仓鼠找sugar（树链剖分）

摘要：【Luogu3398】仓鼠找sugar（树链剖分）题面题目描述小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a）到餐厅（b），而他的基友同时要从他的卧室（c）到图书馆（d）。他们都会走最短路径。现在小阅读全文

posted @ 2017-12-02 08:43 小蒟蒻yyb 阅读(326) 评论(0) 推荐(0)

2017年11月18日

【BZOJ2157】旅游（树链剖分，Link-Cut Tree）

摘要：【BZOJ2157】旅游（树链剖分，Link Cut Tree）题面 Description Ray 乐忠于旅游，这次他来到了T 城。T 城是一个水上城市，一共有 N 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说，阅读全文

posted @ 2017-11-18 22:38 小蒟蒻yyb 阅读(349) 评论(2) 推荐(0)

【BZOJ3669】【NOI2014】魔法森林（Link-Cut Tree）

摘要：【BZOJ3669】【Noi2014】魔法森林（Link Cut Tree）题面题目描述为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图，节点标号为 1,2,3,…,n，边标号为 1,2,3,…,m。初始时小 E 阅读全文

posted @ 2017-11-18 19:05 小蒟蒻yyb 阅读(262) 评论(0) 推荐(1)

2017年11月16日

【BZOJ2049】洞穴勘测（Link-Cut Tree）

摘要：【BZOJ2049】洞穴勘测（Link Cut Tree）题面题目描述辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道阅读全文

posted @ 2017-11-16 23:53 小蒟蒻yyb 阅读(288) 评论(0) 推荐(0)

【BZOJ2002】弹飞绵羊（Link-Cut Tree）

摘要：【BZOJ2002】弹飞绵羊（Link Cut Tree）题面题目描述某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它阅读全文

posted @ 2017-11-16 23:49 小蒟蒻yyb 阅读(315) 评论(0) 推荐(0)

【BZOJ3282】Tree （Link-Cut Tree）

摘要：【BZOJ3282】Tree （Link Cut Tree）题面 "BZOJ权限题呀，良心luogu上有" 题解 Link Cut Tree班子提最近因为NOIP考炸了学科也炸了时间显然没有以后再来填LCT的坑这种题目直接上代码了。。 cpp include include includ 阅读全文

posted @ 2017-11-16 23:44 小蒟蒻yyb 阅读(548) 评论(2) 推荐(1)

2017年11月10日

NOIp2017 滚粗记

摘要：看看蒟蒻yybNOIp是如何炸裂的 yyb离AFO不远的故事阅读全文

posted @ 2017-11-10 14:06 小蒟蒻yyb 阅读(1416) 评论(29) 推荐(1)

【BZOJ1076】奖励关（动态规划，数学期望）

摘要：【BZOJ1076】奖励关（动态规划，数学期望）题面 "懒，粘地址" 题解我也是看了题解才会做看着数据范围，很容易想到状压然后，设$f[i][j]$表示当前第$i$轮，状态为$j$的期望枚举当前掉出来哪一个物品然后。。。。怎么转移？？？当前物品如果原来出现过，，我也不知道出现了几次呀。阅读全文

posted @ 2017-11-10 11:44 小蒟蒻yyb 阅读(314) 评论(1) 推荐(0)

小蒟蒻yyb的博客

AFO

公告