Fork me on GitHub
image frame

My Blog

96. 奇怪的汉诺塔 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int d[15],f[15];
int main()
{
    d[1]=1;
    for(int i=2;i<=12;i++)
        d[i]=d[i-1]*2+1;
    memset(f,0x3f,sizeof(f));
    f[1]=1;
    for(int i=2;i<=12;i++)
    {
        for(int j=1;j<i;j++)
        {
            f[i]=min(f[i],f[j]*2+d[i-j]);
        }
    }
    for (int i = 1; i <= 12; i ++ )
        cout << f[i]<<endl;
    return 0;
}

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
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
83
84
85
86
87
88
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char g[10][10];
int n,t;
int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};
void turn(int x,int y)
{
    for(int i=0;i<5;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx>=0&&xx<5&&yy>=0&&yy<5)
            g[xx][yy]^=1;
    }
}
void print()
{
    for(int i=0;i<5;i++)
        cout << g[i]<<endl;
}
int work()
{
    int ans=0x3f3f3f3f;
    for(int k=0;k<(1<<5);k++)
    {
        char buf[10][10];
        memcpy(buf,g,sizeof(g));
        int res=0;
        for(int i=0;i<5;i++)
        {
            if((k>>i)&1)
            {
                res++;
                turn(0,i);
                // print();
                // cout<<endl;
            }
        }
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<5;j++)
            {
                if(g[i][j]=='0')
                {
                    res++;
                    turn(i+1,j);
                    // print();
                    // cout<<endl;
                }
            }
        }
        bool ok=1;
        for(int i=0;i<5;i++)
        {
            if(g[4][i]=='0')
            {
                ok=0;
                break;
            }
        }
        //cout<<res<<" 01 "<<ok<<endl;
        //print();
        if(ok)
            ans=min(ans,res);
        memcpy(g,buf,sizeof(g));
    }
    //cout << ans<<" "<<res<<endl;
    if(ans>6)
        return -1;
    else
        return ans;
}
int main()
{
    cin >> t;
    while(t--)
    {
        for(int i=0;i<5;i++)
            cin>>g[i];
        // print();
        // cout<<endl;
        cout << work()<<endl;
    }
    return 0;
}

94. 递归实现排列型枚举 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int n,a[10];
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
        a[i]=i;
    do
    {
        for(int i=1;i<=n;i++)
            printf("%d ",a[i]);
        printf("\n");
    }while(next_permutation(a+1,a+1+n));
    return 0;
}

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int ans[50],vis[50];
int n,m;
void dfs(int u,int cnt)
{
    ans[cnt]=u;
    vis[u]=1;
    if(cnt==m)
    {
        for(int i=1;i<=m;i++)
            printf("%d ",ans[i]);
        printf("\n");
        vis[u]=0;
        return ;
    }
    for(int i=u+1;i<=n;i++)
    {
        if(!vis[i])
            dfs(i,cnt+1);
    }
    vis[u]=0;
}
int main()
{
    cin >> n>>m;
    for (int i = 1; i <= n; i ++ )
        dfs(i,1);
    return 0;
}

92. 递归实现指数型枚举 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int n;
int a[16],vis[16];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        a[i]=i+1;
    int state;
    cout<<endl;
    for(state=1;state<(1<<n);state++)
    {
        for (int j = 0; j <n; j ++ )
        {
            if((state>>j)&1)
                printf("%d ",a[j]);
        }
        cout << endl;
    }
    return 0;
}

91. 最短Hamilton路径 

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int w[N][N];
int f[1<<N][N],n;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < n; j ++ )
        {
            cin>>w[i][j];
        }
    }
    memset(f,0x3f,sizeof(f));
    f[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)
                    {
                        f[i][j]=min(f[i-(1<<j)][k]+w[k][j],f[i][j]);
                    }
                }
            }
        }
    }
    cout<<f[(1<<n)-1][n-1]<<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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a,b,p;
ll qmul(ll a,ll b,ll p)
{
    ll res=0;
    while(b)
    {
        if(b&1)
            res=(res+a)%p;
        a=(a*2)%p;
        b>>=1;
    }
    return res;
}
int main()
{
    cin >> a>>b>>p;
    cout<<qmul(a,b,p)<<endl;
    return 0;
}

AcWing 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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a,b,p;
ll qpow(ll a,ll b,ll p)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=(res*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return res%p;
}
int main()
{
    cin>>a>>b>>p;
    cout<<qpow(a,b,p)<<endl;
    return 0;
}

旧作补档

前言

快考蓝桥杯了，发现自己dp不会，补了几题。
写一篇题解攒攒人品以防爆零

题目描述

小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。
第一行有 2 个用空格隔开的整数 m 和 n，表示学生矩阵有 m 行 n 列。
接下来的 m 行是一个 m×n 的矩阵，矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度，每行的 n 个整数之间用空格隔开。

样例

1
2
3
4
3 3
0 3 9
2 8 5
5 7 0

算法1

(dp) $O(n^2 m^2)$

C++ 代码

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
//来回传纸条和从起点传两次到终点是等价的，建模成从起点传两次到终点更好写
//dp[i][j][k][l]表示第一次传到(i,j)、第二次传到(k,l)时好心程度的最大值
//显然第一次传到(i,j)的最大值可以从(i-1,j)、(i,j-1)的最大值得来
//第二次传到(k,l)的最大值可以从(k-1,j)、(k,j-1)的最大值得来
//所以dp[i][j][k][l]的值是max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])+a[i][j]+a[k][l];(两种转移方式的组合的最大值再加上两个格子上的值)
//需要注意的是i==k&&j==l时，此时两个纸条到了同一格子上，但是每个格子上的好心值只能计算一次，所以要减去重复的
//最后结果根据dp的定义是dp[n][m][n][m]
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 51;
int dp[N][N][N][N],a[N][N],m,n;
int main()
{
    cin >> n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cin >> a[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for (int j = 1; j <=m; j ++ )
        {
            for(int k=1;k<=n;k++)
            {
                for(int l=1;l<=m;l++)
                {
                    dp[i][j][k][l]=max(dp[i-1][j][k-1][l],max(dp[i-1][j][k][l-1],max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])))+a[i][j]+a[k][l];
                    if(i==k&&j==l)
                        dp[i][j][k][l]-=(a[i][j]+a[k][l]);
                }
            }
        }
    }
    cout << dp[n][m][n][m]<<endl;
    return 0;
}

Markdown笔记2

段落

一个 Markdown 段落是由一个或多个连续的文本行组成，它的前后要有一个以上的空行（空行的定义是显示上看起来像是空的，便会被视为空行。
Markdown 段落没有特殊的格式，直接编写文字就好，段落的换行是使用两个以上空格加上回车。

段落换行示例

1
2
3
4
5
6
7
这是第一段的第一行  

这是第一段的第二行  

这是第二段的第一行  

这是第二段的第二行

最终效果如下：

这是第一段的第一行
这是第一段的第二行

这是第二段的第一行
这是第二段的第二行

字体

可以使用以下字体

字体示例

1
2
3
4
5
6
*斜体文本*
_斜体文本_
**粗体文本**
__粗体文本__
***粗斜体文本***
___粗斜体文本___

效果如下：
斜体文本
_斜体文本_
粗体文本
粗体文本
粗斜体文本
_粗斜体文本_

注意事项

Markdown 应用程序在如何处理单词或短语中间的下划线上并不一致。为兼容考虑，在单词或短语中间部分加粗的话，请使用星号（asterisks）。
Markdown 应用程序在处理单词或短语中间添加的下划线上并不一致。为了实现兼容性，请使用星号将单词或短语的中间部分加粗并以斜体显示，以示重要。
要同时用粗体和斜体突出显示文本，请在单词或短语的前后各添加三个星号或下划线。要加粗并用斜体显示单词或短语的中间部分，请在要突出显示的部分前后各添加三个星号，中间不要带空格。

例如：

1
2
3
Love**is**bold √    Love__is__bold ×  
A*cat*meow √    A_cat_meow ×
This is really***very***important text. √    This is really___very___important text. ×

实际效果
Loveisbold √ Loveisbold ×
Acatmeow √ A_cat_meow ×
This is reallyveryimportant text. √ This is really_very_important text. ×

  • Copyrights © 2022-2026 CPY
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信