超级马拉松比赛赛道有 。每 的位置有一个水站。包括起点和终点一共有 个水站。
Taka 现在在 的位置。请输出离他最近的水站的位置。
#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
if (n % 5 < 5 - n % 5)
{
cout << n / 5 * 5 << "\n";
}
else
{
cout << (n / 5 + 1) * 5 << "\n";
}
return 0;
}
直线上从左到右按顺序有 个点 。从左到右、两个相邻的点之间距离分别为 。
输入两个大写英文字母 ，为两个点的编号（）。输出 两点间的距离。
#include <bits/stdc++.h>
using namespace std;
int d[] = {0, 3, 1, 4, 1, 5, 9};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
for (int i = 1; i <= 6; i++)
d[i] += d[i - 1];
char a, b;
cin >> a >> b;
if (a > b)
swap(a, b);
a = a - 'A', b = b - 'A';
cout << d[b] - d[a] << "\n";
return 0;
}
有一个 行 列的字符画。有一个边长至少为 的正方形区域都是 #，其他的位置都是 .
Snuke 选择了一个 #，并将其变成了 .，给你变化后的字符画。
输出 Snuke 选择的位置。
#include <bits/stdc++.h>
using namespace std;
int n, m;
char g[505][505];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
int l, r, u, d;
l = m + 1, r = 0, u = n + 1, d = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
cin >> g[i][j];
if (g[i][j] == '#')
l = min(l, j),
r = max(r, j),
u = min(u, i),
d = max(d, i);
}
for (int i = u; i <= d; i++)
for (int j = l; j <= r; j++)
if (g[i][j] == '.')
cout << i << " " << j << "\n";
return 0;
}
给定一个长度为 的序列 ，保证 且 是奇数。
这是一个睡眠的记录表。奇数位置的数为起床的时间，偶数位置的数为入睡的时间。
给 个问题，第 个问题为 。请输出 区间内一共睡了多长时间。
预处理 为第 时间点前一共睡了多久。
对于时间点 来说，可以二分找到它属于哪个小时间段 。
之前的睡觉总时间就是 或 。
#include <bits/stdc++.h>
using namespace std;
int n;
int a[212345];
int t[212345]; // a[i] 这个时间点之前一共睡了多久
int q, l, r;
int cal(int x)
{
// 最后一个小于等于 x 的位置
int pos = upper_bound(a + 1, a + n + 1, x) - a - 1;
if (pos % 2 == 0)
return t[pos] + x - a[pos];
return t[pos];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
t[1] = 0;
for (int i = 2; i <= n; i++)
{
if (i % 2 == 1)
t[i] = t[i - 1] + a[i] - a[i - 1];
else
t[i] = t[i - 1];
}
cin >> q;
while (q--)
{
cin >> l >> r;
cout << cal(r) - cal(l) << "\n";
}
return 0;
}
给定一个简单无向图，有 个点， 条边。
图上有 个守卫，第 个守卫在 点上，耐力值为 。
如果点 到某个守卫的距离小于等于那个守卫的耐力值，那么 就是被守护了的。
从小到大输出所有被守护的点的编号。
一个耐力值为 h 守卫发挥的作用，可以看作是把一步能的点，变成一个耐力值为 h-1 的守卫。如果那个点耐力值本来就大于等于了 h-1，那么这一步的作用就没发挥到。
显然优先做耐力值高的守卫最好，用优先队列广搜依次处理即可。时间复杂度
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
vector<int> e[212345];
priority_queue<pair<int, int>> q;
int h[212345];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
for (int i = 1; i <= k; i++)
{
int p;
cin >> p;
cin >> h[p];
h[p]++;
q.push(make_pair(h[p], p));
}
while (!q.empty())
{
auto now = q.top();
q.pop();
int u = now.second;
int hh = now.first;
if (hh < h[u])
continue;
hh -= 1;
for (int v : e[u])
{
if (h[v] < hh)
{
h[v] = hh;
q.push(make_pair(hh, v));
}
}
}
int cnt = 0;
for (int i = 1; i <= n; i++)
if (h[i] > 0)
cnt++;
cout << cnt << "\n";
for (int i = 1; i <= n; i++)
if (h[i] > 0)
cout << i << " ";
return 0;
}
交互题。
有一个简单无向连通图，包含 个点 条边。点的编号从 。
不给你图的边。
初始你在点 上，给你 和点 能连到的点。
每步操作可以从当前位置移动到相连的点上。你需要输出你要移动到哪个编号 ，交互器会给你 相连的点。
请在 步以内移动到点 。
按 dfs 生成树走就行，因为树上边数量为 ，整个 dfs 跑完每条边也就走两次，总共 步，肯定够了。
需要注意交互题不要忘了刷新缓冲区。cout << endl; 可以输出换行并把当前缓冲区输出。cout.flush() 可以把当前缓冲区输出。
#include <bits/stdc++.h>
using namespace std;
int n, m, temp;
bool flag;
int siz[212345];
vector<int> e[212345];
bool vis[212345];
void check(int u)
{
flag = (siz[u]==-1);
cin >> siz[u];
for (int i = 1; i <= siz[u]; i++)
{
cin >> temp;
if (flag)
e[u].push_back(temp);
}
}
void dfs(int u)
{
cout << u << endl;
if (u == n)
exit(0);
vis[u] = true;
check(u);
for (auto v : e[u])
{
if (!vis[v])
{
dfs(v);
cout << u << endl;
check(u);
}
}
}
int main()
{
cin >> n >> m;
memset(siz, -1, sizeof(siz));
check(1);
vis[1]=true;
for (auto v : e[1]){
dfs(v);
cout << 1 << endl;
check(1);
}
return 0;
}
给定一个集合 。 为一个由 a 或 b 构成的非空字符串，最多包含 个字符。
请找到有多少种方案可以构造一个长度为 的字符串 。使得 里面不包含任何一个子串为 中的字符串。
数量可能很多，输出其对 取余后的结果。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200;
const int MOD = 998244353;
struct matrix
{
int mat[N][N];
} ans, fna;
int trie[N][2];
int fail[N], tot;
bool flag[N];
char c['b' + 1];
int n, m;
string tempS;
void build_trie(string &str) // 构建trie树
{
int root = 0;
int len = str.length();
for (int i = 0; i < len; i++)
{
int id = c[str[i]];
if (trie[root][id] == 0)
{
trie[root][id] = ++tot;
}
root = trie[root][id];
}
flag[root] = 1;
}
void build_fail()
{
queue<int> q;
for (int i = 0; i < 2; i++)
{
if (trie[0][i] != 0)
q.push(trie[0][i]);
}
while (!q.empty())
{
int now = q.front();
q.pop();
if (flag[fail[now]]) // 如果当前结点的指向是不允许的，那么这个点也是不允许的
flag[now] = true;
for (int i = 0; i < 2; i++)
{
if (!trie[now][i])
{
trie[now][i] = trie[fail[now]][i];
continue;
}
fail[trie[now][i]] = trie[fail[now]][i];
q.push(trie[now][i]);
}
}
}
matrix mul(const matrix &x, const matrix &y)
{
matrix tmp;
for (int i = 0; i <= tot; i++)
for (int j = 0; j <= tot; j++)
tmp.mat[i][j] = 0;
for (int i = 0; i <= tot; i++)
for (int k = 0; k <= tot; k++)
for (int j = 0; j <= tot; j++)
{
tmp.mat[i][j] += x.mat[i][k] * y.mat[k][j];
tmp.mat[i][j] %= MOD;
}
return tmp;
}
matrix matrixpow(const matrix &x, int k)
{
matrix ret;
for (int i = 0; i <= tot; i++)
for (int j = 0; j <= tot; j++)
ret.mat[i][j] = 0;
for (int i = 0; i <= tot; i++)
ret.mat[i][i] = 1;
while (k)
{
if (k & 1)
ret = mul(ret, ans);
ans = mul(ans, ans);
k >>= 1;
}
return ret;
}
matrix build_mat() // 构建矩阵
{
matrix temp;
for (int i = 0; i <= tot; i++)
for (int j = 0; j <= tot; j++)
temp.mat[i][j] = 0;
for (int i = 0; i <= tot; i++)
{
if (flag[i])
continue;
for (int j = 0; j < 2; j++)
{
if (flag[trie[i][j]])
continue;
++temp.mat[i][trie[i][j]];
}
}
return temp;
}
void init()
{
memset(fail, 0, sizeof(fail));
memset(trie, 0, sizeof(trie));
tot = 0;
memset(flag, 0, sizeof(flag));
c['a'] = 0;
c['b'] = 1;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
init();
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> tempS;
build_trie(tempS);
}
build_fail();
ans = build_mat();
fna = matrixpow(ans, n);
int ans = 0;
for (int i = 0; i <= tot; i++)
{
ans += fna.mat[0][i];
ans %= MOD;
}
cout << ans << "\n";
}