NanoApe's Blog

既是咸鱼又是辣鸡

【Plan B】#6

NanoApe posted @ 2015年10月09日 18:15 in 蒟蒻不做题提前退役 , 625 阅读

进入了省选题时间了。。。

刷的速度越来越慢了。。。

现在已完成:

50/50

3195: [JXOI2012]奇怪的道路

设置状态(x,y,S)表示现在在x点连边至后面的点,且已连边数为y,后面的奇偶状态为S的方案数

★2439: [中山市选2011]序列

你有一个数列S,每次操作可以把某段区间的Si-Sj增加或减少一个数,费用为其改变数大小。求最小代价使得数列满足S1<...<Sx>...>Sy<...<Sz>...>ST(Sy不能改变)(N<100000)

先把数列构造成差分数列,那么操作就变成修改两个数一个加一个减。枚举Sy,然后找左右边分别弄成一段正数+一段负数的最小代价。单调队列优化至\(O(n)\)

2463: [中山市选2009]谁能赢呢?

由多米诺骨牌摆放方案可知n分奇偶讨论就行

2464: [中山市选2009]小明的游戏

转成最短路

2469: [中山市选2010]简单数谜

搜索大法

2467: [中山市选2010]生成树

可以知道要拿n+1条边,且中间的圈一定要拿走至少一条,然后就DP一遍

3997: [TJOI2015]组合数学

DAG中有个D开头的定理,最小链覆盖=最长反链

3996: [TJOI2015]线性代数

给一个N*N的矩阵B和一个1*N的矩阵C,求出一个1*N的01矩阵A,使得\(D=(A*B-C)*A^T\)最大(N<1000)

$$D=\sum_{i=1}^n \sum_{j=1}^n a_i a_j b_{i,j} - \sum_{i=1}^n a_i c_i$$

然后就转化模型,变成一道最大权闭合图的最小割裸题了

3175: [TJOI2013]攻击装置

转化成二分图后求最小点覆盖集,最小点覆盖集=最大匹配

3174: [TJOI2013]拯救小矮人

贪心排序后DP。按A+B从小到大排序(因为越小的让其越先出去)然后F[i]表示现在出去i人后的剩余人的最高高度

4034: [HAOI2015]T2

裸树剖

2748: [HAOI2012]音量调节

水题

2429: [HAOI2006]聪明的猴子

就一道MST

3105: [CQOI2013]新Nim游戏

(拟阵)给定一个集合,求一个最大子集S,使得S的任意子集的xor和不为0

按火柴总数排序后贪心取并维护线性基

3106: [CQOI2013]棋盘游戏

对抗搜索。可以证明假如相邻的话白棋必胜,否则黑棋必胜,且步数最多为3n,然后就记忆化搜索。

1257: [CQOI2007]余数之和

求\(\sum_{i=1}^n k\;mod\;i\)

枚举k/m的数,会发现k%m是个等差数列,然后就\(O(\sqrt n)\)了

2751: [HAOI2012]容易题

就一个快速幂

4004: [JLOI2015]装备购买

(拟阵)有个向量集合,求一个最大子集S,使得S的任意子集的系数向量和(就是设每个向量为\(A_i\),系数为\(B_i\),值为\(\sum B_i*A_i\))不可能为0

也是拟阵,按花费排序后贪心取并维护线性基

4037: [HAOI2015]Str

\(F(x)\)表示x拆分成若干个不大于m的数的和的方案数,\(G(x)\)表示将数字串分割成若干个数,将他们加起来,求F,并求和。求\(G(x)\)

首先F可以通过矩阵快速幂计算得到,设A为转移矩阵,可以知道\(G(123)=F(12+3)=A^{12+3}=A^{12}*A^3\),然后G也可以\(O(n^2)\)计算,叠加起来就是\(O(n^2 m^3)\),顺便%太多次会TLE,卡常数

4033: [HAOI2015]T1

有大小为N的树,K个点染成黑色,价值定义为黑点两两距离和+白点两两距离和,求最大价值

树状DP,然后就结合背包随便做了,看起来复杂度是\(O(n^3)\),事实上可以证明复杂度为\(O(n^2)\)

3631: [JLOI2014]松鼠的新家

裸链剖

3172: [TJOI2013]单词

AC自动机,然后每个字符串的前缀节点+1,然后fail树累积至树根

3998: [TJOI2015]弦论

SA裸题

2761: [JLOI2011]不重复数字

省选签到题

4029: [HEOI2015]定价

省选签到题*2

3609: [HEOI2014]人人尽说江南好

首先,每个局面都有最多进行轮数,奇数的话先手必胜,否则后手必胜,而且可以证明必胜的那一方绝对能把局面推到最多进行轮数的情况(然而不会证,直觉)

3191: [JLOI2013]卡牌游戏

就是概率DP

2764: [JLOI2011]基因补全

DP,类似最长公共子序列

2431: [HAOI2009]逆序对数列

DP,F[i,j]表示数列中1..i的数构成的序列的逆序对为j的方案数

2425: [HAOI2010]计数

数位DP,预处理C算方案数

2423: [HAOI2010]最长公共子序列

裸题。。。

1046: [HAOI2007]上升序列

倒过来做最长下降序列,然后从后往前扫一遍

1045: [HAOI2008]糖果传递

一开始每人有\(K_i\)个苹果,相邻可以传递,用最小传递次数使得所有人的苹果数一样

设p[i]表示第i人需要传给第i+1人的苹果数,然后我们会发现同时增减所有p时都是合法的,而答案等于p的绝对值之和,于是当p的中位数=0时答案最优

1044: [HAOI2008]木棍分割

对于问题一是二分答案+贪心,问题二则是DP+滚动数组。

1042: [HAOI2008]硬币购物

DP+容斥,先预处理出每种价钱的方案数,然后$Ans=([Null])-([1]+[2]+[3]+[4])+([12]+[13]+[14]+[23]+[24]+[34])……$

($[abc]$表示哪些种硬币超出使用限制)

1048: [HAOI2007]分割矩阵

状态数(10*10*10*10*10)不多,可以考虑记忆化搜索

2424: [HAOI2010]订货

裸网络流

1047: [HAOI2007]理想的正方形

给一个矩阵,选取一个子正方矩阵,求$Min(max-min)$

利用单调队列两次,求出每个正方形的max&min

1041: [HAOI2008]圆上的整点

已知$z$,求符合$x^2+y^2=z^2$的$(x,y)$对数

先考虑本原勾股数,本原勾股数满足:

$$x=ab$$

$$y=\frac{a^2-b^2}2$$

$$z=\frac{a^2+b^2}2$$

其中$1 \le a < b$且$gcd(a,b)=1$

然后只需要将$x,y,z$同乘个正整数$d$就能得到所有勾股数了

算法也就出来了,枚举$d$为$z$的约数,然后再枚举$a$,判断$b$是否存在

2301: [HAOI2011]Problem b

莫比乌斯反演

$$gcd(x,y)=k(a \le x \le b 且 c \le y \le d)$$

首先,利用子矩阵求和的特点,转成子矩阵前缀和;然后消掉k得到

$$gcd(x/k,y/k)=1(1 \le x \le a/k 且 1 \le y \le b/k)$$

然后就变成求互质对数了。根据莫比乌斯反演某条需要用到容斥的公式,互质对数为

$$\begin{align} & \sum_a^{x/k} \sum_b^{y/k} [gcd(a,b)=1] \\ = & \sum_a^{x/k} \sum_b^{y/k} \sum_d [d|gcd(a,b)]\mu(d) \\ = & \sum_d \mu(d) \frac{x}{kd} \frac{y}{kd} \end{align} $$

然后对于某一段$d$,$(x/kd)$和$(y/kd)$是不变的,于是我们就可以计算$\phi(d)$的前缀和,将$(x/kd)$和$(y/kd)$不变的那一段合并起来计算

2299: [HAOI2011]向量

裴蜀定理,首先将8种操作换成6种:

$(\pm 2a,0)(\pm 2b,0)(0,\pm 2a)(0,\pm 2b)(a,b)(b,a)$

其中最后两种只需用到一次,即可完成题目所需要的所有操作

然后就是枚举最后两种的使用情况(4种可能),列两个个二元方程,判断是否有整数解(Exgcd)

1051: [HAOI2006]受欢迎的牛

询问有多少点能由任意一个点出发到达

Tarjan缩点完判断一下有没有出度为0的联通块,有多个则无答案,一个则答案为此联通块大小

1054: [HAOI2008]移动玩具

傻叉题

1258: [CQOI2007]三角形tri

傻叉题

1303: [CQOI2009]中位数图

傻叉题

1053: [HAOI2007]反素数ant

质因数越小越好,然后约数个数可以通过分解质因数算得,接着就搜索+剪枝大法(其实前10个素数就够用了)

1306: [CQOI2009]match循环赛

搜索+剪枝,能加的剪枝就加

1816: [Cqoi2010]扑克牌

二分答案,J的功能就是来填补其余牌的空缺的,且J的使用张数不能超过答案(否则根据抽屉原理,一定会有一个套牌包含两个J,然而这是不合法的)

1818: [Cqoi2010]内部白点

首先证明不可能有无限循环的情况,而且只需一回合,所有能变黑的白点就都会变黑。

然后离散化的时候就顺便找每个横坐标的垂线段,接着坐标排序完用树状数组维护,垂线段上端点+1,下端点-1,扫完一个纵坐标就累计答案

1055: [HAOI2008]玩具取名

就一个搜索,加点状压


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter