喵哈哈村的魔法考试 Round #15 (Div.2) 题解-白红宇

喵哈哈村的魔法考试 Round #15 (Div.2) 题解

阅读量：6284 次

发布时间：2019-06-22

本文共 5712 字，大约阅读时间需要 19 分钟。

哗啦啦村的奇迹果实（一）

题解：显然答案就是最大值减去最小值。

#include
    
     using namespace std;const int maxn = 1e5+7;int n,a[maxn];int main(){    while(cin>>n){        int x;scanf("%d",&x);        int Mx = x;        int Mi = x;        for(int i=1;i

哗啦啦村的奇迹果实（二）

题解：虽然0可以与其他位置交换，但是0不改变其他数字的相对位置，所以只要找到相对位置，然后进行匹配即可。

#include
    
     using namespace std;const int maxn = 200005;int a[maxn],b[maxn],tot1,tot2,n;int solve(){    tot1=0;    tot2=0;    for(int i=0;i
     
      >n)solve();}

哗啦啦村的奇迹果实（三）

题解：动态规划。

f[i][j][0]表示当前小象位于格子(i,j)且上一个位置是(i-1,j)所看见的老鼠的最少数量。

f[i][j][1]表示当前小象位于格子(i,j)且上一个位置是(i,j-1)所看见的老鼠的最少数量。

f[i][j][0]=min(f[i-1][j][0]+a[i][j-1],f[i-1][j][1])+a[i+1][j]+a[i][j+1]

f[i][j][1]=min(f[i][j-1][0],f[i][j-1][1]+a[i-1][j])+a[i+1][j]+a[i][j+1]

answer=min(f[n][m][0],f[n][m][1])。

复杂度为 O(NM)。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define N 1100using namespace std;int n,m;int f[N][N];int g[N][N];int a[N][N];int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            scanf("%d",&a[i][j]);    memset(f,0x3f,sizeof(f));    memset(g,0x3f,sizeof(g));    f[1][1]=g[1][1]=a[1][1]+a[1][2]+a[2][1];    for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)        {            if(j-1>0)                f[i][j]=min(f[i][j],min(f[i][j-1]+a[i-1][j]+a[i][j+1]+a[i+1][j],g[i][j-1]+a[i][j+1]+a[i+1][j]));            if(i-1>0)                g[i][j]=min(g[i][j],min(f[i-1][j]+a[i][j+1]+a[i+1][j],g[i-1][j]+a[i][j-1]+a[i][j+1]+a[i+1][j]));        }    }    printf("%d\n",min(f[n][m],g[n][m]));}

哗啦啦村的奇迹果实（四）

算法：最短路。

将“如果城市 B 愿意与城市 A 建立合作关系，当且仅当对于所有满足 d(A,C)<=d(A,B)的城市

C，都有 R(C)<=R(B)。”这一条件转化为“如果城市 B 愿意与城市 A 建立合作关系，当且仅当

对于所有满足 R(C)>R(B)的城市 C，都有 d(A,C)>d(A,B)。”

我们倒序枚举 R 的值 r，然后枚举 R(X)=r 的点 X，以每个点为起点对原图做最短路。设 lim[i]

表示所有点 K(R(K)>R(X))中到点 i 的最小距离，设 dist[i]表示 X 到 i 的最短路。对于点 i，在最

短路过程中，如果 dist[i]>=lim[i]，那么表示比 X 的 R 值大的某个点到点 i 的最短距离要比 X

到 i 的距离短，所以 i 不会与 X 建立合作关系，而且不会用 dist[i]去更新其它点的最短路了。

因此，一个点用来更新其它点的条件是 dist[i]<lim[i]，此时答案+1，因为答案<=30N，所以总

的更新次数不会超过 30N 次。所以最后复杂度为 O(kNlogN)，k 为常数。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int INF=0x3f3f3f3f;const int N=30010,M=300100;int n,m,nowRank;int head[N],key[M],Next[M],len[M],cnt;int Rank[N],dis[N],lim[N],minr[N];int stack[N],tp;int top,ans;struct Heap{    int x,w;    Heap(void){}    Heap(int _x,int _w):x(_x),w(_w){}}heap[10*M];void add(int x,int y,int z){    Next[++cnt]=head[x];    key[cnt]=y;    len[cnt]=z;    head[x]=cnt;}inline bool cmp(const Heap &a,const Heap &b){    if(a.w!=b.w) return a.w>b.w;    else return Rank[a.x]
         
          nowRank) continue; if(dis[key[i]]>sta.w+len[i]&&lim[key[i]]>sta.w+len[i]) { dis[key[i]]=sta.w+len[i]; heap[++top]=Heap(key[i],dis[key[i]]); push_heap(heap+1,heap+top+1,cmp); } } }}int main(){ memset(head,-1,sizeof head); memset(dis,0x3f,sizeof dis); memset(lim,0x3f,sizeof lim); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&Rank[i]); for(int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z); for(int i=10;i>=1;i--) { nowRank=i; memset(minr,0x3f,sizeof minr); for(int j=1;j<=n;j++) if(Rank[j]==i) { heap[++top]=Heap(j,0); dis[j]=0; dijk(); for(;tp;tp--) { int k=stack[tp]; if(lim[k]>dis[k]) ans++; minr[k]=min(minr[k],dis[k]); dis[k]=INF; } } for(int j=1;j<=n;j++) lim[j]=min(minr[j],lim[j]); } cout<
          
           <

哗啦啦村的奇迹果实（五）

算法：字符串 hash

枚举两段的长度 len 和第一段的起点 i，我们定义 L 为第一段与第二段的最长公共后缀，当

L>=len 的时候答案+1，而起点为 i+1 时 L 的大小仅仅取决于起点为 i 时 L 大小和 a[i+len]与

a[i+2*len+F]的相等关系：

L[i+1] = L[i] + 1 (a[i+len]=a[i+2*len+F])

L[i+1] = 0 (a[i+len]!=a[i+2*len+F])

这样朴素的枚举 len 后扫描整个序列是 N^2 的，我们考虑优化这个算法。

首先枚举两段的长度 len，然后我们在递推的时候可以发现，在长度为 len 时，我们没有必

要一格一格的递推，而可以每次向右递推 len 格。我们不妨设第一段的末尾位置为 i，第二

段的末尾位置为 j，设 frontL 表示 a[i+1]„a[i+len]与 a[j+1]„a[j+len]的最长公共前缀，设 backL

表示 a[i+1]„a[i+len]与 a[j+1]„a[j+len]的最长公共后缀，令 L 表示当前的最长公共后缀。

下面分两种情况考虑对于答案的贡献：

情况一：如果 L>=len，ans+=frontL。

情况二：反之，ans+=max(0,L+frontl-i+1)。

下面分两种情况考虑递推后的最长公共后缀 nL:

情况一：如果 a[i+1]„a[i+len]与 a[j+1]„a[j+len]整段相同，nL=L+len。

情况二：反之，nL=backl。

这样对于每个长度 len，需要递推 N/len 次，每次采用 hash+二分的方法 O(logN)的计算最长

公共前/后缀，总的复杂度为 O(NlnNlogN)。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;typedef unsigned int ull;const int N=1000010;const ull mul=133331;ll ans;int n,m,k;int b[N],a[N];int X[N];ull Hash[N];ull f[N]={1};inline int bin(int x){ int l=1,r=k; while(l<=r) { int mid=l+r>>1; if(b[mid]<=x) l=mid+1; else r=mid-1; } return r;}inline ull getHash(const int &l,const int &r){ return Hash[r]-Hash[l-1]*f[r-l+1];}inline int lcp(int x,int y){ int l=0,r=min(n-x+1,n-y+1); while(l<=r) { int mid=l+r>>1; if(getHash(x,x+mid-1)==getHash(y,y+mid-1)) l=mid+1; else r=mid-1; } return r;}inline int anti_lcp(int x,int y){ int l=0,r=min(x,y); while(l<=r) { int mid=l+r>>1; if(getHash(x-mid+1,x)==getHash(y-mid+1,y)) l=mid+1; else r=mid-1; } return r;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); X[i]=a[i]; } sort(X+1,X+n+1); X[0]=~0U>>1; for(int i=1;i<=n;i++) if(X[i]!=X[i-1]) b[++k]=X[i]; for(int i=1;i<=n;i++) a[i]=bin(a[i]); for(int i=1;i<=n;i++) f[i]=f[i-1]*mul; for(int i=1;i<=n;i++) Hash[i]=Hash[i-1]*mul+a[i]; for(int i=1;2*i+m<=n;i++) { int nowl=0; for(int j=1;;) { int len=min(i,n-(j+i+m-1)); if(!len) break; int frontl=lcp(j,j+i+m); int backl=anti_lcp(j+len-1,j+m+i+len-1); frontl=min(frontl,len); backl=min(backl,len); if(frontl==len) { if(nowl>=i) ans+=len; else ans+=max(0,nowl+frontl-i+1); nowl+=len; } else { if(nowl>=i) ans+=frontl; else ans+=max(0,nowl+frontl-i+1); nowl=backl; } j+=len; } } cout<
           
            <