2019 HDOJ Multi-University Training Contest Stage 3

时间:2023-01-03 15:24:23

今天究极自闭……继续锅++

题目链接: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)。

2019 HDOJ Multi-University Training Contest Stage 32019 HDOJ Multi-University Training Contest Stage 3
  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 }
View Code

参考 https://www.cnblogs.com/inctry/p/11267516.html

E:

一点都不简单的筛式子题。

F:

由质数的密度分布,很明显可以直接暴力找出最大的比p小的质数q。相差不会很远。

如何求大数阶乘呢?用威尔逊定理即可。

2019 HDOJ Multi-University Training Contest Stage 32019 HDOJ Multi-University Training Contest Stage 3
 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 }
View Code

G:

对于第i个位置,如何选择数字才能在满足条件情况下使得选择数字数目最少?显然是贪心找尽量大的数字。但如果暴力必TLE。

题目可以转化为前i-1个数中最多选出多少个数字和a[i]相加使得其和<=m,显然可以用线段树做。

对给定数组离散化,然后在离散化后的数组建立线段树,线段树上节点记录区间和以及区间内数字个数。

询问时二分出区间第k大即可。时间复杂度O(nlogn)。

2019 HDOJ Multi-University Training Contest Stage 32019 HDOJ Multi-University Training Contest Stage 3
 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 }
View Code

参考 https://www.cnblogs.com/worcher/p/11271148.html

H:

对序列求前缀异或和。修改操作相当于对前缀异或和的单点修改,查询相当于询问区间相同点对数。

三维莫队。

I:

网络流。

J:

差分+线段树+树链剖分。

K:

图论题。