bupt summer training for 16 #8 —

https://vjudge.net/contest/175596#overview

A.设第i次出现的位置左右端点分别为Li，Ri

初始化L0 = 0，则有ans = sum{ (L[i] - L[i-1]) * (n + 1 - Ri) }

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 int last = ;

 char s[];

 long long ans;

 int main() {

     scanf("%s", s + );

     int n = strlen(s + );

     for(int i = ;i <= n;i ++) {

         if(i +  <= n && s[i] == 'b' && s[i + ] == 'e' && s[i + ] == 'a' && s[i + ] == 'r') {

             ans += 1ll * (i - last) * (n +  - i - );

             last = i;

             i += ;

         }

     }

     cout << ans;

     return ;

 }

B.AC自动机板子题，我的板子常数很大

 #include <queue>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn = ;

 struct trie {

     int next[maxn][], fail[maxn], end[maxn];

     int L, root;

     queue <int> q;

     int newnode() {

         for(int i = ;i < ;i ++)

             next[L][i] = -;

         end[L] = ;

         return L ++;

     }

     void clear() {

         L = ;

         root = newnode();

     }

     int idx(char c) {

         return c - 'a';

     }

     void insert(char *buf) {

         int len = strlen(buf), now = root, c;

         for(int i = ;i < len;i ++) {

             c = idx(buf[i]);

             if(next[now][c] == -)

                 next[now][c] = newnode();

             now = next[now][c];

         }

         end[now] ++;

     }

     void build() {

         for(int i = ;i < ;i ++) {

             if(next[root][i] == -)

                 next[root][i] = root;

             else {

                 fail[next[root][i]] = root;

                 q.push(next[root][i]);

             }

         }

         while(!q.empty()) {

             int now = q.front();

             q.pop();

             for(int i = ;i < ;i ++) {

                 if(next[now][i] == -)

                     next[now][i] = next[fail[now]][i];

                 else {

                     fail[next[now][i]] =  next[fail[now]][i];

                     q.push(next[now][i]);

                 }

             }

         }

     }

     int query(char *buf) {

         int len = strlen(buf), now = root, res = , tmp;

         for(int i = ;i < len;i ++) {

             tmp = now = next[now][idx(buf[i])];

             while(tmp != root) {

                 res += end[tmp];

                 end[tmp] = ;

                 tmp = fail[tmp];

             }

         }

         return res;

     }

 };

 trie ac;

 int Case, n;

 char buf[];

 int main() {

     scanf("%d", &Case);

     while(Case --) {

         scanf("%d", &n), ac.clear();

         while(n --) scanf("%s", buf), ac.insert(buf);

         scanf("%s", buf), ac.build();

         printf("%d\n", ac.query(buf));

     }

     return ;

 }

C.考察对KMP中next数组的理解，由一个串重复而来

所以就是max(i - next[i])

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 char s[];

 int nex[];

 int main() {

     int i, j, ans, len;

     while(~scanf("%s", s)) {

         len = strlen(s);

         nex[] = -;

         ans = ;

         for(i = ;i < len;i ++) {

             j = nex[i - ];

             while(j >=  && s[j + ] != s[i]) j = nex[j];

             if(s[j + ] == s[i]) {

                 nex[i] = j + ;

                 ans = max(ans, i - nex[i]);

             }

             else nex[i] = -, ans = max(ans, i + );

         }

         printf("%d\n", ans);

     }

     return ;

 }

D.令a[i] -= a[i + 1]，题目就变成了

求数列中出现次数不小于2次的最长重复子串

后缀数组一个典型问题，二分子串长度即可

(考场上观察了半天手里板子的接口...然后放弃了)

E.先假设要由空串刷成串2，区间DP即可

dp[i][j]代表把 i-j 这段刷成串2需要的最少次数

可能分成几段分开去刷，所以不能直接ans = dp[L][R] (s1[L] != s2[L]，s1[R] != s2[R])

利用f[i]代表 1-i 这段由串1刷成串2的最少次数

ans = f[n]

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 int n, dp[][], f[];

 char s1[], s2[];

 int main() {

     while(~scanf("%s %s", s1 + , s2 + )) {

         n = strlen(s1 + );

         memset(dp, 0x3f, sizeof dp);

         for(int d = ;d <= n;d ++)

             for(int i = ;i + d -  <= n;i ++) {

                 int j = i + d - ;

                 if(i == j) dp[i][i] = ;

                 else if(j == i + ) dp[i][j] =  - (s2[i] == s2[j]);

                 else {

                     for(int k = i;k < j;k ++)

                         dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + ][j] - (s2[i] == s2[k + ]));

                 }

             }

         for(int i = ;i <= n;i ++) {

             f[i] = dp[][i];

             if(s1[i] == s2[i]) f[i] = min(f[i - ], f[i]);

             else

                 for(int j = ;j < i;j ++)

                     f[i] = min(f[i],  f[j] + dp[j + ][i]);

         }

         printf("%d\n", f[n]);

     }

     return ;

 }

F.简单的字典树

 #include <cstdio>

 #include <cstring>

 const int maxn = ;

 struct trie {

     int ch[maxn][];

     int val[maxn];

     int siz;

     void init() {

         siz = ;

         memset(ch, , sizeof ch);

         memset(val, , sizeof val);

     }

     void insert(int x) {

         int i, u, c;

         int num[] = {};

         for(i = ;i < ;i ++)

             num[i] = x & ( << i);

         for(i = u = ;i < ;i ++) {

             c = (num[ - i] != );

             if(!ch[u][c]) ch[u][c] = siz ++;

             u = ch[u][c], val[u] ++;

         }

         val[] ++;

     }

     void de1ete(int x) {

         int i, u, c;

         int num[] = {};

         for(i = ;i < ;i ++)

             num[i] = x & ( << i);

         for(i = u = ;i < ;i ++) {

             u = ch[u][(num[ - i] != )];

             val[u] --;

         }

         val[] --;

     }

     void query(int x) {

         int i, u, c, ans = ;

         int num[] = {};

         for(i = ;i < ;i ++)

             num[i] = x & ( << i);

         for(i = u = ;i < ;i ++) {

             c = !(num[ - i] != );

             if(ch[u][c] && val[ch[u][c]]) ans |= ( << ( - i)), u = ch[u][c];

             else u = ch[u][!c];

         }

         printf("%d\n", ans);

     }

 };

 trie now;

 int n, x;

 char str[];

 int main() {

     now.init();

     now.insert();

     scanf("%d", &n);

     while(n --) {

         scanf("%s %d", str, &x);

         switch(str[]) {

             case '+':now.insert(x);break;

             case '-':now.de1ete(x);break;

             case '?':now.query(x);break;

         }

     }

     return ;

 }

K.最长回文子串，直接上马拉车

板子不长，mp[i] - 1 表示以 i 为中心的最长回文串长度

 #include <map>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 char str[], s[maxn], ma[maxn], ans[maxn];

 int mp[maxn], l, len;

 map <char, char> p;

 void manacher() {

     l = ;

     ma[l ++] = '$';

     ma[l ++] = '#';

     for(int i = ;i < len;i ++)

         ma[l ++] = s[i], ma[l ++] = '#';

     ma[l] = ;

     int mx = , id = ;

     for(int i = ;i < l;i ++) {

         mp[i] = mx > i ? min(mp[ * id - i], mx - i) : ;

         while(ma[i + mp[i]] == ma[i - mp[i]]) mp[i] ++;

         if(i + mp[i] > mx) mx = i + mp[i], id = i;

     }

 }

 int main() {

     while(~scanf("%s %s", str, s)) {

         len = strlen(s);

         manacher();

         int leng = , pos = -;

         for(int i = ;i < l;i ++)

             if(mp[i] > leng)

                 leng = mp[i], pos = i;

         leng --;

         if(leng == ) {

             puts("No solution!");

             continue;

         }

         if(pos & ) {

             printf("%d %d\n", pos /  - leng / , pos /  - leng /  + leng - );

             for(int i = pos /  - leng / , j = ;j <= leng;i ++, j ++)

                 ans[j] = s[i];

         }

         else {

             printf("%d %d\n", pos /  - leng /  - , pos /  - leng /  + leng - );

             for(int i = pos /  - leng /  - , j = ;j <= leng;i ++, j ++)

                 ans[j] = s[i];

         }

         ans[leng + ] = ;

         int dis = 'a' - str[];

         for(int i = ;i < ;i ++)

             p['a' + i] = 'a' + (i + dis + ) % ;

         for(int i = ;i <= leng;i ++)

             ans[i] = p[ans[i]];

         puts(ans + );

     }

     return ;

 }

L.变换同D题，然后就是裸的KMP了

 #include <map>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 char str[], s[maxn], ma[maxn], ans[maxn];

 int mp[maxn], l, len;

 map <char, char> p;

 void manacher() {

     l = ;

     ma[l ++] = '$';

     ma[l ++] = '#';

     for(int i = ;i < len;i ++)

         ma[l ++] = s[i], ma[l ++] = '#';

     ma[l] = ;

     int mx = , id = ;

     for(int i = ;i < l;i ++) {

         mp[i] = mx > i ? min(mp[ * id - i], mx - i) : ;

         while(ma[i + mp[i]] == ma[i - mp[i]]) mp[i] ++;

         if(i + mp[i] > mx) mx = i + mp[i], id = i;

     }

 }

 int main() {

     while(~scanf("%s %s", str, s)) {

         len = strlen(s);

         manacher();

         int leng = , pos = -;

         for(int i = ;i < l;i ++)

             if(mp[i] > leng)

                 leng = mp[i], pos = i;

         leng --;

         if(leng == ) {

             puts("No solution!");

             continue;

         }

         if(pos & ) {

             printf("%d %d\n", pos /  - leng / , pos /  - leng /  + leng - );

             for(int i = pos /  - leng / , j = ;j <= leng;i ++, j ++)

                 ans[j] = s[i];

         }

         else {

             printf("%d %d\n", pos /  - leng /  - , pos /  - leng /  + leng - );

             for(int i = pos /  - leng /  - , j = ;j <= leng;i ++, j ++)

                 ans[j] = s[i];

         }

         ans[leng + ] = ;

         int dis = 'a' - str[];

         for(int i = ;i < ;i ++)

             p['a' + i] = 'a' + (i + dis + ) % ;

         for(int i = ;i <= leng;i ++)

             ans[i] = p[ans[i]];

         puts(ans + );

     }

     return ;

 }

巴特西

bupt summer training for 16 #8 ——字符串处理

最新文章

热门文章