[关闭]
@KirinBill 2017-10-05T13:26:45.000000Z 字数 5698 阅读 466

2017.10.5 NOIP模拟赛

题解 套题

目录


猜数游戏

AZn6j.png
AZkGR.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 <cstring>
  30. const int MAXL=2005;
  31. int n;
  32. int cnt[26],tot[10];
  33. char s[MAXL];
  34. inline int idx(char c){return c-'A';}
  35. inline void deal(){
  36. for(int i=1;i<=n;++i)
  37. ++cnt[idx(s[i])];
  38. }
  39. inline void solve(){
  40. //0
  41. tot[0]=cnt[idx('Z')];
  42. cnt[idx('Z')]=0;
  43. cnt[idx('E')]-=tot[0];
  44. cnt[idx('O')]-=tot[0];
  45. cnt[idx('R')]-=tot[0];
  46. //2
  47. tot[2]=cnt[idx('W')];
  48. cnt[idx('W')]=0;
  49. cnt[idx('O')]-=tot[2];
  50. cnt[idx('T')]-=tot[2];
  51. //4
  52. tot[4]=cnt[idx('U')];
  53. cnt[idx('U')]=0;
  54. cnt[idx('F')]-=tot[4];
  55. cnt[idx('O')]-=tot[4];
  56. cnt[idx('R')]-=tot[4];
  57. //6
  58. tot[6]=cnt[idx('X')];
  59. cnt[idx('X')]=0;
  60. cnt[idx('I')]-=tot[6];
  61. cnt[idx('S')]-=tot[6];
  62. //8
  63. tot[8]=cnt[idx('G')];
  64. cnt[idx('G')]=0;
  65. cnt[idx('E')]-=tot[8];
  66. cnt[idx('H')]-=tot[8];
  67. cnt[idx('I')]-=tot[8];
  68. cnt[idx('T')]-=tot[8];
  69. //3
  70. tot[3]=cnt[idx('T')];
  71. cnt[idx('T')]=0;
  72. cnt[idx('E')]-=tot[3]<<1;
  73. cnt[idx('H')]-=tot[3];
  74. cnt[idx('R')]-=tot[3];
  75. //5
  76. tot[5]=cnt[idx('F')];
  77. cnt[idx('F')]=0;
  78. cnt[idx('E')]-=tot[5];
  79. cnt[idx('I')]-=tot[5];
  80. cnt[idx('V')]-=tot[5];
  81. //1
  82. tot[1]=cnt[idx('O')];
  83. cnt[idx('O')]=0;
  84. cnt[idx('E')]-=tot[1];
  85. cnt[idx('N')]-=tot[1];
  86. //7
  87. tot[7]=cnt[idx('S')];
  88. cnt[idx('S')]=0;
  89. cnt[idx('E')]-=tot[7]<<1;
  90. cnt[idx('N')]-=tot[7];
  91. cnt[idx('V')]-=tot[7];
  92. //9
  93. tot[9]=cnt[idx('E')];
  94. cnt[idx('E')]=0;
  95. cnt[idx('I')]-=tot[9];
  96. cnt[idx('N')]-=tot[9]<<1;
  97. }
  98. int main(){
  99. setIO("number");
  100. scanf("%s",s+1);
  101. n=strlen(s+1);
  102. deal();
  103. solve();
  104. for(int i=0;i<=9;++i){
  105. for(int j=1;j<=tot[i];++j)
  106. putchar(i|'0');
  107. }
  108. return 0;
  109. }

暴力快递

AZtp8.png
AZfuX.png
AZggw.png

思路

代码

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <queue>
  4. #include <cmath>
  5. #include <vector>
  6. #include <functional>
  7. using std::queue;
  8. using std::abs;
  9. using std::priority_queue;
  10. using std::vector;
  11. using std::greater;
  12. const int MAXN=100005,MAXHW=505;
  13. int n,h,w,a,b,c;
  14. int dirx[]={1,0,-1,0},diry[]={0,1,0,-1};
  15. long long nearP[MAXHW][MAXHW];
  16. struct node{
  17. int x,y;
  18. long long dis;
  19. node(int x=0,int y=0,long long dis=0):x(x),y(y),dis(dis){}
  20. friend bool operator> (const node &a,const node &b){
  21. return a.dis>b.dis;
  22. }
  23. }p[MAXN];
  24. inline bool inG(node &a){
  25. return 0<=a.x && a.x<=h && 0<=a.y && a.y<=w;
  26. }
  27. inline void BFS(){
  28. static queue<node> que;
  29. memset(nearP,0x7f,sizeof(nearP));
  30. nearP[p[n].x][p[n].y]=0;
  31. for(int i=1;i<n;++i){
  32. nearP[p[i].x][p[i].y]=0;
  33. que.push(node(p[i].x,p[i].y));
  34. }
  35. node u,v;
  36. int d;
  37. while(que.size()){
  38. u=que.front();
  39. que.pop();
  40. d=nearP[u.x][u.y]+1;
  41. for(int i=0;i<4;++i){
  42. v.x=u.x+dirx[i],v.y=u.y+diry[i];
  43. if(inG(v) && nearP[v.x][v.y]>d){
  44. nearP[v.x][v.y]=d;
  45. que.push(v);
  46. }
  47. }
  48. }
  49. for(int i=0;i<=h;++i){
  50. for(int j=0;j<=w;++j)
  51. nearP[i][j]*=c;
  52. }
  53. }
  54. inline long long hp_SPFA(){
  55. static long long dis[MAXHW][MAXHW];
  56. static bool inQ[MAXHW][MAXHW];
  57. static priority_queue<node,vector<node>,greater<node> > hq;
  58. memset(dis,0x7f,sizeof(dis));
  59. memset(inQ,false,sizeof(inQ));
  60. dis[p[1].x][p[1].y]=0;
  61. hq.push(p[1]);
  62. inQ[p[1].x][p[1].y]=true;
  63. node u,v;
  64. long long d;
  65. while(hq.size()){
  66. u=hq.top();
  67. hq.pop();
  68. inQ[u.x][u.y]=false;
  69. d=dis[u.x][u.y]+c;
  70. for(int i=0;i<4;++i){
  71. v.x=u.x+dirx[i],v.y=u.y+diry[i];
  72. if(inG(v) && dis[v.x][v.y]>d){
  73. v.dis=dis[v.x][v.y]=d;
  74. if(!inQ[v.x][v.y]){
  75. hq.push(v);
  76. inQ[v.x][v.y]=true;
  77. }
  78. }
  79. }
  80. v.y=u.y;
  81. for(v.x=0;v.x<=h;++v.x){
  82. d=dis[u.x][u.y]+(long long)a*abs(u.x-v.x)+b+nearP[v.x][v.y];
  83. if(dis[v.x][v.y]>d){
  84. v.dis=dis[v.x][v.y]=d;
  85. if(!inQ[v.x][v.y]){
  86. hq.push(v);
  87. inQ[v.x][v.y]=true;
  88. }
  89. }
  90. }
  91. v.x=u.x;
  92. for(v.y=0;v.y<=w;++v.y){
  93. d=dis[u.x][u.y]+(long long)a*abs(u.y-v.y)+b+nearP[v.x][v.y];
  94. if(dis[v.x][v.y]>d){
  95. v.dis=dis[v.x][v.y]=d;
  96. if(!inQ[v.x][v.y]){
  97. hq.push(v);
  98. inQ[v.x][v.y]=true;
  99. }
  100. }
  101. }
  102. }
  103. return dis[p[n].x][p[n].y];
  104. }
  105. int main(){
  106. freopen("express.in","r",stdin);
  107. freopen("express.out","w",stdout);
  108. scanf("%d%d",&h,&w);
  109. scanf("%d%d%d",&a,&b,&c);
  110. scanf("%d",&n);
  111. for(int i=1;i<=n;++i)
  112. scanf("%d%d",&p[i].x,&p[i].y);
  113. BFS();
  114. printf("%lld",hp_SPFA());
  115. return 0;
  116. }

超越光速

AZZdg.png
AZeOc.png
AZ63G.png
AZIsy.png
AZlPK.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <queue>
  4. #include <vector>
  5. #include <functional>
  6. using std::min;
  7. using std::priority_queue;
  8. using std::vector;
  9. using std::greater;
  10. const int MAXN=3005;
  11. int n,m,k,rest,a,b,c;
  12. int stp[MAXN];
  13. long long T;
  14. inline int solve(){
  15. static priority_queue<int,vector<int>,greater<int> > hp;
  16. long long t,cnt,nowt;
  17. int ret=0;
  18. for(int i=1;i<m;++i){
  19. t=(long long)b*(stp[i]-1);
  20. if(t>T) break;
  21. ret+=(i!=1);
  22. cnt=min((long long)stp[i+1]-stp[i]-1,(T-t)/a);
  23. ret+=cnt;
  24. for(int now=cnt+stp[i]+1,nex=stp[i+1];now<nex;now+=cnt){
  25. nowt=t+(long long)c*(now-stp[i]);
  26. if(nowt>T) break;
  27. cnt=1+min((long long)nex-now-1,(T-nowt)/a);
  28. if(rest){
  29. --rest;
  30. hp.push(cnt);
  31. }
  32. else if(hp.top()<cnt){
  33. hp.pop();
  34. hp.push(cnt);
  35. }
  36. else break;
  37. }
  38. }
  39. if((long long)b*(stp[m]-1)<=T) ++ret;
  40. while(hp.size()){
  41. ret+=hp.top();
  42. hp.pop();
  43. }
  44. return ret;
  45. }
  46. int main(){
  47. freopen("ftl.in","r",stdin);
  48. freopen("ftl.out","w",stdout);
  49. scanf("%d%d%d",&n,&m,&k);
  50. scanf("%d%d%d",&a,&b,&c);
  51. scanf("%lld",&T);
  52. for(int i=1;i<=m;++i)
  53. scanf("%d",&stp[i]);
  54. rest=k-m;
  55. printf("%d",solve());
  56. return 0;
  57. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注