思路：O(n)。每次找到bear就计算前面字母个数x和后面字母个数y，然后(x + 1) * (y + 1) - 上一个的(x + 1) * (y + 1)（用来除去重复的）
代码：
#include#include #include using namespace std; char str[5005]; __int64 i, j, x, y; __int64 ans = 0; int main() { scanf("%s", str); __int64 len = strlen(str); x = 0; for (i = 0; i < len - 3; i++) { if (str[i] == 'b' && str[i + 1] == 'e' && str[i + 2] == 'a' && str[i + 3] == 'r') { ans += (i + 1) * (len - i - 3) - (len - i - 3) * x; x = i + 1; } } printf("%I64d\n", ans); return 0; }
C. Bear and Prime Numbers time limit per test 2 seconds memory limit per test 512 megabytes input standard input output standard output
Recently, the bear started studying data structures and faced the following problem.
You are given a sequence of integers x1, x2, ..., xn of length n and m queries, each of them is characterized by two integers li, ri. Let's introduce f(p) to represent the number of such indexes k, that xk is divisible by p. The answer to the query li, ri is the sum: 
, where S(li, ri) is a set of prime numbers from segment [li, ri] (both borders are included in the segment).< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+CkhlbHAgdGhlIGJlYXIgY29wZSB3aXRoIHRoZSBwcm9ibGVtLjwvcD4KCgoKSW5wdXQKPHA+ClRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGludGVnZXIgPGVtPm48L2VtPiAoMT+h3D88ZW0+bjwvZW0+P6HcPzEwNikuCiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgPGVtPm48L2VtPiBpbnRlZ2VycyA8ZW0+eDwvZW0+MSw/PGVtPng8L2VtPjIsPy4uLiw/PGVtPng8L2VtPjxlbT5uPC9lbT4gKDI/odw/PGVtPng8L2VtPjxlbT5pPC9lbT4/odw/MTA3KS4KIFRoZSBudW1iZXJzIGFyZSBub3QgbmVjZXNzYXJpbHkgZGlzdGluY3QuPC9wPgo8cD4KVGhlIHRoaXJkIGxpbmUgY29udGFpbnMgaW50ZWdlciA8ZW0+bTwvZW0+ICgxP6HcPzxlbT5tPC9lbT4/odw/NTAwMDApLgogRWFjaCBvZiB0aGUgZm9sbG93aW5nIDxlbT5tPC9lbT4gbGluZXMgY29udGFpbnMgYSBwYWlyIG9mIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycywgPGVtPmw8L2VtPjxlbT5pPC9lbT4gYW5kIDxlbT5yPC9lbT48ZW0+aTwvZW0+KDI/odw/PGVtPmw8L2VtPjxlbT5pPC9lbT4/odw/PGVtPnI8L2VtPjxlbT5pPC9lbT4/odw/MqGkMTA5KSChqgogdGhlIG51bWJlcnMgdGhhdCBjaGFyYWN0ZXJpemUgdGhlIGN1cnJlbnQgcXVlcnkuPC9wPgoKCgpPdXRwdXQKPHA+ClByaW50IDxlbT5tPC9lbT4gaW50ZWdlcnMgoaogdGhlIGFuc3dlcnMgdG8gdGhlIHF1ZXJpZXMgb24gdGhlIG9yZGVyIHRoZSBxdWVyaWVzIGFwcGVhciBpbiB0aGUgaW5wdXQuPC9wPgoKCgpTYW1wbGUgdGVzdChzKQoKCgppbnB1dAo8cHJlIGNsYXNzPQ=="brush:java;">6 5 5 7 10 14 15 3 2 11 3 12 4 4 output
9 7 0input
7 2 3 5 7 11 4 8 2 8 10 2 123output
0 7Note
Consider the first sample. Overall, the first sample has 3 queries.
- The first query l = 2, r = 11 comes. You need to count f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9.
- The second query comes l = 3, r = 12. You need to count f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7.
- The third query comes l = 4, r = 4. As this interval has no prime numbers, then the sum equals 0.
C题：直接在筛素数的过程把和求出来即可，然后用前缀和访问每个区间的和
代码：
#include#include const int N = 10000001; int vis[N], sum[N], v[N]; void init() { int num, n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &num); vis[num]++; } } void cal() { for (int i = 2; i < N; i++) { if (v[i]) continue; for (int j = i; j < N; j += i) { if (vis[j]) sum[i] += vis[j]; v[j] = 1; } } } void solve() { for (int i = 2; i < N; i++) sum[i] += sum[i - 1]; int m, l, r; scanf("%d", &m); while (m--) { scanf("%d%d", &l, &r); if (r >= N) r = N - 1; if (l >= N) l = N; printf("%d\n", sum[r] - sum[l - 1]); } } int main() { init(); cal(); solve(); return 0; }
D. Bear and Floodlight time limit per test 4 seconds memory limit per test 256 megabytes input standard input output standard outputOne day a bear lived on the Oxy axis. He was afraid of the dark, so he couldn't move at night along the plane points that aren't lit. One day the bear wanted to have a night walk from his house at point (l, 0) to his friend's house at point (r, 0), along the segment of length(r - l). Of course, if he wants to make this walk, he needs each point of the segment to be lit. That's why the bear called his friend (and yes, in the middle of the night) asking for a very delicate favor.
The Oxy axis contains n floodlights. Floodlight i is at point (xi, yi) and can light any angle of the plane as large as ai degree with vertex at point (xi, yi). The bear asked his friend to turn the floodlights so that he (the bear) could go as far away from his house as possible during the walking along the segment. His kind friend agreed to fulfill his request. And while he is at it, the bear wonders: what is the furthest he can go away from his house Hep him and find this distance.
Consider that the plane has no obstacles and no other light sources besides the floodlights. The bear's friend cannot turn the floodlights during the bear's walk. Assume that after all the floodlights are turned in the correct direction, the bear goes for a walk and his friend goes to bed.
InputThe first line contains three space-separated integers n, l, r (1 ≤ n ≤ 20; - 105 ≤ l ≤ r ≤ 105). The i-th of the next n lines contain three space-separated integers xi, yi, ai ( - 1000 ≤ xi ≤ 1000; 1 ≤ yi ≤ 1000; 1 ≤ ai ≤ 90) ― the floodlights' description.
Note that two floodlights can be at the same point of the plane.
OutputPrint a single real number ― the answer to the problem. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.
Sample test(s) input2 3 5 3 1 45 5 1 45
output2.000000000
input1 0 1 1 1 30
output0.732050808
input1 0 1 1 1 45
output1.000000000
input1 0 2 0 2 90
output2.000000000
思路：dp+几何，在计算灯能覆盖的面积的时候，利用向量的方法去求，然后dp求最大长度。代码：
#include#include #include #include using namespace std; #define min(a,b) ((a)<(b) (a):(b)) #define max(a,b) ((a)>(b) (a):(b)) const int N = 25; const double pi = acos(-1.0); int n; double l, r, dp[1<<20]; struct D { double x, y, du; void scan() { scanf("%lf%lf%lf", &x, &y, &du); du = du * pi / 180.0; x -= l; } } d[N]; double cal(int i, double x0) { double dx = x0 - d[i].x; double dy = -d[i].y; double x1 = dx * cos(d[i].du) - dy * sin(d[i].du); double y1 = dx * sin(d[i].du) + dy * cos(d[i].du); if (fabs(y1) < 1e-12 || y1 > 0) return r; return min(r, d[i].x - d[i].y * x1 / y1); } void init() { scanf("%d%lf%lf", &n, &l, &r); r -= l; for (int i = 0; i < n; i++) d[i].scan(); } double solve() { for (int i = 0; i < (1<
E. Bear in the Field time limit per test 1 second memory limit per test 256 megabytes input standard input output standard outputOur bear's forest has a checkered field. The checkered field is an n × n table, the rows are numbered from 1 to n from top to bottom, the columns are numbered from 1 to n from left to right. Let's denote a cell of the field on the intersection of row x and column y by record(x, y). Each cell of the field contains growing raspberry, at that, the cell (x, y) of the field contains x + y raspberry bushes.
The bear came out to walk across the field. At the beginning of the walk his speed is (dx, dy). Then the bear spends exactly t seconds on the field. Each second the following takes place:
- Let's suppose that at the current moment the bear is in cell (x, y).
- First the bear eats the raspberry from all the bushes he has in the current cell. After the bear eats the raspberry from k bushes, he increases each component of his speed by k. In other words, if before eating the k bushes of raspberry his speed was (dx, dy), then after eating the berry his speed equals (dx + k, dy + k).
- Let's denote the current speed of the bear (dx, dy) (it was increased after the previous step). Then the bear moves from cell (x, y)to cell (((x + dx - 1) mod n) + 1, ((y + dy - 1) mod n) + 1).
- Then one additional raspberry bush grows in each cell of the field.
You task is to predict the bear's actions. Find the cell he ends up in if he starts from cell (sx, sy). Assume that each bush has infinitely much raspberry and the bear will never eat all of it.
InputThe first line of the input contains six space-separated integers: n, sx, sy, dx, dy, t (1 ≤ n ≤ 109; 1 ≤ sx, sy ≤ n; - 100 ≤ dx, dy ≤ 100; 0 ≤ t ≤ 1018).
OutputPrint two integers ― the coordinates of the cell the bear will end up in after t seconds.
Sample test(s) input5 1 2 0 1 2
output3 1
input1 1 1 -1 -1 2
output1 1
NoteOperation a mod b means taking the remainder after dividing a by b. Note that the result of the operation is always non-negative. For example, ( - 1) mod 3 = 2.
In the first sample before the first move the speed vector will equal (3,4) and the bear will get to cell (4,1). Before the second move the speed vector will equal (9,10) and he bear will get to cell (3,1). Don't forget that at the second move, the number of berry bushes increased by 1.
In the second sample before the first move the speed vector will equal (1,1) and the bear will get to cell (1,1). Before the second move, the speed vector will equal (4,4) and the bear will get to cell (1,1). Don't forget that at the second move, the number of berry bushes increased by 1.
E题：应该是矩阵快速幂，暂时没什么想法。都以后有想法回头补上