A – Past ABCs (abc350 A)
题目大意
给定一个形如 ABCXXX
的字符串。
问XXX
是否是(001 to 349)之间,且不能是 (316)。
解题思路
将后三位转换成数字后判断即可。
神奇的代码
a = int(input().strip()[3:])
if a >= 1 and a
B – Dentist Aoki (abc350 B)
题目大意
给定(n)个 (01)序列。
进行(q)次操作,每次操作反转某一位上的 (01)。
问最后 (1)的个数。
解题思路
反转操作的复杂度是(O(1)),因此直接模拟反转即可,最后求和得到答案。
神奇的代码
#include
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 a(n, 1);
while (q--) {
int x;
cin >> x;
--x;
a[x] ^= 1;
}
int ans = accumulate(a.begin(), a.end(), 0);
cout
C – Sort (abc350 C)
题目大意
给定一个(1 to n)的排序,通过最多(n-1)次操作以下操作将其变得有序。
操作为,交换任意两个数。
输出任意可行的操作次数及其对应的操作步骤。
解题思路
从(i = 1 to n),依次考虑将 (i)交换到第 (i)位。经过 (n-1)次操作后则必定有序。
因此需要记录 (pos[i])表示数字 (i)所在的位置,每次交换第(i, pos[i]) 位,就将(i)交换到第 (i)位,重复执行(n-1)次即可。
神奇的代码
#include
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 pos(n);
vector a(n);
for (int i = 0; i > x;
--x;
pos[x] = i;
a[i] = x;
}
vector> ans;
for (int i = 0; i
D – New Friends (abc350 D)
题目大意
给定一张无向图,若三点(x,y,z),存在:
- (x,y)有连边
- (y,z)有连边
- (x,z)无连边
则连边(x,z)。
问最多能连多少次边。
解题思路
考虑最简单的一条链的情况(1 to 2 to 3 to 4),容易发现可以连的边有
- (1 to 2, 2 to 3) => (1 to 3)
- (1 to 3, 3 to 4) => (1 to 4)
- (2 to 3, 3 to 4) => (2 to 4)
观察(1)的新增边的情况,会发现它可以和所有能到达的点连边,即最终情况下,一个连通块内的任意两点都会连边,即变成一张完全图。
因此(BFS)得到每个连通块的点数 (cp)和边数 (ce),最终情况下该连通块会有 (frac{cp * (cp – 1)}{2}) 条边,而已经有(ce)条(无向)边,因此可以连 (frac{cp * (cp – 1)}{2} – ce)条边。
所有连通块的连边次数相加即为答案。
神奇的代码
#include
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> edge(n);
for (int i = 0; i > u >> v;
--u, --v;
edge[u].push_back(v);
edge[v].push_back(u);
}
LL ans = 0;
vector vis(n, 0);
for (int i = 0; i team;
team.push(i);
vis[i] = 1;
int cp = 1, ce = 0;
while (!team.empty()) {
int u = team.front();
team.pop();
for (auto v : edge[u]) {
++ce;
if (vis[v])
continue;
vis[v] = 1;
team.push(v);
cp++;
}
}
ans += 1ll * cp * (cp - 1) - ce;
}
ans /= 2;
cout
E – Toward 0 (abc350 E)
题目大意
给定一个数字(n),(x,y,a)。通过两类操作,使得(n)变为 (0)。
- 操作一,花费代价(x),使得 (n = lfloor frac{n}{a} rfloor)
- 操作二,花费代价(y),掷骰子,等概率掷出(1 to 6)中的一个(b),使得 (n = lfloor frac{n}{b} rfloor)
问最优情况下,最小期望花费。
解题思路
期望题,根据定义,当前的期望值是所有后继情况的期望值的概率加权。
设(dp[i])表示当前数字为 (x),将其变为 (0)的最小期望花费。
边界条件很明显就是 (dp[0] = 0)。
虽然是期望,但它问的是最优情况下的最小花费,那就是一个决策最优问题,考虑我的决策是什么。
很显然,决策就是操作一还是操作二,如果我决定执行操作一,会有一个期望值,执行操作二,会有另一个期望值,这两个期望值取最小,就是我做出的最优决策。因此需要分别求出操作一和操作二的期望花费。
根据定义,当前的期望值是所有后继情况的期望值的概率加权。
当我执行操作一后,后继情况只有一个,那就是(dp[ lfloor frac{n}{a} rfloor ]),达到这个情况的概率是 (1)。因此操作一的期望花费(cost1 = dp[ lfloor frac{n}{a} rfloor ] + x)。
当我执行操作二后,后继情况有(6)个:
- (dp[ lfloor frac{n}{1} rfloor ])
- (dp[ lfloor frac{n}{2} rfloor ])
- (dp[ lfloor frac{n}{3} rfloor ])
- (dp[ lfloor frac{n}{4} rfloor ])
- (dp[ lfloor frac{n}{5} rfloor ])
- (dp[ lfloor frac{n}{6} rfloor ])
到达每一个后继情况的概率都是(frac{1}{6})。
根据期望定义,可以得到操作二的期望花费 (dp[n] = frac{sum_{i=1}^{6} dp[ lfloor frac{n}{i} rfloor ]}{6} + y)
但注意到(i=1)那一项是 (dp[n]),与左式是一样的,这会造成循环求值,这里我们将右边的 (dp[n]) 移到左边,合并同类项,就可以得到真正的(cost2 = frac{sum_{i=2}^{6} dp[ lfloor frac{n}{i} rfloor ]}{5} + frac{6}{5}y)
得到两个操作的期望花费(cost1,cost2)后,接下来就是做决策——取花费最小的,作为 (dp[n])的值。这样是转移了。
虽然 (n)有 (O(10^{18})),但由于每次都至少(/2),最多除以 (log)次就变成 (0),总的状态数其实很少,只有(O(log_2 * log_3 * log_4 * log_5 * log_6)),大概就(4e7)的数量级。
从上面的分析可以看出,期望(dp)和(dp)之间的区别仅仅是计算转移代价时需要用到期望定义来算,最终还是根据不同操作之间的代价取最优,还是个决策问题。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
LL n;
int a, x, y;
cin >> n >> a >> x >> y;
map dp;
auto dfs = [&](auto dfs, LL u) -> double {
if (u == 0)
return 0.;
if (dp.find(u) != dp.end())
return dp[u];
double cost1 = dfs(dfs, u / a) + x;
double cost2 = 0;
for (int i = 2; i
F – Transpose (abc350 F)
题目大意
给定一个括号序列(s),长度为(n),其中也包括大小写字母。
依次处理每个匹配的括号里的字符,将其左右颠倒,并将大小写字母变换。
问最终的字符串。
解题思路
考虑朴素的做法,进行括号匹配,然后处理括号内的字符串,容易发现最坏情况下复杂度是(O(n^2)),比如((((((((((asjigjiogjwifjwefckfj))))))))))
。
注意到同一个字符块执行两次上述变换后相当于没变换,从上述的最坏情况下可以启示我们,我们不需要实际进行变换,仅仅将这一块字符串看作整体,然后打个标记。就跟线段树的懒标记差不多。
比如(((as)(sf))(ef))
,我们先将每一块字符串看作整体,从 (0)开始标号,则变为(((0)(1))(2))
,然后处理每对匹配的括号,比如变成了((34)(2))
,然后处理 (34)
,这里我们就不给34
重复打标记,因为那样的复杂度可能会变回原来的(O(n^2)),而是将 (34)看成一个整体 (5),在(5)上打标记,最后输出时再传递给 (34)。变成 (5(2))
,然后是(56)
,然后是7
。
就跟线段树的思想一样,我们会发现(34 to 5, 2 to 6, 56 to 7),它们的关系形成了一棵树的关系(但可能不是二叉树),然后打标记都是在父亲节点打标记,最后输出时,从根节点开始遍历,不断下放标记,下放到叶子时,再根据标记决定是否倒序输出即可。
神奇的代码
#include
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;
s = "(" + s + ")";
vector info;
info.push_back("(");
info.push_back(")");
string t;
vector tr;
for (auto& i : s) {
if (i == '(' || i == ')') {
if (!t.empty()) {
tr.push_back(info.size());
info.push_back(t);
}
t.clear();
if (i == '(')
tr.push_back(0);
else
tr.push_back(1);
} else
t += i;
}
vector> edge(info.size());
stack st;
for (auto i : tr) {
if (i == 0) { // (
st.push(0);
} else if (i == 1) { // )
int fa = info.size();
info.push_back("");
edge.push_back(vector());
while (!st.empty() && st.top() != 0) {
edge[fa].push_back(st.top());
st.pop();
}
st.pop();
st.push(fa);
} else {
st.push(i);
}
}
auto inverse = [](string& s) {
reverse(s.begin(), s.end());
for (auto& i : s) {
if (islower(i))
i = toupper(i);
else
i = tolower(i);
}
};
auto dfs = [&](auto dfs, int u, int d) -> void {
if (edge[u].empty()) { // leaf
if (d)
inverse(info[u]);
cout
G – Mediator (abc350 G)
题目大意
给定(n)个点,执行下列 (q)次操作,分两种,强制在线。
-
1 u v
,连无向边(u to v),连边之前保证(u,v)不连通。 -
2 u v
,询问是否有一个点(x),使得(u to x to v)。
解题思路
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net