今天究极自闭……继续锅++
题目链接：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)。
1 /************************************************************************* 2 *File Name: d.cpp 3 *Author: JHSeng 4 *zxc98567@163.com 5 *Created Time: Tue 30 Jul 2019 12:35:56 PM CST 6 ************************************************************************/ 7 /* basic header */ 8 #include <bits/stdc++.h> 9 /* define */ 10 #define ll long long 11 #define dou double 12 #define pb emplace_back 13 #define mp make_pair 14 #define sot(a,b) sort(a+1,a+1+b) 15 #define rep1(i,a,b) for(int i=a;i<=b;++i) 16 #define rep0(i,a,b) for(int i=a;i<b;++i) 17 #define eps 1e-8 18 #define int_inf 0x3f3f3f3f 19 #define ll_inf 0x7f7f7f7f7f7f7f7f 20 #define lson (curpos<<1) 21 #define rson (curpos<<1|1) 22 /* namespace */ 23 using namespace std; 24 /* header end */ 25 26 const int maxn = 2e5 + 10; 27 vector<ll>v; 28 struct Node { 29 ll w = 0; 30 } segt[maxn << 2]; 31 ll a[maxn], sum[maxn]; 32 int n, m, k; 33 34 void build(int curpos, int curl, int curr) { 35 if (curl == curr) { 36 segt[curpos].w = 0; 37 return; 38 } 39 int mid = curl + curr >> 1; 40 build(lson, curl, mid); build(rson, mid + 1, curr); 41 segt[curpos].w = 0; 42 } 43 44 void update(int curpos, int pos, int curl, int curr, ll x) { 45 if (curl == curr) { 46 segt[curpos].w = max(segt[curpos].w, x); 47 return; 48 } 49 int mid = curl + curr >> 1; 50 if (pos <= mid) update(lson, pos, curl, mid, x); 51 else update(rson, pos, mid + 1, curr, x); 52 segt[curpos].w = max(segt[lson].w, segt[rson].w); 53 } 54 55 ll query(int curpos, int curl, int curr, int ql, int qr) { 56 if (ql <= curl && curr <= qr) 57 return segt[curpos].w; 58 int mid = curl + curr >> 1; ll ret = 0; 59 if (ql <= mid) ret = max(ret, query(lson, curl, mid, ql, qr)); 60 if (qr > mid) ret = max(ret, query(rson, mid + 1, curr, ql, qr)); 61 return ret; 62 } 63 64 int check(ll x) { 65 build(1, 1, m); 66 rep1(i, 1, n) { 67 ll l = lower_bound(v.begin(), v.end(), sum[i] - x) - v.begin() + 1; 68 ll r = lower_bound(v.begin(), v.end(), sum[i]) - v.begin() + 1; 69 if (l > m) { 70 if (sum[i] <= x) update(1, r, 1, m, 1); 71 continue; 72 } 73 ll w = query(1, 1, m, l, m); 74 if (w) update(1, r, 1, m, w + 1); 75 else if (sum[i] <= x) update(1, r, 1, m, 1); 76 } 77 return query(1, 1, m, 1, m) >= k; 78 } 79 80 int main() { 81 sum[0] = 0; 82 int t; scanf("%d", &t); 83 while (t--) { 84 scanf("%d%d", &n, &k); 85 v.clear(); 86 rep1(i, 1, n) { 87 scanf("%lld", &a[i]); 88 sum[i] = sum[i - 1] + a[i]; 89 v.pb(sum[i]); 90 } 91 sort(v.begin(), v.end()); 92 v.erase(unique(v.begin(), v.end()), v.end()); 93 m = v.size(); 94 ll l = -1e14 - 10, r = 1e14 + 10, ans = 0; 95 while (l <= r) { 96 ll mid = l + r >> 1; 97 if (check(mid)) { 98 ans = mid, r = mid - 1; 99 } else l = mid + 1; 100 } 101 printf("%lld\n", ans); 102 } 103 return 0; 104 }
参考 https://www.cnblogs.com/inctry/p/11267516.html
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，显然可以用线段树做。
对给定数组离散化，然后在离散化后的数组建立线段树，线段树上节点记录区间和以及区间内数字个数。
询问时二分出区间第k大即可。时间复杂度O(nlogn)。
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 const int maxn = 2e5 + 10; 21 int t, n, ans[maxn]; 22 ll m, sum[maxn * 5], cnt[maxn * 5]; 23 24 struct SegmentTree { 25 struct STNode { 26 ll sum, cnt; 27 } mem[maxn * 5]; 28 29 SegmentTree() { 30 rep0(i, 0, maxn * 5) mem[i].cnt = mem[i].sum = 0; 31 } 32 33 int query(int curpos, int curl, int curr, ll val, ll tot) { 34 if (mem[curpos].sum + tot <= val) return mem[curpos].cnt; 35 int mid = curl + curr >> 1; 36 int ret = query(lson, curl, mid, val, tot); 37 if (ret == mem[lson].cnt) 38 ret += query(rson, mid + 1, curr, val, tot + mem[lson].sum); 39 return ret; 40 } 41 42 void insert(int curpos, int pos, int curl, int curr, ll val) { 43 if (curl == curr) { 44 mem[curpos].sum = val; mem[curpos].cnt = 1; 45 return; 46 } 47 int mid = curl + curr >> 1; 48 if (pos <= mid) insert(lson, pos, curl, mid, val); 49 else insert(rson, pos, mid + 1, curr, val); 50 mem[curpos].sum = mem[lson].sum + mem[rson].sum; 51 mem[curpos].cnt = mem[lson].cnt + mem[rson].cnt; 52 } 53 54 void clear() { 55 rep0(i, 0, maxn * 5) mem[i].cnt = mem[i].sum = 0; 56 } 57 } st; 58 59 struct Node { 60 ll val; 61 int num, rank; 62 } a[maxn]; 63 64 bool cmp(const Node &lhs, const Node &rhs) { 65 return lhs.val < rhs.val; 66 } 67 68 bool cmp2(const Node &lhs, const Node &rhs) { 69 return lhs.num < rhs.num; 70 } 71 72 int main() { 73 scanf("%d", &t); 74 while (t--) { 75 st.clear(); 76 rep0(i, 0, maxn) ans[i] = 0; 77 scanf("%d%lld", &n, &m); 78 rep1(i, 1, n) { 79 scanf("%lld", &a[i].val); 80 a[i].num = i; 81 } 82 sort(a + 1, a + 1 + n, cmp); 83 rep1(i, 1, n) a[i].rank = i; 84 sort(a + 1, a + 1 + n, cmp2); 85 rep1(i, 1, n) { 86 int t = st.query(1, 1, n, m - a[i].val, 0); 87 ans[i] = i - 1 - t; 88 st.insert(1, a[i].rank, 1, n, a[i].val); 89 } 90 rep1(i, 1, n) printf("%d ", ans[i]); 91 puts(""); 92 } 93 return 0; 94 }
参考 https://www.cnblogs.com/worcher/p/11271148.html
H：
对序列求前缀异或和。修改操作相当于对前缀异或和的单点修改，查询相当于询问区间相同点对数。
三维莫队。
I：
网络流。
J：
差分+线段树+树链剖分。
K：
图论题。