A - Generalized ABC (abc282 a)
题目大意
给定\(n\)，输出一个字符串，从'A','B','C'...拼接得到的长度为 \(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;
string s;
for(int i = 0; i < n; ++ i)
s += 'A' + i;
cout << s << '\n';
return 0;
}
B - Let's Get a Perfect Score (abc282 b)
题目大意
给定一个\(01\)矩阵。选两行，其每一列至少有一个 \(1\)。问满足要求的选法。
解题思路
范围不大，暴力即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<string> qwq(n);
for(auto &i : qwq)
cin >> i;
int ans = 0;
auto check = [&](int x, int y){
int cnt = 0;
FOR(i, 0, m){
cnt += (qwq[x][i] == 'o' || qwq[y][i] == 'o');
}
return cnt == m;
};
FOR(i, 0, n)
FOR(j, i + 1, n){
ans += check(i, j);
}
cout << ans << '\n';
return 0;
}
C - String Delimiter (abc282 c)
题目大意
给定一个字符串，要求把非"括起来的,换成.。
解题思路
模拟即可。
神奇的代码
#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;
string s;
cin >> n >> s;
bool ok = false;
for(auto &i : s){
if (i == '\"')
ok ^= 1;
else if (i == ',' && !ok)
i = '.';
}
cout << s << '\n';
return 0;
}
D - Make Bipartite 2 (abc282 d)
题目大意
给定一张\(n\)个点的无向图，给其加一条边，满足其是二分图。问满足该条件的方案数。
解题思路
注意原图不一定连通。
对原图进行黑白染色，如果颜色冲突则答案为\(0\)。
否则，对于一个连通块内，假设点数为\(cnt\)，边数为 \(cntm\)，染了\(w\)个白点和 \(b\)个黑点，则满足要求的方案数为 \(wb - cntm\)。该连通块还能连向其他连通块，且可以任意连，其方案数为\(cnt \times (n - cnt)\)。
对所有连通块累计方案数即为答案。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
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 + 1);
vector<int> deep(n + 1, -1);
FOR(i, 0, m){
int u, v;
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
LL ans = 0;
vector<int> col(2, 0);
bool ok = true;
int cnt = 0;
set<pair<int, int>> ee;
function<void(int, int, int)> dfs = [&](int u, int fa, int cc){
deep[u] = cc;
col[cc] ++;
++ cnt;
for(auto &v : edge[u]){
if (v == fa)
continue;
ee.insert({u, v});
ee.insert({v, u});
if (deep[v] != -1){
if (deep[v] == deep[u])
ok = false;
}else
dfs(v, u, cc ^ 1);
}
};
int block = 0;
FOR(i, 1, n + 1){
if (deep[i] == -1){
++ block;
cnt = 0;
col[0] = col[1] = 0;
ee.clear();
dfs(i, i, 0);
int cntm = ee.size() / 2;
ans += 1ll * col[0] * col[1] - cntm;
ans += 1ll * cnt * (n - cnt);
n -= cnt;
}
}
if (!ok)
ans = 0;
cout << ans << '\n';
return 0;
}
E - Choose Two and Eat One (abc282 e)
题目大意
给定\(n\)个数，每个数范围\([1, m - 1]\)，每次选择两个数\(x,y\)，获得 \(x^y + y^x \mod m\) 分数。再将其中一个数丢弃，直至剩一个数。问获得的分数最大值。
解题思路
对于每个数，可能被选择多次，其中仅一次会被干掉，其他的都能保留。一个与多个的关系与树节点非常类似。
给定一棵树，题意操作相当于每次将叶子节点去掉，同时获得叶子与父亲的边权值。
对原图跑一边最大生成树即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
int n, m;
LL qpower(LL a, LL b){
LL qwq = 1;
while(b){
if (b & 1)
qwq = qwq * a % m;
a = a * a % m;
b >>= 1;
}
return qwq;
}
LL calc(LL x, LL y){
return (qpower(x, y) + qpower(y, x)) % m;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
vector<vector<LL>> dis(n + 1, vector<LL>(n + 1, 0));
vector<LL> a(n + 1);
for(int i = 1; i <= n; ++ i){
cin >> a[i];
}
vector<pair<LL, pair<int, int>>> edge;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
edge.push_back({calc(a[i], a[j]), {i, j}});
vector<int> fa(n + 1);
function<int(int)> findfa = [&](int x){
return fa[x] == x ? x : fa[x] = findfa(fa[x]);
};
iota(fa.begin(), fa.end(), 0);
sort(edge.begin(), edge.end(), [&](const pair<LL, pair<int, int>>& a, const pair<LL, pair<int, int>>& b){
return a.first > b.first;
});
LL ans = 0;
for(auto &i : edge){
int fu = findfa(i.second.first);
int fv = findfa(i.second.second);
if (fu != fv){
fa[fu] = fv;
ans += i.first;
}
}
cout << ans << '\n';
return 0;
}
F - Union of Two Sets (abc282 f)
题目大意
交互题。给定\(n\)，要求生成 \(m\)个区间，并用这些区间回答 \(q\)组询问。
每组询问给定 \(l,r\)，要求从 \(m\)个区间选出 \(2\)个区间，其并集为区间\([l,r]\) 。
\(n \leq 4000, m \leq 500000\)
解题思路
其实\(RMQ\)里的\(ST\)表的做法就能达到题目所述的要求。
即为每个左端点生成\(2\)的幂的区间。
设长度 \(len = r - l + 1\) ，其最大的小于等于\(len\)的 \(2\)的幂为 \(x\)。
则选择的区间为 \([l, l + x - 1], [r - x + 1, r]\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
inline int highbit(int x) { return 31 - __builtin_clz(x); }
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
map<pair<int, int>, int> area;
int m = 0;
for(int i = 1; i <= n; ++ i){
for(int j = 1; i + j - 1 <= n; j <<= 1){
++ m;
area[{i, i + j - 1}] = m;
}
}
cout << area.size() << '\n';
for(auto &i : area){
cout << i.first.first << ' ' << i.first.second << '\n';
}
cout.flush();
int q;
cin >> q;
while(q--){
int l, r;
cin >> l >> r;
int t = highbit(r - l + 1);
cout << area[{l, l + (1 << t) - 1}] << ' ' << area[{r - (1 << t) + 1, r}] << endl;
}
return 0;
}
G - Similar Permutation (abc282 g)
题目大意
定义两个排列的相似度为，差分数组下符号相同的标号数量。
给定\(n,k\)，问 长度为 \(n\)的相似度为 \(k\)的排列对数。
解题思路
<++>
神奇的代码
Ex - Min + Sum (abc282 h)
题目大意
<++>
解题思路
<++>
神奇的代码
标签：AtCoder,cout,Beginner,int,LL,cin,using,_##,282 From： https://www.cnblogs.com/Lanly/p/16990328.html