AtCoder Beginner Contest 266 Solution更好的阅读体验戳此进入题面链接题面 Luogu 链接abcd 都没什么可说的[ABC266E] Throwing the Die题面SolutionCode[ABC266F] Well-defined Path Queries on a Namori题面SolutionCode[ABC266G] Yet Another RGB Sequence题面SolutionCode[ABC266Ex] Snuke Panic (2D)题面SolutionCodeUPD
你有一个普通均匀的正方体骰子,六个面写有
给定
十分显然且简单的 期望DP。令
答案即
xxxxxxxxxx
521
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;
26ld dp[110];
27
28int main(){
29 N = read();
30 for(int i = 1; i <= N; ++i)
31 for(int j = 1; j <= 6; ++j)
32 dp[i] += dp[i - 1] > j ? dp[i - 1] / 6.0 : j / 6.0;
33 printf("%.8Lf\n", dp[N]);
34 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
35 return 0;
36}
37
38template < typename T >
39inline T read(void){
40 T ret(0);
41 int flag(1);
42 char c = getchar();
43 while(c != '-' && !isdigit(c))c = getchar();
44 if(c == '-')flag = -1, c = getchar();
45 while(isdigit(c)){
46 ret *= 10;
47 ret += int(c - '0');
48 c = getchar();
49 }
50 ret *= flag;
51 return ret;
52}
给定一张有
如果路径上的各顶点均不重复,则称这样的路径为简单路径。
思路比较容易想到。
根据定义显然为基环树,考虑发现若两点在树上路径经过环那么有多条,反之有且仅有一条。
最开始的思路是断环然后树剖加线段树查有没有环上的点,但是想了一下好像不用这么麻烦。
直接对环标记,对环上每个点进行染色并从非环边搜索下去继续染色,这样如果查询两个点颜色不同的需跨环,反之则不用,跑一下即可。
复杂度应该是
xxxxxxxxxx
881
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
25struct Edge{
26 Edge* nxt;
27 int to;
28 bool blocked;
29 OPNEW;
30}ed[410000];
31ROPNEW;
32Edge* head[210000];
33
34int N;
35int deg[210000];
36bitset < 210000 > inloop;
37int col[210000], cnt(0);
38basic_string < int > loop;
39
40void dfs(int p, int ccol, int fa = 0){
41 col[p] = ccol;
42 for(auto i = head[p]; i; i = i->nxt)
43 if(!i->blocked && SON != fa)dfs(SON, ccol, p);
44}
45
46int main(){
47 inloop.set();
48 N = read();
49 for(int i = 1; i <= N; ++i){
50 int s = read(), t = read();
51 head[s] = new Edge{head[s], t, false};
52 head[t] = new Edge{head[t], s, false};
53 ++deg[s], ++deg[t];
54 }queue < int > cur;
55 for(int i = 1; i <= N; ++i)if(deg[i] == 1)cur.push(i), inloop[i] = false;
56 while(!cur.empty()){
57 int p = cur.front(); cur.pop();
58 for(auto i = head[p]; i; i = i->nxt)
59 if(inloop[SON] && --deg[SON] == 1)
60 inloop[SON] = false, cur.push(SON);
61 }
62 for(int i = 1; i <= N; ++i)if(inloop[i])loop += i;
63 for(auto p : loop)for(auto i = head[p]; i; i = i->nxt)if(inloop[SON])i->blocked = true;
64 for(auto p : loop)dfs(p, ++cnt);
65 int Q = read();
66 while(Q--){
67 int s = read(), t = read();
68 printf("%s\n", !(col[s] ^ col[t]) ? "Yes" : "No");
69 }
70 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
71 return 0;
72}
73
74template < typename T >
75inline T read(void){
76 T ret(0);
77 int flag(1);
78 char c = getchar();
79 while(c != '-' && !isdigit(c))c = getchar();
80 if(c == '-')flag = -1, c = getchar();
81 while(isdigit(c)){
82 ret *= 10;
83 ret += int(c - '0');
84 c = getchar();
85 }
86 ret *= flag;
87 return ret;
88}
求符合要求的字符串个数,对
满足要求的字符串
r
、g
、b
构成。r
,g
,b
,rg
。大概就是我们根据组合意义去考虑,一种思路是先从
一种思路是考虑先插入
这东西复杂度显然是
然后还有二项式反演的思路,类似于前者去掉
xxxxxxxxxx
671
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
27ll R, G, B, K;
28ll qpow(ll a, ll b){
29 ll ret(1), mul(a);
30 while(b){
31 if(b & 1)ret = ret * mul % MOD;
32 b >>= 1;
33 mul = mul * mul % MOD;
34 }return ret;
35}
36ll GetC(ll n, ll m){
37 if(m > n)return 0;
38 ll ret(1);
39 for(int i = 1; i <= n; ++i)(ret *= i) %= MOD;
40 ll div(1);
41 for(int i = 1; i <= m; ++i)(div *= i) %= MOD;
42 for(int i = 1; i <= n - m; ++i)(div *= i) %= MOD;
43 return ret * qpow(div, MOD - 2) % MOD;
44}
45
46int main(){
47 R = read(), G = read(), B = read(), K = read();
48 printf("%lld\n", GetC(G + B, G) * GetC(G, K) % MOD * GetC(R + B, R - K) % MOD);
49 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
50 return 0;
51}
52
53template < typename T >
54inline T read(void){
55 T ret(0);
56 int flag(1);
57 char c = getchar();
58 while(c != '-' && !isdigit(c))c = getchar();
59 if(c == '-')flag = -1, c = getchar();
60 while(isdigit(c)){
61 ret *= 10;
62 ret += int(c - '0');
63 c = getchar();
64 }
65 ret *= flag;
66 return ret;
67}
二维平面直角坐标系中,你初始位于
类比 ABC266D 考虑朴素 DP,显然我们可以认为对于无收益的点是无意义的,所以我们可以采用离散化的思想,令
这里的
显然
移项一下:
于是就变成了经典的三位偏序问题,我们将
这里我们考虑使用 BIT套BIT,即 二维BIT 解决。
注意虽然 BIT 是不支持区间
同时注意需要对其全部离散化。
还有一个细节就是在 BIT 里维护的下标是离散化后的值,值则为对应的
然后还有一个很重要的细节就是对于
还没完,还有一个细节,就是排序的时候不能只排
xxxxxxxxxx
951
2
3
4
5
6
7
8
9
10using namespace std;
11
12mt19937 rnd(random_device{}());
13int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
14bool rnddd(int x){return rndd(1, 100) <= x;}
15
16typedef unsigned int uint;
17typedef unsigned long long unll;
18typedef long long ll;
19typedef long double ld;
20
21template < typename T = int >
22inline T read(void);
23
24int N;
25ll ans(0);
26
27struct Earn{
28 ll t;
29 ll x, y;
30 ll v;
31 ll ftmp1, ftmp2;
32};
33basic_string < Earn > E;
34basic_string < ll > data1, data2;
35
36class BIT_D1{
37private:
38 unordered_map < int, ll > tr;
39public:
40 int lowbit(int x){return x & -x;}
41 void Modify(int x, ll v/*ftmp2, dp(j)*/){while(x <= N)tr[x] = max(tr[x], v), x += lowbit(x);}
42 ll Query(int x){ll ret(0); while(x)ret = max(ret, tr[x]), x-= lowbit(x); return ret;}
43};
44class BIT_D2{
45private:
46 unordered_map < int, BIT_D1 > tr;
47public:
48 int lowbit(int x){return x & -x;}
49 void Modify(int x1, int x2, ll v/*ftmp1, ftmp2, dp(j)*/){while(x1 <= N)tr[x1].Modify(x2, v), x1 += lowbit(x1);}
50 ll Query(int x1, int x2){ll ret(0); while(x1)ret = max(ret, tr[x1].Query(x2)), x1 -= lowbit(x1); return ret;}
51}bit;
52
53int main(){
54 // freopen("in.txt", "r", stdin);
55 // freopen("out.txt", "w", stdout);
56 N = read();
57 for(int i = 1; i <= N; ++i){
58 int t = read(), x = read(), y = read(), v = read();
59 if(t - x - y < 0)continue;
60 E += {t, x, y, v, t - x - y, t + x - y};
61 data1 += t - x - y, data2 += t + x - y;
62 }
63 sort(E.begin(), E.end(), [](const Earn &a, const Earn &b)->bool{
64 if(a.y != b.y)return a.y < b.y;
65 if(a.ftmp1 != b.ftmp1)return a.ftmp1 < b.ftmp1;
66 return a.ftmp2 < b.ftmp2;
67 });
68 sort(data1.begin(), data1.end()), sort(data2.begin(), data2.end());
69 for(auto &e : E)
70 e.ftmp1 = distance(data1.begin(), lower_bound(data1.begin(), data1.end(), e.t - e.x - e.y)) + 1,
71 e.ftmp2 = distance(data2.begin(), lower_bound(data2.begin(), data2.end(), e.t + e.x - e.y)) + 1;
72 for(auto e : E){
73 ll ret = bit.Query(e.ftmp1, e.ftmp2) + e.v;
74 ans = max(ans, ret);
75 bit.Modify(e.ftmp1, e.ftmp2, ret);
76 }printf("%lld\n", ans);
77 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
78 return 0;
79}
80
81template < typename T >
82inline T read(void){
83 T ret(0);
84 int flag(1);
85 char c = getchar();
86 while(c != '-' && !isdigit(c))c = getchar();
87 if(c == '-')flag = -1, c = getchar();
88 while(isdigit(c)){
89 ret *= 10;
90 ret += int(c - '0');
91 c = getchar();
92 }
93 ret *= flag;
94 return ret;
95}
update-2023_01_12 初稿