暑假专题训练 dp 2023-7-26
L. Hamiltonian Wall
算法：dp
做法：由于要一笔将所有黑块都划出来。所以我们状态转移方程应尽可能从左上角或者右下角的黑方块转移过来。$$f[i,j] = f[i, j - 1] + 1 \ (wall[i,j - 1] = B, w[i, j] = B)$$ $$f[i][j] = f[i + 1][j - 1] + 2 \ (i == 1,wall[i + 1][j - 1] == B,wall[i + 1][j] == B)$$ $$f[i][j] = f[i - 1][j - 1] + 2 \ (i == 2,wall[i - 1][j - 1] == B,wall[i - 1][j] == B)$$
code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define fir first
#define sec second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const int N = 200010;
int m;
char wall[3][N];
int f[3][N];
void solve()
{
cin >> m;
int cnt = 0;
wall[1][0] = 'B', wall[2][0] = 'B';
for (int i = 1; i <= 2; i++)
for (int j = 0; j <= m; j++)
f[i][j] = 0;
for (int i = 1; i <= 2; i++)scanf("%s", wall[i] + 1);
for (int i = 1; i <= 2; i++)
for (int j = 1; j <= m; j++)
if (wall[i][j] == 'B')cnt++;
for (int j = 1; j <= m; j++)
{
for (int i = 1; i <= 2; i++)
{
if (wall[i][j] == 'B')
{
if (wall[i][j - 1] == 'B')f[i][j] = f[i][j - 1] + 1;
if (i == 1 && wall[i + 1][j - 1] == 'B' && wall[i + 1][j] == 'B')f[i][j] = f[i + 1][j - 1] + 2;
if (i == 2 && wall[i - 1][j - 1] == 'B' && wall[i - 1][j] == 'B')f[i][j] = f[i - 1][j - 1] + 2;
}
}
}
if (f[1][m] == cnt || f[2][m] == cnt)cout << "YES" << endl;
else cout << "NO" << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
K. Living Sequence
算法：数位dp+二分或者是构造（这里只写构造）
做法：考虑每一个数的一个数位如果出现4，那么就删去，这说明十进制的数少了一个数，变成了九进制。即九进制0、1、2、3、4、5、6、7、8可以变成0、1、2、3、5、6、7、8、9。题目中的k为十进制中去掉4的第几位数，那么就相当于每一个数位都是0、1、2、3、5、6、7、8、9这样的九进制。那么把k转化为九进制为dg，随后对dg的每一位进行判断，小于4就说明没有跳过4000...这样的数。大于等于4就说明有跳过4000...这样的数，那么这个数位要加1。
code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define fir first
#define sec second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const int N = 200010;
LL k;
void solve()
{
cin >> k;
vector<int> dg;
while (k)dg.push_back(k % 9), k /= 9;
reverse(dg.begin(), dg.end());
for (int i = 0; i < dg.size(); i++)
{
if (dg[i] < 4)cout << dg[i];
else cout << dg[i] + 1;
}
cout << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
A. Matching
算法：状态压缩dp
做法：
f[i][j]第一维表示男生与女生的匹配个数，第二维表示男女生的匹配关系。
注意i个男生和女生的各种关系的匹配的方案数是从i - 1个男生和女生的各种关系的匹配的方案数转移过来的。
由于最终我们要找的是每一个男生都要与一个女生成一对的方案数（每个男生或女生都只能出现在一对关系中）。
那么我们可以这样想，1 -- i有i个男生，那么必定要有i个女生，我们预处理出所有1的个数为i（ \(1 <= i <= n\) ）的且大小不超过(1 << n) - 1的数，这些数存入vector数组w[n + 1]中。 枚举到i的时候，我们从有i个1的数中遍历且设该数为p，如果这个第i个男生对第j（ \(0 <= j < n\) ）个女生有好感，即初始输入的数组中 \(a_{i,j - 1} = 1\)，那么我们再判断p右移j位是否也是1，是的话我们将这个1减去，得到的数必定1的数量比先前少1个，即i - 1。那么我们当前i个男生和i个女生的匹配关系的式子是f[i][p]。
那么我们就可以有f[i][p] = ((LL)f[i][p] + f[i - 1][q]) % mod， 且q = p - (1 << j)（减去一个1后的匹配关系），表示上一次i - 1个男生在与i - 1个女生按q的关系匹配的数量加到目前i个男生和i个女生的匹配关系为p的方案数中。
code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define fir first
#define sec second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const int N = 22, M = 1 << 21, mod = 1e9 + 7;
int n;
int g[N][N];
int f[N][M];
vector<int> w[23];
int count(int x)
{
int cnt = 0;
for (int j = 0; j < n; j++)
if ((x >> j) & 1)cnt++;
return cnt;
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 0; j < n; j++)
cin >> g[i][j];
for (int i = 0; i < (1 << n); i++)
{
int cnt = count(i);
w[cnt].push_back(i);
}
f[0][0] = 1;
for (int i = 1; i <= n; i++)
{
for (auto p : w[i])
{
for (int j = 0; j < n; j++)
{
if (g[i][j] && ((p >> j) & 1))
{
int q = p - (1 << j);
f[i][p] = ((LL)f[i][p] + f[i - 1][q]) % mod;
}
}
}
}
cout << f[n][(1 << n) - 1];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
E. ConstructOR
算法：构造
做法：我们先求出a | b的值，设为k。判断k的二进制的最小的一位1是否比d的二进制的最小的一位1还要小，若是则不存在x。之后我们对于k值的二进制数从小到大遍历，只要当前的数位为1且我们所求的x的对应数位为0的话我们就加上d在左移若干位后的结果。左移的结果一定要保证其二进制数的最小的一位1的对应数位与k的对应数位相同，这样x加上这个值才能把0变成1。
code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define fir first
#define sec second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
LL a, b, d, c;
void solve()
{
cin >> a >> b >> d;
a = a | b, c = d;
if ((a & (-a)) < (d & (-d)))
{
cout << -1 << endl;
return;
}
vector<int> w;
while (a)w.push_back(a % 2), a /= 2;
int p = 0;
while (c)
{
if (c & 1)break;
c /= 2, p++;
}
LL x = 0;
for (int i = 0; i < w.size(); i++)
{
if (w[i] == 1 && ((x >> i) & 1) == 0)
{
x += d << (i - p);
}
}
cout << x << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}