[关闭]
@KirinBill 2017-10-25T10:20:17.000000Z 字数 6447 阅读 946

2017.10.25 NOIP模拟赛

题解 套题

目录


mine

qnnka.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 MAXN=1e6+5,P=1e9+7;
  31. int n;
  32. char s[MAXN];
  33. inline int idx(char c){
  34. if(isdigit(c)) return c^'0';
  35. return 3;
  36. }
  37. inline int DP(){
  38. //0,1,2,3=*,4->1
  39. static int dp[MAXN][5];
  40. if(s[1]=='?') dp[1][0]=dp[1][3]=dp[1][4]=1;
  41. else if(s[1]!='1') dp[1][idx(s[1])]=1;
  42. else dp[1][4]=1;
  43. for(int i=1;i<n;++i){
  44. if(s[i]=='?'){
  45. //3
  46. if(s[i-1]!='0'){
  47. for(int j=1;j<4;++j)
  48. dp[i+1][j]=dp[i][3];
  49. }
  50. if(s[i-1]!='*'){
  51. //0
  52. dp[i+1][0]=(dp[i+1][0]+dp[i][0])%P;
  53. dp[i+1][4]=(dp[i+1][4]+dp[i][0])%P;
  54. //4
  55. dp[i+1][3]=(dp[i+1][3]+dp[i][4])%P;
  56. }
  57. if(s[i-1]=='*' || s[i-1]=='?'){
  58. //1
  59. dp[i+1][0]=(dp[i+1][0]+dp[i][1])%P;
  60. dp[i+1][4]=(dp[i+1][4]+dp[i][1])%P;
  61. //2
  62. dp[i+1][3]=(dp[i+1][3]+dp[i][2])%P;
  63. }
  64. }
  65. else{
  66. switch(idx(s[i])){
  67. case 0: dp[i+1][0]=(dp[i+1][0]+dp[i][0])%P;
  68. dp[i+1][4]=(dp[i+1][4]+dp[i][0])%P;
  69. break;
  70. case 1: dp[i+1][0]=(dp[i+1][0]+dp[i][1])%P;
  71. dp[i+1][4]=(dp[i+1][4]+dp[i][1])%P;
  72. dp[i+1][3]=(dp[i+1][3]+dp[i][4])%P;
  73. break;
  74. case 2: dp[i+1][3]=(dp[i+1][3]+dp[i][2])%P;
  75. break;
  76. case 3: dp[i+1][1]=(dp[i+1][1]+dp[i][3])%P;
  77. dp[i+1][2]=(dp[i+1][2]+dp[i][3])%P;
  78. dp[i+1][3]=(dp[i+1][3]+dp[i][3])%P;
  79. break;
  80. }
  81. }
  82. }
  83. if(s[n]!='?') return dp[n][idx(s[n])];
  84. else{
  85. int ret=0;
  86. if(s[n-1]!='0') ret=(ret+dp[n][3])%P;
  87. if(s[n-1]!='*') ret=(ret+dp[n][0])%P;
  88. if(s[n-1]=='*' || s[n-1]=='?') ret=(ret+dp[n][1])%P;
  89. return ret;
  90. }
  91. }
  92. inline bool jud(){
  93. for(int i=1;i<=n;++i){
  94. if(s[i]=='0' && (s[i-1]=='*' || s[i+1]=='*'))
  95. return false;
  96. if(s[i]=='1' && (s[i-1]!='*' && s[i-1]!='?' && s[i+1]!='*' && s[i+1]!='?'))
  97. return false;
  98. if(s[i]=='2' && ((s[i-1]!='*' && s[i-1]!='?') || (s[i+1]!='*' && s[i+1]!='?')))
  99. return false;
  100. if(s[i]=='*' && (s[i-1]=='0' || s[i+1]=='0'))
  101. return false;
  102. }
  103. return true;
  104. }
  105. int main(){
  106. #ifdef DEBUG
  107. setIO("a");
  108. #endif
  109. scanf("%s",s+1);
  110. n=strlen(s+1);
  111. if(!jud()) putchar('0');
  112. else write(DP());
  113. return 0;
  114. }

water

qnl0D.png
qnIRd.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 <algorithm>
  31. #include <cstring>
  32. using std::queue;
  33. using std::max;
  34. const int MAXN=305;
  35. int n,m;
  36. int G[MAXN][MAXN];
  37. int dirx[]={1,0,-1,0},diry[]={0,1,0,-1};
  38. long long dis[MAXN][MAXN];
  39. bool inQ[MAXN][MAXN];
  40. struct node{
  41. int x,y;
  42. node(int x=0,int y=0):x(x),y(y){}
  43. };
  44. queue<node> que;
  45. inline void init(){
  46. for(int i=1;i<=n;++i){
  47. dis[i][1]=max(0,G[i][1]);
  48. que.push(node(i,1));
  49. inQ[i][1]=true;
  50. dis[i][m]=max(0,G[i][m]);
  51. que.push(node(i,m));
  52. inQ[i][m]=true;
  53. }
  54. for(int i=1;i<=m;++i){
  55. dis[1][i]=max(0,G[1][i]);
  56. que.push(node(1,i));
  57. inQ[1][i]=true;
  58. dis[n][i]=max(0,G[n][i]);
  59. que.push(node(n,i));
  60. inQ[n][i]=true;
  61. }
  62. }
  63. inline bool inG(node &u){
  64. return 1<u.x && u.x<n && 1<u.y && u.y<m;
  65. }
  66. inline void SPFA(){
  67. node u,v;
  68. while(que.size()){
  69. u=que.front();
  70. que.pop();
  71. inQ[u.x][u.y]=false;
  72. for(int i=0,d;i<4;++i){
  73. v.x=u.x+dirx[i],v.y=u.y+diry[i];
  74. if(!inG(v)) continue;
  75. d=max((long long)G[v.x][v.y],dis[u.x][u.y]);
  76. if(dis[v.x][v.y]>d){
  77. dis[v.x][v.y]=d;
  78. if(!inQ[v.x][v.y]){
  79. que.push(v);
  80. inQ[v.x][v.y]=true;
  81. }
  82. }
  83. }
  84. }
  85. }
  86. int main(){
  87. #ifdef DEBUG
  88. setIO("b");
  89. #endif
  90. read(n),read(m);
  91. for(int i=1;i<=n;++i){
  92. for(int j=1;j<=m;++j)
  93. read(G[i][j]);
  94. }
  95. memset(dis,0x7f,sizeof(dis));
  96. init();
  97. SPFA();
  98. for(int i=1;i<=n;++i){
  99. for(int j=1;j<=m;++j){
  100. write(dis[i][j]-G[i][j]);
  101. if(j!=m) putchar(' ');
  102. }
  103. if(i!=n) putchar('\n');
  104. }
  105. return 0;
  106. }

gcd

qneru.png
qn6W1.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 <vector>
  30. using std::vector;
  31. const int MAXN=200005,MAXX=500005;
  32. int n;
  33. long long ans;
  34. int x[MAXN],fac[MAXX],prm[MAXX];
  35. bool slc[MAXN];
  36. vector<int> div[MAXX];
  37. inline void Euler_prm(){
  38. static bool notP[MAXX];
  39. notP[1]=true;
  40. for(int i=2;i<MAXX;++i){
  41. if(!notP[i]) prm[++prm[0]]=i;
  42. for(int j=1;j<=prm[0] && i*prm[j]<MAXX;++j){
  43. notP[i*prm[j]]=true;
  44. if(i%prm[j]==0) break;
  45. }
  46. }
  47. }
  48. inline void pre_tab(){
  49. Euler_prm();
  50. for(int i=1;i<=prm[0];++i){
  51. for(int j=prm[i];j<MAXX;j+=prm[i])
  52. div[j].push_back(prm[i]);
  53. }
  54. }
  55. void cal(int x,int cur,int num,int pm,bool add){
  56. if(cur==div[x].size()){
  57. if(!add) --fac[num];
  58. ans+=pm*fac[num];
  59. if(add) ++fac[num];
  60. return;
  61. }
  62. cal(x,cur+1,num,pm,add);
  63. cal(x,cur+1,num*div[x][cur],-pm,add);
  64. }
  65. int main(){
  66. #ifdef DEBUG
  67. setIO("c");
  68. #endif
  69. pre_tab();
  70. int m;
  71. read(n),read(m);
  72. for(int i=1;i<=n;++i)
  73. read(x[i]);
  74. for(int i=1,id;i<=m;++i){
  75. read(id);
  76. if(!slc[id]){
  77. slc[id]=true;
  78. cal(x[id],0,1,1,true);
  79. }
  80. else{
  81. slc[id]=false;
  82. cal(x[id],0,1,-1,false);
  83. }
  84. write(ans,'\n');
  85. }
  86. return 0;
  87. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注