2019 HDOJ Multi-University Training Contest Stage 3(杭电多校)

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

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

/*************************************************************************
*File Name: d.cpp
*Author: JHSeng
*zxc98567@163.com
*Created Time: Tue 30 Jul 2019 12:35:56 PM CST
 ************************************************************************/
/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

const int maxn = 2e5 + 10;
vector<ll>v;
struct Node {
    ll w = 0;
} segt[maxn << 2];
ll a[maxn], sum[maxn];
int n, m, k;

void build(int curpos, int curl, int curr) {
    if (curl == curr) {
        segt[curpos].w = 0;
        return;
    }
    int mid = curl + curr >> 1;
    build(lson, curl, mid); build(rson, mid + 1, curr);
    segt[curpos].w = 0;
}

void update(int curpos, int pos, int curl, int curr, ll x) {
    if (curl == curr) {
        segt[curpos].w = max(segt[curpos].w, x);
        return;
    }
    int mid = curl + curr >> 1;
    if (pos <= mid) update(lson, pos, curl, mid, x);
    else update(rson, pos, mid + 1, curr, x);
    segt[curpos].w = max(segt[lson].w, segt[rson].w);
}

ll query(int curpos, int curl, int curr, int ql, int qr) {
    if (ql <= curl && curr <= qr)
        return segt[curpos].w;
    int mid = curl + curr >> 1; ll ret = 0;
    if (ql <= mid) ret = max(ret, query(lson, curl, mid, ql, qr));
    if (qr > mid) ret = max(ret, query(rson, mid + 1, curr, ql, qr));
    return ret;
}

int check(ll x) {
    build(1, 1, m);
    rep1(i, 1, n) {
        ll l = lower_bound(v.begin(), v.end(), sum[i] - x) - v.begin() + 1;
        ll r = lower_bound(v.begin(), v.end(), sum[i]) - v.begin() + 1;
        if (l > m) {
            if (sum[i] <= x) update(1, r, 1, m, 1);
            continue;
        }
        ll w = query(1, 1, m, l, m);
        if (w) update(1, r, 1, m, w + 1);
        else if (sum[i] <= x) update(1, r, 1, m, 1);
    }
    return query(1, 1, m, 1, m) >= k;
}

int main() {
    sum[0] = 0;
    int t; scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &k);
        v.clear();
        rep1(i, 1, n) {
            scanf("%lld", &a[i]);
            sum[i] = sum[i - 1] + a[i];
            v.pb(sum[i]);
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        m = v.size();
        ll l = -1e14 - 10, r = 1e14 + 10, ans = 0;
        while (l <= r) {
            ll mid = l + r >> 1;
            if (check(mid)) {
                ans = mid, r = mid - 1;
            } else l = mid + 1;
        }
        printf("%lld
", ans);
    }
    return 0;
}

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

E：

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

F：

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

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

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

ll mulmod(ll x, ll y, ll mod) {
    ll ret = 0; x %= mod; y %= mod;
    while (y) {
        if (y & 1) ret = (ret + x) % mod;
        x = (x << 1) % mod;
        y >>= 1;
    }
    return ret;
}

ll qmul(ll x, ll y, ll p) {
    if (!y) return 1;
    ll tmp = x, ret = 1;
    while (y) {
        if (y & 1) ret = mulmod(ret, tmp, p);
        tmp = mulmod(tmp, tmp, p);
        y = y >> 1;
    }
    return ret;
}

int MillerRobin(ll x) {
    if (x <= 1 || !(x & 1)) return 0;
    if (x == 2) return 1;
    rep1(i, 1, 8) {
        ll rnd = rand() % (x - 2) + 2, k = x - 1;
        while (!(k & 1)) k >>= 1;
        ll tmp = qmul(rnd, k, x);
        while (k != x - 1 && tmp != x - 1 && tmp != 1) {
            tmp = mulmod(tmp, tmp, x);
            k <<= 1;
        }
        if ((tmp == 1 && !(k & 1)) ||  (tmp == x - 1 && k == x - 1) || (tmp != x - 1 && tmp != 1)) return 0;
    }
    return 1;
}

ll qp(ll a, ll b, ll mod) {
    ll ret = 1, base = a;
    while (b) {
        if (b & 1) ret = mulmod(ret, base, mod);
        base = mulmod(base, base, mod);
        b >>= 1;
    }
    return ret;
}

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        ll n, currPrime; scanf("%lld", &n);
        for (ll i = n - 1; i >= 1; i--) {
            if (MillerRobin(i)) {
                currPrime = i; break;
            }
        }
        ll ans = n - 1;
        for (ll i = currPrime + 1; i < n; i++) ans = mulmod(ans, qp(i, n - 2, n), n);
        printf("%lld
", ans);
    }
}

G：

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

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

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

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

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

const int maxn = 2e5 + 10;
int t, n, ans[maxn];
ll m, sum[maxn * 5], cnt[maxn * 5];

struct SegmentTree {
    struct STNode {
        ll sum, cnt;
    } mem[maxn * 5];

    SegmentTree() {
        rep0(i, 0, maxn * 5) mem[i].cnt = mem[i].sum = 0;
    }

    int query(int curpos, int curl, int curr, ll val, ll tot) {
        if (mem[curpos].sum + tot <= val) return mem[curpos].cnt;
        int mid = curl + curr >> 1;
        int ret = query(lson, curl, mid, val, tot);
        if (ret == mem[lson].cnt)
            ret += query(rson, mid + 1, curr, val, tot + mem[lson].sum);
        return ret;
    }

    void insert(int curpos, int pos, int curl, int curr, ll val) {
        if (curl == curr) {
            mem[curpos].sum = val; mem[curpos].cnt = 1;
            return;
        }
        int mid = curl + curr >> 1;
        if (pos <= mid) insert(lson, pos, curl, mid, val);
        else insert(rson, pos, mid + 1, curr, val);
        mem[curpos].sum = mem[lson].sum + mem[rson].sum;
        mem[curpos].cnt = mem[lson].cnt + mem[rson].cnt;
    }

    void clear() {
        rep0(i, 0, maxn * 5) mem[i].cnt = mem[i].sum = 0;
    }
} st;

struct Node {
    ll val;
    int num, rank;
} a[maxn];

bool cmp(const Node &lhs, const Node &rhs) {
    return lhs.val < rhs.val;
}

bool cmp2(const Node &lhs, const Node &rhs) {
    return lhs.num < rhs.num;
}

int main() {
    scanf("%d", &t);
    while (t--) {
        st.clear();
        rep0(i, 0, maxn) ans[i] = 0;
        scanf("%d%lld", &n, &m);
        rep1(i, 1, n) {
            scanf("%lld", &a[i].val);
            a[i].num = i;
        }
        sort(a + 1, a + 1 + n, cmp);
        rep1(i, 1, n) a[i].rank = i;
        sort(a + 1, a + 1 + n, cmp2);
        rep1(i, 1, n) {
            int t = st.query(1, 1, n, m - a[i].val, 0);
            ans[i] = i - 1 - t;
            st.insert(1, a[i].rank, 1, n, a[i].val);
        }
        rep1(i, 1, n) printf("%d ", ans[i]);
        puts("");
    }
    return 0;
}

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

H：

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

三维莫队。

I：

网络流。

J：

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

K：

图论题。