Nyoi Round 1 Solution

考试总结

---

Nyoi Round 1 Solution

同步发表在作业部落。

题目难度较上场有所下降，可见这是一场良心温暖比赛，理论上可以做到 2h ak！（T1 40min，T2 20min，T3 25min，T4 35min）

真正的 csp/noip 模拟赛！

在考前一天我写了一下 T4 的暴力，发现跑的飞快，直接过了，血压飙升，于是赶紧联系 cdz 重造数据，hack 掉暴力之后写了一个记忆化 $85pts$​，非常恐怖，于是卡暴力卡了一天。。。在 cxy 的帮助下终于卡掉了。

简化版题解：

t1：最短路板子
t2：kmp板子
t3：平凡的问题，差分解决
t4：有趣的问题，根号分治可以完成。

T1 小 N 的迷宫

签到题。

我们发现是图论问题，又要求最小次数，所以我们会联想到最短路。

由于图要么翻转，要么不翻转，所以我们可以对于两种状态分别建一张图，然后随便连一下边跑最短路，复杂度 $O(nm\log(nm))$

由于边权只有两种，所以直接 bfs 可以做到复杂度 $O(nm)$，不过本题没卡 dijkstra。

#include<stdio.h>
#include<queue>
#include<iostream>
#define inf 1000000000
using namespace std;
const int maxn=2000005,maxm=maxn*3,maxk=1005;
int n,m,e,sx,sy,ex,ey;
int start[maxn],to[maxm],then[maxm],worth[maxm],dis[maxn],a[maxk][maxk],vis[maxn];
priority_queue< pair<int,int> >q;
string s;
inline void add(int x,int y,int z){
    then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z;
}
inline int getp(int x,int y){
    return (x-1)*m+y;
}
void build(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]==0){
                if(i>1&&a[i-1][j]==0)
                    add(n*m+getp(i,j),n*m+getp(i-1,j),0);
                if(i<n&&a[i+1][j]==0)
                    add(getp(i,j),getp(i+1,j),0);
                if(a[i-1][j]){
                    add(n*m+getp(i,j),getp(i,j),1);
                    if(j>1&&a[i][j-1]==0)
                        add(n*m+getp(i,j),n*m+getp(i,j-1),0);
                    if(j<m&&a[i][j+1]==0)
                        add(n*m+getp(i,j),n*m+getp(i,j+1),0);
                }
                if(a[i+1][j]){
                    add(getp(i,j),n*m+getp(i,j),1);
                    if(j>1&&a[i][j-1]==0)
                        add(getp(i,j),getp(i,j-1),0);
                    if(j<m&&a[i][j+1]==0)
                        add(getp(i,j),getp(i,j+1),0);
                }
            }
}
void dijkstra(int s){
    for(int i=1;i<=2*n*m;i++)
        dis[i]=inf;
    dis[s]=0,q.push(make_pair(0,s));
    while(!q.empty()){
        int x=q.top().second;
        q.pop();
        if(vis[x])
            continue;
        vis[x]=1;
        for(int i=start[x];i;i=then[i])
            if(dis[to[i]]>dis[x]+worth[i])
                dis[to[i]]=dis[x]+worth[i],q.push(make_pair(-dis[to[i]],to[i]));
    }
}
int main(){
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&ex,&ey);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    build(),dijkstra(getp(sx,sy));
    int res=min(dis[getp(ex,ey)],dis[getp(ex,ey)+n*m]);
    printf("%d\n",res==inf? -1:res);
    return 0;
}

T2 小 Y 的串串

似乎比 T1 更加签到的签到题，是不是平均难度太低了？

观察数据范围判断是线性，观察一下题意，首先跑一遍 kmp 得到所有匹配位置 $(l_1,r_1)\cdots (l_k,r_k)$。

再预处理一个 $lst_i$ 表示 位置 $i$ 表示的后缀至少要到哪里才能出现一个匹配位置。

我们设 $f_i$ 为到了第 $i$ 个位置，一共有多少种情况，不难发现 dp 转移方程是

$$\sum_{i=1}^i f_i\rightarrow \forall_{j\geqslant lst_i} f_j$$

直接前缀和扫一遍就没了，复杂度 $O(n)$。

#include<stdio.h>
#include<string.h>
const int maxn=2000005,mod=1000000007;
int n,m,now;
int f[maxn],lst[maxn],p[maxn];
char s[maxn],t[maxn];
inline int add(int x){
    return x>=mod? x-mod:x;
}
int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    scanf("%s%s",s,t),n=strlen(s),m=strlen(t);
    for(int i=1,j=0;i<m;i++){
        while(j>0&&t[i]!=t[j])
            j=p[j-1];
        if(t[i]==t[j])
            j++;
        p[i]=j;
    }
    for(int i=0,j=0;i<n;i++){
        while(j>0&&s[i]!=t[j])
            j=p[j-1];
        if(s[i]==t[j])
            j++;
        if(j==m)
            lst[i+1-m+1]=i+1;
    }
    lst[n+1]=n+1;
    for(int i=n;i>=1;i--)
        if(lst[i]==0)
            lst[i]=lst[i+1];
    for(int i=1;i<=n;i++)
        f[lst[i]]=add(f[lst[i]]+now+1),f[i]=add(f[i]+f[i-1]),now=add(now+f[i]);
    printf("%d\n",now);
    return 0;
}

T3 小 N 的序列

这里令 $k$ 为题目中的 $\Sigma$。

题目难度有所提升，但是仍然很简单，有经验的选手应该可以秒掉。

考虑直接列出式子暴力上莫反：

$$\sum_{i_1=1}^k\sum_{i_2=1}^k\cdots\sum_{i_n=1}^k[\gcd(i_1,i_2,\cdots,i_n)=1]=\sum_{i_1=1}^k\sum_{i_2=1}^k\cdots\sum_{i_n=1}^k\sum_{d\mid \gcd(i_1,i_2,\cdots,i_n)}\mu(d)\\=\sum_{d=1}^k\mu(d)\lfloor\frac{k}{d}\rfloor^n$$

这里看似要直接进行除法分块，但这样的复杂度为 $O(n\sqrt n\log n)$，实现精细可以做到 $O(n\sqrt n)$，但是还是无法通过本题。

我们发现我们要对全局求解，于是对于每个位置求解是没有前途的，我们应该考虑每个值的贡献。

固定 $d$，考虑除以 $d$ 下取整这个函数，隔 $d$ 个数才会变化一遍，也就是说 $1\cdots d$ 得到的贡献永远为 $0$， $d+1\cdots 2d$ 得到的贡献永远为 $\mu(d)$，$2d+1\cdots 3d$ 得到的贡献永远为 $2^n\mu(d)$。

这明显是差分的模型，直接枚举 $d$ 并枚举 $d$ 的倍数，差分解决就好了，记得用线性筛预处理数的 $n$ 次幂。

时间复杂度：$O(n\log n)$。（默认 $n,k$ 同阶）

bonus：值域固定，长度不固定

#include<stdio.h>
const int maxn=2000005,mod=1000000007;
int n,k,cnt,ans;
int a[maxn],p[maxn],miu[maxn],b[maxn],mul[maxn];
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)
            res=1ll*res*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return res;
}
int main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    scanf("%d%d",&n,&k);
    miu[1]=p[1]=1;
    for(int i=1;i<=k;i++){
        if(p[i]==0)
            a[++cnt]=i,miu[i]=-1;
        for(int j=1;j<=cnt&&i*a[j]<=k;j++){
            p[i*a[j]]=1;
            if(i%a[j]==0){
                miu[i*a[j]]=0;
                break;
            }
            miu[i*a[j]]=-miu[i];
        }
    }
    for(int i=1;i<=k;i++)
        mul[i]=ksm(i,n);
    for(int i=1;i<=k;i++)
        for(int j=i;j<=k;j+=i)
            b[j]=((b[j]+1ll*(mul[j/i]-mul[j/i-1]+mod)%mod*miu[i]%mod)%mod+mod)%mod;
    for(int i=1;i<=k;i++)
        b[i]=(b[i]+b[i-1])%mod,ans=(ans+(b[i]^i)%mod)%mod;
    printf("%d\n",ans);
    return 0;
}

T4 小 Y 的旅行

读题发现保证 $x$ 是 $y$ 的祖先这一性质，它提示我们可以预处理一个位置向上走若干个结点的答案并合并。

向上走多少个结点呢？此时在我们面前的有三条路：倍增/树剖/分块。

我们观察 $n$ 和 $a_i$ 的范围是很不对劲的，它只到了 $5\times 10^4$，根据大家良好的数感可以发现它是接近 $2^{16}$的。

也就是说，$dis$ 和 $a_i$ 均只有 $16$ 位。

考虑根号分治+分块，每个点预处理向上走 $2^8$ 个结点的答案，那么这些结点的 $dis$ 前八位（指 $2^8$ 到 $2^{15}$ 对应的位）是相同的，但是会随着询问改变，于是我们预处理 $f_{x,k}$ 表示结点 $x$ 向上走 $2^8$ 个结点，目前的 $dis$ 前八位为 $k$ 的最大惊喜值。

这个东西在树上 dfs 一遍，每个位置向上暴力跳然后建一个 trie 就可以了。

向上跳完大小为 $2^8$ 的整块之后，散块暴力算就可以了。

时间复杂度：$O(2^{11}(n+q)+\frac{nq}{2^8})$，可以通过。

#include<stdio.h>
const int maxn=50005,maxm=maxn<<1,t=256,maxt=257;
int n,m,e,tot;
int val[maxn],start[maxn],to[maxm],then[maxm],f[maxn][maxt],g[maxn][maxt],chd[maxn<<8][2],ffa[maxn],fa[maxn],dep[maxn];
inline int max(int a,int b){
    return a>b? a:b;
}
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
void insert(int x){
    int now=1;
    for(int i=7;i>=0;now=chd[now][(x>>i)&1],i--)
        if(chd[now][(x>>i)&1]==0)
            chd[now][(x>>i)&1]=++tot,chd[tot][0]=chd[tot][1]=0;
}
int query(int x,int p){
    int now=1,val=0,res=0;
    for(int i=7;i>=0;i--){
        int c=(x>>i)&1;
        if(chd[now][c^1])
            now=chd[now][c^1],val|=((c^1)<<i),res|=(1<<i);
        else now=chd[now][c],val|=(c<<i);
    }
    return (res<<8)|g[p][val];
}
void dfs(int x,int last){
    fa[x]=last,dep[x]=dep[last]+1;
    if(dep[x]>=t){
        int y=x;
        tot=1,chd[tot][0]=chd[tot][1]=0;
        while(dep[x]-dep[y]<t)
            insert(val[y]>>8),g[x][val[y]>>8]=max(g[x][val[y]>>8],((dep[x]-dep[y])^val[y])&(t-1)),y=fa[y];
        ffa[x]=y;
        for(int i=0;i<t;i++)
            f[x][i]=query(i,x);
    }
    for(int i=start[x];i;i=then[i])
        if(to[i]!=last)
            dfs(to[i],x);
}
int main(){
    freopen("trip.in","r",stdin);
    freopen("trip.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&val[i]);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=m;i++){
        int x,y,res=0,tot=0,dis=0;
        scanf("%d%d",&x,&y);
        while(dep[y]-t>=dep[x])
            res=max(res,f[y][tot]),y=ffa[y],tot++;
        dis=tot<<8;
        while(y!=x)
            res=max(res,dis^val[y]),y=fa[y],dis++;
        res=max(res,dis^val[x]);
        printf("%d\n",res);
    }
    return 0;
}