NanoApe's Blog

既是咸鱼又是辣鸡

【Plan B】#10

NanoApe posted @ 2016年1月18日 14:37 in 蒟蒻不做题提前退役 , 1388 阅读

隔壁Child正在把之前用学长权限号交的题批量转移中。。。

拿不到Year#1了QwQ

50/50

1000: A+B Problem

看到这题还没写题解我就来充数了(跑

1297: [SCOI2009]迷路

矩阵DP,由于边长最多为9,于是拆边变成各个中间点,就可以矩阵DP了

1934: [SHOI2007]Vote 善意的投票

最小割,将同意的连源点,反对的连汇点,可知一种方案对应一种割,于是求最小割

1019: [SHOI2008]汉诺塔

构造题,与普通的汉诺塔一样得一层层推,然而层与层之间转化不止$x*2+1$那么简单,有可能是$x*3+2$

2749: [HAOI2012]外星人

可知到最后一定是2被分解,所以看分解出来的2的个数

2750: [HAOI2012]Road

最短路,对每个点跑最短路,然后对每个点x统计起点到x的最短路径数(拓扑DP)和x到其余各点的最短路径数(DFS),按边统计一下

2752: [HAOI2012]高速公路(road)

★线段树+概率

求每段路径的贡献,将公式变形,然后用线段树维护$v[i],v[i]*i,v[i]*i*i$的区间和,就可以算了

2302: [HAOI2011]Problem c

DP,可知编号小于i的至少得i个

设$f_{i,j}$表示编号小于i的有j个的方案数,$cnt_i$表示确定编号为i的人的个数,$sum_i$表示编号可以小于i的人的个数 

则$f_{i,j}=\sum_{k=cnt_i}^{j-i+1}f_{i-1,j-k}*C_{sum_i-cnt_i-(j-k)}^{k-cnt_i}$

那个组合数表示现在有$sum_i$个人,$cnt_i$个人已经确定必须选,$j−k$个人已经选完了,在剩下的人中选出$k−cnt_i$个人使其编号为i

2428: [HAOI2006]均分数据

写了个略残的模拟退火

2426: [HAOI2010]工厂选址

枚举工厂,先贪心把煤运往最便宜的地方,然后再来按代价从小到大调整

2298: [HAOI2011]problem a

DP,$F_i$表示名次1-i的最大可确定人数,$Num_{i,j}$表示名次在i至j的人数,则$F_i=F_j+Num_{j+1,i}$

2440: [中山市选2011]完全平方数

数论+容斥,二分答案,转化为求x以内有多少个无平方因子数,$cnt=\sum x/i^2*\mu(i)$

2438: [中山市选2011]杀人游戏

图论,问x个人成功的概率为$1-x/n$,Tarjan缩环后入度为1的点都要询问;假如有个点入度为1但连的点的入度都大于1,则答案减一

4031: [HEOI2015]小Z的房间

生成树计数,Matrix-Tree定理+行列式

做个基尔霍夫矩阵,然后去掉一列一行,求行列式的值(由于模数不为质数,所以行与行之间用辗转相除消元)

2743: [HEOI2012]采花

离线排序,左端点不断移动,维护每种颜色第二左的点的坐标

1225: [HNOI2001]求正整数

搜索,首先质数最多16个,然后就加各种剪枝各种搜索了(可以用log加法代替乘法比较当前值与答案的大小)

2783: [JLOI2012]树

dfs一遍

2768: [JLOI2010]冠军调查

最小割,这跟某道小朋友不肯睡觉的题一样啊

2665: [CQOI2012]编号

$C(5,7)$种状态,然后乱搞

1305: [CQOI2009]dance跳舞

二分答案+网络流

1260: [CQOI2007]涂色paint

DP,$F[i,j]=min(F[i,j-1](s[j]==s[i]~or~s[j-1]),F[i+1,j](s[i]==s[i+1]~or~s[j]),F[i,k]+F[k+1,j])$

1304: [CQOI2009]叶子的染色

树形DP,可以证明取哪个结点做根都一样

3108: [CQOI2013]图的逆变换

若A→B,C→B,A→D,但没有C→D,则为非法图

3107: [CQOI2013]二进制a+b

DP,$F[i,a,b,c,o]$表示末i位A用了a个1,B用了b个1,C用了c个1且是否进位(o)时的$C_{min}$

3293: [CQOI2011]分金币

默认每人的金币都从右边拿,拿的个数设为F[],让F[]的绝对值和最小,就排个序大家一起减掉中位数就行了

3503: [CQOI2014]和谐矩阵

每个点的约束条件弄成异或方程组,$O(1600^3)$(居然不会TLE

由第一行可以推出其他行,把最后一行的约束条件弄成异或方程组,$O(40^3)$

3109: [CQOI2013]新数独

搜索 or DLX

3295: [CQOI2011]动态逆序对

倒过来执行,然后CDQ分治+树状数组计算逆序对个数

3506: [CQOI2014]排序机械臂 & 1552: [Cerc2007]robotic sort

就Splay

3504: [CQOI2014]危桥

最大流跑一边,路径B的起点终点颠倒再跑一次

3626: [LNOI2014]LCA

树链剖分,转成区间加&区间和

3173: [TJOI2013]最长上升子序列

Treap可以支持

3170: [TJOI2013]松鼠聚会

首先把$max(x1-x2,y1-y2)$改成曼哈顿距离,然后横纵坐标各取中位数

设两点$(x1,y1)(x2,y2)$则其曼哈顿距离为

$$|x1-x2|+|y1-y2|=max((x1+y1)-(x2+y2),(x1-y1)-(x2-y2))$$

3171: [TJOI2013]循环格

费用流

满足条件的情况当且仅当每个点的入度出度等于1,然后就费用流一发

4000: [TJOI2015]棋盘

行的状态最多有$2^6$种,行与行之间的转移矩阵拿去快速幂松松

3999: [TJOI2015]旅游

树链剖分

带有方向的路径询问。。。于是线段树要考虑正反两向,线段树的遍历也要考虑先左子树还是右子树

3226: [SDOI2008]校门外的区间

线段树啊,除了整数多维护$x.5$这种数就行

2037: [SDOI2008]Sue的小球

来回DP,$F[i,j,k]$表示已走过区间[i,j]的最小消耗值,k表示当前在哪一端

2186: [SDOI2008]沙拉公主的困惑

数论,$ans=n!/m!*\varphi(m!)=n!*\frac{p-1}{p}*...$,其中p为不超过m的质数

线性求逆元

$inv[i]=(Q-Q/i)*inv[Q\%i]%Q$

证明:

设$t=Q/i,k=Q\%i$

则:

$$t*i \equiv -k \pmod Q$$

$$t*inv[k] \equiv -inv[i] \pmod Q$$

$$inv[i] \equiv -t*inv[k] \pmod Q$$

$$inv[i] \equiv (Q-Q/i)*inv[Q\%i] \pmod Q$$

3229: [SDOI2008]石子合并

专治这种问题的GarsiaWachs算法

设一个序列是$A[1..n]$,每次寻找最小的一个满足$A[k-1]<=A[k+1]$的$k$(方便起见设$A[-1]=A[n]=\infty$),那么我们就把$A[k]
$与$A[k-1]$合并,之后找最大的一个满足$A[j]>A[k]+A[k-1]$的$j$,把合并后的值$A[k]+A[k-1]$插入$A[j]$的后面

整个过程一个队列就可以实现

3231: [SDOI2008]递归数列

矩阵快速幂

1951: [SDOI2010]古代猪文

数论,Lucas+CRT

又费马定理可知先求$K\pmod{p-1}$的值再去快速幂即可

由于$(p-1)$不是素数,所以我们先用CRT拆开来,然后用Lucas算结果,再合并起来

2243: [SDOI2011]染色

树链剖分维护即可

2705: [SDOI2012]Longge的问题

数论

求$\sum gcd(i,n)$

枚举gcd的值,$gcd(i,n)=a$的数量为$\varphi(n/a)$(a是n的约数)

2282: [SDOI2011]消防

枢纽路径一定是在直径上,然后在所有极大合法枢纽中找最大值

1221: [HNOI2001]软件开发

经典费用流,以每次使用毛巾作为流量

1222: [HNOI2001]产品加工

DP,$F[o,i]$表示前o件事中第一人花了i小时的时候第二人花的最小时间,o这一维可以空间优化

1223: [HNOI2002]Kathy函数

打表可知满足条件的数,其二进制数都是回文串,然后就是数位DP的事了

1224: [HNOI2002]彩票

搜索,上下界剪枝勉强过得了

Avatar_small
zhouzixuan 说:
Jan 30, 2016 09:55:33 PM

太神了
gz弱渣看着您
%%%


登录 *


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