HDU 3474 Necklace

题目链接：Problem - 3474 (hdu.edu.cn)

Problem Description

You are given a necklace consists of N beads linked as a circle. Each bead is either crystal or jade.
Now, your task is:
1.  Choose an arbitrary position to cut it into a chain.
2.  Choose either direction to collect it.
3.  Collect all the beads in the chosen direction under the constraint that the number of crystal beads in your hand is not less than the jade at any time.
Calculate the number of ways to cut meeting the constraint

Input

In the first line there is an integer T, indicates the number of test cases. (T<=50)
Then T lines follow, each line describes a necklace. ‘C’ stands for a crystal bead and ‘J’ stands for a jade bead. The length of necklace is between 2 and 10^6.

Output

For each case, print “Case x: d” on a single line in which x is the number of case counted from one and d is the number of ways.

Sample Input

2

CJCJCJ

CCJJCCJJCCJJCCJJ

Sample Output

Case 1: 6

Case 2: 8

题意：任选一个切割点，然后从左或者从右去拿珠子，（C表示水晶珠， J表示玉珠）， 满足收集过程中水晶珠数量大于玉珠

思路：把水晶珠看成1，把玉珠看成-1， 有多少个切点满足从这个切点左右方向中有一个方向n个珠子的和大于等于0。利用前缀和和单调队列从前往后遍历一遍，从后往前遍历一遍。

#include
using namespace std;
#define maxn 1000005string s;
int p[maxn * 2];
int a[maxn * 2];
int sum[maxn * 2];
bool num[maxn * 2];int main(){ios::sync_with_stdio(false);int t;cin >> t;int cnt = 1;while(t--){cin >> s;memset(num, 0, sizeof(num));memset(a, 0, sizeof(a));int len = s.length();for(int i = 0; i < len; i++){if(s[i] == 'C'){a[i + 1] = 1;a[i + len + 1] = 1;}else{a[i + 1] = -1;a[i + len + 1] = -1;}}sum[0] = 0;for(int i = 1; i <= len * 2; i++){sum[i] = sum[i - 1] + a[i];}int ans = 0;int h = 1, t = 0;for(int i = 1; i < len * 2; i++){while(h <= t && sum[p[t]] > sum[i]){t--;}p[++t] = i;while(h <= t && i - p[h] >= len){h++;}if(i >= len && sum[p[h]] - sum[i - len] >= 0){num[i - len + 1] = 1;}}sum[0] = 0;for(int i = 1; i <= len * 2; i++){int k = len + len - i + 1;sum[i] = sum[i - 1] + a[k];}h = 1, t = 0;for(int i = 1; i <= len * 2; i++){while(h <= t && sum[p[t]] > sum[i]){t--;}p[++t] = i;while(h <= t && i - p[h] >= len){h++;}if(i > len && sum[p[h]] - sum[i - len] >= 0){num[len - (i - len) + 1] = 1;}}ans = 0;for(int i = 1; i <= len; i++){if(num[i]){ans++;}}cout << "Case " << cnt++ << ": " << ans << endl;}return 0;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！