Gym 100712L Alternating Strings II（单调队列）

题目链接 Alternating Strings II

题意是指给出一个长度为n的01串，和一个整数k，要求将这个01串划分为很多子串（切很多刀），使得每个子串长度不超过k，且每个字串不是01交替出现的串（例如01， 10， 101， 010， 101010这些都是01交替出现的串），求最少需要切多少次

令F[i]代表前i个数所需要切的最少的刀数(从1开始计数)，那么有

F[i] = min{F[j] | |j + 1, i| <= k 且 [j, i]这个子串不是01交替出现的串} + 1

这时O(n^2)的思路，足以解决上一个问题Gym 100712D了（n=1000），但是这个题数据n<=100000，所以首先寻求NlogN的方法。

我们记录以i结尾的且是交替串的最长长度为pre，可以看到在计算f[i]时，有以下几种情况：

1.s[i] == s[i - 1] 这时候没有以i结尾交替出现的串，重置pre=1，f[i] = min{f[i - k], ..., f[i - 1]} + 1 (初始化f[0] = -1，注意f下标是从1开始计数的)

2.s[i] != s[i - 1] 这时候pre++,由于最后一个与前一个形成交替串，所以需要比较pre与k的关系:

1) 若pre >= k 或 pre == i，着说明连续出现的交替串长度>k，或者前i个全是01串，那么此时f[i]只能由f[i - 1]转移（相当于在i-1与i之间切一刀）

2)否则的话pre + 1这个串（[i - pre - 1, i])一定不是交替串,那么此时[i - k, i - pre - 1]这个区间的所有点都可以转移到i【1】（最后pre+1个不是交替串，那么最后pre+1+x个一定也不是），所以有f[i] = min{f[i - k], ..., f[i - pre - 1]} + 1，所以可以使用线段树查询区间最小值，复杂度NlogN
【1】可以由i转移到j表示在i的后面切一刀，[i + 1, j]这个区间是合法串（非交替串）

下面是代码：

 //#pragma comment(linker, "/STACK:1677721600")

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, (L + R)>>1

 #define rson k<<1|1,  ((L + R)>>1) + 1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FIN freopen("in.txt", "r", stdin)

 #define FOUT freopen("out.txt", "w", stdout)

 #define rep(i, a, b) for(int i = a; i <= b; i ++)

 #define dec(i, a, b) for(int i = a; i >= b; i --)

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 typedef long long LL;

 const int MAXN =  + ;

 const int MAXM = ;

 const double eps = 1e-;

 LL MOD = ;

 const double PI = 4.0 * atan(1.0);

 int t, n, k;

 char s[MAXN];

 struct SegTree {

     int mi[MAXN << ];

     void update(int k, int L, int R, int p, int v) {

         if(L == R) { mi[k] = v; return ; }

         if((L + R) /  >= p) update(lson, p, v);

         else update(rson, p, v);

         mi[k] = min(mi[k << ], mi[k <<  | ]);

     }

     int query(int k, int L, int R, int l, int r) {

         if(l == ) return -;

         if(R < l || r < L) return INF;

         if(l <= L && R <= r) return mi[k];

         return min(query(lson, l, r), query(rson, l, r));

     }

 }st;

 int main()

 {

 //    FIN;

     while(~scanf("%d", &t)) while(t--) {

         scanf("%d %d%*c %s", &n, &k, s);

         mem0(st.mi);

         st.update(, , n, , );

         int pre = , val;

         rep (i, , n) {

             if(s[i - ] == s[i - ]) {

                 pre = ;

                 val = st.query(, , n, max(i - k, ), i - );

             }

             else {

                 pre ++;

                 if(pre >= k || pre == i) val = st.query(, , n, i - , i - );

                 else val = st.query(, , n, max(i - k, ), i -  - pre);

             }

             st.update(, , n, i, val + );

         }

         cout << st.query(, , n, n, n) << endl;

     }

     return ;

 }

同时，这道题还有O(N)的方法（想了太久才搞出= =！）

在上面的过程中讲到，如果i可以由j转移得到，那么一定可以由j - 1转移得到(前提是|j - 1, i| <= k), 那么如果此时f[j - 1] > f[j]，那么在计算f[i]时吗，只要j存在，就不可能由j - 1转移（这时显而易见的），所以我们使用队列维护一个f值不降的序列，并记录下标。

在计算f[i]时，首先将队首与i的区间长度>k的点删掉，然后再根据上面讨论的几种情况判断是根据队首转移还是队尾转移，然后将f[i]入队，再根据f[i]的值维护队列的单调性。

 //#pragma comment(linker, "/STACK:1677721600")

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, (L + R)>>1

 #define rson k<<1|1,  ((L + R)>>1) + 1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FIN freopen("in.txt", "r", stdin)

 #define FOUT freopen("out.txt", "w", stdout)

 #define rep(i, a, b) for(int i = a; i <= b; i ++)

 #define dec(i, a, b) for(int i = a; i >= b; i --)

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 typedef long long LL;

 const int MAXN =  + ;

 const int MAXM = ;

 const double eps = 1e-;

 LL MOD = ;

 const int R = ;

 const int S = ;

 const int P = ;

 struct Node {

     int id, x;

     Node(int _id = , int _x = ) {

         id = _id; x = _x;

     }

 }q[MAXN];

 int st = , ed = ;

 int T, n, k;

 char s[MAXN];

 void pop_fr(int i) {

     while(st < ed && i - q[st].id > k) st++;

 }

 void pop_ed(int id, int val) {

     while(st < ed && q[ed - ].x > val) ed --;

     q[ed++] = Node(id, val);

 }

 int main()

 {

 //    FIN;

 //    FOUT;

     int cas = ;

     while(~scanf("%d", &T)) while(T--) {

         scanf("%d %d%*c %s", &n, &k, s);

         int len = strlen(s), pre = ;

         int f = ;

         st = ed = ;

         q[ed ++] = Node(, -);

         q[ed ++] = Node(, );

         rep (i, , len - ) {

             pop_fr(i + );

             if(s[i] == s[i - ]) {

                 f = q[st].x + ;

                 pre = ;

             }

             else {

                 pre ++;

                 f = (pre >= (i +  - q[st].id) || pre == i + ) ? (q[ed - ].x + ) : (q[st].x + );

             }

             pop_ed(i + , f);

             //printf("%d: %d\n", i + 1, f);

         }

         cout << f << endl;

     }

     return ;

 }

巴特西

Gym 100712L Alternating Strings II（单调队列）

最新文章

热门文章