牛客练习赛14

 1 #pragma warning(disable:4996)
 2 #include<map>
 3 #include<queue>
 4 #include<string>
 5 #include<vector>
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<iostream>
 9 #include<algorithm>
10 using namespace std;
11 typedef long long ll;
12 
13 const int maxn = 1005;
14 
15 ll n, cnt;
16 int p[20] = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 };
17 
18 void DFS(int k, ll sum, ll num, int Limit) {
19     if (k > 14) return;
20     if (num > cnt) cnt = num;
21 
22     for (int i = 1; i <= Limit; i++) {
23         if (sum <= n / p[k]) {
24             sum *= p[k];
25             DFS(k + 1, sum, num*(i + 1), i);
26         }
27     }
28     /*  可能会爆long long.
29     for (int i = 1; i <= Limit; i++) {
30         sum *= p[k];
31         if (sum < n) DFS(k + 1, sum, num*(i + 1), i);
32     }
33     */
34 }
35 
36 int main()
37 {
38     int T; cin >> T;
39     while (T--) {
40         cin >> n;
41         cnt = 1;
42         DFS(0, 1, 1, 15);
43         cout << cnt << endl;
44     }
45     return 0;
46 }

B-区间的连续段

题解：用ST表记录当前起点i跳2^j次能到达的位置，然后从大到小（当前查找的区间最长）查找就行了。

感受：看到网上题解说用ST表，蒙着脑袋就开始写了，结果。。。存错对象了。死活写不出来，orzzzzz。这里ST表存的是以当前结点为左端点，不满足区间和小于或等于k的第一个出现的右端点位置（跳一次的情况，1=2^0）！

 1 #pragma warning(disable:4996)
 2 #include<map>
 3 #include<queue>
 4 #include<string>
 5 #include<vector>
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<iostream>
 9 #include<algorithm>
10 using namespace std;
11 typedef long long ll;
12 
13 const int maxn = 1000005;
14 
15 int n, m, k;
16 int b[maxn], dp[maxn][20];
17 ll sum[maxn];
18 
19 void Inite() {
20     for (int i = 1; (1 << i) <= n; i++) {
21         for (int j = 1; j <= n; j++) dp[j][i] = dp[dp[j][i - 1]][i - 1];
22     }
23 }
24 
25 int solve(int l,int r) {
26     if (b[r] - b[l - 1] > 0) return -1;       //是减去b[l-1]!!!!!
27     int ans = 1;
28     for (int i = 19; dp[l][0] <= r; i--) {
29         if (dp[l][i] && dp[l][i] <= r) {
30             l = dp[l][i];
31             ans += (1 << i);
32         }
33     }
34     return ans;
35 }
36 
37 int main()
38 {
39     while (scanf("%d%d%d", &n, &m, &k) != EOF) {
40 
41         memset(b, 0, sizeof(b));
42         memset(dp, 0, sizeof(dp));
43         memset(sum, 0, sizeof(sum));
44 
45         for (int i = 1; i <= n; i++) {
46             int tp;
47             scanf("%d", &tp);
48             sum[i] = sum[i - 1] + tp;
49             b[i] = b[i - 1] + (tp > k);
50         }
51 
52         for (int i = 1; i <= n; i++) dp[i][0] = upper_bound(sum + 1, sum + n + 1, sum[i - 1] + k) - sum;
53         Inite();
54 
55         for (int i = 1; i <= m; i++) {
56             int l, r;
57             scanf("%d%d", &l, &r);
58             int ans = solve(l, r);
59             if (ans == -1) puts("Chtholly");
60             else printf("%d
", ans);
61         }
62     }
63     return 0;
64 }