Chengrui's Blog

0%

发表于 分类于 Disqus：

链接

传送门

题意

给出\(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;
}

发表于 分类于 Disqus：

链接

传送门

题意

有一个\(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;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出一个长度为\(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;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出\(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;
}

发表于 分类于 Disqus：

链接

传送门

题意

有\(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;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出\(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;
}

发表于 分类于 Disqus：

链接

传送门

题意

有\(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;
}

发表于 分类于 Disqus：

链接

传送门

题意

定义 \[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;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出一棵有\(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;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出\(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;
}