基地校活动心得(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;

1.1 入门部分

由于都是一些入门知识,本蒟蒻就会讲的稍微快点,如有疑问之处,可留下评论告知在下,在下争取做的更好。(由于是些入门知识,有的地方代码复杂度视题目而定)

第一部分:模拟。

模拟指的是一些“给你指令,你编程去做”的题目类型,完全考验Oier的代码量以及对语言的熟悉度还有思维灵活度。
例题
https://www.luogu.org/problemnew/show/P1187
http://59.61.214.20:3000/problem/show/1006

继续阅读1.1 入门部分

【纪中】Day10+

【C】
题意:求无向图中两点之间的路径数。
水题。由于每个点只在一个简单环上,所以缩点以后图就变成一颗树了,而只要进过一个环,就有两条路。
于是用tarjin缩点再跑lca即可。缩点也可以用dfs,写完tarjin结果忘了无向图怎么处理,只好改dfs。。。
【棋盘游戏】
题意:从一个点走到(0,0),一步可往左、下、左下三个方向走任意步,询问先手的输赢情况。
明显的博弈论,正解是威佐夫博弈,公式很简单:
记w=(int)[((sqrt(5)+1)/2)*z ];
若w=x,则先手必败,否则先手必胜。
来讲讲部分分的做法。
30%:显然,若起点为(0,0)则先手必输,那么,从(0,0)右、上、右上的点便是先手必胜。接着,从(0,0)开始一层一层地找,若没有被标记过先手必胜,则就是先手必败。
60%:既然可以从上述方法得知输赢情况,那么,可以发现先手必败的情况特别少,打表发现,每一个必败点(x, y),(x - 1)(y - 2)、(x - 2)(y - 3)其中一个一定是必败点,可以找规律求解(反正我没找到)。
【偷窃】
题意:在一堆正方体中拿走最多的数量,并且使其三视图不改变。
正解是二分图匹配,对于行和列的最高点建边,再分别连向源点和汇点,流量是其最大值的数值,跑网络流求最大匹配。
但是,水水就能过去的题为什么要打网络流。要使三视图不改变,只要最高的不少,其余的全搬走只剩一个即可。那么,对于列上的最大值,去找行上有没有与其想等的,如果有,在一个位置就可满足行列的要求,如果没有,就随便找一个比它大的放。
代码如下:
继续阅读【纪中】Day10+

传送带(三分查找)

题目描述:

在一个二维平面上有两条传送带,每一条传送带可以看成是一条线段。两条
传送带分别为线段 AB 和线段 CD。小 y 在 AB 上的移动速度为 P,在 CD 上的
移动速度为 Q,在平面上的移动速度 R。现在,小 y 想从 A 点走到 D 点,请问
他最少需要走多长时间。

输入格式:

第一行是4个整数,表示A和B的坐标,分别为Ax,Ay,Bx,By。
第二行是4个整数,表示C和D的坐标,分别为Cx,Cy,Dx,Dy。
第三行是3个整数,分别是P,Q,R。

输出格式:

输出一行一个数,表示小 y 从 A 点走到 D 点的最短时间,保留到小数点后
2位。

样例输入:

0 0 0 100
100 0 100 100
2 2 1

样例输出:

136.60

数据范围:

对于30%的数据满足:
1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=10
1<=P,Q,R<=5
对于100%的数据满足:
1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000
1<=P,Q,R<=10

继续阅读传送带(三分查找)

Day12

【质数生成器】
题意:询问区间[m,n]里的质数,1<=m<=n<=10^9,n-m<=1000000。
显然线筛过不了1e9的数据,只能对[m,n]区间求质数。
一个数n如果是合数,那么必定会被sqrt(n)中的质数整除,考虑普通筛(233)。对于[m,n]中的数,只需枚举每个质数,将其在这个区间中的倍数筛去即可。
正确性:线筛只要将sqrt(n)中的质数筛出,大概是1e5左右,明显不会超时。[m,n]区间的普通筛是用质数去筛,比用每个数筛的时间大大减少。
【魔法树】
题意:一棵树,每个点有一种属性。一条路径上的魔法值是这样计算的:在起点的时候,魔法值为 1,每经过一条边,假设这条边拥有的魔法属性是 ci,如果这是奇数次经过带有 ci 魔法属性的边,则将魔法值乘上 ci 对应的魔法系数,否则将魔法值除以 ci 对应的魔法系数。
简化题目,即如果奇数次经过ci的点,那么答案就乘上di,否则这个ci对答案没用贡献。
考虑用二进制来表示每种属性的贡献,对于询问的两个点,只需以任意的点为树根,求出每个点的二进制数,在询问使^即可。
【hill】
题意:给出一座山,求一个最低的点能够看到所有地方。
简单的三分题。

Day7

【最长上升子序列】
题意:对一个序列进行操作,可以在序列最后加上一个数,可以回到k时的序列,求每次操作后序列的最长上升子序列长度。
【LIS求法】:通常求最长上升子序列都是n^2动规,当n较大时便要考虑nlogn的算法。
设f[k]表示长度为k的LIS最末尾的元素,易知f是单调递增的,对于新加入的x,如果f[k] < x, 意味着最长上升子序列的长度可以加1。如果f[k] > x,那么 对于f[i] > x > f[i - 1]考虑f第i位的值哪个更优?显然要取x。求i可以用二分优化,LIS便能在nlongn的时间内求出。
这题需要回到第k时的序列,由上述算法可知,对于操作j、j - 1,f数组的变化只有一个数,于是用可持久化线段树来维护这个数组,使修改和查询的时间变成logn, 时间复杂度是O(nlog^2n)。
由于时间复杂度和空间复杂度与题目要求十分相近,要考虑常数与每个结点的线段树子节点数量。
正解对于每个回到k序列的操作建一棵树,直接在这棵树上跑LIS,时间复杂度O(nlogn)。
【图的X匹配】
题意:对于一个多边形,使取出的边没有交点(即没有相邻的边)的方案数。
打表可以发现答案的规律类似斐波那契数列, 由于没有取模, 需要用高精度完成加法操作, n的值最大为10000, 最好用滚动数组。
证明:
【努力】
题意:使n个点形成一棵树的连边方法。
由prufer数列可得n个点的无向图有n^(n-2)种, n个点的树有n-1条边,答案便是n^(n-2)*(n-1)!。

代码如下:

继续阅读Day7

2017长乐集训day2

首先是其实是A+组的B组

T1      今天唯一的得分项也是这几天第一次A的题,题目要求区间[0...1000]一些二次函数的最大值中的最小值,注意区间可取的数可为实数(刚开始被这个卡样例),因为二次函数的a总是大于零,即开口向上,可知F[x]在区间内定有最小值,画图可知。于是便可用三分查找的方法不断逼近最小值(要注意精度)。

 

T2        字符串分块,动态规划,不是很清楚

 

T3        非常强势的暴力,同样需要非常强势的预处理。。用线段树什么的

--------------------------------------下面是萌萌的分割线----------------------------------

继续阅读2017长乐集训day2

Day2

【曲线】
题意:令f(x)为多个二次(一次)函数的最大值,求f(x)的最小值。
画图可以发现两个二次函数取最大值的图像形状类似二次函数,可得f(x)的图像也类似二次函数。那么,可以在所给区间内用三分求出答案。
二分也可完成此题,二分答案ans,暴力判断每个二次函数<=ans的区间是否有交集,若有,则答案可行,反之答案不可行。

【挑战】

题意:将字符串分块,使每个块中的字母都在下一个块中出现过。(即下一块每个字母的出现次数比当前块多)。求最多的分块。
令f[i][j]表示在i位是最后一个块的长度为j的答案。可由f[i - j][k]转移得到。时间复杂度为O(n ^ 3)。可得70分。
改进这个算法,因为要求块最多,应用贪心的思想,每个块的长度越少,块的数量越多。令f[i]表示以i为结尾最后一块的长度最短是多少。可以由f[i - f[i]]转移得到。

【序列】

题意:判断序列的所有子序列是否都有数只出现一次。
暴力枚举每个子序列,判断是否符合条件,可得30分。
改进暴力,对于一个a[i],前一次出现记为pre[i],后一次出现记为nex[i]。那左端点l在pre[i]+1..i,右端点在i..nex[i]-1都是合法的。如果判定一个区间[l,r],a[i]是其中唯一出现过的数字。那这个区间就可以切割成判定2个区间[l,i - 1],[i + 1, r]。那对于一个区间[l,r],i,j同时从左边和右边开始扫,碰到第一个唯一出现的数字就切割。直到l>=r。
这种做法看起来很像暴力,但实际上跑得飞快。时间复杂度证明:T(n) = T(k) + T(n-k)+min(n, n - k)。一种直观的想法就是,每次复杂度都是较小的那个区间。倒过来看相当于较小的合并到较大的。那就是启发式合并。O(nlogn)。

主要代码如下:

继续阅读Day2

2017/7/6 东海集训

https://vjudge.net/contest/164345#problem

vjudge上的题目2.2一往直前贪心法

今日成果4T

TA 为字符串贪心    刚开始时理解题目不到位,没有考虑前后字母相同的情况就一直W,最后在A.K.Z.的帮助下得以脱困。

下为code


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

char z,c[2001],s[2001];
int l,n;

int main(void)
{
    scanf("%d ",&n);
    int aa=0;
    while (scanf("%c",&z)==1)
    {
        if (z>='A' && z<='Z')
        {
            aa++;
            c[aa]=z;
        }
    }
    int he=1,ta=n,now=0;
    for (int i=1;i<=n;i++)
    {
        int h=he,t=ta;
        while (c[h]==c[t] && h<t)
        {
            h++;
            t--;
        }
        if (c[h]<c[t])
        {
            now++;
            s[now]=c[he];
            he++;
        }
        else
        {
            now++;
            s[now]=c[ta];
            ta--;
        }
    }
    for (int i=1;i<=n;i++)
    {
        printf("%c",s[i]);
        if (i%80==0)
        {
            printf("\n");
        }
    }
    printf("\n");
    return 0;
}

TB 为用最少的线段覆盖点,水题,不多做评论。

下为code


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int a[1010],vis[1010],p[1010],ans,n,r;

int main(void)
{
    while (1)
    {
        ans=0;
        scanf("%d%d",&r,&n);
        if (r==-1 && n==-1)
        {
            break;
        }
        memset(a,0,sizeof a);
        memset(p,0,sizeof p);
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&p[i]);
        }
        sort(p+1,p+n+1);
        int now=1;
        while (now<=n)
        {
            int nn=now;
            for (int i=now+1;i<=n;i++)
            {
                if (p[i]-p[now]<=r)
                {
                    nn++;
                }
                else
                break;
            }
            now=nn;
            for (int i=now+1;i<=n;i++)
            {
                if (p[i]-p[now]<=r)
                {
                    nn++;
                }
                else
                break;
            }
            now=nn;
            ans++;
            now++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

TC 与合并果子非常相似,由于时间限制为2s,所以刚开始每次暴力查找最小和次小的值然后合并,耗时1s+;后来发现可以使用系统自带的优先队列维护,耗时40ms+。

首先是暴力


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
[cce_cpp]
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int n;
int c;
long long a[20010],ans;

void swap(int m,int n)
{
    long long cc=a[m];
    a[m]=a[n];
    a[n]=cc;
}

void se(int x)
{
    int q=x;
    for (int i=q+1;i<=n;i++)
    {
        if (a[i]<a[q])
        {
            q=i;
        }
    }
    swap(q,x);
}


int main(void)
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+1+n);
    se(1);
    se(2);
    for (int i=2;i<=n;i++)
    {
        a[i]=a[i-1]+a[i];
        ans+=a[i];
        se(i);
        se(i+1);
    }
    printf("%lld\n",ans);
    return 0;
}
[/cce_cpp]

优先队列


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>  
#include<vector>
using namespace std;

int n;
int c;
long long a[20010];
long long ans;

int main(void)
{
    scanf("%d",&n);
    priority_queue<long long,vector<long long>,greater<long long> > que;
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        que.push(a[i]);
    }
    while (que.size()>1)
    {
        int m1=que.top();
        que.pop();
        int m2=que.top();
        que.pop();
        ans+=m1+m2;
        que.push(m1+m2);
    }

    printf("%lld\n",ans);
    return 0;
}

TD  为最小区间覆盖问题,用快速排序处理头尾时间,再用贪心for一遍便可得到正解,因为调程序时少删了一行导致W,感谢wmf同学指出错误。(真的很低级Σ( ° △ °|||))

下为code


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int n,t,ans,a[25010],b[25010];

void qsort(int l,int r)
{
    int i,j,mid,p;
    i=l;
    j=r;
    mid=a[(l+r)/2];
    do
    {
        while (a[i]<mid) i++;
        while (a[j]>mid) j--;
        if (i<=j)
        {
            p=a[i];
            a[i]=a[j];
            a[j]=p;
            p=b[i];
            b[i]=b[j];
            b[j]=p;
            i++;
            j--;
        }
    }while (i<=j);
    if (l<j) qsort(l,j);
    if (i<r) qsort(i,r);
}

int main(void)
{
    scanf("%d%d",&n,&t);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        if (a[i]>b[i])
        {
            int te=a[i];
            a[i]=b[i];
            b[i]=te;
        }
    }
    qsort(1,n);
    int maxx=0,now=1;
    while (maxx<t)
    {
        int minn=maxx+1;
        for (int i=now;i<=n;i++)
        {
            if (a[i]<=minn && b[i]>=minn)
            {
                maxx=max(maxx,b[i]);
            }
            else
            if (a[i]>minn)
            {
                now=i;
                break;
            }
        }
        if (minn>maxx)
        {
            break;
        }
        else
        {
            ans++;
        }
    }
    if (maxx<t)
    printf("-1\n");
    else
    {
        printf("%d\n",ans);
    }
    return 0;
}

 

贪心的题目属于比较容易理解的,但需要注意细节,并且要掌握各种技巧(堆,优先队列,字符串,二叉树......)

 

细节决定成败,代码改变人生。

2017/7/6        Y.W.