Chengrui's Blog

0%

发表于 分类于 Disqus：

链接

传送门

题意

给出\(1\)到\(n(1 \leq n \leq 1000000)\)的排列，再给出\(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
#include <cstdio>
#include <algorithm>
#include <functional>
#include <cstring>
#include <vector>

using namespace std;
const int maxn = 1000010;
int a[maxn], p[maxn], ans[maxn];
vector<int> g[maxn], v, pos;
bool vis[maxn];

void dfs(int u) {
  vis[u] = true;
  v.push_back(a[u]);
  pos.push_back(u);
  for (int v: g[u]) {
    if (!vis[v]) {
      dfs(v);
    }
  }
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    p[a[i]] = i;
  }
  for (int i = 0; i < m; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; ++i) {
    if (!vis[i]) {
      v.clear();
      pos.clear();
      dfs(i);
      sort(v.begin(), v.end(), greater<int> ());
      sort(pos.begin(), pos.end());
      for (int j = 0; j < pos.size(); ++j) {
        ans[pos[j]] = v[j];
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    printf("%d ", ans[i]);
  }
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出\(n(1 \leq n \leq 200000)\)个整数，依次输出所有长度为\(x(1 \leq x \leq 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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

typedef long long LL;
using namespace std;
const int maxn = 200010;
int a[maxn], l[maxn], r[maxn];
priority_queue<int> q[maxn];
int ans[maxn];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    l[i] = 1;
    r[i] = n;
  }
  deque<pair<int, int>> dq;
  dq.push_back(make_pair(1, a[1]));
  for (int i = 2; i <= n; ++i) {
    while (!dq.empty() && dq.back().second > a[i]) {
      r[dq.back().first] = i - 1;
      dq.pop_back();
    }
    dq.push_back(make_pair(i, a[i]));
  }
  while (!dq.empty()) {
    dq.pop_front();
  }
  dq.push_back(make_pair(n, a[n]));
  for (int i = n - 1; i > 0; --i) {
    while (!dq.empty() && dq.back().second > a[i]) {
      l[dq.back().first] = i + 1;
      dq.pop_back();
    }
    dq.push_back(make_pair(i, a[i]));
  }
  for (int i = 1; i <= n; ++i) {
    int x = r[i] - l[i] + 1;
    q[x].push(a[i]);
  }
  for (int i = n; i > 0; --i) {
    ans[i] = max(ans[i + 1], q[i].empty() ? 0 : q[i].top());
  }
  for (int i = 1; i <= n; ++i) {
    printf("%d ", ans[i]);
  }
  return 0;
}

发表于 Disqus：

链接

传送门

题意

一队\(n\)个人，单位时间队首的人有\(p\)的概率出队，求\(t\)单位时间后出队的人数量的期望。

思路

可以dp也可以使用数学二项分布公式，注意使用公式时要用对数优化精度。

代码

概率dp：

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

using namespace std;

const int maxn = 2010;
double dp[maxn][maxn];

int main() {
  int n, t;
  double p;
  scanf("%d%lf%d", &n, &p, &t);
  dp[0][0] = 1;
  for (int i = 0; i < t; ++i) {
    for (int j = min(n - 1, i); j >= 0; --j) {
      dp[i + 1][j] += dp[i][j] * (1 - p);
      dp[i + 1][j + 1] += dp[i][j] * p;
    }
    dp[i + 1][n] += dp[i][n];
  }
  double ans = 0;
  for (int i = 0; i <= n; ++i) {
    ans += dp[t][i] * i;
  }
  printf("%.10f", ans);
  return 0;
}

数学公式：

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

using namespace std;

const int maxn = 2010;
long double Log[maxn];

int main() {
  int n, t;
  double p, ans = 0;
  scanf("%d%lf%d", &n, &p, &t);
  if (p == 1) {
    ans = min(n, t);
  } else if (p != 0) {
    for (int i = 1; i < maxn; ++i) {
      Log[i] = Log[i - 1] + log(i);
    }
    for (int i = 0; i <= t; ++i) {
      long double tmp = Log[t] - Log[t - i] - Log[i];
      tmp += i * log(p);
      tmp += (t - i) * log(1 - p);
      ans += min(i, n) * exp(tmp);
    }
  }
  printf("%.10f", ans);
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出\(n \times m, (1 \leq n, m, n \dot m \leq 1000000)\)的矩阵，对其进行处理，用正整数替换矩阵中数值，使得原本每行和每列中数的大小关系不变，且矩阵中的最大元素最小。

思路

分别对列和行进行处理，对于每个阶段储存与其相邻的比它小或相等的元素。对元素排序后，对于每一个未赋值的元素，找出所有和它相等的在同一行或同一列的元素，对于所有找出的元素求比它们小的元素的最大值。

Tutorial里称这种做法为“lazy computations”。

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
using namespace std;

const int maxn = 1000010;
bool vis[maxn];
int a[maxn], x[maxn], ans[maxn];
vector<int> eq[maxn], mr[maxn];
struct node {
  int v, id;
  void Set(int x) {
    id = x;
    v = a[id];
  }
  bool operator < (const node& rhs) const {
    return v < rhs.v || (v == rhs.v && id == rhs.id);
  }
} b[maxn];

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int num = n * m;
  for (int i = 0; i < num; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      b[j].Set(i * m + j);
    }
    sort(b, b + m);
    for (int j = 1; j < m; ++j) {
      int x = b[j].id;
      int y = b[j - 1].id;
      if (b[j].v == b[j - 1].v) {
        eq[x].push_back(y);
        eq[y].push_back(x);
      } else {
        mr[x].push_back(y);
      }
    }
  }
  for (int j = 0; j < m; ++j) {
    for (int i = 0; i < n; ++i) {
      b[i].Set(i * m + j);
    }
    sort(b, b + n);
    for (int i = 1; i < n; ++i) {
      int x = b[i].id;
      int y = b[i - 1].id;
      if (b[i].v == b[i - 1].v) {
        eq[x].push_back(y);
        eq[y].push_back(x);
      } else {
        mr[x].push_back(y);
      }
    }
  }
  for (int i = 0; i < num; ++i) {
    b[i].Set(i);
  }
  sort(b, b + num);
  for (int i = 0; i < num; ++i) {
    int id = b[i].id;
    if (vis[id]) {
      continue;
    }
    x[0] = id;
    vis[id] = true;
    int s = 0, e = 0;
    while (s <= e) {
      for (int u: eq[x[s]]) {
        if (!vis[u]) {
          x[++e] = u;
          vis[u] = true;
        }
      }
      ++s;
    }
    ++e;
    int put = 0;
    for (int j = 0; j < e; ++j) {
      for (int v: mr[x[j]]) {
        put = max(put, ans[v]);
      }
    }
    ++put;
    for (int j = 0; j < e; ++j) {
      ans[x[j]] = put;
    }
  }
  num = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      printf("%d ",ans[num++]);
    }
    puts("");
  }
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出整数\(n,k(1 \leq n, k \leq 1000000)\)，接着给出\(n\)个整数\(c_i\)，在已知\(x \mod {c_i}\)的前提下，能否唯一的确定\(x \mod k\)。

思路

将\(k\)进行分解，对于每个质数，如果都存在\(c_i\)中的质数的幂比\(k\)中的大，则能唯一的确定\(x \mod 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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

LL gcd(LL a, LL b) {
  return b ? gcd(b, a % b) : a;
}

LL lcm(LL a, LL b) {
  return a / gcd(a, b) * b;
}

int main() {
  int n, k, c;
  LL cur = 1;
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &c);
    cur = lcm(cur, gcd(c, k));
  }
  puts(cur == k ? "Yes" : "No");
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出\(n \times n\)的由‘X’和‘.’构成的字符矩阵，求将一块边长为\(k\)的方形内的字符全都变为‘.’之后，最大的由‘.’组成的连通分量。\((1 \leq k \leq n \leq 500)\)

思路

首先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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const int maxn = 510;
int n, k, cnt;
int id[maxn][maxn];
int num[maxn * maxn], vis[maxn * maxn];
char g[maxn][maxn];

void dfs(int x, int y) {
  id[x][y] = cnt;
  ++num[cnt];
  for (int i = 0; i < 4; ++i) {
    int a = x + dx[i], b = y + dy[i];
    if (a >= 0 && a < n && b >= 0 && b < n && g[a][b] == '.' && id[a][b] == 0) {
      dfs(a, b);
    }
  }
}

void add(int x, int y, int clk, int& res) {
  if (x >= 0 && x < n && y >= 0 && y < n && g[x][y] == '.' && vis[id[x][y]] != clk) {
    vis[id[x][y]] = clk;
    res += num[id[x][y]];
  }
}

int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%s", g[i]);
  }
  if (n <= k) {
    printf("%d\n", n * n);
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (g[i][j] == '.' && id[i][j] == 0) {
        ++cnt;
        dfs(i, j);
      }
    }
  }
  int ans = 0, clk = 1;
  for (int u = 0; u + k <= n; ++u) {
    for (int x = 0; x < k; ++x) {
      for (int y = 0; y < k; ++y) {
        --num[id[u + x][y]];
      }
    }
    for (int l = 0; l + k <= n; ++l) {
      int res = k * k;
      for (int x = 0; x < k; ++x) {
        add(u + x, l - 1, clk, res);
        add(u + x, l + k, clk, res);
      }
      for (int y = 0; y < k; ++y) {
        add(u - 1, l + y, clk, res);
        add(u + k, l + y, clk, res);
      }
      ++clk;
      ans = max(ans, res);
      if (l + k != n) {
        for (int x = 0; x < k; ++x) {
          --num[id[u + x][l + k]];
          ++num[id[u + x][l]];
        }
      }
    }
    for (int x = 0; x < k; ++x) {
      for (int y = 0; y < k; ++y) {
        ++num[id[u + x][n - k + y]];
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出递推式\(f(x)=f(x-a^3)+1\)（其中\(a\)为满足\(a^3 \leq x\)的最大整数），给出一个\(m(1 \leq m \leq {10}^{15})\)，求最大的\(f(x)\)和当\(f(x)\)最大时最大的\(x\)。

思路

设所求\(f(x)\)为\(F(m)\)，对于当前的\(m\)，设\(a\)为满足\(a^3 \leq m\)的最大整数，考虑两种转移：

  • 转移至减去\(a^3\)：\(F(m)=F(m-a^3)+1\)
  • 转移至减去\({(a-1)}^3\)：\(F(m)=F(a^3-1-{(a-1)}^3)+1\)

对于如上两种转移，可以递归求解。如果要转移至减去\({(a-2)}^3\)，则变为\(F(m)=F({(a-1)}^3－1-{(a-2)}^3)+1\)，由于\(F(m)\)单调不减，且\({(a-1)}^3-1-{(a-2)}^3 < a^3-1-{(a-1)}^3\)，所以不考虑此转移。

代码

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

typedef long long LL;
const int maxn = 100010;
LL a[maxn];
LL ansNum, ansX;

void solve(LL m, LL num, LL X) {
  if (m == 0) {
    if (num > ansNum || (num == ansNum && X > ansX)) {
      ansNum = num;
      ansX = X;
    }
    return;
  }
  LL x = 1;
  while (a[x + 1] <= m) {
    ++x;
  }
  solve(m - a[x], num + 1, X + a[x]);
  if (x > 0) {
    solve(a[x] - 1 - a[x - 1], num + 1, X + a[x - 1]);
  }
}

int main() {
  for (int i = 1; i < maxn; ++i) {
    a[i] = LL(i) * i * i;
  }
  LL m;
  scanf("%I64d", &m);
  solve(m, 0, 0);
  printf("%I64d %I64d\n", ansNum, ansX);
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

有一个数字\(x,(1 \leq x \leq 100)\)，程序可以最多询问20次，每次输出一个数字，系统会给出他是否为x的因子，最后要求输出\(x\)是否为素数。

思路

检验给出的数字\(x\)的素因子个数，若有多个则为合数，如果只有一个，判断素因子的平方是否为\(x\)的因子，若为则为合数，不为则为素数。

代码

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

using namespace std;
const int maxn = 110;
const int p2[] = {4, 9, 25, 49};
int p[maxn], num;
bool np[maxn] = {1, 1};

void init() {
  for (int i = 2; i < maxn; ++i) {
    if (!np[i]) {
      p[num++] = i;
      for (int j = i * i; j < maxn; j += i) {
        np[j] = true;
      }
    }
  }
}

bool check(int x) {
  cout << x << endl;
  string s;
  cin >> s;
  return s[0] == 'y';
}

int main() {
  init();
  int cnt = 0, x;
  for (int i = 0; i < 16; ++i) {
    if (check(p[i])) {
      ++cnt;
    }
  }
  for (int i = 0; i < 4; ++i) {
    if (check(p2[i])) {
      cnt = 10;
    }
  }
  cout << ((cnt <= 1) ? "prime" : "composite") << endl;
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

原本有一个数字组成的字符串，现在给出将原字符串的长度附加在字符串后打乱的字符串，和原字符串的一个子串。输出字典序最小的原字符串，不允许有前导零。

思路

设原字符串的子串为\(s0\)，在原字符串中去掉\(s0\)之后的字符串为\(s1\)，我们可以构造出两个字符串，最后比较输出。

  • \(ans1\)：\(s1\)中最小的非0数字做第一位，升序排列剩余数字，然后对于每种数字检测应该放在\(s0\)之前还是\(s0\)之后，将\(s0\)插入到合适位置。

  • \(ans2\)：\(s1\)升序排列后，把\(s0\)接在后面。

最后输出\(min(ans1, ans2)\)，注意判断前导零。

代码

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 <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
int cnt[10], len;
char s[maxn];
string ans1, ans2;

int getLen(int k) {
  int res = 0;
  while (k) {
    k /= 10;
    ++res;
  }
  return res == 0 ? 1 : res;
}

bool check(char c) {
  for (int i = 0; i < len; ++i) {
    if (c != s[i]) {
      return c > s[i];
    }
  }
  return false;
}

int main() {
  scanf("%s", s);
  while (s[len]) {
    ++cnt[s[len] - '0'];
    ++len;
  }
  for (int i = 1; i <= 7; ++i) {
    int rm = len - i;
    if (getLen(rm) == i) {
      len = rm;
      while (rm) {
        --cnt[rm % 10];
        rm /= 10;
      }
      break;
    }
  }
  scanf("%s", s);
  len = 0;
  while (s[len]) {
    --cnt[s[len] - '0'];
    ++len;
  }
  ans2 += s;
  int flag = -1;
  for (int i = 1; i < 10; ++i) {
    if (cnt[i] > 0) {
      ans1 += char(i + '0'); 
      --cnt[i];
      flag = i;
      break;
    }
  }
  bool ok = false;
  for (int i = 0; i < 10; ++i) {
    if (flag == i) {
      ans2 += char(i + '0');
    }
    if (cnt[i] > 0) {
      char c = i + '0';
      if (!ok && check(c)) {
        ans1 += s;
        ok = true;
      }
      while (cnt[i] > 0) {
        ans1 += c;
        ans2 += c;
        --cnt[i];
      }
    }
  }
  if (flag == -1) {
    puts(ans2.c_str());
    return 0;
  }
  if (!ok) {
    ans1 += s;
  }
  puts(ans2[0] != '0' && ans2 < ans1 ? ans2.c_str() : ans1.c_str());
  return 0;
}

发表于 分类于 Disqus：

开场之后，我开始登PC^2，开比赛排行榜页面，开CB。

ZDL读到K是水题，跟我说我开始写，过了一会写完了，测了样例，提交WA。然后开始查错，过了挺久才查出来，多输出了个空格，K2y(12)。 然后ZDL说A水，跟我说式子，A1y(16)。

LRY说E是水题，跟我讲题意和思路，题意上一开始出了点问题，整理好思路之后，敲了交了一发WA。打印代码Debug。发现上界写错了，E2y(29)。

刷榜，发现有队伍过了B，10w的数据量应该不是暴力，LRY和我开始推式子，题目要求不相临，但似乎没有无解的时候，我跟LRY说了思路，每次找最大的减去，LRY感觉可行，写完交了一发，B1y(50)。

这个时候又读出来了I、F、G的题意。但感觉不是很简单。

ZDL上机写C。我开始读J，读题时，少看了一个词，导致一直没有看懂样例，读懂之后发现是水题。ZDL调代码卡了一下，打印代码。我上机写J，交了一发WA。发现式子写错一位数，修改之后，J2y(92)。

ZDL上机继续改C，LRY跟我讲G思路，他推了个式子，需要验证，手算了几个小数据感觉靠谱。又给我讲了F的DP思路，我也感觉靠谱。ZDL交了一发C，WA。我上机敲G的暴力，验证了几组大数据，感觉没什么问题，交了一发G1y(104)。

LRY查代码，我开始敲F，写了一半发现转移多了一维，跟LRY说，LRY继续思路。ZDL上机改C，LRY跟我讲了H的题意，我感觉时间挺长的，可以往后放一放。

ZDL改好C，C2y(112)。LRY跟我说最后一位转移可以优化掉，于是我继续敲F，LRY和ZDL读其他的题。

我敲好代码之后发现样例不过，LRY开始Debug，ZDL跟我讲了D题的思路，我刷榜发现排名靠后的队有出这道题的，感觉似乎可以暴力水过去，于是跟LRY和ZDL商量了一下，准备先交一发暴力，写了个下标优化的暴力排序，提交TLE。

LRY查完错，过了样例，交了一发WA。榜上又有了个队过了D，LRY说可以用合并有序表过，写了一发，D2y(174)。

然后LRY继续查F，ZDL跟我讲了L思路，类似于预处理后，对于查询求相对位置，直接输出。感觉比H好写，于是开始写L，写好之后，测试样例时发现过不了，和想的不一样，0不能向下转到9。于是开始想优化，发现似乎并不能搞。

LRY找F的错，一会帮LRY测F的数据，我开始想H的写法。LRY找到了个错，修改后提交WA，打印代码，我上机。

因为要测F的数据，H断断续续写了半个小时左右，LRY发现，F题应该写continue的地方写成了break。修改之后F3y(297)。

剩下的时间写H，写好后测了样例提交WA，一直修改到最后没改出来。

总体来讲，这次比赛我发挥的挺水的，开场的几次WA，直接就把整个队伍搞得节奏搞乱了，还好后来三开做题才把