[关闭]
@KirinBill 2017-11-02T07:53:12.000000Z 字数 3947 阅读 626

2017.11.2 NOIP模拟赛

题解 套题

目录


思路

代码

  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. using std::max;
  31. const int MAXN=17;
  32. int n;
  33. long long ans;
  34. int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
  35. void DFS(int cur,int oi,int whk){
  36. if(cur==n+1){
  37. ans=max(ans,(long long)oi*whk);
  38. return;
  39. }
  40. DFS(cur+1,max(0,oi-b[cur]),whk+a[cur]);
  41. DFS(cur+1,oi+c[cur],max(0,whk-d[cur]));
  42. }
  43. int main(){
  44. #ifdef DEBUG
  45. setIO("a");
  46. #endif
  47. read(n);
  48. for(int i=1;i<=n;++i)
  49. read(a[i]),read(b[i]),read(c[i]),read(d[i]);
  50. DFS(1,0,0);
  51. write(ans);
  52. return 0;
  53. }

思路

代码

  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=2005;
  30. int n,m,x1,y1,x2,y2;
  31. int blk[MAXN][MAXN],all[MAXN][MAXN],le[MAXN][MAXN],up[MAXN][MAXN];
  32. char G[MAXN][MAXN];
  33. inline void prepare(){
  34. for(int i=1;i<=n;++i){
  35. for(int j=1;j<=m;++j)
  36. blk[i][j]=blk[i-1][j]+blk[i][j-1]-blk[i-1][j-1]+(G[i][j]^'0');
  37. }
  38. for(int i=1;i<=n;++i){
  39. for(int j=1;j<=m;++j){
  40. if(G[i][j]=='1' && G[i][j-1]=='1')
  41. ++all[i][j],++le[i][j];
  42. if(G[i][j]=='1' && G[i-1][j]=='1')
  43. ++all[i][j],++up[i][j];
  44. le[i][j]+=le[i-1][j];
  45. all[i][j]=all[i-1][j]+all[i][j-1]-all[i-1][j-1]+all[i][j];
  46. }
  47. }
  48. for(int i=1;i<=m;++i){
  49. for(int j=1;j<=n;++j)
  50. up[j][i]+=up[j][i-1];
  51. }
  52. }
  53. inline int solve(){
  54. int ret=blk[x2][y2]-blk[x1-1][y2]-blk[x2][y1-1]+blk[x1-1][y1-1];
  55. ret-=all[x2][y2]-all[x1-1][y2]-all[x2][y1-1]+all[x1-1][y1-1];
  56. ret+=le[x2][y1]-le[x1-1][y1];
  57. ret+=up[x1][y2]-up[x1][y1-1];
  58. return ret;
  59. }
  60. int main(){
  61. #ifdef DEBUG
  62. setIO("b");
  63. #endif
  64. int q;
  65. read(n),read(m),read(q);
  66. for(int i=1;i<=n;++i)
  67. scanf("%s",G[i]+1);
  68. prepare();
  69. for(int i=1;i<=q;++i){
  70. read(x1),read(y1),read(x2),read(y2);
  71. write(solve(),'\n');
  72. }
  73. return 0;
  74. }

思路

代码

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