[关闭]
@KirinBill 2017-10-12T14:06:25.000000Z 字数 4562 阅读 1030

2017.10.12 NOIP模拟赛

题解 套题

目录


奶牛没问么,要穿越马路 1?

思路

代码

  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 <algorithm>
  30. #include <cstring>
  31. #include <climits>
  32. #include <queue>
  33. #include <vector>
  34. #include <functional>
  35. using std::min;
  36. using std::priority_queue;
  37. using std::vector;
  38. using std::greater;
  39. const int MAXN=105;
  40. int n,t;
  41. int G[MAXN][MAXN];
  42. int dirx[]={0,1,0,-1},diry[]={1,0,-1,0};
  43. struct state{
  44. int x,y,k;
  45. long long d;
  46. state(int x=0,int y=0,int k=0,long long d=0):x(x),y(y),k(k),d(d){}
  47. friend bool operator> (const state &a,const state &b){
  48. return a.d>b.d;
  49. }
  50. };
  51. inline bool inG(state &u){
  52. return 1<=u.x && u.x<=n && 1<=u.y && u.y<=n;
  53. }
  54. inline long long Dijkstra(){
  55. static long long his[MAXN][MAXN][3];
  56. static priority_queue<state,vector<state>,greater<state> > hp;
  57. memset(his,0x7f,sizeof(his));
  58. his[1][1][0]=0;
  59. hp.push(state(1,1,0,0));
  60. state u,v;
  61. long long d;
  62. while(hp.size()){
  63. u=hp.top();
  64. hp.pop();
  65. if(his[u.x][u.y][u.k]<d) continue;
  66. v.k=(u.k+1)%3;
  67. for(int i=0;i<4;++i){
  68. v.x=u.x+dirx[i],v.y=u.y+diry[i];
  69. v.d=u.d+t;
  70. if(v.k==0) v.d+=G[v.x][v.y];
  71. if(inG(v) && his[v.x][v.y][v.k]>v.d){
  72. his[v.x][v.y][v.k]=v.d;
  73. hp.push(v);
  74. }
  75. }
  76. }
  77. long long ret=INT_MAX;
  78. for(int i=0;i<3;++i)
  79. ret=min(ret,his[n][n][i]);
  80. return ret;
  81. }
  82. int main(){
  83. #ifdef DEBUG
  84. setIO("a");
  85. #endif
  86. read(n),read(t);
  87. for(int i=1;i<=n;++i){
  88. for(int j=1;j<=n;++j)
  89. read(G[i][j]);
  90. }
  91. write(Dijkstra());
  92. return 0;
  93. }

奶牛没问么,要穿越马路 2?

思路

代码

  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 <algorithm>
  30. #include <cmath>
  31. using std::max;
  32. using std::abs;
  33. const int MAXN=1005;
  34. int n;
  35. int x[MAXN],y[MAXN];
  36. bool can[MAXN][MAXN];
  37. inline int DP(){
  38. static int dp[MAXN][MAXN][2];
  39. int ret=0;
  40. for(int i=1;i<=n;++i){
  41. for(int j=1;j<=n;++j){
  42. dp[i][j][0]=max(max(dp[i-1][j][0],dp[i][j-1][0]),max(dp[i-1][j][1],dp[i][j-1][1])-1);
  43. dp[i][j][0]=max(dp[i][j][0],max(dp[i-1][j-1][0],dp[i-1][j-1][1]));
  44. if(can[i][j]) dp[i][j][1]=dp[i][j][0]+1;
  45. ret=max(ret,max(dp[i][j][0],dp[i][j][1]));
  46. }
  47. }
  48. return ret;
  49. }
  50. int main(){
  51. #ifdef DEBUG
  52. setIO("b");
  53. #endif
  54. read(n);
  55. for(int i=1;i<=n;++i)
  56. read(x[i]);
  57. for(int i=1;i<=n;++i)
  58. read(y[i]);
  59. for(int i=1;i<=n;++i){
  60. for(int j=1;j<=n;++j)
  61. can[i][j]=(abs(x[i]-y[j])<=4);
  62. }
  63. write(DP());
  64. return 0;
  65. }

奶牛没问么,要穿越马路 3?

思路

代码

  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. const int MAXN=50005;
  30. int n,m;
  31. int last[MAXN];
  32. class BIT{
  33. private:
  34. long long c[MAXN<<1];
  35. int lowbit(int x){return x&-x;}
  36. long long qry(int r){
  37. long long ret=0;
  38. for(;r;r-=lowbit(r))
  39. ret+=c[r];
  40. return ret;
  41. }
  42. public:
  43. void add(int l,int x){
  44. for(;l<=m;l+=lowbit(l))
  45. c[l]+=x;
  46. }
  47. long long qry(int l,int r){
  48. return qry(r)-qry(l-1);
  49. }
  50. }ta;
  51. int main(){
  52. #ifdef DEBUG
  53. setIO("c");
  54. #endif
  55. read(n);
  56. m=n<<1;
  57. long long ans=0;
  58. for(int i=1,a;i<=m;++i){
  59. read(a);
  60. if(last[a]){
  61. ans+=ta.qry(last[a]+1,i);
  62. ta.add(last[a],-1);
  63. }
  64. else{
  65. last[a]=i;
  66. ta.add(i,1);
  67. }
  68. }
  69. write(ans);
  70. return 0;
  71. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注