@KirinBill 2017-10-05T06:15:14.000000Z 字数 5641 阅读 685

# 2017.10.3 NOIP模拟赛

题解 套题

## 圆盘时钟

### 思路

• 直接暴力枚举时间，算一下夹角是不是题目询问的即可；
• 也可以用一些麻烦的方法检验（比如我）。。。

### 代码

#include <cstdio>#include <cctype>#include <string>#include <ctime>using namespace std;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>#include <iostream>#include <cmath>using std::sort;using std::unique;using std::cin;using std::istream;using std::cout;using std::ostream;using std::abs;int cur;long long a[5],b[5],c[5],d[5][2];struct frac{    int up,dwn;    friend istream& operator>> (istream &in,frac &a){        read(a.up),read(a.dwn);        return in;    }}hm,hs,ms;struct clk{    int h,m,s;    friend bool operator< (const clk &a,const clk &b){        if(a.h!=b.h) return a.h<b.h;        else if(a.m!=b.m) return a.m<b.m;        else return a.s<b.s;    }    friend bool operator== (const clk &a,const clk &b){        return a.h==b.h && a.m==b.m && a.s==b.s;    }    friend ostream& operator<< (ostream &out,clk &a){        if(a.h<10) putchar('0');        write(a.h,':');        if(a.m<10) putchar('0');        write(a.m,':');        if(a.s<10) putchar('0');        write(a.s,'\n');        return out;    }}ans[50005];inline bool jud(int x,int y,int z){    long long tmp;    for(int i=1;i<=3;++i){        tmp=abs(a[i]*x+b[i]*y+c[i]*z);        if(tmp==d[i][0]) continue;        if(tmp!=d[i][1]) return false;    }    return true;}//ax+by+cz=dinline void solve(){    for(int x=0;x<=11;++x){        for(int y=0;y<=59;++y){            for(int z=0;z<=59;++z){                if(jud(x,y,z)) ans[++cur]=(clk){x,y,z};            }        }    }}int main(){    setIO("clock");    int T;    read(T);    while(T--){        cur=0;        cin>>hm>>hs>>ms;        //h->m        a[1]=(long long)3600*hm.dwn;        b[1]=(long long)-660*hm.dwn;        c[1]=(long long)-11*hm.dwn;        d[1][0]=abs((long long)120*hm.up);        d[1][1]=abs((long long)360*120*hm.dwn-d[1][0]);        //h->s        a[2]=(long long)3600*hs.dwn;        b[2]=(long long)60*hs.dwn;        c[2]=(long long)-719*hs.dwn;        d[2][0]=abs((long long)120*hs.up);        d[2][1]=abs((long long)360*120*hs.dwn-d[2][0]);        //s->m        a[3]=0;        b[3]=(long long)60*ms.dwn;        c[3]=(long long)-59*ms.dwn;        d[3][0]=abs((long long)10*ms.up);        d[3][1]=abs((long long)360*10*ms.dwn-d[3][0]);        solve();        sort(ans+1,ans+cur+1);        cur=unique(ans+1,ans+cur+1)-ans-1;        write(cur,'\n');        for(int i=1;i<=cur;++i)            cout<<ans[i];    }    return 0;}

## 路径子序列

### 思路

• 题意其实就是只能按给定那个$1 \to n$路径的点的顺序走的$1 \to n$的最短路；
• 直接BFS即可，只走符合要求的边。

### 代码

#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 <cstring>using std::queue;const int MAXN=50005,MAXM=200005;int n,m,cnt,k,tot;int he[MAXN],dis[MAXN],rk[MAXN];bool use[MAXN];struct line{int to,nex;}ed[MAXM<<1];inline void addE(int u,int v){    ed[++cnt]=(line){v,he[u]};    he[u]=cnt;}inline int BFS(){    static queue<int> que;    while(que.size()) que.pop();    memset(dis,-1,sizeof(dis));    dis[1]=0;    que.push(1);    int u;    while(que.size()){        u=que.front();        que.pop();        for(int i=he[u],v;i;i=ed[i].nex){            v=ed[i].to;            if(rk[v]>rk[u] && dis[v]==-1 && use[v]){                dis[v]=dis[u]+1;                if(v==n) return dis[v];                que.push(v);            }        }    }}int main(){    setIO("seqpath");    int T;    read(T);    int u;    while(T--){        cnt=tot=0;        memset(use,false,sizeof(use));        memset(he,0,sizeof(he));        memset(ed,0,sizeof(ed));        read(n),read(m),read(k);        read(u),use[u]=true,rk[u]=++tot;        for(int i=1,v;i<=k;++i){            read(v),use[v]=true,rk[v]=++tot;            addE(u,v),addE(v,u);            u=v;        }        for(int i=1,lim=m-k,v;i<=lim;++i){            read(u),read(v);            addE(u,v),addE(v,u);        }        write(BFS(),'\n');    }    return 0;}

## 聚会

### 思路

• 就是暴力，但是主要问题是每个点到哪个地方；
• 显然最终的位置集中心应该是所有点横纵坐标中位数组成的新点；
• 因为若所有点最终可以聚到一个点上，反证法易证到上述的点曼哈顿距离和最小，虽然该题不允许点重合，但考虑也是聚到一起，也可以证明出来；
• 那么接下来，我们可以DFS求一下最终位置集的形状，具体操作就是每次从可行点集中选一个点，将该点四周的点加到可行点集中，这样选出来的点都是可行的；
• 最后，我们可以暴力但是很方便的直接求一个排列，即枚举每个点最终到达这次枚举的位置集中哪个点，然后算一下曼哈顿距离即可。

### 代码

#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#include <climits>using std::sort;using std::min;using std::abs;using std::next_permutation;const int MAXN=7;int n,mx,my;int dirx[]={1,0,-1,0},diry[]={0,1,0,-1},sx[MAXN],sy[MAXN],tx[MAXN],ty[MAXN],canx[MAXN<<2],cany[MAXN<<2];long long ans;bool vis[MAXN<<1][MAXN<<1];inline int lim(int x){    static int dta=MAXN;    return x+dta;}inline void cal_mid(){    static int tmpx[MAXN],tmpy[MAXN];    memcpy(tmpx,sx,sizeof(tmpx));    memcpy(tmpy,sy,sizeof(tmpy));    sort(tmpx+1,tmpx+n+1);    sort(tmpy+1,tmpy+n+1);    mx=(tmpx[(n>>1)+1]+tmpx[n+1>>1])>>1;    my=(tmpy[(n>>1)+1]+tmpy[n+1>>1])>>1;}inline long long cal(){    static int pmt[MAXN];    long long ret=LLONG_MAX;    for(int i=1;i<=n;++i)        pmt[i]=i;    long long dis;    do{        dis=0;        for(int i=1;i<=n;++i)            dis+=(long long)abs(sx[pmt[i]]-tx[i])+abs(sy[pmt[i]]-ty[i]);        ret=min(ret,dis);    }while(next_permutation(pmt+1,pmt+n+1));    return ret;}void DFS(int now,int l,int r){    if(now>n){        ans=min(ans,cal());        return;    }    for(int i=l,nr;i<=r;++i){        tx[now]=canx[i],ty[now]=cany[i];        nr=r;        for(int j=0,x,y;j<4;++j){            x=canx[i]+dirx[j],y=cany[i]+diry[j];            if(!vis[lim(x)][lim(y)]){                ++nr,canx[nr]=x,cany[nr]=y;                vis[lim(x)][lim(y)]=true;            }        }        DFS(now+1,i+1,nr);        for(int j=r+1;j<=nr;++j)            vis[lim(canx[j])][lim(cany[j])]=false;    }}inline void solve(){    cal_mid();    for(int i=1;i<=n;++i)        sx[i]-=mx,sy[i]-=my;    memset(vis,false,sizeof(vis));    vis[lim(0)][lim(0)]=true;    ans=LLONG_MAX;    for(int i=0,x,y;i<4;++i){        x=dirx[i],y=diry[i];        canx[i+1]=x,cany[i+1]=y;        vis[lim(x)][lim(y)]=true;    }    DFS(2,1,4);}int main(){    freopen("meet.in","r",stdin);    freopen("meet.out","w",stdout);    int T;    scanf("%d",&T);    while(T--){        scanf("%d",&n);        for(int i=1;i<=n;++i)            scanf("%d%d",&sx[i],&sy[i]);        solve();        printf("%lld\n",ans);    }    return 0;}

• 私有
• 公开
• 删除