contest0110

模拟赛

题目链接放原题的吧

marshland

网络流

将图分为三类点,$X+Y$为奇数的$A$点和$X+Y$为偶数的$B$点。

在将$B$点分为$X$为奇数的$B’$点和$X$为偶数的$B’’$点

可以强制最后答案$L$型的初始端点为$B’$点,这样就可以方便的建图了

$S \rightarrow B’ \rightarrow A \rightarrow B’’ \rightarrow T$

要建立一个$S’$点来满足$m$的限制。

$S’$向$S$要连一条容量为$1$,费用为$0$的边,然后再残留网络上跑一遍费用流,进行$m$次

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
119
120
/*
>Author: zxy_hhhh
>blog: zxy-hhhh.cn
>date: 2019/01/10
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<queue>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x--)
#define cross(x,a) for (int x=hd[a];~x;x=nx[x])
#define ll long long
using namespace std;
inline ll rd()
{
ll _x=0;int _ch=getchar(),_f=1;
for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
if (_ch=='-'){_f=0;_ch=getchar();}
for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
return _f?_x:-_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 300005
ll nx[maxn],to[maxn],hd[maxn],val[maxn],cost[maxn],cnt=-1;
inline void add(int u,int v,int c,ll L) {
//wrt(u,' '),wrt(v,' '),wrt(c,'\n');
nx[++cnt]=hd[u],to[cnt]=v,cost[cnt]=-c,val[cnt]=L,hd[u]=cnt;
nx[++cnt]=hd[v],to[cnt]=u,cost[cnt]=c,val[cnt]=0,hd[v]=cnt;
}
int n,m,p,num;
ll a[55][55],s,t,s1;
bool vis[55][55];
ll pre1[maxn],pre2[maxn],dis[maxn];
ll ans=0;
bool inq[maxn];
queue<int> que;
inline int get(int x,int y){return (x-1)*n+y;}
#define INF 16666666666
ll min_cost_flow(){
ll flow=0,f=INF;
while(f > 0){
memset(inq, 0, sizeof(inq));
rep(i,1,t) dis[i]=INF;
dis[s]=0,que.push(s);
while(!que.empty()){
int u=que.front();que.pop();
inq[u]=0;
cross(x,u){
if(val[x]>0 && dis[to[x]] > dis[u] + cost[x]){
dis[to[x]]=dis[u]+cost[x];
pre1[to[x]]=u,pre2[to[x]]=x;
if(!inq[to[x]]) que.push(to[x]),inq[to[x]]=1;
}
}
}
//wrt(dis[t],'\n');
if(dis[t]==INF) return ans;
ll delta=f;
for(int i=t;i!=s;i=pre1[i])
delta=min(delta,val[pre2[i]]);
f-=delta,flow+=delta,ans+=delta*dis[t];
for(int i=t;i!=s;i=pre1[i])
val[pre2[i]]-=delta,val[pre2[i]^1]+=delta;
}
}
int main()
{
memset(hd,-1,sizeof hd);
n=rd(),m=rd(),p=rd(),num=n*n;
ll sum=0;
s=num*2+1,s1=num*2+2,t=num*2+3;
rep(i,1,n)
rep(j,1,n)
a[i][j]=rd(),sum+=a[i][j];
rep(i,1,p){
int x=rd(),y=rd();
vis[x][y]=1;
}
rep(i,1,n)
rep(j,1,n)
if (!vis[i][j])
add(get(i,j),get(i,j)+num,a[i][j],1);
for(int i=1;i<=n;i+=2){
for(int j=1;j<=n;j+=2){
int out=get(i,j)+num;
if (j>1) add(out,get(i,j-1),0,INF);
if (j<n) add(out,get(i,j+1),0,INF);
if (i>1) add(out,get(i-1,j),0,INF);
if (i<n) add(out,get(i+1,j),0,INF);
}
}
for(int i=1;i<=n;i+=2){
for(int j=2;j<=n;j+=2){
int out=get(i,j)+num;
if (i>1) add(out,get(i-1,j),0,INF);
if (i<n) add(out,get(i+1,j),0,INF);
}
}
for(int i=2;i<=n;i+=2){
for(int j=1;j<=n;j+=2){
int out=get(i,j)+num;
if (j>1) add(out,get(i,j-1),0,INF);
if (j<n) add(out,get(i,j+1),0,INF);
}
}
for(int i=2;i<=n;i+=2)
for(int j=2;j<=n;j+=2) add(get(i,j)+num,t,0,INF);
for(int i=1;i<=n;i+=2)
for(int j=1;j<=n;j+=2) add(s1,get(i,j),0,INF);
ll x=0;
rep(i,1,m){
add(s,s1,0,1);
x=min(x,min_cost_flow());
}
wrt(sum+x,'\n');
}

party

最终一定在所有点$Lca$处集合,答案一定是$c$的倍数

可以找出路径上所有出现过的颜色,然后二分答案,二分图匹配,这样可得$45pt$

用$bitset$,树剖维护,维护每个点跳到$top_x$的$bitset$或和

这里需要一点技巧,要强制每条重链长度不超过$\sqrt n$

然后使用hall定理

$2^n​$枚举子集,所有子集中答案除以子集大小取$min​$

然后$min*c$就是最终答案

时间复杂度$O(\sqrt n\frac{m}{64}q+mq)$

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
/*
>Author: zxy_hhhh
>blog: zxy-hhhh.cn
>date: 2019/01/10
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<bitset>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x--)
#define cross(x,a) for (int x=hd[a];x;x=nx[x])
#define ll long long
using namespace std;
inline ll rd()
{
ll _x=0;int _ch=getchar(),_f=1;
for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
if (_ch=='-'){_f=0;_ch=getchar();}
for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
return _f?_x:-_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 400005
int nx[maxn],to[maxn],hd[maxn],cnt;
inline void add(int u,int v){nx[++cnt]=hd[u],to[cnt]=v,hd[u]=cnt;}
int a[maxn];
int top[maxn],fa[maxn],dep[maxn],sz[maxn],son[maxn];
int sn,n,m,c,q;
inline void dfs(int u)
{
dep[u]=dep[fa[u]]+1,sz[u]=1;
cross(i,u){
fa[to[i]]=u,dfs(to[i]),sz[u]+=sz[to[i]];
if (sz[to[i]]>sz[son[u]]) son[u]=to[i];
}
}
bitset<1005> jump[maxn];
bitset<1005> A[6],now,tmp[6];
int Q[maxn];
inline void dfs(int u,int tp)
{
if (dep[u]-dep[tp]>sn) tp=u;
if (tp!=u)
jump[u]=jump[fa[u]],jump[u][a[u]]=1;
else jump[u][a[u]]=1;
top[u]=tp;
if (son[u]) dfs(son[u],tp);
cross(i,u) if (to[i]!=son[u]) dfs(to[i],to[i]);
}
inline int _lca(int u,int v)
{
while(top[u]!=top[v])
if (dep[top[u]]>dep[top[v]]) u=fa[top[u]];
else v=fa[top[v]];
return dep[u]<dep[v]?u:v;
}
inline void Get(int u,int v,int res)
{
A[res].reset();
while(top[u]!=top[v]) A[res]|=jump[u],u=fa[top[u]];
while(u!=v) A[res][a[u]]=1,u=fa[u];
A[res][a[v]]=1;
}
int Ans;
inline void work(int k,int use)
{
if (k>c){
if (use) Ans=min(Ans,(int)now.count()/use);
return ;
}
work(k+1,use);
tmp[k]=now,now=now|A[k];
work(k+1,use+1);
now=tmp[k];
}
void solve()
{
int Lca=Q[1];
rep(i,2,c) Lca=_lca(Lca,Q[i]);
rep(i,1,c) Get(Q[i],Lca,i);
Ans=n,work(1,0);
wrt(Ans*c,'\n');
}
int main()
{
n=rd(),m=rd(),q=rd();
rep(i,2,n) add(rd(),i);
rep(i,1,n) a[i]=rd();
sn=sqrt(n);
dfs(1),dfs(1,1);
rep(i,1,q){
c=rd();
rep(i,1,c) Q[i]=rd();
solve();
}
}

platform

$idea\ by\ sooke$

后缀数组

可以发现对于每一个后缀,排名递减,权值递增,所以最多只会有一个交点。

二分交点,权值可以前缀和维护。

对于一个串的排名,此处排名是升序,最后总数相减即可。

最后本质不同的子串数为$\frac{n*(n+1)}{2}-\sum\limits_{i=1}^nheight[i]$

从前往后扫,对于一个后缀$x$,$1到height[x]$的位置排名都将继承前一个后缀的前$height[x]$个数的排名

第$height[x]+1$到最后一个位置的排名一定是前面的最大值后连续的数。

使用栈维护栈内每个元素$x$记录它的排名是$l_x到r_x$,然后二分即可。

时间复杂度$O(nlogn)$,跑到飞快

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
/*
>Author: zxy_hhhh
>blog: zxy-hhhh.cn
>date: 2019/01/10
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x--)
#define cross(x,a) for (int x=hd[a];x;x=nx[x])
#define ll long long
using namespace std;
inline ll rd()
{
ll _x=0;int _ch=getchar(),_f=1;
for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
if (_ch=='-'){_f=0;_ch=getchar();}
for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
return _f?_x:-_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 100005
int tp[maxn],tax[30],a[maxn],n,m;
int rk[maxn],height[maxn],sa[maxn];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
inline void Qsort() {
rep(i,0,m) tax[i]=0;
rep(i,1,n) tax[rk[i]]++;
rep(i,1,m) tax[i]+=tax[i-1];
drp(i,n,1) sa[ tax[rk[tp[i]]]-- ]=tp[i];
}
void SAsort() {
rep(i,1,n) rk[i]=a[i],tp[i]=i;
Qsort();
for(int w=1,p=0;p<n;m=p,w<<=1) {
p=0;
rep(i,1,w) tp[++p]=n-w+i;
rep(i,1,n) if (sa[i]>w) tp[++p]=sa[i]-w;
Qsort(),swap(tp,rk);
rk[sa[1]]=p=1;
rep(i,2,n)
rk[sa[i]]=cmp(tp,sa[i-1],sa[i],w)?p:++p;
}
}
void calheight(int *r,int *sa,int n) {
int i,j,k=0;
for(i=1;i<=n;height[rk[i++]]=k){
if (!rk[i]) continue;
for(k?k--:0,j=sa[rk[i]-1];r[i+k]==r[j+k];)
k++;
}
return;
}
char s[maxn];
struct node {
ll l,r,S;
bool operator < (const node &B)const{return S<B.S;}
}sta[maxn];
int top,Ans;
ll tot;
pair<int,int> res[maxn];
int sum[maxn];
ll mx;
inline void getans(int bg,int R) {
int l=1,r=R;
while(l<=r){
int mid=(l+r)>>1;
int pos=lower_bound(sta+1,sta+1+top,node{0,0,mid})-sta;
ll rk=mx-(sta[pos].l+(mid-sta[pos-1].S-1))+1;
ll S=sum[bg+mid-1]-sum[bg-1];
if (rk==S) {
res[++Ans]=make_pair(bg,bg+mid-1);
return ;
}
if (rk<S) r=mid-1;
else l=mid+1;
}
}
inline void push(int x) {
if (height[x]==0) top=0;
else {
int pos=lower_bound(sta+1,sta+1+top,node{0,0,height[x]})-sta;
sta[pos].r=(sta[pos].l+(height[x]-sta[pos-1].S-1));
sta[pos].S=sta[pos-1].S+(sta[pos].r-sta[pos].l+1);
top=pos;
}
sta[++top]=node{tot+1,tot+(n-sa[x]+1)-height[x],0};
tot=sta[top].r;
sta[top].S=sta[top-1].S+sta[top].r-sta[top].l+1;
}
int main()
{
//n=rd();
scanf("%s",s+1);
n=strlen(s+1);m=27;
rep(i,1,n) a[i]=s[i]-'a'+1;
SAsort();
calheight(a,sa,n);
mx=1ll*n*(n+1)/2;
rep(i,1,n) sum[i]=sum[i-1]+rd(),mx-=height[i];
rep(i,1,n) push(i),getans(sa[i],n-sa[i]+1);
sort(res+1,res+1+Ans);
wrt(Ans,'\n');
rep(i,1,Ans)
wrt(res[i].first,' '),wrt(res[i].second,'\n');
}
avatar
contest0111

  1. 1. marshland
  2. 2. party
  3. 3. platform