A - Happy New Year 2025
题意
给定正整数\(A,B\)，求\((A+B)^2\)
思路
模拟
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
void solve()
{
int a, b;
cin >> a >> b;
cout << (a + b) * (a + b) << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
B - 9x9 Sum
题意
有\(9×9\)的网格，\((i,j)\)的权是\(i×j\)。给定\(n\)，求所有网格中权不是\(n\)的数的和。
思路
模拟
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
int cnt[100];
void solve()
{
int n;
cin >> n;
if (n > 81)
{
cout << 2025 << endl;
return;
}
for (int i = 1; i <= 9; i++)
{
for (int j = 1; j <= 9; j++)
{
cnt[i * j]++;
}
}
cout << 2025 - cnt[n] * n << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
C - Snake Numbers
题意
定义"蛇数"为：一个不小于\(10\)的数，且这个数的十进制首位严格大于其他位的数。给定区间\([L,R]\)，求该区间内的"蛇数"个数
思路
将上下限转化为两个上限之差，即 \(ans([L,R])=ans([10,R])-ans([10,L-1])\)。
对于上限\(R\)，枚举\(x\)，当\(x\)的位数小于\(R\)的位数以及位数相等但\(x\)的首位\(<R\)的首位时，可以很容易地计算出答案；当位数相等且首位相等时，就枚举\(R\)的每一位，当能够判断\(R\)不是蛇数或枚举完时结束，注意后者需要多计\(1\)(\(R\)本身也是蛇数)。
注意：C++库中的\(pow\)在数据很大时会有精度问题(可能？反正我在这\(wa\)了一晚上)，所以需要自己实现\(pow\)
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
int _pow(int a, int b)
{
int res = 1;
while (b--)
{
res *= a;
}
return res;
}
int f(int x)
{
if (x < 10)
{
return 0;
}
string s = to_string(x);
int res = 0, len = s.length();
for (int i = 1; i <= 9; i++) // 最高位
{
for (int j = 2; j < len; j++) // 位数
{
res += _pow(i, j - 1);
}
}
for (int i = 1; i < s[0] - '0'; i++)
{
res += _pow(i, len - 1);
}
for (int i = 1; i < len; i++)
{
res += (min(s[i], s[0]) - '0') * _pow((s[0] - '0'), len - i - 1);
if (s[i] >= s[0]) // x不是蛇形数
{
return res;
}
}
return res + 1;
}
void solve()
{
int L, R;
cin >> L >> R;
cout << f(R) - f(L - 1) << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
D - Snaky Walk
题意
给定\(H\)行\(W\)列的网格，\(S\)代表起点，\(G\)代表终点，#代表障碍物，对每次移动进行限制：当前移动须不同于上次，即上次水平这次就要垂直。求起点到终点需要的最短步数，无解输出\(-1\)
思路
加上限制的经典\(BFS\)，对于每个点需要额外记录上一次移动的状态，两次\(BFS\)即可得出答案。也可以将\(vis\)数组开成三维就不用跑两遍了，时间复杂度差不多。
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e3 + 5;
struct node
{
int x, y, step;
bool d; // false代表上一步水平
};
char a[mxn][mxn];
int H, W, sx, sy, gx, gy, ans = LLONG_MAX;
int xdx[] = { 1,-1 };
int xdy[] = { 0,0 };
int ydx[] = { 0,0 };
int ydy[] = { 1,-1 };
void bfs(bool f)
{
queue<node> q;
vector<vector<bool>> vis(mxn, vector<bool>(mxn, false));
q.push({ sx,sy,0,f });
while (q.size())
{
int x = q.front().x, y = q.front().y, step = q.front().step;
bool d = q.front().d;
q.pop();
if (x == gx && y == gy)
{
ans = min(step, ans);
}
if (vis[x][y])
{
continue;
}
vis[x][y] = true;
for (int i = 0; i < 2; i++)
{
// 分水平、垂直两种走
int tx = x + (d ? ydx[i] : xdx[i]);
int ty = y + (d ? ydy[i] : xdy[i]);
if (tx < 0 || ty < 0 || tx >= H || ty >= W || a[tx][ty] == '#')
{
continue;
}
q.push({ tx,ty,step + 1,!d });
}
}
}
void solve()
{
cin >> H >> W;
for (int i = 0; i < H; i++)
{
for (int j = 0; j < W; j++)
{
cin >> a[i][j];
if (a[i][j] == 'S')
{
sx = i;
sy = j;
}
else if (a[i][j] == 'G')
{
gx = i;
gy = j;
}
}
}
bfs(false); // 先垂直
bfs(true); //先水平
cout << (ans == LLONG_MAX ? -1 : ans) << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
E - Digit Sum Divisible 2
题意
思路
代码
点击查看代码