Fork me on GitHub
image frame

My Blog

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. ×

Markdown笔记1

标题

Markdown 支持两种标题的语法，类 Setext 和类 atx 形式。
类 Setext形式使用 = 和 - 标记一级和二级标题；类 Atx 形式则是在行首插入 1 到 6 个 # ，对应到标题 1 到 6 阶。

类 Setext形式示例

1
2
3
4
5
一级标题
=================

二级标题
-----------------

效果如下所示：

一级标题

二级标题

类 Atx 形式示例

1
2
3
4
5
6
# h1
## h2
### h3
#### h4
##### h5
###### h6

效果如下所示：

h1

h2

h3

h4

h5
h6

小技巧

VSCode 可以用Ctrl+Shift+V快捷键来对md文件进行预览
不同的 Markdown 应用程序处理 # 和标题之间的空格方式并不一致。为了兼容考虑，请用一个空格在 # 和标题之间进行分隔。

参考资料与文献

1、https://www.w3cschool.cn/markdownyfsm/ysu1e1.html

2、https://www.runoob.com/markdown/md-paragraph.html

3、https://markdown.com.cn/cheat-sheet.html

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

请我喝杯咖啡吧~

支付宝
微信