[关闭]
@KirinBill 2017-10-15T08:12:30.000000Z 字数 5386 阅读 905

2017.10.15 NOIP模拟赛

题解 套题

目录


表达式

Oel71.png
OeG2v.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. #include <iostream>
  31. using std::getline;
  32. using std::cin;
  33. const int MAXN=155;
  34. int n,len;
  35. char fml[MAXN];
  36. string s;
  37. inline bool jud_oper(char fml[]){
  38. int cnt=0;
  39. bool oper=false;
  40. for(int i=1;i<=len;++i){
  41. if(!isdigit(fml[i]) && fml[i]!='*' && fml[i]!='/' && fml[i]!='+' && fml[i]!='-' && fml[i]!='(' && fml[i]!=')') return false;
  42. else if(fml[i]=='('){
  43. if(isdigit(fml[i-1])) return false;
  44. ++cnt,oper=false;
  45. }
  46. else if(fml[i]==')'){
  47. if(fml[i-1]=='(') return false;
  48. --cnt;
  49. }
  50. else if(isdigit(fml[i])){
  51. if(fml[i-1]==')' || isdigit(fml[i-1])) return false;
  52. oper=false;
  53. }
  54. else{
  55. if(oper) return false;
  56. else if(fml[i-1]=='(') return false;
  57. oper=true;
  58. }
  59. }
  60. return cnt==0 && !oper;
  61. }
  62. int main(){
  63. setIO("expr");
  64. read(n);
  65. bool num,blk;
  66. for(int i=1;i<=n;++i){
  67. memset(fml,0,sizeof(fml));
  68. getline(cin,s);
  69. s.copy(fml+1,s.length(),0);
  70. len=0;
  71. num=blk=false;
  72. for(int j=1,lim=strlen(fml+1);j<=lim;++j){
  73. if(fml[j]!=' ' && (!num || !isdigit(fml[j])))
  74. fml[++len]=fml[j];
  75. if(!isdigit(fml[j])) num=false;
  76. else num=true;
  77. if(fml[j]!=' ') blk=true;
  78. }
  79. if(!blk) puts("No");
  80. else if(jud_oper(fml)) puts("Yes");
  81. else puts("No");
  82. }
  83. return 0;
  84. }

食物链

Oem8u.png
Oe1XD.png
Oeen0.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 <iostream>
  30. #include <map>
  31. #include <queue>
  32. #include <cstring>
  33. using std::cin;
  34. using std::map;
  35. using std::queue;
  36. const int MAXN=50005,MAXM=100005,P=1e9+7;
  37. int n;
  38. int he[MAXN],inD[MAXN],outD[MAXN],topo[MAXN];
  39. map<string,int> mp;
  40. struct line{int to,nex;}ed[MAXM];
  41. inline void addE(int u,int v){
  42. static int cnt=0;
  43. ed[++cnt]=(line){v,he[u]};
  44. he[u]=cnt;
  45. }
  46. inline void topo_sort(){
  47. static int inD[MAXN];
  48. static queue<int> que;
  49. memcpy(inD,::inD,sizeof(inD));
  50. for(int i=1;i<=n;++i){
  51. if(!inD[i]) que.push(i);
  52. }
  53. int u;
  54. while(que.size()){
  55. u=que.front();
  56. que.pop();
  57. topo[++topo[0]]=u;
  58. for(int i=he[u],v;i;i=ed[i].nex){
  59. v=ed[i].to;
  60. if(--inD[v]==0) que.push(v);
  61. }
  62. }
  63. }
  64. inline int DAG_DP(){
  65. static int dp[MAXN];
  66. int ret=0;
  67. for(int i=n,u;i;--i){
  68. u=topo[i];
  69. if(!outD[u]){
  70. dp[u]=1;
  71. continue;
  72. }
  73. for(int i=he[u],v;i;i=ed[i].nex){
  74. v=ed[i].to;
  75. dp[u]=(dp[u]+dp[v])%P;
  76. }
  77. if(!inD[u]) ret=(ret+dp[u])%P;
  78. }
  79. return ret;
  80. }
  81. int main(){
  82. setIO("chain");
  83. int m;
  84. read(m);
  85. string u,v;
  86. for(int i=1;i<=m;++i){
  87. cin>>u>>v;
  88. if(!mp.count(u)) mp[u]=++n;
  89. if(!mp.count(v)) mp[v]=++n;
  90. addE(mp[u],mp[v]);
  91. ++outD[mp[u]],++inD[mp[v]];
  92. }
  93. topo_sort();
  94. write(DAG_DP());
  95. return 0;
  96. }

路径

OeuTd.png
OecZa.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 <algorithm>
  30. using std::sort;
  31. using std::unique;
  32. const int MAXN=100005,MAXK=3005,P=1e9+7;
  33. int n,m,k;
  34. int fac[MAXN<<1],fac_inv[MAXN<<1];
  35. struct point{
  36. int x,y;
  37. friend bool operator< (const point &a,const point &b){
  38. return a.x<b.x || (a.x==b.x && a.y<b.y);
  39. }
  40. friend bool operator== (const point &a,const point &b){
  41. return a.x==b.x && a.y==b.y;
  42. }
  43. }d[MAXK];
  44. inline int pow(int x,int y){
  45. int ret=1;
  46. for(;y;y>>=1,x=(long long)x*x%P){
  47. if(y&1) ret=(long long)ret*x%P;
  48. }
  49. return ret;
  50. }
  51. inline int inv(int x){return pow(x,P-2);}
  52. inline void pre_tab(){
  53. fac[0]=1;
  54. for(int i=1,lim=n+m;i<=lim;++i)
  55. fac[i]=(long long)fac[i-1]*i%P;
  56. fac_inv[n+m]=inv(fac[n+m]);
  57. for(int i=n+m-1;i>=0;--i)
  58. fac_inv[i]=(long long)fac_inv[i+1]*(i+1)%P;
  59. }
  60. inline int C(int n,int m){
  61. return (long long)fac[n]*fac_inv[n-m]%P*fac_inv[m]%P;
  62. }
  63. inline int cal(){
  64. static int dp[MAXK];
  65. for(int i=1;i<=k;++i){
  66. dp[i]=C(d[i].x+d[i].y,d[i].x);
  67. for(int j=1;j<i;++j){
  68. if(d[j].x<=d[i].x && d[j].y<=d[i].y)
  69. dp[i]=(dp[i]-(long long)dp[j]*C(d[i].x-d[j].x+d[i].y-d[j].y,d[i].x-d[j].x)%P+P)%P;
  70. }
  71. }
  72. return dp[k];
  73. }
  74. int main(){
  75. setIO("path");
  76. read(n),read(m),read(k);
  77. pre_tab();
  78. for(int i=1;i<=k;++i)
  79. read(d[i].x),read(d[i].y);
  80. ++k;
  81. d[k].x=n,d[k].y=m;
  82. sort(d+1,d+k+1);
  83. k=unique(d+1,d+k+1)-d-1;
  84. write(cal());
  85. return 0;
  86. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注