Chengrui's Blog

0%

发表于 分类于 Disqus：

链接

传送门

题意

给出一个\(n\)个结点的父结点，改变最少的结点的父结点使得图变为一棵有向树。

思路

dfs搜出所有的环，指定新的根，把环解开后连到根上就好啦。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 200005;

int a[maxn];
int x[maxn], vis[maxn];

void dfs(int u, int id) {
  vis[u] = id;
  if (vis[a[u]]) {
    x[id] = vis[a[u]] == id ? u : -1;
  } else {
    dfs(a[u], id);
  }
}

int main() {
  int n, u = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    if (a[i] == i) {
      u = i;
    }
  }
  int num = 0;
  for (int i = 1; i <= n; ++i) {
    if (!vis[i]) {
      dfs(i, ++num);
    }
  }
  if (u == 0) {
    for (int i = 1; i <= num; ++i) {
      if (x[i] != -1) {
        u = x[i];
        break;
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= num; ++i) {
    if (x[i] != -1 && a[x[i]] != u) {
      a[x[i]] = u;
      ++ans;
    }
  }
  printf("%d\n", ans);
  for (int i = 1; i <= n; ++i) {
    printf("%d ", a[i]);
  }
  puts("");
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出一个\(n\)个结点的树，有\(q\)个查询，对于每个查询输出以\(x\)为根的子树的重心。

思路

在两个树合并后，新的重心在链接原来两个树重心的路径上。因此可以dfs求解。

可以参考这篇博客：Codeforces 685B - Kay and Snowflake | Sengxian's Blog

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int maxn = 300005;

int p[maxn];
int sum[maxn], ans[maxn];
vector<int> g[maxn];

int dfs(int u) {
  sum[u] = 1;
  for (int v: g[u]) {
    sum[u] += dfs(v);
  }
  for (int v: g[u]) {
    if ((sum[v] << 1) >= sum[u]) {
      ans[u] = ans[v];
      while (((sum[u] - sum[ans[u]]) << 1) > sum[u]) {
        ans[u] = p[ans[u]];
      }
    }
  }
  if (ans[u] == 0) {
    ans[u] = u;
  }
  return sum[u];
}

int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 2; i <= n; ++i) {
    scanf("%d", &p[i]);
    g[p[i]].push_back(i);
  }
  dfs(1);
  while (q--) {
    int x;
    scanf("%d", &x);
    printf("%d\n", ans[x]);
  }
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出一个浮点数，转化成标准形式。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <deque>

using namespace std;

typedef long long LL;

deque<char> dq;

int main() {
  char c;
  int cnt = 0;
  bool flag = false;
  while (~(c = getchar())) {
    if (c == '.') {
      flag = true;
    } else if (isdigit(c)) {
      dq.push_back(c);
      if (flag) {
        --cnt;
      }
    }
  }
  while (!dq.empty()) {
    if (dq.front() == '0') {
      dq.pop_front();
    } else {
      break;
    }
  }
  while (!dq.empty()) {
    if (dq.back() == '0') {
      ++cnt;
      dq.pop_back();
    } else {
      break;
    }
  }
  if (dq.empty()) {
    puts("0");
    return 0;
  }
  putchar(dq.front());
  dq.pop_front();
  cnt += dq.size();
  if (!dq.empty()) {
    putchar('.');
    while (!dq.empty()) {
      putchar(dq.front());
      dq.pop_front();
    }
  }
  if (cnt != 0) {
    printf("E%d", cnt);
  }
  puts("");
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出\(n\)个区间，问所有选择\(k\)个不同区间的方法下它们相交区间的长度和。

思路

离散化之后用扫描线维护有多少个区间包含当前子区间，然后当前区间的贡献为\({num \choose k} \cdot len\)。

代码

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>

using namespace std;

typedef long long LL;

const LL mod = 1000000007;
const int maxn = 200010;
int l[maxn], r[maxn];
int Hash[maxn << 1], sum[maxn << 1];
LL inv[maxn], fac[maxn], invfac[maxn];

LL C(int n, int k) {
  return fac[n] * invfac[k] % mod * invfac[n - k] % mod;
}

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  int num = 0;
  inv[1] = fac[1] = fac[0] = invfac[1] = invfac[0] = 1;
  for (int i = 2; i <= n; ++i) {
    inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    fac[i] = fac[i - 1] * i % mod;
    invfac[i] = invfac[i - 1] * inv[i] % mod;
  }
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &l[i], &r[i]);
    Hash[num++] = l[i];
    Hash[num++] = r[i] + 1;
  }
  sort(Hash , Hash + num);
  num = int(unique(Hash, Hash + num) - Hash);
  for (int i = 0; i < n; ++i) {
    ++sum[int(lower_bound(Hash, Hash + num, l[i]) - Hash)];
    --sum[int(lower_bound(Hash, Hash + num, r[i] + 1) - Hash)];
  }
  int tmp = sum[0];
  LL ans = 0;
  for (int i = 1; i < num; ++i) {
    if (tmp >= k) {
      ans = (ans + C(tmp, k) * (Hash[i] - Hash[i - 1])) % mod;
    }
    tmp += sum[i];
  }
  printf("%lld\n", ans);
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出序列a和序列b，问有多少组l、r满足\(\max \limits_{i=l}^{r}a_i=\min\limits_{i=l}^{r}b_i\)。

思路

对于左端点固定的区间，最大值随右端点的单调不降，最小值单调不增。 所以\(\max \limits_{i=l}^{r}a_i-\min\limits_{i=l}^{r}b_i\)也是单调不降的。因此可以对于每个左端点二分满足条件的右端点的区间求解。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 200005;
const int maxm = 18;

int n, mm[maxn];
int Max[maxn][maxm], Min[maxn][maxm];

int rmq(int L, int R, bool x) {
  int k = mm[R - L + 1];
  return x ? max(Max[L][k], Max[R - (1 << k) + 1][k]) : min(Min[L][k], Min[R - (1 << k) + 1][k]);
}

int main() {
  int n;
  scanf("%d", &n);
  mm[0] = -1;
  for (int i = 1; i <= n; ++i) {
    mm[i] = (i & (i - 1)) ? mm[i - 1] : mm[i - 1] + 1;
    scanf("%d", &Max[i][0]);
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &Min[i][0]);
  }
  for(int j = 1; j <= mm[n]; ++j) {
    for(int i = 1; i + (1 << j) - 1 <= n; ++i) {
      Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);
      Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
    }
  }
  LL ans = 0;
  int L, R, mid;
  for (int i = 1; i <= n; ++i) {
    L = i, R = n;
    while (L <= R) {
      mid = (L + R) >> 1;
      if (rmq(i, mid, true) - rmq(i, mid, false) < 0) {
        L = mid + 1;
      } else {
        R = mid - 1;
      }
    }
    ans -= L;
    L = i, R = n;
    while (L <= R) {
      mid = (L + R) >> 1;
      if (rmq(i, mid, true) - rmq(i, mid, false) <= 0) {
        L = mid + 1;
      } else {
        R = mid - 1;
      }
    }
    ans += L;
  }
  printf("%lld\n", ans);
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出\(n\)个点，每个点都有一条弧连接着一个其他的点，对于给出的弧，可以选一部分进行反转使得图中没有环，输出操作的方法数对\(10^9+7\)取模后的值。

思路

易得，弧的方向对结果不产生影响，将弧转为无向边考虑。显然，对于任意连通分量都至多有一个环。每个环的反转方式为\(2^e-2\)，不在环中的每条边的反转状态任意。最终的结果为\(2^{n-\sum e} \prod {\left(2^e-2\right)}\)。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef long long LL;

const LL mod = 1000000007;
const int maxn = 200005;

int p[maxn], a[maxn], d[maxn];
bool vis[maxn];
vector<int> g[maxn];
queue<int> q;

int Find(int x) {
  return x == p[x] ? x : p[x] = Find(p[x]);
}

LL fexp(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);
  for (int i = 1; i <= n; ++i) {
    p[i] = i;
    scanf("%d", &a[i]);
  }
  int m = 0;
  LL ans = 1;
  for (int i = 1; i <= n; ++i) {
    int fu = Find(i), fv = Find(a[i]);
    if (fu != fv) {
      p[fu] = fv;
      g[i].push_back(a[i]);
      g[a[i]].push_back(i);
    } else {
      q.push(i);
      vis[i] = true;
      d[i] = 1;
      while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v: g[u]) {
          if (!vis[v]) {
            vis[v] = true;
            d[v] = d[u] + 1;
            q.push(v);
          }
        }
      }
      m += d[a[i]];
      ans = ans * (fexp(2, d[a[i]]) - 2) % mod;
    }
  }
  printf("%d\n", int(ans * fexp(2, n - m) % mod));
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出\(n \times m(1 \leq n, m \leq 1000)\)的矩阵，有\(q(1 \leq q \leq 10000)\)次操作，每次给出两个大小相同的且不相交无公共边的子矩阵，交换两个子矩阵，输出\(q\)次操作之后的矩阵。

思路

用十字链表储存矩阵，每个点记录下面和右面两个方向的编号。这样对于每次操作，可以在\(O(n + m)\)的时间内完成。

代码

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1005;
const int maxm = 1002010;

int v[maxm], id[maxn][maxn];
int D[maxm], R[maxm];

int main() {
  int n, m, q, num;
  scanf("%d%d%d", &n, &m, &q);
  num = n + m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      int x;
      scanf("%d", &x);
      id[i][j] = ++num;
      v[num] = x;
    }
  }
  for (int i = 1; i <= n; ++i) {
    R[i] = id[i][1];
    D[i] = i + 1;
    for (int j = 1; j <= m; ++j) {
      D[id[i][j]] = id[i + 1][j];
      R[id[i][j]] = id[i][j + 1];
    }
  }
  for (int i = 1; i <= m; ++i) {
    R[i + n] = i + n + 1;
    D[i + n] = id[1][i];
  }
  while (q--) {
    int a, b, c, d, h, w;
    scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &h, &w);
    int p1 = a, p2 = c;
    for (int i = 1; i < b; ++i) {
      p1 = R[p1];
    }
    for (int i = 1; i < d; ++i) {
      p2 = R[p2];
    }
    int p3 = p1, p4 = p2;
    for (int i = 0; i < w; ++i) {
      p3 = R[p3], p4 = R[p4];
    }
    for (int i = 0; i < h; ++i) {
      swap(R[p1], R[p2]);
      swap(R[p3], R[p4]);
      p1 = D[p1], p2 = D[p2];
      p3 = D[p3], p4 = D[p4];
    }
    p1 = b + n, p2 = d + n;
    for (int i = 1; i < a; ++i) {
      p1 = D[p1];
    }
    for (int i = 1; i < c; ++i) {
      p2 = D[p2];
    }
    p3 = p1, p4 = p2;
    for (int i = 0; i < h; ++i) {
      p3 = D[p3], p4 = D[p4];
    }
    for (int i = 0; i < w; ++i) {
      swap(D[p1], D[p2]);
      swap(D[p3], D[p4]);
      p1 = R[p1], p2 = R[p2];
      p3 = R[p3], p4 = R[p4];
    }
  }
  for (int i = 1; i <= n; ++i) {
    int p = R[i];
    for (int j = 1; j <= m; ++j) {
      printf("%d ", v[p]);
      p = R[p];
    }
    puts("");
  }
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出一个可重集，最初其中有一个0，有插入删除询问三种操作。对于询问操作，输出给出的数字和可重集中的数字异或的最大值。

思路

对可重集中的数字建trie树，查询时每次都优先走于所给数字当前位相反的边，达到底层的结点即为与给出数字异或和最大的结点。

代码

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 6400005;

char s[maxn];

struct Trie {
  int next[maxn][2];
  int fa[maxn];
  int num[maxn];
  int root, L;
  
  int newnode() {
    next[L][0] = next[L][1] = fa[L] = -1;
    num[L] = 0;
    return L++;
  }
  
  void Init() {
    L = 0;
    root = newnode();
  }
  
  void Insert(int x) {
    int now = root;
    for (int i = 30; i >= 0; --i) {
      int k = (x & (1 << i)) ? 1 : 0;
      if (next[now][k] == -1) {
        next[now][k] = newnode();
        fa[next[now][k]] = now;
      }
      now = next[now][k];
      ++num[now];
    }
  }
  
  void Delete(int x) {
    int now = root;
    for (int i = 30; i >= 0; --i) {
      int k = (x & (1 << i)) ? 1 : 0;
      if (next[now][k] == -1) {
        next[now][k] = newnode();
      }
      now = next[now][k];
      --num[now];
    }
    while (fa[now] != -1) {
      if (next[now][0] != -1 && num[next[now][0]] == 0) {
        next[now][0] = -1;
      }
      if (next[now][1] != -1 && num[next[now][1]] == 0) {
        next[now][1] = -1;
      }
      now = fa[now];
    }
  }
  
  int getNum(int x) {
    int now = root, y = 0;
    for (int i = 30; i >= 0; --i) {
      int k = (x & (1 << i)) ? 0 : 1;
      y <<= 1;
      if (next[now][k] == -1) {
        k ^= 1;
      }
      y |= k;
      now = next[now][k];
    }
    return x ^ y;
  }
} trie;

int main() {
  int n, x;
  scanf("%d", &n);
  trie.Init();
  trie.Insert(0);
  while (n--) {
    scanf("%s%d", s, &x);
    if (s[0] == '+') {
      trie.Insert(x);
    } else if (s[0] == '-') {
      trie.Delete(x);
    } else {
      printf("%d\n", trie.getNum(x));
    }
  }
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出\(n(1 \leq n \leq 100000)\)个字符串，翻转和字符串的费用。现在对部分字符串进行反转操作，使得最后的字符串序列字典序单调不降。输出最小花费。

思路

显然的\(dp\)问题，状态\(dp[i][0]\)表示前\(i\)个字符串，第\(i\)个不翻转时的最小花费，\(dp[i][1]\)表示前\(i\)个字符串，第\(i\)个翻转时的最小花费。

代码

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL inf = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = 100010;

int c[maxn];
LL dp[maxn][2];
string s[maxn][2];

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> c[i];
  }
  for (int i = 1; i <= n; ++i) {
    cin >> s[i][0];
    s[i][1] = s[i][0];
    reverse(s[i][1].begin(), s[i][1].end());
  }
  memset(dp, 0x3f, sizeof dp);
  dp[1][0] = 0, dp[1][1] = c[1];
  for (int i = 2; i <= n; ++i) {
    if (s[i][0] >= s[i - 1][0]) {
      dp[i][0] = min(dp[i][0], dp[i - 1][0]);
    }
    if (s[i][0] >= s[i - 1][1]) {
      dp[i][0] = min(dp[i][0], dp[i - 1][1]);
    }
    if (s[i][1] >= s[i - 1][0]) {
      dp[i][1] = min(dp[i][1], dp[i - 1][0] + c[i]);
    }
    if (s[i][1] >= s[i - 1][1]) {
      dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i]);
    }
  }
  LL ans = min(dp[n][0], dp[n][1]);
  printf("%I64d\n", ans == inf ? -1 : ans);
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出\(n \times m\)的矩阵，矩阵中的数分为了\(k\)个分量，其中\(1 \leq n, m, k \leq 2000\)。每个点都有各自的权值。有两种操作：

  • 修改一个分量的开关状态。
  • 查询一个矩形内所有开着的点的权值和并输出。

其中查询操作不超过2000次。

思路

记录查询时分量的开关状态，然后用二维树状数组计算出分量对每个查询的贡献。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define X first
#define Y second

using namespace std;

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

const int maxn = 2005;

char cmd[maxn];
LL bit[maxn][maxn], ans[maxn];
int n, m, a[maxn][maxn];
int u[maxn], l[maxn], d[maxn], r[maxn];
bool vis[maxn][maxn], cur[maxn];
vector<pii> g[maxn];

LL sum(int x, int y) {
  LL res = 0;
  for (int i = x; i > 0; i -= i & -i) {
    for (int j = y; j > 0; j -= j & -j) {
      res += bit[i][j];
    }
  }
  return res;
}

void add(int x, int y, int d) {
  for (int i = x; i <= n; i += i & -i) {
    for (int j = y; j <= m; j += j & -j) {
      bit[i][j] += d;
    }
  }
}

int main() {
  int k;
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= k; ++i) {
    int x, y, z;
    scanf("%d", &z);
    for (int j = 0 ; j < z; ++j) {
      scanf("%d%d", &x, &y);
      g[i].emplace_back(make_pair(x, y));
      scanf("%d", &a[x][y]);
    }
  }
  int q, num = 0;
  scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    scanf("%s", cmd);
    if (cmd[0] == 'A') {
      ++num;
      scanf("%d%d%d%d", &u[num], &l[num], &d[num], &r[num]);
      for (int j = 1; j <= k; ++j) {
        vis[j][num] = !cur[j];
      }
    } else {
      int x;
      scanf("%d", &x);
      cur[x] = !cur[x];
    }
  }
  for (int i = 1; i <= k; ++i) {
    for (pii& u: g[i]) {
      add(u.X, u.Y, a[u.X][u.Y]);
    }
    for (int j = 1; j <= num; ++j) {
      if (vis[i][j]) {
        ans[j] += sum(d[j], r[j]) - sum(d[j], l[j] - 1) - sum(u[j] - 1, r[j]) + sum(u[j] - 1, l[j] - 1);
      }
    }
    for (pii& u: g[i]) {
      add(u.X, u.Y, -a[u.X][u.Y]);
    }
  }
  for (int i = 1; i <= num; ++i) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}