刷题计划
第一季我们来刷算法竞赛进阶指南好吧。
先说,题目太长了,我就只发链接了。
每期做四道水题
T1
这道题没啥好说的,当热身吧。
观察可得,就是简单的快速幂。
然后打一下板子就行了。
#include<bits/stdc++.h>
using namespace std;
int qmi(int a, int k, int p)
{
int res = 1;
while(k)
{
if(k & 1) res = (long long)res * a % p;
k >>= 1;
a = (long long ) a * a % p;
}
return res;
}
int main()
{
int a, k, p;
scanf("%d%d%d", &a, &k, &p);
printf("%d", qmi(a, k, p));
return 0;
}
哎,咋还wa了。
我们没有考虑$p = 1$和$k = 0$这种情况。
那就加一个特判就行了。
#include<bits/stdc++.h>
using namespace std;
int qmi(int a, int k, int p)
{
int res = 1;
if(p == 1) return 0;
if(k == 0) return 1;
if(a == 0) return 0;
while(k)
{
if(k & 1) res = (long long)res * a % p;
k >>= 1;
a = (long long ) a * a % p;
}
return res;
}
int main()
{
int a, k, p;
scanf("%d%d%d", &a, &k, &p);
printf("%d", qmi(a, k, p));
}
继续。
T2
这个就有点意思了。
是让你快速的求出这个整数的大乘法。
首先分析时间复杂度是$log$级别的。
这时候就应该想到用二进制了。
那怎么做呢?
我们可以像快速幂一样,把乘法也转化为加法,就像快速幂中幂转乘法一样。
也是同理,关于快速幂,见这个blog
那样的话啊,我们就可以按照二进制来枚举了,这样时间复杂度就快了很多很多。
代码如下:
#include<iostream>
using namespace std;
#define ll long long
const int N = 100010;
ll a, k, p, res = 0;
int main()
{
cin >>a >> k >> p;
while(k)
{
if(k & 1) res = (ll)(res + a ) % p;
k = k>>1;
a = (ll)(a * 2) % p;
}
cout << res;
}
T3
先说这题的算法:状压dp。
关于dp,这里不细讲了。
留到cht讲算法系列的第5章说吧。
简单介绍一下,其实dp就是递推递归的进阶。
关于递推递归,可以看我以前的这个blog
先考虑最暴力的做法:爆搜。
怎么个搜法呢?
那我们可以考虑一下,这个dfs的参数。
首先,走的长度,然后,走到的点。
最重要的是,你**得把怎么走存下来啊!存个二维数组是要存死人吗?
这就好比明知自己熬不到凌晨两点却非要熬夜更博,后果就是爆栈+TLE+MLE+SF+RE。
然后我们可以用什么来搞呢?
首先注意,我们只用存0和1两种状态就行了。
然后我们就想到可以压缩对吧,就是把这个所有的0和1都放在一起,然后写成一个二进制数,这样的话就实现了减少空间和降低运算时间复杂度的双重效果。
所以的话,我们就可以大大的减少dp所需要的时间复杂度(状态数量)了。
那我们维护两维:
1.到了哪个点
2.走过哪些点(压缩成state)
然后的话我们就可以用已经更新过的点更新没有更新过的点了。
代码如下:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int N = 20, M = 1 << N;
int n;
int w[N][N];
int f[M][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 = 0; 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][j], f[i - (1 << j)][k] + w[k][j]);//那就更新
cout << f[(1 << n) -1][n - 1];
return 0;
}
关于位运算,可以看这篇我以前的blog
T4
最后来一道状态压缩dp。
这道题的思路是什么啊
就是一个全新的思想:
f[i][j] 表示考虑到第i列,上一列伸出来的小方格的状态是j的情况。
为啥可以这么列呢?
首先,我们一旦摆出来一种方案使得横向的满足情况,竖向也就只有一种方法了。
这么说的话,问题就转化成了如何让横向的满足情况,自然就可以用上面的dp来解决了。
咋考虑呢?
需要考虑如下几个问题:
- 如何表示j
- 需要满足什么?
- 怎么转移
j的表示可以用二进制来搞。如果是0表示没有伸出,否则就表示伸出了。
那么要满足什么呢?
i列和i-1列同一行不同时伸出,不然不行。
本列伸出的状态j和上列伸出的状态k求或,得到上列是否为奇数空行状态,奇数空行不转移。要不然没办法对吧。
最后的坑:f[0][0] = 1!!!!
最后贴上本题的代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 12, M = 1 << N;
int n, m;
long long int f[N][M];
bool st[M];
int main()
{
while(cin >> n >> m, n || m)
{
for(int i = 0; i < 1 << n; i ++)
{
int cnt = 0;
st[i] = true;
for(int j = 0; j < n; j ++)
{
if(i >> j & 1)
{
if(cnt & 1) st[i] = false;
cnt = 0;
}
else cnt ++;
}
if(cnt & 1) st[i] = false;
}
memset(f, 0, sizeof f);
f[0][0] = 1;
for(int i = 1; i <= m; i ++)
for(int j = 0; j < 1 << n; j ++)
for(int k = 0; k < 1 << n; k ++)
if((j & k) == 0 && st[j | k])
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
}
快速冥:
扔下我的代码(因为我的代码不值得奉上
stccccccccccccccccccco
CCCCCCCCCCCCCCCCCCCCCCCCCCCCrz
伪运算是哈
伪是虚伪的意思,表面上是指“虚伪虚假”的运算,但实际上其实是指位运算妙处很多,可以解决很多问题
突然意识到你打错标题了 是位运算……
我故意的,伪是虚伪的意思,表面上是指“虚伪虚假”的运算,但实际上其实是指位运算妙处很多,可以解决很多问题
Orz 语文大师
。。
话说我(当时)做哈密尔顿路那题的时候并不觉得它是DP(
哈哈哈哈
T1好难啊(手动滑稽)
HH