做题笔记"/>
SDOI2016 R1做题笔记
SDOI2016 R1做题笔记
经过很久很久的时间，shzr终于做完了SDOI2016一轮的题目。
其实没想到竟然是2016年的题目先做完，因为14年的六个题很早就做了四个了，但是后两个有点开不动...
那么就顺着开始说：
储能表：.php?id=4513
题意概述：给定一张大表格，i行j列的数是 $i$ $xor$ $j$,多组询问，求
$\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}max((i \bigoplus j)-k,0)$
$T=5000，n≤10^{18}，m≤10^{18}，k≤10^{18}，p≤10^9$
几个月前第一次看这道题的反应:这能做？弃了弃了。今天早上再看时发现也没那么难。
如果想着正面去处理异或值减k这种操作，会非常棘手，因为异或的一个很好的性质就是各位独立，而减法破坏了这样的性质。发现如果异或值小于 $k$ 对答案就没有贡献，所以可以只考虑异或值大于 $k$ 的部分，这样就消除了max操作的影响。把减法拆开，先算前半部分的和，再计算一下需要减掉几个k即可。因为异或的每一位是独立的，可以想到二进制数位dp，状态还是很好设计的：$dp[i][j][k][z]$表示填到第 $i$ 位，是否卡 $n$ 的上界，是否卡 $m$ 的上界，是否卡 $k$ 的下界的方案数，再列一个类似的式子表示和，转移显然。
实际写程序的时候要注意：方案数为0（可能是恰好为模数的倍数），方案值的和不一定为0，这时不要直接跳出循环。第一次交的时候没有注意到这一点，只有10分，要是省选遇上这种事可就...
1 # include <cstdio>
2 # include <iostream>
3 # include <cstring>
4 # define R register int
5 # define ll long long
6
7 using namespace std;
8
9 int T,n[65],m[65],k[65];
10 ll a,b,d,s[65][2][2][2],c[65][2][2][2],t,su,nj,nl,nz,p;
11
12 void div (ll x,int *a)
13 {
14 for (R i=0;i<=60;++i)
15 a[60-i+1]=(x&(1LL<<i))?1:0;
16 }
17
18 ll ad (ll a,ll b,ll p) { a+=b; if(a>=p) a-=p; return a; }
19
20 int main()
21 {
22 scanf("%d",&T);
23 while(T--)
24 {
25 scanf("%lld%lld%lld%lld",&a,&b,&d,&p);
26 a--,b--;
27 div(a,n); div(b,m); div(d,k);
28 memset(s,0,sizeof(s)); memset(c,0,sizeof(c));
29 c[0][1][1][1]=1;
30 for (R i=0;i<=60;++i)
31 for (R j=0;j<=1;++j)
32 for (R l=0;l<=1;++l)
33 for (R z=0;z<=1;++z)
34 {
35 if(s[i][j][l][z]==0&&c[i][j][l][z]==0) continue;
36 t=c[i][j][l][z]%p; su=s[i][j][l][z]%p;
37 for (R v=0;v<=1;++v)
38 for (R w=0;w<=1;++w)
39 {
40 if(j==1&&v>n[i+1]) continue;
41 if(l==1&&w>m[i+1]) continue;
42 if(z==1&&(v^w)<k[i+1]) continue;
43 if(j==1&&v==n[i+1]) nj=1; else nj=0;
44 if(l==1&&w==m[i+1]) nl=1; else nl=0;
45 if(z==1&&(v^w)==k[i+1]) nz=1; else nz=0;
46 c[i+1][nj][nl][nz]=ad(c[i+1][nj][nl][nz],t,p);
47 s[i+1][nj][nl][nz]=(s[i+1][nj][nl][nz]%p+su*2LL+t*(v^w))%p;
48 }
49 }
50 ll ans=0;
51 d%=p;
52 for (R i=0;i<=1;++i)
53 for (R j=0;j<=1;++j)
54 for (R l=0;l<=1;++l)
55 ans=(ans+s[61][i][j][l]-d*c[61][i][j][l]%p+p)%p;
56 printf("%lld\n",(ans+p)%p);
57 }
58 return 0;
59 } D1T1
数字配对：.php?id=4514
直接粘题面.jpg
“有 $n$ 种数字，第 $i$ 种数字是 $a_i$、有 $b_i$ 个，权值是 $c_i$。
若两个数字 $(a_i,a_j)$ 满足，$a_i$ 是 $a_j$ 的倍数，且 $a_i/a_j$ 是一个质数，
那么这两个数字可以配对，并获得 $c_i×c_j$ 的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于 $0$ 的前提下，求最多进行多少次配对。”
...第一次看到以为是一般图的最大权匹配，这能做？后来又复习网络流的时候才发现并不是一般图。
发现两个数如果满足可以匹配的标准，那么它们分解质因数后的指数和必然一奇一偶，所以是二分图，二分图最大匹配就很好做啦。等等，它要求的并不是最大匹配，而是最多能匹配几个。考虑网络流的贪心过程，每次走的增广路都是边权最大的，所以如果某一次发现增广完以后价值和小于0了，那么以后更不可能加回来，这时退出即可。
这题第一次交30...因为我自己yy了一个错误的二分图染色算法...
1 # include <cstdio>
2 # include <iostream>
3 # include <cstring>
4 # include <queue>
5 # define inf 1000000009
6 # define R register int
7 # define ll long long
8
9 using namespace std;
10
11 const int maxn=205;
12 int n,a[maxn],b[maxn],c[maxn],vis[maxn],h=1,firs[maxn],s,t,Fl[maxn],pre[maxn],col[maxn],f[maxn],tot;
13 ll max_cos,max_flow,d[maxn];
14 struct edge { int too,nex,cap; ll co; }g[(maxn+maxn*maxn)<<1],ed[maxn*maxn*2];
15 queue <int> q;
16
17 inline int read()
18 {
19 R x=0,f=1;
20 char c=getchar();
21 while (!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }
22 while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
23 return x*f;
24 }
25
26 inline void add (int x,int y,int cap,ll co)
27 {
28 g[++h].nex=firs[x];
29 g[h].too=y;
30 g[h].cap=cap;
31 g[h].co=co;
32 firs[x]=h;
33 g[++h].nex=firs[y];
34 g[h].too=x;
35 g[h].cap=0;
36 g[h].co=-co;
37 firs[y]=h;
38 }
39
40 inline bool check (int x)
41 {
42 if(x==1) return false;
43 for (R i=2;i*i<=x;++i) if(x%i==0) return false;
44 return true;
45 }
46
47 bool bfs ()
48 {
49 memset(d,128,sizeof(d));
50 int minn=d[0];
51 d[s]=0,Fl[s]=inf,pre[s]=0;
52 q.push(s);
53 int j,beg;
54 while(q.size())
55 {
56 beg=q.front();
57 q.pop();
58 vis[beg]=false;
59 for (R i=firs[beg];i;i=g[i].nex)
60 {
61 if(g[i].cap<=0) continue;
62 j=g[i].too;
63 if(d[beg]+g[i].co<=d[j]) continue;
64 d[j]=d[beg]+g[i].co;
65 Fl[j]=min(Fl[beg],g[i].cap);
66 pre[j]=i;
67 if(!vis[j]) vis[j]=true,q.push(j);
68 }
69 }
70 if(d[t]==minn) return false;
71 if(d[t]*Fl[t]+max_cos<0)
72 {
73 max_flow+=max_cos/(-d[t]);
74 return false;
75 }
76 return true;
77 }
78
79 inline void dfs ()
80 {
81 int i=0,x=t;
82 while(x!=s)
83 {
84 i=pre[x];
85 g[i].cap-=Fl[t];
86 g[i^1].cap+=Fl[t];
87 x=g[i^1].too;
88 }
89 max_flow+=Fl[t];
90 max_cos+=Fl[t]*d[t];
91 }
92
93 inline void ad (int x,int y)
94 {
95 ed[++tot].nex=f[x];
96 ed[tot].too=y;
97 f[x]=tot;
98 }
99
100 void pt (int x)
101 {
102 int j;
103 for (R i=f[x];i;i=ed[i].nex)
104 {
105 j=ed[i].too;
106 if(col[j]!=0) continue;
107 col[j]=-col[x];
108 pt(j);
109 }
110 }
111
112 int main()
113 {
114 n=read();
115 t=n+1;
116 for (R i=1;i<=n;++i) a[i]=read();
117 for (R i=1;i<=n;++i) b[i]=read();
118 for (R i=1;i<=n;++i) c[i]=read();
119 for (R i=1;i<=n;++i)
120 for (R j=1;j<=n;++j)
121 if(a[i]%a[j]==0&&check(a[i]/a[j])) ad(i,j),ad(j,i);
122 for (R i=1;i<=n;++i) if(col[i]==0) col[i]=1,pt(i);
123 for (R i=1;i<=n;++i)
124 if(col[i]==1) add(s,i,b[i],0);
125 else add(i,t,b[i],0);
126 for (R i=1;i<=n;++i)
127 for (R j=1;j<=n;++j)
128 if(a[i]%a[j]==0&&check(a[i]/a[j]))
129 {
130 if(col[i]==1) add(i,j,inf,1LL*c[i]*c[j]);
131 else add(j,i,inf,1LL*c[i]*c[j]);
132 }
133 while(bfs())
134 dfs();
135 printf("%lld",max_flow);
136 return 0;
137 } D1T2
游戏：.php?id=4515
题意概述：给定一棵树，支持在一条路径上添加一次函数，以及询问一条路径上的最大值。$n,m<=10^5$
关于这道题还有一点故事：我刚看到这道题的时候，就跟asuldb说“SDOI2016好像不难，怎么还出个李超树板子啊”，这句话说出去之后如果再做不出来就不大好了。于是写了几乎整整一下午才做出来，“思考5分钟，写题5小时”。
看到这种数据结构题肯定要先写个对拍，然而这道题的暴力挺难写的（当然还是比正解简单得多），写了100多行。
1 # include <cstdio>
2 # include <iostream>
3 # include <cstring>
4 # define R register int
5 # define ll long long
6
7 using namespace std;
8
9 const int maxn=100005;
10 const ll inf=123456789123456789LL;
11 int n,m,h,firs[maxn],x,y,w,dep[maxn],f[maxn][20],s,t;
12 ll l[maxn],v[maxn],a,b,ans;
13 struct edge { int too,nex,w; }g[maxn<<1];
14
15 void add_ed (int x,int y,int w)
16 {
17 g[++h].nex=firs[x];
18 firs[x]=h;
19 g[h].too=y;
20 g[h].w=w;
21 }
22
23 int lca (int x,int y)
24 {
25 if(dep[x]>dep[y]) swap(x,y);
26 for (R i=18;i>=0;--i) if(dep[y]-(1<<i)>=dep[x]) y=f[y][i];
27 if(x==y) return x;
28 for (R i=18;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
29 return f[x][0];
30 }
31
32 void dfs (int x)
33 {
34 int j;
35 for (R i=firs[x];i;i=g[i].nex)
36 {
37 j=g[i].too;
38 if(dep[j]) continue;
39 l[j]=l[x]+g[i].w; dep[j]=dep[x]+1;
40 f[j][0]=x;
41 for (R k=1;k<=18;++k) f[j][k]=f[ f[j][k-1] ][k-1];
42 dfs(j);
43 }
44 }
45
46 ll dis (int x,int y)
47 {
48 int a=lca(x,y);
49 return l[x]+l[y]-2*l[a];
50 }
51
52 void ask (int s,int t)
53 {
54 ans=min(ans,v[s]);
55 ans=min(ans,v[t]);
56 while(s!=t)
57 {
58 if(dep[s]<dep[t]) t=f[t][0];
59 else s=f[s][0];
60 ans=min(ans,v[s]);
61 ans=min(ans,v[t]);
62 }
63 }
64
65 void add (int s,int t,ll a,ll b)
66 {
67 int x=s,y=t;
68 v[x]=min(v[x],a*dis(s,x)+b);
69 v[y]=min(v[y],a*dis(s,y)+b);
70 while(x!=y)
71 {
72 if(dep[x]<dep[y]) y=f[y][0];
73 else x=f[x][0];
74 v[x]=min(v[x],a*dis(s,x)+b);
75 v[y]=min(v[y],a*dis(s,y)+b);
76 }
77 }
78
79 int main()
80 {
81 freopen("data.in","r",stdin);
82 freopen("std.out","w",stdout);
83
84 scanf("%d%d",&n,&m);
85 for (R i=1;i<n;++i)
86 {
87 scanf("%d%d%d",&x,&y,&w);
88 add_ed(x,y,w); add_ed(y,x,w);
89 }
90 for (R i=1;i<=n;++i) v[i]=inf;
91 memset(l,-1,sizeof(l));
92 l[1]=0; dep[1]=1;
93 dfs(1);
94 int opt=0;
95 for (R i=1;i<=m;++i)
96 {
97 scanf("%d",&opt);
98 if(opt==1)
99 {
100 scanf("%d%d%lld%lld",&s,&t,&a,&b);
101 add(s,t,a,b);
102 }
103 else
104 {
105 scanf("%d%d",&s,&t);
106 ans=inf;
107 ask(s,t);
108 printf("%lld\n",ans);
109 }
110 }
111 return 0;
112 } 对拍 （恭喜这个程序成为我博客里第一篇暴力）
话说回来，这道题真的就是个模板题，只不过是复杂了很多的模板题。李超树套个树剖，完事。细节问题比较复杂。
首先看插入路径：
路径上的点到指定点的距离这一信息比较麻烦，所以将一条路径从LCA处拆开，将距离全部转化为根路径前缀和。细节就不说了，注意分出来的两条路径的ab和之前不同。
对于线段树上的一个节点，如果它有“优势线段”，那么由于一次函数是单调的，最小值必然在端点处取到。除此以外，还有可能是两个子节点的最小值。
然后看查询：
代码里把路径拆开了分别查询，现在想想好像没必要。
一般写的李超树都是单点查询，所以写区间查询时要多注意。首先将区间分为三类：被询问区间包含的，包含了询问区间的，与询问区间有交集但不符合之前两种情况的；
对于第一种，直接返回区间的最小值；
对于第二种，肯定还是要往下分询问的，但还有一种情况，就是此区间的“优势线段”在询问区间上的最小值；
对于第三种，除了上述情况外，还有可能是线段树区间的端点在自己区间的“优势线段”所取到的值（前提是得在询问区间内），也可以是询问区间在这里取到的最小值（当然也得在线段树区间内）；
是不是非常复杂...一个比较好写的做法是直接无脑讨论四个端点，像这样：
做比较复杂的数据结构题，如果想第一次就多得点分，暴力对拍是必不可少的。利用随机生成的小数据，我查出了10+个细节错误和刚刚那些要注意的细节问题（这么多细节哪能一下子全想到还不都是对拍）。最后分析一下复杂度：树剖一个log，李超树两个log，总的来说三个log，但是常数小，跑不满。
1 # include <cstdio>
2 # include <iostream>
3 # include <cstring>
4 # define R register int
5 # define LL long long
6 # define nl (n<<1)
7 # define nr (n<<1|1)
8
9 using namespace std;
10
11 const int maxn=100005;
12 const LL inf=123456789123456789LL;
13 int n,m,x,y,w,h,firs[maxn],seg_cnt=0,c[maxn<<2],S,T,d[maxn];
14 int id[maxn],Top[maxn],siz[maxn],son[maxn],f[maxn],cnt;
15 LL l[maxn],t[maxn<<2],dep[maxn],a,b;
16 struct edge { int too,nex,w; }g[maxn<<1];
17 struct seg { LL a,b; }se[maxn<<1];
18
19 void add_ed (int x,int y,int w);
20 int lca (int x,int y);
21 LL dis (int x,int y);
22 void dfs1 (int x);
23 void dfs2 (int x,int Tp);
24 void add_p (int x,int y,int v);
25 void add_t (int n,int l,int r,int v);
26 void add (int n,int l,int r,int ll,int rr,int v);
27 LL ask_p (int x,int y);
28 LL ask (int n,int l,int r,int ll,int rr);
29 void build (int n,int l,int r);
30 void update (int n);
31 LL read();
32
33 int main()
34 {
35 n=read(),m=read();
36 for (R i=1;i<n;++i)
37 {
38 x=read(),y=read(),w=read();
39 add_ed(x,y,w); add_ed(y,x,w);
40 }
41 l[1]=0; d[1]=1;
42 dfs1(1); dfs2(1,1); build(1,1,n);
43 int opt=0;
44 for (R i=1;i<=m;++i)
45 {
46 opt=read();
47 if(opt==1)
48 {
49 S=read(),T=read(),a=read(),b=read();
50 int LA=lca(S,T);
51 se[++seg_cnt].b=b+l[S]*a; se[seg_cnt].a=-a;
52 add_p(S,LA,seg_cnt);
53 se[++seg_cnt].a=a; se[seg_cnt].b=a*l[S]-2*l[LA]*a+b;
54 add_p(LA,T,seg_cnt);
55 }
56 else
57 {
58 S=read(),T=read();
59 int LA=lca(S,T);
60 LL ans=min(ask_p(S,LA),ask_p(LA,T));
61 printf("%lld\n",ans);
62 }
63 }
64 return 0;
65 }
66
67 LL read()
68 {
69 LL x=0,f=1;
70 char c=getchar();
71 while (!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }
72 while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
73 return x*f;
74 }
75
76 void update (int n)
77 {
78 t[n]=min(t[n],t[nl]);
79 t[n]=min(t[n],t[nr]);
80 }
81
82 void build (int n,int l,int r)
83 {
84 t[n]=inf;
85 if(l==r) return;
86 int mid=(l+r)>>1;
87 build(nl,l,mid); build(nr,mid+1,r);
88 }
89
90 void add_ed (int x,int y,int w)
91 {
92 g[++h].nex=firs[x];
93 firs[x]=h;
94 g[h].too=y;
95 g[h].w=w;
96 }
97
98 int lca (int x,int y)
99 {
100 while(Top[x]!=Top[y])
101 {
102 if(d[ Top[x] ]>d[ Top[y] ]) swap(x,y);
103 y=f[ Top[y] ];
104 }
105 return (d[x]<d[y])?x:y;
106 }
107
108 LL dis (int x,int y)
109 {
110 int a=lca(x,y);
111 return l[x]+l[y]-2*l[a];
112 }
113
114 void dfs1 (int x)
115 {
116 int j,maxs=-1; siz[x]=1;
117 for (R i=firs[x];i;i=g[i].nex)
118 {
119 j=g[i].too;
120 if(f[x]==j) continue;
121 l[j]=l[x]+g[i].w;
122 f[j]=x; d[j]=d[x]+1;
123 dfs1(j);
124 siz[x]+=siz[j];
125 if(siz[j]>=maxs) maxs=siz[j],son[x]=j;
126 }
127 }
128
129 void dfs2 (int x,int Tp)
130 {
131 id[x]=++cnt; Top[x]=Tp; dep[ cnt ]=l[x];
132 if(!son[x]) return;
133 dfs2(son[x],Tp);
134 int j;
135 for (R i=firs[x];i;i=g[i].nex)
136 {
137 j=g[i].too;
138 if(son[x]==j||f[x]==j) continue;
139 dfs2(j,j);
140 }
141 }
142
143 void add_p (int x,int y,int v)
144 {
145 while(Top[x]!=Top[y])
146 {
147 if(d[ Top[x] ]>d[ Top[y] ]) swap(x,y);
148 add(1,1,n,id[ Top[y] ],id[y],v);
149 y=f[ Top[y] ];
150 }
151 if(d[x]>d[y]) swap(x,y);
152 add(1,1,n,id[x],id[y],v);
153 }
154
155 void add_t (int n,int l,int r,int v)
156 {
157 if(!c[n]) { t[n]=min(t[n],min(dep[l]*se[v].a+se[v].b,dep[r]*se[v].a+se[v].b)); c[n]=v; return; }
158 int x=c[n],mid=(l+r)>>1;
159 if(l!=r) update(n);
160 t[n]=min(t[n],min(dep[l]*se[v].a+se[v].b,dep[r]*se[v].a+se[v].b));
161 if(dep[l]*se[v].a+se[v].b>=dep[l]*se[x].a+se[x].b&&dep[r]*se[v].a+se[v].b>=dep[r]*se[x].a+se[x].b) return;
162 if(dep[l]*se[v].a+se[v].b<=dep[l]*se[x].a+se[x].b&&dep[r]*se[v].a+se[v].b<=dep[r]*se[x].a+se[x].b) { c[n]=v; return; }
163 if(se[x].a>=se[v].a)
164 {
165 if(se[x].a*dep[mid]+se[x].b>=se[v].a*dep[mid]+se[v].b) c[n]=v,add_t(nl,l,mid,x);
166 else add_t(nr,mid+1,r,v);
167 }
168 else
169 {
170 if(se[x].a*dep[mid]+se[x].b>=se[v].a*dep[mid]+se[v].b) c[n]=v,add_t(nr,mid+1,r,x);
171 else add_t(nl,l,mid,v);
172 }
173 if(l!=r) update(n);
174 }
175
176 void add (int n,int l,int r,int ll,int rr,int v)
177 {
178 if(ll<=l&&r<=rr) add_t(n,l,r,v);
179 else
180 {
181 int mid=(l+r)>>1;
182 if(ll<=mid) add(nl,l,mid,ll,rr,v);
183 if(rr>mid) add(nr,mid+1,r,ll,rr,v);
184 update(n);
185 }
186 }
187
188 LL ask_p (int x,int y)
189 {
190 LL ans=inf;
191 while(Top[x]!=Top[y])
192 {
193 if(d[ Top[x] ]>d[ Top[y] ]) swap(x,y);
194 ans=min(ans,ask(1,1,n,id[ Top[y] ],id[y]));
195 y=f[ Top[y] ];
196 }
197 if(d[x]>d[y]) swap(x,y);
198 ans=min(ans,ask(1,1,n,id[x],id[y]));
199 return ans;
200 }
201
202 LL ask (int n,int l,int r,int ll,int rr)
203 {
204 if(ll<=l&&r<=rr) return t[n];
205 int mid=(l+r)>>1; LL ans=inf;
206 if(ll<=mid) ans=min(ans,ask(nl,l,mid,ll,rr));
207 if(rr>mid) ans=min(ans,ask(nr,mid+1,r,ll,rr));
208 if(c[n])
209 {
210 if(l<=ll&&ll<=r) ans=min(ans,dep[ll]*se[ c[n] ].a+se[ c[n] ].b);
211 if(l<=rr&&rr<=r) ans=min(ans,dep[rr]*se[ c[n] ].a+se[ c[n] ].b);
212 if(ll<=l&&l<=rr) ans=min(ans,dep[l]*se[ c[n] ].a+se[ c[n] ].b);
213 if(ll<=r&&r<=rr) ans=min(ans,dep[r]*se[ c[n] ].a+se[ c[n] ].b);
214 }
215 return ans;
216 } D1T3
生成魔咒：.php?id=4516
题意概述：每次在一个字符串后插入字符，并求出每次操作后本质不同的子串数量。$n<=10^5$
这题挺妙的。SAM应该很好做，因为它本来就是个在线算法。不过还是考虑用SA.（不是模拟退火）
SA计算本质不同子串数量的时候有这么一个公式：
$\sum_{i=1}^nn-sa_i+1-height_i$
理解一下：先求出每个后缀的前缀数量（也就是子串数量），然后减掉相同的。其实为什么大家都用这个公式我并不是很明白，因为完全可以简化很多，不就是所有子串数量减掉ht的和吗？
好的，那我们化简一下，只考虑ht的和。
再说的直白一点，就是每个后缀与排名在它之前一名的后缀的LCP的和。
动态的插入字符，如果反过来看，也就是每次加入一个新的后缀，它的排名在之前已经处理好了，现在需要的就是动态的维护刚刚所说的那个值了。
随便找一个能维护前驱后继的数据结构，插入一个点时，找到它的前驱后继（这两个本来相当于是挨着的），把这一对对答案的贡献消除，再加入新串和前驱后继对答案的贡献。
1 # include <cstdio>
2 # include <iostream>
3 # include <cstring>
4 # include <map>
5 # define R register int
6 # define nl (n<<1)
7 # define nr (n<<1|1)
8
9 using namespace std;
10
11 const int maxn=100005;
12 const int inf=1e7;
13 int n;
14 int a[maxn],cnt,ta[maxn],tb[maxn],A[maxn],B[maxn],sa[maxn],rk[maxn],ht[maxn];
15 int st[maxn][20],lg[maxn],tl[maxn<<2],tr[maxn<<2];
16 map <int,int> M;
17
18 void build_SA ()
19 {
20 for (R i=1;i<=n;++i) ta[ a[i] ]++;
21 for (R i=1;i<=1000;++i) ta[i]+=ta[i-1];
22 for (R i=n;i>=1;--i) sa[ ta[ a[i] ]-- ]=i;
23 rk[ sa[1] ]=1;
24 for (R i=2;i<=n;++i)
25 {
26 rk[ sa[i] ]=rk[ sa[i-1] ];
27 if(a[ sa[i] ]!=a[ sa[i-1] ]) rk[ sa[i] ]++;
28 }
29 for (R l=1;rk[ sa[n] ]!=n;l<<=1)
30 {
31 for (R i=0;i<=n;++i) ta[i]=tb[i]=0;
32 for (R i=1;i<=n;++i) ta[ A[i]=rk[i] ]++,tb[ B[i]=(i+l<=n)?rk[i+l]:0 ]++;
33 for (R i=1;i<=n;++i) ta[i]+=ta[i-1],tb[i]+=tb[i-1];
34 for (R i=n;i>=1;--i) rk[ tb[ B[i] ]-- ]=i;
35 for (R i=n;i>=1;--i) sa[ ta[ A[ rk[i] ] ]-- ]=rk[i];
36 rk[ sa[1] ]=1;
37 for (R i=2;i<=n;++i)
38 {
39 rk[ sa[i] ]=rk[ sa[i-1] ];
40 if(A[ sa[i] ]!=A[ sa[i-1] ]||B[ sa[i] ]!=B[ sa[i-1] ]) rk[ sa[i] ]++;
41 }
42 }
43 int j=0;
44 for (R i=1;i<=n;++i)
45 {
46 if(j) j--;
47 while(a[i+j]==a[ sa[ rk[i]-1 ]+j ]) j++;
48 ht[ rk[i] ]=j;
49 }
50 }
51
52 void build_ST()
53 {
54 for (R i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
55 for (R i=1;i<=n;++i) st[i][0]=ht[i];
56 for (R k=1;k<=17;++k)
57 for (R i=1;i+(1<<k)-1<=n;++i) st[i][k]=min(st[i][k-1],st[i+(1<<(k-1))][k-1]);
58 }
59
60 int lcp (int i,int j)
61 {
62 int k=lg[j-i+1];
63 return min(st[i][k],st[j-(1<<k)+1][k]);
64 }
65
66 void build (int n,int l,int r)
67 {
68 tr[n]=inf;
69 if(l==r) return;
70 int mid=(l+r)>>1;
71 build(nl,l,mid); build(nr,mid+1,r);
72 }
73
74 int askl (int n,int l,int r,int ll,int rr)
75 {
76 if(ll<=l&&r<=rr) return tl[n];
77 int mid=(l+r)>>1,ans=-inf;
78 if(ll<=mid) ans=max(ans,askl(nl,l,mid,ll,rr));
79 if(rr>mid) ans=max(ans,askl(nr,mid+1,r,ll,rr));
80 return ans;
81 }
82
83 int askr (int n,int l,int r,int ll,int rr)
84 {
85 if(ll<=l&&r<=rr) return tr[n];
86 int mid=(l+r)>>1,ans=inf;
87 if(ll<=mid) ans=min(ans,askr(nl,l,mid,ll,rr));
88 if(rr>mid) ans=min(ans,askr(nr,mid+1,r,ll,rr));
89 return ans;
90 }
91
92 void ins (int n,int l,int r,int pos)
93 {
94 if(l==r) { tl[n]=l,tr[n]=l; return; }
95 int mid=(l+r)>>1;
96 if(pos<=mid) ins(nl,l,mid,pos);
97 else ins(nr,mid+1,r,pos);
98 tl[n]=max(tl[nl],tl[nr]);
99 tr[n]=min(tr[nl],tr[nr]);
100 }
101
102 int main()
103 {
104 scanf("%d",&n);
105 for (R i=1;i<=n;++i)
106 {
107 scanf("%d",&a[i]);
108 if(M[ a[i] ]) a[i]=M[ a[i] ];
109 else M[ a[i] ]=++cnt,a[i]=cnt;
110 }
111 for (R i=1;i<=n/2;++i) swap(a[i],a[n-i+1]);
112 build_SA();
113 build_ST();
114 long long ans=0;
115 build(1,1,n);
116 for (R i=n;i>=1;--i)
117 {
118 int lef=0,rig=0;
119 if(rk[i]!=1) lef=askl(1,1,n,1,rk[i]-1);
120 if(rk[i]!=n) rig=askr(1,1,n,rk[i]+1,n);
121 if(lef==-inf) lef=0; if(rig==inf) rig=0;
122 if(lef&&rig) ans-=lcp(lef+1,rig);
123 if(lef) ans+=lcp(lef+1,rk[i]);
124 if(rig) ans+=lcp(rk[i]+1,rig);
125 ins(1,1,n,rk[i]);
126 printf("%lld\n",1LL*(n-i+1)*(n-i+2)/2-ans);
127 }
128 return 0;
129 } D2T1
排列计数：.php?id=4517
直接粘题面.jpg
“ 有多少种长度为 n 的序列 A，满足以下条件：
1 ~ n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多，序列数对 10^9+7 取模。”
$T=500000，n≤1000000，m≤1000000$
这题十分诡异,因为它的难度和其它几题真的不搭。
那么这题怎么做？$C_n^m$ 表示选出哪些数是稳定的,$\times d_{n-m}$表示其它元素进行错排。没了？没了。
1 # include <cstdio>
2 # include <iostream>
3 # include <queue>
4 # include <cstring>
5 # include <string>
6 # define R register int
7 # define ll long long
8 # define mod 1000000007
9
10 using namespace std;
11
12 const int maxn=1000000;
13 int T;
14 int n,m;
15 long long d[maxn+3],f[maxn+3],inv[maxn+3];
16
17 ll qui (ll a)
18 {
19 ll b=mod-2,s=1;
20 while (b)
21 {
22 if(b&1LL) s=s*a%mod;
23 a=a*a%mod;
24 b>>=1LL;
25 }
26 return s;
27 }
28
29 ll C (int n,int m)
30 {
31 return f[n]*inv[m]%mod*inv[n-m]%mod;
32 }
33
34 inline int read ()
35 {
36 int x=0;
37 char c=getchar();
38 while (!isdigit(c)) c=getchar();
39 while (isdigit(c)) { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }
40 return x;
41 }
42
43 int main()
44 {
45 scanf("%d",&T);
46 d[0]=1;
47 d[1]=0;
48 for (R i=2;i<=maxn;++i)
49 d[i]=(i-1)*(d[i-1]+d[i-2])%mod;
50 f[0]=1;
51 for (R i=1;i<=maxn;++i)
52 f[i]=f[i-1]*i%mod;
53 inv[maxn]=qui(f[maxn]);
54 for (R i=maxn-1;i>=0;--i)
55 inv[i]=inv[i+1]*(i+1)%mod;
56 while(T--)
57 {
58 n=read();
59 m=read();
60 printf("%lld\n",C(n,m)*d[n-m]%mod);
61 }
62 return 0;
63 } D2T2
征途:.php?id=4518
题意概述：将一个长度为 $n$ 的序列分成 $m$ 段，使得每一段的方差和最小。$n,m<=3000$
这题做的比较早，也写过blog，在这里；
但是后来有学了一种方法：带权二分；
显然如果不限制分段数量，最优解就是每个数分成一段，这样的答案是0，如果要求必须分成1段，那么答案就是整个序列的方差。
可以发现随着段数的增加，最优解也在变优，所以就有了一种很有趣的做法：给“分段”这件事带上一个权值，每多分一段，就要在最终答案里加上一个常数；
加的数越大，分的段数就会越少，如果某次最优解的段数恰好为所要求的的值，把这个值减掉段数*常数即为答案。需要注意的是有可能一直分不到段数为k，即：二分的常数为c，段数是k+1，常数为c-1，段数就直接跳到了k-1。这里不用实数二分，因为这道题涉及的所有量都是整数，如果出现上述情况，说明k-1段和k段的最优解是相等的，这时的答案就可以作为k段的答案。
不限制段数的dp很好做，利用斜率优化可以做到 $O(N)$，再加上二分的复杂度，还是比之前的那种 $O(NM)$快到不知道哪里去了，有图为证：
1 # include <cstdio>
2 # include <iostream>
3 # define R register int
4 # define ll long long
5
6 using namespace std;
7
8 const int maxn=3005;
9 int n,m,s[maxn],c,f[maxn];
10 ll ans,dp[maxn];
11
12 double X (int x) { return s[x]; }
13 double Y (int x) { return dp[x]+1LL*s[x]*s[x]; }
14 double K (int x,int y) { return (Y(x)-Y(y))/(X(x)-X(y)); }
15
16 struct que
17 {
18 int q[maxn],h,t;
19 void init() { h=1,t=1; }
20 void ins (int x)
21 {
22 int a=q[t-1],b=q[t],c=x;
23 while(h<t&&K(a,b)>K(b,c))
24 {
25 t--;
26 a=q[t-1],b=q[t],c=x;
27 }
28 q[++t]=x;
29 }
30 void del (int x)
31 {
32 double k=2*s[x];
33 int a=q[h],b=q[h+1];
34 while(h<t&&K(a,b)<k)
35 {
36 h++;
37 a=q[h],b=q[h+1];
38 }
39 }
40 }q;
41
42 int check (int c)
43 {
44 q.init(); int x;
45 for (R i=1;i<=n;++i)
46 {
47 q.del(i);
48 x=q.q[ q.h ];
49 dp[i]=Y(x)-2*s[i]*s[x]+c+s[i]*s[i];
50 f[i]=f[x]+1;
51 q.ins(i);
52 }
53 return f[n];
54 }
55
56 int main()
57 {
58 scanf("%d%d",&n,&m);
59 for (R i=1;i<=n;++i) scanf("%d",&s[i]),s[i]+=s[i-1];
60 int l=0,r=2000000000;
61 while(l<=r)
62 {
63 c=r-(r-l)/2; int t=check(c);
64 if(t==m) break;
65 if(t<m) r=c-1; else l=c+1;
66 }
67 printf("%lld",(dp[n]-1LL*c*m)*m-s[n]*s[n]);
68 return 0;
69 } D2T3
总的来说这套题的排题让人挺迷惑的。明明是最简单的“排列计数”却放到D2T2这样的位置，复杂难调的“游戏”放到D1，但题目的质量还是很不错的。
下次再发类似的做题笔记可能就要很久了，因为14年的“向量集”，15年的“道路修建”，17年的“树点涂色”...哪个都不是好做的题。想再做完整一套还是要花一些时间的。
SDOI 2019 rp++;
---shzr
转载于:.html
更多推荐
SDOI2016 R1做题笔记
发布评论