avatar
文章
24
标签
19
首页
时间轴
标签
友链
关于
ruogu's blog
首页
时间轴
标签
友链
关于
2018syc（一）
阅读量:|评论数:

noi.ac problem11,12,1311,12,13


A

其实是一道水题，但是我wa了。

我以为答案是n!∏leni\frac{n!}{\prod{len_i}}

其实呢，相同的长度的环是不能交换的，所以还要除以相同长度环个数的阶乘。

所以令aia_i表示长度为ii的环的个数，答案就是n!∏iaiai!\frac{n!}{\prod{i^{a_i}a_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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 998244353;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 1e6 + 5;
int n, p[N], inv[N], a[N];
bool vis[N];
//
int main() {
  n = getint();
  rep(i, n) p[i] = getint() - 1;
  int res = 1;
  for (int i = 1; i <= n; i++) res = mul(res, i);
  inv[1] = 1;
  for (int i = 2; i <= n; i++) inv[i] = mul(mod - mod / i, inv[mod % i]); 
  rep(i, n) if (!vis[i]) {
    int len = 0, x = i;
    while (!vis[x]) {
      vis[x] = true;
      ++len;
      x = p[x];
    }
    res = mul(res, inv[len]);
    ++a[len];
  }
  for (int i = 2; i <= n; i++) inv[i] = mul(inv[i - 1], inv[i]);
  for (int i = 1; i <= n; i++) if (a[i]) res = mul(res, inv[a[i]]); 
  cout << res << endl;
  return 0;
}

B

非常神仙的题。

https://blog.csdn.net/wmhtxdy/article/details/104457810参考了神仙的博客。

首先无论是正解，还是O(n2)O(n^2)的暴力，都要把原数组从大到小排序。

首先，根据xyy神仙打表发现，答案是不会退流的。也就是若SkS_k表示有kk天的最大答案，那么存在一组最优解满足Sk⊂Sk+1S_k \sub S_{k+1}。

突然感觉自己完全解释不清楚，决定不解释了，直接看代码吧。

代码没写完。

upd(5.17)

解释一下代码？

按aa从大往小插入。考虑为平衡树每个节点维护一个rk（只是为了方便其实），我们要保证当插入前ii个肥宅后，kk天的答案就是所有rk≤krk \leq k的节点值的和。那么，我们最终插入的这个节点ii，他的aa比所有之前答案集合的aa要小，也就是他一进入，后面每个数都要加上这个aia_i。

问题就是他插入在哪里比较好。考虑平衡树上两个相邻的节点差值一定大于等于aia_i，由归纳法可以证明。那么，这个插入一定是具有单调性的：考虑一个节点如果我用ii代替他的rk，让他右移一位怎么样？这样子考虑。

这样的话，似乎自然而然的证明了上述结论，也可能不需要上述结论就可以完成本题了。

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
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 1e6 + 5;
int n, k, sz[N], rd[N], ls[N], rs[N], rt, a[N];
ll b[N], res;
ll val[N], tag_val[N];
int rk[N], tag_rk[N];
vector<pair<int, ll>> aa; 
//
inline ll calc(int x, int y) {
  return 1ll * x * a[y] + b[y];
}
inline void upd_rk(int k, int x) {
  rk[k] += x; tag_rk[k] += x;
}
inline void upd_val(int k, ll x) {
  val[k] += x; tag_val[k] += x;
}
inline void up(int k) {
  sz[k] = sz[ls[k]] + sz[rs[k]] + 1;
}
inline void pd(int k) {
  if (tag_rk[k]) {
    upd_rk(ls[k], tag_rk[k]);
    upd_rk(rs[k], tag_rk[k]);
    tag_rk[k] = 0;
  }
  if (tag_val[k]) {
    upd_val(ls[k], tag_val[k]);
    upd_val(rs[k], tag_val[k]);
    tag_val[k] = 0;
  }
}
void merge(int x, int y, int &z) {
  if (!x || !y) { z = x ^ y; return; }
  pd(x); pd(y);
  //if (rnd[x] < rnd[y]) {
  //if (rand() % (sz[x] + sz[y]) < sz[x]) {
  if (rand() & 1) {
    merge(rs[x], y, rs[x]);
    z = x;
  }
  else {
    merge(x, ls[y], ls[y]);
    z = y;
  }
  up(z);
}
void split(int x, int &y, int &z, int id) {
  if (!x) { y = z = 0; return; }
  pd(x);
  if (val[x] < calc(rk[x], id)) {
    split(rs[x], rs[x], z, id);
    y = x;
  }
  else {
    split(ls[x], y, ls[x], id);
    z = x;
  }
  up(x);
}
void dfs(int x) {
  if (!x) return;
  if (rk[x] < k) res += val[x];
  pd(x);
  dfs(ls[x]); dfs(rs[x]);
}
int main() {
  srand(233);
  n = getint(); k = getint();
  rep(i, n) {
    int x = getint(); ll y; scanf("%lld", &y);
    aa.emplace_back(x, y);
  }
  sort(aa.begin(), aa.end());
  reverse(aa.begin(), aa.end());
  rep(i, aa.size()) {
    a[i] = aa[i].first;
    b[i] = aa[i].second;
  }
  rt = 1; val[1] = calc(0, 0); sz[1] = 1;
  for (int i = 1; i < n; i++) {
    int x, y;
    split(rt, x, y, i);
    if (y) {
      upd_rk(y, 1);
      upd_val(y, a[i]);
    }
    rt = i + 1; 
    sz[rt] = 1;
    rk[rt] = x ? sz[x] : 0;
    val[rt] = calc(rk[rt], i);
    merge(x, rt, rt);
    merge(rt, y, rt);
  }
  dfs(rt);
  cout << res << endl;
  return 0;
}

然后出现了一个很奇怪的现象，就是mergemerge函数那里正常的两种写法都过不了，只有现在这个能过。。大约是fhq-treap本身常数足够大。可能在这种情况下写splay比较好。。


C

正解我不会。

有人写了一些奇怪的做法，比如从当前度数最大的点开始跑最短路，然后把与之相邻的没有归类的点归到一类上去。这样恰好是满足[d,d+2][d,d+2]的条件的。但是不清楚他的复杂度，好像只能过6060。

http://noi.ac/submission/1167

那么，这题都是0101，自然可以bitset！复杂度大概是O(n3w)O(\frac{n^3}{w})。w=64w=64的时候差不多1e91e9级别，但是很快，可以过。

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 <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 4005;
const int inf = 998244353;
int n;
struct bitset {
  ull d[64];
  void cl() { rep(i, n) d[i >> 6] |= 1ull << (i & 63); }
  void upd(int x) { d[x >> 6] ^= 1ull << (x & 63); }
} e[N], vis;
int q, dis[N][N], qu[N];
char s[N];
//
int main() {
  n = getint(); q = getint();
  rep(i, n) {
    scanf("%s", s);
    rep(j, n) if (s[j] == '1') e[i].upd(j);
  }
  rep(s, n) {
    vis.cl();
    int st = 0, ed = 1; qu[st] = s;
    rep(i, n) dis[s][i] = inf; dis[s][s] = 0; vis.upd(s);
    while (st < ed) {
      int u = qu[st++];
      rep(i, 64) {
        ull x = e[u].d[i] & vis.d[i];
        while (x) {
          int y = __builtin_ctzll(x) | (i << 6);
          x ^= x & -x;
          qu[ed++] = y;
          vis.upd(y);
          dis[s][y] = dis[s][u] + 1;
        }
      }
    }
  }
  rep(qq, q) {
    printf("%d\n", dis[getint() - 1][getint() - 1]);
  }
  return 0;
}
文章作者: ruogu
文章链接: http://ruogu-alter.github.io/2020/05/16/2018syc%EF%BC%88%E4%B8%80%EF%BC%89/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ruogu's blog！
总结
评论
簡