时间限制: 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.
样例输入
【样例1】 PEPEP 2 【样例2】 EPE 1 【样例3】 PPPP 1 【样例4】 EPEP 2
样例输出
【样例1】 6 【样例2】 2 【样例3】 0 【样例4】 6
题目大意：
给出一个首尾相接的字符串，问有多少长度不超过 n 的包含字符 ‘E’ 的子串
方法： 尺取
代码如下：
string s; int n; int main() { cin >> s >> n; int len = s.length(); s = s + s; for(int i=0,r = 0,x = 0;i < len ;i ++){ while(r + 1 < s.size() && x == 0){ if(s[r] == 'E') x++; r ++; } ans += max(n - (r - i - 1) ,0); if(s[i] == 'E') x --; } cout << ans <<endl; return 0; }
队友的暴力代码（据说）：
ll m,n,cnt,a[maxn]; string sz; ll t=1,sum=0; int main(){ cin>>sz>>n; ll m=sz.size(); for(ll i=0;i<m;i++) sz.push_back(sz[i]); for(ll i=0;i<m*2;i++) if(sz[i]=='E') a[++cnt]=i; if(!cnt){ cout<<0; return 0; } for(ll i=0;i<m;i++){ if(a[t]<i&&t<=cnt) t++; if(t>cnt) break; sum+=max(ll(0),i+n-a[t]); } cout<<sum; }
另一个队友的代码：
const int N = 1e6 + 10; char s[N]; int f[N]; int cnt; struct node { int l, r; }q[N]; vector<int> vt; ll get(ll n, ll x, const int len) { if (x == len) { return n; } else if (x >= n) return 0; else return n - x; } int main() { cin >> s + 1; int len = strlen(s + 1); int n; cin >> n; int cntE = 0, pos = 0; for (int i = len; i >= 1; i--) { if (s[i] == 'E') { f[i] = len; cntE++; pos = i; } else if (pos != 0) { f[i] = pos - i; } } if (cntE == 0) { cout << 0 << endl; return 0; } for (int i = len; i >= 1; i--) { if (f[i]) break; f[i] = len - i + pos; } ll ans = 0; for (int i = 1; i <= len; i++) { //cout << f[i] << " "; ans += get(n, f[i], len); } //puts(""); cout << ans << endl; return 0; }
时间限制: 1 Sec 内存限制: 128 MB
题目描述
Our world has been invaded by shapeshifting aliens that kidnap people and steal their identities.You are an inspector from a task force dedicated to detect and capture them. As such, you were given special tools to detect aliens and differentiate them from real humans. Your current mission is to visit a city that is suspected of have been invaded, secretly inspect every person there so as to know whose are aliens and whose aren’t, and report it all to Headquarters. Then they can send forces to the city by surprise and capture all the aliens at once. The aliens are aware of the work of inspectors like you, and are monitoring all radio channels to detect the transmission of such reports, in order to anticipate any retaliation. Therefore, there have been several efforts to encrypt the reports, and the most recent method uses polynomials.
The city you must visit has N citizens, each identified by a distinct even integer from 2 to 2N. You want to find a polynomial P such that, for every citizen i, P(i) > 0 if citizen i is
a human, and P(i) < 0 otherwise. This polynomial will be transmitted to the Headquarters.With the aim of minimizing bandwidth, the polynomial has some additional requirements:each root and coefficient must be an integer, the coefficient of its highest degree term must be either 1 or −1, and its degree must be the lowest possible.
For each citizen, you know whether they’re a human or not. Given this information, you must find a polynomial that satisfies the described constraints.
输入
The input consists of a single line that contains a string S of length N (1 ≤ N ≤ 104),where N is the population of the city. For i = 1, 2, . . . , N, the i-th character of S is either the uppercase letter “H” or the uppercase letter “A”, indicating respectively that citizen 2i is a human or an alien.
输出
The first line must contain an integer D indicating the degree of a polynomial that satisfies the described constraints. The second line must contain D + 1 integers representing the coefficients of the polynomial, in decreasing order of the corresponding terms. It’s guaranteed that there exists at least one solution such that the absolute value of each coefficient is less than 263.
样例输入
【样例1】 HHH 【样例2】 AHHA 【样例3】 AHHHAH
样例输出
【样例1】 0 1 【样例2】 2 -1 10 -21 【样例3】 3 1 -23 159 -297
Code :
string s; ll x[maxn]; ll b[maxn]; int cnt; void _Get_x(){ int len = s.size(); for(int i=1;i < len-1;i++){ if(s[i] != s[i+1]) x[++cnt] = 2*i+1; } cout<<cnt<<endl; } void _Get_xi(){ for(int i=1;i<= cnt;i++){ for(int j=i+1;j>=1;j--){ b[j] = b[j - 1]; } for(int j=1;j<=i;j++){ b[j] += b[j+1] * x[i]; } } } int main() { b[1] = 1; cin >> s; s = 'a' + s; _Get_x(); _Get_xi(); int oper = 1; if(s[1] == 'H' && cnt % 2) oper *= -1; if(s[1] == 'A' && cnt % 2 == 0) oper *= -1; for(int i=cnt + 1;i >= 1;i --){ printf("%lld",b[i]*oper); oper *= -1; if(i != 1) printf(" "); } return 0; }
