求随机的
最开始的思路是 int
范围内,但是
关于具体的证明,准备在补完 ABC266Ex,写完可持久化文艺平衡树和序列加强版之后再去补生成函数相关内容。
xxxxxxxxxx
871
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24template < typename T = int >
25inline T read(void);
26
27int N;
28// ld dp[2][1100][1100];
29// ll dp[1100];
30// ll tot[1100];
31// ld dp[1100];
32
33int main(){
34 freopen("tree.in", "r", stdin);
35 freopen("tree.out", "w", stdout);
36 N = read();
37 // dp[1][1][0] = 1.0;
38 // for(int i = 2; i <= N; ++i){
39 // ll base(0);
40 // for(int j = 0; j <= i; ++j)for(int k = 0; k <= i; ++k)if(dp[!(i & 1)][j][k])base += 2 * j + k;
41 // for(int j = 0; j <= i; ++j){
42 // for(int k = 0; k <= i; ++k){
43 // dp[i & 1][j][k] = 0.0;
44 // if(k - 1 >= 0)dp[i & 1][j][k] += (2.0 * j / base) * dp[!(i & 1)][j][k - 1],
45 // printf("upd i = %d, j = %d, k = %d, from %.5Lf\n", i, j, k, dp[!(i & 1)][j][k - 1]);
46 // if(j - 1 >= 0)dp[i & 1][j][k] += ((k + 1.0) / base) * dp[!(i & 1)][j - 1][k + 1];
47 // }
48 // }
49 // }
50 // ld ans(0.0);
51 // for(int j = 0; j <= N; ++j)for(int k = 0; k <= N; ++k)ans += dp[N & 1][j][k] * j;
52 // printf("%.9Lf\n", ans);
53
54 // dp[1] = 1.0;
55 // for(int i = 2; i <= N; ++i)
56 // for(int j = 0; j <= i; ++j)
57 // if(i - j - 1 >= 0)
58 // dp[i] += (dp[j] + dp[i - j - 1])
59 // printf("%.9Lf\n", (ld)((__float128)dp[N] / tot[N]));
60
61 // dp[1] = 1, tot[0] = tot[1] = 1;
62 // for(int i = 2; i <= N; ++i)
63 // for(int j = 0; j <= i; ++j)
64 // if(i - j - 1 >= 0)
65 // dp[i] += dp[j] * tot[i - j - 1] + dp[i - j - 1] * tot[j],
66 // tot[i] += tot[j] * tot[i - j - 1];
67 // for(int i = 0; i <= N; ++i)printf("dp is %lld, tot is %lld\n", dp[i], tot[i]);
68 printf("%.10Lf\n", (((ld)N * N + N) / (4 * N - 2)));
69 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
70 return 0;
71}
72
73template < typename T >
74inline T read(void){
75 T ret(0);
76 int flag(1);
77 char c = getchar();
78 while(c != '-' && !isdigit(c))c = getchar();
79 if(c == '-')flag = -1, c = getchar();
80 while(isdigit(c)){
81 ret *= 10;
82 ret += int(c - '0');
83 c = getchar();
84 }
85 ret *= flag;
86 return ret;
87}
给定
以前没见过这种套路,想了一会能想到的只有离线下来 Tarjan 求 LCA,这样最终复杂度是
然后最后耗时
xxxxxxxxxx
1011
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24template < typename T = int >
25inline T read(void);
26
27struct Edge{
28 Edge* nxt;
29 int to;
30 OPNEW;
31}ed[21000];
32ROPNEW;
33Edge* head[11000];
34
35int N, M;
36int cnt(0);
37int dep[11000];
38ll ans[11000];
39struct Query{short p; int idx;};
40basic_string < Query > qs[11000];
41bitset < 11000 > vis;
42int lca[110000000];
43struct Q{int l, r, z;}q[11000];
44
45class UnionFind{
46private:
47 int fa[11000];
48public:
49 UnionFind(void){for(int i = 1; i <= 10000; ++i)fa[i] = i;}
50 int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
51 void Union(int x, int y){fa[Find(y)] = Find(x);}
52}uf;
53
54void dfs(int p = 1, int fa = 0){
55 dep[p] = dep[fa] + 1;
56 for(auto i = head[p]; i; i = i->nxt)if(SON != fa)dfs(SON, p);
57}
58void Tarjan(int p = 1, int fa = 0){
59 vis[p] = true;
60 for(auto i = head[p]; i; i = i->nxt)if(SON != fa)Tarjan(SON, p), uf.Union(p, SON);
61 for(auto q : qs[p])if(vis[q.p])lca[q.idx] = uf.Find(q.p);
62}
63
64int main(){
65 freopen("eert.in", "r", stdin);
66 freopen("eert.out", "w", stdout);
67 N = read(), M = read();
68 for(int i = 2; i <= N; ++i){
69 int s = i, t = read();
70 head[s] = new Edge{head[s], t};
71 head[t] = new Edge{head[t], s};
72 }dfs();
73 for(int i = 1; i <= M; ++i){
74 q[i].l = read(), q[i].r = read(), q[i].z = read();
75 for(int p = q[i].l; p <= q[i].r; ++p)qs[q[i].z] += Query{(short)p, ++cnt}, qs[p] += Query{(short)q[i].z, cnt};
76 }Tarjan();
77 int cur(0);
78 for(int i = 1; i <= M; ++i){
79 for(int ccnt = cur + 1; ccnt <= cur + (q[i].r - q[i].l + 1); ++ccnt)ans[i] += dep[lca[ccnt]];
80 cur += (q[i].r - q[i].l + 1);
81 }
82 for(int i = 1; i <= M; ++i)printf("%lld\n", ans[i]);
83 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
84 return 0;
85}
86
87template < typename T >
88inline T read(void){
89 T ret(0);
90 int flag(1);
91 char c = getchar();
92 while(c != '-' && !isdigit(c))c = getchar();
93 if(c == '-')flag = -1, c = getchar();
94 while(isdigit(c)){
95 ret *= 10;
96 ret += int(c - '0');
97 c = getchar();
98 }
99 ret *= flag;
100 return ret;
101}
LG-P6621 [省选联考 2020 A 卷] 魔法商店。
及其阴间的保序回归,经典 @sssmzy 组的模拟赛中的科技题,感觉暴力都不是很可写,跳了跳了。
上面提过了,long long
。
xxxxxxxxxx
481
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22template < typename T = int >
23inline T read(void);
24
25int N;
26
27int main(){
28 N = read();
29 printf("%.10Lf\n", (((ld)N * N + N) / (4ll * N - 2)));
30 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
31 return 0;
32}
33
34template < typename T >
35inline T read(void){
36 T ret(0);
37 int flag(1);
38 char c = getchar();
39 while(c != '-' && !isdigit(c))c = getchar();
40 if(c == '-')flag = -1, c = getchar();
41 while(isdigit(c)){
42 ret *= 10;
43 ret += int(c - '0');
44 c = getchar();
45 }
46 ret *= flag;
47 return ret;
48}
正解看到之后会发现非常显然,但是如果要直接想却不太容易想到,应该算是一种套路。
考虑对区间
不难想到 树剖 + 线段树 维护,这样的复杂度是
于是考虑将询问转成差分形式,即拆成
需要注意本题点的编号的问题。
xxxxxxxxxx
1481
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24template < typename T = int >
25inline T read(void);
26
27struct Edge{
28 Edge* nxt;
29 int to;
30 OPNEW;
31}ed[110000];
32ROPNEW;
33Edge* head[51000];
34
35int N, M;
36struct Query{
37 int endp;
38 int val;
39 int idx;
40 bool flag; //false -> [1, l - 1], true -> [1, r]
41};
42basic_string < Query > qs;
43ll ans[51000];
44
45class SegTree{
46private:
47 ll tr[51000 << 2];
48 ll lz[51000 << 2];
49
50
51
52public:
53 void Pushup(int p){tr[p] = (tr[LS] + tr[RS]) % MOD;}
54 void Pushdown(int p, int gl, int gr){
55 if(!lz[p])return;
56 (lz[LS] += lz[p]) %= MOD, (lz[RS] += lz[p]) %= MOD;
57 (tr[LS] += lz[p] * (MID - gl + 1) % MOD) %= MOD, (tr[RS] += lz[p] * (gr - (MID + 1) + 1) % MOD) %= MOD;
58 lz[p] = 0;
59 }
60 ll Query(int l, int r, int p = 1, int gl = 1, int gr = N){
61 if(l <= gl && gr <= r)return tr[p];
62 if(gr < l || r < gl)return 0;
63 Pushdown(p, gl, gr);
64 return (Query(l, r, LS, gl, MID) + Query(l, r, RS, MID + 1, gr)) % MOD;
65 }
66 void Modify(int l, int r, int v = 1, int p = 1, int gl = 1, int gr = N){
67 if(l <= gl && gr <= r)return (tr[p] += (gr - gl + 1) * v % MOD) %= MOD, (lz[p] += v) %= MOD, void();
68 Pushdown(p, gl, gr);
69 if(l <= MID)Modify(l, r, v, LS, gl, MID);
70 if(MID + 1 <= r)Modify(l, r, v, RS, MID + 1, gr);
71 Pushup(p);
72 }
73}st;
74
75int dep[51000], dfn[51000], fa[51000], hson[51000], siz[51000], top[51000], idx[51000];
76
77void dfs_pre(int p = 1, int ffa = 0){
78 fa[p] = ffa;
79 dep[p] = dep[ffa] + 1;
80 siz[p] = 1;
81 for(auto i = head[p]; i; i = i->nxt){
82 if(SON == ffa)continue;
83 dfs_pre(SON, p);
84 siz[p] += siz[SON];
85 if(siz[SON] > siz[hson[p]])hson[p] = SON;
86 }
87}
88void dfs_make(int p = 1, int tp = 1){
89 top[p] = tp;
90 static int cdfn(0);
91 dfn[p] = ++cdfn;
92 idx[cdfn] = p;
93 if(hson[p])dfs_make(hson[p], tp);
94 for(auto i = head[p]; i; i = i->nxt){
95 if(SON == fa[p] || SON == hson[p])continue;
96 dfs_make(SON, SON);
97 }
98}
99void ModifyTree(int p){
100 while(top[p] != 1)
101 st.Modify(dfn[top[p]], dfn[p]), p = fa[top[p]];
102 st.Modify(1, dfn[p]);
103}
104ll QueryTree(int p){
105 ll ret(0);
106 while(top[p] != 1)
107 (ret += st.Query(dfn[top[p]], dfn[p])) %= MOD, p = fa[top[p]];
108 (ret += st.Query(1, dfn[p])) %= MOD;
109 return ret;
110}
111
112int main(){
113 N = read(), M = read();
114 for(int i = 2; i <= N; ++i){
115 int s = i, t = read() + 1;
116 head[s] = new Edge{head[s], t};
117 head[t] = new Edge{head[t], s};
118 }dfs_pre(), dfs_make();
119 for(int i = 1; i <= M; ++i){
120 int l = read() + 1, r = read() + 1, p = read() + 1;
121 qs += {Query{l - 1, p, i, false}, Query{r, p, i, true}};
122 }sort(qs.begin(), qs.end(), [](const Query &a, const Query &b)->bool{return a.endp < b.endp;});
123 int cur(0);
124 for(auto q : qs){
125 for(int i = cur + 1; i <= q.endp; ++i)ModifyTree(i);
126 cur = q.endp;
127 ans[q.idx] += (q.flag ? 1 : -1) * QueryTree(q.val);
128 }
129 for(int i = 1; i <= M; ++i)printf("%lld\n", (ans[i] % MOD + MOD) % MOD);
130 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
131 return 0;
132}
133
134template < typename T >
135inline T read(void){
136 T ret(0);
137 int flag(1);
138 char c = getchar();
139 while(c != '-' && !isdigit(c))c = getchar();
140 if(c == '-')flag = -1, c = getchar();
141 while(isdigit(c)){
142 ret *= 10;
143 ret += int(c - '0');
144 c = getchar();
145 }
146 ret *= flag;
147 return ret;
148}
跳!
update-2023_01_12 初稿