分类 Oi 下的文章:

4923: K小值查询 splay
发表于: | 分类:Oi | 评论:0 | 阅读:69
辣鸡bz卡我常数毁我青春 考虑把$>k$的数字分成两个部分,一部分在$[k+1,2k]$内,一部分在$[2k+1,inf]$ 在$[k+1,2k]$内的数字显然都至少变小了一半,那么每个数字最多在$log$次就变成了1,所以我们对于这部分直接暴力重新插入 然...

阅读全文>>

4921: 互质序列 枚举
发表于: | 分类:Oi | 评论:0 | 阅读:87
注意题中说的是取出一个子串 我去年买了个表我想了十分钟动态规划最后发现是连续子序列 那就非常套路了,考虑维护前缀gcd $pre$ 和 后缀gcd $last$ $pre$和$last$显然都只有$\log(n)$个取值直接暴力 #include <stdi...

阅读全文>>

4886: [Lydsy2017年5月月赛]叠塔游戏 dp
发表于: | 分类:Oi | 评论:0 | 阅读:68
首先他要求要用上所有的牌【划重点】 看错题的可以回去重新想去了 然后我们考虑他那个递增P用没有,其实就是让你确定一组互不相同的底,然后让高的和最大 考虑在边权直接连边 然后考虑$i\to j$表示以$i$为底$j$为高 然后这题大概就变得傻逼了一半,显然就是每个点...

阅读全文>>

4884: [Lydsy2017年5月月赛]太空猫 dp
发表于: | 分类:Oi | 评论:0 | 阅读:67
首先容易发现向左走就是在骗你 然后就是傻逼dp $f_{i,0/1}$表示到达$i$处的上/下面的最小代价 不会转移的左转NOIP普及组学习双线程dp 注意无解的情况 #include <stdio.h> #include <string.h&g...

阅读全文>>

4883: [Lydsy2017年5月月赛]棋盘上的守卫 Kruskal
发表于: | 分类:Oi | 评论:0 | 阅读:74
左侧$n$个点右侧$m$个点中间连$a_{i,j}$的费用 然后跑费用流 然后考虑直接$Kruskal$就行了,注意到我们求得是最小环套树森林哦……所以是可以存在一个环的,但是环和环直接是不能合并的 #include <stdio.h> #includ...

阅读全文>>

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP