输入两个长度为 的字符串 ，检测他们是不是相似的。如果对于所有的 都有 与 相似，那么我们就说这两个字符串相似。
两个字符相似的条件为：
1 另一个字符为 l0 另一个字符为 o#include <bits/stdc++.h>
using namespace std;
int n;
string s, t;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> s >> t;
for (int i = 0; i < n; i++)
{
if (s[i] == t[i])
continue;
if (s[i] == '1' && t[i] == 'l' || s[i] == 'l' && t[i] == '1')
continue;
if (s[i] == '0' && t[i] == 'o' || s[i] == 'o' && t[i] == '0')
continue;
cout << "No\n";
return 0;
}
cout << "Yes\n";
return 0;
}
有 个人拍了 张照片。每张照片里都是一些人从左到右排成一排。
如果两个人没有在任意一张照片中相邻，这两个人就会不开心。
问有多少对人会因为这个不开心。
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[55][55];
bool e[55][55];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> m >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
e[a[i][j]][a[i][j - 1]] = true;
e[a[i][j - 1]][a[i][j]] = true;
}
int cnt = 0;
for (int i = 1; i <= m; i++)
for (int j = i + 1; j <= m; j++)
{
if (!e[i][j])
cnt++;
}
cout << cnt << "\n";
return 0;
}
在一个平面直角坐标系上有一个人，初始在 位置上，初始生命值为 。有 瓶生命药水，第 瓶在 。
给出这个人的 步的行动规划。每次行动用一个字符描述，R,L,U,D 分别表示向“右、左、上、下”移动。
每次移动回消耗一点生命值。如果移动到了一个有生命药水的位置，并且这个人的生命值目前严格小于 ，那么他就会使用这瓶药水，并把生命值恢复到 。
问这 步行动能不能完整走完（整个过程中没有出现过生命值小于 的情况）。
显然问题的难点只有怎么判断当前位置还有没有药水。
根据数据范围，只需要达到 的效率查询和修改即可。
我直接使用了 set<pair<int,int>> 来存所有有药水的位置。
显然也可以用 vector<int> x[412345]; 来保存每个 x 坐标有哪些 y 坐标有药水，排序后二分查找就能达到需求的时间复杂度。考虑到需要消耗药水，可以再配一个 vector<bool> xx[412345]; 保存那个药水还在不在。
或者用 set<int> x[412345];，这样移除药水就可以直接 地 earse 了。
#include <bits/stdc++.h>
using namespace std;
int n, m, h, k;
string s;
set<pair<int, int>> se;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> h >> k;
cin >> s;
// cout << s << endl;
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
se.insert(make_pair(x, y));
}
pair<int, int> now;
now.first = now.second = 0;
for (char c : s)
{
if (c == 'R')
{
now.first += 1;
}
if (c == 'L')
{
now.first -= 1;
}
if (c == 'U')
{
now.second += 1;
}
if (c == 'D')
{
now.second -= 1;
}
h -= 1;
if (h < 0)
{
cout << "No\n";
return 0;
}
if (h < k)
{
auto it = se.find(now);
if (it != se.end())
{
h = k;
se.erase(it);
}
}
}
cout << "Yes\n";
return 0;
}
对于一个只有 a、Shift、Caps Lock 三个按键的键盘来说。
a 的耗时是 shift + a 的耗时是 Caps Lock 的耗时是 初始时大写锁定没有开启。现在给出一个只包含大小写英文字符的字符串 ，问最少需要多少时间能敲完 。
一眼 DP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int x, y, z;
string s;
// f[i][j] 打完第i个字符后的最小花费、打完后大写锁定的灯是j状态
int f[312345][2];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> x >> y >> z;
cin >> s;
f[0][0] = 0;
f[0][1] = z;
for (int i = 1; i <= s.length(); i++)
{
if (s[i - 1] == 'A')
{
f[i][0] = min(min(f[i - 1][1] + x + z, f[i - 1][1] + z + y),
min(f[i - 1][0] + y, f[i - 1][0] + z + x + z));
f[i][1] = min(min(f[i - 1][1] + x, f[i - 1][1] + z + y + z),
min(f[i - 1][0] + y + z, f[i - 1][0] + z + x));
}
else if (s[i - 1] == 'a')
{
f[i][0] = min(min(f[i - 1][1] + y + z, f[i - 1][1] + z + x),
min(f[i - 1][0] + x, f[i - 1][0] + z + y + z));
f[i][1] = min(min(f[i - 1][1] + y, f[i - 1][1] + z + x + z),
min(f[i - 1][0] + x + z, f[i - 1][0] + z + y));
}
}
cout << min(f[s.length()][0], f[s.length()][1]) << "\n";
return 0;
}
定义一个 级别星星图为：
初始 Taka 有很多个星星图，他循环执行下面的步骤，直到把这些星星图连城了一个树：
现在给你最终的树，求初始的星星图都是什么级别的。
题目保证只有唯一解。
显然最终树的所有叶子节点连接到的点都是星星图的中心。类似于拓扑排序，把所有确定了中心的星星删去，即可还原出每颗行星。
#include <bits/stdc++.h>
using namespace std;
int n;
set<int> e[212345];
queue<int> qD; // 存度为1的星星图边缘
queue<int> qC; // 存待处理的星星图中心
int ans[212345];
bool vis[212345];
vector<int> levels;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n - 1; i++)
{
int u, v;
cin >> u >> v;
e[u].insert(v);
e[v].insert(u);
}
for (int i = 1; i <= n; i++)
if (e[i].size() == 1)
{
vis[i] = true;
qD.push(i);
}
while (!qD.empty())
{
// 找到星星图中心
int len = qD.size();
for (int i = 0; i < len; i++)
{
int now = qD.front();
qD.pop();
int nxt = *(e[now].begin());
if (vis[nxt])
continue;
vis[nxt] = true;
qC.push(nxt);
}
// 处理星星图
while (!qC.empty())
{
// u~~v~~vv
int u = qC.front();
qC.pop();
ans[u] = e[u].size();
for (auto v : e[u])
{
for (auto vv : e[v])
{
if (vv = u)
continue;
e[vv].erase(v);
if (e[vv].size() == 1 && !vis[vv])
{
vis[vv] = true;
qD.push(vv);
}
}
e[v].clear();
}
e[u].clear();
}
}
for (int i = 1; i <= n; i++)
if (ans[i])
levels.push_back(ans[i]);
sort(levels.begin(), levels.end());
for (auto x : levels)
cout << x << " ";
cout << "\n";
return 0;
}
因为这不是一个 DAG 而是一棵树，所以实际上可以直接树上 dfs 找到每个点是中心还是星星图的边缘。因为按照题目构成树的方法，只有唯一解，所以不用考虑多解的情况。
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> e[212345];
bool vis[212345]; // i 被处理过（被捕获了的行星/是恒星）
int ans[212345]; // i 作为恒星的大小
vector<int> levels;
void dfs(int u, int fa)
{
bool flag1 = false; // 下面有恒星
bool flag2 = true; // 下面都是被处理过了
for (auto v : e[u])
{
if (v == fa)
continue;
dfs(v, u);
flag1 = flag1 || (ans[v] > 0);
flag2 = flag2 && vis[v];
}
if (flag1)
{
// 下面有恒星，当前是被捕获了的行星
vis[u] = true;
}
else if (flag2)
{
// 下面没有恒星，且全是已被捕获行星时，当前就是未被捕获的行星
vis[u] = false;
}
else
{
// 下面没有恒星且有未被捕获的行星，当前就是恒星
vis[u] = true;
ans[u] = e[u].size();
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n - 1; i++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++)
if (ans[i])
levels.push_back(ans[i]);
sort(levels.begin(), levels.end());
for (auto x : levels)
cout << x << " ";
cout << "\n";
return 0;
}
比赛时一开始读错题，最终狂乱写法的代码：
#include <bits/stdc++.h>
using namespace std;
int n;
set<int> e[212345];
int d[212345];
int cnt[212345];
int hav[212345];
queue<int> q;
bool vis[212345];
vector<int> ans;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n - 1; i++)
{
int u, v;
cin >> u >> v;
e[u].insert(v);
e[v].insert(u);
d[u]++;
d[v]++;
}
for (int i = 1; i <= n; i++)
{
hav[i] = 1;
if (d[i] == 1)
{
vis[i] = true;
q.push(i);
}
}
while (!q.empty())
{
int u = q.front();
q.pop();
if (e[u].empty())
continue;
int v = *(e[u].begin());
//cout << u << " " << v << endl;
e[v].erase(e[v].find(u));
e[u].erase(e[u].begin());
d[u]--;
d[v]--;
if (!vis[v] && d[v] == 1)
{
vis[v] = true;
q.push(v);
}
if (cnt[u] == 0)
{
cnt[v] += hav[u];
hav[u] = 0;
}
else
{
cnt[u] += hav[v];
hav[v] = 0;
}
}
for (int i = 1; i <= n; i++)
{
if (cnt[i])
{
//cout << i << ":" << cnt[i] << endl;
ans.push_back(cnt[i]);
}
}
sort(ans.begin(), ans.end());
for (int x : ans)
cout << x << " ";
return 0;
}