2022 Niuke summer multi school training camp 2 (bdghjkl)

Question set links ;

Video problem solving ;

B light

Computational geometry

Ideas

First of all, the periphery of the fence is quantitatively shrunk to form the campus area ;
Then to the campus area （ In fact, the shape of the campus area , A floating polygon with a height of wall ） Project to form areas that may be illuminated by moonlight ;
Finally, the intersection of the polygon area between the moonlight area and the actual area （ Half plane intersection ） Get the problem area ;

Code

#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) //  Symbolic function 
{
    
    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

graph theory , Two points

Ideas

The title gives a directed graph , There is edge power , Define the weight of a ring as the weight product of the upper edge of the ring , Now let's multiply all the edge weights by a coefficient w , Make the weight of all rings not greater than 1, Ask for the biggest w;

First of all, I think that for judging negative rings, I can pass BellmanFord Algorithm , Empathy , In this problem, we can determine whether there is a positive ring ;

Practical discovery , Too much edge power , More than the long double The carrying capacity of , We are right on the side and w take log, From multiplication to addition , Can maintain a positive correlation ;

Code

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

In fact, I found that everyone used dfs more , and dfs Because there are fewer operations , Can directly long double Run over , The code of teammates is attached below ;

#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

mathematics （？）

Ideas

Given n, Output one n Permutation , Make the maximum length of the longest ascending subsequence and the longest descending subsequence of this arrangement minimum ;

Find rules for the output of violence ： Findings will be n Divide into numbers $\sqrt{(n)}$ Block , Become like ：789456123 In the form of , Meet the requirements of the topic ;

Code

#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

greedy

Ideas

k Floor building ,n A man is waiting for the elevator , Elevators can be installed at most m people , The elevator can be switched from down to up only on the first floor , Reverse switching is unlimited , It takes one unit of time for the elevator to go up or down , It doesn't take time for passengers to get on and off the elevator , From the first floor , Ask how much time it takes to complete the transportation and return to the first floor ;

Consider uplink and downlink separately , Think that one trip will deal with the uplink first , Then deal with the downlink ; Consider separately , There is no essential difference between uplink and downlink , We also turn the upward part into the downward form （ That is, below the lower level , On the higher level ）;

For downlink （ The same goes for the upside ）, We use greedy tactics , Give priority to passengers who want to reach the highest level , To reduce the number of elevator visits to high floors ; We record the highest level reached by each round of transportation up and down , And take the maximum value in the uplink and downlink to calculate the transportation time of this ship , Accumulating all transport wheels is the answer ;

Code

#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

mathematics

Ideas

Given some points , Fitting a straight line minimizes variance ;

The least square method is used to fit the straight line , Pay attention to precision ;

Code

#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

Ideas

Given length is n Bracket string of a, Find the length of m In the legal bracket string of ,a Is the number of subsequences ;

I really didn't see it was DP

Construction state indicates ：$dp[i][j][k]$ For a length of i In the bracket string of ,a Of j The long prefix string is a subsequence of the current string , And there are more left parentheses than right parentheses k individual Number of alternatives ;
Define initial state ：$dp[0][0][0]=1$;
Construct the state transition equation ：
I tried for a long time , There is no more elegant expression than code , In general, we should consider adding left parentheses and right parentheses respectively to reach the current k value , If a The corresponding bit of the string is inconsistent with the current consideration , Then it becomes updated $dp[i][j-1][k]$;

Code

#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++)
                {
    
                    //  Right parenthesis 
                    {
    
                        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) //  Add left parenthesis 
                    {
    
                        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

Ideas

Given n Directed graph ,m A little bit , From the 1 Starting at No , You can choose to move along the edge in this picture every time , Or change to the same number point of the next figure ; Find the , from 1 Shop No m In a path at point , Minimum number of graphs ;

I really didn't see it was DP

Construction state indicates ：$dp[i][u]$ In front of i Zhang Tuzhong , It can lead to i Picture of u The last point 1 No. of the drawing where the No. point is located ;
Initial state of structure ： The initial value is 0;
Construction state indicates ： For edge $v\to u$ , $dp[i][u]=max(dp[i-1][u],dp[i-1][v])$ ;
For edge $1\to u$ , $dp[i][u]=i$ ;
Update the answer after receiving each figure ;

Between memory limit , You can use a scrolling array to keep only two layers dp Array ;

Code

#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

After reading the solution , Find out B I can do it , The so-called polygon area intersection does not exist , It's just the intersection of half planes , stay A Before dropping this question, we need to test the performance of half plane intersection board in the case of empty set , Try to get rid of it before the next game ;

B has AC Updated ;