4 ixRic

尚未进行身份认证

我要认证

Even god envies youth.

等级
TA的排名 1w+

二进制状态压缩枚举子集

对于二进制状态 SSS,可以用此方法不重不漏地枚举出子状态:for (int sub = S; sub; sub = (sub - 1) & S) { // sub 为 S 的子集}【证明】 由 sub=(sub−1)∩Ssub = (sub - 1) \cap Ssub=(sub−1)∩S 可知 subsubsub 每次必然会变小,于是我们只需要证明区间 ((sub−1)∩S,sub)\left((sub - 1) \cap S, sub\right)((sub−1)∩S,sub) 中不

2020-05-30 10:15:40

洛谷P1117 [NOI2016]优秀的拆分(巧妙的计数方法)

文章目录题目分析代码题目[NOI2016]优秀的拆分分析统计以SiS_iSi​开头的形如AA\text{AA}AA的子串的数量,存入L[i]L[i]L[i];统计以SiS_iSi​结尾的形如AA\text{AA}AA的子串,存入R[i]R[i]R[i]。于是把可以把它们拼起来,答案就是∑i=2n(L[i]×R[i−1])\sum \limits_{i = 2}^{n} (L[i] \tim...

2020-05-03 19:57:51

NOI.AC170 数数(计数DP)

文章目录题目分析代码题目题目描述求有多少对1∼n1∼n1∼n的排列(a,b)(a, b)(a,b)满足m≤∑i=1nmax⁡{ai,bi}m \leq \sum\limits_{i = 1}^{n} \max\{a_i,b_i\}m≤i=1∑n​max{ai​,bi​}。两个方案(a,b)(a, b)(a,b)和(a′,b′)(a', b')(a′,b′)不同当且仅当存在iii使得ai≠a...

2020-03-28 15:31:38

LOJ530 「LibreOJ β Round #5」最小倍数(二分)

文章目录题目分析代码题目「LibreOJ β Round #5」最小倍数分析令n!=p1a1p2a2⋯pkakn! = {p_1}^{a_1}{p_2}^{a_2} \cdots {p_k}^{a_k}n!=p1​a1​p2​a2​⋯pk​ak​,那么ai=∑j=1∞⌊npij⌋a_i = \sum\limits_{j = 1}^{\infty} \left\lfloor \dfrac{n...

2020-03-28 11:32:25

LOJ2161 「POI2011 R2 Day1」差值 Difference(细节DP)

文章目录题目分析代码题目「POI2011 R2 Day1」差值 Difference分析考虑枚举两个字符分别作为子序列的出现次数最多和最少的字符。一个性质是,这两个字符到底是不是次数最多或最少的字符并不重要,我们只需要统计最大差值,就能自动避免不符合要求的情况(因为不符合要求的情况一定比大差值小)。简单来说,枚举字符aaa,bbb和区间[l,r][l, r][l,r],计算[l,r][l...

2020-03-28 11:17:54

C++类欧几里得算法

文章目录概述算法版题(本文用绿色\color{green}绿色绿色标注一切函数,用紫色\color{purple}紫色紫色标注部分可以O(1)O(1)O(1)计算的常量式,便于观察)(不知道为什么加了颜色过后括号不能自动变大了,将就看吧= =)概述类欧几里得算法用于求形如f(a,b,c,n)=∑i=0n⌊ai+bc⌋\color{green}{f(a, b, c, n)} \color{o}...

2020-02-20 12:25:48

[CTSC2006] 歌唱王国(概率生成函数 + KMP / 哈希)

文章目录题面分析代码题面洛谷P4548 [CTSC2006]歌唱王国分析先了解一下概率生成函数,对于一个随机变量aaa,它的概率生成函数是F(x)=∑i≥0(Pr(a=i)⋅xi)F(x)=\sum\limits_{i\geq0}(\text{Pr}(a=i)\cdot x^i)F(x)=i≥0∑​(Pr(a=i)⋅xi)对它求导得F′(x)=∑i≥0(Pr(a=i)⋅i⋅xi−1)F'(...

2020-02-09 17:37:25

[TopCoder 12984] TorusSailing(高斯消元主元法优化)

文章目录题面分析代码题面Vjudge TorusSailing分析首先得到一个DP方程dp[i][j]=12(dp[(i+1) mod N][j]+dp[i][(j+1) mod M])+1①dp[i][j]=\dfrac{1}{2}\left(dp[(i + 1)\ \text{mod}\ N][j]+dp[i][(j + 1)\ \text{mo...

2020-02-09 14:37:17

[SDOI2012]走迷宫(Tarjan + 概率DP + 高斯消元)

文章目录题面分析代码题面洛谷P6030 [SDOI2012]走迷宫分析设dp[u]dp[u]dp[u]表示从uuu走到TTT的期望步数,VuV_uVu​表示uuu能到的点的集合,那么有dp[u]=∑v∈Vu1∣Vu∣⋅(dp[v]+1)=1∣Vu∣∑v∈vudp[v]+1\begin{aligned}dp[u]&=\sum\limits_{v\in V_u}\dfrac{1}{|...

2020-02-09 12:58:31

网络流24题

文章目录1. 餐巾计划问题题面分析代码2.[CTSC1999]家园题面分析代码3.航空路线问题题面1. 餐巾计划问题【洛谷1251】餐巾计划问题题面题目描述一个餐厅在相继的 NNN 天里,每天需用的餐巾数不尽相同。假设第 iii 天需要 rir_iri​ 块餐巾(i=1,2,...,Ni=1,2,...,Ni=1,2,...,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 ppp 分;或者...

2020-02-07 12:32:32

斜率优化之凸包优化与李超线段树

文章目录前言例一前言本题的例题可能比较偏,但难度都是正常的(经典例题已经用传统斜率优化AC过了,不想再写)。例一Kalila and Dimna in the Logging Industry不用看题,直接看转移方程即可:dp[i]=min⁡1≤j<i{dp[j]+bj⋅ai}dp[i] = \min\limits_{1 \leq j < i}\{dp[j] + b_j \...

2019-12-28 09:59:41

[CodeForces 697F][CodeForces 696D] Legen...(AC自动机+矩阵加速)

文章目录题目分析代码题目time limit per test: 6 secondsmemory limit per test: 256 megabytesinput: standard inputoutput: standard outputDescriptionBarney was hanging out with Nora for a while and now he thin...

2019-11-14 17:39:30

C++高斯消元详解

文章目录前言直接来代码前言学了才发现这玩意贼简单虽然据说是复习。直接来高斯消元用于解一个线性方程组,就是:{a1,1⋅x1+a1,2⋅x2+⋯+a1,n⋅xn=a1,n+1a2,1⋅x1+a2,2⋅x2+⋯+a2,n⋅xn=a2,n+1⋯an,1⋅x1+an,2⋅x2+⋯+an,n⋅xn=an,n+1\begin{cases}a_{1,1}\cdot x_1+a_{1,2}\cdot ...

2019-11-13 08:04:43

代码规范

文章目录前言参考博客代码风格概览缩进空白符空格前言众所周知,人类具有鸽的本质,而我仅仅是突然觉得打空格挺好看,就写了这个文章,所以此文章说出的话是极有可能被我放掉的。另外,这个仅针对OI,其他的懒得写。参考博客主要是这两位神犇的神作_rqy’s Code Style for OIXXX(记不得了以后想起再说吧)代码风格概览所有的#include均放在文件开头,#include...

2019-11-11 20:30:36

[洛谷P2540]【NOIP2015】斗地主增强版(DP+搜索)

文章目录题目分析代码题目P2540 斗地主增强版分析如果不出顺子,那么怎么出最优是可以DP解决的:dp[i][j][k][l]dp[i][j][k][l]dp[i][j][k][l]表示一副牌有iii个炸弹、jjj个三张、kkk个顺子、lll个单牌的最优出法。在这个状态定义下,原来的4i+3j+2k+l4i+3j+2k+l4i+3j+2k+l张牌变成了i+j+k+li+j+k+li+j+k...

2019-11-11 20:11:18

[HNOI2019] 校园旅行(搜索+二分图性质)

文章目录题目分析代码题目注意数据范围是N≤5000N\leq 5000N≤5000!!分析考虑最plain的DP,dp[u][v]=1/0dp[u][v]=1/0dp[u][v]=1/0表示uuu到vvv是否有一条回文路径,如果dp[u][v]=1dp[u][v]=1dp[u][v]=1,那么dp[x][y]=1dp[x][y]=1dp[x][y]=1(xxx为uuu的邻结点,yyy为vv...

2019-11-11 10:48:31

【牛客CSP-S提高组赛前集训营5】B 十二桥问题(最短路+状压DP)

文章目录题目分析代码题目十二桥问题分析k≤12k\leq12k≤12,果断考虑状压。将所有必须走的边的端点u,vu,vu,v视为关键点,为每个关键点跑Dijkstra,然后状压DP。dp[S][i][0]dp[S][i][0]dp[S][i][0]表示走完集合为SSS的边,最后停在第iii条边的uuu点的最小代价;dp[S][i][1]dp[S][i][1]dp[S][i][1]表示...

2019-11-08 22:21:46

C++自动取模的模数类

一直想写,今天终于写出来了。使用方法:ModNumber<MOD> k,可以定义一个模MOD意义下的变量k,它接下来的所有运算都自动模MOD,不需要再手写。具体操作方法请自行探索:#define LL long longtemplate<const int _MOD> struct ModNumber{ int x; ModNumber(){x=0...

2019-11-06 18:51:01

浅谈WQS二分、带权二分、凸优化与一类斜率优化DP

幕天题意一个简单的转化二维DP朴素斜率优化带权二分我们先看一道简单题题意分析代码进入正题题目回顾分析加权权与段数的关系单调性两个问题DP朴素DP斜率优化就题论题的分析方法一个普适的结论代码后记除最后一张普适公式外,文中所有图像和公式均为原创,转载请附出处谢谢!!!题意[BZOJ 4518] Sdoi2016 征途求nnn个数a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1​,...

2019-11-05 10:39:33

[BZOJ 3551][ONTAK2010]Peaks加强版(Kruskal重构树+主席树)

文章目录题目分析代码题目Description在Bytemountains有NNN座山峰,每座山峰有他的高度hih_ihi​。有些山峰之间有双向道路相连,共MMM条路径,每条路径有一个困难值,这个值越大表示越难走,现在有QQQ组询问,每组询问询问从点vvv开始只经过困难值小于等于xxx的路径所能到达的山峰中第kkk高的山峰,如果无解输出-1。Input第一行三个数NNN,MMM,QQQ。...

2019-11-02 11:39:49

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。