2022牛客暑期多校训练营2（BDGHJKL）

题集链接；

视频题解；

• B light
  *
  • 思路
  • 代码
• D Link with Game Glitch
  *
  • 思路
  • 代码
• G Link with Monotonic Subsequence
  *
  • 思路
  • 代码
• H Take the Elevator
  *
  • 思路
  • 代码
• J Link with Arithmetic Progression
  *
  • 思路
  • 代码
• K Link with Bracket Sequence I
  *
  • 思路
  • 代码
• L Link with Level Editor I
  *
  • 思路
  • 代码
• ED

B light

计算几何

思路

首先对围墙外围进行定量缩水形成校园区域；
再对校园区域（实际上是对形状为校园区域，高度为墙高的悬浮多边形）进行投影形成月光可能照到的区域；
最后对月光区域和实际区域求多边形面积交（半平面交）获得题求面积；

代码

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

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
{
    double 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); }
    Point left90() { return Point(-y, x); }
};
struct Line
{
    Point a, v;
    Line(Point x = Point(), Point y = Point()) { a = x, v = y; }
};
struct Segm
{
    Point a, b;
    Segm(Point x = Point(), Point y = Point()) { a = x, b = y; }
};
struct Circle
{
    Point o;
    double r;
    Circle(Point x = Point(), double y = 0) { o = x, r = y; }
};
const int dots_num = 2003;
struct Poly
{
    int num;
    Point dots[dots_num];
    Poly(int x = 0) { num = x; }
};

double dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
double cross(Point a, Point b) { return a.x * b.y - b.x * a.y; }
double get_length(Point a) { return sqrt(dot(a, a)); }
Point get_line_intersection(Line m, Line n)
{
    Point u = m.a - n.a;
    if (sign(cross(m.v, n.v)) == 0)
        return Point(0, 0);
    double t = cross(n.v, u) / cross(m.v, n.v);
    return m.a + m.v * t;
}

bool cmp(const Line &a, const Line &b)
{
    double da = atan2(a.v.y, a.v.x), db = atan2(b.v.y, b.v.x);
    if (!sign(da - db))
    {
        return cross(a.v, b.a + b.v - a.a) < 0;
    }
    else
        return da < db;
}
bool point_on_line_right(Point p, Line l)
{
    return sign(cross(l.v, p - l.a)) < 0;
}
Line lne[4006];
Poly half_plane_intersection(int cnt)
{
    sort(lne, lne + cnt, cmp);
    int hh = 0, tt = -1;
    Line dque[4006];
    for (int i = 0; i < cnt; i++)
    {
        if (i && !sign(atan2(lne[i].v.y, lne[i].v.x) - atan2(lne[i - 1].v.y, lne[i - 1].v.x)))
            continue;
        while (hh + 1 <= tt &&
               point_on_line_right(get_line_intersection(dque[tt - 1], dque[tt]), lne[i]))
            tt--;
        while (hh + 1 <= tt &&
               point_on_line_right(get_line_intersection(dque[hh], dque[hh + 1]), lne[i]))
            hh++;
        dque[++tt] = lne[i];
    }
    while (hh <= tt && point_on_line_right(get_line_intersection(dque[tt], dque[tt - 1]), dque[hh]))
        tt--;
    Poly ans = Poly();
    if (tt - hh + 1 >= 3)
        for (int i = 0; i <= tt - hh; i++)
            ans.dots[ans.num++] =
                get_line_intersection(dque[hh + i], dque[hh + (i + 1) % (tt - hh + 1)]);
    return ans;
}

Poly Polygon_shrinkage(Poly pl, double d)
{
    for (int i = 0; i < pl.num; i++)
    {
        Line tmp = Line(pl.dots[i], pl.dots[(i + 1) % pl.num] - pl.dots[i]);
        Point dir = tmp.v.left90();
        dir = dir / get_length(dir) * d;
        lne[i] = Line(tmp.a + dir, tmp.v);
    }
    return half_plane_intersection(pl.num);
}

double polygon_square(Poly m)
{
    double ans = 0;
    for (int i = 0; i < m.num; i++)
    {
        ans += cross(m.dots[i], m.dots[(i + 1) % m.num]);
    }
    return ans / 2;
}

double Poly_area_intersection(Poly a, Poly b)
{
    int ct = 0;
    for (int i = 0; i < a.num; i++)
    {
        lne[ct++] = Line(a.dots[i], a.dots[(i + 1) % a.num] - a.dots[i]);
    }
    for (int i = 0; i < b.num; i++)
    {
        lne[ct++] = Line(b.dots[i], b.dots[(i + 1) % b.num] - b.dots[i]);
    }
    return polygon_square(half_plane_intersection(ct));
}

bool on_segment(Point p, Segm m)
{
    Point u = m.a - p, v = m.b - p;
    return sign(cross(u, v)) == 0 && sign(dot(u, v)) <= 0;
}
bool point_in_polygon(Point p, Poly m)
{
    for (int i = 0; i < m.num; i++)
    {
        if (on_segment(p, Segm(m.dots[(i + 1) % m.num], m.dots[i])))
            return 1;
        if (sign(cross(p - m.dots[i], m.dots[(i + 1) % m.num] - m.dots[i])) > 0)
            return 0;
    }
    return 1;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        double h, w;
        scanf("%d%lf%lf", &n, &h, &w);
        Poly yrd = Poly(n);
        for (int i = 0; i < n; i++)
        {
            scanf("%lf%lf", &yrd.dots[i].x, &yrd.dots[i].y);
        }
        yrd = Polygon_shrinkage(yrd, w);
        Point blb;
        double hb;
        scanf("%lf%lf%lf", &blb.x, &blb.y, &hb);
        if (point_in_polygon(blb, yrd))
        {
            printf("%.10lf\n", polygon_square(yrd));
            continue;
        }
        else if (sign(hb - h) <= 0 || !yrd.num)
        {
            printf("0\n");
            continue;
        }
        Poly nyrd = Poly(yrd.num);
        for (int i = 0; i < yrd.num; i++)
        {
            Point d = yrd.dots[i] - blb;
            nyrd.dots[i] = yrd.dots[i] + d * h / (hb - h);
        }
        printf("%.10lf\n", Poly_area_intersection(yrd, nyrd));
    }
    // printf("*%d\n",yrd.num);
    // for(int i=0;i<yrd.num;i++)printf("%lf %lf\n",yrd.dots[i].x,yrd.dots[i].y);
    return 0;
}

D Link with Game Glitch

图论，二分

思路

题目给出一有向图，边上有边权，定义一个环的的权重为环上边权积，现让所有边权乘上一个系数 w ，使得所有环的权重不大于1，求最大w；

首先想到对于判断负环可以通过BellmanFord算法，同理，在这道题中我们可以来确定是否存在正环；

实践发现，边权过大，超过了long double的承载能力，我们对边权和w取log，由乘法变成加法，即可保持正相关性；

代码

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
const int N = 1010;
const double inf = 1e9;
#define double long double
vector<pair<int, double>> E[N];

double value[N];
int n;

bool bf(int s, double w)
{
    value[s] = 1;
    for (int i = 1; i <= n + 1; i++)
    {
        int f = 0;
        for (int j = 1; j <= n; j++)
        {
            for (int k = 0; k < E[j].size(); k++)
            {
                if (value[j] + E[j][k].second + w > value[E[j][k].first])
                {
                    f = 1;
                    value[E[j][k].first] = value[j] + E[j][k].second + w;
                }
            }
        }
        if (!f)
            return 1;
    }
    return 0;
}
bool check(double m)
{
    for (int i = 1; i <= n; i++)
        value[i] = 1e-2;
    for (int i = 1; i <= n; i++)
    {
        if (fabs(value[i] - 1e-2) < 1e-4)
        {
            if (!bf(i, m))
                return false;
        }
    }
    return true;
}

int main()
{
    int m;
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        E[b].push_back({d,log( c * 1.0 / a)});
    }

    double l = 0, r = 100;

    while (r - l > 1e-17)
    {
        // printf("*%.10Lf %.10Lf\n",l,r);
        auto mt = (l + r) / 2;
        if (check(log(mt)))
        {
            l = mt;
        }
        else
        {
            r = mt;
        }
    }
    // if(l > 1e7) l = 1;
    printf("%.15Lf\n", l);
}

实际上发现大家用dfs更多，而且dfs由于运算更少，可以直接long double碾过去，下附队友的代码；

#include <iostream>
#include <vector>
using namespace std;

const int N = 1010;

vector<pair<int, double>> E[N];

long double value[N];
bool vis[N];
int cnt[N];

bool dfs(int u, double m) {
   vis[u] = true;
   for (auto [v, w] : E[u]) {
      if (value[v] < w * m * value[u]) {
         if (vis[v]) {
            return false;
         }
         value[v] = w * m * value[u];
         if (dfs(v, m) == false) return false;
      }
   }
   vis[u] = false;
   return true;
}

bool check(int n, double m) {
   for (int i = 1; i <= n; i++) value[i] = 1, vis[i] = false;
   for (int i = 1; i <= n; i++) {
      if (value[i] == 1) {
         cnt[i] = 0;
         if (dfs(i, m) == false) return false;
      }
   }
   return true;
}

int main() {
   int n, m;
   cin >> n >> m;

   for (int i = 0; i < m; i++) {
      int a, b, c, d;
      cin >> a >> b >> c >> d;
      E[b].push_back({d, c * 1.0 / a});
   }

   double l = 0, r = 1e9;

   while (r - l > 1e-15) {
      auto m = (l + r) / 2;
      if (check(n, m)) {
         l = m;
      } else {
         r = m;
      }
   }
   printf("%.15lf\n", r);
}

G Link with Monotonic Subsequence

数学（？）

思路

给定n，输出一个n的排列，使得这个排列的最长上升子序列与最长下降子序列的长度最大值最小；

暴力输出找规律：发现将n个数分成 $\sqrt{(n)}$ 个块，变成形如：789456123的形式，符合题目要求；

代码

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

int main()
{
    int t,n,p,ct,bas;
    cin>>t;
    while(t--)
    {
        cin>>n;
        p=sqrt(n)+1-1e-4;
        bas=0,ct=0;
        while(ct<n)
        {
            if(ct%p==0)bas=min(bas+p,n);
            printf("%d ",bas-ct%p);
            ct++;
        }
        printf("\n");
    }
    return 0;
}

H Take the Elevator

贪心

思路

k层大楼，n个人在等电梯，电梯最多同时装m人，电梯只有在一层时可以由下行切换至上行，反向切换不受限制，电梯上一层或下一层均消耗一单位时间，乘客上下电梯不消耗时间，从一层开始，求最少用多少时间运送完成回到一层；

将上行和下行分开考虑，认为一趟先处理上行，再处理下行；分开考虑后，上行下行没有本质区别，我们也将上行部分调转为下行形式（即较低层下，较高层上）；

对于下行（上行亦然），我们使用贪心策略，优先处理欲到达最高层的乘客，以减少电梯访问高层的次数；我们记录每轮运输上下行所到达的最高层，并在上下行中取最大值来计算此轮运输时间，累计所有运输轮即为答案；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define pir make_pair
using namespace std;

int n, m, k, u, v;
vector<pii> up, down;
vector<int> up_set, down_set;

bool cmp(pii a, pii b)
{
    if (a.first == b.first)
        return a.second < b.second;
    return a.first > b.first;
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &u, &v);
        if (u < v)
            up.push_back({u, -1}), up.push_back({v, 1});
        else
            down.push_back({u, 1}), down.push_back({v, -1});
    }
    sort(up.begin(), up.end(), cmp);
    sort(down.begin(), down.end(), cmp);

    int nowcnt = 0, up_turn = 0, down_turn = 0;
    for (auto p : up)
    {
        nowcnt += p.second;
        if (nowcnt > up_turn * m)
            up_set.push_back(p.first), up_turn++;
    }
    for (auto p : down)
    {
        nowcnt += p.second;
        if (nowcnt > down_turn * m)
            down_set.push_back(p.first), down_turn++;
    }

    int allturns = max(up_turn, down_turn);
    while (up_turn < allturns)
        up_set.push_back(0), up_turn++;
    while (down_turn < allturns)
        down_set.push_back(0), down_turn++;

    ll ans = 0;
    for (int i = 0; i < allturns; i++)
        ans += 2ll * (max(up_set[i], down_set[i]) - 1);
    printf("%lld\n", ans);
    return 0;
}

J Link with Arithmetic Progression

数学

思路

给定一些点，拟合直线使得方差最小；

最小二乘法拟合直线，注意精度；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll M = 998244353;
ld a[100005];
namespace GTI
{
    char gc(void)
    {
        const int S = 1 << 16;
        static char buf[S], *s = buf, *t = buf;
        if (s == t)
            t = buf + fread(s = buf, 1, S, stdin);
        if (s == t)
            return EOF;
        return *s++;
    }
    int gti(void)
    {
        int a = 0, b = 1, c = gc();
        for (; !isdigit(c); c = gc())
            b ^= (c == '-');
        for (; isdigit(c); c = gc())
            a = a * 10 + c - '0';
        return b ? a : -a;
    }
}
using GTI::gti;
int main()
{
    int t;
    // cin >> t;
    t=gti();
    while (t--)
    {
        int n;
        ll tmp;
        // cin >> n;
        n=gti();
        for (int i = 1; i <= n; i++)
        {
            // scanf("%Lf", &a[i]);
            a[i]=gti();
        }
        ld A, B, C, D;
        A = B = C = D = 0;
        for (int i = 1; i <= n; i++)
        {
            A += (ld)i * i;
            B += (ld)i;
            C += (ld)i * a[i];
            D += a[i];
        }
        long double k = (long double)(C * n - B * D) / (A * n - B * B);
        long double b = (long double)(D - k * B) / n;
        long double cst = 0;
        for (int i = 1; i <= n; i++)
        {
            long double tmp = (a[i] - (ld)i * k - b);
            cst += tmp * tmp;
        }
        printf("%.16Lf\n", cst);
    }
}

K Link with Bracket Sequence I

DP

思路

给定长度为n的括号串a，求长度为m的合法括号串中，a为其子序列的个数；

真的没看出来是DP

构造状态表示：$dp[i][j][k]$ 为长度为i的括号串中，a的j长前缀串是当前串的子序列，且左括号比右括号多k个 的方案数；
定义初态：$dp[0][0][0]=1$；
构造状态转移方程：
试着打了半天，找不到比代码更优雅的表现形式，大体上就是分别考虑加左括号和右括号来到达目前的k值，如果a串的对应位与当前考虑的不符，则变为更新$dp[i][j-1][k]$；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll M = 1e9 + 7;
ll dp[202][202][102];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        string a;
        cin >> a;
        for (int i = 0; i <= m; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                for (int k = 0; k <= min(i + 1, m - i + 1); k++)
                {
                    dp[i][j][k] = 0;
                }
            }
        }
        dp[0][0][0] = 1;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= min(n+1, i); j++)
            {
                for (int k = 0; k <= min(i + 1, m - i + 1); k++)
                {
                    // 加右括号
                    {
                        if (a[j - 1] == ')')
                            dp[i][j][k] = (dp[i - 1][j - 1][k + 1] + dp[i][j][k]) % M;
                        else
                            dp[i][j - 1][k] = (dp[i - 1][j - 1][k + 1] + dp[i][j - 1][k]) % M;
                    }
                    if (k > 0) // 加左括号
                    {
                        if (a[j - 1] == '(')
                            dp[i][j][k] = (dp[i - 1][j - 1][k - 1] + dp[i][j][k]) % M;
                        else
                            dp[i][j - 1][k] = (dp[i - 1][j - 1][k - 1] + dp[i][j - 1][k]) % M;
                    }
                }
            }
        }
        // for (int i = 1; i <= m; i++)
        // {
        //     for (int j = 0; j <= n; j++)
        //     {
        //         for (int k = 0; k <= m; k++)
        //             printf("%lld* ", dp[i][j][k]);
        //         printf("\n");
        //     }
        //     printf("\n");
        // }
        printf("%lld\n", dp[m][n][0]);
    }
}

L Link with Level Editor I

DP

思路

给定n张有向图，m个点，从某一张图的1号点出发，每次可以选择在此张图中沿边运动，或者变化到下一张图的同编号点；求这些图中，从1号店到m号点的一条路径里，最少经过图的数量；

真的没看出来是DP

构造状态表示：$dp[i][u]$ 表示在前 i 张图中，能通到第 i 张图的 u 点的最后一个1号点所在图编号；
构造初态：初值为0；
构造状态表示：对于边 $v\to u$ ， $dp[i][u]=max(dp[i-1][u],dp[i-1][v])$ ；
对于边 $1\to u$ ， $dp[i][u]=i$ ；
每个图接收完成后更新答案；

介于内存限制，可以使用滚动数组只保留两层dp数组；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[2][2010], ans = 100000000;
int main()
{
    int n, m, r, u, v, now = 1;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        
        for (int j = 0; j <= m; j++)
            dp[now][j] = dp[now ^ 1][j];
        scanf("%d", &r);
        while (r--)
        {
            scanf("%d%d", &u, &v);
            if (u == 1)
                dp[now][v] = i;
            else
                dp[now][v] = max(dp[now ^ 1][u], dp[now][v]);
        }
        if (dp[now][m])
            ans = min(ans, i - dp[now][m] + 1);
        now ^= 1;
    }
    if (ans == 100000000)
        cout << -1 << endl;
    else
        cout << ans << endl;
    return 0;
}

ED

看了题解之后，发现B题是会做的，所谓多边形面积交并不存在，只不过是半平面交罢了，在A掉这道题之前还需要试验一下半平面交板子在空集情况下的表现，争取在下一场比赛之前处理掉；

B已AC已更新；