ABC377(A-G)
A - Rearranging ABC¶
题目大意
给你一个长度为 \(3\) 的由大写字母组成的字符串 \(S\)，判断能否重排 \(S\) 使其等于 ABC
参考代码
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
string s;
cin >> s;
sort(s.begin(), s.end());
cout << (s == "ABC" ? "Yes" : "No") << endl;
return 0;
}
B - Avoid Rook Attack¶
题目大意
给你一个 \(8 \times 8\) 的棋盘，每个位置如果是 . 表示上面没有棋子，如果是 # 表示上面有国际象棋的车。国际象棋的车能攻击到同一行、同一列的棋子。问：棋盘上有多少个位置不会被任何车攻击到？
参考代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
const int n = 8;
vector<string> g(n);
vector<bool> row(n), col(n);
for (int i = 0; i < n; i++)
{
cin >> g[i];
for(int j = 0; j < n; j++)
if(g[i][j] == '#')
{
row[i] = true;
col[j] = true;
}
}
int ans = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(!row[i] && !col[j])
ans++;
cout << ans << endl;
return 0;
}
C - Avoid Knight Attack¶
题目大意
有一个 \(N \times N(1 \le N \le 10 ^ 9)\) 的棋盘，棋盘上有 \(M(1 \le M \le 2 \times 10 ^ 5)\) 个国际象棋的马，第 \(i\) 个马的位置是 \((a_i, b_i)\) 。国际象棋的马能够攻击到“日”形状的位置，且不受蹩马腿的限制。问：棋盘上有多少个位置不会被任何马攻击到？
解题思路
因为 \(N\) 很大，但是 \(M\) 较小，只需要记录下所有被马攻击到的位置，用合法的位置去减就可以。
参考代码
#include <iostream>
#include <set>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
set<pair<int, int>> vis;
int dr[] = {-1, 1, -2, 2, -2, 2, -1, 1};
int dc[] = {-2, -2, -1, -1, 1, 1, 2, 2};
auto in_lim = [n](int r, int c) -> bool
{ return r > 0 && r <= n && c > 0 && c <= n; };
while (m--)
{
int r, c;
cin >> r >> c;
for (int i = 0; i < 8; i++)
{
int nr = r + dr[i];
int nc = c + dc[i];
if (in_lim(nr, nc))
vis.insert({nr, nc});
}
vis.insert({r,c});
}
cout << (long long)n * n - vis.size() << endl;
return 0;
}
D - Many Segments 2¶
题目大意
给你 \(N(1 \le N \le 2 \times 10 ^ 5)\) 个闭区间和一个整数 \(M(1 \le M \le 2 \times 10 ^ 5)\)，第 \(i\) 个闭区间为 \([L_i, R_i]\)，其中 \(1 \le L_i \le R_i \le M\)。求出有多少个数对 \((l, r)\) 满足以下条件：
- \(1 \le l \le r \le M\)
- 对于任意的 \(1 \le i \le N\)，区间 \([L_i, R_i]\) 不被 \([l, r]\) 完全包含。
解题思路
对于两个区间，\([L_i, R_i]\) 和 \([L_j, R_j]\)，如果 \(R_i = R_j\)，则实际只需要考虑 \(L\) 更大的区间，因为更大 \(L\) 意味着区间更小，也就更容易被包含。
设 \(f[r]\) 表示对于某个特定的 \(r\) 值，满足条件的 \(l\) 值的最小值。也就是当 \(f[r] \le l \le r\) 就能满足条件。这样，对于固定的 \(r\) 值，其贡献的 \((l, r)\) 数量就是 \(r-f[r]+1\)。初始的时候我们有 \(f[0] = 1\)。
\(f[r]\) 的含义表示 \([f[r], r]\) 不会完全包含任何区间，而 \([f[r]-1, r]\) 会完全包含一个区间从而不满足条件。于是我们可以挖掘一个性质，也就是 \(f[r] \ge f[r-1]\)，正确性可以用反证法证明。
于是我们遍历 \(r\) 值，当 \(r\) 值向右扩充的时候，考虑是否有某个区间是 \([L_i, r]\)，如果有这样的区间，为了避免完全包含进来，\(l\) 的值至少需要是 \(L_i+1\)，于是我们可以得到 \(f[r] = \max(f[r-1], L_i+1)\)。这样就做完了。
参考代码
#include <iostream>
#include <map>
using namespace std;
using LL = long long;
int main()
{
int n, m;
cin >> n >> m;
map<int, int> l_map;
for (int i = 0; i < n; i++)
{
int l, r;
cin >> l >> r;
l_map[r] = max(l_map[r], l);
}
l_map[m+1] = m+1;
auto it = l_map.begin();
int nr = it->first, nl = it->second;
int l = 1;
LL ans = 0;
for(int r = 1; r <= m; r++)
{
if(r == nr)
{
l = max(l, nl + 1);
it++;
nr = it->first;
nl = it->second;
}
ans += r - l + 1;
}
cout << ans << endl;
return 0;
}
E - Permute K times 2¶
题目大意
给你一个 \(1\) 到 \(N(2 \times 10 ^ 5)\) 的排列 \(P = (P_1, P_2, \cdots, P_N)\)，执行以下操作 \(K(1 \le K \le 10 ^ {18})\) 次：
- 对于 \(i = 1, 2, ..., N\)，同时 将 \(P_i\) 替换为 \(P_{P_i}\)
输出 \(K\) 次操作后的序列。
解题思路
之前做过两道类似的题目：ABC367-E、ABC371-G 但这道题有一个不太一样的地方，前面两道题有两个序列，一个是不变的序列指导如何置换，另一个序列的数字进行换位。但是这道题只有一个序列，既是置换序列，也要交换自己的位置。推导一下规律。不妨设 \(f[i][j]\) 表示进行了 \(i\) 次操作后第 \(j\) 个位置的值。则有：
因此我们有 \(f[K][j] = P^{2^K}_j\)，这个计算式仅仅依赖于初始的排列 \(P\)，也就是替换一次的结果，于是我们和前面的解法一样，将数字的替换关系处理成环，每个位置置换 \(2^K\) 轮，求出环的长度 \(m\)，相当于每个环置换 \(2^K \bmod m\) 次。
参考代码
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
int n;
LL k;
cin >> n >> k;
vector<int> p(n);
for(int i = 0; i < n; i++)
{
cin >> p[i];
p[i]--;
}
vector<bool> vis(n);
vector<int> ans(n);
auto quick_pow = [](LL x, LL a, LL mod) -> LL
{
LL res = 1;
while(a)
{
if(a & 1)
res = res * x % mod;
x = x * x % mod;
a >>= 1;
}
return res;
};
for(int i = 0; i < n; i++)
{
if(vis[i])
continue;
int u = i;
vector<int> idx;
while(!vis[u])
{
vis[u] = true;
idx.push_back(u);
u = p[u];
}
int len = idx.size();
LL d = quick_pow(2, k, len);
d = (d - 1 + len) % len;
for(int x = 0, y = d; x < len; x++, y = (y + 1) % len)
{
int u = idx[x], v = idx[y];
ans[u] = p[v];
}
}
for(int i = 0; i < n; i++)
cout << ans[i] + 1 << ' ';
return 0;
}
F - Avoid Queen Attack¶
题目大意
有一个 \(N \times N(1 \le N \le 10 ^ 9)\) 的棋盘，棋盘上有 \(M(1 \le M \le 2 \times 10 ^ 3)\) 个国际象棋的皇后，第 \(i\) 个皇后的位置是 \((a_i, b_i)\) 。国际象棋的皇后能够攻击到同一行、同一列、同一条主对角线和副对角线的棋子。问：棋盘上有多少个位置不会被任何皇后攻击到？
解题思路
因为 \(N\) 很大。如果标记每一行、列、主副对角线有皇后，然后枚举每一个点的话，时间复杂度达到 \(O(N^2)\)，过不了。
考虑找出有多少个点会被攻击到，处于位置 \((a_i, b_i)\) 的皇后可以攻击到四条直线的棋子：\(r = a_i\)，\(c = b_i\)，\(r+c = a_i + b_i\)，\(r-c = a_i - b_i\)。
\(r = a_i\) 和 \(c = b_i\) 的直线各自会攻击到 \(N\) 个点（包括皇后自身），\(r+c = a_i + b_i\) 的直线取决会攻击到 \(a_i + b_i - 1\) 个点（当 \(a_i + b_i \le N + 1\) 也就是直线在上半区时）或 \(2N + 1 - a_i - b_i\) 个点（当 \(a_i + b_i > N + 1\) 也就是直线在下半区时）。
\(r-c = a_i - b_i\) 的直线取决会攻击到 \(a_i - b_i + N\) （当 \(a_i - b_i \le 0\) 也就是直线在上半区时）个点或 \(N - a_i + b_i\) 个点（当 \(a_i - b_i > 0\) 也就是直线在下半区时）。
但是这样会有一些问题，有一些点会被多次计入。可以发现这些点都是直线之间产生的交点，我们可以记录下所有交点和相交次数。一共有 \(M\) 个皇后，也就是至多 \(4M\) 条直线，一个点至多被 \(4\) 条直线经过，如果有 \(2\) 个直线过 \(1\) 个点，那么两两相交的次数是 \(1\)；如果有 \(3\) 个点，两两相交的次数是 \(3\)；\(4\) 条直线两两相交的次数是 \(6\) 次。记录下所有交点的相交次数，最后的统一减掉就好。
参考代码
#include <iostream>
#include <map>
#include <unordered_set>
#include <utility>
using namespace std;
using LL = long long;
int main()
{
LL n;
int m;
cin >> n >> m;
unordered_set<LL> r, c, sum, diff;
map<pair<LL, LL>, int> cnt;
auto valid = [n](LL x) -> bool
{ return x >= 1 && x <= n; };
for (int i = 0; i < m; i++)
{
LL nr, nc;
cin >> nr >> nc;
if (!r.count(nr))
{
// r = nr
// c = cc
for (auto cc : c)
cnt[{nr, cc}]++;
// r + c = s
// c = s - nr
for (auto s : sum)
if (valid(s - nr))
cnt[{nr, s - nr}]++;
// r - c = d
// c = nr - d
for (auto d : diff)
if (valid(nr - d))
cnt[{nr, nr - d}]++;
}
if (!c.count(nc))
{
// c = nc
// r = rr
for (auto rr : r)
cnt[{rr, nc}]++;
// r + c = s
// r = s - nc
for (auto s : sum)
if (valid(s - nc))
cnt[{s - nc, nc}]++;
// r - c = d
// r = nc + d
for (auto d : diff)
if (valid(nc + d))
cnt[{nc + d, nc}]++;
}
if (!sum.count(nr + nc))
{
// r + c = nr + nc
// r = rr
// c = nr + nc - rr
for (auto rr : r)
if (valid(nr + nc - rr))
cnt[{rr, nr + nc - rr}]++;
// c = cc
// r = nr + nc - cc
for (auto cc : c)
if (valid(nr + nc - cc))
cnt[{nr + nc - cc, cc}]++;
// r - c = d
// r = (nr + nc + d) / 2
// c = (nr + nc - d) / 2
for (auto d : diff)
if ((nr + nc + d) % 2 == 0 && valid((nr + nc + d) / 2) && valid((nr + nc - d) / 2))
cnt[{(nr + nc + d) / 2, (nr + nc - d) / 2}]++;
}
if (!diff.count(nr - nc))
{
// r - c = nr - nc
// r = rr
// c = rr - nr + nc
for (auto rr : r)
if (valid(rr - nr + nc))
cnt[{rr, rr - nr + nc}]++;
// c = cc
// r = nr - nc + cc
for (auto cc : c)
if (valid(nr - nc + cc))
cnt[{nr - nc + cc, cc}]++;
// r + c = s
// r = (nr - nc + s) / 2
// c = (s - nr + nc) / 2
for (auto s : sum)
if ((nr - nc + s) % 2 == 0 && valid((nr - nc + s) / 2) && valid((s - nr + nc) / 2))
cnt[{(nr - nc + s) / 2, (s - nr + nc) / 2}]++;
}
r.insert(nr);
c.insert(nc);
sum.insert(nr + nc);
diff.insert(nr - nc);
cnt[{nr, nc}] = 6;
}
LL ans = n * n - (r.size() + c.size()) * n;
for (auto s : sum)
ans -= s <= n + 1 ? s - 1 : 2 * n + 1 - s;
for (auto d : diff)
ans -= d <= 0 ? d + n : n - d;
for (auto [p, c] : cnt)
if (c == 1)
ans++;
else if (c == 3)
ans += 2;
else if (c == 6)
ans += 3;
cout << ans << endl;
return 0;
}
G - Edit to Match¶
题目大意
给你 \(N(1 \le N \le 2 \times 10 ^ 5)\) 个字符串 \(S_1, S_2, ..., S_N\)。其中每个字符串都由小写字母组成且 \(\sum\limits_{i = 1} ^ N|S_i| \le \times 10 ^ 5\)。
对于每个 \(k = 1, 2, ... , N\)，解决以下问题：
初始的时候，你有一个字符串 \(T = S_k\)，你可以执行以下两种类型的操作：
- 花费 \(1\) 元删除 \(T\) 的最末尾字符。
- 花费 \(1\) 元在 \(T\) 的末尾添加任意一个小写字母。
问：至少需要花费多少元，才能让 \(T\) 等于 \(S_1, S_2, ... , S_{k-1}\) 或空字符串？
解题思路
可以发现，如果 \(T\) 添加了一个字符，则后面一定不会删掉这个字符（否则，一开始就该不加这个字符）。因此最优的做法一定是先执行操作 1 删掉一部分后缀的字符，然后只执行操作 2 添加字符直到匹配。为此，我们需要知道 \(T\) 的某个前缀匹配 \(S_1, S_2, ..., S_k\) 还需要补齐多少字符，只需要用 Trie 树维护这个信息即可，如果某个前缀匹配了多个字符串，就取长度最短的那个。这个操作甚至可以在插入字符串的同时维护。
参考代码
#include <iostream>
#include <limits>
#include <string>
#include <unordered_map>
using namespace std;
struct Trie
{
struct Node
{
unordered_map<char, Node *> ne;
int dis = numeric_limits<int>::max() / 2;
void update(int d) { dis = min(dis, d); }
Node *at_or_new(char ch)
{
auto it = ne.find(ch);
if (it == ne.end())
it = ne.insert({ch, new Node()}).first;
return it->second;
}
};
Node *root = new Node();
int insert(const string &s)
{
int n = s.size();
int ans = n;
Node *p = root;
for (int i = 0; i < n; i++)
{
char ch = s[i];
p = p->at_or_new(ch);
ans = min(ans, n - i - 1 + p->dis);
p->update(n - i - 1);
}
return ans;
}
};
int main()
{
int n;
cin >> n;
Trie t;
while(n--)
{
string s;
cin >> s;
cout << t.insert(s) << endl;
}
return 0;
}
创建日期: 2024-12-23