A – Divisible (abc347 A)
题目大意
给定(n)个数(a_i)以及(k),输出是 (k)的倍数的(a_i)整除以 (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, k;
cin >> n >> k;
while (n--) {
int a;
cin >> a;
if (a % k == 0)
cout
B – Substring (abc347 B)
题目大意
给定字符串(s),问子串种类数。
解题思路
(|s|)只有 (100),直接 (O(n^2))枚举子串丢进 (set)里,答案就是 (set)的大小。
长度大的话得后缀自动机。
神奇的代码
#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;
set ans;
for (int i = 0; i
C – Ideal Holidays (abc347 C)
题目大意
一周前(a)天假期,后 (b)天工作日。
给定 (n)天的安排,问第一个安排定在哪天,使得每个安排都在假期。
解题思路
先让安排日期对(a+b)取模,剩下的问题就是, ([0,a+b-1])数轴上有一堆点,问能否有一个长度为 (a)的区间覆盖了所有点。
枚举覆盖的左端点,看与最右边的点的距离是否超过 (a)即可。
注意计算(a+b+d_i)会超 (int)范围。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
LL n, a, b;
cin >> n >> a >> b;
LL tot = a + b;
vector d;
for (int i = 0; i > x;
--x;
x %= tot;
d.push_back(x);
d.push_back(x + tot);
}
ranges::sort(d);
LL dis = numeric_limits::max();
for (int i = 0; i
D – Popcount and XOR (abc347 D)
题目大意
给定(a,b,c),输出一对 (x,y),满足:
- (x
- (popcount(x) = a)
- (popcount(y) = b)
- (x oplus y = c)
(popcount(x))即返回 (x)在二进制下(1)的个数。 (oplus)是异或。
解题思路
构造题。
假设(c)在二进制下 (1)的个数为 (cnt)。
那么这 (cnt)个 (1)要分配在 (x,y)里。假设分配了 (l)个 (1)给 (x), (r)个 (1)给 (y),其中 (l+r=cnt)。
此时 (x)还剩下 (a-l)个 (1), (y)还剩下 (b-r)个 (1)要分配,这些 (1)的分配需要在 (oplus)时抵消掉。
所以应有 (a-l=b-r)。结合 (l+r=cnt)可以解得 (l,r)值。
即 (over=frac{a+b-cnt}{2})是分配给(x,y)的 (1),以在 (oplus)时抵消。
剩下的(a-over)和 (b-over)是分配给 (x,y),以凑成 (c)。
因此就逐位遍历 (c),如果是 (1),则分配给 (x)或 (y)(看(a,b > 0)),如果是 (0),则都分配给 (x,y)(如果 (over > 0))。
至于无解条件,一个是 (a+b ,一个是 (a+b-cnt)不是偶数,还有的情况难以言说,比如 (a=60,b=60,cnt=60),因为限定了(x ,没有多余的位置分配给用于抵消的 (1)。所以就最后再判断一下构造出来符不符合要求。
神奇的代码
#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;
LL c;
cin >> a >> b >> c;
int aa = a, bb = b;
auto popcount = [](LL x) {
int ret = 0;
while (x) {
ret += x & 1;
x >>= 1;
}
return ret;
};
int cc = popcount(c);
if (cc > a + b || ((a + b - cc) & 1)) {
cout
E – Set Add Query (abc347 E)
题目大意
初始(n)个 (0)的数组(a_i)和空集合(s)。进行以下 (q)次操作。
每次操作给定一个 (x),
- 如果 (x)在集合里,移除它,否则放入它。
- 对于(j in s),(a_j += |s|)
解题思路
朴素的模拟的复杂度是(O(nq)),考虑在这个过程,每个操作后,都要遍历一下集合里的元素,给数组(a)的对应位置相加。
当一个数(x)在集合 (s)里时,每个操作之后都会对 (a_x)作贡献,直到它被移除集合。
每次操作都计算贡献的话,就是朴素的模拟,复杂度上限就是 (O(nq))。要优化,就不能每次操作算贡献了。
注意到一个数 (x)做出的贡献是一个连续的操作区间,贡献值就是这个操作区间的 (|s|)的和。那我们可以维护一个关于操作顺序的 (|s|)的前缀和(presum),当 (x)被移除时,我们就结算它对 (a_x)的贡献:就一个前缀和的相减,这里需要记录下(x)何时放入的。
操作结束后,再对还在(s)里的元素结算下贡献就好了。
神奇的代码
#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 presum;
presum.push_back(0);
set s;
vector la(n, 0);
vector ans(n, 0);
for (int i = 1; i > x;
--x;
if (s.count(x)) {
ans[x] += presum[i - 1] - presum[la[x] - 1];
s.erase(x);
} else {
la[x] = i;
s.insert(x);
}
presum.push_back(presum.back() + s.size());
}
for (auto& i : s) {
ans[i] += presum[q] - presum[la[i] - 1];
}
for (auto& i : ans) {
cout
F – Non-overlapping Squares (abc347 F)
题目大意
给定一个(n times n)的网格,问三个不重叠的 (m times m)的网格覆盖,和的最大值。
解题思路
神奇的代码
G – Grid Coloring 2 (abc347 G)
题目大意
解题思路
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net