NanoApe's Blog

既是咸鱼又是辣鸡

【Plan B】#8

NanoApe posted @ 2015年12月23日 18:31 in 蒟蒻不做题提前退役 , 474 阅读

省选题真多啊……

50/50

1880: [SDOI2009]Elaxia的路线

无向图中给出两条路径的两端,求最长公共最短路径

四个点跑最短路,把最短路网提取出来,然后把同是两条路径上的最短路的边设为1,跑最长路(注意由于是无向图,所以某条路径还要反转方向再跑一边)

1925: [SDOI2010]地精部落

求抖动排列个数

F[i][j]表示由$1-i$所组成且$j=A[1]<A[2]$的抖动排列的个数,G[i][j]与其类似,只是$j=A[1]>A[2]$

$F[i][i+1-j]=G[i][j]=\sum_{k=1}^{j-1}F[i-1][o]$(所以G数组只是为了理解方便,可以去掉

1922: [SDOI2010]大陆争霸

神奇的Dijkstra

1923: [SDOI2010]外星千足虫

判断一个xor方程组是否有唯一解

就维护下线性基

1924: [SDOI2010]所驼门王的宝藏

Tarjan缩环后在拓扑图上找一遍

对于第一种类型的门,每行找一个作为往返中心,非第一种门连单向边,第一种门连双向边;第二种类似;第三种用个map加速查找,然后直接连

1927: [SDOI2010]星际竞速

费用流

每个点拆成入点和出点,S连所有出点,出点连入点(假如x能到y的话将x的出点连至y的入点),入点连T,对于跳跃就S连入点。流量都为1,费用则为时间

1941: [SDOI2010]Hide and Seek

KDTree

Click Here

1972: [SDOI2010]猪国杀

BZOJ模拟题系列,比杀蚂蚁难

Click Here

1974: [SDOI2010]auction 代码拍卖会

一个数字递增的数,我们可以看成是不超过9个类似"111111..."的数加在一起的结果

所以我们先求出所有类似"111111..."的数的mod值,并记录个数为cnt

设F[i][j][k]表示当前用到的k个“连一数”都满足$Mod\;p \in [0,i]$且数本身满足$Mod\;p=j$的方案数

$F[i][j][k]=\sum_{o=0}^k F[i-1][(j-o*i)mod\;p][k-o]*Calc(cnt[i],o)$,其中Calc表示从A个数可重复取B个数的方案数,$Calc(n,m)=C(n+m-1,m)$

2190: [SDOI2008]仪仗队

就欧拉函数求个总和

2241: [SDOI2011]打地鼠

枚举锤子长宽直接暴力求+最优性剪枝

2242: [SDOI2011]计算器

快速幂+ExGCD+BSGS

1007: [HNOI2008]水平可见直线

斜率从小到大排序,相同斜率取最上面的直线,然后弄个队列完事

1006: [HNOI2008]神奇的国度

弦图+最大势算法MCS

完美消除序列不是从后往前求的嘛,那你颜色也从后往前弄就行了

1009: [HNOI2008]GT考试

就是把KMP的状态转移弄成矩阵然后快速幂一发

1008: [HNOI2008]越狱

可能越狱方案数=总方案数-不能越狱方案数

1005: [HNOI2008]明明的烦恼

PruferSequence

这种一年前学的东西都忘光了QwQ

如何制造?每次找最小标号叶子,与其相连的点的标号扔进PS序列,然后删点

如何还原?根据PS序列算出每个点的度数,每次拿序列开头的数和最小标号叶子(度数为1)相连,最后剩余两点再连一次

性质?每棵树对应一个PS序列

然后这题就和顺利变成组合数学题了

1192: [HNOI2006]鬼谷子的钱袋

$Ans=log_2(x)$

1011: [HNOI2008]遥远的行星

由题目可知$f[i]=m_i*m_j/(i-j)(j \le Ai \ge 0.35i)$

前面暴力算,后面把$(i-j)$这部分看成平均数初略求

1188: [HNOI2007]分裂游戏

子游戏组合,就求SG函数完判断胜负关系再求可能方案

1010: [HNOI2008]玩具装箱toy

斜率优化

1193: [HNOI2006]马步距离

远的时候贪心(只走一个方向,在边界则轮流两个方向走,逐渐逼近终点)

近的时候随便搜索

1191: [HNOI2006]超级英雄Hero

随便二分匹配

1189: [HNOI2007]紧急疏散evacuate

先求出每个格到各个门的距离,然后二分答案+最大流判断

1195: [HNOI2006]最短母串

★把字符串看成点,就变成了求哈密顿路径了,状压DP可以接受

本来很容易的,然而要求最小字典序的答案。。。WTF(╯‵□′)╯︵┻━┻

1190: [HNOI2007]梦幻岛宝珠

F(i,j)表示j*2^i的背包,G(i,j)表示j*2^i+W%(2^i)的背包,Sum(i)表示前i层能达到的最大体积

先把物品分层,算F,然后算G,

$G(i,j)=max(F(i,j),F(i,j-k)+G(i-1,min(k*2+W\;and\;2^{i-1},sum(o-1))))$

1026: [SCOI2009]windy数

数位DP

1024: [SCOI2009]生日快乐

由于每块的面积要一样,所以每一步至多有20种切法,可以暴力搜

2756: [SCOI2012]奇怪的游戏

按照棋盘格子数的奇偶性分类讨论:偶数就二分答案+最大流判定,奇数就直接最大流判定

1025: [SCOI2009]游戏

记忆化搜索,求和为n的数列的最小公倍数种数

1033: [ZJOI2008]杀蚂蚁antbuster

BZOJ模拟题*2

1001: [BeiJing2006]狼抓兔子

平面图最大流转最短路求

1031: [JSOI2007]字符加密Cipher

双倍串连在一起后直接后缀数组求排名

3239: Discrete Logging

离散对数,BSGS

2480: Spoj3105 Mod

离散对数,然而模数可能不是质数所以要用ExBSGS

1467: Pku3243 clever Y

同上题

3122: [SDOI2013]随机数生成器

离散对数,BSGS

对a分情况讨论

若$a=0$直接判断

若$a=1$,$x_n=x_1+(n-1)b$,直接Exgcd

若$a>1$,$x_n=a^{n-1}x_1+b \frac {a^{n-1}-1}{a-1}\pmod p=t$

设$c$为$a-1$的逆元,用Exgcd解出$an−1$,最后用BSGS算一下$n$即可

1319: Sgu261 Discrete Roots

N次剩余

1420: Discrete Root

N次剩余,同上

4128: Matrix

离散对数,求逆改成矩阵求逆然后就可以做了

4271: Chemistry

具体见此

★△2219: 数论之神

数论综合

贴个Po姐姐的题解

1012: [JSOI2008]最大数maxnumber

线段树

1013: [JSOI2008]球形空间产生器sphere

高斯消元

设球心坐标,然后根据n+1个点做出n个方程

1015: [JSOI2008]星球大战starwar

并查集

离线完倒着做

1016: [JSOI2008]最小生成树计数

MST+并查集

由MST性质可知所有MST中相同长度的边数是一样的,那么算出相同权值边的连接方案数,然后乘起来就是答案

1029: [JSOI2007]建筑抢修

贪心

任务按t2从小到大排序,若能完成则完成,若不能但耗时比当前已完成最耗时的短则替换,否则就丢掉

1028: [JSOI2007]麻将

枚举等待牌和对子搜一发

1034: [ZJOI2008]泡泡堂BNB

最弱能打赢对方最弱的则打,最强能打赢对方最强的则打,否则让最弱的和对方最强的打

1037: [ZJOI2008]生日聚会Party

DP,将男生看成+1,女生看成-1,F[i][j][k]表示前i个数最大差为j且第i个数为第k大的方案数


登录 *


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