A - Majority (abc287 a)
题目大意
给定\(n\)个人对某个提案的意见，问大多数意见是支持还是反对
解题思路
统计比较即可。
神奇的代码
#include <bits/stdc++.h>
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;
int ans = 0;
while(n--){
string s;
cin >> s;
ans += (s[0] == 'F') * 2 - 1;
}
if (ans > 0)
cout << "Yes" << '\n';
else
cout << "No" << '\n';;
return 0;
}
B - Postal Card (abc287 b)
题目大意
给定\(n\)个字符串和 \(m\)个模板。
问有多少个字符串的后缀包含在这 \(m\)个模板内。
解题思路
用set储存这些模板，然后对于每个字符串直接查找即可。
神奇的代码
#include <bits/stdc++.h>
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<string> s(n);
for(auto &i : s)
cin >> i;
set<string> f;
for(int i = 0; i < m; ++ i){
string s;
cin >> s;
f.insert(s);
}
int ans = count_if(s.begin(), s.end(), [&](string& a){
return f.count(a.substr(3)) > 0;
});
cout << ans << '\n';
return 0;
}
C - Path Graph? (abc287 c)
题目大意
给定一张图，问是不是一个链。
解题思路
链的性质就是：
- 一个连通块
- 两个点度数为\(1\)，其余点度数为 \(2\)。
神奇的代码
#include <bits/stdc++.h>
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<int> du(n, 0);
vector<int> fa(n, 0);
iota(fa.begin(), fa.end(), 0);
function<int(int)> findfa = [&](int x){
return fa[x] == x ? x : fa[x] = findfa(fa[x]);
};
for(int i = 0; i < m; ++ i){
int u, v;
cin >> u >> v;
-- u;
-- v;
du[u] ++;
du[v] ++;
int fu = findfa(u);
int fv = findfa(v);
if (fu != fv)
fa[fu] = fv;
}
int one = count(du.begin(), du.end(), 1);
int two = count(du.begin(), du.end(), 2);
int block = 0;
for(int i = 0; i < n; ++ i)
block += (fa[i] == i);
if (one == 2 && two == n - 2 && block == 1)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
D - Match or Not (abc287 d)
题目大意
给定两个由小写字母和?组成的字符串\(S,T\)，
对于 \(x \in [0,|T|]\) ，问\(S^\prime\)和 \(T\)是否匹配。
其中 \(S^\prime\)由 \(S\)串的前 \(x\)个字符和后 \(|T| - x\)个字符组成。
两个字符串匹配，当且仅当将其中的 ?替换成英文字母后，两个字符串相同。
解题思路
两个字符串匹配，当且仅当每一位要么是相同字母，要么至少有一个?。于是我们可以储存所有不满足这些条件的位数。当且仅当该位数为\(0\)时，两个字符串匹配。
注意到当\(x\)递增的时候，前后两个 \(S^\prime\)仅有一个位置不同，因此我们可以继承上一个状态，仅修改变化的位置能否匹配即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
string s, t;
cin >> s >> t;
int n = s.size();
int m = t.size();
unordered_set<int> bad;
int tp = 0;
for(int i = n - m; i < n; ++ i, ++ tp){
if (s[i] != '?' && t[tp] != '?' && s[i] != t[tp])
bad.insert(tp);
}
if (bad.empty())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
for(int i = 0; i < m; ++ i){
bad.erase(i);
if (s[i] != '?' && t[i] != '?' && s[i] != t[i])
bad.insert(tp);
if (bad.empty())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
}
return 0;
}
E - Karuta (abc287 e)
题目大意
给定\(n\)个字符串，对于每个字符串 \(s_i\)，问 \(\max LCP(s_i, s_j)_{i \neq j}\)，其中\(LCP\)是最长公共前缀。
解题思路
注意到最大的最长公共前缀一定在字典序上前后两个的字符串之间，因此将这\(n\)个字符串按字典序排序，求每个字符串与其相邻的字符串的\(LCP\)，取最大值即可。
神奇的代码
#include <bits/stdc++.h>
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<string> s(n);
for(auto &i : s)
cin >> i;
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int x, int y){
return s[x] < s[y];
});
vector<int> ans(n);
auto LCP = [&](string& l, string& r){
int tmp = 0;
while(tmp < l.size() && tmp < r.size() && l[tmp] == r[tmp])
++ tmp;
return tmp;
};
for(int i = 0; i < n - 1; ++ i){
int l = id[i], r = id[i + 1];
int tmp = LCP(s[l], s[r]);
ans[l] = max(ans[l], tmp);
ans[r] = max(ans[r], tmp);
}
for(auto &i : ans)
cout << i << '\n';
return 0;
}
F - Components (abc287 f)
题目大意
给定一棵有\(n\)个点的树，在所有\(2^n - 1\)的非空点集中，回答下列问题：
对于\(i \in [1,n]\) ，有多少个点集所形成的连通块个数恰好是\(i\)。
数量对 \(998244353\)取模。
解题思路
当设\(dp[u][i]\)表示以 \(u\)为根的子树，能形成连通块数量恰好为 \(i\)的，点集数时，会发现在合并子树的时候，如果点\(u\)和子树节点都选择的时候，连通块个数会减一，其余情况都不会，因此还要加上是否选择点 \(u\)的状态。
设\(dp[u][i][0/1]\)表示以 \(u\)为根的子树，能形成连通块数量恰好为 \(i\)的，且不选择/选择点 \(u\)的点集数。
转移时枚举儿子树的连通块大小。
咋一看这样的复杂度会是\(O(n^3)\)，但如果每次枚举的范围都是儿子树的大小，可以证明这样的树型 \(dp\)的复杂度是 \(O(n^2)\)的。
神奇的代码
G - Balance Update Query (abc287 g)
题目大意
有\(N\)种类型的卡，每种卡有\(10^{100}\)张。每种卡有分数和大小属性。
维护以下三种操作：
1 x y，将第\(x\)种卡的分数修改为\(y\)。2 x y，将第\(x\)种卡的大小修改为\(y\)。3 x，选\(x\)张卡，要求最大化分数和，且每种类型的卡的数量不得超过其大小。
解题思路
不考虑修改，仅考虑询问的话，很显然我们从分数大的卡贪心取，直到取了\(x\)张。由于张数随着种类的增加而越来越多，因此可以二分取的卡的种类，计算一下取的卡的数量（其实就是大小属性的前缀和）求得答案。
而如果加上操作 \(2\)，实际上是要维护下大小属性的前缀和，用线段树维护即可（线段树二分的话复杂度还是不变的）
但如果加上操作\(1\)的话，就要动态维护卡的顺序就寄了，后续再思索思索。
神奇的代码
Ex - Directed Graph and Query (abc287 h)
题目大意
给定一张有向图，回答\(q\)组询问。
每组询问包括 \(s,t\)，问从 \(s\)到点 \(t\)的路径的代价最小值。
一条路径的代价是其经过的点的编号的最大值。
解题思路
如果是无向图，可以对原图跑一棵最小生成树，边权就是两点的点编号较大的那个。
然后每次询问其最大的，连接了这两个点的点，就是Kruscal重构树中两点的LCA。
但这是有向图。再思索思索。
神奇的代码
标签：tmp,AtCoder,cout,Beginner,int,cin,字符串,using,287 From： https://www.cnblogs.com/Lanly/p/17071525.html