A – Leftrightarrow (abc345 A)
题目大意
给定一个字符串,问是不是形如的字符串。
解题思路
根据长度构造出期望的字符串,再判断是否相等即可。
神奇的代码
s = input()
print("Yes" if s == "" else "No")
B – Integer Division Returns (abc345 B)
题目大意
给定(a),输出 (lceil frac{a}{10} rceil)
解题思路
上下取整的转换,(lceil frac{a}{10} rceil = lfloor frac{a + 9}{10} rfloor)。用下取整即可。
Python
的//
是下取证,C++
的 /
是向(0)取整,即正数时是下取整
,负数时是上取整
。
神奇的代码
a = int(input())
print((a + 9) // 10)
C – One Time Swap (abc345 C)
题目大意
给定一个字符串(s),长度为(n),问交换任意两个字符,可以得到的不同字符串个数。
解题思路
注意到交换的两个字符(s_i neq s_j)不相同的话,得到的一定是个新的字符串,并且没有其他交换方式得到这个字符串。
而(s_i == s_j)时,则字符串不变。
因此, 可以 总情况数-字符串不变数
,总情况数
即为(frac{n(n-1)}{2}),字符串不变数
则是((i,j))满足 (s_i==s_j, i 的个数,这是一个经典计数问题,维护(s_i)的出现次数即可(O(n))求得。
最后特别注意一下原字符串(s)是否会出现,即有两个字母相同就会出现。
当然也可以正向统计。
神奇的代码
#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;
array cnt = {0};
LL n = 1ll * s.size() * (s.size() - 1) / 2;
for (auto c : s) {
n -= cnt[c - 'a'];
cnt[c - 'a']++;
}
if (ranges::max(cnt) > 1)
++n;
cout
D – Tiling (abc345 D)
题目大意
给定一个网格,有(k)块矩形板,问是否能选若干块板,恰好铺满网格,板可旋转。
解题思路
只有(7)块板,网格大小只有 (10 times 10),范围比较小,可以直接搜索。
如何搜索呢?起初考虑每块板放在何处,这个复杂度比较大。
从左上考虑,没被覆盖的第一个格子一定是某块板的左上角,因此从左到右,从上到下,找到没被覆盖的第一个格子,枚举其被哪块板覆盖即可。
复杂度感性理解下不会很大
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, h, w;
cin >> n >> h >> w;
vector> a(n);
for (auto& i : a) {
cin >> i[0] >> i[1];
}
vector> full(h, vector(w, 0));
auto set_full = [&](int i, int j, int k, int v) {
for (int x = 0; x bool {
if (i + a[k][0] > h || j + a[k][1] > w)
return false;
for (int x = 0; x pair {
for (int i = 0; i used(n, 0);
auto dfs = [&](auto self, int x, int y) -> bool {
if (x == -1 && y == -1)
return true;
for (int i = 0; i
E – Colorful Subsequence (abc345 E)
题目大意
(n)个球排成一排,球有颜色(c_i),有价值(v_i)。
现需恰好移除 (l)个球,使得俩俩球颜色不同,且剩下的球的价值和最大。问最大值。
解题思路
按顺序考虑每个球,我们的决策就是是否移除这个球。考虑我们需要哪些状态。
首先肯定是前(i)个球这个基本状态。由于要恰好移除 (l)个球,因此当前已经移除的球数也必须知道。
除此之外,对于当前球移除或不移除,还取决于上一个球的颜色,因为不能有相邻两个相同的颜色的球。
据此可以有两种 (dp)方式,一种朴素的是 (dp[i][j][k])表示前 (i)个球,已经移除了 (j)个,且最后一个球的颜色是 (k)时的剩余球最大价值和。这样对于当前球移除与否都能转移。初见这个(dp)感觉时间复杂度是(O(n^3k)),但细想转移的话可见是 (O(n^2k))。
还有一种方式为 (dp[i][j]) 表示前(i)个球,且我保留第 (i)个球,并且已经移除了 (j)个球的最大价值和,转移就枚举上一个保留的球的下标,其时间复杂度是 (O(nk^2))。
由于 (n)有 (10^5), (k)有 (500),两者的时间复杂度都太高了。思考如何优化,事实上最后这两种方式都可以优化到 (O(nk))。
先考虑第一种 (dp)方式的转移式子:
]
其中(1 leq k_1, k leq n)表示颜色,且 (k_1 neq k)。虽然这里是(O(n^3k)),但考虑到,如果保留球,实际上只有一个(dp[i][j][k])会改动,需要遍历(dp[i-1][j][k_1]),如果不保留球,则直接 (dp[i][j][k] = dp[i – 1][j – 1][k]) ,转移是(O(1)),只有一个状态转移是 (O(n))。所以总的是(O(n^2k))。
两大项的最大值分别对应着保留球
和移除球
这两种决策。其中保留球
的决策中,需额外条件(k_1 neq k),即上一个球颜色不与当前球颜色相同。而 移除球
的决策中,就一个值而已。
考虑如何优化转移,初看其实感觉很难优化,因为状态数就已经是(O(n^2k)),优化转移的同时刚好可以把状态数优化到(O(nk))。
对于后者转移,其就一项,转移就(O(1)),无需过多考虑。
对于前者转移,如果没有(k neq k_1)的条件,我维护(dp[i-1][j][…])的最值,那转移就不需要遍历 (k_1),通过维护的最值可以(O(1))转移,就是在求 (dp[i-1][j][…])的每一项时,就可以维护 (mx[i-1][j] = max(dp[i-1][j][…]))。
棘手的就是(k_1 neq k)这个条件,就是要求(dp[i-1][j][…])除 (dp[i-1][j][k])这一项的最值。
如何处理这个条件呢?事实上我们除了维护最大值
,再维护一个次大值
,这两个的颜色一定是不同的,那转移时,一定就是从这两个选一个出来转移。
即维护(mx[i-1][j] = [[MAX1, color], [MAX2, color]]),这样,我每个(dp[i][j][k])从可以从 (mx[i-1][j])中(O(1))找到原转移式里的 (max(dp[i-1][j][k_1]))这一项 ,得以转移。
转移式变为(dp[i][j][k] = max(mx[i – 1][j][0] + v_i, mx[i – 1][j][1] + v_i, dp[i – 1][j – 1][k])) ,其中(mx)那部分要判断颜色是否不同((c_i neq color))。最后的答案即为(max(dp[n][l][…])),或者说是 (mx[n][l][0])。
但至此,只是将一个转移从(O(n))降到了 (O(1)),但状态数还是(O(n^2k)),降不下来 ,怎么办呢?
注意到状态里的(k),当初之所以定义(k)这个状态,是因为转移时要避免出现相邻球颜色相同(即能够转移),事实上这个状态非常冗余,它的用途只是为了转移,最后求解答案时不需要该状态(即对该状态的所有取值取个最值,而不关心具体是什么),观察上述的转移式,会发现这个(k)已经没有用了, 保留球
的话转移从(mx)来就可以了,移除球的话,最终能成为(mx[i][j])里的情况,也必定是 (mx[i-1][j-1])里的最大值或次大值。
换句话说,这个 (k)的状态其实可以砍掉(就变成了 (mx)了),即 (mx[i][j])表示前 (i)个球,移除 (j)个球后的两个两元组
,分别表示(最大价值和,最后一个球的颜色)
和 (次大价值和,最后一个球的颜色)
。转移时同样考虑当前球保留或移除,保留的话,则从(mx[i-1][j][0] + v to mx[i][j])或 (mx[i-1][j][1] + v to mx[i][j]) (看哪个颜色不同),移除的话就(mx[i-1][j-1][0] to mx[i][j])和 (mx[i-1][j-1][1] to mx[i][j]),这样就维护出 (mx[i][j])的最大值和次大值,可以转移了。
由于每个(mx[i][j])的转移都是依赖上一个(mx[i-1]),这里也可以滚动数组优化下。
最后的时间复杂度是 (O(nk))。
神奇的代码
#include
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
vector, 2>> dp(k + 1, {{{-inf, -1}, {-inf, -1}}});
dp[0][0] = {0, 0};
auto update = [&](array, 2>& a, pair b) {
if (b.first > a[0].first) {
swap(a[0], b);
}
if (b.second != a[0].second && b.first > a[1].first) {
swap(a[1], b);
}
};
for (int i = 0; i > c >> v;
vector, 2>> dp2(k + 1, {{{-inf, -1}, {-inf, -1}}});
for (int j = 0; j 0) {
update(dp2[j], dp[j - 1][0]);
update(dp2[j], dp[j - 1][1]);
}
}
dp.swap(dp2);
}
cout
还有另一种方式为 (dp[i][j]) 表示前(i)个球,且我保留第 (i)个球,并且已经移除了 (j)个球的最大价值和,转移就枚举上一个保留的球的下标,期间的球就被移除掉。其时间复杂度是 (O(nk^2)),其中状态数(O(nk)),转移耗时 (O(k))。
即转移式(dp[i][j] = max(dp[i – k – 1][j – k]) + v_i, c_i neq c_{i – k – 1})
考虑如何优化转移。观察转移式,转移枚举的是(0 leq k leq l),将 (dp[i][j])看作是一个二元函数的话,那一系列 ((i-k-1, j – k))点构成的是一条斜线,注意到这条斜线的特征是(i-k-1-(j-k)=i-j-1)是个定值。也就是说转移实际上就是在一条斜线取最值,但仍有 (c_i neq c_{i-k-1})这一棘手的条件。
对于这一棘手条件,处理的方法同上述一样,我们维护一条斜线的最大值和次大值。即(mx[o])表示当前状态下, 满足(i-j-1=o)的这条斜线的(dp[i][j])的最大值和次大值及其颜色,每个 (dp[i][j])都从 (mx[i-j-1])中得到颜色不相同的最值即可。这样转移就变为 (O(1))了。
代码里是将(mx[o])压成一个数,即我们的枚举顺序不是朴素的(dp[i][0],dp[i][1],dp[i][2]…),而是一条条斜线,即 (dp[i][0],dp[i+1][1],dp[i+2][2],…,dp[i+1][0],dp[i+2][1]…),当求完一条斜线的所有值时,再求下一条斜线。这样的话就不用保留其他斜线的最值信息,当需要的时候才算。朴素枚举顺序实际上是依次求每条斜线的每个点,所以需要保留历史信息,而当依次求完每条斜线时,就不需要保留其他斜线的信息了。
神奇的代码
#include
using namespace std;
using LL = long long;
const LL inf = 1e18 + 7;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
vector c(n + 2), v(n + 2);
for (int i = 1; i > c[i] >> v[i];
}
c[n + 1] = n + 1;
n += 2;
vector> dp(n, vector(k + 1, -1));
dp[0][0] = 0;
for (int i = 1; i , 2> mx{{{-inf, -1}, {-inf, -1}}};
for (int j = 0; j la = {dp[i + j - 1][j], c[i + j - 1]};
if (la.first > mx[0].first)
swap(la, mx[0]);
if (la.second != mx[0].second && la.first > mx[1].first)
swap(la, mx[1]);
dp[i + j][j] = mx[c[i + j] == mx[0].second].first + v[i + j];
}
}
cout
F – Many Lamps (abc345 F)
题目大意
给定一张图,点上有灯,初始灯灭。
选择一条边,边上的两点的灯的状态会反转。
给出一种边的选择方案,使得恰好有(k)盏灯亮。
解题思路
是个构造题。初看这张图感觉无从下手,因为构造题一般要按照某种顺序执行,但图基本没有什么顺序可言。
可以在更简化的图考虑,比如图的(DFS)树,或者是生成树。
考虑在图的一棵生成树上,会发现有一种构造方法,可以使得根之外,其他点上的灯都能控制亮或灭。
从下往上,叶子到根考虑每个点,如果该点灯灭,则可以选择其父亲边,使其灯亮,或者灯亮变灯灭。
即每个点,都可以通过其父亲边使得它亮或灭,除了根节点之外,这个灯能亮能灭,全凭其点的度数是奇是偶。即一个连通块,除了个点之外,我能保证让其余点都灯亮。
注意到每选择一条边,要么两灯亮,要么两灯灭,要么一亮一灭,即亮灯数量始终是偶数。因此(k)是奇数的情况无解。
否则,注意原图不一定连通,则对于每个连通块,通过(DFS)从叶子考虑,尽量开满所有的灯,直到达到(k)盏灯为止,多开了就灭。
神奇的代码
#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, k;
cin >> n >> m >> k;
vector>> edge(n);
vector du(n, 0);
for (int i = 0; i > u >> v;
--u, --v;
edge[u].push_back({v, i + 1});
edge[v].push_back({u, i + 1});
}
if (k & 1) {
cout vis(n, 0);
vector ans;
function dfs = [&](int u, int fa, int fa_id) {
debug(u, fa, fa_id);
int cnt = 0;
vis[u] = 1;
for (auto& [v, id] : edge[u]) {
if (vis[v] == 0) {
dfs(v, u, id);
}
}
if (du[u] & 1) {
--k;
}
if (u != fa) {
if (k > 0 && (~du[u] & 1)) {
ans.push_back(fa_id);
--k;
du[u]++;
du[fa]++;
} else if (k
G – Sugoroku 5 (abc345 G)
题目大意
扔骰子,([1,k])等概率出现。
对于每个 (i in [1,n]),问扔(i)次骰子后,其和 (geq n)的概率。
解题思路
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net