基地校活动心得(2019.07.25)

今天讲了高深基础算法,分别是递推,贪心,分治,它们都简狂。


递推

其实就是找规律(状态转移方程),但会把你 算||找 到吐,比如说铺瓷砖
首先,我们先把n=1-4的输出写出来

n=1 n=2 n=3 n=4
1 2 3 5

可以得出f[i]=f[i-1]+f[i-2],同时,定义f[1]=1,f[2]=2,然后就好了!

真简单

贪心

由局部最优解扩展到全局最优解,注意,你的贪心不一定正确,如果你想用贪心解决问题,要试着用反例否定它.

举个栗子:

非自然死亡

题目内容和标题好像没有什么关系

首先,两格的距离不包括斜对角线,题目没有说清楚.这题看似是比赛压轴,实际上简单,我们从左上角开始遍历棋盘,如果没有标记,就放一个棋子,然后把它周围两格距离的格子标记.于是,你就可以得到最优解了!

真简单+1

分治

分开来算!减少数据规模!让你的题目不再超时!

再举个栗子

求a^b%9 (b<=2^64)

如题,有的人可能会疑惑,直接pow(a,b)%9不就好了吗?看!(b&lt;=2^64) ,pow(a,b)%9时间复杂度是O(b),而2^64=18446744073709551616,不超时才怪;

所以,我们要用分治

先认为a=2,b=10;那么2^10=2^5*2^5,我们可以不重复计算2^5,同理可得

2^10=2^5*2^5;
2^5=2^2*2^2*2;
2^2=2*2;

数的计算(2019/07/24)

第一篇博客,写的不好请见谅

这是一道NOIP的水题,先看题目:

数的计算

题目描述

我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
1.          不作任何处理;
2.          在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3.          加上数后,继续按此规则进行处理,直到不能再加自然数为止.

输入

一个数n

输出

 一个数表示答案

样例输入

6

样例输出

6

 

看完题目,很显然,这道题可以用暴力,但众所周知,暴力出超时,所以我们要用打表递推的方式解决这道题。

我们以4为例,4后面可以跟1,2,所以只要算出1,2的所有可能性的和,就是4的所有可能性。我们来手动模拟一下:
f[1]=1;
f[2]=2=f[1]+1;
f[3]=2=f[1]+1;
f[4]=4=f[1]+f[2]+1;

代码如下


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>//万能头
using namespace std;
int main(){
    //文件读写
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
   
    int n,f[10001],i,j;//定义变量
    //输入
    cin>>n;
    //核心代码
    for(i=1;i<=n;i++){//1至n
        for(j=1;j<=i/2;j++){//只循环一半
            f[i]+=f[j];//加上之前的可能性
        }
        f[i]++;//加上自身的可能性
    }
    //---------分界线----------
    cout<<f[n];//直接输出
    return 0;
}

病毒入侵

矩阵乘法优化的动态规划。

考虑位数增长时答案的变化:

用数组 F[i][j] 记录长度为 i 且末尾三位的十进制表示为 j 的未感染 DNA 个数,那么每一个 j 可以向后转移到的状态如下:


j   DNA     possible subfix
0   000  +  0/1
1   001  +  0/1
2   010  +  0
3   011  +  0
4   100  +  0/1
5   101  +  nothing
6   110  +  0
7   111  +  nothing

上表还不太明显,用图表示:

那么转移就很明显了:


f[i+1][0] = f[i][0] + f[i][4]
f[i+1][1] = f[i][0] + f[4][0]
f[i+1][2] = f[i][1]
f[i+1][3] = f[i][1]
f[i+1][4] = f[i][2] + f[i][6]
f[i+1][6] = f[i][3]

但是,考虑到数据范围 ( L<=10^9 ),直接线性递推做会超时。

于是用矩阵乘法优化转移过程,具体实现见代码:

继续阅读病毒入侵

[BZOJ 2326] [HNOI 2011] 数学作业

矩阵乘法优化的线性递推。

令 f[i] 为 Concatenate(1 .. N) Mod M 的值。则显然地,有这么一个关于 f[i] 的线性递推式:

f[i] = f[i-1] * (10 ^ log10(i)) + i

但是直接用这个式子做的话复杂度是 O(n) 的,会超时。考虑利用矩阵乘法来计算。

把刚才的式子稍加变换,得:

f[i+1] = f[i] * (10 ^ log10(i+1)) + i+1

可以发现,对于位数相同的一段,10 ^ log10(i+1) 的值是固定的。可以考虑分段矩乘。

可以构造出这么两个矩阵:


   Matrix 1            Matrix 2

[ f[i], i,  1 ]     [ k ,  0,   0]     [ f[i]*k+i+1, i+1, 1]
[ 0   , 0,  0 ]  *  [ 1 ,  1,   0]  =  [ 0         , 0  , 0]
[ 0   , 0,  0 ]     [ 1 ,  1,   1]     [ 0         , 0  , 0]

那么对于位数相同的一段,Matrix 2 都是不变的,可以快速幂做掉。

还有一些边界情况需要多加考虑。注意在题目运算过程中间量可能会超出 long long 范围,所以需要使用类似快速幂的慢速乘以及 unsigned long long。

代码如下:

继续阅读[BZOJ 2326] [HNOI 2011] 数学作业