Today it's very autistic...Continue Pot+.

Title Link: http://acm.hdu.edu.cn/contests/contest_show.php?cid=850

A:

Convex hull + interval dp.

B:

Graph Thesis.

C:

Spot division.For a reference blog: https://www.cnblogs.com/uid001/p/11266021.html

D:

Title maximum minimum, obviously two points.

Set each answer to x, how can I determine if x meets the requirements of k parts?Consider dp.

Make dp[i] denote that the first I can be divided into several segments at most:

dp[i]=max(dp[j])+1; (sum[i]-sum[j]<=x)

Direct dp is O(n^2) complexity and unacceptable.Consider balanced tree maintenance or discretized weighted segment tree maintenance with reduced complexity to O(nlogn).

E:

It's not a simple sieve subtitle at all.

F:

From the density distribution of prime numbers, it is obvious that the largest prime q smaller than p can be found directly and violently.It won't be far apart.

How do I find the factorial of a large number?Use Wilson's theorem.

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 ll mulmod(ll x, ll y, ll mod) {
21     ll ret = 0; x %= mod; y %= mod;
22     while (y) {
23         if (y & 1) ret = (ret + x) % mod;
24         x = (x << 1) % mod;
25         y >>= 1;
26     }
27     return ret;
28 }
29 
30 ll qmul(ll x, ll y, ll p) {
31     if (!y) return 1;
32     ll tmp = x, ret = 1;
33     while (y) {
34         if (y & 1) ret = mulmod(ret, tmp, p);
35         tmp = mulmod(tmp, tmp, p);
36         y = y >> 1;
37     }
38     return ret;
39 }
40 
41 int MillerRobin(ll x) {
42     if (x <= 1 || !(x & 1)) return 0;
43     if (x == 2) return 1;
44     rep1(i, 1, 8) {
45         ll rnd = rand() % (x - 2) + 2, k = x - 1;
46         while (!(k & 1)) k >>= 1;
47         ll tmp = qmul(rnd, k, x);
48         while (k != x - 1 && tmp != x - 1 && tmp != 1) {
49             tmp = mulmod(tmp, tmp, x);
50             k <<= 1;
51         }
52         if ((tmp == 1 && !(k & 1)) ||  (tmp == x - 1 && k == x - 1) || (tmp != x - 1 && tmp != 1)) return 0;
53     }
54     return 1;
55 }
56 
57 ll qp(ll a, ll b, ll mod) {
58     ll ret = 1, base = a;
59     while (b) {
60         if (b & 1) ret = mulmod(ret, base, mod);
61         base = mulmod(base, base, mod);
62         b >>= 1;
63     }
64     return ret;
65 }
66 
67 int main() {
68     int t; scanf("%d", &t);
69     while (t--) {
70         ll n, currPrime; scanf("%lld", &n);
71         for (ll i = n - 1; i >= 1; i--) {
72             if (MillerRobin(i)) {
73                 currPrime = i; break;
74             }
75         }
76         ll ans = n - 1;
77         for (ll i = currPrime + 1; i < n; i++) ans = mulmod(ans, qp(i, n - 2, n), n);
78         printf("%lld\n", ans);
79     }
80 }

G:

For position I i, how do I select a number to minimize the number of numbers selected when the condition is met?Apparently greedy for the largest number possible.But TLE is necessary if violence occurs.

The title can be converted to the maximum number selected from the first i-1 numbers and added to a[i] to make the sum <=m, obviously using a segment tree.

The given array is discretized, and then a segment tree is built on the discretized array. The nodes in the segment tree record the intervals and the number of numbers in the intervals.

Time Complexity O(nlogn).

H:

Find the prefix XOR and the sequence.The modification operation is equivalent to a single point modification of the XOR prefix and the query is equivalent to the logarithm of the same points in the query interval.

3-D Moose Team.

I:

Network Stream.

J:

Differential+Segment Tree+Tree Chain Split.

K:

Graph Thesis.