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

【纪中】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+

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.

 

 

[POJ 1379] [CEOI 1999] 逃离陷阱

模拟退火。

概念见大白话解析模拟退火算法

实现:

首先随机在平面中取一个点 A,每轮都以这个点为圆心,R 为半径(每轮递减)随机选取若干个圆上的点 B。若点 B 已经优于 A,则直接用 B 更新 A,否则以一个概率 P(每轮递减)决定是否以 B 更新 A。这样就可以得到一个近似最优解。

在实现过程中,可以同时维护 20 个点,最后取这些点中的最优值作为答案。具体 R 与 P 的初始值与更新方式见代码。

代码如下:

继续阅读[POJ 1379] [CEOI 1999] 逃离陷阱

【BZOJ3624】免费道路

这题大意是有n个点, 给你m条边,其中有一些是水泥路,另一些是鹅卵石路。让你取n-1条边,其中要有k条鹅卵石路,使它成为一棵生成树。

因为有两种路,所以肯定要有几条边是一定要取得,那就先将所有水泥路连边,接着再做生成树,则需要加的边肯定是在答案中的。

这时再判断必定要取的鹅卵石路是否大于k,若大于k则无答案。接着只要将剩下的点做生成树即可