Codeforces Round 911 (Div. 2)
A - Cover in Water
解题思路:
如果存在三个以上相邻的格子需要填，那么答案为二，否则有多少空格答案为多少。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
int cnt = 0;
ll ans = 0;
bool f = false;
for (auto c : s)
{
if (c == '.')
{
cnt++;
}
else
{
if (cnt == 1)
{
ans += 1;
}
else if (cnt == 2)
{
ans += 2;
}
else if (cnt > 2)
{
ans = 2;
f = true;
break;
}
cnt = 0;
}
}
if (!f)
{
if (cnt == 1)
{
ans += 1;
}
else if (cnt == 2)
{
ans += 2;
}
else if (cnt > 2)
{
ans = 2;
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Laura and Operations
解题思路:
有\(a,b,c\),假设我们要探讨\(a\)所代表的数能否有留存。
\(b,c\)中较大数减去较小数，较小数化为0。设留存数为\(d\).
此时，我们有\(a,d\)，若\(d\)为奇数，那么无论无论如何也化不完。否则就可以。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
bool check(int a, int b, int c)
{
if (b >= c)
{
a += c;
b -= c;
c = 0;
if (b == 0)
{
return true;
}
else
{
if (b & 1)
{
return false;
}
else
{
if (a > 0)
{
return true;
}
return false;
}
}
}
else
{
a += b;
c -= b;
b = 0;
if (c == 0)
{
return true;
}
else
{
if (c & 1)
{
return false;
}
else
{
if (a > 0)
{
return true;
}
return false;
}
}
}
}
void solve()
{
int a, b, c;
cin >> a >> b >> c;
int fa = check(a, b, c);
int fb = check(b, a, c);
int fc = check(c, a, b);
cout << fa << ' ' << fb << ' ' << fc << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Anji's Binary Tree
解题思路:
一次\(dfs\)即可。我们找到从根节点到叶子结点的最小需要修改路径即可。
路径中，若非叶子结点为\(U\),那么一定要修改。
走左儿子时，如果结点标记为\(R\)要修改，走右儿子同理。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
s = ' ' + s;
vector<int> l(n + 1), r(n + 1);
vector<bool> leaf(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> l[i] >> r[i];
if (l[i] == 0 && r[i] == 0)
{
leaf[i] = true;
}
}
ll ans = 1e9;
ll cur = 0;
auto dfs = [&](auto self, int u) -> void
{
// cout << u << endl;
if (leaf[u])
{
ans = min(ans, cur);
return;
}
if (s[u] == 'U')
{
cur++;
}
if (l[u] > 0)
{
if (s[u] == 'R')
{
cur++;
}
self(self, l[u]);
if (s[u] == 'R')
{
cur--;
}
}
if (s[u] == 'U')
{
cur--;
}
if (s[u] == 'U')
{
cur++;
}
if (r[u] > 0)
{
if (s[u] == 'L')
{
cur++;
}
self(self, r[u]);
if (s[u] == 'L')
{
cur--;
}
}
if (s[u] == 'U')
{
cur--;
}
};
// cout << 1 << endl;
dfs(dfs, 1);
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Small GCD
解题思路:
根据式子，不难看出就是遍历三元组全集，所以顺序无关，直接排序同样遍历三元组全集即可。
对排序后的数组取三元组\((a[i],a[j],a[k]),(i < j <k)\)，所以\(a[i] \leq a[j] \leq a[k]\)。那么\((a[i],a[j])\)能够做出贡献的次数为\(n - j\)。
如上，按升序遍历每个元素的因子，记录\(f[i]\)。
\(f[i]:最大公因数为i的倍数的数对数量\)。
\(c[x]:为枚举到当前，所有元素中因子x出现的次数\).由于\(c[x]\)的系数随着遍历位置而改变，所以我们边累计\(f[x]\)边更新\(c[x]\)。
\(f[x] = \sum_{i = 1}^{n}(c_i[x] * (n - i))\)。
然后，经典容斥更新\(f[i]\)得到新\(f[i]\)。
\(f[i]:最大公因数恰好为i的数对数量\).
设\(ans[i]:最大公因数恰好为i的数对数量\)。\(maxval 为值域最大值\)。
\(ans[i] = f[i] - ans[2 * i] - ans[3 * i] - ... -ans[k * i],((k + 1) * i > maxval)\)。
最终答案为\(\sum_{i= 1}^{maxval}(f[i] *i)\)
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
vector<int> b[N];
void solve()
{
int n;
cin >> n;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a.begin() + 1, a.end());
vector<ll> c(1e5 + 10);
// 枚举每个a[i]的因子,计算最大公因数为x的倍数的数对数量
// f[i]:最大公因数为i的倍数的数对数量
vector<ll> f(1e5 + 10, 0);
for (int i = 1; i <= n; i++)
{
for (auto x : b[a[i]])
{
// 此处a[i]为三元组中第二大的数，数组经过排序
// 所以能组成的合法三元组为(n - i)个
f[x] += c[x] * (n - i);
// 边计数边累加
c[x]++;
}
}
// 经典容斥求得 f[i] : 最大公因数恰好为i的数对数量
ll ans = 0;
for (int i = 1e5; i; i--)
{
for (int j = i * 2; j <= 1e5; j += i)
{
f[i] -= f[j];
}
// 每个数对的贡献值就是i
ans += f[i] * i;
}
// cout << 1 << endl;
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
// 筛出j的所有因子
for (int i = 1; i <= N - 5; i++)
{
for (int j = i; j <= N - 5; j += i)
{
b[j].push_back(i);
}
}
// cout << 1 << endl;
while (t--)
{
solve();
}
return 0;
}