NOI2016 简要题解
command_block
2021-06-16 08:53:35
$$\large\text{Current Score : 300}$$
# D1T1 [优秀的拆分](https://www.luogu.com.cn/problem/P1117)
**题意** : 给出字符串 $S$，求 `AABB` 型拆分的个数。
$|S|\leq 3\times 10^4$。
------------
首先对于每个位置，求出 `AA` 在此结尾和 `BB` 在此开始的方案数，然后对应相乘即可得到答案。
接下来只考虑计数在每个位置开始的 `AA` 型串。
枚举 `AA` 型串的串长，设为 $2k$ 。
考虑每隔 $k$ 个位置放置一个关键点，就会得到一个很重要的性质 ： 每个长度为 $2k$ 的`AA`串**恰好**会经过相邻的两个关键点。这形成了一一对应。
从相邻的一对关键点向前求 $\rm LCS$ ,向后求 $\rm LCP$ 。
如果两个区间没有交,如图:
```cpp
======== ========
*********u********************v*********************
======== ========
????
```
如果要安排一个 `AA` 串同时经过两个关键点，那么 `????` 处肯定不对应。
然后如果这个两区间有交，我们就可以获得一些 `AA` 型串。
```cpp
======== ========
*********u********************v*********************
================= =================
[...........................................]
{...} {...}
```
所有被包在区间内的长为 $2k$ 的串都对应一种 `AA` 拆分。
这些串开头和结尾的范围，就像骨牌在木槽里滑动，容易计算。差分处理对答案的贡献 (区间加) 即可。
我们一共会产生$O(\sum_{i=1}^n\frac{n}{i})=O(n\log n)$个关键点。
每个点要 $O(\log n)$ 的 Hash 匹配，总复杂度 $O(n\log^2n)$。也可以用后缀数组做到 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MaxN 30500
#define ll long long
using namespace std;
template<const int mod,const int buf>
struct StrHash{
ll p[MaxN],h[MaxN];
void Init(char *s,int n)
{
p[0]=1;
for (int i=1;i<=n;i++){
p[i]=p[i-1]*buf%mod;
h[i]=(h[i-1]*buf+s[i]-'a'+1)%mod;
}
}
bool tl(int l,int r,int len)
{return (h[l]-h[l-len]*p[len]-mod)%mod==(h[r]-h[r-len]*p[len]-mod)%mod;}
bool tr(int l,int r,int len)
{return (h[l+len-1]-h[l-1]*p[len]-mod)%mod==(h[r+len-1]-h[r-1]*p[len]-mod)%mod;}
};
StrHash<1000000007,29> h1;
StrHash<1000000009,31> h2;
int n;char s[MaxN];
int extl(int u,int v)
{
if (s[u]!=s[v])return 0;
int l=1,r=min(u,v),mid;
while(l<r){
mid=(l+r+1)>>1;
if (h1.tl(u,v,mid)&&h2.tl(u,v,mid))l=mid;
else r=mid-1;
}return l;
}
int extr(int u,int v)
{
if (s[u]!=s[v])return 0;
int l=1,r=n-max(u,v)+1,mid;
while(l<r){
mid=(l+r+1)>>1;
if (h1.tr(u,v,mid)&&h2.tr(u,v,mid))l=mid;
else r=mid-1;
}return l;
}
int sl[MaxN],sr[MaxN];
void solve()
{
scanf("%s",s+1);n=strlen(s+1);
for (int i=1;i<=n;i++)sl[i]=sr[i]=0;
h1.Init(s,n);h2.Init(s,n);
for (int p=1;p<=n;p++){
for (int k=p;k+p<=n;k+=p){
int u=k,v=k+p,tl=extl(u,v),tr=extr(u,v);
if (tl+tr>=p+1){
int l=max(u-tl+1,v-2*p+1),r=min(v+tr-2*p,u);
sl[l]++;sl[r+1]--;
sr[l+2*p-1]++;sr[r+2*p]--;
}
}
}
for (int i=1;i<=n;i++)
{sl[i]+=sl[i-1];sr[i]+=sr[i-1];}
ll ans=0;
for (int i=1;i<n;i++)
ans+=1ll*sr[i]*sl[i+1];
printf("%lld\n",ans);
}
int main()
{
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
```
------------
# D1T2 [网格](https://www.luogu.com.cn/problem/P1173)
**题意** ： 给出一个 $n\times m$ 的矩阵，其中有 $k$ 个 $1$ ，其余是 $0$。
问至少要修改多少个位置，使得矩阵中至少有两个 $0$ ，且存在两个 $0$ 不连通。
多组数据，$T\leq 10,n,m\leq 10^9,\sum k\leq 10^5$。
------------
# D1T3 [循环之美](https://www.luogu.com.cn/problem/P1587)
见 [[数论记录]P1587 [NOI2016]循环之美](https://www.luogu.com.cn/blog/command-block/post-shuo-xue-ji-lu-p1587-noi2016-xun-huan-zhi-mei)
------------
# D2T1 [区间](https://www.luogu.com.cn/problem/P1712)
**题意** : 给出 $n$ 个区间，要求选出恰好 $m$ 个使得其有交，代价为区间长度的极差。求出最小代价或指出无解。
$n\leq 5\times 10^5,m\leq 2\times 10^5$。
------------
首先把区间根据长度排序，加入我们选择了最短的区间 $L_1$ ，最长的区间$L_2$ ，那么中间的区间就任君挑选了，反正不会增加费用。
问题在于我们必须恰好选择出 $m$ 个区间。
考虑对于某个确定了 $L_1,L_2$ 的决策，如何判断是否合法。
容易发现，其等价于 $[L_1,L_2]$ 中所有区间是否有覆盖 $m$ 次的公共部分。
至于怎么维护，不难想到区间加查询最大值。需要离散化。
然后我们就可以使用尺取法了。维护两个指针 `l,r` ，每次 $l$ 前进一步，$r$ 前进到合法为止。
复杂度 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 500500
using namespace std;
const int INF=2000000000;
struct Node{
int x,tg;
inline void ladd(int t)
{x+=t;tg+=t;}
}a[MaxN<<3];
inline void up(int u)
{a[u].x=max(a[u<<1].x,a[u<<1|1].x);}
inline void ladd(int u){
if (a[u].tg){
a[u<<1].ladd(a[u].tg);
a[u<<1|1].ladd(a[u].tg);
a[u].tg=0;
}
}
int wfl,wfr,wfc,n;
void add(int l=1,int r=n+n,int u=1)
{
if (wfl<=l&&r<=wfr)
{a[u].ladd(wfc);return ;}
int mid=(l+r)>>1;ladd(u);
if (wfl<=mid)add(l,mid,u<<1);
if (mid<wfr)add(mid+1,r,u<<1|1);
up(u);
}
struct Line{int l,r,c;}l[MaxN];
bool cmp(const Line &A,const Line &B)
{return A.c<B.c;}
int m,x[MaxN<<1];
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d%d",&l[i].l,&l[i].r);
x[i*2-1]=l[i].l;x[i*2]=l[i].r;
l[i].c=l[i].r-l[i].l;
}sort(x+1,x+n+n+1);
for (int i=1;i<=n;i++){
l[i].l=lower_bound(x+1,x+n+n+1,l[i].l)-x;
l[i].r=lower_bound(x+1,x+n+n+1,l[i].r)-x;
}sort(l+1,l+n+1,cmp);
int p=0,ans=INF;
for (int i=1;i<=n;i++){
while(p<n&&a[1].x<m){
p++;
wfl=l[p].l,wfr=l[p].r;
wfc=1;add();
}if (a[1].x>=m)
ans=min(ans,l[p].c-l[i].c);
wfl=l[i].l;wfr=l[i].r;
wfc=-1;add();
}printf("%d\n",ans== INF ? -1 : ans);
return 0;
}
```
------------
# D2T2 [国王饮水记](https://www.luogu.com.cn/problem/P1721)
**题意** ：
------------
# D2T3 [旷野大计算](https://www.luogu.com.cn/problem/P1737)
**题意** ：提交答案题。