問題 E: Eggfruit Cake
時間限制: 1 Sec 記憶體限制: 128 MB
題目描述
Today is Jaime’s birthday and, to celebrate, his friends ordered a cake decorated with eggfruits and persimmons. When the cake arrived, to their surprise, they noticed that the bakery didn’t use equal amounts of eggfruits and persimmons, but just randomly distributed the fruits over the cake’s border instead.
Jaime eats persimmons every day, so he was eager to try some eggfruit on his birthday.
However, as he doesn’t want to eat too much, his cake slice should be decorated with at most S fruits. Since Jaime doesn’t like when a fruit is cut into parts, each fruit should either be entirely in his slice or be left in the rest of the cake. The problem is, with the fruits distributed in such a chaotic order, his friends are having trouble cutting a suitable slice for him.
Jaime is about to complain that his friends are taking too long to cut his slice, but in order to do so, he needs to know how many different slices with at least one eggfruit and containing at most S fruits there are. A slice is defined just based on the set of fruits it contains. As Jaime is quite focused on details, he is able to distinguish any two fruits, even if both fruits are of the same type. Hence, two slices are considered different when they do not contain exactly the same set of fruits. The following picture shows a possible cake, as well as the six different slices with at most S = 2 fruits that can be cut from it.
輸入
The first line contains a circular string B (3 ≤ |B| ≤ 105) describing the border of the cake.Each character of B is either the uppercase letter “E” or the uppercase letter “P”, indicating
respectively that there’s an eggfruit or a persimmon at the border of the cake. The second line contains an integer S (1 ≤ S < |B|) representing the maximum number of fruits that a slice can contain.
輸出
Output a single line with an integer indicating the number of different slices with at most S fruits and at least one eggfruit.
樣例輸入 Copy
【樣例1】
PEPEP
2
【樣例2】
EPE
1
【樣例3】
PPPP
1
【樣例4】
EPEP
2
樣例輸出 Copy
【樣例1】
6
【樣例2】
2
【樣例3】
【樣例4】
6
題意：
就是給出你一個循環序列（就是首尾系相連）然後給出你一個長度尾 M M M的卡尺 卡出來長度小于等于 M M M的序列，如果卡出來的序列有“E”就算，沒有即不算。問一共有幾種算的。
思路：尺取 尺取 尺取*
就是利用尺取的思想，一直分。
具體：就是分成這兩段，把前一段放在後面看，（因為我們看 i i i的時候看以 i i i結尾的滿足條件的）然後，我們看第一個點 m m m
大前提：以m結尾，就是m一直不變
- 如果 m m m點是E那麼不用說他從長度為1到長度尾m的都滿足條件是以一共m種
- 如果 m m m點是P那麼那就得找他前一個為E的位置，因為這樣他取的區間中才有E，才能滿足條件，是以符合條件的一共有（卡尺最長度m-(目前位置m-前一個E的位置)）;這裡就用到了尺取。
上述的2.因為m的問題容易誤解 因為是推廣是以這樣了解：
假設目前點是x（x>=m）是 P P P那麼就得找他前面一個 E E E的位置，因為這樣他取的區間（從x點往前取，都往一個方向取就不會重複也不會漏）中才有 E E E才能滿足條件，是以符合條件的一共有(卡尺長度m-(目前位置x-前一個E的位置));
接而推出 m − l e n m-len m−len都是這樣的，到了（len—len+m-1）這就會出來（m-(目前位置-前一個E的位置)）。
注意**(目前位置-前一個E的位置)**如果隔的P太多會造成差為負數，是以為了避免這種就需要max（0,這個）;就像這樣的
EEPPPPPPPPPPPPPPPPPE
3
正确是12
不正确-93
加abs就是117
是以就是這個地方的錯誤
for(int i=m; i<len+m; i++) {
if(a[i]!=0) {
sum+=max(0ll,m-(i-a[i]));///會出來負數，是以要用max（0,）
}
}
還有一點就是需要注意就是如果前 m + X m+X m+X都是P的話
是以就需要加上這個判斷了
具體看看全部代碼吧。
代碼：
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#pragma GCC optimize(2)
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e6+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*
vector<ll> m1;
vector<ll> m2;
priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m;
char str[maxn];
ll a[maxn];
ll sum;
#define read read()
int main() {
cin>>str+1;
ll len=strlen(str+1);
ll l=0;
cin>>m;
for(int i=1; i<=len; i++) {
if(str[i]=='E') {
l=i;
a[i]=i;
} else {
a[i]=l;
}
}
for(int i=len+1;i<len+m;i++){
if(str[i-len]=='E') {
l=i;
a[i]=i;
} else {
a[i]=l;
}
}
for(int i=m; i<len+m; i++) {
if(a[i]!=0) {
sum+=max(0ll,m-(i-a[i]));///會出來負數，是以要用max（0,）
}
}
/**
這個地方會廢掉3個背景資料。
出現負數原因：因為a[i]記錄的是前一個是以i-a[i]這樣的話最後一個跟剛開始的差得太多就會導緻(i-a[i])就會出現負數
*/
cout<<sum<<endl;
return 0;
}