XATU第八届算法大赛题解

博主： zclll
发布时间：2021 年 11 月 27 日
1846 次浏览
暂无评论
3664字数
分类：算法

# 第八届算法大赛题解（普通组）

## 7-1 选举

让我们解决第一个候选人的问题，为了赢得选举，他需要比其他候选人至少多获得$1$张选票。因此，第一个候选人至少需要获得 $max(b,c)+1$ 票。 如果 $a$ 已经大于这个值，那么你不需要添加任何投票，否则你需要添加 $max(b,c)+1−a$ 票。 所以第一个候选的答案是 $max(0,max(b,c)+1−a)$。

类似地，第二个候选人的答案是 $max(0,max(a,c)+1−b)$，第三个候选人的答案是 $max(0,max(a,b)+1−c)$。

```cpp
#include <bits/stdc++.h>
using namespace std;

int solveSingle(int best, int other1, int other2) {
    return max(0, max(other1, other2) + 1 - best);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int a, b, c;
        cin >> a >> b >> c;
        cout << solveSingle(a, b, c) << ' ' << solveSingle(b, a, c) << ' ' << solveSingle(c, a, b) << '\n';
    }
    return 0;
}
```

## 7-2 DaLaBengBa

### 题目大意

给定$n$的一个全排列，对于每个位置$i$，给定$d_i$代表任意时刻位于该位置的数字可以与满足距离为$j$的位置数字进行交换。求该排列是否可以通过任意次交换变为一个顺序排列$(1，2，........,n)$

### 解法

图论题。

给定一个图$G=(V,E)$，其中$V=\{1,2,3...n\},G=\{\}$，对于每个可交换的关系$(i,j)$，在节点$i$和$j$之间建边，由于是交换操作，所以这条边是**无向边**。接下来跑一个传递闭包即可得知**哪些位置的点是可以相互交换的**。由于数据范围小，传递闭包用$O(N^3)$的Floyd-Warshall算法或者$O(N\alpha(N))$的并查集都可以。

之后考虑每个数字$x$，若$x$所在位置$i$与$x$在一个闭包里，那么这个数字可以回到它在顺序排列中的应有位置，如果所有数字都可以，那么输出YES，否则输出NO。

```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N = 10000;

int f[N], to[N], d[N];

int find(int x) {
    if (f[x] != x) f[x] = find(f[x]);
    return f[x];
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) f[x] = y;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        f[i] = i;
        scanf("%d", &to[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &d[i]);
        if (i - d[i] > 0) merge(i, i - d[i]);//这里用并查集做传递闭包
        if (i + d[i] <= n) merge(i, i + d[i]);//注意不要越界
    }
    for (int i = 1; i <= n; i++) {
        if (find(i) == find(to[i])) continue;
        puts("NO");
        return 0;
    }
    puts("YES");
    return 0;
}
```

## 7-3 Dividing candy

由于侄子清空了他所选择的盒子$i$，并希望使其他$n-1$个盒子相等，那么这意味着至少所有数组$a$的总和应该被$(n-1)$整除，而且其他每个盒子里的块数应该至少是$⌈\frac{sum}{n-1}⌉$（上限函数）。

另一方面，由于侄子选择了$i$，那么他可以选择一个不是最大值的盒子，而且由于他使唯一的盒子$i$为空，那么其他每个盒子中的最终数量应该至少是最大值。

总的来说，所产生的$n-1$个其他盒子中的每个块的数量应该至少是$k=max(⌈\frac{sum}{n-1}⌉,max)$，我们需要在初始数组中添加至少$(n-1)⋅k-sum$元素。

```cpp
#include <bits/stdc++.h>
using namespace std;

int a[100000 + 5];
int n;
long long sum, ans;

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    if (n == 2) {
        cout << "0\n";
        return;
    }
    int mx = *max_element(a, a + n);
    sum = 0;
    for (int i = 0; i < n; i++) {
        sum += (mx - a[i]);
    }
    sum -= mx;	//本身被分了
    if (sum == 0) ans = 0;         //0
    else if (sum > 0) ans = sum;   //需要补齐的糖果数
    else {
        sum = abs(sum);           //可以给其他的n-1堆分配
        sum %= (n - 1);            //取余
        if (sum)              	  	 //未分配完
            ans = n - 1 - sum;     //sum余数可以分配，ans为sum分配完剩下的个数
        else
            ans = 0;
    }
    cout << ans << endl;
}

int main() {
    int TC;
    cin >> TC;
    while (TC--)
        solve();
    return 0;
}
```

## 7-4 List

### 考点

莫队

### 解法 1

```cpp
#include <iostream>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cctype>

using namespace std;

# define Rep(i, a, b) for(int i=a;i<=b;i++)
# define _Rep(i, a, b) for(int i=a;i>=b;i--)
# define RepG(i, u) for(int i=head[u];~i;i=e[i].next)

const int N = 1e5 + 5;

typedef long long ll;
typedef double db;

# define chkmax(a, b) a=max(a,b)
# define chkmin(a, b) a=min(a,b)
# define PII pair<int,int>
# define mkp make_pair
# define pb push_back

template<typename T>
void read(T &x) {
    x = 0;
    int f = 1;
    char c = getchar();

for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = -1;

for (; isdigit(c); c = getchar())
        x = (x << 1) + (x << 3) + c - '0';

x *= f;
}

int n, m, B;
int a[N];
int stk[N], top;
int st[N][20], lg[N];
ll fl[N], fr[N];
int pre[N], suf[N];
int pos[N];
ll out[N], ans;

struct node {
    int l, r, id;
} Q[N];

bool cmp(node a, node b) {
    if (pos[a.l] != pos[b.l])
        return pos[a.l] < pos[b.l];
    else if (pos[a.l] & 1)
        return a.r < b.r;
    else
        return a.r > b.r;
}

int gg(int x, int y) {
    if (x < 0 || y < 0)
        assert(false);
    return a[x] < a[y] ? x : y;
}

int getmin(int l, int r) {
    int k = lg[r - l + 1];
    return gg(st[l][k], st[r - (1 << k) + 1][k]);
}

ll calcl(int l, int r) {
    int p = getmin(l - 1, r);

if (a[l - 1] < a[p])
        return 1ll * a[l - 1] * (r - l + 2);

return 1ll * a[p] * (r - p + 1) + fr[l - 1] - fr[p];
}

ll calcr(int l, int r) {
    int p = getmin(l, r + 1);
    return 1ll * a[p] * (p - l + 1) + fl[r + 1] - fl[p];
}

int main() {
    read(n), read(m);
    Rep(i, 1, n)read(a[i]);
    B = sqrt(n);
    Rep(i, 1, n)pos[i] = (i - 1) / B + 1;
    Rep(i, 1, m)read(Q[i].l), read(Q[i].r), Q[i].id = i;
    sort(Q + 1, Q + m + 1, cmp);

Rep(i, 1, n) {
        while (top && a[stk[top]] > a[i])
            top--;

pre[i] = top ? stk[top] : 0;
        stk[++top] = i;
    }
    top = 0;
    _Rep(i, n, 1) {
        while (top && a[stk[top]] > a[i])
            top--;

suf[i] = top ? stk[top] : n + 1;
        stk[++top] = i;
    }
    Rep(i, 1, n)fl[i] = fl[pre[i]] + 1ll * a[i] * (i - pre[i]);
    _Rep(i, n, 1)fr[i] = fr[suf[i]] + 1ll * a[i] * (suf[i] - i);
    lg[1] = 0;
    Rep(i, 2, n)lg[i] = lg[i >> 1] + 1;
    _Rep(i, n, 1) {
        st[i][0] = i;
        Rep(j, 1, 19) {
            if (i + (1 << (j - 1)) > n)
                break;

st[i][j] = gg(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }

for (int i = 1, l = 1, r = 0; i <= m; i++) {
        while (Q[i].r > r) ans += calcr(l, r), r++;
        while (Q[i].l < l) ans += calcl(l, r), l--;
        while (Q[i].r < r) ans -= calcr(l, r - 1), r--;
        while (Q[i].l > l) ans -= calcl(l + 1, r), l++;

out[Q[i].id] = ans;
    }

Rep(i, 1, m)printf("%lld\n", out[i]);
    return 0;
}
```

### 解法 2

```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e6 + 10;
inline ll read() {
    ll x = 0, w = 1;
    char ch = getchar();

while (ch < '0' || ch > '9') {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }

while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }

return x * w;
}
ll n, m, a[N], f[24][N], st[N], tp, pr[N], sf[N], fl[N], fr[N], gl[N], gr[N], ql, qr;

ll rmq(ll l, ll r) {
    ll k = log2(r - l + 1), x = f[k][l], y = f[k][r - (1 << k) + 1];
    return (a[x] < a[y] ? x : y);
}

#undef ll
int main() {
#define ll long long
    n = read(), m = read();

for (ll i = 1; i <= n; i++)
        a[i] = read(), f[0][i] = i;

for (ll i = 1; i <= 20; i++)
        for (ll j = 1; j <= n; j++) {
            ll x = f[i - 1][j], y = f[i - 1][j + (1 << (i - 1))];
            f[i][j] = (a[x] < a[y] ? x : y);
        }

for (ll i = 1; i <= n; i++) {
        while (tp && a[st[tp]] >= a[i])
            tp--;

pr[i] = st[tp], st[++tp] = i;
    }

tp = 0;

for (ll i = n; i; i--) {
        while (tp && a[st[tp]] >= a[i])
            tp--;

sf[i] = st[tp], st[++tp] = i;
    }

for (ll i = 1; i <= n; i++)
        fr[i] = fr[pr[i]] + a[i] * (i - pr[i]), gr[i] = gr[i - 1] + fr[i];

for (ll i = n; i; i--)
        fl[i] = fl[sf[i]] + a[i] * (sf[i] - i), gl[i] = gl[i + 1] + fl[i];

while (m--) {
        ql = read();
        qr = read();
        ll res = rmq(ql, qr);
        ll mi = (res - ql + 1) * (qr - res + 1) * a[res] + gr[qr] - gr[res] - fr[res] * (qr - res) + gl[ql] - gl[res] - fl[res] * (res - ql);
        cout << mi << '\n';
    }

return 0;
}
```

## 7-5 An easy Concrete Mathematics question

以$(1101000)_2$为例，我们将它分成三个部分处理：

$$
(0000001)_2——(1000000)_2

$$
(1000001)_2——(1100000)_2

$$
(1100001)_2——(1101000)_2

我们倒序去考虑三个区间（这样处理的原因是通过$lowbit$可以快速找到当前需要处理的区间并迭代），将这三个区间的$Sum(i)$分别求和。

那么每个区间怎么求和呢？我们称一个区间的终点为$end$（那么起点对应的就为$end-lowbit(end)+1$，显然），考虑将其分为$lowbit(end)$所包含的低位和$lowbit(end)$以上的高位两部分位分别考察他们的贡献。

> 例如，$(1101000)_2$就拆分为$(1100000)_2$和$(0001000)_2$

首先有引理1：当前区间的数字个数$=lowbit(end)$

其次有引理2：高位数字有$popcount(end)-1$个$1$

观察到由于高位部分不变，那么高位的贡献显然为$(popcount(end)-1)*lowbit(end)$

接下来考察低位部分，那么低位从形式上看就是$000……001$到$100……000$这样形式的一个数列求$Sum(i)$之和。这样考虑没有头绪，接下来考虑每一个二进制位，于是有引理3：

从$0$到$2^i$（$i$为任意正整数）的所有数的二进制表示，除最高位以外**每一个二进制位上都是均匀分布的**，也就是说，每一位在整个低位区间中，都有一半的情况是$1$。

利用这个引理，我们就知道低位表示中$1$的个数为$lowbit(end)*低位位数/2+1$。其中这个$1$是低位的左端那一个$1$。至于低位位数可以用$popcount$求。

这样，时间复杂度是$O(logN)$，在题目所给范围甚至所有整型范围内，甚至可以认为是$O(1)$的。

```cpp
#include <iostream>
#include <algorithm>

using namespace std;

#define MOD 1000000007
typedef long long ll;

ll x;

ll lowbit(ll x) {	return x & (-x);	}

int main() {
    cin >> x;
    ll ans = 0;
    int hi = __builtin_popcount(x);//一共有多少个1
    while (x) {
        ll n = lowbit(x);
        int low = __builtin_ctz(x);//最低位的1是右数第几个
        ans += n * (--hi) + ((n * low) >> 1) + 1;
        ans %= MOD;
        x -= n;
    }
    cout << ans << endl;
    return 0;
}
```

## 7-6 Auto-qieti Machine

由于要求最值的范围，显然应当采用二分答案加检验的方式处理。

时间复杂度：$2 * log1e18 * l$。最坏情况，也就是 $l$ 取到 $1e5$ 时，复杂度大概为 $2 * 60 * 1e5$ 也就是 $1e7$

```cpp
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
ll x[maxn];
ll l, k;

ll check(ll ans) {
    ll now = 0, tmp = 0;

for (ll i = 1; i <= l; i++) {
        now += x[i];
        now = max(0ll, now);

if (now >= ans) {
            tmp++;
            now = 0;
        }
    }
    return tmp;
}

int main() {
    scanf("%lld%lld", &l, &k);

for (ll i = 1; i <= l; i++) {
        scanf("%lld", &x[i]);
    }

ll L = 1, R = 1e18;

while (L <= R) {
        ll mid = (L + R) >> 1;

if (check(mid) >= k + 1)
            L = mid + 1; //R找最大的分的段多于要求值的
        else
            R = mid - 1;
    }

if (L > 1e18) {
        printf("-1 ");
        return 0;
    }

if (check(L) == k)
        printf("%lld ", L);
    else {
        printf("-1 ");
        return 0;
    }

L = 1;
    R = 1e18;

while (L <= R) {
        ll mid = (L + R) >> 1;

if (check(mid) >= k)
            L = mid + 1; //R找最大的分的段大于等于要求值的
        else
            R = mid - 1;
    }

printf("%lld", R);
} //n越小分的段越多
```

## 7-7 Crash?Rub?Drop it!

这道题本质是一个三维凸包的板子题

题目中最后要求输出体积已经是疯狂暗示了（x

题目大意是给出$n$组点 每一个点都由 $x,y,z$ 三个坐标来描述。然后考虑这些点组成的物体（点连线，线连面，面连体）是否存在碰撞（也就是空间体积是否存在重合的情况）。思路也十分简单：

对于每一个点，求出其最小三维凸包的体积。然后和所有点组成三维图凸包的体积进行比较就可以了。

而三维凸包计算时会对每一个点进行微扰，所以题中也说明了，不存在边界上的点。也就是两个物体不存在仅共用一个点，一条线，或一个面的情况。

```cpp
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<vector>
using namespace std;

typedef long long ll;
const ll MAXN = 2048;
const double eps = 1e-8;

struct Point3 {
    //三维的点
    double x, y, z;

Point3() {}

Point3(double x, double y, double z) : x(x), y(y), z(z) {}

Point3 operator+(Point3 B) { return Point3(x + B.x, y + B.y, z + B.z); }

Point3 operator-(Point3 B) { return Point3(x - B.x, y - B.y, z - B.z); }

Point3 operator*(double k) { return Point3(x * k, y * k, z * k); }

Point3 operator/(double k) { return Point3(x / k, y / k, z / k); }
};

typedef Point3 Vector3;

double Dot(Vector3 A, Vector3 B) { return A.x * B.x + A.y * B.y + A.z * B.z; }

Point3 Cross(Vector3 A, Vector3 B) {
    return Point3(A.y * B.z - A.z * B.y, A.z * B.x - A.x * B.z, A.x * B.y - A.y * B.x);
}

double Len(Vector3 A) { return sqrt(Dot(A, A)); }

//向量的长度
double Area2(Point3 A, Point3 B, Point3 C) { return Len(Cross(B - A, C - A)); }

//四面体有向体积*6
double volume4(Point3 A, Point3 B, Point3 C, Point3 D) { return Dot(Cross(B - A, C - A), D - A); }

struct CH3D {
    struct face {
        ll a, b, c;
        //凸包的一个面上的3个点的编号
        bool ok;
        //该面是否在最终的凸包上
    };
    ll n;
    //初始顶点数
    Point3 P[MAXN];
    //初始顶点
    ll num;
    //凸包表面的三角形个数
    face F[8 * MAXN];
    //凸包表面的三角形
    ll g[MAXN][MAXN];// g[x][y]表示点x到点y属于哪个面
    //点在面的同向
    double dblcmp(Point3 &p, face &f) {
        Point3 m = P[f.b] - P[f.a];
        Point3 n = P[f.c] - P[f.a];
        Point3 t = p - P[f.a];
        return Dot(Cross(m, n), t);
    }

void deal(ll p, ll a, ll b) {
        ll f = g[a][b];
        //搜索与该边相邻的另一个平面
        face add;
        if (F[f].ok) {
            if (dblcmp(P[p], F[f]) > eps) {
                //如果如果从p点能看到该面f,则继续深度搜索f的三条边
                //以更新新的凸面（维护）
                F[f].ok = false;
                deal(p, F[f].b, F[f].a);
                deal(p, F[f].c, F[f].b);
                deal(p, F[f].a, F[f].c);
            } else {
                //如果如果从p点不能看到f面，则p点和a、b点组成一个三角形
                add.a = b;
                add.b = a;
                add.c = p;
                add.ok = true;
                g[p][b] = g[a][p] = g[b][a] = num;
                F[num++] = add;
            }
        }
    }

void dfs(ll p, ll now) {
        //维护凸包，如果点p在凸包外则更新凸包
        F[now].ok = false;
        deal(p, F[now].b, F[now].a);
        deal(p, F[now].c, F[now].b);
        deal(p, F[now].a, F[now].c);
    }

bool same(ll s, ll t) {
        //判断两个面是否为同一面
        Point3 &a = P[F[s].a];
        Point3 &b = P[F[s].b];
        Point3 &c = P[F[s].c];
        return fabs(volume4(a, b, c, P[F[t].a])) < eps &&
               fabs(volume4(a, b, c, P[F[t].b])) < eps &&
               fabs(volume4(a, b, c, P[F[t].c])) < eps;
    }

void create() {
        //构建三维凸包
        ll i, j, tmp;
        face add;
        num = 0;
        if (n < 4)return;
        bool flag = true;
        for (i = 1; i < n; i++) {
            //使前两个点不共点
            if (Len(P[0] - P[i]) > eps) {
                swap(P[1], P[i]);
                flag = false;
                break;
            }
        }
        if (flag)return;
        flag = true;
        for (i = 2; i < n; i++) {
            //使前三个点不共线
            if (Len(Cross(P[0] - P[1], P[1] - P[i])) > eps) {
                swap(P[2], P[i]);
                flag = false;
                break;
            }
        }
        if (flag)return;
        flag = true;
        for (ll i = 3; i < n; i++) {
            //使前四个点不共面
            if (fabs(Dot(Cross(P[0] - P[1], P[1] - P[2]), P[0] - P[i])) > eps) {
                swap(P[3], P[i]);
                flag = false;
                break;
            }
        }
        if (flag)return;
        for (i = 0; i < 4; i++) {
            //构建初始四面体
            //四个点为：
            //p[0],p[1],p[2],p[3]
            add.a = (i + 1) % 4;
            add.b = (i + 2) % 4;
            add.c = (i + 3) % 4;
            add.ok = true;
            if (dblcmp(P[i], add) > 0)swap(add.b, add.c);
            //保证逆时针，即法向量朝外，这样新点才可看到
            g[add.a][add.b] = g[add.b][add.c] = g[add.c][add.a] = num;
            //逆向的有向边保存
            F[num++] = add;
        }
        for (i = 4; i < n; i++) {
            //构建&更新凸包
            for (j = 0; j < num; j++) {
                //判断点是否在当前三维凸包内，i表示当前点，j表示当前面
                if (F[j].ok && dblcmp(P[i], F[j]) > eps) {
                    //对当前凸包面进行判断，看点能否看到这个面
                    dfs(i, j);
                    //点能看到当前面，更新凸包的面
                    break;
                }
            }
        }
        tmp = num;
        for (i = num = 0; i < tmp; i++) {
            if (F[i].ok)F[num++] = F[i];
        }
    }

//凸包的表面积
    double area() {
        double res = 0;
        for (ll i = 0; i < num; i++)res += Area2(P[F[i].a], P[F[i].b], P[F[i].c]);
        return res / 2.0;
    }

//体积
    double volume() {
        double res = 0;
        Point3 tmp(0, 0, 0);
        for (ll i = 0; i < num; i++)res += volume4(tmp, P[F[i].a], P[F[i].b], P[F[i].c]);
        return fabs(res / 6.0);
    }

//表面三角形个数
    ll triangle() {
        return num;
    }

//表面多边形个数
    ll polygon() {
        ll i, j, res, flag;
        for (i = res = 0; i < num; i++) {
            flag = true;
            for (j = 0; j < i; j++) {
                if (same(i, j)) {
                    flag = false;
                    break;
                }
            }
            res += flag;
        }
        return res;
    }
};

int main() {
    int totalnum = 0;
    cin >> totalnum;
    double tolvolum = 0.00;
    vector<double> pointset;
    vector<double> volumm;
    CH3D allhull;
    for (int q = 0; q < totalnum; q++) {
        CH3D hull;
        cin >> hull.n;
        for (ll i = 0; i < hull.n; i++) {
            double a, b, c;
            cin >> a;
            cin >> b;
            cin >> c;
            hull.P[i].x = a;
            hull.P[i].y = b;
            hull.P[i].z = c;
            pointset.push_back(a);
            pointset.push_back(b);
            pointset.push_back(c);
        }
        hull.create();
        tolvolum += hull.volume();
        volumm.push_back(hull.volume());
    }
    int poinum = pointset.size() / 3;
    allhull.n = poinum;
    for (ll i = 0, q = 0; i < poinum * 3; i = i + 3, q++) {
        double a = pointset.at(i), b = pointset.at(i + 1), c = pointset.at(i + 2);
        allhull.P[q].x = a;
        allhull.P[q].y = b;
        allhull.P[q].z = c;
    }
    allhull.create();
    double vvoll = allhull.volume();
    for (auto q: volumm) {
        printf("%.3f", q);
        cout << endl;
    }
    if (vvoll < (tolvolum - 0.01)) {
        cout << "Crash!";
    } else {
        cout << "Safe";
    }

return 0;
}
```

## 7-8 Two-dimensional LIS

### 题意：

求二维最长上升子序列。

### 题解：

直接算DP时间复杂度是$O(n^2)$，考虑CDQ分治。

定义$CDQ(l，r)$处理区间$[l, r]$之间的LIS，进行如下操作：

1. 将区间$[l, r]$二分为$[l, mid]$和$[mid+1, r]$
2. $CDQ(l，mid)$
3. 处理左半区间对右半区间的影响（将左半区间的点为右端点，右半区间的点为左端点的能拼接的LIS拼接起来更新右半区间的LIS）
4. $CDQ(mid+1，r)$

接下来主要考虑操作3如何进行即可。可以用树状树组维护左半区间对应值的LIS长度。只不过这个树状树组维护的是前缀最大值而非前缀和。那么操作*4*就可以变成：

1. 将左半区间的值全部插入BIT中
2. 枚举右半区间的点，查询BIT中对应值在左半区间的LIS，然后和当前点的LIS进行拼接。

对值进行离散化处理，就可以在$O(nlog^2{n})$时间复杂度解决本问题。不进行离散化直接处理，时间复杂度为$O(nlog^2{n}logL)$，也可以通过本题。

```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 30;
struct node {
    int x, y, ans;
} a[maxn], tmp[maxn];
int b[maxn], cnt, imax[maxn], id[maxn];

void update(int pos, int val) {
    for (; pos <= cnt; pos += pos & -pos) {
        if (imax[pos] < val)
            imax[pos] = val;
        else
            break;
    }
}

int cal(int pos) {
    int res = 0;
    for (; pos > 0; pos -= pos & -pos)
        res = max(res, imax[pos]);
    return res;
}

void clr(int pos) {
    for (; pos <= cnt; pos += pos & -pos) {
        if (imax[pos] == 0)
            break;
        imax[pos] = 0;
    }
}

bool cmp(int i, int j) {
    return a[i].x < a[j].x;
}

void cdq(int l, int r) {
    if (l == r)
        return;
    int mid = l + r >> 1, L = l, R, k = 0;
    cdq(l, mid);
    for (int i = mid + 1; i <= r; ++i)
        id[i] = i; //准备更新右区间答案
    sort(id + mid + 1, id + r + 1, cmp);
    for (int i = mid + 1; i <= r; ++i) {
        int c = id[i];
        while (L <= mid && a[L].x < a[c].x) {
            update(a[L].y, a[L].ans);
            ++L;
        }
        a[c].ans = max(a[c].ans, cal(a[c].y - 1) + 1);
    }
    for (int i = l; i <= mid; ++i)
        clr(a[i].y); //清空BIT
    cdq(mid + 1, r);
    L = l, R = mid + 1; //准备归并本区间
    while (L <= mid && R <= r) {
        if (a[L].x <= a[R].x)
            tmp[k++] = a[L++];
        else
            tmp[k++] = a[R++];
    }
    while (L <= mid)
        tmp[k++] = a[L++];
    while (R <= r)
        tmp[k++] = a[R++];
    for (int i = 0; i < k; ++i)
        a[l + i] = tmp[i];
}

int main() {
    int n;
    cnt = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].x;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].y;
        a[i].ans = 1;
        b[++cnt] = a[i].y;
    }
    sort(b + 1, b + 1 + cnt);
    cnt = unique(b + 1, b + 1 + cnt) - b - 1;
    for (int i = 1; i <= n; ++i)
        a[i].y = lower_bound(b + 1, b + 1 + cnt, a[i].y) - b;
    cdq(1, n);
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, a[i].ans);
    cout << ans;
    return 0;
}
```

## 7-9 Strings

签到题之一。

在这个问题中，观察到数据很小，所以可以暴力每种类型的操作删除了多少个字符。如果从字符串$s$中删除了开头的$l$个字符和结尾的$x$个字符，则子字符串 $s[l+1，n−x]$ 保留，其中$n$是字符串$s$的长度。然后更新答案即可。

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    int ans = 0;
    for (int len = 1; len <= min(n, m); len++)
        for (int i = 0; i + len <= n; i++)
            for (int j = 0; j + len <= m; j++)
                if (a.substr(i, len) == b.substr(j, len))
                    ans = max(ans, len);
    cout << a.size() + b.size() - 2 * ans << "\n";
}

int main() {
    int n;
    cin >> n;
    while (n--)
        solve();
    return 0;
}
```

## 7-10 Alien Mothership

### 题意

给定一颗基环树，每个节点带有价值。选择任意节点之后，其相邻节点不能被选择。请选择点以使总价值最大。

### 题解

首先考虑树的部分，是一个最简单的树上DP。用$DP[i][0]$, $DP[i][1]$分别表示不选/选择$i$节点，其整颗子树的最大价值。

那么有：

$DP[i][0]=\sum_{j=sons[i][1]}^{sons[i][n]}{max(DP[j][0], DP[j][1])}$

$DP[i][1]=\sum_{j=sons[i][1]}^{sons[i][n]}{DP[j][0]}+val[i]$

这部分正确性显然。

那么再考虑环的部分，我们可以把环在任意边上拆开，称这条边相连的节点为A、B。拆环以后整个图变成一个无根树，因此AB任选一个节点作为根节点，取其$dp[x][0]$与$dp[x][1]$的最大值（共4个数的最大值）即可作为答案。

接下来考虑加上这条边AB对图造成的影响：最大值组合里面同时取到点A和B的方案变成非法了。那么结果就变成了$max({dp[A][0], dp[B][0]})$。为什么可以这样取呢？因为如果某个最大值方案包含点$B$，那么在$dp[A][0]$里就已经包含了，反之同理，所以这两种方案是能够涵盖可能的最大值情况的。

时间复杂度$O(M)$

### 代码

```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define int long long//我懒得改longlong了 不要学这种写法

const int _ = 100005;

int n, p[_], fa[_], S, T;
struct ed {
    int to, next;
} e[_ << 1];
int cnt, head[_];
double f[_][2];

void link(int u, int v) {
    e[++cnt] = (ed) {v, head[u]};
    head[u] = cnt;
}

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void dfs(int u, int fa) {
    f[u][1] = p[u];
    f[u][0] = 0;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v == fa)continue;
        dfs(v, u);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        fa[i] = i;
    }
    for (int i = 1; i <= n; ++i) {
        int u, v;
        cin >> u >> v;
        u++, v++;
        if (find(u) == find(v)) {
            S = u, T = v;
            continue;
        }
        link(u, v);
        link(v, u);
        fa[find(v)] = find(u);
    }
    double k, ans = 0;
    scanf("%lf", &k);
    dfs(S, 0);
    ans = f[S][0];
    dfs(T, 0);
    ans = max(ans, f[T][0]);
    printf("%.1lf\n", ans * k);
    return 0;
}
```

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

XATU第八届算法大赛题解

zclll • 2021 年 11 月 27 日