| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 11/12 | O | . | Ø | Ø | Ø | O | Ø | Ø | Ø | Ø | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
给定三个不递减数列 $a,b,c$，$n\le 5e5$，问有多少 个三元组 $(i,j,k)$ 满足 $a_i,b_j,c_k$ 两两间差值不大于 $d$。
解题思路
设 $a_i\le b_j\le c_k$，枚举最小值 $a_i$，则 $j,k$ 取值范围可以单调地求出。于是讨论谁是严格最小的即可。
AC代码
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
typedef long long ll;
using namespace std;
int a[N],b[N],c[N];
int main(){
int i,na,nb,nc,d;
while(~scanf("%d%d%d%d",&d,&na,&nb,&nc)){
for(i=0;i<na;i++)scanf("%d",&a[i]);
for(i=0;i<nb;i++)scanf("%d",&b[i]);
for(i=0;i<nc;i++)scanf("%d",&c[i]);
int al=0,ar=0,bl=0,br=0,cl=0,cr=0;
ll ans=0;
for(i=0;i<na;i++){
while(bl<nb&&b[bl]<a[i])bl++;
while(br<nb&&b[br]<=a[i]+d)br++;
while(cl<nc&&c[cl]<a[i])cl++;
while(cr<nc&&c[cr]<=a[i]+d)cr++;
ans+=1LL*(br-bl)*(cr-cl);
}
al=ar=bl=br=cl=cr=0;
for(i=0;i<nb;i++){
while(al<na&&a[al]<b[i]+1)al++;
while(ar<na&&a[ar]<=b[i]+d)ar++;
while(cl<nc&&c[cl]<b[i])cl++;
while(cr<nc&&c[cr]<=b[i]+d)cr++;
ans+=1LL*(ar-al)*(cr-cl);
}
al=ar=bl=br=cl=cr=0;
for(i=0;i<nc;i++){
while(bl<nb&&b[bl]<c[i]+1)bl++;
while(br<nb&&b[br]<=c[i]+d)br++;
while(al<na&&a[al]<c[i]+1)al++;
while(ar<na&&a[ar]<=c[i]+d)ar++;
ans+=1LL*(br-bl)*(ar-al);
}
printf("%lld\n",ans);
}
return 0;
}
B
题目描述
解题思路
AC代码
2
C
题目描述
给一棵 $n\le 1e5$ 的树和 $m\le 1e5$ 条树上路径，求一个最小集合满足没条给定树上路径都有点在该集合中。
解题思路
先考虑序列上的情况，可以贪心地做，将一个路径分成左右两个端点，从左到右扫一遍维护一个如果当前点被选则可以覆盖到的路径集合，当遇到某个右端点时选择该端点并清空集合。
在树上也是一样，合并的时候注意一下大小顺序即可。
AC代码
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
typedef long long ll;
using namespace std;
vector<int>G[N];
set<int>s[N],ans;
int cnt;
void add(int a,int b){
G[a].pb(b);
G[b].pb(a);
}
void dfs(int p,int f){
for(auto q:G[p]){
if(q==f)continue;
dfs(q,p);
if(s[q].size()>s[p].size())swap(s[p],s[q]);
for(auto x:s[q]){
if(s[p].find(x)==s[p].end())s[p].insert(x);
else ans.insert(p);
}
}
if(ans.find(p)!=ans.end()){
s[p].clear();
}
}
int main(){
int i,n,q;
scanf("%d",&n);
for(i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
scanf("%d",&q);
while(q--){
int a,b;
scanf("%d%d",&a,&b);
if(a==b)ans.insert(a);
else s[a].insert(q),s[b].insert(q);
}
dfs(1,0);
printf("%d\n",ans.size());
for(auto p:ans)printf("%d ",p);
return 0;
}
D
题目描述
有一个电梯，可以直上直下，从 $0$ 楼到任意楼层再返回 $0$ 楼，走一层耗费时间为 $1$。
有 $n\le 2e5$ 个乘客，第 $i$ 个乘客想去 $a_i$ 楼，并在 $t_i$ 时刻到达 $0$ 楼。
问电梯送所有乘客到达之后返回 $0$ 楼的最小时间。
解题思路
很明显如果有 $a_i\le a_j,t_i\le t_j$ 那么 $i$ 可以跟着 $j$ 一趟电梯走，于是可以不考虑 $i$ 点。将 $t$ 升序排，那么 $a$ 是严格递减序列。
设 $f_i$ 表示处理完第 $i$ 个乘客回到 $0$ 楼的时间，则枚举最后一趟电梯接了哪些人，有
$f_i=\min_{j=1}^{i-1}(2a_j+\max(f_{j-1},t_i))$
因此，二分出来 $f_{k-1}\ge t_i$ 的 $k$，$j<k$ 时为 $\min_{j=1}^{k-1}(2a_j+t_i)$， $j\ge k$ 时为 $\min_{j=k}^{i-1}(2a_j+f_{j-1})$，线段树维护一下这区间这两个值的 $\min$ 即可。
AC代码
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
typedef long long ll;
using namespace std;
ll a[N],t[N],f[N];
struct seg{
ll t[2][N<<2],L[N<<2],R[N<<2];
void build(int p,int l,int r){
L[p]=l;R[p]=r;
t[0][p]=t[1][p]=0;
if(l==r)return;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void pushup(int p){
for(int k=0;k<2;k++)t[k][p]=min(t[k][p<<1],t[k][p<<1|1]);
}
void m(int k,int p,int l,ll x){
if(L[p]>l||R[p]<l)return;
if(L[p]==R[p]){
t[k][p]=x;
return;
}
m(k,p<<1,l,x);
m(k,p<<1|1,l,x);
pushup(p);
}
ll q(int k,int p,int l,int r){
if(L[p]>r||R[p]<l)return 1e18;
if(L[p]>=l&&R[p]<=r)return t[k][p];
return min(q(k,p<<1,l,r),q(k,p<<1|1,l,r));
}
}segtree;
int main(){
int i,n;
while(~scanf("%d",&n)){
int top=0;
for(i=0;i<n;i++){
int tt,ta;
scanf("%d%d",&tt,&ta);
while(top&&a[top]<ta)top--;
a[++top]=ta;t[top]=tt;
}
n=top;
segtree.build(1,1,n);
f[0]=0;
segtree.m(0,1,1,2*a[1]);
segtree.m(1,1,1,2*a[1]);
for(i=1;i<=n;i++){
int index=upper_bound(f,f+i,t[i])-f-1;
ll p1=segtree.q(1,1,1,index+1)+t[i];
ll p2=segtree.q(0,1,index+1+1,i);
f[i]=min(p1,p2);
segtree.m(0,1,i+1,f[i]+2*a[i+1]);
segtree.m(1,1,i+1,2*a[i+1]);
}
printf("%lld\n",f[n]);
}
return 0;
}
E
题目描述
$n\le 5e5,m\le 1e6$ 的有向图上构造两个大小均为 $n-1$ 且不交的边集，满足 $a$ 能通过第一个边集走到任何一个点，任何一个点都能通过第二个边集走到 $b$。
解题思路
第一个边集相当于除了 $a$ 所有点入度为 $1$，第二个边集相当于除了 $b$ 所有点出度为 $1$。于是看做一个二分图，左部是 $2n$ 个点，分别表示每个点的入度和出度；右部是 $m$ 个点，代表每个边。相当于每一条边只能在第一个边集中当入度，或者在第二个边集中当出度。将 $b\rightarrow a$ 连两条边后就是一个标准的二分图匹配，如果左部均匹配到那么可行。复杂度 $O(m\sqrt n)$。
这个二分图右部的每个点都会连接左边 $x,y$ 两个点，因此考虑缩成一条边 $x-y$，造出来一张新图。二分图匹配就变成了新图上每个点都选择一个相邻边，且没有边被选两次的问题，所以对一个连通块，只要找到一个环就满足条件，环外均选择父边，环内随便选，也就是找到对连通块找到一个基环树即可。
AC代码
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
typedef long long ll;
using namespace std;
int n,m;
vector<pii>G[N];
void add(int a,int b,int id){
G[a].pb(mp(b,id));
G[b].pb(mp(a,id));
}
int vis[N],sp[N],se[N],top,choose[N],cirp;
int dfs(int p,int ef){ // find circle and choose
vis[p]=1;
for(auto pr:G[p]){
auto q=pr.fi;
if(pr.se==ef)continue;
if(vis[q]){
choose[q]=pr.se;
while(sp[top]!=q){
choose[sp[top]]=se[top];
top--;
}
cirp=q;
return 1;
}else{
se[++top]=pr.se;
sp[top]=q;
if(dfs(q,pr.se))return 1;
top--;
}
}
return 0;
}
int vis2[N];
void dfs2(int p){
vis2[p]=1;
for(auto pr:G[p]){
auto q=pr.fi;
if(vis2[q])continue;
if(!choose[q])choose[q]=pr.se;
dfs2(q);
}
}
int main(){
int i,a,b;
while(~scanf("%d%d%d%d",&n,&m,&a,&b)){
for(i=1;i<=n+n;i++){
G[i].clear();
vis[i]=vis2[i]=choose[i]=0;
}
for(i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v+n,i);
}
add(b,a+n,-1);add(b,a+n,-2);
int flag=1;
for(i=1;i<=n+n;i++){
if(!vis2[i]){
sp[top=1]=i;
if(!dfs(i,0)){
flag=0;
break;
}
dfs2(cirp);
}
}
if(!flag)printf("NO\n");
else{
printf("YES\n");
int cnt=0;
for(i=1+n;i<=n+n;i++){
if(choose[i]>0)printf("%d ",choose[i]);
else cnt++;
}
puts("");
for(i=1;i<=n;i++){
if(choose[i]>0)printf("%d ",choose[i]);
else cnt++;
}
assert(cnt==2);
puts("");
}
}
return 0;
}
F
题目描述
给 $n\le 1e5$ 个 $1e18$ 内的数，问最多删掉 $k(k\le \frac n2)$ 个数后的 $\gcd$ 最大值。
解题思路
solved by qxforever
考虑随机选一个数，在最后的序列中的概率至少为 $\frac 12$，于是多做几次基本上总能保证有某次选出来的数在最后序列中。
于是问题转化成：选定了 $x$ ，再选一些其他值能够获得的 $\gcd$ 最大值。
设 $f_t$ 表示 $t$ 的倍数在 $a$ 中出现的次数，则 $\text{argmax}_t [f_t\ge n-k]$ 即为所求。
通过从小到大枚举 $x$ 的质因数累积贡献可以获得 $f_t$。
AC代码 - by qxforever
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
using namespace std;
using ll = long long;
const int maxn = 5e5 + 10;
using i128 = __int128;
mt19937 rnd;
vector<ll> fact;
ll gcd(ll a, ll b) {
if (b == 0) return a;
return gcd(b, a % b);
}
ll qpow(ll x, ll p, ll mod) {
ll ans = 1;
while (p) {
if (p & 1) ans = (i128)ans * x % mod;
x = (i128)x * x % mod;
p >>= 1;
}
return ans;
}
bool Miller_Rabin(ll p) {
if (p < 2)
return 0;
else if (p == 2 || p == 3)
return 1;
ll d = p - 1, r = 0;
while (!(d & 1)) r++, d >>= 1;
for (ll k = 0; k < 10; k++) {
ll a = rnd() % (p - 2) + 2;
ll x = qpow(a, d, p);
if (x == 1 || x == p - 1) continue;
for (int i = 0; i < r - 1; i++) {
x = (i128)x * x % p;
if (x == p - 1) break;
}
if (x != p - 1) return 0;
}
return 1;
}
ll f(ll x, ll c, ll n) {
return ((i128)x * x + c) % n;
}
ll Pollard_Rho(ll x) {
ll s = 0, t = 0;
ll c = (ll)rand() % (x - 1) + 1;
int step = 0, goal = 1;
ll val = 1;
for (goal = 1;; goal <<= 1, s = t, val = 1) {
for (step = 1; step <= goal; step++) {
t = f(t, c, x);
val = (i128)val * abs(t - s) % x;
if ((step % 127) == 0) {
ll d = gcd(val, x);
if (d > 1) return d;
}
}
ll d = gcd(val, x);
if (d > 1) return d;
}
}
void fac(ll x) {
if (x < 2) return;
if (Miller_Rabin(x)) {
fact.push_back(x);
return;
}
ll p = x;
while (p >= x) p = Pollard_Rho(x);
while ((x % p) == 0) x /= p;
fac(x), fac(p);
}
int n, k;
ll a[maxn];
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
ll ans = 0;
while (clock() < 3.5 * CLOCKS_PER_SEC) {
int who = rnd () % n;
fact.clear();
fac(a[who]);
sort(fact.begin(), fact.end());
fact.erase(unique(fact.begin(), fact.end()), fact.end());
map<ll, int> mp;
for (int i = 0; i < n; i++) {
mp[__gcd(a[i], a[who])]++;
}
for (auto f : fact) {
for (auto it = mp.begin(); it != mp.end(); it++) {
if (it->first % f == 0) {
mp[(it->first) / f] += it->second;
}
}
}
for (auto [x, y] : mp) {
if (y >= n - k) ans = max(ans, x);
}
}
cout << ans;
}
G
题目描述
有 $n\le 1000$ 个邮局，每天只能开 $T$ 时间，有一些开门时间确定为 $o_i$，有一些开门时间不确定。
共有 $m\le 2000$ 个运送任务，每个任务是 $a_i$ 要向 $b_i$ 运送邮件，需要花费 $d_i$ 时间。求对于所有任务都能满足 $o_{a_i}+d_i\le o_{b_i}+T$ 的最小非负实数 $T$，以及对应的全部邮局开门时间。
解题思路
把开门时间 $o$ 看做 $n$ 个变量，对于一个固定的 $T$ ，就是满足一堆不等式条件：
$x_{a_i}+d_i-T\le x_{b_i}$；对于给定开门时间，设 $x_0=0$ 为基准，有 $x_i-o_i\le x_0,x_0+d\le x_i$
于是跑差分约束，判断 $T$ 下有没有解。二分答案 $T$ 进行上述过程即可。
AC代码
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
typedef long long ll;
using namespace std;
int n,m;
int a[N],b[N],c[N],d[N],o[N];
vector<pair<int,double>>G[N];
double dis[N];
int vis[N],cnt[N];
queue<int>Q;
void add(int a,int b,double l){
G[a].pb(mp(b,l));
}
int check(double x){
int i;
while(!Q.empty())Q.pop();
for(i=0;i<=n;i++){
G[i].clear();
dis[i]=1e7;
vis[i]=1,cnt[i]=0;
Q.push(i);
}
dis[0]=0;
// 0: start point, dis[0]=0
// i: o_i
// o_ai + di-T <= o_bi
for(i=0;i<m;i++)add(b[i],a[i],x-d[i]);
// o_i - d <= 0, 0 + d <= o_i
for(i=1;i<=n;i++)if(o[i]<1e6)add(0,i,o[i]),add(i,0,-o[i]);
while(!Q.empty()){
int p=Q.front();
Q.pop();
vis[p]=0;
for(auto pr:G[p]){
int q=pr.fi;double l=pr.se;
if(dis[q]>dis[p]+l){
dis[q]=dis[p]+l;
if(++cnt[q]>n)return 0;
if(!vis[q]){
Q.push(q);vis[q]=1;
}
}
}
}
return 1;
}
int main(){
int i;
while(~scanf("%d%d",&n,&m)){
for(i=1;i<=n;i++){
char s[100]={0};
scanf("%s",s);
if(s[0]=='?')o[i]=1e9;
else sscanf(s,"%d",&o[i]);
}
for(i=0;i<m;i++){
scanf("%d%d%d",&a[i],&b[i],&d[i]);
}
double l=0,r=1e7;
while(r-l>1e-8){
double mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid;
}
printf("%.8f\n",r);check(r);
for(i=1;i<=n;i++)printf("%.8f%c",dis[i],i==n?'\n':' ');
}
return 0;
}
H
题目描述
对于一个树，对于给定集合 $S$，定义 $T(S)$ 表示包含 $S$ 中所有元素，并且其他度数 $>2$ 的节点全部删除后得到的新树节点个数。
给一个 $n\le 100$ 的树，不能超过 $2550$ 次询问，每次询问一个集合 $S$ 返回 $T(S)$，让你猜这棵树长什么样。
解题思路
发现如果询问 $n-1$ 个点， $T(S)=n-1$ 当且仅当被删掉的点是叶子节点。选一个非叶子节点当根，再选两个点，如果这两个点和根在一条路上，那么 $T(S)=3$，否则为 $4$，于是可以知道某个叶子有哪些祖先，根据子树大小排个序就得到树的结构。
AC代码
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
typedef long long ll;
using namespace std;
int n;
int query(vector<int>v){
printf("? %d",v.size());
for(auto q:v)printf(" %d",q);
puts("");
fflush(stdout);
int x;
scanf("%d",&x);
return x;
}
vector<int>leaves;
vector<int>branches;
int siz[N];
vector<int>fa[N];
vector<int>tree[N];
void add(int a,int b){
tree[a].pb(b);
tree[b].pb(a);
}
int ans[N];
void dfs(int p,int f){
for(auto q:tree[p]){
if(q==f)continue;
ans[q]=p;
dfs(q,p);
}
}
int F[N];
int main(){
int i,j;
scanf("%d",&n);
if(n==2){
printf("! 1");
fflush(stdout);
return 0;
}
for(i=1;i<=n;i++){
vector<int>v;
for(j=1;j<=n;j++)if(j!=i)v.pb(j);
if(query(v)==n-1)leaves.pb(i);
else branches.pb(i);
}
int root=leaves[0];
for(auto p:leaves){
if(p==root)continue;
for(auto q:branches){
vector<int>v;
v.pb(root);v.pb(q);v.pb(p);
if(query(v)==3){
siz[q]++;
fa[p].pb(q);
//printf("add: %d %d\n",p,q);
}
}
siz[root]++;
}
siz[root]++;
for(auto p:leaves){
if(p==root)continue;
fa[p].pb(root);
fa[p].pb(p);
sort(fa[p].begin(),fa[p].end(),[&](const int &x,const int &y){return siz[x]<siz[y];});
for(i=1;i<fa[p].size();i++){
if(F[fa[p][i-1]]&&F[fa[p][i-1]]!=fa[p][i])return 1;
F[fa[p][i-1]]=fa[p][i];
}
}
for(i=1;i<=n;i++){
if(i!=root)add(F[i],i);
}
dfs(1,0);
printf("!");
for(i=2;i<=n;i++)printf(" %d",ans[i]);
puts("");
fflush(stdout);
return 0;
}
I
题目描述
给一个 $n\le 4e5$ 的串串，$q4\le e5$ 次询问，每次询问一个区间集合，这个区间集合是 $k(\sum k\le 4e5)$ 个子串，问这个集合有多少个子集满足互不为前缀。
解题思路
考虑把询问集合里的串串排个序。设 $i$ 串是 $j$ 串的前缀，那么连一条 $i\rightarrow j$ 的边，用空串做根，这就造出来一棵树，那么一个从根开始的链上不能选两个点。在树上 $dp$，记 $f_p$ 为在 $p$ 子树中选择且至少选一个节点的选法，那么有 $f_p=\prod_{q\in son_p} (f_q+1)-1$，答案即为 $f_{根}+1$。树的大小是 $O(k)$ 的，因此 $dp$ 也是 $O(k)$ 的，其中 $k$ 为集合大小。
那么如何快速建树呢？首先，通过后缀数组可以容易地计算串之间的 $LCP$，于是容易对询问集合排序。排好序的集合就是树的 $dfs$ 序，于是就建好了。单次询问复杂度 $O(k\log n)$。需要注意的是，可能有重复的串，去重之后 $dp$ 的时候需要稍微改一下递推。
AC代码
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
typedef long long ll;
using namespace std;
// sa
int n;
char s[N];
int sa[N],c[N],x[N],y[N];
void getsa(int m){
int i,k;
for(i=0;i<=m;i++)c[i]=0;
for(i=1;i<=n;i++)c[x[i]=s[i]-'a']++;
for(i=1;i<=m;i++)c[i]+=c[i-1];
for(i=n;i;i--)sa[c[x[i]]--]=i;
for(k=1;k<=n;k<<=1){
int p=0;
for(i=n-k+1;i<=n;i++)y[++p]=i;
for(i=1;i<=n;i++)if(sa[i]>k)y[++p]=sa[i]-k;
for(i=0;i<=m;i++)c[i]=0;
for(i=1;i<=n;i++)c[x[y[i]]]++;
for(i=1;i<=m;i++)c[i]+=c[i-1];
for(i=n;i;i--)sa[c[x[y[i]]]--]=y[i];
swap(x,y);
p=x[sa[1]]=1;
for(i=2;i<=n;i++)
x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p;
if(p>=n)break;
m=p;
}
}
int h[N],rnk[N];
void geth(){
int i,j,k=0;
for(i=1;i<=n;i++)rnk[sa[i]]=i;
for(i=1;i<=n;i++){
if(k)k--;
j=sa[rnk[i]-1];
while(s[i+k]==s[j+k])k++;
h[rnk[i]]=k;
}
}
int rmq[N][22],lg[N];
void init(){
int i,j;
for(i=2;i<N;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
getsa(260);
geth();
for(i=1;i<=n;i++)rmq[i][0]=h[i];
for(i=1;i<=22;i++)
for(j=1;j+(1<<i-1)<=n;j++)
rmq[j][i]=min(rmq[j][i-1],rmq[j+(1<<i-1)][i-1]);
}
int getlcp(int x,int y){
if(x==y)return n-x+1;
if(rnk[x]>rnk[y])swap(x,y);
int l=rnk[x]+1,r=rnk[y];
int p=lg[r-l+1];
return min(rmq[l][p],rmq[r-(1<<p)+1][p]);
}
// solve
struct Q{
int l,r;
int len(){
return r-l+1;
}
bool operator<(const Q &a)const{
int lcp=min(min(a.r-a.l+1,r-l+1),getlcp(l,a.l));
if(a.r-a.l+1==lcp)return false;
if(r-l+1==lcp)return true;
return s[l+lcp]<s[a.l+lcp];
}
}q[N];
int mod;
int sta[N],top;
int siz[N];
int checkequal(Q a,Q b){
int len=a.len();
if(a.len()!=b.len())return 0;
return getlcp(a.l,b.l)>=len;
}
int checkprefix(Q a,Q b){
return getlcp(a.l,b.l)>=a.len();
}
vector<int>G[N];
void add(int a,int b){
G[a].pb(b);
}
int f[N];
void dfs(int p){
ll cur=1;
for(auto q:G[p]){
dfs(q);
cur=cur*(f[q]+1)%mod;
}
f[p]=((cur-1)+siz[p])%mod;
}
int main(){
int i,Q;
scanf("%d%d",&n,&Q);
scanf("%s",s+1);
init();
while(Q--){
int k;
scanf("%d%d",&k,&mod);
for(i=1;i<=k;i++)scanf("%d%d",&q[i].l,&q[i].r);
sort(q+1,q+k+1);
// suppress redundant [1,k]->[1,top]
sta[top=1]=siz[1]=1; // push first item
for(i=2;i<=k;i++){
if(!checkequal(q[i],q[i-1])){
sta[++top]=i;
siz[top]=1;
}else{
siz[top]++;
}
}
for(i=1;i<=top;i++)q[i]=q[sta[i]];
// construct tree as dfn [1,k], 0 rooted
k=top;
sta[top=0]=0;
for(i=0;i<=k;i++){
G[i].clear();
f[i]=0;
}
// stack: current branch
for(i=1;i<=k;i++){
while(top&&!checkprefix(q[sta[top]],q[i]))top--;
add(sta[top],i);
sta[++top]=i;
}
// dp to calculate ans
dfs(0);
printf("%d\n",(f[0]+1)%mod);
}
return 0;
}
J
题目描述
$n\le 2e5$ 的串 $a$，$q\le 2e5$ 次询问，每次问 $[l_i,r_i]$ 区间有多少子序列值之和是 $m\le 20$ 的倍数。
解题思路
容易想到用线段树维护区间子序列之和模 $m$ 余数 $i$ 的种类数，但合并左右区间的复杂度是 $m^2$ 的，总复杂度 $O(qnm^2\log n)$，卡不过去。考虑优化掉一个 $m$。
对询问离线，分治进行处理。对于一个跨区间中点的询问，只需要处理出来每个左端点 $i$ 到 $mid$ 的、余数 $j$ 的方案数，以及 $mid$ 到每个右端点的、余数 $j$ 的方案数。于是总复杂度降到 $O(qnm\log n)$。
AC代码
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
typedef long long ll;
using namespace std;
int mod=1000000007;
int a[N],l[N],r[N],m;
int ans[N];
struct egom{
int x[20];
egom(){memset(x,0,sizeof(x));}
};
void dc(int L,int R,vector<int>v){
if(L>R)return;
if(L==R){
for(auto x:v){
ans[x]=1+(a[L]%m==0);
}
return;
}
vector<int>vl,vr;
int i,j,mid=(L+R)>>1;
// [L,mid] [mid+1,R]
vector<egom>pl,pr;
egom startL,startR;
startL.x[0]=1;startL.x[a[mid]%m]++;
startR.x[0]=1;startR.x[a[mid+1]%m]++;
pl.pb(startL);
pr.pb(startR);
for(i=1;mid-i>=L;i++){
egom last=pl[i-1];
for(j=0;j<m;j++){
// j -> j+a[mid-i]
(last.x[(j+a[mid-i])%m]+=pl[i-1].x[j])%=mod;
}
pl.pb(last);
}
for(i=1;mid+1+i<=R;i++){
egom last=pr[i-1];
for(j=0;j<m;j++){
// j -> j+a[mid+i]
(last.x[(j+a[mid+1+i])%m]+=pr[i-1].x[j])%=mod;
}
pr.pb(last);
}
for(auto index:v){
if(r[index]<=mid)vl.push_back(index);
else if(l[index]>=mid+1)vr.push_back(index);
else{
// l[index]~mid, mid+1~r[index]
int dl=mid-l[index]+1,dr=r[index]-mid;
for(i=0;i<m;i++){
(ans[index]+=1LL*pl[dl-1].x[i]*pr[dr-1].x[(m-i)%m]%mod)%=mod;
}
}
}
dc(L,mid,vl);
dc(mid+1,R,vr);
}
int main(){
int i,n,q;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)scanf("%d",&a[i]);
scanf("%d",&q);
vector<int>Q;
for(i=0;i<q;i++){
scanf("%d%d",&l[i],&r[i]);
l[i]--;r[i]--;
Q.push_back(i);
}
dc(0,n-1,Q);
for(i=0;i<q;i++)printf("%d\n",ans[i]);
return 0;
}
K
题目描述
给一个 $|s|\le 1e5$ 的串， $m$ 次询问 $t,\sum|t|\le 1e5$ 的串，问 $t$ 在 $s$ 中最多不重叠出现几次。
解题思路
solved by nikkukun
不同的长度最多有 $\sqrt n$ 种，每一种长度进行哈希匹配。复杂度 $O(n\sqrt n\log n)$。
AC代码 - by nikkukun
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pint;
typedef tuple<int, int, int> tint;
const int N = 1e5 + 5;
const int BAS = 299213;
const int MOD1 = 991145149;
const int MOD2 = 929292929;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
int POW1[N];
int POW2[N];
struct HashString {
string s;
int id;
int ans;
vector<pint> h;
void init() {
int n = s.size();
h.push_back(make_pair(0, 0));
for (int i = 1; i <= n; i++) {
int c = s[i - 1] - 'a';
int a = h.back().fi;
int b = h.back().se;
a = (1LL * a * BAS + c) % MOD1;
b = (1LL * b * BAS + c) % MOD2;
h.push_back(make_pair(a, b));
}
}
pint hashCode(int l, int r) {
pint a = h[l - 1];
pint b = h[r];
int len = r - l + 1;
auto ret = make_pair(
(b.fi - 1LL * a.fi * POW1[len]) % MOD1,
(b.se - 1LL * a.se * POW2[len]) % MOD2);
ret.fi = (ret.fi + MOD1) % MOD1;
ret.se = (ret.se + MOD2) % MOD2;
return ret;
}
};
HashString s;
HashString t[N];
vector<int> pos[N];
int main() {
ios::sync_with_stdio(0);
POW1[0] = POW2[0] = 1;
for (int i = 1; i < N; i++) {
POW1[i] = 1LL * POW1[i - 1] * BAS % MOD1;
POW2[i] = 1LL * POW2[i - 1] * BAS % MOD2;
}
int n, m;
cin >> n >> m;
string ss;
cin >> ss;
s.s = ss;
s.init();
for (int i = 1; i <= m; i++) {
cin >> ss;
t[i].s = ss;
t[i].init();
t[i].id = i;
}
sort(t + 1, t + m + 1, [](HashString &a, HashString &b) {
return a.s.size() < b.s.size();
});
for (int l = 1; l <= m; l++) {
// [l, r]
int r = l;
while (t[r].s.size() == t[l].s.size()) r++;
r--;
int len = t[l].s.size();
map<pint, int> idx;
for (int j = l; j <= r; j++) {
pint h = t[j].hashCode(1, t[j].s.size());
if (idx.count(h)) {
t[j].ans = -t[idx[h]].id;
} else {
idx[h] = j;
}
}
for (int j = 1; j + len - 1 <= n; j++) {
pint h = s.hashCode(j, j + len - 1);
if (idx.count(h)) {
pos[idx[h]].push_back(j);
}
}
// 每个 t 自己计算
for (int j = l; j <= r; j++) {
if (t[j].ans != 0) continue;
vector<pint> f;
for (auto p: pos[j])
f.push_back(make_pair(p, 1));
int cur = 0;
for (int p = 0; p < f.size(); p++) {
while (cur < f.size() && f[cur].fi < f[p].fi + len) cur++;
if (cur < f.size())
f[cur].se = max(f[cur].se, f[p].se + 1);
if (p + 1 < f.size())
f[p + 1].se = max(f[p + 1].se, f[p].se);
}
int ans = 0;
if (!f.empty()) ans = f.back().se;
t[j].ans = ans;
}
// 释放空间
for (int j = l; j <= r; j++)
pos[j].clear();
l = r;
}
sort(t + 1, t + m + 1, [](HashString &a, HashString &b) {
return a.id < b.id;
});
for (int i = 1; i <= m; i++) {
if (t[i].ans >= 0)
cout << t[i].ans << endl;
else
cout << t[-t[i].ans].ans << endl;
}
return 0;
}
L
题目描述
给一个 $n\le 2e5,m\le 2e5$ 的连通带权无向图，问每条边是从 $1$ 出发到达多少个点最短路的必经之路。
解题思路
solved by qxforever
在最短路图上建出支配树，树上 $dp$ 子树大小即可，在支配树上的支配边才会对答案产生贡献。
AC代码 - by qxforever
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
119
120
121
122
123
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
const int maxn = 1e6 + 10;
int n, m;
namespace DominatorTree {
vector<int> g[maxn], rg[maxn], rdom[maxn], tree[maxn];
int S[maxn], RS[maxn], cs;
int par[maxn], val[maxn], sdom[maxn], rp[maxn], dom[maxn];
void add_edge(int x, int y) {
g[x].push_back(y);
}
void Union(int x, int y) {
par[x] = y;
}
int Find(int x, int c = 0) {
if (par[x] == x) return c ? -1 : x;
int p = Find(par[x], 1);
if (p == -1) return c ? par[x] : val[x];
if (sdom[val[x]] > sdom[val[par[x]]]) val[x] = val[par[x]];
par[x] = p;
return c ? p : val[x];
}
void dfs(int x) {
RS[S[x] = ++cs] = x;
par[cs] = sdom[cs] = val[cs] = cs;
for (int e : g[x]) {
if (S[e] == 0) dfs(e), rp[S[e]] = S[x];
rg[S[e]].push_back(S[x]);
}
}
set<pii> edge;
int solve(int s, int* up = nullptr) {
dfs(s);
for (int i = cs; i; i--) {
for (int e : rg[i]) sdom[i] = min(sdom[i], sdom[Find(e)]);
if (i > 1) rdom[sdom[i]].push_back(i);
for (int e : rdom[i]) {
int p = Find(e);
if (sdom[p] == i)
dom[e] = i;
else
dom[e] = p;
}
if (i > 1) Union(i, rp[i]);
}
for (int i = 2; i <= cs; i++)
if (sdom[i] != dom[i]) dom[i] = dom[dom[i]];
for (int i = 2; i <= cs; i++) tree[RS[dom[i]]].push_back(RS[i]);
return cs;
}
int ans[maxn];
void dfs2(int p) {
ans[p] = 1;
for (int i : tree[p]) {
dfs2(i);
edge.insert({p, i});
ans[p] += ans[i];
}
}
void calc() {
dfs2(1);
}
}
vector<pii> g[maxn];
ll d[maxn];
bool vis[maxn];
int main() {
cin >> n >> m;
vector<pii> edge;
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back({v, w});
g[v].push_back({u, w});
edge.push_back({u, v});
}
memset(d, 0x3f, sizeof(d));
priority_queue<pli, vector<pli>, greater<pli>> q;
q.push({0, 1});
d[1] = 0;
while (!q.empty()) {
int x = q.top().second;
q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (auto [u, v] : g[x]) {
if (d[u] > d[x] + v) {
d[u] = d[x] + v;
q.push({d[u], u});
}
}
}
for (int i = 1; i <= n; i++) {
for (auto [x, y] : g[i]) {
if (d[i] == d[x] + y) {
DominatorTree::add_edge(x, i);
}
}
}
DominatorTree::solve(1);
DominatorTree::calc();
for (auto [u, v] : edge) {
if (DominatorTree::edge.count({u, v})) {
printf("%d\n", DominatorTree::ans[v]);
}
else if (DominatorTree::edge.count({v, u})) {
printf("%d\n", DominatorTree::ans[u]);
}
else printf("%d\n", 0);
}
}