因为一些原因上周落了一些orz

这两周继续递归分治+一点二分

顺便改进了一下写博客的方法

[NOIP2001]求先序排列

题意：已知二叉树的中序和后序排列，求它的先序排列；

求解：二叉树的基本题，首先概念：先序：根-左-右；中序：左-根-右；后序：左-右-根

通过后序的最后一个位置确定根 通过这个根 在中序中找到根的位置 左边是左子树 右边是右子树；然后用递归的方式 事实上中序和后序表达的是同一颗子树 所以可以用长度求出第四个端点；

1
2
3
4
deal(l1,r1,l2,r2);//1中序 2后序

deal(l1,pos-1,l2,l2+pos-1-l1);//pos是在中序里找到的根的位置
deal(pos+1,r1,l2-l1+pos,r2-1);
[NOIP2004]FBI树

题意：全0：B；全1：I；有1有0：F；给定一个长度为2的n次方的“01”串，求其FBI树的后序遍历（左右根）

求解：递归做法 多点判断+后序输出 按左右根的顺序 如果到叶节点就直接判断输出

华华教月月做数学

题意：就是求 A^B mod P

求解：基础的快排板子 有一个大数的问题 （可以用python解决 __int128也可以过）或者可以将快速幂中的乘法拆成加法求余

快速幂的思想就是倍增思想 把幂拆掉求余 贴个板子

1
2
3
4
5
6
7
8
9
10
11
ll quickm(ll a,ll b,ll p)
{
    tmp=a,ans=1;
    while(b)
    {
        if(b&1) ans=ans*tmp%p;
        tmp=tmp*tmp%p;
        b>>=1;
     }
     return ans;
}
P2880 [USACO07JAN] Balanced Lineup G

题意：给个为n的数列 给q次询问 每次问a,b之间最大值和最小值之间的差值

求解：线段树 写两棵树 一棵树存最大的 一棵树存最小的 然后相减一下

P1115 最大子段和

题意：如题

求解：两种想法 一是分治：①求左边的最大字段和②求右边的最大字段和③求左边那段包含最右边点的最大字段和+右边那段包含最左边点的最大字段和 三者取最大

二是贪心：求前缀和 一旦前缀和小于0 就清零

写二的时候卡了一次 没有把第一个数存下来当sum 感觉这个贪心想的没有那么直观（我太菜了）

P1257 平面上的最接近点对

题意：如题

求解：还是分治：取个中轴线 ①求左边平面最接近点 ②求右边平面最接近点 ③分在两边平面的点 但可以用前两个求出来的最小值来约束y轴范围 排个序 这样就是从有限的点中求出最短距离；

P1613 跑路

题意：给n个点 m条边 一条边代表一千米 每秒可以跑2^k（k是任意自然数）千米 要求从1到n的最小时间

求解：这题感觉还是很有意思的 因为n<=50 所以可以很暴力 用倍增的思想预处理一下数据 i到t再到j 如果i到j有2^k-1千米的路 j到t又有2^k-1千米的路 那么i到j就有2^k的路 可以一秒到达 把dis改为1最后用Floyd法求最短路

疯狂写循环（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void bz()
{
    for(int k=1;k<=64;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int t=1;t<=n;t++)
    {
        if(b[i][j][k-1]&&b[j][t][k-1])
        {
            b[i][t][k]=true;
            dis[i][t]=1;
        }
    }
}
void floyd()
{
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); 
}
P2415 集合求和

题意：输入一个集合的所有元素 求所有子集的元素之和

求解：数学问题 首先会有2^n个子集 一半有这个数 另一半没有这个数 所以总共出现了2^（n-1）次 算一下就可以了

P3197 [HNOI2008]越狱

题意：有n个屋子 m种宗教 相邻的屋子里的人如果是同一种宗教就会越狱 问有多少种可能 答案对100003 取模

求解：还是数学问题 公式是mn-(m-1)(n-1) 还是一个快速幂的题目

但是！wa了好几次 后来发现是最后因为是一个减法 有可能存在负数的情况 所以要+p再%p

P2249 【深基13.例1】查找

题意：二分查找

求解：用的lower_bound（第一个≥x的位置）和upper_bound（第一个＞x的位置）自带函数做的

自己写的话很容易出现边界和卡在循环里面的问题 每次写的时候还是要注意一下

P1102 A-B 数对

题意：给N个数和C 求数列中满足A-B的数对个数

求解：写了个双循环然后用二分查找的函数直接写的 十分暴力简单的做法（

P1873 [COCI 2011/2012 #5] EKO / 砍树

题意：N个木材 需要总长度M 定一个H使得能够砍到M米木材 为了怕浪费 求最小的H

求解：二分的运用 就写个check函数判断一下 如果能砍到M就改r 否则就改l

P1678 烦恼的高考志愿

题意：给出m个分数线 以及n个同学的估分 要求帮每个估分找出最合理的分数线 两者相差为不满意度 求不满意度最小值

求解：还是用的二分函数 给分数线排个序 用每个人的估分去找相近的分数线 然后前后都算一下 取一个min值

P2440 木材加工

题意：把n根原木切割成 k 段长度均为 l 的小段木头 求l的最大值

求解：依然是二分的运用 写个check能切成k段就缩小一点l 反之放大 写起来很简单

总结

进度还是挺慢 其实很多东西都相当于复习了 但是！完全没有印象…

所以改进了一下写题解的方式 看起来轻松些 便于自己复习 也不贴代码了 有空还可以自己再码一遍 要不然学过和没学一样orz

做的题都不算难 重建一下信心（）下周继续二分