2022牛客暑期多校训练营7（BCFGJ）

题集链接；

视频题解；

• B Rotate Sum 3
  *
  • 题意
  • 思路
  • 代码
• C Constructive Problems Never Die
  *
  • 题意
  • 思路
  • 代码
• F Candies
  *
  • 题意
  • 思路
  • 代码
• G Regular Expression
  *
  • 题意
  • 思路
  • 代码
• J Melborp Elcissalc
  *
  • 题意
  • 思路
  • 代码

B Rotate Sum 3

计算几何

题意

给出一个凸包，使其绕对称轴旋转，求其扫过的体积；

思路

分类讨论：

1. 若没有对称轴，则不存在体积；
2. 若仅有一条对称轴，则按照旋转体求体积，为了避免被long double卡精度，可以将凸包形成的旋转体切成若干圆台，累加体积；
3. 若有大于等于2条对称轴，则其可以旋转为一个球，其半径为所有点与重心的距离的最大值；

对于第三种情况，由于其具有多条对称轴，重心可以通过坐标累加求平均值来得出；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1.0);
int sign(double x) // 符号函数
{
    if (fabs(x) < eps)
        return 0;
    if (x < 0)
        return -1;
    return 1;
};
struct Point
{
    ll x, y;
    Point(double a = 0, double b = 0) { x = a, y = b; }
    Point operator+(const Point &a) const { return Point(x + a.x, y + a.y); }
    Point operator-(const Point &a) const { return Point(x - a.x, y - a.y); }
    Point operator*(const double &a) const { return Point(x * a, y * a); }
    Point operator/(const double &a) const { return Point(x / a, y / a); }
    bool operator==(const Point &a) const { return !sign(x - a.x) && !sign(y - a.y); }
    bool operator<(const Point &a) const { return (fabs(x - a.x) < eps) ? (y < a.y) : (x < a.x); }
};
struct Line
{
    Point a, v;
    Line(Point x = Point(), Point y = Point()) { a = x, v = y; }
};
const int dots_num = 100005;
struct Poly
{
    int num;
    Point dots[dots_num];
    Poly(int x = 0) { num = x; }
};
ll dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
ll cross(Point a, Point b) { return a.x * b.y - b.x * a.y; }
ll get_length2(Point a) { return abs(dot(a, a)); }
ll polygon_square2(Poly m)
{
    ll ans = 0;
    for (int i = 0; i < m.num; i++)
    {
        ans += cross(m.dots[i], m.dots[(i + 1) % m.num]);
    }
    return abs(ans);
}
int pos;

int d[4 * dots_num];
int manacher(Poly v)
{
    vector<pair<ll, pair<Point, Point>>> str;
    int axiss = 0;
    for (int i = 0; i < v.num; i++)
    {
        str.push_back(
            make_pair(get_length2(v.dots[(i - 1 + v.num) % v.num] - v.dots[(i + 1) % v.num]),
                      make_pair(v.dots[(i - 1 + v.num) % v.num], v.dots[(i + 1) % v.num])));
        str.push_back(make_pair(get_length2(v.dots[i] - v.dots[(i + 1) % v.num]),
                                make_pair(v.dots[i], v.dots[(i + 1) % v.num])));
    }
    for (int i = 0; i < v.num << 1; i++)
    {
        str.push_back(str[i]);
    }
    int mx = 0, id; // mx为最右边，id为中心点
    for (int i = 0; i < str.size(); i++)
    {
        if (i < mx)
            d[i] = min(mx - i + 1, d[2 * id - i]); //判断当前点超没超过mx
        else
            d[i] = 1; //超过了就让他等于1，之后再进行查找
                      // if (i + d[i] - 1 >= mx) //实际操作中并不需要特判
        while (i + d[i] <= str.size() && i - d[i] >= 0 &&
               !sign(str[i + d[i]].first - str[i - d[i]].first))
            d[i]++; //判断当前点是不是最长回文子串，不断的向右扩展
        if (d[i] + i - 1 > mx)
        { //更新mx
            mx = d[i] + i - 1;
            id = i; //更新中间点
        }
        if (i >= v.num && i < 2 * v.num && 1 + 2 * (d[i] - 1) >= 2 * v.num)
            axiss++, pos = i -v.num;
    }
    return axiss;
}

double distance_to_line(Point p, Line m)
{
    return fabs(cross(p - m.a, m.v) / sqrt(get_length2(m.v)));
}
double polygon_center(Poly m, Line ml)
{
    Point ans(0, 0);
    pair<double, double> mp;
    if (sign(polygon_square2(m)) == 0)
        return 0;
    for (int i = 0; i < m.num; i++)
    {
        ans =
            ans + (m.dots[i] + m.dots[(i + 1) % m.num]) * cross(m.dots[i], m.dots[(i + 1) % m.num]);
    }
    mp.first = ans.x / 3.0 / (polygon_square2(m));
    mp.second = ans.y / 3.0 / (polygon_square2(m));
    pair<double, double> tmp = {mp.first - ml.a.x, mp.second - ml.a.y};
    double dis = fabs((tmp.first * ml.v.y - ml.v.x * tmp.second) / sqrt(get_length2(ml.v)));
    return dis;
}

int main()
{
    int n;
    cin >> n;
    Poly a = Poly(n), h = Poly(0);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld%lld", &a.dots[i].x, &a.dots[i].y);
    }
    int as = manacher(a);
    // cout << as << endl;
    if (as == 0)
    {
        printf("0");
    }
    else if (as == 1)
    {
        vector<Point> u;
        for (int i = 0; i < a.num; i++)
        {
            u.push_back(a.dots[i] + a.dots[i]);
            u.push_back(a.dots[i] + a.dots[(i + 1) % a.num]);
        }
        // u[pos] 为对称轴的上的点
        Point lp = u[(pos + a.num) % (2 * a.num)], lv = lp - u[pos];
        int l = (pos - 1 + (2 * a.num)) % (2 * a.num), r = (pos + 1) % (2 * a.num);
        long double ans = 0, k2 = 0;
        for (; l != r; l = (l - 1 + (2 * a.num)) % (2 * a.num), r = (r + 1) % (2 * a.num))
        {
            long double k1 = sqrt(get_length2(u[l] - u[r])) / 2;
            long double h = fabs(dot(u[r] - u[(r - 1 + (2 * a.num)) % (2 * a.num)], lv));
            ans += h * (k1 * k1 + k2 * k2 + k1 * k2);
            k2 = k1;
        }
        printf("%.12Lf", PI * ans / 24 / sqrt(get_length2(lv)));
    }
    else
    {
        Point m = Point();
        for (int i = 0; i < n; i++)
        {
            m = m + a.dots[i];
        }
        __int128 r = 0;
        for (int i = 0; i < n; i++)
        {
            r = max(r, (__int128)(m.x - n * a.dots[i].x) * (m.x - n * a.dots[i].x) + (__int128)(m.y - n * a.dots[i].y) * (m.y - n * a.dots[i].y));
        }
        // cout << r << endl;
        printf("%.12Lf", (long double)4.0 / 3 * PI * sqrtl(r) / n * r / n / n);
    }
}

C Constructive Problems Never Die

构造

题意

给定一个长度为 n 的序列，要求构造一个等长的排列，使得排列每一位都与序列的对应位不同；

思路

默认排列为1~n，顺次处理每一位，如果此位与序列对应位相同，则将此位与最后一位对换；

对于最后一位，如果与序列对应位相同，则向前寻找合适的位来对换，若寻找不到，则认为此情况无解；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int b[100005], a[100005];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, f = 1;
        cin >> n;
        for (int i = 1; i <= n; i++)
            scanf("%d", &b[i]), a[i] = i;
        for (int i = 1; i < n; i++)
            if (b[i] == a[i])
                swap(a[i], a[i + 1]);
        if (a[n] == b[n])
        {
            int i = n;
            while (b[i] == a[n] && i >= 1)
                i--;
            if (i)
                swap(a[i], a[n]);
            else
                f = 0;
        }
        if (f)
        {
            printf("YES\n");
            for (int i = 1; i <= n; i++)
                printf("%d ", a[i]);
            printf("\n");
        }
        else
        {
            printf("NO\n");
        }
    }
    return 0;
}

F Candies

数据结构、贪心

题意

给出一个长度为n的循环序列和数字x，若序列中相邻的两位相同或和为x，则删去这两位，与这两位相邻的两位变得相邻；求最多删去多少次；

思路

考虑贪心维护双向链表暴力做，赛时并没有发现可以卡掉贪心策略或将其复杂度卡至 $O(n^2)$ 的情况；
注意判断在双向链表过短时的处理方式；

也可以将所有满足 $x/2<a_i\leqslant x$ 的数字处理成 $x-a_i$ ，之后使用栈来依据相等判据维护，最后处理栈顶和栈底是否可以消除；

代码

下面是第一种

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct
{
    ll a;
    int lst, nxt;
} lk[100005];
int main()
{
    ll n, x, ct = 0;
    cin >> n >> x;
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &lk[i].a);
        lk[i].nxt = (i + 1) % n;
        lk[i].lst = (i - 1 + n) % n;
    }
    int nw = 0;
    while (1)
    {
        if (n - 2 * ct <= 1)
        {
            break;
        }
        int f = 0, ctt = 0;
        while (ctt / 2 <= n - 2 * ct)
        {
            if (lk[nw].a == lk[lk[nw].nxt].a || lk[nw].a + lk[lk[nw].nxt].a == x)
            {
                // printf("%d %d %d*\n",nw,lk[nw].a,lk[lk[nw].nxt].a);
                nw = lk[nw].lst;
                lk[nw].nxt = lk[lk[lk[nw].nxt].nxt].nxt;
                int tmp = lk[nw].nxt;
                lk[tmp].lst = nw;
                ct++;
                f++;
            }
            else
            {
                // printf("%d*\n",nw);
                nw = lk[nw].nxt;
            }
            ctt++;
            // nw%=n;
        }
        if (!f)
            break;
    }
    cout << ct;
    return 0;
}

G Regular Expression

题意

依照题目中给出的正则表达式规则，对于每个题给串找出最短的、全匹配的正则表达式长度，和最短长度下的表达式数目；

思路

我们发现表达式 .* 即可以表示任意串，所以表达式长度不会超过2；

对于长度为1的串，其正则表达式最短长度为1，2种情况为 a .；
对于长度为2的串，如果每位相同，则最短长度为2，8种情况为aa a. .a a* a+ .. .* .+；
对于长度为2的串，如果每位不同，则最短长度是2，6种情况为ab a. .b .. .* .+；
对于长度大于等于3的串，如果每位相同，则最短长度为2，4种情况为a* a+ .* .+；
对于长度大于等于3的串，如果不满足每位相同，则最短长度为2，2种情况为.* .+；
（上述a,b均仅为示意）

代码

队友代码如下

#include <iostream>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t ; cin >> t;
    while(t--) {
        string s ; cin >> s;
        if(s.length() == 1) {
            cout << "1 2\n";
            continue;
        } 
        if(s.length() == 2) {
            if(s[0] == s[1]) {
                cout << "2 8\n";
            } else cout << "2 6\n";
            continue;
        }
        
        bool f = true;
        for (int i = 1 ; i != s.length() ; i ++ ) {
            if(s[i] == s[i - 1]) continue;
            f = false;
            break;
        }
        
        if(f) {
            cout << "2 4\n";
        } else {
            cout << "2 2\n";
        }
        
    }
    
    return 0;
}

J Melborp Elcissalc

数学，DP

题意

定义由0~k-1数字组成的序列的k意义下好度为该序列所有子序列中，子序列和在k意义下与0同余的数量；求长度为n的序列中k意义下好度为t的序列个数；

思路

我们将序列转换成模k前缀和，我们定义$c[i]$为数字i在模k前缀和中出现的次数；
我们发现该序列的好度为 $\sum_{i=0}^{k-1}C_{c[i]}^2$；
也就是说每一个模k前缀和序列都对应着一个原始序列，我们只需要统计模k前缀和序列中符合条件的个数即可；

我们定义状态表示：
$dp[i][j][k]$为仅使用数字0~i，长度为j，好度为k的方案数；
有初态：
$dp[0][j][(j+1)j/2]=1$；
有状态转移方程：

$dp[i][j][k]=\sum_{j=0}^n\sum_{ct=0}^j\sum_{k=\frac{ct(ct-1)}{2}}^{t}dp[i-1][j-ct][k-\frac{ct(ct-1)}{2}]C_{j}^{ct}$

即从j长度中填入ct个数字i；

答案即为$dp[k-1][n][t]$；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 70;
const ll M = 998244353;
ll dp[N][N][N * N / 2]; //使用数字0~i，长度j，贡献k
ll fc[N], inv[N];
ll qm(ll a, ll b)
{
    ll ans = 1;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % M;
        a = a * a % M;
    }
    return ans;
}
int c(int n, int m) { return fc[n] * inv[m] % M * inv[n - m] % M; }
void init()
{
    fc[0] = inv[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fc[i] = fc[i - 1] * i % M;
        inv[i] = qm(fc[i], M - 2);
    }
}
int main()
{
    int n, m, t;
    cin >> n >> m >> t;
    init();
    for (int j = 0; (j + 1) * j / 2 <= t; j++)
        dp[0][j][(j + 1) * j / 2] = 1;
    for (int i = 1; i < m; i++) //限定数字
    {
        for (int j = 0; j <= n; j++) //限定长度
        {
            for (int ct = 0; ct <= j; ct++) //限定i的使用量
            {
                for (int k = ct * (ct - 1) / 2; k <= t; k++) //限定贡献
                {
                    dp[i][j][k] += dp[i - 1][j - ct][k - ct * (ct - 1) / 2] * c(j, ct) % M;
                    dp[i][j][k] %= M;
                }
            }
        }
    }
    cout << dp[m-1][n][t];
    return 0;
}