2017.10.9 NOIP模拟赛

题解 套题

赛后AK，心态爆炸。

目录

• 2017.10.9 NOIP模拟赛
  • String Master
    • 思路
    • 代码
  • Tourist Attractions
    • 思路
    • 代码
  • Walk
    • 思路
    • 代码

String Master

思路

• 考虑到是最长公共子串，那么我们应尽可能使匹配部分连续，所以$k$次修改机会一定是用在连续的一段上的；
• 再看这题数据量显然$O(n^3)$，那么直接枚举公共子串在两个串的开头，暴力匹配即可。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <algorithm>
using std::max;
const int MAXN=305;
int n,k;
char s[MAXN],t[MAXN];
inline int solve(int sl,int tl){
    int rest=k,ret=0;
    for(int i=sl,j=tl;i<=n && j<=n;++i,++j){
        if(s[i]!=t[j]){
            if(!rest) break;
            else --rest;
        }
        ++ret;
    }
    return ret;
}
int main(){
#ifdef DEBUG
    setIO("a");
#endif
    read(n),read(k);
    scanf("%s%s",s+1,t+1);
    int ans=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            ans=max(ans,solve(i,j));
        }
    }
    write(ans);
    return 0;
}

Tourist Attractions

思路

• 如果直接DFS的话，$n=10$的完全图就很悬了（我没试）；
• 那么我们枚举路径的前三个点$u,v,w$，判断$w$是否和$u$有连边即可$O(n^3)$求解；
• 继续思考，既然对于$w$只需判断是不是和$u$有连边，我们不妨判断$v$和$w$是否连有公共点；
• 也就是，如果不考虑环，枚举路径中间的两个点$v,w$的话，贡献是$(deg(v)-1)\times(deg(w)-1)$；
• 考虑到环，就减去那些起始点和终点重合的个数，也就是$v,w$所能到达的点的交集；
• 这样还是$O(n^3)$，但求交集用bitset优化的话，复杂度就除了个神奇的东西，可以过了。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <bitset>
using std::bitset;
const int MAXN=1505;
int deg[MAXN];
char s[MAXN];
bitset<MAXN> G[MAXN],tmp;
int main(){
#ifdef DEBUG
    setIO("b");
#endif
    int n;
    read(n);
    for(int i=1;i<=n;++i){
        scanf("%s",s+1);
        for(int j=1;j<=n;++j)
            G[i][j]=s[j]^'0';
    }
    for(int i=1;i<=n;++i)
        deg[i]=G[i].count();
    long long ans=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(i==j || !G[i][j]) continue;
            ans+=(long long)(deg[i]-1)*(deg[j]-1);
            tmp=G[i]&G[j];
            ans-=tmp.count();
        }
    }
    write(ans);
    return 0;
}

Walk

思路

• 暴力建图BFS的话$40$分是有的，但瓶颈在建图，所以我们考虑怎么优化这个过程；
• 首先，如果暴力判断两点之间是否还应连边显然要$O(n^2)$；
• 如果建一些虚拟节点表示不同的$val$的话，每个点$u$应连边$u \to val(u),val(u) \to u$，边权分别为$1,0$，这样，值相同的点之间就不需要连边了，但题目所给的$m$条边还是要连；
• 而剩下的要求的边只用在虚拟节点中连零边就可以了，但如果暴力枚举，还是要$O(w \times 2^{\log w})=O(w^2)$；
• 考虑我们在虚拟节点间连的都是零边，那么在保证联通性正确的前提下应该是可以少连边的；
• 其实是可以的，每个值$w$，只需枚举每一位，连这一位为$0$的值$w'$即可，这样联通性是合法的，但边数减到了$O(w \log w)$；
• 这样还会MLE，其实，我们不用建出这些边，只需在跑最短路时算一下能转移到哪里就行了；
• 复杂度有些卡，用了堆优化的SPFA（Dijkstra重复入堆可能会爆）。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <queue>
#include <vector>
#include <functional>
#include <cstring>
using std::priority_queue;
using std::vector;
using std::greater;
const int MAXN=200005,MAXM=300005,MAXW=1<<20,MAXV=MAXN+MAXW,MAXE=MAXM+(MAXN<<1);
int n,m;
int he[MAXV],dis[MAXV];
struct line{int to,nex,w;}ed[MAXE];
struct node{
    int id;
    node(int id=0):id(id){}
    friend bool operator> (const node &a,const node &b){
        return dis[a.id]>dis[b.id];
    }
};
inline void addE(int u,int v,int w){
    static int cnt=0;
    ed[++cnt]=(line){v,he[u],w};
    he[u]=cnt;
}
inline void hp_SPFA(){
    static bool inQ[MAXV];
    static priority_queue<node,vector<node>,greater<node> > pq;
    memset(dis,0x7f,sizeof(dis));
    dis[1]=0;
    pq.push(node(1));
    inQ[1]=true;
    int u;
    while(pq.size()){
        u=pq.top().id;
        pq.pop();
        inQ[u]=false;
        for(int i=he[u],v,d;i;i=ed[i].nex){
            v=ed[i].to,d=dis[u]+ed[i].w;
            if(dis[v]>d){
                dis[v]=d;
                if(!inQ[v]){
                    pq.push(node(v));
                    inQ[v]=true;
                }
            }
        }
        if(u>n){
            for(int j=0,v,w=u-n,d=dis[u];(1<<j)<w;++j){
                if(w&1<<j){
                    v=(w^1<<j)+n;
                    if(dis[v]>d){
                        dis[v]=d;
                        if(!inQ[v]){
                            pq.push(node(v));
                            inQ[v]=true;
                        }
                    }
                }
            }
        }
    }
}
int main(){
#ifdef DEBUG
    setIO("c");
#endif
    read(n),read(m);
    for(int i=1,w,v;i<=n;++i){
        read(w),v=n+w;
        addE(i,v,1),addE(v,i,0);
    }
    for(int i=1,u,v;i<=m;++i){
        read(u),read(v);
        addE(u,v,1);
    }
    hp_SPFA();
    for(int i=1;i<=n;++i){
        if(dis[i]>n) dis[i]=-1;
        write(dis[i],'\n');
    }
    return 0;
}