codeforces - 808 (div2)

谁借莪１个温暖的怀抱￠ 2023-10-11 13:26 167阅读 0赞

A.把这个数+1,如果符合条件就符合条件了，不符合就把最高位 + 1，其余位置0

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <map>
  2. #include <set>
  3. #include <ctime>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <vector>
  8. #include <string>
  9. #include <bitset>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. #include <cstring>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <algorithm>
  16. #include <functional>
  17. using namespace std;
  18. #define For(i, x, y) for(int i=x;i<=y;i++)  
  19. #define _For(i, x, y) for(int i=x;i>=y;i--)
  20. #define Mem(f, x) memset(f,x,sizeof(f))  
  21. #define Sca(x) scanf("%d", &x)
  22. #define Sca2(x,y) scanf("%d%d",&x,&y)
  23. #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  24. #define Scl(x) scanf("%lld",&x)  
  25. #define Pri(x) printf("%d\n", x)
  26. #define Prl(x) printf("%lld\n",x)  
  27. #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
  28. #define LL long long
  29. #define ULL unsigned long long  
  30. #define mp make_pair
  31. #define PII pair<int,int>
  32. #define PIL pair<int,long long>
  33. #define PLL pair<long long,long long>
  34. #define pb push_back
  35. #define fi first
  36. #define se second 
  37. typedef vector<int> VI;
  38. int read(){
  39.      int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
  40.      if (c == '-') f = -1;c = getchar();}
  41. while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
  42. const double eps = 1e-9;
  43. const int maxn = 110;
  44. const int INF = 0x3f3f3f3f;
  45. const int mod = 1e9 + 7; 
  46. LL N,M,K;
  47. int cul(LL x){
  48.     int ans = 0;
  49.     while(x){
  50.         if(x % 10) ans++;
  51.         x /= 10;
  52.     }
  53.     return ans;
  54. }
  55. int main(){
  56.     Scl(N);
  57.     LL x = N + 1;
  58.     int num = cul(x);
  59.     if(num == 1){
  60.         Pri(1);
  61.         return 0;
  62.     }
  63.     int p = 0;
  64.     do{
  65.         p++;
  66.         x /= 10;
  67.     }while(x >= 10);
  68.     x++;
  69.     for(int i = 0 ; i < p ;i ++) x *= 10;
  70.     Prl(x - N);
  71.     return 0;
  72. }

A

B.列几下就找到规律，每个数加的次数是呈阶梯状的，例如 1 2 3 3 3 3 3 2 1,阶梯顶的值由星期数和K的最小值决定

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <map>
  2. #include <set>
  3. #include <ctime>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <vector>
  8. #include <string>
  9. #include <bitset>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. #include <cstring>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <algorithm>
  16. #include <functional>
  17. using namespace std;
  18. #define For(i, x, y) for(int i=x;i<=y;i++)  
  19. #define _For(i, x, y) for(int i=x;i>=y;i--)
  20. #define Mem(f, x) memset(f,x,sizeof(f))  
  21. #define Sca(x) scanf("%d", &x)
  22. #define Sca2(x,y) scanf("%d%d",&x,&y)
  23. #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  24. #define Scl(x) scanf("%lld",&x)  
  25. #define Pri(x) printf("%d\n", x)
  26. #define Prl(x) printf("%lld\n",x)  
  27. #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
  28. #define LL long long
  29. #define ULL unsigned long long  
  30. #define mp make_pair
  31. #define PII pair<int,int>
  32. #define PIL pair<int,long long>
  33. #define PLL pair<long long,long long>
  34. #define pb push_back
  35. #define fi first
  36. #define se second 
  37. typedef vector<int> VI;
  38. int read(){
  39.      int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
  40.      if (c == '-') f = -1;c = getchar();}
  41. while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
  42. const double eps = 1e-9;
  43. const int maxn = 2e5 + 10;
  44. const int INF = 0x3f3f3f3f;
  45. const int mod = 1e9 + 7; 
  46. int N,M,K;
  47. long double a[maxn];
  48. int main(){
  49.     Sca2(N,M);
  50.     long double sum = 0;
  51.     for(int i = 1; i <= N; i ++){
  52.         scanf("%Lf",&a[i]); 
  53.         sum += a[i] * min(min(min(i,N - i + 1),M),N - M + 1);
  54.     } 
  55.     printf("%.10Lf",sum / (N - M + 1));
  56.     return 0;
  57. }

B

C.先全部装一半，然后从大杯子往小杯子依次把剩下的水倒完，倒不完的和水不够的都是有问题的

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <map>
  2. #include <set>
  3. #include <ctime>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <vector>
  8. #include <string>
  9. #include <bitset>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. #include <cstring>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <algorithm>
  16. #include <functional>
  17. using namespace std;
  18. #define For(i, x, y) for(int i=x;i<=y;i++)  
  19. #define _For(i, x, y) for(int i=x;i>=y;i--)
  20. #define Mem(f, x) memset(f,x,sizeof(f))  
  21. #define Sca(x) scanf("%d", &x)
  22. #define Sca2(x,y) scanf("%d%d",&x,&y)
  23. #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  24. #define Scl(x) scanf("%lld",&x)  
  25. #define Pri(x) printf("%d\n", x)
  26. #define Prl(x) printf("%lld\n",x)  
  27. #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
  28. #define LL long long
  29. #define ULL unsigned long long  
  30. #define mp make_pair
  31. #define PII pair<int,int>
  32. #define PIL pair<int,long long>
  33. #define PLL pair<long long,long long>
  34. #define pb push_back
  35. #define fi first
  36. #define se second 
  37. typedef vector<int> VI;
  38. int read(){
  39.      int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
  40.      if (c == '-') f = -1;c = getchar();}
  41. while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
  42. const double eps = 1e-9;
  43. const int maxn = 110;
  44. const int INF = 0x3f3f3f3f;
  45. const int mod = 1e9 + 7; 
  46. int N,M,K;
  47. PII a[maxn];
  48. int b[maxn];
  49. int ans[maxn];
  50. int main(){
  51.     Sca2(N,M); int sum = 0;
  52.     for(int i = 1; i <= N ; i ++) Sca(a[i].fi),a[i].se = i;
  53.     sort(a + 1,a + 1 + N);
  54.     for(int i = 1; i <= N ; i ++){
  55.         b[i] = a[i].fi / 2;
  56.         if(a[i].fi & 1) b[i]++;
  57.         M -= b[i];
  58.     }
  59.     if(M < 0){
  60.         puts("-1");
  61.         return 0;
  62.     } 
  63.     for(int i = N; i >= 1 && M; i --){
  64.         int t = min(a[i].fi - b[i],M);
  65.         b[i] += t;
  66.         M -= t;
  67.     }
  68.     if(M){
  69.         puts("-1");
  70.         return 0;
  71.     }
  72.     for(int i = 1; i <= N ; i ++) ans[a[i].se] = b[i];
  73.     for(int i = 1; i <= N ; i ++){
  74.         printf("%d ",ans[i]);
  75.     }
  76.     return 0;
  77. }

C

D.求出前缀和,枚举移动的数字t，然后二分在数字左端寻找pre[i] + t = sum的i，二分在右寻找pre[i] - t = sum的i

找到一次就是YES

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <map>
  2. #include <set>
  3. #include <ctime>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <vector>
  8. #include <string>
  9. #include <bitset>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. #include <cstring>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <algorithm>
  16. #include <functional>
  17. using namespace std;
  18. #define For(i, x, y) for(int i=x;i<=y;i++)  
  19. #define _For(i, x, y) for(int i=x;i>=y;i--)
  20. #define Mem(f, x) memset(f,x,sizeof(f))  
  21. #define Sca(x) scanf("%d", &x)
  22. #define Sca2(x,y) scanf("%d%d",&x,&y)
  23. #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  24. #define Scl(x) scanf("%lld",&x)  
  25. #define Pri(x) printf("%d\n", x)
  26. #define Prl(x) printf("%lld\n",x)  
  27. #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
  28. #define LL long long
  29. #define ULL unsigned long long  
  30. #define mp make_pair
  31. #define PII pair<int,int>
  32. #define PIL pair<int,long long>
  33. #define PLL pair<long long,long long>
  34. #define pb push_back
  35. #define fi first
  36. #define se second 
  37. typedef vector<int> VI;
  38. int read(){
  39.      int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
  40.      if (c == '-') f = -1;c = getchar();}
  41. while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
  42. const double eps = 1e-9;
  43. const int maxn = 1e5 + 10;
  44. const int INF = 0x3f3f3f3f;
  45. const int mod = 1e9; 
  46. int a[maxn];
  47. LL pre[maxn];
  48. int N;
  49. LL sum;
  50. bool check(int t)
  51. {
  52.     int l = 0;
  53.     int r = t - 1;
  54.     while(l <= r){
  55.         int mid = (l + r) / 2;
  56.         if(pre[mid] + a[t] < sum) l = mid + 1;
  57.         else if(pre[mid] + a[t] > sum) r = mid - 1;
  58.         else return true;
  59.     }
  60.     l = t; r = N;
  61.     while(l <= r){
  62.         int mid = (l + r) / 2;
  63.         if(pre[mid] - a[t] < sum) l = mid + 1;
  64.         else if(pre[mid] - a[t] > sum) r = mid - 1;
  65.         else return true;
  66.     }
  67.     return false;
  69. }
  70. int main()
  71. {
  72.     Sca(N);
  73.     sum = 0;
  74.     for(int i = 1; i <= N ; i ++){
  75.         scanf("%d",&a[i]);
  76.         sum += a[i];
  77.         pre[i] = pre[i - 1] + a[i];
  78.     }
  79.     if(sum & 1){
  80.         printf("NO\n");
  81.         return 0;
  82.     }
  83.     sum /= 2; bool flag = 0;
  84.     for(int i = 1; i <= N && !flag; i ++) if(check(i)) flag = 1;
  85.     if(flag) printf("YES\n");
  86.     else printf("NO\n");
  87.     return 0;
  88. }

D

E.感觉是个dp，我的做法肯定不是正解。

把三种重量的背包分类，按照价值从大到小排序然后求出前缀和,那么一定是在1，2，3中选择a,b,c个物品，答案是pre[a] + pre[b] + pre[c]

但是枚举是个O(n²),不能直接做。

所以直接上了模拟退火,模拟a,b,c指针的移动寻找最大值,洗了洗手交了一发就AC了

注：交下面的代码一遍可能A不了，需要洗洗手多交一边

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <map>
  2. #include <set>
  3. #include <ctime>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <vector>
  8. #include <string>
  9. #include <bitset>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. #include <cstring>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <algorithm>
  16. #include <functional>
  17. using namespace std;
  18. #define For(i, x, y) for(int i=x;i<=y;i++)  
  19. #define _For(i, x, y) for(int i=x;i>=y;i--)
  20. #define Mem(f, x) memset(f,x,sizeof(f))  
  21. #define Sca(x) scanf("%d", &x)
  22. #define Sca2(x,y) scanf("%d%d",&x,&y)
  23. #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  24. #define Scl(x) scanf("%lld",&x)  
  25. #define Pri(x) printf("%d\n", x)
  26. #define Prl(x) printf("%lld\n",x)  
  27. #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
  28. #define LL long long
  29. #define ULL unsigned long long  
  30. #define mp make_pair
  31. #define PII pair<int,int>
  32. #define PIL pair<int,long long>
  33. #define PLL pair<long long,long long>
  34. #define pb push_back
  35. #define fi first
  36. #define se second 
  37. typedef vector<int> VI;
  38. int read(){
  39.      int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
  40.      if (c == '-') f = -1;c = getchar();}
  41. while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
  42. const double eps = 1e-9;
  43. const int maxn = 1e5 + 10;
  44. const int maxm = 3e5 + 10;
  45. const int INF = 0x3f3f3f3f;
  46. const int mod = 1e9 + 7; 
  47. int N,M,K;
  48. LL pre[4][maxn],cnt[4];
  49. vector<LL>Q[4];
  50. bool cmp(LL a,LL b){
  51.     return a > b;
  52. }
  53. LL ans,ansa,ansb,ansc;
  54. LL cul(LL a,LL b,LL c){
  55.     if(a + 2 * b + 3 * c > M) return 0;
  56.     return pre[1][a] + pre[2][b] + pre[3][c];
  57. }
  58. const double delta = 0.999;
  59. void s_a(){
  60.     double t = 30000;
  61.     int a = ansa,b = ansb,c = ansc;
  62.     while(t > 1e-14){
  63.         int atmp = a + (rand() * 2 - RAND_MAX) * t; atmp = ((atmp % (Q[1].size() + 1)) + Q[1].size() + 1) % (Q[1].size() + 1);
  64.         int btmp = b + (rand() * 2 - RAND_MAX) * t; btmp = ((btmp % (Q[2].size() + 1)) + Q[2].size() + 1) % (Q[2].size() + 1);
  65.         int ctmp = c + (rand() * 2 - RAND_MAX) * t; ctmp = ((ctmp % (Q[3].size() + 1)) + Q[3].size() + 1) % (Q[3].size() + 1);
  66.         LL new_ans = cul(atmp,btmp,ctmp);
  67.         LL DE = new_ans - ans;
  68.         if(DE > 0){
  69.             ansa = a = atmp; ansb = b = btmp; ansc = c = ctmp;
  70.             ans = new_ans;
  71.         }else if(-exp(-DE / t) * RAND_MAX > rand()){
  72.             a = atmp; b = btmp; c = ctmp;
  73.         }
  74.         t = t * delta;
  75.     }
  76. }
  77. void SA(){
  78.     s_a();s_a();
  79.     s_a();s_a();
  80.     s_a();s_a();
  81. }
  82. int main(){
  83.     Sca2(N,M); srand(time(NULL));
  84.     for(int i = 1; i <= N ; i ++){
  85.         LL w = read(),t = read();
  86.         Q[w].pb(t);
  87.     }
  88.     for(int i = 1; i <= 3; i ++) sort(Q[i].begin(),Q[i].end(),cmp);
  89.     for(int i = 1; i <= 3; i ++){
  90.         for(int j = 0 ; j < Q[i].size(); j ++){
  91.             pre[i][j + 1] = pre[i][j] + Q[i][j];
  92.         }
  93.     }
  94.     ansa = ansb = ansc = 0;
  95.     SA(); //ACACAC
  96.     Prl(cul(ansa,ansb,ansc));
  97.     return 0;
  98. }

E

F.题目的导向很明显,二分level或者将level排序依次更新答案。

先考虑2分level,如果将题目的意思换一种方式说:对于ci和为质数的两张卡片，必须至少放弃其中一张。

再配上N这个100的范围,思路就呼之欲出了

这是一个类似最大权闭合子图的网络流,建图的方法稍微和最大权闭合子图有些出入

拆所有点i为i和i + N

将所有点S向i连边，容量为p，将所有点i + N向T连边,然后对于每一对和为质数的点i,j,从i - j + N连边，容量为INF

最后整张图最大流的一半就是不得不放弃的最小权值，将总权值减去他和K比较即可check成功

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <map>
  2. #include <set>
  3. #include <ctime>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <vector>
  8. #include <string>
  9. #include <bitset>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. #include <cstring>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <algorithm>
  16. #include <functional>
  17. using namespace std;
  18. #define For(i, x, y) for(int i=x;i<=y;i++)  
  19. #define _For(i, x, y) for(int i=x;i>=y;i--)
  20. #define Mem(f, x) memset(f,x,sizeof(f))  
  21. #define Sca(x) scanf("%d", &x)
  22. #define Sca2(x,y) scanf("%d%d",&x,&y)
  23. #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  24. #define Scl(x) scanf("%lld",&x)  
  25. #define Pri(x) printf("%d\n", x)
  26. #define Prl(x) printf("%lld\n",x)  
  27. #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
  28. #define LL long long
  29. #define ULL unsigned long long  
  30. #define mp make_pair
  31. #define PII pair<int,int>
  32. #define PIL pair<int,long long>
  33. #define PLL pair<long long,long long>
  34. #define pb push_back
  35. #define fi first
  36. #define se second 
  37. typedef vector<int> VI;
  38. int read(){
  39.      int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
  40.      if (c == '-') f = -1;c = getchar();}
  41. while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
  42. const double eps = 1e-9;
  43. const int maxn = 1010;
  44. const int maxm = 2e5 + 10;
  45. const int INF = 0x3f3f3f3f;
  46. const int mod = 1e9 + 7; 
  47. int N,M,K;
  48. bool isprime[maxm];
  49. void init(){
  50.     for(int i = 2; i < maxm; i ++) isprime[i] = 1;
  51.     for(int i = 2; i < maxm;  i ++){
  52.         if(!isprime[i]) continue;
  53.         for(int j = i + i; j < maxm; j += i){
  54.             isprime[j] = 0;
  55.         }
  56.     }
  57. }
  58. struct Dinic{
  59.     struct Edge{
  60.         int from,to,next,cap,flow;
  61.         Edge(){}
  62.         Edge(int from,int to,int next,int cap,int flow):from(from),to(to),next(next),cap(cap),flow(flow){}
  63.     }edge[maxm * 2];  
  64.     int n,s,t,head[maxn],tot;
  65.     int dep[maxn],cur[maxn];
  66.     void init(int n,int s,int t){
  67.         this->n = n; this->s = s; this->t = t; 
  68.         tot = 0;
  69.         for(int i = 0 ; i <= n ; i ++) head[i] = -1;
  70.     }
  71.     inline void add(int s,int t,int w){
  72.         //cout << s << ' ' << t << " " << w << endl;
  73.         edge[tot] = Edge(s,t,head[s],w,0);
  74.         head[s] = tot++;
  75.         edge[tot] = Edge(t,s,head[t],0,0);
  76.         head[t] = tot++;
  77.     }
  78.     inline bool BFS(){
  79.         for(int i = 0 ; i <= n ; i ++) dep[i] = -1;
  80.         dep[s] = 1;
  81.         queue<int>Q; Q.push(s);
  82.         while(!Q.empty()){
  83.             int u = Q.front(); Q.pop();
  84.             for(int i = head[u]; ~i ; i = edge[i].next){
  85.                 int v = edge[i].to;
  86.                 if(~dep[v] || edge[i].flow >= edge[i].cap) continue;
  87.                 dep[v] = dep[u] + 1;
  88.                 Q.push(v);
  89.             }
  90.          }
  91.          return ~dep[t];
  92.     }
  93.     inline int DFS(const int& u,int a){
  94.         if(u == t || !a) return a;
  95.         int flow = 0;
  96.         for(int &i = cur[u]; ~i ; i = edge[i].next){
  97.             int v = edge[i].to;
  98.             if(dep[v] != dep[u] + 1) continue;
  99.             int f = DFS(v,min(a,edge[i].cap - edge[i].flow));
  100.             if(!f) continue;
  101.             edge[i ^ 1].flow -= f;
  102.             edge[i].flow += f; 
  103.             a -= f;
  104.             flow += f;
  105.         }
  106.         return flow;
  107.     }
  108.     inline int maxflow(){
  109.         return maxflow(s,t);
  110.     }
  111.     inline int maxflow(int s,int t){
  112.         int flow = 0;
  113.         while(BFS()){
  114.             for(int i = 0; i <= n ; i ++) cur[i] = head[i];
  115.             flow += DFS(s,INF);
  116.         }
  117.         return flow;
  118.     }
  119. }g;
  120. struct Node{
  121.     int p,c,l;
  122. }node[110];
  123. bool cmp(Node a,Node b){
  124.     return a.l < b.l;
  125. }
  126. bool check(int m){
  127.     int S = N + N + 1,T = N + N + 2;
  128.     g.init(T,S,T); LL sum = 0;
  129. //    if(m == 4){
  130. //        puts("bug");
  131. //    }
  132.     for(int i = 1; i <= N ; i ++){
  133.         if(node[i].l > m) break;
  134.         sum += node[i].p * 2;
  135.         g.add(S,i,node[i].p); g.add(i + N,T,node[i].p);
  136.         for(int j = 1; j <= N ; j ++){
  137.             if(i == j) continue;
  138.             if(node[j].l > m) break;
  139.             if(isprime[node[i].c + node[j].c]) g.add(i,j + N,INF);
  140.         }
  141.     }
  142.     int x = g.maxflow(); 
  143.     return (sum - x) >= M * 2;
  144. }
  145. int solve(){
  146.     int l = 1,r = N;
  147.     int ans = -1;
  148.     while(l <= r){
  149.         int m = l + r >> 1;
  150.         if(check(m)){
  151.             ans = m;
  152.             r = m - 1;
  153.         }else{
  154.             l = m + 1;
  155.         }
  156.     }
  157.     return ans;
  158. }
  159. int main(){
  160.     Sca2(N,M); init();
  161.     for(int i = 1; i <= N ; i ++) Sca3(node[i].p,node[i].c,node[i].l);
  162.     sort(node + 1,node + 1 + N,cmp);
  163.     Pri(solve());
  164.     return 0;
  165. }

F

G.

dp[i]表示到这个[1 - i]范围内的字符串A最多可以匹配多少B,dp2[i]表示最后一个字符串是以i结尾的情况下,[1-i]范围内的字符串最多可以匹配多少B

那么先通过跳next指针的方式更新dp[2],然后dp[i] = max(dp[i - 1],dp2[i])

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <map>
  2. #include <set>
  3. #include <ctime>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <vector>
  8. #include <string>
  9. #include <bitset>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. #include <cstring>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <algorithm>
  16. #include <functional>
  17. using namespace std;
  18. #define For(i, x, y) for(int i=x;i<=y;i++)  
  19. #define _For(i, x, y) for(int i=x;i>=y;i--)
  20. #define Mem(f, x) memset(f,x,sizeof(f))  
  21. #define Sca(x) scanf("%d", &x)
  22. #define Sca2(x,y) scanf("%d%d",&x,&y)
  23. #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  24. #define Scl(x) scanf("%lld",&x)  
  25. #define Pri(x) printf("%d\n", x)
  26. #define Prl(x) printf("%lld\n",x)  
  27. #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
  28. #define LL long long
  29. #define ULL unsigned long long  
  30. #define mp make_pair
  31. #define PII pair<int,int>
  32. #define PIL pair<int,long long>
  33. #define PLL pair<long long,long long>
  34. #define pb push_back
  35. #define fi first
  36. #define se second 
  37. typedef vector<int> VI;
  38. int read(){
  39.      int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
  40.      if (c == '-') f = -1;c = getchar();}
  41. while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
  42. const double eps = 1e-9;
  43. const int maxn = 1e5 + 10;
  44. const int INF = 0x3f3f3f3f;
  45. const int mod = 1e9 + 7;
  46. char A[maxn],B[maxn]; 
  47. LL dp[maxn],dp2[maxn];
  48. int nxt[maxn];
  49. int N,M,K;
  50. void kmp_pre(char x[],int m,int nxt[]){
  51.     int j = 0;
  52.     nxt[1] = 0;
  53.     for(int i = 2; i <= m ; i ++){
  54.         while(j && x[i] != x[j + 1]) j = nxt[j];
  55.         if(x[j + 1] == x[i]) j ++;
  56.         nxt[i] = j;
  57.     }
  58. }
  59. int main(){
  60.     scanf("%s%s",A + 1,B + 1);
  61.     N = strlen(A + 1),M = strlen(B + 1);
  62.     kmp_pre(B,M,nxt);
  63. //    for(int i = 1; i <= M ; i ++){
  64. //        cout << nxt[i] << " ";
  65. //    }
  66. //    cout << endl;
  67.     for(int i = M; i <= N ; i ++){
  68.         bool flag = 1;
  69.         for(int j = 1; j <= M; j ++){
  70.             if(B[j] != A[i - M + j] && A[i - M + j] != '?') flag = 0;
  71.         }
  72.         if(!flag){
  73.             dp[i] = dp[i - 1];
  74.             continue;
  75.         } 
  76.         dp2[i] = max(dp2[i],dp[i - M] + 1);
  77.         for(int j = nxt[M]; j ; j = nxt[j]){
  78.             dp2[i] = max(dp2[i],dp2[i - M + j] + 1);
  79.         }
  80.         dp[i] = max(dp[i - 1],dp2[i]);
  81.     }
  82.     Prl(dp[N]);
  83.     return 0;
  84. }

G

转载于:https://www.cnblogs.com/Hugh-Locke/p/11214567.html

发表评论

表情：
评论列表 （有 0 条评论，167人围观）

还没有评论，来说两句吧...

相关阅读

    相关 codeforces-round375-div2

    题目链接：[codeforces round 375 div2][] A题： 读一遍题目就知道是超级水的题目，，就是给你三个坐标，求三个坐标汇集到一个点所走的路程

    亦凉亦凉/ 0 赞/ 289 阅读