A - CAPS LOCK (abc292 a)
题目大意
给定一个小写字母串，将其转换成大写字母。
解题思路
调库，或者按照ascii码转换即可。
神奇的代码
#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;
cin >> s;
for(auto &i : s)
i = toupper(i);
cout << s << endl;
return 0;
}
B - Yellow and Red Card (abc292 b)
题目大意
\(n\)个人， \(m\)个事件，分三种：给某人黄牌，给某人红牌，问某人是否被罚下场。
如果一人被罚两张黄牌或一张红牌则被罚下场。
回答每个询问。
解题思路
按照题意，维护每个人的黄牌和红牌数量模拟即可。
神奇的代码
#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, q;
cin >> n >> q;
vector<vector<int>> cnt(2, vector<int>(n, 0));
while(q--){
int c, x;
cin >> c >> x;
c --;
x --;
if (c == 2){
if (cnt[0][x] < 2 && cnt[1][x] < 1)
cout << "No" << '\n';
else
cout << "Yes" << '\n';
}else
cnt[c][x] ++;
}
return 0;
}
C - Four Variables (abc292 c)
题目大意
给定\(n\)，问有多少正整数组\((A,B,C,D)\)，满足 \(AB + CD = n\)
解题思路
给定\(X\)，预处理\(AB=X\) 的方案数\(cnt[X]\)。
然后枚举\(AB\)的乘积 \(X\)，则 \(CD\)的乘积为 \(n-X\)，其两个方案数相乘\(cnt[X] \times cnt[n - X]\)。然后累加即是答案。
时间复杂度为 \(O(n\log 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;
vector<int> cnt(n + 1);
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j){
if (1ll * i * j > n)
break;
cnt[i * j] ++;
}
LL ans = 0;
for(int i = 1; i < n; ++ i)
ans += 1ll * cnt[i] * cnt[n - i];
cout << ans << '\n';
return 0;
}
D - Unicyclic Components (abc292 d)
题目大意
给定一张无向图，问每个连通块是否满足：其边数与点数相等。
解题思路
用并查集维护连通性，同时维护连通块的边数和点数，最后一一判断即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
class dsu {
public:
vector<int> p;
vector<int> psz;
vector<int> esz;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
psz.resize(n);
esz.resize(n);
iota(p.begin(), p.end(), 0);
fill(psz.begin(), psz.end(), 1);
fill(esz.begin(), esz.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
esz[y] ++;
if (x != y) {
p[x] = y;
psz[y] += psz[x];
esz[y] += esz[x];
return true;
}
return false;
}
inline bool check(){
for(int i = 0; i < p.size(); ++ i){
if (get(i) == i && psz[i] != esz[i]){
return false;
}
}
return true;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
dsu d(n);
for(int i = 0; i < m; ++ i){
int u, v;
cin >> u >> v;
-- u, -- v;
d.unite(u, v);
}
if (d.check())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
E - Transitivity (abc292 e)
题目大意
给定一张有向图。如果对于三个点\((a,b,c)\)， \(a->b\)， \(b->c\)，则必须有边\(a->c\) 。
问最少添加多少条边，使得对于任意三个点，都满足以上性质。
解题思路
考虑一条链，从左连到右，容易发现左边的点与右边的每个点都要连一条边。
即从一个点出发，它能到达的所有点，在最终的图都要与其连边。
因此从每个点\(BFS\)，求得其能到达的所有点数。对所有点累加即是最终图的边数，减去已有的边数，则是需要添加的最小边数。
神奇的代码
#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<vector<int>> edge(n);
for(int i = 0; i < m; ++ i){
int u, v;
cin >> u >> v;
-- u, -- v;
edge[u].push_back(v);
}
int ans = 0;
auto bfs = [&](int st){
queue<int> team;
team.push(st);
int cnt = 0;
vector<int> visit(n, 0);
visit[st] = 1;
while(!team.empty()){
auto u = team.front();
team.pop();
for(auto &v : edge[u]){
if (!visit[v]){
++ cnt;
team.push(v);
visit[v] = 1;
}
}
}
return cnt;
};
for(int i = 0; i < n; ++ i)
ans += bfs(i);
ans -= m;
cout << ans << '\n';
return 0;
}
F - Regular Triangle Inside a Rectangle (abc292 f)
题目大意
给定一个矩阵，问其内接的最大正三角形的边长是多少。
解题思路
从样例的图我们可以进行猜测：
- 三角形的一个顶点在矩形的顶点上
- 当矩形的长不够长时，三角形的另外两个点都在矩形的边上。
设\(15^\circ\)的角为 \(\theta\)，矩形长\(a\)，宽 \(b\)（\(a > b\)），三角形边长 \(x\)，根据正三角形边相等和高中数学知识可得
\[x = \frac{a}{\cos \theta} = \frac{b}{\cos(30^{\circ} - \theta)} \]用和角公式将\(\cos(30^{\circ} - \theta)\)拆开，然后解方程得到
\[\tan \theta = \frac{2b}{a} - \sqrt{3} \]因为这里\(0 \leq \theta \leq 30^\circ\)，所以 \(\tan \theta\)应该大于 \(0\)。因此这里就有个边界条件 \(\frac{2b}{a} > \sqrt{3}\)
一旦不满足，说明长 \(a\)太大了，此时三角形最大的情况，就是其高和矩形的宽相等，即三角形的边长就是 \(x = \frac{2b}{\sqrt{3}}\)
否则，算得\(\cos \theta = \sqrt{ \frac{1}{1 + tan^2 \theta}}\)，\(x = \frac{a}{cos \theta}\)
神奇的代码
#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 a, b;
cin >> a >> b;
if (a < b)
swap(a, b);
long double sq3 = sqrt(3);
if (2.0 * b / a < sq3){
double x = b / sq3 * 2;
cout << fixed << setprecision(15) << x << '\n';
}else {
long double tan = 2.0 * b / a - sq3;
long double cos = sqrt(1 / (1 + tan * tan));
long double x = a / cos;
cout << fixed << setprecision(15) << x << '\n';
}
return 0;
}
G - Count Strictly Increasing Sequences (abc292 g)
题目大意
给定\(n\)个长度为 \(m\)的包含数字和 ?的字符串。
将这些 ?替换数字。问有多少种替换方案，满足\(s_0 < s_1 < s_2 < ... < s_{n-1}\)
解题思路
应该是个数位\(DP\)
神奇的代码
Ex - Rating Estimator (abc292 h)
题目大意
<++>
解题思路
<++>
神奇的代码
标签：AtCoder,cnt,cout,Beginner,int,cin,long,using,292 From： https://www.cnblogs.com/Lanly/p/17179400.html