2017.9.16 NOIP模拟赛

题解 套题

考试时，永远不要想着能AK。。。

目录

• 2017.9.16 NOIP模拟赛
  • Crash的任务
    • 思路
    • 代码
  • 星际旅行
    • 思路
    • 代码
  • 回家的路线
    • 思路
    • 代码

Crash的任务

思路

• 设难度恰为$i$的题目数为$exa(i)$（exact），可为$i$或$i+1$的题目数为$both(i)$；
• 由于难度为$i$和$i+1$的题目间的关系只有$both(i)$能影响，其它相对独立，所以考虑递推求解（我想叫DP，但是同班大佬D我说不是一个概念。。。）；
• 设$f(i)$为前$i$种难度的题目每种都恰好选$1$个的方案数，其中$f_0(i)$表示难度为$i$的题目只从之前$both(i-1)$剩下的和$exa(i)$中选，而$f_1(i)$表示只从$both(i)$中选；
• 则有：
  $f_0(i)=f_0(i-1)\times(both(i-1)+exa(i))+f_1(i-1)\times(\max(0,both(i-1)-1)+exa(i))$
  $f_1(i)=both(i)\times(f_0(i-1)+f_1(i-1))$
• 于是$O(n)$就切了；结果考试时...

代码

#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){
    x=0;
    int pm=1; char c;
    do{c=getchar();}while(!isdigit(c) && c!='-');
    c=='-' ? pm=-1: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);
}
const int MAXN=100005,P=1e9+7;
int n;
int exa[MAXN],both[MAXN],dp[MAXN][2];
inline int DP(){
    dp[1][0]=exa[1];
    dp[1][1]=both[1];
    for(int i=2,rest;i<=n;++i){
        rest=both[i-1]-1;
        rest= rest<0 ? 0:rest;
        dp[i][0]=(long long)dp[i-1][1]*(exa[i]+rest)%P;
        dp[i][0]=(dp[i][0]+(long long)dp[i-1][0]*(exa[i]+both[i-1])%P)%P;
        dp[i][1]=(long long)both[i]*(dp[i-1][0]+dp[i-1][1])%P;
    }
    return dp[n][0];
}
int main(){
    setIO("choose");
    read(n);
    for(int i=1;i<=n;++i)
        read(exa[i]);
    for(int i=1;i<n;++i)
        read(both[i]);
    write(DP());
    return 0;
}

星际旅行

思路

• 显然最短路在最小生成树上，但是任意两点之间都可以连边，边数高达$O(n^2)$，所以考虑缩小边的范围；
• 由于边权定义为$\min(\mid x_1-x_2 \mid,\mid y_1-y_2 \mid,\mid z_1-z_2 \mid)$，所以我们连$3(n-1)$条边，分别为对于$x,y,z$来说的最小生成树的边，这样题中的边权意义下的最小生成树的边一定被包含其中；
• 可是有些边的边权不符合题中的定义怎么办？考虑到题中取的是$\min$，所以做最小生成树时，那些不符合定义的边肯定比符合定义的边权值大，排在后面，不会影响结果。

代码

#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){
    x=0;
    int pm=1; char c;
    do{c=getchar();}while(!isdigit(c) && c!='-');
    c=='-' ? pm=-1: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::sort;
const int MAXN=1e5+5;
int n,m;
int ufs[MAXN];
struct line{
    int u,v,w;
    line(int u=0,int v=0,int w=0):u(u),v(v),w(w){}
    friend bool operator< (const line &a,const line &b){
        return a.w<b.w;
    }
}ed[MAXN*3];
struct point{
    int x,y,z,id;
    static bool cmp_x(const point &a,const point &b){
        return a.x<b.x;
    }
    static bool cmp_y(const point &a,const point &b){
        return a.y<b.y;
    }
    static bool cmp_z(const point &a,const point &b){
        return a.z<b.z;
    }
}p[MAXN];
inline void ufs_init(int n){
    for(int i=1;i<=n;++i)
        ufs[i]=i;
}
int find_anc(int x){
    if(x==ufs[x]) return x;
    ufs[x]=find_anc(ufs[x]);
    return ufs[x];
}
inline void deal(){
    sort(p+1,p+n+1,point::cmp_x);
    for(int i=1;i<n;++i)
        ed[++m]=line(p[i].id,p[i+1].id,p[i+1].x-p[i].x);
    sort(p+1,p+n+1,point::cmp_y);
    for(int i=1;i<n;++i)
        ed[++m]=line(p[i].id,p[i+1].id,p[i+1].y-p[i].y);
    sort(p+1,p+n+1,point::cmp_z);
    for(int i=1;i<n;++i)
        ed[++m]=line(p[i].id,p[i+1].id,p[i+1].z-p[i].z);
}
inline long long Kruskal(){
    ufs_init(n);
    sort(ed+1,ed+m+1);
    long long ret=0;
    for(int i=1,j=0,lim=n-1,ufa,vfa;j<lim;++i){
        ufa=find_anc(ed[i].u);
        vfa=find_anc(ed[i].v);
        if(ufa!=vfa){
            ufs[ufa]=vfa;
            ret+=ed[i].w;
            ++j;
        }
    }
    return ret;
}
int main(){
    setIO("planet");
    read(n);
    for(int i=1;i<=n;++i){
        read(p[i].x),read(p[i].y),read(p[i].z);
        p[i].id=i;
    }
    deal();
    write(Kruskal());
    return 0;
}

回家的路线

思路

我开始竟没有想到是，用了Dijkstra的思想A了，不过常数好大啊...

• 由于求的是最小中的最大，所以是二分答案；
• 考虑，怎么验证，如果已知每个点到距它最近的树的距离，每次跑一遍BFS，只走符合二分的值的要求的点看能否走到终点即可，复杂度$O(n^2 \log n^2)$；
• 现在考虑怎么处理距每个点最近的树，设$dis(x,y)$为距第$x$行第$y$列的点$(x,y)$最近的树的距离；
• 若设$last(i)=j$为扫到当前点$(x,y)$时，第$i$列最后一个出现的树在第$j$行，则有$dis(x,y)\leq\min_{i=1}^m \{\mid last(i)-x \mid +\mid i-y \mid\}$，考虑$last(i)$只更新到$(x,y)$之前，所以绝对值可以去掉；
• 而我们要求最小，所以维护一个$maxd$为$max_{i=1}^m\{ last(i)+j \}$其中，$j$为每次的$y$，那么每次可以用$x+y-maxd$来更新$dis(x,y)$；
• 但是这样只是从左上到右下的情况，我们还需要从其它三个方向也更新一下，就能在$O(n^2)$复杂度内求出$dis(x,y)$了，具体细节看代码就能明白了；
• 其实，不用预处理$dis(x,y)$也可以，zzzc18大佬的方法更为简单orz。

代码

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using std::queue;
using std::max;
using std::min;
const int MAXN=505,INF=1e9;
int n,m;
int dis[MAXN][MAXN];
char mp[MAXN][MAXN];
struct node{
    int x,y;
    node(int x=0,int y=0):x(x),y(y){}
}s,t;
inline void cal_dis(){
    static int last[MAXN];
    memset(dis,0x7f,sizeof(dis));
    memset(last,-0x3f,sizeof(last));
    for(int i=1;i<=n;++i){
        for(int j=1,maxd=-INF;j<=m;++j){
            if(mp[i][j]=='+') last[j]=i;
            maxd=max(maxd,last[j]+j);
            dis[i][j]=min(dis[i][j],i+j-maxd);
        }
    }
    memset(last,-0x3f,sizeof(last));
    for(int i=1;i<=n;++i){
        for(int j=m,maxd=-INF;j;--j){
            if(mp[i][j]=='+') last[j]=i;
            maxd=max(maxd,last[j]-j);
            dis[i][j]=min(dis[i][j],i-j-maxd);
        }
    }
    memset(last,0x3f,sizeof(last));
    for(int i=n;i;--i){
        for(int j=1,maxd=-INF;j<=m;++j){
            if(mp[i][j]=='+') last[j]=i;
            maxd=max(maxd,-last[j]+j);
            dis[i][j]=min(dis[i][j],-i+j-maxd);
        }
    }
    memset(last,0x3f,sizeof(last));
    for(int i=n;i;--i){
        for(int j=m,maxd=-INF;j;--j){
            if(mp[i][j]=='+') last[j]=i;
            maxd=max(maxd,-last[j]-j);
            dis[i][j]=min(dis[i][j],-i-j-maxd);
        }
    }
}
inline bool in_G(int x,int y){
    return x>0 && x<=n && y>0 && y<=m;
}
inline bool jud(int lim){
    static int dir[][2]={{0,1},{0,-1},{1,0},{-1,0}};
    static bool vis[MAXN][MAXN];
    static queue<node> que;
    if(dis[s.x][s.y]<lim) return false;
    while(que.size()) que.pop();
    memset(vis,false,sizeof(vis));
    que.push(s);
    vis[s.x][s.y]=true;
    node u;
    int x,y;
    while(que.size()){
        u=que.front();
        que.pop();
        for(int i=0;i<4;++i){
            x=u.x+dir[i][0],y=u.y+dir[i][1];
            if(in_G(x,y) && !vis[x][y] && dis[x][y]>=lim){
                if(x==t.x && y==t.y) return true;
                que.push(node(x,y));
                vis[x][y]=true;
            }
        }
    }
    return false;
}
inline int bin_chop(){
    int l=1,r=n+m,mid;
    while(l<=r){
        mid=l+r>>1;
        if(jud(mid)) l=mid+1;
        else r=mid-1;
    }
    return l-1;
}
int main(){
    freopen("path.in","r",stdin);
    freopen("path.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%s",mp[i]+1);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(mp[i][j]=='V') s=node(i,j);
            else if(mp[i][j]=='J') t=node(i,j);
        }
    }
    cal_dis();
    printf("%d",bin_chop());
    return 0;
}