A – Chord (abc312 A)
题目大意
给定一个长度为(3)的字符串，问是不是ACE, BDF, CEG, DFA, EGB, FAC, GBD中的一个。
解题思路
依次判断即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
set q{"ACE", "BDF", "CEG", "DFA", "EGB", "FAC", "GBD"};
string a;
cin >> a;
if (q.find(a) != q.end()) {
cout B – TaK Code (abc312 B)
题目大意
给定一个仅包含#.的二维图案，找出所有符合以下模板的(9 times 9)的子图案。
###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###
其中#.必须严格符合，而?随意。
解题思路
数据规模不大，直接枚举(9 times 9)的左上角，然后暴力判断这个图案是否符合上述要求即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string t = "###.?????"
"###.?????"
"###.?????"
"....?????"
"?????????"
"?????...."
"?????.###"
"?????.###"
"?????.###";
int n, m;
cin >> n >> m;
vector s(n);
for (auto& i : s)
cin >> i;
auto ok = [&](int x, int y) {
for (int i = 0; i = n || ny >= m)
return false;
if (t[pos] != '?' && s[nx][ny] != t[pos])
return false;
}
return true;
};
for (int i = 0; i C – Invisible Hand (abc312 C)
题目大意
有(n)个售卖者和(m)个购买者。
你现在要决定一个最小的价格(x)，使得愿意售卖的人数不小于愿意购买的人数。
对于第(i)个售卖者，如果 (x geq a_i)，则他愿意售卖。
对于第(i)个购买者，如果 (x leq b_i)，则他愿意购买。
解题思路
注意到(x)越大，愿意售卖的人会越来越多，愿意购买的人会越来越小，两者均呈现一个单调性，因而愿意售卖人数-愿意购买人数也具有 单调性，而题意就是找零点。因此我们可以二分这个x。
事先对售卖者的(a_i)和购买者的(b_i)排个序，对于一个(x)，可通过二分找到愿意售卖和购买的人数，然后判断是否符合条件即可。
时间复杂度是(O(log 10^9 log nm))
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector a(n), b(m);
for (auto& i : a)
cin >> i;
for (auto& i : b)
cin >> i;
int l = -1, r = 1e9 + 1;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
while (l + 1 > 1;
int seller = upper_bound(a.begin(), a.end(), mid) - a.begin();
int buyer = b.end() - lower_bound(b.begin(), b.end(), mid);
if (seller >= buyer)
r = mid;
else
l = mid;
}
cout 或许你可以注意到最终答案一定是其中的(a_i)或 (b_i)，因此可以从小到大枚举这些候选答案，故愿意售卖的人数会越来越多，愿意购买的人数会越来越小，两个双指针维护一下其人数也可以。
D – Count Bracket Sequences (abc312 D)
题目大意
给定一个()?的序列，将其中的?替换成(或)。
问有多少种替换方案，满足替换后的序列符合一个合法的括号序列。
解题思路
要判断一个序列是否是合法的括号序列，就要求从左到右的每个位置，(的数量不少于)的数量，且最后两者数量相等。
因此为了保证方案的合法性，我们在搜索时需要记录此时有多少个(和)，但这样的状态是(O(n^2))，注意到我们实际上并不需要记录括号的对数，只需要保证其差 不小于0，且最后的差等于0，因此我们只需记录两者的差，就可以转移了。
即设(dp[i][j])表示前 (i)个字符中，替换 ?后(数量 - )数量 = j的方案数。
根据当前的字符转移即可，如果是?则决定是(还是)。
初始条件就是(dp[0][0] = 1)
神奇的代码
#include
using namespace std;
using LL = long long;
const int mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
int n = s.size();
vector dp(n + 1, 0);
dp[0] = 1;
for (auto& c : s) {
vector dp2(n + 1, 0);
for (int i = 0; i = mo)
dp2[i] -= mo;
}
}
dp.swap(dp2);
}
cout E – Tangency of Cuboids (abc312 E)
题目大意
给定(n)个没有相交的正方体，对于每个正方体，问它与多少个正方体会有面的相切。
解题思路
考虑正方体面相切的情况，分别为上下切、左右切、前后切，其实分别对应着某一维度的坐标相同。
因此我们分别考虑三个坐标相同的情况。
比如对于同为(z=1)的面，我们要判断的就是这个面上的一个正方形与多少个正方形相交。
考虑如何判断正方形相交，或者相离，由于坐标大小只有(100)，感觉可以前缀和然后容斥下，但发现貌似非常复杂。
注意到正方形相交的情况，由于题意表示正方体之间没有相交，这意味着在这个平面内，某点最多被两个正方形覆盖（上下相切的话，那么某点被正方形覆盖，只有上正方体和下正方体的两个面），这意味着我们可以直接记录某个位置是被哪个正方形覆盖的，这样通过遍历每个位置，就知道每个位置有哪两个正方形相互覆盖了。
神奇的代码
#include
using namespace std;
using LL = long long;
constexpr int sz = 101;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector> p(n);
for (auto& i : p) {
for (auto& j : i)
cin >> j;
}
vector> ans(n);
auto solve = [&](int x, int y, int z) {
array, sz> id;
for (int i = 0; i , sz> belong{};
for (auto& i : belong)
fill(i.begin(), i.end(), -1);
for (auto& i : id[Z]) {
for (int X = p[i][y]; X F – Cans and Openers (abc312 F)
题目大意
给定(n)个物品，物品分三种：
- 普通物品，快乐值 (x_i)
- 特殊物品，需要钥匙打开，快乐值 (x_i)
- 钥匙物品，可打开(x_i) 个特殊物品。
你现在只能拿(m)个物品，问最大的快乐值。
解题思路
初看此题，有一些比较显然的性质。
如果规定了只能拿(a)个普通物品，那我肯定拿快乐值最大的那 (a)个。 同理对于特殊物品、钥匙物品，都是贪心的取最大的那些。
由于(n)有 (10^5)，注定我们只能枚举一种物品的数量。
可以发现如果考虑枚举取(a)个钥匙物品的数量的话，假设这(a)个钥匙物品可打开 (b)个特殊物品，那剩下的就是从所有普通物品和前 (b)大的特殊物品中取快乐值最大的 (m-a)个。随着这个 (a)的递增，可取的特殊物品的范围越来越大，这意味着我们可以继承上一步的信息，考虑新增的特殊物品是否取即可。
维护一堆物品的前 (m)大的和，用一个小根堆的优先队列维护，当新增的物品的快乐值大于堆顶时，且堆大小等于 (m)，则丢弃堆顶，将新的放进去。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
array, 3> items;
for (int i = 0; i > t >> x;
items[t].push_back(x);
}
for (auto& item : items)
sort(item.begin(), item.end(), greater());
priority_queue s;
LL sum = 0;
for (int i = 0; i m) {
sum += s.top();
s.pop();
}
while (l = items[1].size())
break;
if (s.size() G – Avoid Straight Line (abc312 G)
题目大意
给定一棵树，问有多少个递增的三元组((i,j,k))，满足不存在一条简单路径覆盖这三个点。
解题思路
首先考虑怎样的三个点不能被一条简单路径覆盖。
树上两点确定唯一一条路径，如果第三点在这条路径上，或者在两点的子树里，则可以存在一条路径覆盖这三个点，其点数时两个子树大小+路径长度，这两个值都可以通过预处理很快算出来，其补集就是不存在覆盖情况。
但如果枚举这两点的话，复杂度避免不了(O(n^2))，因此只能枚举一个点。
同样考虑枚举这条路径，要么枚举路径最边边的点要么枚举路径的中间点。
可以发现枚举路径的中间点(u)时，另外两个点的所在情况只有两种：
- 两个点在(u)的两个不同的儿子子树中，这个用类似树形(dp)的方式合并求答案即可。
- 一个点在(u)的儿子子树 ，另一个点在父亲往上的其余位置。父亲往上的情况数就是总点数减去子树大小。
两种情况累加存在简单路径覆盖三个点的情况。
用总情况数((frac{n(n-1)(n-2)}{6}))减去即为答案。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector> edge(n);
for (int i = 0; i > u >> v;
--u, --v;
edge[u].push_back(v);
edge[v].push_back(u);
}
LL ans = 0;
vector son(n, 0);
function dfs = [&](int u, int fa) {
for (auto& v : edge[u]) {
if (v == fa)
continue;
dfs(v, u);
ans += 1ll * son[u] * son[v];
son[u] += son[v];
}
son[u] += 1;
ans += 1ll * (son[u] - 1) * (n - son[u]);
};
dfs(0, 0);
ans = (1ll * n * (n - 1) * (n - 2) / 6 - ans);
cout Ex – snukesnuke (abc312 Ex)
题目大意
有(n)个人及其名字 (s_i)。
但名字可能有重复，为了不重复，你需要依次对每个人的名字操作。
对于第 (i)个人的名字，如果它与前面的重复了，你需要决定一个最小的数 (k)，使得 (s_i)重复 (k)次后与前面不重复。
对于每个人，输出 (k)的大小。
解题思路
考虑对字符串hash，这样的话重复操作相当于hash的一个简单四则运算（乘以一个关于长度的基底+原字符串hash值）。
然后我们记录哪些hash值出现过，暴力做貌似最坏会(O(n^2)) ，就像样例(3)的五个 x。究其原因是我们经过了很多次的x -> xx -> xxx这样重复的变换了，为了不重复，我们可以把这样的信息记录下来，即记录某个hash值因冲突而被重复的最高次数，或许就能(O(text{能过}))?
写了写发现过了，朴素的自然hash也没被卡。细想一下复杂度貌似确实是(O(n))的，考虑每个字符串被后面字符串考虑是否冲突的次数，会发现最多只有一次，即在因冲突而进行重复操作后，之后因为记录了最高重复次数，所以之后考虑时就不再会考虑这个字符串了。
神奇的代码
#include
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const int x = 135;
const int N = 2e5 + 10;
ULL xp[N];
void init_xp() {
xp[0] = 1;
for (int i = 1; i = 0; --j) {
val = val * x + s[j];
}
return val;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init_xp();
int n;
cin >> n;
unordered_set name;
unordered_map k;
unordered_map khash;
for (int i = 0; i > s;
ULL val = hash_string(s);
ULL cur = val;
int ans = 0;
if (name.find(val) == name.end()) {
ans = 1;
} else {
if (k.find(val) == k.end())
ans = 1;
else {
ans = k[val];
cur = khash[val];
}
while (name.find(cur) != name.end()) {
cur = cur * xp[s.size()] + val;
++ans;
}
}
k[val] = ans;
khash[val] = cur;
name.insert(cur);
cout 机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net
