A[CF1025A(800)]
观察一下容易发现只要存在两个不同字母即可。
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; string S; cin >> S; if (N == 1) { cout << "Yes" << ' '; exit(0); } vector<int> cnt(26); for (char c : S) { cnt[c - 'a'] ++; } if (*max_element(cnt.begin(), cnt.end()) == 1) { cout << "No" << ' '; } else { cout << "Yes" << ' '; } }
View Code
B[UOJ436(1500)]
一个简单的想法是每次消掉最底层的公共部分，然后把整体分为两部分递归进行，可以$nlogn$实现。当然仔细观察可以发现答案等价于$a_n+sum_{i=1}^{n-1}{max(0,a_{i+1}-a_i}$，因为一个断崖会造成额外的贡献。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } long long ans = a[n - 1]; for (int i = 0; i < n - 1; ++i) { ans += max(0ll, a[i] - a[i + 1]); } cout << ans << ' '; }
View Code
C[计蒜客39280(1800)]
发现具有单调性，二分答案然后用$bfs$判断即可。
D[1213G(1800)]
比较套路的想法，首先把询问按照最大值大小排序，然后考虑从小到大加边使得最大值满足要求，每次合并两个顶点时计算合并的贡献即可，利用并查集维护图的连通性。
#include <bits/stdc++.h> using namespace std; using lint = long long; template<class T = int> using V = vector<T>; template<class T = int> using VV = V< V<T> >; struct UnionFind { const int n; V<> t; // root ? -sz : par UnionFind(int n) : n(n), t(n, -1) {} int find(int v) { return t[v] < 0 ? v : t[v] = find(t[v]); } void unite(int u, int v) { if ((u = find(u)) == (v = find(v))) return; if (-t[u] < -t[v]) swap(u, v); t[u] += t[v]; t[v] = u; } bool same(int u, int v) { return find(u) == find(v); } int size(int v) { return -t[find(v)]; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, m; cin >> n >> m; struct Edge { int u, v, w; }; V<Edge> es(n - 1); for (int i = 0; i < n - 1; ++i) { int u, v, w; cin >> u >> v >> w, --u, --v; es[i] = {u, v, w}; } struct Q { int id, q; }; V<Q> qs(m); for (int i = 0; i < m; ++i) { int q; cin >> q; qs[i] = {i, q}; } sort(begin(qs), end(qs), [](const Q& l, const Q& r) { return l.q < r.q; }); V<lint> res(m, -1); UnionFind uf(n); lint t = 0; sort(begin(es), end(es), [](const Edge& l, const Edge& r) { return l.w < r.w; }); auto itr = begin(es); for (const auto& e : qs) { while (itr != end(es) and itr->w <= e.q) { lint sz = uf.size(itr->u); t -= sz * (sz - 1) / 2; sz = uf.size(itr->v); t -= sz * (sz - 1) / 2; uf.unite(itr->u, itr->v); sz = uf.size(itr->u); t += sz * (sz - 1) / 2; ++itr; } res[e.id] = t; } for (int i = 0; i < m; ++i) { cout << res[i] << " "[i == m - 1]; } }
View Code