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

    个人题解，非广告
    题集链接；

    视频题解；

    目录

    B Rotate Sum 3

    计算几何

    题意

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

    思路

    分类讨论：

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

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

    代码

    #include 
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);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164

    C Constructive Problems Never Die

    构造

    题意

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

    思路

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

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

    代码

    #include 
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    F Candies

    数据结构、贪心

    题意

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

    思路

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

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

    代码

    下面是第一种

    #include 
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    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 

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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    J Melborp Elcissalc

    数学，DP

    题意

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

    思路

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

    我们定义状态表示：
    d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]为仅使用数字0~i，长度为j，好度为k的方案数；
    有初态：
    d p [ 0 ] [ j ] [ ( j + 1 ) j / 2 ] = 1 dp[0][j][(j+1)j/2]=1 dp[0][j][(j+1)j/2]=1；
    有状态转移方程：
    d p [ i ] [ j ] [ k ] = ∑ j = 0 n ∑ c t = 0 j ∑ k = c t ( c t − 1 ) 2 t d p [ i − 1 ] [ j − c t ] [ k − c t ( c t − 1 ) 2 ] C j c t 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} dp[i][j][k]=j=0∑n​ct=0∑j​k=2ct(ct−1)​∑t​dp[i−1][j−ct][k−2ct(ct−1)​]Cjct​
    即从j长度中填入ct个数字i；

    答案即为 d p [ k − 1 ] [ n ] [ t ] dp[k-1][n][t] dp[k−1][n][t]；

    代码

    #include 
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
  • 相关阅读:
    Java集合类ArrayList的应用-杨辉三角的前n行
    智能巡检系统有什么特点和功能？它是如何推动企业高效管理？
    前缀，后缀转中缀以及中缀转前缀，后缀
    openssl编程-基础知识-OpenSSL堆栈
    java压缩base64位图
    JSR303校验,分组校验,自定义注解校验,全局异常处理
    P1030 [NOIP2001 普及组] 求先序排列
    Drools规则属性，高级语法
    SS8837T智能门锁驱动马达-门锁电机驱动解决方案
    Mybatis-plus插件的一次完美实践
  • 原文地址：https://blog.csdn.net/Tan_Yuu/article/details/126270825