牛客CSP-S提高组赛前集训营 2 – 解题报告

这次比赛必须要仔细反省,不能再出现暑假的精神状态。

A – 服务器需求

假设我们有很多服务器了,我们现在按天考虑,进行服务器的分配:假设有一个服务器编号集合\(\{id_i\}\),考虑一天天分配若干台,这样就可以保证每一台服务器的分配中不会出现同样的日期。

这样就可以分配完了,直接就有\(\sum a_i \leq |id_i| m\)。然后就是傻逼代码了。

继续阅读牛客CSP-S提高组赛前集训营 2 – 解题报告

[CEOI2011]Traffic 题解

主要思路

我们发现这其实就是一个多源覆盖问题。注意到「保证边在交点以外的任何地方不相交」,大概画个图就可以知道这样我们所覆盖的是一个区间(这有点像某年的一道跟种田有关的题目)。

如果没有这个性质,那么我们只能用 bitset 来维护所能到的点集,在缩完点上的 DAG 做需要\(\Theta(\frac{n^2}{32})\)的时间。然而,有了这个性质之后我们可以直接记录上下端点,相减得到答案。

继续阅读[CEOI2011]Traffic 题解

P4320:道路相遇题解

做法

我们发现,其实这道题就是要求询问无向图上点对之间的割点数量:可以确定割点的数量是唯一的,因为如果有更多的割点,那么不存在更少的割点使点双连通分量连通。

既然我们知道了大概的题意和要求,那么我们可以发现:如果把这些割点所在域内的非割点全部缩成一个点,然后让割点分别连接,那么根据「不存在更少的割点使点双连通分量连通」的「唯一性」,可以知道这样建出来的东西一定是一棵树。

这样就很好做了!直接树上差分+LCA即可。我们需要用 Tarjan 把这些点缩起来,通过割点进行连接,然后做一遍 DFS 之类的获取前缀和,再处理 LCA 倍增数组,我们就可以在线回答询问了。算法的复杂度为\(\Theta(n \log n + m \log n)\)。

继续阅读P4320:道路相遇题解

「杂题集」- 2019年9月25日

[POI2008]BLO

一眼可以了解到是一道割点题。对于不是割点的情况,那么被计算的点对一定包含此点本身,又因为有序,所以贡献就是\(2(n – 1)\)。如果是割点的话,就比较麻烦,分下面几个来算:

  • 此点延伸出去的点对。
  • 连通块之间的点对。
  • 本身就无法互通的点对。

第一个很好算,是\(2(n – 1)\)。第二个,在 Tarjan 枚举搜索子树的时候计算子树大小和全图补集的乘积(注意,这里会多计算一遍与点\(u\)的点对,所以我们第一个改成算\(n – 1\));第三个,算「当前整颗搜索树与图的补集大小」与「搜索树的大小」的乘积。

综合起来就是,对于点\(u\):

\[ ans_u = \sum_{k \in son(u)} (n – size(k)) \times size(k) + (n – 1) + (n – 1 – \sum_{k \in son(u)} size(k)) \times (1 + \sum_{k \in son(u)} size(k)) \]

继续阅读「杂题集」- 2019年9月25日

[Fortuna OJ]Mar 5th – Group A 解题报告

A – 旷野大计算

嗯,是我这种菜鸡不会的类型。

这个题主要的思路就是用离线莫队算法,这个算法是我本人第一次打,所以我会尝试一处一处讲清楚。首先大致分析一下,这道题的本质其实就是查询区间最大的加权众数。那么,根据题解上讲的,有一个这样的结论:

给定集合\(A,B\),则\(mode(A \cup B) \to mode(A) \cup B\)这两玩意本质一样。

所以就可以考虑进行区间增大的莫队了。首先,离散化后简单的分个块,把问答离线下来排个序搞一搞。针对每一个询问,如果可以从上个区间进行转移,就进行快速转移;否则,重新开始。

莫队算法的精髓就是:暴力的进行转移。

// A.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e6 + 2000;
int n, m, arr[MAX_N], blockId[MAX_N];
int currentId[MAX_N], bucket[MAX_N];
ll cnt[MAX_N], leftBucket[MAX_N], answer, anses[MAX_N];
struct query
{
    int l, r, id;
    bool operator<(const query &qu) const
    {
        return blockId[l] < blockId[qu.l] ||
               (blockId[l] == blockId[qu.l] && r < qu.r);
    }
} queries[MAX_N];
void update_left(int x)
{
    leftBucket[currentId[x]]++;
    answer = max(answer, (leftBucket[currentId[x]] + cnt[currentId[x]]) * 1LL * arr[x]);
}
int main()
{
    scanf("%d%d", &n, &m);
    int siz = sqrt(n * 1.0);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]), bucket[i] = arr[i], blockId[i] = (i - 1) / siz + 1;
    sort(bucket + 1, bucket + 1 + n);
    int buckTot = unique(bucket + 1, bucket + 1 + n) - bucket;
    for (int i = 1; i <= n; i++)
        currentId[i] = lower_bound(bucket + 1, bucket + 1 + buckTot, arr[i]) - bucket;
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &queries[i].l, &queries[i].r), queries[i].id = i;
    sort(queries + 1, queries + 1 + m);
    // Previous Information:
    int L = 1, R = 0, tmd;
    ll tmp = 0;
    answer = 0;
    queries[0].l = 0, blockId[0] = 0;
    for (int i = 1; i <= m; i++)
    {
        // Validiate if this interval is able to be calced by the previous one;
        if (blockId[queries[i - 1].l] != blockId[queries[i].l])
        {
            memset(cnt, 0, sizeof(cnt));
            R = tmd = blockId[queries[i].l] * siz;
            answer = tmp = 0;
        }
        L = min(tmd + 1, queries[i].r + 1);
        // Calc;
        while (L > queries[i].l)
            update_left(--L);
        while (R < queries[i].r)
        {
            R++;
            tmp = max((++cnt[currentId[R]]) * 1LL * arr[R], tmp);
            answer = max(answer, (cnt[currentId[R]] + leftBucket[currentId[R]]) * 1LL * arr[R]);
        }
        // Set the answer;
        anses[queries[i].id] = answer;
        // Set the bucket back;
        for (int j = L; j <= queries[i].r && j <= tmd; j++)
            leftBucket[currentId[j]]--;
        answer = tmp;
    }
    // Print the answer;
    for (int i = 1; i <= m; i++)
        printf("%lld\n", anses[i]);
    return 0;
}

B – 爬山

这是一道傻逼题,然后我强行搞了个拓扑序 DP 就 GG 了。现在想想非常后悔。

显然,把环全部缩成点就会形成一个 DAG (有向无环图),之后直接暴力 DP,然后再取出标记过的答案进行最大值比较即可。很傻逼的一道题。

哦,对了,记得开栈。(JZOJ 万年卡栈)

// B.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 602000;
extern int theMain(void) __asm__("theMain");
int head[MAX_N << 1], current, n, m, dfn[MAX_N], low[MAX_N], aff[MAX_N];
int tot, stk[MAX_N], cur, afftot, indeg[MAX_N << 1], tmpx, tmpy, s;
ll cnt[MAX_N << 1], dp[MAX_N << 1], answer;
bool inst[MAX_N], mark[MAX_N];
struct edge
{
    int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
    edges[current].to = dst;
    edges[current].nxt = head[src], head[src] = current++;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++tot, stk[++cur] = u, inst[u] = true;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (dfn[edges[i].to] == 0)
            tarjan(edges[i].to), low[u] = min(low[u], low[edges[i].to]);
        else if (inst[edges[i].to])
            low[u] = min(low[u], dfn[edges[i].to]);
    if (low[u] == dfn[u])
    {
        int j, nd = ++afftot;
        do
        {
            j = stk[cur], inst[j] = false;
            aff[j] = nd;
        } while (stk[cur--] != u);
    }
}
void toposort()
{
    queue<int> q;
    q.push(aff[s]), dp[aff[s]] = cnt[aff[s]];
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
        {
            dp[edges[i].to] = max(dp[edges[i].to], dp[u] + cnt[edges[i].to]);
            q.push(edges[i].to);
        }
    }
}
int theMain()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy);
    afftot = n;
    for (int i = 1; i <= n; i++)
        if (aff[i] == 0)
            tarjan(i);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &cnt[i]);
    for (int u = 1; u <= n; u++)
    {
        cnt[aff[u]] += cnt[u];
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (aff[u] != aff[edges[i].to])
                addpath(aff[u], aff[edges[i].to]), indeg[aff[edges[i].to]]++;
    }
    scanf("%d%d", &s, &tmpx);
    for (int i = 1; i <= tmpx; i++)
        scanf("%d", &tmpy), mark[aff[tmpy]] = true;
    toposort();
    for (int i = 1; i <= n; i++)
        if (mark[aff[i]])
            answer = max(answer, dp[aff[i]]);
    printf("%lld", answer);
    return 0;
}

int main()
{
    int size = 64 << 20;
    char *p = (char *)malloc(size) + size;
    __asm__ __volatile__("movq  %0, %%rsp\n"
                         "pushq $exit\n"
                         "jmp theMain\n" ::"r"(p));
    return 0;
}

C – 货仓选址 运输妹子

如题,然后秒切。

// C.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 101000;
ll n, l, w, pos[MAX_N], prefix[MAX_N], answer;
bool validiate(int l, int r)
{
    int mid = (l + r) >> 1;
    ll ans = pos[mid] * (mid - l + 1) - (prefix[mid] - prefix[l - 1]) + (prefix[r] - prefix[mid]) - pos[mid] * (r - mid);
    return ans <= w;
}
int main()
{
    scanf("%lld%lld%lld", &n, &l, &w);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &pos[i]), prefix[i] = prefix[i - 1] + pos[i];
    ll lcur = 1, rcur = 0;
    while (rcur < n && lcur <= n)
    {
        rcur++;
        while (lcur <= rcur && !validiate(lcur, rcur))
            lcur++;
        answer = max(rcur - lcur + 1, answer);
    }
    printf("%lld", answer);
    return 0;
}

[Fortuna OJ]Feb 26th – Group A 解题报告

A – 礼物

说实话,这就是我最薄弱的一项,且在比赛中一览无余的暴露出来了。

我们可以把这道题转换一下,可以发现,这个喜悦值毫无关系,第二题的题意即为

给一些物品\(a_i\),每次操作有\(p_i\)的概率可能出现,求要使所有物品出现的期望操作次数。

考虑物品的个数很少,可以进行状压,压缩到\(S\)。对于每一个出现过物品\(i\)的情况,都可以从没有出现过的状态转移过来,即S^(1<<(i - 1))。对之前的情况乘上一个\(p_i\)即为这一部分的贡献。之后,因为\(\sum_{i} {p_i} \neq 1\),所以存在操作无效的情况,也就是\((1-\sum_{i\in S} p_i)*E_S\)。之后加上操作次数\(1\),式子全貌为:

\[ E_S = (\sum_{i\in S} p_i*E_{S’}) + (1-\sum_{i\in S} p_i)*E_S + 1 \]

移项合并可得:

\[ (\sum_{i\in S} p_i)*E_S = (\sum_{i\in S} p_i*E_{S’}) + 1 \\ E_S = \frac{(\sum_{i\in S} p_i*E_{S’}) + 1}{\sum_{i\in S} p_i} \]

代码

// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 21;
int n, wi[MAX_N];
long long ans1;
double pi[MAX_N], dp[(1 << 20)];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf%d", &pi[i], &wi[i]), ans1 += wi[i];
    for (int stat = 0; stat < (1 << n); stat++)
    {
        double psum = 0, ans = 0;
        for (int i = 1; i <= n; i++)
            if (stat & (1 << (i - 1)))
            {
                int prestat = stat ^ (1 << (i - 1));
                psum += pi[i];
                ans += pi[i] * dp[prestat];
            }
        if (psum != 0)
            dp[stat] = (ans + 1) / psum;
    }
    printf("%lld\n%.3lf", ans1, dp[(1 << n) - 1]);
    return 0;
}

B – 通讯

啊,我*。

这道题很水,不讲。

代码

/// B.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 100400, MAX_M = 1e5 + 2000;
int head[MAX_N], current, dfn[MAX_N], low[MAX_N], tot, st[MAX_N], hd, aff[MAX_N];
int totp, n, m, tmpx, tmpy, tmpz, ufs[MAX_N], dist[MAX_N];
bool inst[MAX_N];
struct edge
{
    int to, nxt, weight, from;
    bool operator<(const edge &e) const { return weight > e.weight; }
} edges[MAX_M << 1];
int find(int x) { return (ufs[x] == x) ? x : ufs[x] = find(ufs[x]); }
void unite(int x, int y)
{
    if (find(x) != find(y))
        ufs[find(x)] = find(y);
}
int addpath(int u, int v, int weight)
{
    edges[current].to = v, edges[current].nxt = head[u];
    edges[current].from = u;
    edges[current].weight = weight, head[u] = current++;
    return current - 1;
}
void tarjan(int u)
{
    inst[u] = true, st[++hd] = u;
    dfn[u] = ++tot, low[u] = dfn[u];
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (dfn[edges[i].to] == 0)
            tarjan(edges[i].to), low[u] = min(low[u], low[edges[i].to]);
        else if (inst[edges[i].to])
            low[u] = min(low[u], dfn[edges[i].to]);
    if (dfn[u] == low[u])
    {
        int j;
        totp++;
        do
        {
            j = st[hd], aff[j] = totp;
            inst[j] = false;
        } while (st[hd--] != u);
    }
}
int main()
{
    while (scanf("%d%d", &n, &m) && n != 0 && m != 0)
    {
        memset(dist, 0x3f, sizeof(dist));
        memset(st, 0, sizeof(st)), memset(dfn, 0, sizeof(dfn)), hd = 0;
        for (int i = 1; i <= 2 * n; i++)
            ufs[i] = i;
        memset(head, -1, sizeof(head)), memset(aff, 0, sizeof(aff));
        totp = n, current = 0, tot = 0;
        for (int i = 1; i <= m; i++)
            scanf("%d%d%d", &tmpx, &tmpy, &tmpz), addpath(tmpx + 1, tmpy + 1, tmpz);
        tarjan(1);
        for (int i = 1; i <= n; i++)
            for (int e = head[i]; e != -1; e = edges[e].nxt)
                if (aff[i] != aff[edges[e].to])
                    dist[aff[edges[e].to]] = min(dist[aff[edges[e].to]], edges[e].weight);
        long long ans = 0;
        for (int i = n + 1; i <= totp; i++)
            if (aff[1] != i)
                ans += dist[i];
        printf("%lld\n", ans);
    }
    return 0;
}

C – 奇袭

这道题来自于 Codeforces,画风十分一至。

首先转换题意,这道题提示了每一个横纵坐标都只会存在一个点,求长为\(len\)且纵坐标最大最小值也为\(len\)的区间个数。我们可以用分治来搞一搞。首先定一个区间\([l,r]\),中点为\(mid\)。我们来探索跨这两个小区间的几种情况。

首先,我们在分类讨论之前设定几个数组:

  1. 设\(minl[i]\)为区间\([i,mid]\)的最小值,\(maxl[i]\)为区间\([i,mid]\)的最大值;

  2. 设\(minr[i]\)为区间\([mid+1,i]\)的最小值,\(maxr[i]\)为区间\([mid+1,i]\)的最大值。

那么,我们可以讨论跨越的情况:

  1. 最值都在左、右同一个区间内

  2. 最值分别在两个不同的区间

第一种情况比较好解决,在左区间的情况下:枚举一个左端点\(i\),可以根据最值之差算出右端点,进行检查并计数。

第二种稍稍麻烦一点:跨区间要考虑最值的两种分布方式,我们以最小值在左侧,最大值在右侧为例,假设有个点符合条件:

\[ maxr[j]-minl[i] = j-i \\ \text{移项得} \\ maxr[j]-j=minl[i]-i \]

可以枚举断点,把计算内容放到桶里去(注意负数,加上数域偏移),然后用两个指针判断合法区间,左端指针减一,右指针加一。

代码

// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50200, NUM_DOMAIN = 6e5;
pair<int, int> prs[MAX_N];
int arr[MAX_N], n, maxl[MAX_N], maxr[MAX_N], minl[MAX_N], minr[MAX_N], bucket[2 * NUM_DOMAIN + 1];
long long answer = 0;
void dq(int l, int r)
{
    if (l == r)
    {
        answer++;
        return;
    }
    int mid = (l + r) >> 1;
    // preprocessing;
    minl[mid] = arr[mid], maxl[mid] = arr[mid];
    maxr[mid + 1] = arr[mid + 1], minr[mid + 1] = arr[mid + 1];
    for (int i = mid - 1; i >= l; i--)
        minl[i] = min(minl[i + 1], arr[i]), maxl[i] = max(maxl[i + 1], arr[i]);
    for (int i = mid + 2; i <= r; i++)
        maxr[i] = max(maxr[i - 1], arr[i]), minr[i] = min(minr[i - 1], arr[i]);
    // make judges;
    // at the left:
    for (int i = mid; i >= l; i--)
    {
        int j = i + (maxl[i] - minl[i]);
        if (j > mid && j <= r && minr[j] > minl[i] && maxr[j] < maxl[i])
            answer++;
    }
    // at the right;
    for (int i = mid + 1; i <= r; i++)
    {
        int j = i - (maxr[i] - minr[i]);
        if (j <= mid && j >= l && minl[j] > minr[i] && maxl[j] < maxr[i])
            answer++;
    }
    // in the middle;
    // min|max:
    int ptr1 = mid + 1, ptr2 = mid;
    for (int i = mid; i >= l; i--)
    {
        while (minr[ptr2 + 1] > minl[i] && ptr2 < r)
            ptr2++, bucket[maxr[ptr2] - ptr2 + NUM_DOMAIN]++;
        while (maxl[i] > maxr[ptr1])
        {
            bucket[maxr[ptr1] - ptr1 + NUM_DOMAIN]--, ptr1++;
            if (ptr1 > r)
                break;
        }
        if (ptr1 > r)
            break;
        if (ptr1 <= ptr2)
            answer += bucket[minl[i] - i + NUM_DOMAIN];
    }
    for (int i = mid; i >= l; i--)
        bucket[minl[i] - i + NUM_DOMAIN] = 0;
    for (int i = mid + 1; i <= r; i++)
        bucket[maxr[i] - i + NUM_DOMAIN] = 0;
    // max|min:
    ptr1 = mid,
    ptr2 = mid + 1;
    for (int i = mid + 1; i <= r; i++)
    {
        while (minl[ptr2 - 1] > minr[i] && ptr2 > l)
            ptr2--, bucket[maxl[ptr2] + ptr2 + NUM_DOMAIN]++;
        while (maxr[i] > maxl[ptr1])
        {
            bucket[maxl[ptr1] + ptr1 + NUM_DOMAIN]--, ptr1--;
            if (ptr1 < l)
                break;
        }
        if (ptr1 < l)
            break;
        if (ptr2 <= ptr1)
            answer += bucket[minr[i] + i + NUM_DOMAIN];
    }
    for (int i = mid + 1; i <= r; i++)
        bucket[minr[i] + i + NUM_DOMAIN] = 0;
    for (int i = mid; i >= l; i--)
        bucket[maxl[i] + i + NUM_DOMAIN] = 0;
    dq(l, mid), dq(mid + 1, r);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &prs[i].first, &prs[i].second);
    for (int i = 1; i <= n; i++)
        arr[prs[i].first] = prs[i].second;
    dq(1, n);
    printf("%lld", answer);
    return 0;
}