NOI2018 简要题解
command_block
2021-06-15 09:34:10
$$\large\textbf{Task Clear}$$
$$\large\text{Score : 515}$$
# D1T1 [归程](https://www.luogu.com.cn/problem/P4768)
**题意** ： 给出一张 $n$ 个点 $m$ 条边的无向图，边有（长度，海拔）两个参数。
有 $q$ 个询问 ：
从 $u$ 点出发前往 $1$ ，初始时可以乘车，但车不能经过海拔 $\leq q$ 的边。
可以在合适的时机下车行走，最小化行走的路程。
$n\leq 2\times 10^5,m,q\leq 4\times 10^5$
------------
签到题。
先从 $1$ 号点跑一个单源最短路，若在点 $v$ 下车，则行走路程为 $dis_v$。
以“海拔”建立克鲁斯卡尔重构树，则“点 $u$ 经过 $>q$ 的边能到达的区域”可以被描述为重构树的一个子树。
子树取 $\min$ 即可得到答案，复杂度 $1\log$。
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#define Pr pair<int,int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
#define MaxN 200500
#define MaxM 400500
using namespace std;
int INF=2000000000;
int n,dis[MaxN<<1];
vector<int> g[MaxN<<1],l[MaxN];
priority_queue<Pr> q;
void dijk(int s)
{
for (int i=1;i<=n;i++)dis[i]=INF;
dis[s]=0;q.push(mp(0,s));
while(!q.empty()){
Pr now=q.top();q.pop();
if (dis[now.sec]!=-now.fir)continue;
int u=now.sec;
for (int i=0,v;i<g[u].size();i++)
if (dis[v=g[u][i]]>dis[u]+l[u][i]){
dis[v]=dis[u]+l[u][i];
q.push(mp(-dis[v],v));
}
}
}
int w[MaxN<<1],f[18][MaxN<<1];
int qry(int u,int lim)
{
int k=17;
while(k--)
if (w[f[k][u]]>lim)
u=f[k][u];
return dis[u];
}
int fa[MaxN<<1];
int find(int u)
{return fa[u]==u ? u : fa[u]=find(fa[u]);}
bool chk(int u,int v)
{return find(u)!=find(v);}
void merge(int u,int v)
{fa[find(u)]=find(v);}
struct Line{int u,v,w;}s[MaxM];
bool cmp(const Line &A,const Line &B)
{return A.w>B.w;}
int m,Q,K,S;
void solve()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){g[i].clear();l[i].clear();}
for (int i=1,u,v,len,a;i<=m;i++){
scanf("%d%d%d%d",&u,&v,&len,&a);
g[u].pb(v);l[u].pb(len);
g[v].pb(u);l[v].pb(len);
s[i]=(Line){u,v,a};
}dijk(1);
for (int i=1;i<=n;i++)g[i].clear();
for (int i=1;i<=n+n;i++)fa[i]=i;
sort(s+1,s+m+1,cmp);
int tn=n;
for (int i=1;i<=m;i++){
int u=s[i].u,v=s[i].v;
if (chk(u,v)){
u=fa[u];v=fa[v];
w[f[0][u]=f[0][v]=++tn]=s[i].w;
g[tn].pb(u);g[tn].pb(v);
dis[tn]=min(dis[u],dis[v]);
merge(u,tn);merge(v,tn);
}
}
for (int j=1;j<17;j++)
for (int i=1;i<=tn;i++)
f[j][i]=f[j-1][f[j-1][i]];
scanf("%d%d%d",&Q,&K,&S);
for (int i=1,u,lim,las=0;i<=Q;i++){
scanf("%d%d",&u,&lim);
u=(u+K*las-1)%n+1;
lim=(lim+K*las)%(S+1);
printf("%d\n",las=qry(u,lim));
}
}
int main()
{
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
```
# D1T2 [冒泡排序](https://www.luogu.com.cn/problem/P4769)
**题意** ：
对于排列，记数值 $i$ 原来的位置为 $p_i$ ，则相邻交换排序的交换次数有显然的下界 $\dfrac{1}{2}\sum\limits_{i=1}^n\big|i-p_i\big|$。
对于一个排列，若对其冒泡排序所需的交换次数达到上述下界，则称为好的。
求长度为 $n$ ，且字典序严格大于给定的排列 $p$ 的好排列总数，答案对 $998244353$ 取模。
多组数据， $T\leq 5,n\leq 6\times 10^5,\sum n\leq 2\times10^6$
------------
牛逼题。
- ### **Part1**
考虑好排列的充要条件。
我们知道冒泡排序所需的交换次数达到下确界（每一步交换都是必须的），于是我们可以构造任意的交换方案。
每次交换我们都应当使 $\sum\limits_{i=1}^n\big|i-p_i\big|$ 减少 $2$ （也至多减少 $2$），这样才可能符合条件。
若 $p_i\leq i$ ，则数值 $i$ 只能向右移动（不能走弯路），若 $i<p_i$ ，则数值 $i$ 只能向左移动。（充要）
因此，若 $p_i\geq i$ ，则 $p_i$ 左侧的数都应该比 $i$ 小。若 $p_i>i$ ，则 $p_i$ 右侧的数都应该比 $i$ 大。（充要）
进一步观察发现，这等价于要求不存在长度为 $3$ 的下降子序列（三连降）。
- **必要性** ： 若存在三连降，考虑中间的数 $b$，无论 $p_b\leq b$ 还是 $p_b\geq b$ ，由于两侧都有不对的数，都不符合条件。
- **充分性** ： 若 $p_i\leq i$ ，且我们要交换 $p_i,p_{i+1}$ ，此时 $p_i,p_{i+1}$ 已经构成长度为 $2$ 的下降子序列，于是 $p_i$ 左侧不可能有 $>i$ 的数。
类似地， $p_i\geq i$ 时也能保证正确性。
显然交换不会中途产生三连降。
- ### **Part2**
先不考虑字典序的限制。
用 $\rm DP$ 来求解长为 $n$ 的好排列的个数。
设 $f[i,j]$ 表示填写了前 $i$ 个数，其中最大值为 $j$ 的方案数。
下一步，若填更大的值，则必然合法。若填 $<j$ 的值，则必须填最小值，否则会产生三连降。
于是有转移 ：
$$f[i,j]=\sum\limits_{k=1}^jf[i-1,k]$$
利用差分，能发现 $f[i,j]=f[i,j-1]+f[i-1,j]$。
尝试编一个组合意义 ： 路径。
- 当位于 $(i,j)$ 时，可以前往 $(i+1,j)$ 或 $(i,j+1)$。但不能使得 $i>j$。
先不考虑「不能使得 $i>j$」的限制，从 $(0,0)$ 到达 $(n,k)$ 的方案数显然为 $\dbinom{n+k}{n}$。
「使得 $i>j$ 」等价于「达到直线 $i=j+1$」。我们将不合法方案第一次触碰 $i=j+1$ 之后的路径根据 $i=j+1$ 翻转。
于是，不合法方案与「从 $(0,0)$ 到 $(k-1,n+1)$ 的路径」一一对应。
综上我们能得到 ：
$$f[n,k]=\dbinom{n+k}{n}-\dbinom{n+k}{n+1}$$
- ### **Part3**
接下来我们考虑字典序的限制。
枚举第一次不卡下界的位置，可以转化为 ： 钦定一个前缀 $=A_{1\sim k-1}$，且下一个数 $>A_k$ 的所有排列中，好排列的个数。
首先判一下填写这个数是否已经未被了上述 $\rm DP$ 转移的限制。
记 $L=\max A_{1\sim k-1}$ ， $t$ 是不在 $A_{1\sim k-1}$ 中的最小的数。
注意到总有 $t\leq A_k$ ，于是我们在这一位总是不能选择填 $t$。
于是只能填比 $\max(A_k,L)$ 大的数。
相当于将 $f[i,\max(A_k,L)+1\sim \infty]$ 置为 $1$ ，然后 $\rm DP$ 求出 $f[n,n]$ ，即为答案。
转化为下列问题 ：将 $f[i,j\sim \infty]$ 置为 $1$ ，然后 $\rm DP$ 求出 $f[n,n]$ 。
考虑 $f[i,j]\rightarrow f[n,m]$ 的贡献系数，相当于从 $(i,j)$ 走到 $n,m$ 且不使 $i>j$ 的方案数。
利用类似的技巧不难算得 ：
$${\rm contrib}\big(f[i,j]\rightarrow f[n,n]\big)=\dbinom{2n-i-j}{n-i,n-j}-\dbinom{2n-i-j}{n+1-i,n-1-j}$$
我们要求的是 $\sum_{j=k}^{\infty}{\rm contrib}\big(f[i,j]\rightarrow f[n,n]\big)$ ，不难发现其等于 ${\rm contrib}\big(f[i-1,j]\rightarrow f[n,n]\big)$
复杂度 $O(n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 600500
using namespace std;
const int mod=998244353;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
int fac[MaxN<<1],ifac[MaxN<<1];
int C(int n,int m)
{return m<0||n<m ? 0 : 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=1ll*i*fac[i-1]%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=1ll*i*ifac[i]%mod;
}
int n;bool vis[MaxN];
int s(int i,int j)
{return (C(n+n-i-j,n-i)-C(n+n-i-j,n+1-i)+mod)%mod;}
void solve()
{
scanf("%d",&n);
for (int i=1;i<=n+1;i++)vis[i]=0;
int ans=0;bool fl=0;
for (int i=1,mx=0,mn=1,p;i<=n;i++){
scanf("%d",&p);mx=max(mx,p);
vis[p]=1;while(vis[mn])mn++;
if (!fl)ans=(ans+s(i-1,mx+1))%mod;
if (mn<p&&p<mx)fl=1;
}printf("%d\n",ans);
}
int main()
{
Init(1200000);
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
```
# D1T3 [你的名字](https://www.luogu.com.cn/problem/P4770)
**题意** ： 给出文本串 $S$。
$q$ 次询问，每次给出串 $T$ 与区间 $[l,r]$ ，求 $T$ 的不在 $S[l,r]$ 中出现过的本质不同子串数目。
$|S|\leq 5\times10^5,q\leq 10^5,\sum|T|\leq 10^6$
------------
套路题。
首先考虑 $l=1,r=|S|$ 怎么做。
记 $slen[i]$ 表示 $T[1,i]$ 在 $S$ 中匹配的最长后缀长度。
这是一个经典问题，可以使用双指针求解 ：
- 类似 AC 自动机，要添加字符时，若当前节点无出边，则跳父亲，直到有出边为止。
求出 $slen$ 数组后，对 $T$ 建立 SAM。
对于某个 SAM 节点，记串长区间为 $(L,R]$ ，endpos 集合为 $E$ ，则找出任意一个 $d=\in E$ ，该节点中不在 $S$ 中出现的串的个数为 $\max\big(0,R-max(L,slen[d])\big)$。
接下来考虑 $l,r$ ，仍然考虑求出 $slen$ 数组。
观察我们在双指针算法中做了什么 ：
- 查看是否存在出边
- 跳父亲
在 $S$ 的 SAM 上用线段树合并维护 endpos 。
查看字符 $c$ 的出边时，记当前的匹配长度为 $len$ ，当前节点为 $u$。
找出 $v=u.trans(c)$ ，查看 ${\rm edp}(v)$ 中是否存在 $d\in[l+len,r]$。
若满足条件，则 $u\leftarrow v$ ，且 $len$ 加一。
若 $v$ 不存在或不符合条件，则 $len$ 减一，若 $len$ 不在 $u$ 的串长区间内则跳父亲。
复杂度 $O\Big(\big(|S|\sum|T|\big)\log |S|\Big)$
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define pb push_back
#define MaxN 500500
using namespace std;
struct SAM_Node{int t[26],f,len;}a[MaxN<<1],b[MaxN<<1];
int tn,las;
void ins(int c,SAM_Node *a)
{
int p=las,np=++tn;las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=1;
else {
int v=a[p].t[c];
if (a[v].len==a[p].len+1)a[np].f=v;
else {
int nv=++tn;a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[np].f=a[v].f=nv;
}
}
}
struct Node{int l,r;}t[MaxN*42];
int tot,to,rt[MaxN<<1];
void add(int l,int r,int &u)
{
if (!u)u=++tot;
if (l==r)return ;
int mid=(l+r)>>1;
if (to<=mid)add(l,mid,t[u].l);
else add(mid+1,r,t[u].r);
}
int wfl,wfr;
bool qry(int l,int r,int u)
{
if (!u)return 0;
if (wfl<=l&&r<=wfr)return 1;
int mid=(l+r)>>1;
if (wfl<=mid&&qry(l,mid,t[u].l))return 1;
if (mid<wfr&&qry(mid+1,r,t[u].r))return 1;
return 0;
}
int merge(int u,int v)
{
if (!u||!v)return u|v;
int p=++tot;
t[p].l=merge(t[u].l,t[v].l);
t[p].r=merge(t[u].r,t[v].r);
return p;
}
vector<int> g[MaxN<<1];
void dfs(int u)
{
for (int i=0;i<g[u].size();i++){
dfs(g[u][i]);
rt[u]=merge(rt[u],rt[g[u][i]]);
}
}
int ed[MaxN<<1];
void dfs2(int u)
{
for (int i=0;i<g[u].size();i++){
dfs2(g[u][i]);
ed[u]=ed[g[u][i]];
}
}
int n;
bool chk(int u,int len,int l,int r,char c){
wfl=l+len;wfr=r;
return wfl<=wfr&&a[u].t[c]&&qry(1,n,rt[a[u].t[c]]);
}
char s[MaxN];
int m,q,slen[MaxN];
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
tn=las=1;
for (int i=1;i<=n;i++)ins(s[i]-'a',a);
for (int i=2;i<=tn;i++)g[a[i].f].pb(i);
for (int i=1,p=1;i<=n;i++){
p=a[p].t[s[i]-'a'];
to=i;add(1,n,rt[p]);
}dfs(1);
for (int i=1;i<=tn;i++)g[i].clear();
scanf("%d",&q);
for (int qt=1,l,r;qt<=q;qt++){
scanf("%s%d%d",s+1,&l,&r);
m=strlen(s+1);
for (int i=1,p=1,len=0;i<=m;i++){
while(len){
if (chk(p,len,l,r,s[i]-'a'))break;
len--;
if (len==a[a[p].f].len)p=a[p].f;
}
if (chk(p,len,l,r,s[i]-'a')){
p=a[p].t[s[i]-'a'];
len++;
}slen[i]=len;
}
tn=las=1;
for (int i=1;i<=m;i++)ins(s[i]-'a',b);
for (int i=1,p=1;i<=m;i++)
ed[p=b[p].t[s[i]-'a']]=i;
for (int i=2;i<=tn;i++)g[b[i].f].pb(i);
dfs2(1);
long long ans=0;
for (int u=2;u<=tn;u++)
ans+=max(0,b[u].len-max(b[b[u].f].len,slen[ed[u]]));
for (int i=1;i<=tn;i++)g[i].clear();
memset(b,0,sizeof(SAM_Node)*(tn+5));
printf("%lld\n",ans);
}return 0;
}
```
# D2T1 [屠龙勇士](https://www.luogu.com.cn/problem/P4774)
**题意** ： 玩家需要按照 $1\sim n$ 的顺序逐次开 $n$ 把锁。每把锁有两个权值 $(p_i,a_i)$。
在开锁之前，要事先选定参数 $x$ ，之后不可更改。
初始时玩家手上有 $m$ 把钥匙，每个钥匙有一个正整数权值。
开锁 $(p,a)$ 时，找出当前权值 $\leq p$ 且最大的钥匙 $k$，若 $kx\geq a$ 且 $kx\bmod p=a$ ，则开锁成功。
开锁成功后，使用过的钥匙会消失，玩家会获得一把新的钥匙（权值确定）。
求 $x$ 的最小解，或指出无解。
$n,m\leq 10^5$ ，全体 $p_i$ 的最小公倍数 $\leq 10^{12}$。
------------
（签到）科技题。
首先，若有解，每一步使用的钥匙是可以确定的。可以用 `multiset` 求出。
然后就变成了如下问题 ：
给定 $n$ 条形如 $k_ix=a\pmod {p_i}$ 的方程与 $k_ix\geq a_i$ 的不等式，求最小整数解。
对于不等式，先求出 $x$ 的下界，求出同余方程组通解后不难得到最小解。
问题转化为解同余方程组。
考虑将 $kx=a\pmod p$ 变形为 $x=c\pmod p$ 的经典形式。
先特判 $0$ : 当 $k=a=0\pmod p$ 时方程恒成立，不考虑。当 $k=0\pmod p$ 但$c\neq 0\pmod p$时无解。
接下来，由于 $k,p$ 不一定互质,我们不能直接通过逆元来转化。
不过，我们仍然能尝试求解不定方程 $kx+py=c$ ，无解则原方程组无解。
否则由斐蜀定理得有解的充要条件 $\gcd(k,p)|c$ ，设 $d=\gcd(k,p)$。
则有 $\dfrac{k}{d}x+\dfrac{p}{d}y=\dfrac{c}{d}$ 。
我们对 $\dfrac{p}{d}$ 取模即得到 $\dfrac{k}{d}x=\dfrac{c}{d}\pmod {\dfrac{p}{d}}$
由于$\dfrac{k}{d}\perp\dfrac{p}{d}$ ，我们就可以求逆元变为经典形式了。
剩下的就是一个扩展中国剩余定理。
复杂度 $O((n+m)\log)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<set>
#define Itor set<ll>::iterator
#define ll long long
#define MaxN 100500
using namespace std;
const int mod=998244353;
ll mul(ll a,ll b,ll m)
{return (((a>>20)*b%m<<20)+(a-(a>>20<<20))*b)%m;}
ll gcd(ll a,ll b)
{return !b ? a : gcd(b,a%b);}
ll lcm(ll a,ll b)
{return a/gcd(a,b)*b;}
void exgcd(ll a,ll b,ll &x,ll &y){
if (!b){x=1;y=0;return ;}
exgcd(b,a%b,y,x);y-=(a/b)*x;
}
ll inv(ll a,ll m){
ll x,y;exgcd(a,m,x,y);
return (x+m)%m;
}
bool fl;
void merge(ll &c1,ll &p1,ll c2,ll p2)
{
ll c=(c2-c1%p2+p2)%p2,d=gcd(p1,p2);
if (c%d){puts("-1");fl=1;return ;}
ll k,y;exgcd(p1,p2,k,y);
ll p=lcm(p1,p2);
c1=(c1+mul(mul(k,p1,p),c/d,p))%p;
p1=p;
}
multiset<ll> s;
ll a[MaxN],k[MaxN],p[MaxN],t[MaxN]
,mx,tc,tp;
void calc(ll k,ll c,ll p)
{
mx=max(mx,(c-1)/k+1);
if (k%p==0){
if (c%p==0)return ;
else {puts("-1");fl=1;return ;}
}
ll d=gcd(k,p);
if (c%d){puts("-1");fl=1;return ;}
k/=d;p/=d;c/=d;
c=mul(c,inv(k,p),p);
merge(tc,tp,c,p);
}
int n,m;
void solve()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)scanf("%lld",&a[i]);
for (int i=1;i<=n;i++)scanf("%lld",&p[i]);
for (int i=1;i<=n;i++)scanf("%lld",&t[i]);
s.clear();
for (int i=1;i<=m;i++){
ll x;scanf("%lld",&x);
s.insert(x);
}
for (int i=1;i<=n;i++){
Itor it=s.upper_bound(a[i]);
if (it!=s.begin())it--;
k[i]=*it;s.erase(it);
s.insert(t[i]);
}
mx=0;tp=1;tc=0;fl=0;
for (int i=1;i<=n&&!fl;i++)
calc(k[i],a[i],p[i]);
if (fl)return ;
ll tk=mx/tp;
while(tk*tp+tc<mx)tk++;
printf("%lld\n",tk*tp+tc);
}
int main()
{
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
```
# D2T2 [情报中心](https://www.luogu.com.cn/problem/P4775)
见 [题解 【P4775 [NOI2018] 情报中心】](https://www.luogu.com.cn/blog/command-block/solution-p4775)
# D2T3 [多边形](https://www.luogu.com.cn/problem/P4776)
**题意** ： 给出一棵 $n$ 个节点的有根树。
dfs 该树，优先走编号小的儿子，按照访问顺序将叶子排成一个序列 $A$。
对于叶子 $u,v$ ，若他们在 $A$ 中的位置为 $i,j$ ，记 $d(u,v)=\min\big(|i-j|,|A|-|i-j|\big)$
建立新的无向图 $G$ 。$u,v$ 之间有边当且仅当 ：
- $d(u,v)\leq K$。
- $u,v$ 在树中直接相连。
求图 $G$ 的哈密尔顿回路数目，答案对 $998244353$ 取模。
$n\leq 1000,k\leq 3$。
------------
丧心病狂的大胖题……
要不起。
$15$ 分暴力，走了。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define MaxN 1050
using namespace std;
vector<int> t[MaxN],g[MaxN];
int p[MaxN],tn;
void pfs(int u)
{
if (!t[u].size())p[++tn]=u;
sort(t[u].begin(),t[u].end());
for (int i=0;i<t[u].size();i++)
pfs(t[u][i]);
}
bool vis[MaxN];int n,k,ans;
void dfs(int u,int cnt)
{
if (cnt==n){
for (int i=0;i<g[u].size();i++)
if (g[u][i]==1)ans++;
return ;
}
vis[u]=1;
for (int i=0,v;i<g[u].size();i++)
if (!vis[v=g[u][i]])dfs(v,cnt+1);
vis[u]=0;
}
int main()
{
scanf("%d%d",&n,&k);
if (n>20)return 0;
for (int i=2,f;i<=n;i++){
scanf("%d",&f);
t[f].pb(i);
g[f].pb(i);g[i].pb(f);
}pfs(1);
k=min(k,tn/2);
for (int i=1;i<=tn;i++)
for (int j=i+1;j<=i+k;j++){
int v=(j+tn-1)%tn+1;
g[p[i]].pb(p[v]);
g[p[v]].pb(p[i]);
}
dfs(1,1);
printf("%d",ans/2);
return 0;
}
```