A – Wrong Answer (abc343 A)
题目大意
给定(a,b),输出 (c),使得 (a+b neq c)
解题思路
从(0)开始枚举(c)的取值即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int a, b;
cin >> a >> b;
int ans = 0;
while (ans == a + b)
++ans;
cout
B – Adjacency Matrix (abc343 B)
题目大意
给定一个邻接矩阵,对于第(i)个点,输出与之有连边的点的编号,升序。
解题思路
即输出第(i)行中值为 (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;
for (int i = 0; i > x;
if (x)
cout
C – 343 (abc343 C)
题目大意
给定一个数(n),问不超过 (n)的最大的数 (x),其是回文数,且是某个数(y)的三次方。
解题思路
我们可以枚举(y)而不是 (x),这样得到的 (x=y^3)就一定是个三次方数,剩下的就是判断 (x)是不是回文数。
(n)只有 (10^{18}),对应的(y)的范围就只有(10^6),判断回文数的复杂度是 (O(log )),因此直接枚举判断即可。
判断回文数可以直接用 to_string
转换成字符串然后对应位比较。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
LL n;
cin >> n;
int up = 1e6;
LL ans = 0;
for (int i = 1; i n)
break;
string s = to_string(x);
bool ok = true;
int len = s.size();
for (int i = 0; i
D – Diversity of Scores (abc343 D)
题目大意
初始(n)个人都是 (0)分。
第(i)个时刻,第 (a_i)个人分数增加 (b_i) 。
问每个时刻后,不同分数的个数。
解题思路
用map
维护每个数出现的次数,当其次数减为(0)的就删去该元素。
每个时刻的答案就是 map
的元素个数。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, t;
cin >> n >> t;
map cnt;
vector score(n);
cnt[0] = n;
for (int i = 0; i > a >> b;
--a;
cnt[score[a]]--;
if (cnt[score[a]] == 0)
cnt.erase(score[a]);
score[a] += b;
cnt[score[a]]++;
cout
E – 7x7x7 (abc343 E)
题目大意
三维坐标,三个(7 times 7 times 7)的方块放置。
给定 (v1,v2,v3),要求
- 恰好属于一个方块的体积是 (v1)。
- 恰好属于两个方块的体积是 (v2)。
- 恰好属于三个方块的体积是 (v3)。
输出任意一种摆放方式。
解题思路
由于数都不大,考虑直接枚举。
由于空间的平移不变形,第一个方块放置位置可以是((0,0,0))。
考虑枚举第二个和第三个的方块,其坐标范围则是([-7,7])。再远的地方和 (-7,7)的放置效果是一样的。
花(O(2^6 7^6))枚举三个方块位置后,要求(v1,v2,v3),再花(O(2^3 7^3))统计的话总复杂度就是 (10^{10}),会超时了。
考虑 (v3)怎么求,其实这跟求两个线段的交线长度、两个矩形的相交面积一样,分别考虑每一维的交线长度,即右端点的最小值 (-)左端点的最大值,然后三维长度乘起来就是相交体积。
(v2)就是俩俩相交,再减去 (v3)对应的部分。
(v1)就是所有体积加起来,减去 (v2)和 (v3)对应的部分。
这样就可以(O(1))判断,最终的时间复杂度是 (O(2^6 7^6))。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int v1, v2, v3;
cin >> v1 >> v2 >> v3;
array, 3> a;
a[0] = {0, 0, 0};
constexpr int len = 7;
constexpr int sz = 4 * len;
array, sz>, sz> cnt{};
for (int i = 0; i tmp{};
for (auto& i : cnt)
for (auto& j : i)
for (auto& k : j) {
tmp[k]++;
}
return tmp;
};
auto calc3 = [&](int i, int j, int k, int l, int m, int n, int o, int p,
int q) {
int a = max(0, min({i + len, l + len, o + len}) - max({i, l, o}));
int b = max(0, min({j + len, m + len, p + len}) - max({j, m, p}));
int c = max(0, min({k + len, n + len, q + len}) - max({k, n, q}));
return a * b * c;
};
auto calc2 = [&](int i, int j, int k, int l, int m, int n) {
int a = max(0, min(i + len, l + len) - max(i, l));
int b = max(0, min(j + len, m + len) - max(j, m));
int c = max(0, min(k + len, n + len) - max(k, n));
return a * b * c;
};
auto solve = [&]() {
for (int i = -len; i
F – Second Largest Query (abc343 F)
题目大意
(n)个数(a_i), (q)个询问 ,分两种:
-
1 p x
,将(a_p = x) -
2 l r
,问(a_{l..r})的次大值的出现次数,
解题思路
可以考虑带修莫队,但貌似会超时。
注意到次大值的出现次数
这信息是可合并
的,即两个区间的这一信息,可以合并起来,得到更大区间的这一信息。
因此用线段树维护这一信息即可,对应的是单点修改和区间查询。
神奇的代码
#include
using namespace std;
using LL = long long;
const int N = 2e5 + 8;
class segment {
#define lson (root max[N cmax[N , 4> tmp = {max[lson], max[rson], cmax[lson],
cmax[rson]};
map cnt;
for (auto& x : tmp) {
cnt[x[0]] += x[1];
}
max[root] = {cnt.rbegin()->first, cnt.rbegin()->second};
cmax[root] = {0, 0};
cnt.erase(cnt.rbegin()->first);
if (!cnt.empty())
cmax[root] = {cnt.rbegin()->first, cnt.rbegin()->second};
}
array, 2> combine(array, 2> a,
array, 2> b) {
array, 4> tmp = {a[0], a[1], b[0], b[1]};
map cnt;
for (auto& x : tmp) {
cnt[x[0]] += x[1];
}
array, 2> ret;
ret[0] = {cnt.rbegin()->first, cnt.rbegin()->second};
ret[1] = {0, 0};
cnt.erase(cnt.rbegin()->first);
if (!cnt.empty())
ret[1] = {cnt.rbegin()->first, cnt.rbegin()->second};
return ret;
}
void build(int root, int l, int r, vector& a) {
if (l == r) {
max[root] = {a[l - 1], 1};
cmax[root] = {0, 0};
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid, a);
build(rson, mid + 1, r, a);
pushup(root);
}
void update(int root, int l, int r, int pos, int val) {
if (l == r) {
max[root] = {val, 1};
cmax[root] = {0, 0};
return;
}
int mid = (l + r) >> 1;
if (pos , 2> query(int root, int l, int r, int L, int R) {
if (L > 1;
array, 2> lret = {{{0, 0}, {0, 0}}},
rret = {{{0, 0}, {0, 0}}};
if (L mid)
rret = query(rson, mid + 1, r, L, R);
return combine(lret, rret);
}
} sg;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
vector a(n);
for (auto& x : a)
cin >> x;
sg.build(1, 1, n, a);
while (q--) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
sg.update(1, 1, n, x, y);
} else {
auto ret = sg.query(1, 1, n, x, y);
cout
G – Compress Strings (abc343 G)
题目大意
给定(n)个字符串,问最小长度的字符串,使得这 (n)个字符串都是该串的子串。
解题思路
注意到(n)只有 (20)。
考虑最朴素的做法,就是花(O(n!))枚举这(n)个字符串的顺序,然后再把俩俩相邻的字符串中,重复的部分(最长前后缀)删去,得到一个字符串。所有这样的字符串长度取个最小值则为答案,
但还是有点小问题,在原来的(n)个字符串中,对于相同的字符串,我们肯定只保留一个,而对于子串的情况,该子串也不需要。因此得事先预处理,将相同串和子串的都去掉,可以用hash
的方法在(O(n^210^5))内做到。
考虑优化这个朴素做法,容易发现,当确定了前 (i)个字符串的顺序后, 对于第(i+1)个字符串取什么,使得拼接字符串的长度所造成的影响,只取决于第 (i)个字符串是什么,对于前面的字符串的顺序怎样没关系。
因此我们不必保留前 (i)个字符串的顺序 这一信息,只需知道我取了哪些字符串
,且第 (i)个字符串是什么。通过这两个信息,我就可以进行转移:即选择哪个还未取的字符串,以及取了之后最终长度是多少。
因此设(dp[i][j])表示我取的字符串的二进制表示为 (i) ,最后一个字符串是(j)的最小长度。
事先花(O(n^2 10^5))预处理 (cost[i][j])表示字符串 (i)(左)和字符串 (j)(右)拼接起来 后增加的长度(枚举前后缀长度,再hash
判断是否相等)。这样转移时枚举下一个字符串后,就可以(O(1))得到代价。因此转移的复杂度是 (O(n))。
总的时间复杂度是 (O(n^2 2^n))
神奇的代码
#include
using namespace std;
using LL = long long;
typedef long long LL;
typedef unsigned long long ULL;
const int x = 135;
const int N = 2e5 + 10;
const int p1 = 1e9 + 7, p2 = 1e9 + 9;
ULL xp1[N], xp2[N], xp[N];
void init_xp() {
xp1[0] = xp2[0] = xp[0] = 1;
for (int i = 1; i = 0; --j) {
#ifdef ENABLE_DOUBLE_HASH
res1 = (res1 * x + s[j]) % p1;
res2 = (res2 * x + s[j]) % p2;
h[j] = (res1 > 32, right1 = h[right] >> 32;
ULL left2 = h[left] & mask32, right2 = h[right] & mask32;
return (((left1 - right1 * xp1[len] % p1 + p1) % p1) > n;
vector s(n);
for (auto& i : s) {
string x;
cin >> x;
i.init(x.c_str());
i.hash();
}
vector t;
vector sub(n);
for (int i = 0; i s[j].length)
continue;
s[j].get_all_subs_hash(s[i].length);
s[j].sort_substring_hash();
if (s[j].match(s[i].h[0])) {
sub[i] = true;
break;
}
}
if (!sub[i])
t.push_back(s[i]);
}
n = t.size();
int up = (1 > dp(up, vector(n, inf));
dp[0][0] = 0;
auto calc = [&](int i, int j) {
int ans = min(t[i].length, t[j].length);
while (ans > 0 &&
t[i].get_substring_hash(t[i].length - ans, t[i].length) !=
t[j].get_substring_hash(0, ans))
--ans;
return t[j].length - ans;
};
vector> cost(n, vector(n, 0));
for (int i = 0; i
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net