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

2017.10.3 NOIP模拟赛

题解 套题

目录


圆盘时钟

8U6Zt.png
8UZqT.png

思路

代码

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

路径子序列

8UwTM.png

思路

代码

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

聚会

8Utn6.png

思路

代码

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