杂题小记(2023.03.01)更好的阅读体验戳此进入[ARC084D] Small Multiple题面SolutionCodeLG-P2371 [国家集训队]墨墨的等式题面SolutionCodeLG-P2158 [SDOI2008] 仪仗队题面SolutionCodeLG-P2568 GCD题面SolutionCodeCF600E Lomsat gelral题面SolutionCodeLG-P4777 【模板】扩展中国剩余定理(EXCRT)题面SolutionCodeCF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths题面SolutionCodeCF1009F Dominant Indices题面SolutionCodeUPD
给定
依然考虑类似同余最短路的思路,每个点表示模
xxxxxxxxxx
711
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23template < typename T = int >
24inline T read(void);
25
26int K;
27bitset < 110000 > vis;
28int dis[110000];
29
30void bfs(void){
31 memset(dis, 0x3f, sizeof dis);
32 deque < int > cur;
33 vis[1] = true, dis[1] = 1;
34 cur.push_front(1);
35 while(!cur.empty()){
36 int p = cur.front(); cur.pop_front();
37 if(auto val = p * 10 % K; !vis[val]){
38 vis[val] = true;
39 dis[val] = min(dis[val], dis[p]);
40 cur.push_front(val);
41 }
42 if(auto val = (p + 1) % K; !vis[val]){
43 dis[val] = min(dis[val], dis[p] + 1);
44 cur.push_back(val);
45 }
46 }
47}
48
49int main(){
50 K = read();
51 bfs();
52 printf("%d\n", dis[0]);
53 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54 return 0;
55}
56
57template < typename T >
58inline T read(void){
59 T ret(0);
60 int flag(1);
61 char c = getchar();
62 while(c != '-' && !isdigit(c))c = getchar();
63 if(c == '-')flag = -1, c = getchar();
64 while(isdigit(c)){
65 ret *= 10;
66 ret += int(c - '0');
67 c = getchar();
68 }
69 ret *= flag;
70 return ret;
71}
给定序列
经典同余最短路,和跳楼机那题没什么区别,对
xxxxxxxxxx
941
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template < typename T = int >
26inline T read(void);
27
28struct Edge{
29 Edge* nxt;
30 int to;
31 ll val;
32 OPNEW;
33}ed[7100000];
34ROPNEW;
35Edge* head[510000];
36
37int N;
38int P;
39ll l, r;
40int A[510000];
41ll dis[510000];
42ll ans(0);
43bitset < 510000 > vis;
44
45void Dijkstra(void){
46 memset(dis, 0x3f, sizeof dis);
47 priority_queue < pair < ll, int >, vector < pair < ll, int > >, greater < pair < ll, int > > > cur;
48 dis[0] = 0, cur.push({0, 0});
49 while(!cur.empty()){
50 int p = cur.top().second; cur.pop();
51 if(vis[p])continue;
52 vis[p] = true;
53 for(auto i = head[p]; i; i = i->nxt)
54 if(dis[SON] > dis[p] + i->val)
55 dis[SON] = dis[p] + i->val, cur.push({dis[SON], SON});
56 }
57}
58
59int main(){
60 N = read(), l = read < ll >(), r = read < ll >();
61 for(int i = 1; i <= N; ++i)A[i] = read();
62 P = A[1];
63 for(int i = 0; i < P; ++i)
64 for(int j = 2; j <= N; ++j)
65 head[i] = new Edge{head[i], (i + A[j]) % P, A[j]};
66 Dijkstra();
67 ll H = r;
68 for(int i = 0; i < P; ++i)
69 if(H >= dis[i])
70 ans += (H - dis[i]) / P + 1;
71 H = l - 1;
72 for(int i = 0; i < P; ++i)
73 if(H >= dis[i])
74 ans -= (H - dis[i]) / P + 1;
75 printf("%lld\n", ans);
76 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
77 return 0;
78}
79
80template < typename T >
81inline T read(void){
82 T ret(0);
83 int flag(1);
84 char c = getchar();
85 while(c != '-' && !isdigit(c))c = getchar();
86 if(c == '-')flag = -1, c = getchar();
87 while(isdigit(c)){
88 ret *= 10;
89 ret += int(c - '0');
90 c = getchar();
91 }
92 ret *= flag;
93 return ret;
94}
作为体育委员,C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的
现在,C 君希望你告诉他队伍整齐时能看到的学生人数。
不难发现答案转化为求所有横纵坐标在
线性筛欧拉函数即可。
xxxxxxxxxx
661
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template < typename T = int >
26inline T read(void);
27
28int N;
29int phi[LIM + 100];
30int ans(0);
31basic_string < int > Prime;
32bitset < LIM + 100 > notPrime;
33
34int main(){phi[1] = 1;
35 for(int i = 2; i <= LIM; ++i){
36 if(!notPrime[i])Prime += i, phi[i] = i - 1;
37 for(auto p : Prime){
38 if(i * p > LIM)break;
39 phi[i * p] = i % p ? phi[i] * phi[p] : p * phi[i];
40 notPrime[i * p] = true;
41 if(i % p == 0)break;
42 }
43 }
44 N = read();
45 if(N == 1)printf("0\n"), exit(0);
46 for(int i = 1; i <= N - 1; ++i)ans += phi[i] * 2;
47 printf("%d\n", ans + 1);
48 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
49 return 0;
50}
51
52template < typename T >
53inline T read(void){
54 T ret(0);
55 int flag(1);
56 char c = getchar();
57 while(c != '-' && !isdigit(c))c = getchar();
58 if(c == '-')flag = -1, c = getchar();
59 while(isdigit(c)){
60 ret *= 10;
61 ret += int(c - '0');
62 c = getchar();
63 }
64 ret *= flag;
65 return ret;
66}
给定
我们令
然后问题就转化为了 LG-P2158 [SDOI2008] 仪仗队,预处理一下即可。
xxxxxxxxxx
691
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template < typename T = int >
26inline T read(void);
27
28int N;
29int phi[LIM + 100];
30ll ans(0);
31ll sum[LIM + 100];
32basic_string < int > Prime;
33bitset < LIM + 100 > notPrime;
34
35int main(){phi[1] = 1, notPrime[1] = true;
36 for(int i = 2; i <= LIM; ++i){
37 if(!notPrime[i])Prime += i, phi[i] = i - 1;
38 for(auto p : Prime){
39 if((ll)i * p > LIM)break;
40 phi[i * p] = i % p ? phi[i] * phi[p] : p * phi[i];
41 notPrime[i * p] = true;
42 if(i % p == 0)break;
43 }
44 }N = read();
45 for(int i = 1; i <= N; ++i)sum[i] = sum[i - 1] + phi[i] * 2;
46 for(auto p : Prime){
47 if(p > N)break;
48 ans += sum[N / p] - 1;
49 }
50 printf("%lld\n", ans);
51 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
52 return 0;
53}
54
55template < typename T >
56inline T read(void){
57 T ret(0);
58 int flag(1);
59 char c = getchar();
60 while(c != '-' && !isdigit(c))c = getchar();
61 if(c == '-')flag = -1, c = getchar();
62 while(isdigit(c)){
63 ret *= 10;
64 ret += int(c - '0');
65 c = getchar();
66 }
67 ret *= flag;
68 return ret;
69}
给定节点染色的树,对于每个节点询问其子树出现次数最多的颜色,有多个则输出颜色编号和。
dot 模板题,注意更新最大颜色时的一些细节即可。
xxxxxxxxxx
1051
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template < typename T = int >
26inline T read(void);
27
28int N;
29struct Edge{
30 Edge* nxt;
31 int to;
32 OPNEW;
33}ed[210000];
34ROPNEW;
35Edge* head[110000];
36int col[110000];
37int siz[110000], hson[110000];
38int cnt[110000];
39ll ans[110000];
40int mxp(0);
41ll mxv(0);
42queue < int > trash;
43
44void dfs_pre(int p = 1, int fa = 0){
45 siz[p] = 1;
46 for(auto i = head[p]; i; i = i->nxt){
47 if(SON == fa)continue;
48 dfs_pre(SON, p);
49 siz[p] += siz[SON];
50 if(siz[SON] > siz[hson[p]])hson[p] = SON;
51 }
52}
53void Insert(int p){
54 ++cnt[col[p]], trash.push(col[p]);
55 if(mxp == col[p] || cnt[col[p]] > cnt[mxp])mxp = col[p], mxv = col[p];
56 else if(cnt[col[p]] == cnt[mxp])mxv += col[p];
57}
58void InsertSubt(int p, int fa){
59 Insert(p);
60 for(auto i = head[p]; i; i = i->nxt)
61 if(SON != fa)InsertSubt(SON, p);
62}
63void RemoveAll(void){
64 while(!trash.empty())--cnt[trash.front()], trash.pop();
65 mxp = mxv = 0;
66}
67void dfs_make(int p = 1, int fa = 0){
68 for(auto i = head[p]; i; i = i->nxt)
69 if(SON != fa && SON != hson[p])
70 dfs_make(SON, p), RemoveAll();
71 if(hson[p])dfs_make(hson[p], p);
72 for(auto i = head[p]; i; i = i->nxt)
73 if(SON != fa && SON != hson[p])
74 InsertSubt(SON, p);
75 Insert(p), ans[p] = mxv;
76}
77
78int main(){
79 N = read();
80 for(int i = 1; i <= N; ++i)col[i] = read();
81 for(int i = 1; i <= N - 1; ++i){
82 int s = read(), t = read();
83 head[s] = new Edge{head[s], t};
84 head[t] = new Edge{head[t], s};
85 }dfs_pre(), dfs_make();
86 for(int i = 1; i <= N; ++i)printf("%lld%c", ans[i], i == N ? '\n' : ' ');
87 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
88 return 0;
89}
90
91template < typename T >
92inline T read(void){
93 T ret(0);
94 int flag(1);
95 char c = getchar();
96 while(c != '-' && !isdigit(c))c = getchar();
97 if(c == '-')flag = -1, c = getchar();
98 while(isdigit(c)){
99 ret *= 10;
100 ret += int(c - '0');
101 c = getchar();
102 }
103 ret *= flag;
104 return ret;
105}
同余式:
但是不满足
求
虽然是 exCRT 但是除了问题相似之外与 CRT 似乎没什么关系。
首先考虑存在两个同余方程:
考虑对于线性同余方程的常规转化:
有:
可以用 exgcd 求得
所以现在我们以
Tips:读到这里不难发现,若不满足
于是此时我们可以根据
此时两个方程被合成为了同一个,直到最终仅剩一个方程时其解即为答案。
xxxxxxxxxx
741
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23template < typename T = int >
24inline T read(void);
25
26void exgcd(__int128_t a, __int128_t b, __int128_t &x, __int128_t &y){
27 if(!b)return x = 1, y = 0, void();
28 exgcd(b, a % b, x, y);
29 __int128_t tmp(x);
30 x = y;
31 y = tmp - a / b * y;
32}
33void Query(__int128_t a, __int128_t b, __int128_t &x, __int128_t &y, __int128_t c){
34 exgcd(a, b, x, y);
35 __int128_t d = c / __gcd(a, b);
36 x *= d, y *= d;
37 __int128_t val = b / __gcd(a, b);
38 x = (x % val + val) % val;
39 y = (c - a * x) - b;
40}
41
42int N;
43__int128_t rem1(-1), mod1(-1);
44
45int main(){
46 N = read();
47 while(N--){
48 __int128_t mod2 = read < ll >(), rem2 = read < ll >();
49 if(!~rem1 || !~mod1){rem1 = rem2, mod1 = mod2; continue;}
50 __int128_t b1, b2;
51 Query(mod1, -mod2, b1, b2, rem2 - rem1);
52 rem1 = rem1 + b1 * mod1;
53 mod1 = mod1 * mod2 / __gcd(mod1, mod2);
54 rem1 = (rem1 % mod1 + mod1) % mod1;
55 }printf("%lld\n", rem1);
56 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
57 return 0;
58}
59
60template < typename T >
61inline T read(void){
62 T ret(0);
63 int flag(1);
64 char c = getchar();
65 while(c != '-' && !isdigit(c))c = getchar();
66 if(c == '-')flag = -1, c = getchar();
67 while(isdigit(c)){
68 ret *= 10;
69 ret += int(c - '0');
70 c = getchar();
71 }
72 ret *= flag;
73 return ret;
74}
给定树,边权为
属于是 dot 里难度较高的题了。
最开始以为求的是子树所有边的答案,光速糊了一个上去然后第三个点就挂了,又看了一遍题才发现这东西求的是路径。。
该说不说这个题意看着总有点像点分治。
首先考虑回文串的性质,不难发现只要满足对于所有种类的字符,最多有一种字符数量为奇数则可以构成回文串,且发现共
而对于两个状态的合并,也不难发现满足异或的性质。
于是我们考虑记
发现共需要讨论三种情况,子树内的路径,一个端点在子树根的路径,两个端点都在子树内但经过子树根的路径。
对于后两种的维护,考虑记录
xxxxxxxxxx
1101
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template < typename T = int >
26inline T read(void);
27
28int N;
29struct Edge{
30 Edge* nxt;
31 int to;
32 OPNEW;
33}ed[1100000];
34ROPNEW;
35Edge* head[510000];
36int dep[510000], siz[510000], hson[510000];
37int ans[510000];
38int mxdep[4500000], status[510000];
39
40void dfs_pre(int p = 1, int fa = 0){
41 siz[p] = 1, dep[p] = dep[fa] + 1, status[p] ^= status[fa];
42 for(auto i = head[p]; i; i = i->nxt){
43 if(SON == fa)continue;
44 dfs_pre(SON, p);
45 siz[p] += siz[SON];
46 if(siz[SON] > siz[hson[p]])hson[p] = SON;
47 }
48}
49void ClearAll(int p, int fa){
50 mxdep[status[p]] = -INF;
51 for(auto i = head[p]; i; i = i->nxt)
52 if(SON != fa)ClearAll(SON, p);
53}
54void Update(int p, int fa, int rt){
55 ans[rt] = max(ans[rt], dep[p] + mxdep[status[p]]);
56 for(int i = 0; i <= 21; ++i)ans[rt] = max(ans[rt], dep[p] + mxdep[status[p] ^ (1 << i)]);
57 for(auto i = head[p]; i; i = i->nxt)
58 if(SON != fa)Update(SON, p, rt);
59}
60void Insert(int p, int fa){
61 mxdep[status[p]] = max(mxdep[status[p]], dep[p]);
62 for(auto i = head[p]; i; i = i->nxt)
63 if(SON != fa)Insert(SON, p);
64}
65void dfs_make(int p = 1, int fa = 0){
66 for(auto i = head[p]; i; i = i->nxt)
67 if(SON != fa && SON != hson[p])dfs_make(SON, p), ClearAll(SON, p);
68 if(hson[p])dfs_make(hson[p], p);
69 for(auto i = head[p]; i; i = i->nxt)
70 if(SON != fa && SON != hson[p])Update(SON, p, p), Insert(SON, p);
71 mxdep[status[p]] = max(mxdep[status[p]], dep[p]);
72 ans[p] = max(ans[p], dep[p] + mxdep[status[p]]);
73 for(int i = 0; i <= 21; ++i)
74 ans[p] = max(ans[p], dep[p] + mxdep[status[p] ^ (1 << i)]);
75 ans[p] -= dep[p] << 1;
76 for(auto i = head[p]; i; i = i->nxt)
77 if(SON != fa)ans[p] = max(ans[p], ans[SON]);
78}
79
80int main(){
81 for(int i = 0; i < 4500000; ++i)mxdep[i] = -INF;
82 N = read();
83 for(int i = 2; i <= N; ++i){
84 int s = read(), t = i;
85 char c = getchar(); while(!islower(c))c = getchar();
86 status[t] = 1 << (c - 'a');
87 head[s] = new Edge{head[s], t};
88 head[t] = new Edge{head[t], s};
89 }dfs_pre(), dfs_make();
90
91 for(int i = 1; i <= N; ++i)printf("%d%c", ans[i], i == N ? '\n' : ' ');
92 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
93 return 0;
94}
95
96template < typename T >
97inline T read(void){
98 T ret(0);
99 int flag(1);
100 char c = getchar();
101 while(c != '-' && !isdigit(c))c = getchar();
102 if(c == '-')flag = -1, c = getchar();
103 while(isdigit(c)){
104 ret *= 10;
105 ret += int(c - '0');
106 c = getchar();
107 }
108 ret *= flag;
109 return ret;
110}
给定一棵以
对于每个点,求一个最小的
很板子的 dot,注意需要一个类似 CF741D 的思路,记录
xxxxxxxxxx
1021
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template < typename T = int >
26inline T read(void);
27
28int N;
29struct Edge{
30 Edge* nxt;
31 int to;
32 OPNEW;
33}ed[2100000];
34ROPNEW;
35Edge* head[1100000];
36int siz[1100000], hson[1100000], dep[1100000];
37int cnt[1100000];
38ll ans[1100000];
39int mxp(0);
40queue < int > trash;
41
42void dfs_pre(int p = 1, int fa = 0){
43 siz[p] = 1, dep[p] = dep[fa] + 1;
44 for(auto i = head[p]; i; i = i->nxt){
45 if(SON == fa)continue;
46 dfs_pre(SON, p);
47 siz[p] += siz[SON];
48 if(siz[SON] > siz[hson[p]])hson[p] = SON;
49 }
50}
51void Insert(int p){
52 ++cnt[dep[p]], trash.push(dep[p]);
53 if(cnt[dep[p]] > cnt[mxp])mxp = dep[p];
54 else if(cnt[dep[p]] == cnt[mxp])mxp = min(mxp, dep[p]);
55}
56void InsertSubt(int p, int fa){
57 Insert(p);
58 for(auto i = head[p]; i; i = i->nxt)
59 if(SON != fa)InsertSubt(SON, p);
60}
61void RemoveAll(void){
62 while(!trash.empty())--cnt[trash.front()], trash.pop();
63 mxp = 0;
64}
65void dfs_make(int p = 1, int fa = 0){
66 for(auto i = head[p]; i; i = i->nxt)
67 if(SON != fa && SON != hson[p])
68 dfs_make(SON, p), RemoveAll();
69 if(hson[p])dfs_make(hson[p], p);
70 for(auto i = head[p]; i; i = i->nxt)
71 if(SON != fa && SON != hson[p])
72 InsertSubt(SON, p);
73 Insert(p), ans[p] = mxp - dep[p];
74}
75
76int main(){
77 N = read();
78 for(int i = 1; i <= N - 1; ++i){
79 int s = read(), t = read();
80 head[s] = new Edge{head[s], t};
81 head[t] = new Edge{head[t], s};
82 }dfs_pre(), dfs_make();
83 for(int i = 1; i <= N; ++i)printf("%lld\n", ans[i]);
84 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
85 return 0;
86}
87
88template < typename T >
89inline T read(void){
90 T ret(0);
91 int flag(1);
92 char c = getchar();
93 while(c != '-' && !isdigit(c))c = getchar();
94 if(c == '-')flag = -1, c = getchar();
95 while(isdigit(c)){
96 ret *= 10;
97 ret += int(c - '0');
98 c = getchar();
99 }
100 ret *= flag;
101 return ret;
102}
update-2023_03_01 初稿