算法竞赛进阶指南(第一章-基本算法)做题记录

《算法竞赛进阶指南》第一章-基础算法

位运算⋙

89.a^b（快速幂）

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
//Chillstep
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=200000+7;

ll ksm(ll n,ll x,ll p)
{
    ll ans=1;
    ans=ans%p;
    while(x)
    {
        if(x&1) ans=ans*n%p;
        n=n*n%p;
        x>>=1;
    }
    return ans;
}
int main()
{
    ll a,b,p;
    cin>>a>>b>>p;
    cout<<ksm(a,b,p)<<endl;
    
    return 0;
}

90.64位整数乘法

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
//Chillstep
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=200000+7;

ll multi_big(ll a,ll b,ll p)
{
    ll ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%p;
        a=a*2%p;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll a,b,p;
    cin>>a>>b>>p;
    cout<<multi_big(a,b,p)<<endl;
    
    return 0;
}

递推与递归⋙

※91.最短Hamilton路径（位运算，状压DP）

题目链接：https://www.acwing.com/problem/content/93/

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
//Chillstep
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=10+7;
const double pi=cos(-1);

int dp[(1<<20)+2][20];//第一维是当前状态，第二维是达到当前状态时走到了哪一个点。
int mp[20+3][20+3];
int hamilton(int n)
{
    memset(dp,0x3f,sizeof dp);
    dp[1][0]=0;
    for(int i=1;i<(1<<n);i++)//枚举每一种状态
    {
        for(int j=0;j<n;j++)//选择该种状态下的一个位置
        {
            if((i>>j)&1)
            {
                for(int k=0;k<n;k++)
                {
                    if((i^(1<<j))>>k&1)
                    {
                        dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+mp[k][j]);
                    }
                }
            }
        }
    }
    return dp[(1<<n)-1][n-1];
}



int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>mp[i][j];
    cout<<hamilton(n)<<endl;
    return 0;
}

92. 递归实现指数型枚举（二进制枚举）

题目链接：https://www.acwing.com/problem/content/94/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0; i<=(1<<n)-1; i++)
    {
        for(int j=n; j>=1; j--)
        {
            if((i>>j-1)&1)
                printf("%d ",n-j+1);
        }
        printf("\n");
    }
    return 0;
}

93. 递归实现组合型枚举（递归枚举）

题目链接：https://www.acwing.com/problem/content/95/

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
//Chillstep
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=10+7;
const double pi=cos(-1);

vector<int> chosen;
int n,m;
void calc(int x)
{
    if(chosen.size()==m)
    {
        for(int i=0;i<chosen.size();i++)
        {
            printf("%d ",chosen[i]);
        }
        printf("\n");
        return;
    }
    if(x>n) return;
    chosen.push_back(x);
    calc(x+1);
    chosen.pop_back();
    calc(x+1);
}
int main()
{
    scanf("%d%d",&n,&m);
    calc(1);
    return 0;
}

※94. 递归实现排列型枚举（递归排列枚举）

题目链接：https://www.acwing.com/problem/content/96/

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
//Chillstep
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=10+7;
const double pi=cos(-1);


int order[20];
bool chosen[20];
int n;
void calc(int k)
{
    if(k==n+1)
    {
        for(int i=1; i<=n; i++)
        {
            printf("%d ",order[i]);
        }
        printf("\n");
        return;
    }
    for(int i=1; i<=n; i++)
    {
        if(chosen[i])
            continue;
        order[k]=i;
        chosen[i]=true;
        calc(k+1);
        chosen[i]=false;
        order[k]=0;
    }
}
int main()
{
    scanf("%d",&n);
    calc(1);
    return 0;
}

95. 费解的开关（思维+递推+二进制）

题目链接：https://www.acwing.com/problem/content/description/97/

递推，枚举第一层，下面只要是0就改变。

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
//Chillstep ^_^
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=500+7;
const double pi=cos(-1);

char mp[8][8];
int m[8][8];
int T;
void change(int x,int y)
{
    if(x+1<=5&&y>=1&&y<=5) m[x+1][y]=m[x+1][y]^1;
    if(x-1>=1&&y>=1&&y<=5) m[x-1][y]=m[x-1][y]^1;
    if(y-1>=1&&x>=1&&x<=5) m[x][y-1]=m[x][y-1]^1;
    if(y+1<=5&&x>=1&&x<=5) m[x][y+1]=m[x][y+1]^1;
    if(x>=1&&x<=5&&y>=1&&y<=5) m[x][y]=m[x][y]^1;
}
bool check()
{
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            if(m[i][j]!=1) return false;
    return true;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        for(int i=1;i<=5;i++) scanf("%s",mp[i]+1);
        int ans=INF;
        for(int i=0;i<(1<<5);i++)
        {
            int step=0;
            for(int j=1;j<=5;j++)
                for(int k=1;k<=5;k++)
                    m[j][k]=mp[j][k]-'0';
            for(int j=1;j<=5;j++)
                if(((i>>(j-1))&1)==0) {change(1,j);step++;}
            for(int j=2;j<=5;j++)
                for(int k=1;k<=5;k++)
                    if(!m[j-1][k]) {change(j,k);step++;}
            if(check()==true&&step<=6) ans=min(ans,step);
        }
        if(ans==INF) printf("-1\n");
        else printf("%d\n",ans);

    }
    return 0;
}

96. 奇怪的汉诺塔（DP+递推）

题目链接：https://www.acwing.com/problem/content/98/

这里的汉诺塔有四个桩子，但我们可以从三个桩子入手。

三个桩子递推很容易推出 式子$f[i]=2*f[i-1]+1$ 其中i为圆盘数

那么在考虑四个桩子的情况，我们不妨把四个桩子i个圆盘需要的操作次数设为dp[i]

考虑如何构造转移方程：

加入我们先转移$j$个 那么就还剩$n-i$个需要转移，这$n-i$个转移的时候有一个桩已经被开始的j个占据了，也就是说还剩下三个桩子，这时候用上面的$f[n-i]$就是三个桩子的情况下转移到另一处的耗费。

最后我们需要把转移的两个桩子合并在一起，需要$dp[j]$

转移方程为$dp[i]=min(dp[i],dp[j]+dp[j]+f[i-j])$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//Chillstep ^_^
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=500+7;
const double pi=cos(-1);

int f[25],dp[25];
int main()
{
    f[1]=1;
    for(int i=2; i<=12; i++)
        f[i]=2*f[i-1]+1;
    memset(dp,0x3f,sizeof dp);
    dp[0]=0;
    for(int i=1; i<=12; i++)
        for(int j=0; j<i; j++)
            dp[i]=min(dp[i],dp[j]+dp[j]+f[i-j]);
    for(int i=1;i<=12;i++) printf("%d\n",dp[i]);
    return 0;
}

97. 约数之和（矩阵快速幂+分治/逆元+特判）

题目链接：https://www.acwing.com/problem/content/99/

算贡献就好,可以分治也可以逆元来做，但是注意一点，由于模数为9901，所以费马小定理不能直接用，只有当$gcd(p,a)=1$时才可以用（把我恶心坏了，看了一个小时找不出来错误），所以要特判解决这个问题,当这个式子$gcd(p,a)=1$成立时单独拿出来加到ans中去，像下面这样。

1
2
3
4
5
6
7
if((p[i]-1)%MOD==0)
{
    for(int j=1;j<=cnt[i];j++)
    {
        ans=(ans+ksm(p[i],j,MOD))%MOD;
    }
}
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
//Chillstep ^_^
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5e7+7;
const int MOD=9901;
const double pi=cos(-1);
//复杂度log2(x)
ll ksm(int n,int x,int p)//n^x%p
{
    long long int ans=1;
    ans=ans%p;//如果模数p=1，没这步会直接输出ans=1，而正确答案应该是0
    while(x)
    {
        if(x&1) ans=ans*1ll*n%p;//1ll防止溢出
        n=n*1ll*n%p;
        x>>=1;
    }
    return ans;
}
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int p[MAXN],cnt[MAXN];
int main()
{
    int a,b;
    cin>>a>>b;
    int num=0;
    for(int i=2;i<=a;i++)
    {
        while(a%i==0)
        {
            if(p[num]!=i) num++;
            p[num]=i;
            cnt[num]++;
            a=a/i;
        }
    }
    for(int i=1;i<=num;i++) cnt[i]=cnt[i]*b;
    ll ans=1;
    for(int i=1;i<=num;i++)
    {
        if((p[i]-1)%MOD==0)
        {
            for(int j=1;j<=cnt[i];j++)
            {
                ans=(ans+ksm(p[i],j,MOD))%MOD;
            }
        }
        else
        {
            ll c1=ksm(p[i],cnt[i]+1,MOD);
            c1=c1+MOD;
            ans=ans*(c1-1)*ksm(p[i]-1,MOD-2,MOD)%MOD;
        }
    }
    if(a==0) printf("0");
    else if(b==0) printf("1");
    else printf("%lld",ans);
    return 0;
}

98. 分形之城（线性代数坐标变换+规律+递归+分形图）

题目链接：https://www.acwing.com/problem/content/100/

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
//Chillstep ^_^
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5e7+7;
const int MOD=9901;
const double pi=cos(-1);

pll cal(ll n,ll m)
{
    if(n==0) return {0,0};
    ll len=1ll<<n-1,cnt=1ll<<2*n-2;
    auto pos=cal(n-1,m%cnt);
    auto x=pos.first,y=pos.second;
    auto z=m/cnt;
    if(z==0) return {y,x};
    if(z==1) return {x,y+len};
    if(z==2) return {x+len,y+len};
    else return {2*len-1-y,len-1-x};
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        ll n,a,b;
        cin>>n>>a>>b;
        auto ac=cal(n,a-1);
        auto bc=cal(n,b-1);
        double x=ac.first-bc.first;
        double y=ac.second-bc.second;
        printf("%.0f\n",sqrt(x*x+y*y)*10);
    }
    return 0;
}

前缀和⋙

99.激光炸弹（二位前缀和+思维）

题目链接：https://www.acwing.com/problem/content/101/

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
//Chillstep ^_^
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5000+4;
const int MOD=9901;
const double pi=cos(-1);

int n,r;
int max_r,max_c;
int s[MAXN][MAXN];
int main()
{
    scanf("%d%d",&n,&r);
    max_r=max_c=r;//很重要！！
    for(int i=1;i<=n;i++)
    {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        x++;
        y++;
        s[x][y]=w;
        max_r=max(max_r,x);
        max_c=max(max_c,y);
    }
    for(int i=1;i<=max_r;i++)
    {
        for(int j=1;j<=max_c;j++)
        {
            s[i][j]=s[i-1][j]+s[i][j-1]+s[i][j]-s[i-1][j-1];
        }
    }
    int ans=0;
    for(int i=r;i<=max_r;i++)
    {
        for(int j=r;j<=max_c;j++)
        {
            ans=max(ans,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

差分⋙

100.增减序列

题目链接：https://www.acwing.com/problem/content/102/

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
//Chillstep ^_^
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=2e5+5;
const int MOD=1e9+7;
const double pi=cos(-1);

ll p=0,q=0;
int a[MAXN];
int d[MAXN];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=2;i<=n;i++)
    {
        d[i]=a[i]-a[i-1];
        if(d[i]>0) p+=d[i];
        if(d[i]<0) q+=(-d[i]);
    }
    printf("%lld\n%lld",min(p,q)+abs(p-q),abs(p-q)+1);
    return 0;
}

101. 最高的牛

题目链接：https://www.acwing.com/problem/content/103/

题目中保证了m组对中不会出现重复的，但如果不保证的话只需要把每一对存入$pair$即可 然后在q[x]!=y来去重

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
//Chillstep ^_^
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e4+5;
const int MOD=1e9+7;
const double pi=cos(-1);

pii a[MAXN];
int c[MAXN],d[MAXN];
map<ll,ll>q;
int main()
{
    int n,p,h,m;
    cin>>n>>p>>h>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x>y) swap(x,y);
        if(q[x]!=y)
        {
            q[x]=y;
            d[x+1]--,d[y]++;
        }
    }
    for(int i=1;i<=n;i++) c[i]=c[i-1]+d[i];
    for(int i=1;i<=n;i++) printf("%d\n",c[i]+h);
    return 0;
}

二分⋙