题解 | 写给自己看的
小L的三角尺
https://ac.nowcoder.com/acm/contest/120566/A
代码：
#include<bits/stdc++.h>
#include<array>
#define int long long
using namespace std;
const int mod = 998244353;
int fpow(int a, int x)
{
int _res = a % mod, _ans = 1;
while (x)
{
if (x & 1)_ans = _ans * _res % mod;
_res = _res * _res % mod;
x >>= 1;
}
return _ans;
}
// mod必须是质数
int inv(int a)
{
return fpow(a, mod - 2);
}
//初始化，适用于数据范围<1e8的时候
//复杂度 O(N)
const int N = 1000005;
int fz[N], fm[N];
void init()
{
//初始化复杂度O(N)
fz[0] = fm[0] = 1;
for (int i = 1; i <= 1000000; i++)
{
fz[i] = fz[i - 1] * i % mod;
}
fm[1000000] = fpow(fz[1000000], mod - 2);
for (int i = 999999; i >= 1; i--)
{
fm[i] = fm[i + 1] * (i + 1) % mod;
}
}
int C(int n, int k)
{
//查询时间复杂度O(1)
if (k == 0)
{
return 1;
}
if (n < k) return 0;
return fz[n] * fm[k] % mod * fm[n - k] % mod;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1; cin >> T;
init();
while (T--)
{
int n, x, t; cin >> n >> x >> t;
//int sum = 0;
/*for(int n=1;n<=10;n++)
{
for (int x = 1; x <= n; x++)
{
for (int t = 0; t <= n - 1; t++)
{*/
//cout << n << ' ' << x << ' ' << t << endl;
//sum++;
int y = n - x;
if (t >= n)
{
cout << 0 << endl;
continue;
}
if (y == 0 && t == 0)
{
cout << 1 << endl;
continue;
}
if (n == x&&t!=0)
{
cout << 0 << endl;
continue;
}
if (t % 2 == 1)
{
cout << (C(x - 1, (t - 1) / 2) * C(y - 1, (t + 1) / 2 - 1) % mod) * 2 % mod << endl;
}
else
{
int x1 = C(x - 1, t / 2) * C(y - 1, t / 2 - 1) % mod;
int x2 = C(x - 1, (t - 2) / 2) * C(y - 1, t / 2) % mod;
cout << (x1 + x2) % mod << endl;
}
/*}
}
}*/
}
//cout << sum;
return 0;
}
题解：用优先队列bfs即可，蓝色墨水部分在被遍历到时比较转换时间与当前时间，将较大值存入优先队列即可，最后出队的时间就是完全染黑的时间
代码：
#include<bits/stdc++.h>
#include<array>
#define int long long
using namespace std;
const int mod = 998244353;
const int x[4] = { 1, 0, -1, 0 };
const int y[4] = { 0, 1, 0, -1 };
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1; //cin >> T;
while (T--)
{
int n, m, a, b;
cin >> n >> m >> a >> b;
vector<vector<int>> mp(n+5, vector<int>(m+5));
vector<vector<int>> blue(n+5, vector<int>(m+5));
priority_queue<array<int, 3>,vector<array<int, 3>>,greater<array<int, 3>>> que;
for (int i = 1; i <= a; i++)
{
int x1, y1; cin >> x1 >> y1;
mp[x1][y1] = 1;
que.push({ 0,x1,y1 });
}
for (int i = 1; i <= b; i++)
{
int x1, x2, t; cin >> x1 >> x2 >> t;
blue[x1][x2] = 1;
mp[x1][x2] = t;
}
int mx;
while (!que.empty())
{
array<int,3> q = que.top();
que.pop();
mx = q[0];
int x1 = q[1], y1 = q[2];
for (int i = 0; i < 4; i++)
{
if (mp[x1 + x[i]][y1 + y[i]] == 0)
{
if (x1 + x[i] > n || x1 + x[i]<1 || y1 + y[i]>m || y1 + y[i] < 1)continue;
mp[x1 + x[i]][y1 + y[i]] = q[0] + 1;
que.push({ q[0] + 1,x1 + x[i],y1 + y[i] });
}
else
{
if (blue[x1 + x[i]][y1 + y[i]] != 0)
{
blue[x1 + x[i]][y1 + y[i]] = 0;
mp[x1 + x[i]][y1 + y[i]] = max(mp[x1 + x[i]][y1 + y[i]], q[0] + 1);
que.push({ mp[x1 + x[i]][y1 + y[i]],x1 + x[i],y1 + y[i] });
}
}
}
}
// for (int i = 1; i <= n; i++)
// {
// for (int j = 1; j <= m; j++)
// {
// cout << mp[i][j] << ' ';
// }
// cout << endl;
// }
cout << mx;
}
return 0;
}