0%

链接

传送门

题意

给出\(n (1 \leq n \leq 2 \cdot 10^5)\)个数,其中\(1 \leq a_i \leq 10^6\),求满足\(1 \leq i,j \leq n,a_i \geq a_j\)最大的\(a_i \bmod a_j\)

思路

很久前的一道题,一直没写题解,今天回想起来,记录一下。 对于每个数\(x\),记录满足\(x > a_i\)最大的\(b_x=a_i\),然后可以枚举每个\(a_j\)的倍数来找到\(b_{k \cdot a_i} \bmod a_j\)的最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 200010;
const int maxm = 2000010;
int a[maxn], b[maxm];

int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
sort(a, a + n);
n = int(unique(a, a + n) - a);
a[n] = maxm;
int p = a[0] + 1;
for (int i = 1; i <= n; ++i) {
while (p <= a[i]) {
b[p++] = a[i - 1];
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = a[i] << 1; j < maxm; j += a[i]) {
ans = max(ans, b[j] - j + a[i]);
}
}
printf("%d\n", ans);
return 0;
}

链接

传送门

题意

有一个\(n \times n\)的矩阵,用红绿蓝其进行染色,求出至少有一列或者一行为同色的染色方案数。

思路

官方题解:Codeforces Round #493 — Editorial

\(A_i\)表示第\(i\)行颜色相同的矩阵数量,\(B_i\)表示第\(i\)列颜色相同的矩阵数量。

那么要求的答案即为\(\left| A_1 \bigcup A_2 \dots A_n \bigcup B_1 \bigcup B_2 \dots B_n \right|\)

更一般的,由于对称性,具体的某一行和某一列并不重要,只需要统计有多少行和列满足同色就可以了。

这样得到\(ans = \sum_{i = 0 \dots n, j = 0 \dots n, i + j > 0}{C_n^iC_n^j (-1)^{i + j + 1}f(i, j)}\)

其中,\(f(i, j)\)表示前\(i\)\(j\)列同色的矩阵个数。

对于\(i=0\)\(j=0\)的情况,\(f(0, k) = f(k, 0) = 3^k \cdot 3^{n(n - k)}\),这部分用朴素的方法求和复杂度为\(O(n)\)

对于其他情况,\(f(i, j) = 3 \cdot 3^{(n - i)(n - j)}\),这部分用朴素的方法求和复杂度为\(O(n^2)\)\(O(n^2\log n)\),因此需要化简。

\[ans = \sum_{i = 1}^n\sum_{j = 1}^nC_n^iC_n^j (-1)^{i + j + 1}3 \cdot 3^{(n - i)(n - j)}\]

\(i\)替换为\(n-i\)\(j\)替换为\(n-j\)

\[ans = 3\sum_{i = 0}^{n - 1}\sum_{j = 0}^{n - 1}C_n^{n - i}C_n^{n - j} (-1)^{n - i + n - j + 1}\cdot 3^{ij}\]

由于\(C_n^{n-i} = C_n^i\)\((-1)^{2n}=1\)\((-1)^{-i}=(-1)^i\),得

\[ans = 3\sum_{i = 0}^{n - 1}\sum_{j = 0}^{n - 1}C_n^iC_n^j(-1)^{i + j + 1}\cdot 3^{ij}\]

由于\((a + b)^n=\sum_{i=0}^nC_n^ia^ib^{n-i}\),作如下变换:

\[ans = 3\sum_{i = 0}^{n - 1}C_n^i (-1)^{i + 1}\sum_{j = 0}^{n - 1} C_n^j(-1)^j\cdot \left(3^i\right)^j\]

\[ans = 3\sum_{i = 0}^{n - 1}C_n^i (-1)^{i + 1} \sum_{j = 0}^{n - 1} C_n^j\left(-3^i\right)^j\]

\[ans = 3\sum_{i = 0}^{n - 1}C_n^i (-1)^{i + 1}\left[\left(1 + \left(-3^i\right) \right)^n - \left(-3^i\right)^n\right]\]

可以在\(O(n)\)的时间内完成计算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 1000010;
const LL mod = 998244353;

LL c[maxn];
LL inv[maxn];
LL pow3[maxn];

LL pow_mod(LL x, LL k) {
LL res = 1, cur = x;
while (k) {
if (k & 1) {
res = res * cur % mod;
}
cur = cur * cur % mod;
k >>= 1;
}
return res;
}

int main() {
int n;
scanf("%d", &n);
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
c[0] = pow3[0] = 1;
for (int i = 1; i <= n; ++i) {
c[i] = c[i - 1] * (n - i + 1) % mod * inv[i] % mod;
pow3[i] = pow3[i - 1] * 3 % mod;
}
LL ans1 = 0;
for (int i = 1; i <= n; ++i) {
LL sig = i & 1 ? 1 : -1;
ans1 = (ans1 + c[i] * sig * pow3[i] % mod * pow_mod(pow3[n], n - i)) % mod;
}
ans1 = ((ans1 + mod) << 1) % mod;
LL ans2 = 0;
for (int i = 0; i < n; ++i) {
LL sig = i & 1 ? 1 : -1;
LL tmp = mod - pow3[i];
ans2 = (ans2 + c[i] * sig * (pow_mod(1 + tmp, n) - pow_mod(tmp, n))) % mod;
}
ans2 = (ans2 + mod) * 3 % mod;
printf("%lld\n", (ans1 + ans2) % mod);
return 0;
}

链接

传送门

题意

给出一个长度为\(n(1 \leq n \leq 2 \cdot 10^5)\)的字符串,进行\(m(1 \leq m \leq 2 \cdot 10^5)\)次删除操作,每个删除操作将删除当前字符串\(l\)\(r\)间所有字符\(c\)。输出\(m\)次操作之后的字符串。

思路

对每种字符都用set存下出现的位置,用树状数组来计算位置\(x\)前有多少个未被删除的字符。对于每次删除操作,利用树状数组将位置\(l\)\(r\)转换为初始字符串中的位置,然后在set中删除并更新字符串和树状数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>

typedef long long LL;

using namespace std;

const int maxn = 200010;
const int maxm = 260;

int n, m;
int bit[maxn];
char str[maxn];
set<int> s[maxm];

inline int lowbit(int& x) {
return x & (-x);
}

int sum(int i) {
int res = 0;
while (i > 0) {
res += bit[i];
i -= lowbit(i);
}
return res;
}

void add(int i, int x) {
while(i <= n){
bit[i] += x;
i += lowbit(i);
}
return;
}

int getPos(int x) {
int L = x, R = n, m = x;
while (L <= R) {
m = (L + R) / 2;
if (sum(m) >= x) {
R = m - 1;
} else {
L = m + 1;
}
}
return L;
}

int main() {
scanf("%d%d", &n, &m);
scanf("%s", str + 1);
for (int i = 1; str[i]; ++i) {
s[str[i]].insert(i);
add(i, 1);
}
int l, r;
char tmp[5];
while (m--) {
scanf("%d%d%s", &l, &r, tmp);
l = getPos(l);
r = getPos(r);
auto lb = s[tmp[0]].lower_bound(l);
auto ub = s[tmp[0]].upper_bound(r);
while (lb != ub) {
add(*lb, -1);
str[*lb] = 0;
++lb;
}
s[tmp[0]].erase(s[tmp[0]].lower_bound(l), ub);
}
for (int i = 1; i <= n; ++i) {
if (str[i]) {
putchar(str[i]);
}
}
puts("");
return 0;
}

链接

传送门

题意

给出\(n\)个数的序列,每次删除最长连续相同子序列中最靠左的一个。如\([13,13,7,7,7,2,2,2]\)在一次删除操作之后将变为\([13,13,2,2,2]\)。输出使序列为空的最少操作次数。

思路

用map和set分别存每个连续相同子序列的起点、长度和元素值.在set中找到最长连续相同子序列中最靠左的一个之后删除掉,在map中合并该序列前后两个连续子序列,然后删除该序列,再把更新的序列写回set。这样操作直到set为空。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#define X first
#define Y second

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;

map<int, pii> dict;
set<piii> s;

int main() {
int n;
scanf("%d", &n);
int pos = -1, val = -1, num = 0;
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
if (x != val) {
if (val != -1) {
dict[pos] = make_pair(num, val);
s.insert(make_pair(num, make_pair(n - pos, val)));
}
pos = i, val = x, num = 1;
} else {
++num;
}
}
dict[pos] = make_pair(num, val);
s.insert(make_pair(num, make_pair(n - pos, val)));
int ans = 0;
while (!s.empty()) {
++ans;
piii k = *(--s.end());
s.erase(k);
pos = n - k.Y.X, val = k.Y.Y, num = k.X;
auto it = dict.find(pos);
if (it != dict.begin()) {
auto it1 = it;
--it1;
auto it2 = it;
++it2;
if (it2 != dict.end()) {
if (it1 -> Y.Y == it2 -> Y.Y) {
s.erase(make_pair(it1 -> Y.X, make_pair(n - it1 -> X, it1 -> Y.Y)));
it1 -> Y.X += it2 -> Y.X;
s.insert(make_pair(it1 -> Y.X, make_pair(n - it1 -> X, it1 -> Y.Y)));
s.erase(make_pair(it2 -> Y.X, make_pair(n - it2 -> X, it2 -> Y.Y)));
dict.erase(it2);
}
}
}
dict.erase(it);
}
printf("%d\n", ans);
return 0;
}

链接

传送门

题意

\(n\)个铁铲,价格分别为\(1~n\),现在要买两个铲子,要求价格和的末尾数字9的个数最多。输出有多少种买法。

思路

首先可以用买了个最贵的两个铲子的价格求出末尾最多有多少个9。一个9都凑不出来的时候答案为\(\frac{n \times (n - 1)}{2}\)。能凑出来时,枚举连续9之前的数字求和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long LL;

using namespace std;

const LL a[] = {0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999, 9999999999LL};
const LL b[] = {0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000LL};

int main() {
LL n, sum;
scanf("%lld", &n);
sum = n + n - 1;
int p = -1;
while (sum >= a[p + 1]) {
++p;
}
if (p == 0) {
printf("%lld\n", (n - 1) * n / 2);
return 0;
}
LL ans = 0, cur = a[p];
for (int i = 0; i < 10; ++i) {
sum = n + n - 1;
if (sum < cur) {
break;
}
if (n >= cur) {
ans += (cur - 1) / 2;
} else {
LL m = n + n - cur + 1;
if (m > 1) {
ans += m / 2;
}
}
cur += b[p];
}
printf("%lld\n", ans);
return 0;
}

链接

传送门

题意

给出\(n\)个数,\(n\)为偶数,每次操作可以选择一个数字加1或者减1,要求将这\(n\)个数分成两组,一组都是平方数,另一组都不是平方数。

思路

对于平方数,变为非平方数0需要2步,其他的需要1步。对于非平方数,可以预处理所有平方数,然后二分找到最接近的求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

typedef long long LL;

using namespace std;

const int maxn = 200010;
const int maxm = 31625;

int sqnum[maxm];

vector<int> sq, nsq;

int main() {
for (int i = 0; i < maxm; ++i) {
sqnum[i] = i * i;
}
int n;
scanf("%d", &n);
for (int i = 0, x; i < n; ++i) {
scanf("%d", &x);
int *it = lower_bound(sqnum, sqnum + maxm, x);
if (*it == x) {
sq.push_back(x == 0 ? 2 : 1);
} else {
nsq.push_back(min(*it - x, x - *(it - 1)));
}
}
n /= 2;
LL ans = 0;
if (sq.size() > nsq.size()) {
int dt = n - int(nsq.size());
sort(sq.begin(), sq.end());
for (int i = 0; i < dt; ++i) {
ans += sq[i];
}
} else {
int dt = n - int(sq.size());
sort(nsq.begin(), nsq.end());
for (int i = 0; i < dt; ++i) {
ans += nsq[i];
}
}
printf("%lld\n", ans);
return 0;
}

链接

传送门

题意

\(n\)个闹钟和他们响的时间,如果连续\(m\)分钟内, 有至少\(k\)个闹钟响起,Vitalya就会起床,问至少关掉多少个闹钟才能让Vitalya一整天不起床。其中\((1 \leq k \leq n \leq 2 \times 10^5, 1 \leq m \leq 10^6)\)

思路

每次连续\(m\)分钟响起的闹钟个数达到\(k\)个,关掉最后一个就好了🤔。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

typedef long long LL;

using namespace std;

const int maxn = 200010;

deque<int> q;
int a[maxn];

int main() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1);
int ans = 0;
for (int i = 1; i <= n; ++i) {
while (!q.empty() && q.front() + m <= a[i]) {
q.pop_front();
}
q.push_back(a[i]);
if (q.size() >= k) {
q.pop_back();
++ans;
}
}
printf("%d\n", ans);
return 0;
}

链接

传送门

题意

定义 \[d(x, y) = \begin{cases} y - x, & \text{if}\ |x - y| \gt 0 \\\ 0, & \text{if}\ |x-y| \leq 0 \end{cases};\] 给出\(n(1 \leq n \leq 200000)\)个整数\(a_1,a_2,\cdots,a_n(1 \leq a_i \leq 10^9)\),求满足\(1 \leq i \lt j \leq n\)的所有\(d(a_i,a_j)\)的和。

思路

题目本身不难,很容易想到对每一个位置所贡献求和,但是这个题的结果会爆掉long long。最后用long double过掉的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

typedef long long LL;

using namespace std;

map<int, LL> cnt;

int main() {
int n;
scanf("%d", &n);
long double ans = 0;
LL sum = 0;
for (int i = 0, x; i < n; ++i) {
scanf("%d", &x);
ans += (i - cnt[x - 1] - cnt[x] - cnt[x + 1]) * x;
ans -= (sum - (x - 1) * cnt[x - 1] - x * cnt[x] - (x + 1) * cnt[x + 1]);
++cnt[x];
sum += x;
}
printf("%.0Lf\n", ans);
return 0;
}

链接

传送门

题意

给出一棵有\(n(1 \leq n \leq 200000)\)个结点的有根树,每个结点上有一个灯,初始状态已知,有两种操作:

  • pow v:把以\(v\)为根的子树的结点上的灯状态反转;
  • get v:查询\(v\)为根的子树上有多少开着的灯。

对于每个get v输出查询结果,操作总次数为\(q(1 \leq q \leq 200000)\)

思路

dfs对结点重新编号,使每个子树编号连续。这样,pow v是对区间进行反转,get v是求区间和,可以用线段树进行维护。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn = 200010;
const int maxnode = maxn << 2;

char s[5];
int n, n_, id;
int a[maxn];
int l[maxn], r[maxn];
int inv[maxnode];
int sumv[maxnode];
vector<int> g[maxn];

void maintain(int o, int L, int R) {
int lc = o * 2, rc = o * 2 + 1;
if(R > L) {
sumv[o] = sumv[lc] + sumv[rc];
}
if (inv[o]) {
sumv[o] = R - L + 1 - sumv[o];
if (L == R) {
inv[o] = 0;
}
}
}

void pushdown(int o) {
int lc = o * 2, rc= o * 2 + 1;
if (inv[o]) {
inv[lc] ^= 1;
inv[rc] ^= 1;
inv[o] = 0;
}
}

void update(int l, int r, int o = 1, int L = 1, int R = n_) {
int lc = o * 2, rc = o * 2 + 1;
if(l <= L && r >= R) {
inv[o] ^= 1;
} else {
pushdown(o);
int M = L + (R - L) / 2;
if(l <= M) update(l, r, lc, L, M);
else maintain(lc, L, M);
if(r > M) update(l, r, rc, M + 1, R);
else maintain(rc, M + 1, R);
}
maintain(o, L, R);
}

int query(int l, int r, int o = 1, int L = 1, int R = n_) {
int lc = o * 2, rc = o * 2 + 1;
maintain(o, L, R);
if(l <= L && r >= R) {
return sumv[o];
}
pushdown(o);
int M = L + (R - L) / 2;
int lsum = 0, rsum = 0;
if(l <= M) lsum = query(l, r, lc, L, M);
else maintain(lc, L, M);
if(r > M) rsum = query(l, r, rc, M+1, R);
else maintain(rc, M+1, R);
return lsum + rsum;
}

void dfs(int u) {
a[u] = ++id;
l[u] = id;
for (int v: g[u]) {
dfs(v);
}
r[u] = id;
}

int main() {
scanf("%d", &n);
for (int i = 2, x; i <= n; ++i) {
scanf("%d", &x);
g[x].push_back(i);
}
dfs(1);
n_ = 1;
while (n_ < n) {
n_ <<= 1;
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &sumv[n_ - 1 + a[i]]);
}
for (int i = n_ - 1; i >= 1; --i) {
sumv[i] = sumv[i * 2] + sumv[i * 2 + 1];
}
int q, v;
scanf("%d", &q);
while (q--) {
scanf("%s%d", s, &v);
if (s[0] == 'g') {
printf("%d\n", query(l[v], r[v]));
} else {
update(l[v], r[v]);
}
}
return 0;
}

链接

传送门

题意

给出\(n \times m(1 \leq n, m \leq 1000)\)的地图(有障碍物)、起点和终点,每秒最多向一个方向走\(k(1 \leq k \leq 1000)\)步,问最少多少秒能从起点走到终点,无解输出-1。

思路

从起点开始BFS,每次向同一个方向扩展\(k\)步,由于每次可以走多步,所以可能出现路径交叉,多次访问同一个位置,这时不需要入队,只需要跳过重复位置继续进行后续的扩展。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define X first
#define Y second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1010;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

char s[maxn][maxn];
int vis[maxn][maxn];
queue<pii> q;

int main() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i) {
scanf("%s", s[i] + 1);
}
int ax, ay, bx, by;
scanf("%d%d%d%d", &ax, &ay, &bx, &by);
memset(vis, -1, sizeof vis);
vis[ax][ay] = 0;
q.push(make_pair(ax, ay));
while (!q.empty()) {
pii u = q.front();
if (u.X == bx && u.Y == by) {
break;
}
q.pop();
for (int i = 0; i < 4; ++i) {
int x = u.X + dx[i], y = u.Y + dy[i], j = k;
while (j-- && s[x][y] == '.' && (vis[x][y] == -1 || vis[x][y] > vis[u.X][u.Y])) {
if (vis[x][y] == -1) {
q.push(make_pair(x, y));
}
vis[x][y] = vis[u.X][u.Y] + 1;
x += dx[i], y += dy[i];
}
}
}
printf("%d\n", vis[bx][by]);
return 0;
}