M_sea

「合集」BZOJ 1000~1099 题解
前言缓慢更新ing请结合右侧目录进行查询,或者直接在上方搜索栏中进行查询。1000-10091000 A+B Pr...
扫描右侧二维码阅读全文
01
2019/01

「合集」BZOJ 1000~1099 题解

前言

缓慢更新ing

请结合右侧目录进行查询,或者直接在上方搜索栏中进行查询。

1000-1009

1000 A+B Problem

模拟退火板子题。随机出一个结果,代价为这个结果与$a+b$的差的绝对值。

代码

1001 [BeiJing2006]狼抓兔子

最小割。

题解

1002 [FJOI2007]轮状病毒

打表找规律+高精度。或者用$\mathrm{Matrix\_Tree}$定理。

题解

1003 [ZJOI2006]物流运输

最短路+DP。

题解

1004 [HNOI2008]Cards

$\text{Burnside引理}$,组合数学。

题解

1005 [HNOI2008]明明的烦恼

$\text{prufer序列}$,组合数学。

题解

1006 [HNOI2008]神奇的国度

弦图最小染色。可以使用最大势算法,详见$\texttt{CDQ}$的论文。

题解

1007 [HNOI2008]水平可见直线

单调栈。考虑清楚出栈的条件。

题解

1008 [HNOI2008]越狱

正难则反。组合数学+快速幂。

题解

1009 [HNOI2008]GT考试

$\texttt{KMP}$,矩阵快速幂优化$\texttt{DP}$。

题解

1010-1019

1010 [HNOI2008]玩具装箱toy

斜率优化。

题解

1011 [HNOI2008]遥远的行星

用近似值乱搞。

题解

1012 [JSOI2008]最大数maxnumber

线段树。

题解

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

构造出二次方程组,邻项作差得到一次方程组,再高斯消元。

题解

1014 [JSOI2008]火星人prefix

平衡树+$\texttt{Hash}$。

题解

1015 [JSOI2008]星球大战starwar

倒推,并查集。

题解

1016 [JSOI2008]最小生成树计数

$\texttt{Kruskal}$+$\texttt{dfs}$。

题解

1017 [JSOI2008]魔兽地图DotR

很麻烦的DP。

题解

1018 [SHOI2008]堵塞的交通traffic

维护动态图连通性。可以使用线段树分治或者$\texttt{LCT}$。

题解

1019 [SHOI2008]汉诺塔

模拟+递推。关键在于搞出递推式。

题解

1020-1029

1021 [SHOI2008]Debt 循环的债务

DP。

题解

1022 [SHOI2008]小约翰的游戏John

博弈论($\texttt{Anti-SG}$游戏)。

题解

1024 [SCOI2009]生日快乐

dfs。

题解

1025 [SCOI2009]游戏

线性筛,DP。重点在转换题意。

题解

1026 [SCOI2009]windy数

数位DP。

题解

1027 [JSOI2007]合金

计算几何+$\texttt{Floyd}$。

题解

1028 [JSOI2007]麻将

暴力枚举。注意怎样凑更优秀。

题解

1029 [JSOI2007]建筑抢修

贪心。用堆来维护。

题解

1030-1039

1030 [JSOI2007]文本生成器

AC自动机上跑DP。

题解

1031 [JSOI2007]字符加密Cipher

倍长字符串,然后跑后缀排序。

题解

1032 [JSOI2007]祖码Zuma

区间DP。假题

题解

1034 [ZJOI2008]泡泡堂BNB

贪心。

题解

1036 [ZJOI2008]树的统计Count

树链剖分,用线段树维护。

题解

1037 [ZJOI2008]生日聚会Party

DP。

题解

1038 [ZJOI2008]瞭望塔

枚举+计算几何(然而初中知识就可以解决)。

题解

1040-1049

1040 [ZJOI2008]骑士

基环树最大独立集。

题解

1041 [HAOI2008]圆上的整点

神仙题。

题解

1043 [HAOI2008]硬币购物

DP+容斥。

题解

1044 [HAOI2008]木棍分割

二分+DP。前缀和优化+滚动数组。

题解

1045 [HAOI2008]糖果传递

贪心。

题解

1046 [HAOI2007]上升序列

DP。

题解

1047 [HAOI2007]理想的正方形

二维ST表。

题解

1048 [HAOI2007]分割矩阵

DP。记搜比较好写?

题解

1049 [HAOI2006]数字序列

DP。需要一个神仙结论。

题解

1050-1059

1050 [HAOI2006]旅行comf

枚举+并查集。

题解

1051 [HAOI2006]受欢迎的牛

$\texttt{Tarjan}$缩点。

题解

1052 [HAOI2007]覆盖问题

二分答案+dfs。

题解

1053 [HAOI2007]反素数ant

爆搜/打表。

打表代码

1054 [HAOI2008]移动玩具

状压搜索。

题解

1055 [HAOI2008]玩具取名

DP。

题解

1056 [HAOI2008]排名系统

双关键字平衡树。

题解

1057 [ZJOI2007]棋盘制作

转换为0/1矩阵,再用悬线法求最大子矩阵。

题解

1058 [ZJOI2007]报表统计

平衡树。或者用STL。

题解

1059 [ZJOI2007]矩阵游戏

行列连边,再二分图匹配。

题解

1060-1069

1060 [ZJOI2007]时态同步

树形DP。

题解

1061 [Noi2008]志愿者招募

费用流。

题解

1063 [Noi2008]道路设计

树形DP。

题解

1066 [SCOI2007]蜥蜴

网络流。

题解

1067 [SCOI2007]降雨量

ST表/线段树。情况和细节都很多。

题解

1068 [SCOI2007]压缩

区间DP。

题解

1069 [SCOI2007]最大土地面积

凸包,旋转卡壳。

题解

1070-1079

1070 [SCOI2007]修车

拆点跑费用流。

题解

1071 [SCOI2007]组队

神仙题qwq

题解

1072 [SCOI2007]排列perm

$\texttt{next_permutaion}$。

题解

1076 [SCOI2008]奖励关

状压DP+期望DP。

题解

1077 [SCOI2008]天平

差分约束+$\texttt{Floyd}$+枚举。

题解

1080-1089

1081 [SCOI2005]超级格雷码

找规律,然后直接爆搜。

题解

1086 [SCOI2005]王室联邦

树分块。

题解

1087 [SCOI2005]互不侵犯King

状压DP。

题解

1088 [SCOI2005]扫雷Mine

枚举初始状态,再DP。

题解

最后修改:2019 年 02 月 20 日 09 : 40 AM

8 条评论

  1. sdgzy

    A+B 用退火搞还行OωO

    1. M_sea
      @sdgzy

      qwq

  2. wsm000

    话说Bzoj现在可以注册?OωO

    1. M_sea
      @wsm000

      可以的qwq
      见首页通知qwq

      1. wsm000
        @M_sea

        注册了,谢谢ヾ(≧∇≦*)ゝ

  3. smy

    缓慢吗qwq

    1. M_sea
      @smy

      有点吧qwq

      1. smy
        @M_sea

        可是您更新速度不知道比我快到哪里去了

发表评论