A – Adjacent Product (abc346 A)
题目大意
给定(n)个数,依次输出相邻俩数的乘积。
解题思路
按照题意模拟即可。
神奇的代码
#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;
int la = 0;
cin >> la;
for (int i = 1; i > a;
cout
B – Piano (abc346 B)
题目大意
给定一个由wbwbwwbwbwbw
无限拼接的字符串。
给定(w,b),问是否由一个子串,其有 (w)个 w
, (b)个 b
解题思路
考虑枚举子串的起点,其实只有(len(wbwbwwbwbwbw)=12)种情况。
枚举起点后,统计其后的(w+b)个字符,看看是否满足上述需求即可。
时间复杂度是 (O(12(w+b)))
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s = "wbwbwwbwbwbw";
int w, b;
cin >> w >> b;
int len = w + b;
bool ok = false;
for (int i = 0; i cc;
for (int j = i, cnt = 0; cnt
C – Σ (abc346 C)
题目大意
给定(n)个数 (a_i)。
问 (1 sim k)中,不是 (a_i)的数的和。
解题思路
先计算(sum_{i=1}{k}i = frac{k(k+1)}{2}),然后减去 (a_i)中出现过的数即可。注意要对 (a_i)去重,可以先 (sort)再 (unique),或者直接丢到 (set)里。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
vector a(n);
for (auto& i : a)
cin >> i;
LL ans = 1ll * k * (k + 1) / 2;
for (auto& i : set(a.begin(), a.end())) {
if (i
D – Gomamayo Sequence (abc346 D)
题目大意
给定一个(01)字符串(s),对第 (i)位翻转需要 (c_i)的代价。
定义一个好的字符串,当且仅当只有一个相邻位置上的数字是相同的。
问将字符串变成好的字符串的最小代价。
解题思路
注意到好的字符串的情况数只有(O(n))个,其中 (n)是串 (s)的长度。因此我们可以枚举所有情况。
枚举相邻数字相同的位置
,然后计算变成 (010101…..)和 (101010…)这两种情况的代价,所有位置情况代价取最小值即为答案。
如何快速计算代价?考虑到由相邻数字相同的位置
左右分割开来的都是固定的(010101)或 (101010),因此事先预处理所有前缀和后缀变换成 (010101)和 (101010)的代价后,通过前缀代价+后缀代价,就可以(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;
string s;
cin >> n >> s;
vector c(n);
for (auto& i : c)
cin >> i;
vector> pre(n + 1), suff(n + 1);
const string expect = "01";
for (int i = 0; i 0 ? pre[i - 1][0] : 0);
pre[i][1] =
(s[i] == expect[~i & 1] ? c[i] : 0) + (i > 0 ? pre[i - 1][1] : 0);
}
for (int i = n - 1; i >= 0; --i) {
suff[i][0] = (s[i] == expect[i & 1] ? c[i] : 0) +
(i
E – Paint (abc346 E)
题目大意
(h times w)的平面,格子初始全为颜色 (0)。
依次进行 (m)次操作,每次操作将某一行或某一列的格子涂成颜色 (x_i)。
问最后各个颜色的格子数量。
解题思路
朴素的想法,最后统计每块格子的颜色,时间复杂度避免不了为为(O(hw))。
考虑到每次操作都是对一行或一列涂色,其涂的格子数是已知的,所以可以直接累计结果。
但这样的问题是,后面的操作会影响到前面的结果,颜色会覆盖,导致先前涂的颜色数量可能会减少。
注意到后面的操作会覆盖前面的操作,如果我们对操作反过来考虑,先考虑最后一次操作,再考虑前一个操作,那么后考虑的操作不会影响先考虑的操作,就不会出现上面的先前涂的颜色会减少的问题。
因此我们对操作倒过来考虑,每次操作所涂的格子数。格子数的求法比较简单,比如一次操作对某一行涂色,其涂得格子数为(w-)已经涂过的列操作数。维护一下已经涂过的列和行数量即可。当然还要维护某一列和某一行是否被涂过,后涂的操作是无效的。
神奇的代码
#include
using namespace std;
using LL = long long;
const int up = 2e5 + 8;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w, m;
cin >> h >> w >> m;
vector> op(m);
for (auto& [t, a, x] : op) {
cin >> t >> a >> x;
--a;
}
vector cnt(up, 0);
vector used_row(h, 0);
vector used_col(w, 0);
int row = h, col = w;
reverse(op.begin(), op.end());
for (auto& [t, a, x] : op) {
if (t == 1) {
if (used_row[a])
continue;
used_row[a] = 1;
--row;
cnt[x] += col;
} else {
if (used_col[a])
continue;
used_col[a] = 1;
--col;
cnt[x] += row;
}
}
cnt[0] += 1ll * h * w - accumulate(cnt.begin(), cnt.end(), 0ll);
vector> ans;
for (int i = 0; i
F – SSttrriinngg in StringString (abc346 F)
题目大意
给定两个字符串(s,t),定义 (f(s,n))表示将字符串 (s)重复拼接 (n)次。 (g(t,k))表示将 (t)的每个字符重复 (k)次得到。
给定 (n),问最大的 (k),使得 (g(t,k))是 (f(s,n))的子序列。
解题思路
(k)越小越好满足, (k)越大越难满足是子序列,容易发现(k)与 是否是子序列
具有单调性,因此二分(k)。
二分(k)后,就按照匹配子序列那样(就近匹配)的暴力匹配 (t)的每个字符即可。只是细节有点多。
匹配 (t)的每个字符时,每个字符(c)有 (k)个,假设 (s)有该字符 (cnt_c)个,那先每 (cnt_c)个 (cnt_c)个匹配,耗掉 (frac{k}{cnt_c})个 (s),然后剩下的 (k % cnt_c)个(c)匹配 新一份的(s)的一部分。此时剩下的 字符就匹配(t)的下一个字符。
因此二分验证时需要维护信息有:
- 当前匹配的是 (t)的第(cur)个字符
- 当前字符还剩下 (left)个要匹配,
- 当前用了 (sum)份(s)
- 当前份正匹配到第(it)个字符。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
LL n;
string s, t;
cin >> n >> s >> t;
vector> pos(26);
for (int i = 0; i cnt) {
left -= cnt;
it = 0;
} else {
it = (pos[c][st + left - 1] + 1) % s.size();
left = 0;
}
}
if (left == 0) {
++cur;
left = x;
}
}
return sum > 1;
if (check(mid))
l = mid;
else
r = mid;
}
cout
G – Alone (abc346 G)
题目大意
给定(n)个数(a_i)。问 ((l,r))的数量,满足(a[l..r])中有数字仅出现一次。
解题思路
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net