今天究极自闭……继续锅++
题目链接：http://acm.hdu.edu.cn/contests/contest_show.php?cid=850
A：
凸包+区间dp。
B：
图论题。
C：
点分治。给一个参考博客：https://www.cnblogs.com/uid001/p/11266021.html
D：
题目令最大值最小，显然二分。
设每次答案为x，如何判定x能否满足分为k份的要求？考虑dp。
令dp[i]表示前i个数最多能分为几段，则有：
dp[i]=max(dp[j])+1; (sum[i]-sum[j]<=x)
直接dp是O(n^2)复杂度，无法接受。可以考虑用平衡树维护或者离散化后权值线段树维护，复杂度降至O(nlogn)。
E：
一点都不简单的筛式子题。
F：
由质数的密度分布，很明显可以直接暴力找出最大的比p小的质数q。相差不会很远。
如何求大数阶乘呢？用威尔逊定理即可。
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：
对于第i个位置，如何选择数字才能在满足条件情况下使得选择数字数目最少？显然是贪心找尽量大的数字。但如果暴力必TLE。
题目可以转化为前i-1个数中最多选出多少个数字和a[i]相加使得其和<=m，显然可以用线段树做。
对给定数组离散化，然后在离散化后的数组建立线段树，线段树上节点记录区间和以及区间内数字个数。
时间复杂度O(nlogn)。
H：
对序列求前缀异或和。修改操作相当于对前缀异或和的单点修改，查询相当于询问区间相同点对数。
三维莫队。
I：
网络流。
J：
差分+线段树+树链剖分。
K：
图论题。
2019 HDOJ Multi-University Training Contest Stage 3
原文：https://www.cnblogs.com/JHSeng/p/11267421.html
