[关闭]
@KirinBill 2017-10-09T15:32:59.000000Z 字数 4378 阅读 1220

2017.10.9 NOIP模拟赛

题解 套题

赛后AK,心态爆炸。

目录


String Master

AFBFw.png
AFxjg.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::max;
  31. const int MAXN=305;
  32. int n,k;
  33. char s[MAXN],t[MAXN];
  34. inline int solve(int sl,int tl){
  35. int rest=k,ret=0;
  36. for(int i=sl,j=tl;i<=n && j<=n;++i,++j){
  37. if(s[i]!=t[j]){
  38. if(!rest) break;
  39. else --rest;
  40. }
  41. ++ret;
  42. }
  43. return ret;
  44. }
  45. int main(){
  46. #ifdef DEBUG
  47. setIO("a");
  48. #endif
  49. read(n),read(k);
  50. scanf("%s%s",s+1,t+1);
  51. int ans=0;
  52. for(int i=1;i<=n;++i){
  53. for(int j=1;j<=n;++j){
  54. ans=max(ans,solve(i,j));
  55. }
  56. }
  57. write(ans);
  58. return 0;
  59. }

Tourist Attractions

AFPJR.png
AFXAW.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 <bitset>
  30. using std::bitset;
  31. const int MAXN=1505;
  32. int deg[MAXN];
  33. char s[MAXN];
  34. bitset<MAXN> G[MAXN],tmp;
  35. int main(){
  36. #ifdef DEBUG
  37. setIO("b");
  38. #endif
  39. int n;
  40. read(n);
  41. for(int i=1;i<=n;++i){
  42. scanf("%s",s+1);
  43. for(int j=1;j<=n;++j)
  44. G[i][j]=s[j]^'0';
  45. }
  46. for(int i=1;i<=n;++i)
  47. deg[i]=G[i].count();
  48. long long ans=0;
  49. for(int i=1;i<=n;++i){
  50. for(int j=1;j<=n;++j){
  51. if(i==j || !G[i][j]) continue;
  52. ans+=(long long)(deg[i]-1)*(deg[j]-1);
  53. tmp=G[i]&G[j];
  54. ans-=tmp.count();
  55. }
  56. }
  57. write(ans);
  58. return 0;
  59. }

Walk

AFTKX.png
AFR48.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 <vector>
  31. #include <functional>
  32. #include <cstring>
  33. using std::priority_queue;
  34. using std::vector;
  35. using std::greater;
  36. const int MAXN=200005,MAXM=300005,MAXW=1<<20,MAXV=MAXN+MAXW,MAXE=MAXM+(MAXN<<1);
  37. int n,m;
  38. int he[MAXV],dis[MAXV];
  39. struct line{int to,nex,w;}ed[MAXE];
  40. struct node{
  41. int id;
  42. node(int id=0):id(id){}
  43. friend bool operator> (const node &a,const node &b){
  44. return dis[a.id]>dis[b.id];
  45. }
  46. };
  47. inline void addE(int u,int v,int w){
  48. static int cnt=0;
  49. ed[++cnt]=(line){v,he[u],w};
  50. he[u]=cnt;
  51. }
  52. inline void hp_SPFA(){
  53. static bool inQ[MAXV];
  54. static priority_queue<node,vector<node>,greater<node> > pq;
  55. memset(dis,0x7f,sizeof(dis));
  56. dis[1]=0;
  57. pq.push(node(1));
  58. inQ[1]=true;
  59. int u;
  60. while(pq.size()){
  61. u=pq.top().id;
  62. pq.pop();
  63. inQ[u]=false;
  64. for(int i=he[u],v,d;i;i=ed[i].nex){
  65. v=ed[i].to,d=dis[u]+ed[i].w;
  66. if(dis[v]>d){
  67. dis[v]=d;
  68. if(!inQ[v]){
  69. pq.push(node(v));
  70. inQ[v]=true;
  71. }
  72. }
  73. }
  74. if(u>n){
  75. for(int j=0,v,w=u-n,d=dis[u];(1<<j)<w;++j){
  76. if(w&1<<j){
  77. v=(w^1<<j)+n;
  78. if(dis[v]>d){
  79. dis[v]=d;
  80. if(!inQ[v]){
  81. pq.push(node(v));
  82. inQ[v]=true;
  83. }
  84. }
  85. }
  86. }
  87. }
  88. }
  89. }
  90. int main(){
  91. #ifdef DEBUG
  92. setIO("c");
  93. #endif
  94. read(n),read(m);
  95. for(int i=1,w,v;i<=n;++i){
  96. read(w),v=n+w;
  97. addE(i,v,1),addE(v,i,0);
  98. }
  99. for(int i=1,u,v;i<=m;++i){
  100. read(u),read(v);
  101. addE(u,v,1);
  102. }
  103. hp_SPFA();
  104. for(int i=1;i<=n;++i){
  105. if(dis[i]>n) dis[i]=-1;
  106. write(dis[i],'\n');
  107. }
  108. return 0;
  109. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注