A - Happy New Year 2025
按题意输出即可。
点击查看代码
void solve() {
int a, b;
std::cin >> a >> b;
std::cout << (a + b) * (a + b) << "\n";
}
B - 9x9 Sum
直接遍历累加满足不等于x的数即可，注意这个九九乘法表是9*9的矩阵，不是我们学的下三角。
点击查看代码
void solve() {
int x;
std::cin >> x;
int ans = 0;
for (int i = 1; i <= 9; ++ i) {
for (int j = 1; j <= 9; ++ j) {
if (i * j != x) {
ans += i * j;
}
}
}
std::cout << ans << "\n";
}
C - Snake Numbers
题意：求[l, r]之间满足最高位严格大于其他位的数。
没想到c就上了数位dp。。。
但还是挺基础的，f[i][j]表示填到第i位且最大值为j的数字数量，最开始我们让最大值为10，一直等到填到一个不为0的数更新最大值，其他都是数位dp的基操。
点击查看代码
void solve() {
i64 l, r;
std::cin >> l >> r;
std::vector<int> a;
std::vector f(20, std::vector<i64>(11, -1));
auto dp = [&](auto self, int u, int max, bool limit) -> i64 {
if (u < 0) {
return 1;
}
if (u == 0 && max == 10) {
return 0;
}
if (f[u][max] != -1 && !limit) {
return f[u][max];
}
int up = limit ? a[u] : 9;
up = std::min(max - 1, up);
i64 ans = 0;
for (int i = 0; i <= up; ++ i) {
int nmax = max;
if (max == 10 && i != 0) {
nmax = i;
}
ans += self(self, u - 1, nmax, limit && i == a[u]);
}
if (!limit) {
f[u][max] = ans;
}
return ans;
};
auto work = [&](i64 x) -> i64 {
if (x < 10) {
return 0;
}
a.clear();
while (x) {
a.push_back(x % 10);
x /= 10;
}
return dp(dp, a.size() - 1, 10, true);
};
std::cout << work(r) - work(l - 1) << "\n";
}
D - Snaky Walk
（这题不是比c简单很多？）
题意：给你一个矩阵，有起点终点，不能走障碍物，并且要上下和左右交替走，也就是每次都要拐正好90度的弯，求最短距离。
比较简单的bfs，加一维记上次走的方向就可以了。
点击查看代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::string> s(n);
for (int i = 0; i < n; ++ i) {
std::cin >> s[i];
}
std::pair<int, int> S, G;
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < m; ++ j) {
if (s[i][j] == 'S') {
S = {i, j};
} else if (s[i][j] == 'G') {
G = {i, j};
}
}
}
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
std::queue<std::array<int, 3> > q;
const int inf = 1e9;
std::vector dist(n, std::vector(m, std::array<int, 4>{inf, inf, inf, inf}));
for (int i = 0; i < 4; ++ i) {
q.push({S.first, S.second, i});
dist[S.first][S.second][i] = 0;
}
while (q.size()) {
auto [x, y, d] = q.front(); q.pop();
for (int i = 0; i < 4; ++ i) {
if (i + d & 1) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || s[nx][ny] == '#') {
continue;
}
if (dist[nx][ny][i] <= dist[x][y][d] + 1) {
continue;
}
dist[nx][ny][i] = dist[x][y][d] + 1;
q.push({nx, ny, i});
}
}
}
int ans = inf;
for (int i = 0; i < 4; ++ i) {
ans = std::min(ans, dist[G.first][G.second][i]);
}
if (ans == inf) {
ans = -1;
}
std::cout << ans << "\n";
}
E - Digit Sum Divisible 2
不会这种
待补
F - Count Arrays
有n个数，第i个数要小于等于第ai个数，每个数的值域为[1, m]，求可以构造的数组方案数。
我们把ai向i连边，最后会是一个森林，可能会有一颗基环树，对每颗树求出来方案数然后相乘即可。对于基环树进行缩环后当一般树处理，因为环上的元素值肯定一样。
那么怎么求一颗树的方案数呢？直接树形dp。f[i][j]为i值为j时的方案树，g[i][j]为i取值1~j的方案数，那么f[u][i] = g[v][i], v是u的儿子。
点击查看代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int> > adj(n);
std::vector<int> in(n);
for (int i = 0; i < n; ++ i) {
int x;
std::cin >> x;
-- x;
if (x != i) {
adj[x].push_back(i);
++ in[i];
}
}
std::vector<int> st(n), st1(n), in_cycle(n);
std::vector<int> a;
int U, V;
auto get_cycle = [&](auto self, int u) -> bool {
if (u == V) {
a.push_back(u);
return in_cycle[u] = 1;
}
for (auto & v : adj[u]) {
if (self(self, v)) {
a.push_back(u);
return in_cycle[u] = 1;
}
}
return false;
};
auto cycle = [&](auto self, int u) -> bool {
st[u] = 1;
for (auto & v : adj[u]) {
if (st[v]) {
U = v, V = u;
return true;
}
if (self(self, v)) {
return true;
}
}
st[u] = 0;
return false;
};
std::vector f(n, std::vector<Z>(m + 1, 1)), g(n, std::vector<Z>(m + 1));
auto dfs = [&](auto self, int u) -> void {
st[u] = 1;
for (auto & v : adj[u]) {
if (in_cycle[v]) {
continue;
}
self(self, v);
for (int i = 1; i <= m; ++ i) {
f[u][i] *= g[v][i];
}
}
for (int i = 1; i <= m; ++ i) {
g[u][i] = g[u][i - 1] + f[u][i];
}
};
Z ans = 1;
for (int i = 0; i < n; ++ i) {
if (in[i] == 0) {
dfs(dfs, i);
ans *= g[i][m];
} else if (!in_cycle[i] && !st[i] && cycle(cycle, i)) {
a.clear();
// std::cout << i + 1 << "--" << U + 1 << "-" << V + 1 << ": ";
get_cycle(get_cycle, U);
for (auto & x : a) {
// std::cout << x + 1 << " ";
if (x == U) {
continue;
}
for (auto & y : adj[x]) {
if (!in_cycle[y]) {
adj[U].push_back(y);
}
}
}
dfs(dfs, U);
ans *= g[U][m];
}
}
std::cout << ans << "\n";
}
G - Prime Circuit
待补
标签：std,AtCoder,return,int,auto,self,VP,vector,387 From： https://www.cnblogs.com/maburb/p/18662981