分类 Oi 下的文章:

BZOJ 4197: [Noi2015]寿司晚宴 状压dp
发表于: | 分类:Oi | 评论:0 | 阅读:47
这题我居然自己做出来了…… 主要是我以前做过这么一个问题 给定$n$个数,规定一组数的价值为这组数的最小公倍数,现在求所有组合的价值的和。这样的组合一共有$2^n−1$种,$n\le 500$,$val\le 200$ 然后这题是用了这么一个性质就是对于任意一个$...

阅读全文>>

3672: [Noi2014]购票 树链剖分 线段树 凸包 三分 斜率优化 点分治
发表于: | 分类:Oi | 评论:0 | 阅读:54
我要死了 调了三个小时最后发现是因为算叉积的时候爆long long ,日死出题人! 咳咳 首先我们把所有点到根变成根到所有点,然后变成了一个大力$dp$ $f(i) = min(f(j)+calc(j,i))$ $f(i) = min(f(j)+(len(i)-...

阅读全文>>

4025: 二分图 LCT维护动态二分图
发表于: | 分类:Oi | 评论:0 | 阅读:59
昨天半夜写来着,写完splay最后的讨论已经神志不清了 [早上一看写的什么玩意……删了重来 和以前我写的一道HDU的题目相似,这类题目都有两种解法,第一种是分治并查集,第二种是Lct,原理都是二分图中没有奇环 分治并查集的做法是建立一棵时间线段树,一个东西相当于一...

阅读全文>>

BZOJ 4521: [Cqoi2016]手机号码 数位dp
发表于: | 分类:Oi | 评论:0 | 阅读:79
貌似我的状态和大家的都不太一样 然后我跑的也确实比大家都慢…… 数位dp,从低位到高位,$f(i,j,k,l,m,n)$ 表示第$i$位是$j$,$i+1$位是$k$,然后把含有$4,8$的状态压进$l$,$m$(0/1)表示是否已经存在了三个相同的,然后$n$表...

阅读全文>>

BZOJ 4843: [Neerc2016]Expect to Wait 扫描线 暴力
发表于: | 分类:Oi | 评论:0 | 阅读:229
我们统计每个时刻的时候有多少人在等待 注意我们可以让这个人数是负数,负数的含义就是多了若干本书 然后……? 我们建立直角坐标系,把横坐标当成时间,纵坐标当成是等待的人数 那么询问就是直线,每次就是问一下直线上方的合法的面积了……大力扫描线一下就行了 注意这个扫描线...

阅读全文>>

Title - Artist
0:00

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

TOP