[关闭]
@KirinBill 2017-10-05T14:15:14.000000Z 字数 5641 阅读 1384

2017.10.3 NOIP模拟赛

题解 套题

目录

圆盘时钟

8U6Zt.png
8UZqT.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. #include <ctime>
  6. using namespace std;
  8. inline void setIO(string file){
  9.     string in=file+".in",out=file+".out";
  10.     freopen(in.c_str(),"r",stdin);
  11.     freopen(out.c_str(),"w",stdout);
  12. }
  14. template<typename type>
  15. inline void read(type &x){
  16.     int pm=1; char c;
  17.     do{
  18.         c=getchar();
  19.         if(c=='-') pm=-1;
  20.     }while(!isdigit(c));
  21.     x=c^'0';
  22.     while(c=getchar(),isdigit(c))
  23.         x=x*10+(c^'0');
  24.     x*=pm;
  25. }
  27. template<typename type>
  28. void write(type x,char c=0){
  29.     if(x<0) putchar('-'),x=-x;
  30.     if(x>9) write(x/10);
  31.     putchar(x%10|'0');
  32.     if(c) putchar(c);
  33. }
  35. #include <algorithm>
  36. #include <iostream>
  37. #include <cmath>
  39. using std::sort;
  40. using std::unique;
  41. using std::cin;
  42. using std::istream;
  43. using std::cout;
  44. using std::ostream;
  45. using std::abs;
  47. int cur;
  48. long long a[5],b[5],c[5],d[5][2];
  50. struct frac{
  51.     int up,dwn;
  52.     friend istream& operator>> (istream &in,frac &a){
  53.         read(a.up),read(a.dwn);
  54.         return in;
  55.     }
  56. }hm,hs,ms;
  57. struct clk{
  58.     int h,m,s;
  59.     friend bool operator< (const clk &a,const clk &b){
  60.         if(a.h!=b.h) return a.h<b.h;
  61.         else if(a.m!=b.m) return a.m<b.m;
  62.         else return a.s<b.s;
  63.     }
  64.     friend bool operator== (const clk &a,const clk &b){
  65.         return a.h==b.h && a.m==b.m && a.s==b.s;
  66.     }
  67.     friend ostream& operator<< (ostream &out,clk &a){
  68.         if(a.h<10) putchar('0');
  69.         write(a.h,':');
  70.         if(a.m<10) putchar('0');
  71.         write(a.m,':');
  72.         if(a.s<10) putchar('0');
  73.         write(a.s,'\n');
  74.         return out;
  75.     }
  76. }ans[50005];
  78. inline bool jud(int x,int y,int z){
  79.     long long tmp;
  80.     for(int i=1;i<=3;++i){
  81.         tmp=abs(a[i]*x+b[i]*y+c[i]*z);
  82.         if(tmp==d[i][0]) continue;
  83.         if(tmp!=d[i][1]) return false;
  84.     }
  85.     return true;
  86. }
  88. //ax+by+cz=d
  89. inline void solve(){
  90.     for(int x=0;x<=11;++x){
  91.         for(int y=0;y<=59;++y){
  92.             for(int z=0;z<=59;++z){
  93.                 if(jud(x,y,z)) ans[++cur]=(clk){x,y,z};
  94.             }
  95.         }
  96.     }
  97. }
  99. int main(){
  100.     setIO("clock");
  101.     int T;
  102.     read(T);
  103.     while(T--){
  104.         cur=0;
  105.         cin>>hm>>hs>>ms;
  106.         //h->m
  107.         a[1]=(long long)3600*hm.dwn;
  108.         b[1]=(long long)-660*hm.dwn;
  109.         c[1]=(long long)-11*hm.dwn;
  110.         d[1][0]=abs((long long)120*hm.up);
  111.         d[1][1]=abs((long long)360*120*hm.dwn-d[1][0]);
  112.         //h->s
  113.         a[2]=(long long)3600*hs.dwn;
  114.         b[2]=(long long)60*hs.dwn;
  115.         c[2]=(long long)-719*hs.dwn;
  116.         d[2][0]=abs((long long)120*hs.up);
  117.         d[2][1]=abs((long long)360*120*hs.dwn-d[2][0]);
  118.         //s->m
  119.         a[3]=0;
  120.         b[3]=(long long)60*ms.dwn;
  121.         c[3]=(long long)-59*ms.dwn;
  122.         d[3][0]=abs((long long)10*ms.up);
  123.         d[3][1]=abs((long long)360*10*ms.dwn-d[3][0]);
  124.         solve();
  125.         sort(ans+1,ans+cur+1);
  126.         cur=unique(ans+1,ans+cur+1)-ans-1;
  127.         write(cur,'\n');
  128.         for(int i=1;i<=cur;++i)
  129.             cout<<ans[i];
  130.     }
  131.     return 0;
  132. }

路径子序列

8UwTM.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  5. using std::string;
  7. inline void setIO(string file){
  8.     string in=file+".in",out=file+".out";
  9.     freopen(in.c_str(),"r",stdin);
  10.     freopen(out.c_str(),"w",stdout);
  11. }
  13. template<typename type>
  14. inline void read(type &x){
  15.     int pm=1; char c;
  16.     do{
  17.         c=getchar();
  18.         if(c=='-') pm=-1;
  19.     }while(!isdigit(c));
  20.     x=c^'0';
  21.     while(c=getchar(),isdigit(c))
  22.         x=x*10+(c^'0');
  23.     x*=pm;
  24. }
  26. template<typename type>
  27. void write(type x,char c=0){
  28.     if(x<0) putchar('-'),x=-x;
  29.     if(x>9) write(x/10);
  30.     putchar(x%10|'0');
  31.     if(c) putchar(c);
  32. }
  34. #include <queue>
  35. #include <cstring>
  37. using std::queue;
  39. const int MAXN=50005,MAXM=200005;
  40. int n,m,cnt,k,tot;
  41. int he[MAXN],dis[MAXN],rk[MAXN];
  42. bool use[MAXN];
  44. struct line{int to,nex;}ed[MAXM<<1];
  46. inline void addE(int u,int v){
  47.     ed[++cnt]=(line){v,he[u]};
  48.     he[u]=cnt;
  49. }
  51. inline int BFS(){
  52.     static queue<int> que;
  53.     while(que.size()) que.pop();
  54.     memset(dis,-1,sizeof(dis));
  55.     dis[1]=0;
  56.     que.push(1);
  57.     int u;
  58.     while(que.size()){
  59.         u=que.front();
  60.         que.pop();
  61.         for(int i=he[u],v;i;i=ed[i].nex){
  62.             v=ed[i].to;
  63.             if(rk[v]>rk[u] && dis[v]==-1 && use[v]){
  64.                 dis[v]=dis[u]+1;
  65.                 if(v==n) return dis[v];
  66.                 que.push(v);
  67.             }
  68.         }
  69.     }
  70. }
  72. int main(){
  73.     setIO("seqpath");
  74.     int T;
  75.     read(T);
  76.     int u;
  77.     while(T--){
  78.         cnt=tot=0;
  79.         memset(use,false,sizeof(use));
  80.         memset(he,0,sizeof(he));
  81.         memset(ed,0,sizeof(ed));
  82.         read(n),read(m),read(k);
  83.         read(u),use[u]=true,rk[u]=++tot;
  84.         for(int i=1,v;i<=k;++i){
  85.             read(v),use[v]=true,rk[v]=++tot;
  86.             addE(u,v),addE(v,u);
  87.             u=v;
  88.         }
  89.         for(int i=1,lim=m-k,v;i<=lim;++i){
  90.             read(u),read(v);
  91.             addE(u,v),addE(v,u);
  92.         }
  93.         write(BFS(),'\n');
  94.     }
  95.     return 0;
  96. }

聚会

8Utn6.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <climits>
  7. using std::sort;
  8. using std::min;
  9. using std::abs;
  10. using std::next_permutation;
  12. const int MAXN=7;
  13. int n,mx,my;
  14. 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];
  15. long long ans;
  16. bool vis[MAXN<<1][MAXN<<1];
  18. inline int lim(int x){
  19.     static int dta=MAXN;
  20.     return x+dta;
  21. }
  23. inline void cal_mid(){
  24.     static int tmpx[MAXN],tmpy[MAXN];
  25.     memcpy(tmpx,sx,sizeof(tmpx));
  26.     memcpy(tmpy,sy,sizeof(tmpy));
  27.     sort(tmpx+1,tmpx+n+1);
  28.     sort(tmpy+1,tmpy+n+1);
  29.     mx=(tmpx[(n>>1)+1]+tmpx[n+1>>1])>>1;
  30.     my=(tmpy[(n>>1)+1]+tmpy[n+1>>1])>>1;
  31. }
  33. inline long long cal(){
  34.     static int pmt[MAXN];
  35.     long long ret=LLONG_MAX;
  36.     for(int i=1;i<=n;++i)
  37.         pmt[i]=i;
  38.     long long dis;
  39.     do{
  40.         dis=0;
  41.         for(int i=1;i<=n;++i)
  42.             dis+=(long long)abs(sx[pmt[i]]-tx[i])+abs(sy[pmt[i]]-ty[i]);
  43.         ret=min(ret,dis);
  44.     }while(next_permutation(pmt+1,pmt+n+1));
  45.     return ret;
  46. }
  48. void DFS(int now,int l,int r){
  49.     if(now>n){
  50.         ans=min(ans,cal());
  51.         return;
  52.     }
  53.     for(int i=l,nr;i<=r;++i){
  54.         tx[now]=canx[i],ty[now]=cany[i];
  55.         nr=r;
  56.         for(int j=0,x,y;j<4;++j){
  57.             x=canx[i]+dirx[j],y=cany[i]+diry[j];
  58.             if(!vis[lim(x)][lim(y)]){
  59.                 ++nr,canx[nr]=x,cany[nr]=y;
  60.                 vis[lim(x)][lim(y)]=true;
  61.             }
  62.         }
  63.         DFS(now+1,i+1,nr);
  64.         for(int j=r+1;j<=nr;++j)
  65.             vis[lim(canx[j])][lim(cany[j])]=false;
  66.     }
  67. }
  69. inline void solve(){
  70.     cal_mid();
  71.     for(int i=1;i<=n;++i)
  72.         sx[i]-=mx,sy[i]-=my;
  73.     memset(vis,false,sizeof(vis));
  74.     vis[lim(0)][lim(0)]=true;
  75.     ans=LLONG_MAX;
  76.     for(int i=0,x,y;i<4;++i){
  77.         x=dirx[i],y=diry[i];
  78.         canx[i+1]=x,cany[i+1]=y;
  79.         vis[lim(x)][lim(y)]=true;
  80.     }
  81.     DFS(2,1,4);
  82. }
  84. int main(){
  85.     freopen("meet.in","r",stdin);
  86.     freopen("meet.out","w",stdout);
  87.     int T;
  88.     scanf("%d",&T);
  89.     while(T--){
  90.         scanf("%d",&n);
  91.         for(int i=1;i<=n;++i)
  92.             scanf("%d%d",&sx[i],&sy[i]);
  93.         solve();
  94.         printf("%lld\n",ans);
  95.     }
  96.     return 0;
  97. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注