D. 矩阵
题意
有\(n\times m\)大小的矩阵，每个元素可能是字符'0'或'1'，从起点(1,1)开始，可以上下左右移动，如果移动前后位置的字符不同，则花费一个单位时间，否则，需要花费一个单位时间把移动后位置的字符更改，再花费一个单位时间移动。求走到(n,m)最少需要多少单位时间。
思路
用Dijkstra算法求最短路，图分为两层，一层元素全是'0'，一层元素全是'1'。每次移动就是从一层图调到另一层图，如果移动前后位置的元素不同，则权值为1，否则权值为2。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
const int N = 1005;
struct node {
int x, y, k, dis;
bool operator <(const node &a) const {return dis > a.dis;}
};
array<array<array<int, 2>, N>, N> dis;
array<array<array<bool, 2>, N>, N> vis;
array<int, 4> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
priority_queue<node> q;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> s(n + 1);
for(int i = 1; i <= n; i++) {
cin >> s[i];
s[i] = " " + s[i];
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
dis[i][j][1] = dis[i][j][0] = inf;
}
}
dis[1][1][s[1][1]-'0'] = 0;
q.push({1, 1, s[1][1] - '0'});
while(!q.empty()) {
int x = q.top().x,
y = q.top().y,
k = q.top().k;
q.pop();
if(vis[x][y][k]) continue;
vis[x][y][k] = true;
for(int i = 0; i < 4; i++) {
int tx = x + dx[i],
ty = y + dy[i];
if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
if(dis[tx][ty][k^1] > dis[x][y][k] + 1 + (s[tx][ty] - '0' == k)) {
dis[tx][ty][k^1] = dis[x][y][k] + 1 + (s[tx][ty] - '0' == k);
q.push({tx, ty, k ^ 1, dis[tx][ty][k^1]});
}
}
}
cout << min(dis[n][m][0], dis[n][m][1]) << "\n";
return 0;
}
E. 数数
题意
如果长为\(n\)一个数组\(a\)满足以下条件，则其称美好数组。
1. 对于\(1\le i\le n\)，满足\(1\le a_i\le m\)。
2. 对于\(1\le i\le n\)，满足\(\sum_{j=1}^i a_i\)是\(i\)的倍数。
思路
设\(dp[i][j]\)为前\(i\)个数，和为\(i\times j\)的状态，则有\(i\times j_1-(i-1)\times j_2\le m\)，\(j_2\)从大到小枚举，直到不满足该不等式。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int N = 2005;
array<array<int, N>, N> dp;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
dp[0][1] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int f = (i == 1) ? 1 : i * j / (i - 1);
f = min(f, m);
if(f * (i - 1) == i * j) {
f -= 1;
}
while(f > 0 && i * j - (i - 1) * f <= m) {
dp[i][j] = (dp[i][j] + dp[i-1][f]) % mod;
f--;
}
}
}
ll ans = 0;
for(int i = 1; i <= m; i++) {
ans = (ans + dp[n][i]) % mod;
}
cout << ans << "\n";
return 0;
}