2022 Niu Ke Summer Multi-School Training Camp 5 (BCDFGHK)

题集链接;

B Watches

二分

题意

Watch shop has n Watch for sale,第 i Watch for $a_i$ .若购买 k 个手表,那么第 i Watches cost $a_i+ki$ 元.现有 m 元,O can buy up to how many watch;

思路

We consider that each watch costs related to the total purchase,Is not convenient to direct greedy processing,We choose binary out k 后,According to the actual cost for sorting and greedy;

代码

Teammates as follows

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

int main() {
    
    cin.tie(0) -> sync_with_stdio(false);
   int n, m;
   cin >> n >> m;

   vector<long long> a(n);
   for (auto& x : a) cin >> x;

   auto solve = [&](int k) -> bool {
    
      vector<long long> b(a);
      for (int i = 0; i < n; i++) {
    
         b[i] += 1ll * (i + 1) * k;
      }
      sort(b.begin(), b.end());
      long long sum = 0;
      for (int i = 0; i < k; i++) {
    
         sum += b[i];
      }
      return sum <= m;
   };

   int l = 0, r = n;
   int ans = 0;
   while (l <= r) {
    
      int mid = (l + r) / 2;
      if (solve(mid)) {
    
         ans = mid;
         l = mid + 1;
      } else {
    
         r = mid - 1;
      }
   }
   cout << ans << '\n';
}

C Bit Transmission

题意

Robot has a length of n 的字符串,Now ask the robot 3n Whether one is 1 ,But in all ask,Most robots will return an error.For a robot to answer,If there is a unique string of the output,否则返回 -1 ;

思路

First to exclude some obvious without the only answer,Such as the one without being asked;

Due to the unknown whether there is wrong,We need to first positioning error,To one asked more than twice a,If the results appear in a different,You can conclude that errors occur in here;

If can't positioning error,In addition to all who are being questioned more than twice and answer the same outside,The rest of the case are not only the original string;

代码

Teammates as follows

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

int main()
{
    
    int n;
    while (cin >> n)
    {
    
        vector a(n, pair<int, int>(0, 0));
        for (int i = 0; i < n * 3; i++)
        {
    
            int x;
            string s;
            cin >> x >> s;
            if (s[0] == 'Y')
            {
    
                a[x].second++;
            }
            else
            {
    
                a[x].first++;
            }
        }

        bool f = true;

        for (int i = 0; i < n; i++)
        {
    
            if (a[i].first + a[i].second == 0)//No asked
            {
    
                f = false;
                break;
            }
        }

        int cnt = 0;
        if (f)
        {
    
            for (int i = 0; i < n; i++)
            {
    
                if (a[i].first + a[i].second > 2)
                {
    
                    if (a[i].first == 1 || a[i].second == 1)//错误发生
                    {
    
                        cnt++;
                    }
                    else if (a[i].first != 0 && a[i].second != 0)//At least two same mistake
                    {
    
                        f = false;
                        break;
                    }
                    if (cnt == 2)//多个错误
                    {
    
                        f = false;
                        break;
                    }
                }
            }
        }
        if (f)
        {
    
            if (cnt == 0)//If can't positioning error
            {
    
                for (int i = 0; i < n; i++)
                {
    
                    if (a[i].first == 1 || a[i].second == 1)//Unable to determine the result authenticity
                    {
    
                        f = false;
                        break;
                    }
                }
            }
            for (int i = 0; i < n; i++)
            {
    
                if (a[i].first == 1 && a[i].second == 1)//若出现11
                {
    
                    f = false;
                    break;
                }
            }
        }
        if (f)
        {
    
            for (int i = 0; i < n; i++)
            {
    
                if (a[i].first > a[i].second)
                {
    
                    cout << 0;
                }
                else
                    cout << 1;
            }
        }
        else
        {
    
            cout << -1;
        }
        cout << '\n';
    }

    return 0;
}

D Birds in the tree

树状DP

题意

给出一个 n 个节点的树,每个节点有颜色 0 或 1 ,Its how many connected subgraph,Meet the degree of 1 The nodes of the same color;

思路

构造状态表示：$dp[i][j]$ 为以节点 i 为根的子树中,How many connected subgraph,度数为 1 的节点（若 i Is not the only one not consider i ）颜色为 j;
推导状态转移方程：
$$dp[i][j]=\prod _{k\in so{n}_i}(1+dp[k][j])-[col[i]!=j]$$
The previous LianCheng type obviously for counting multiplication principle,对于每一个子节点k,有 $dp[k][j]$ 种选择,Can not choose the child node;
For the back of the reduction,则表示若 i Node color and target different,You will need to remove only choice i 一个点的情况;

答案即为
$$\sum _{i}dp[i][1]+dp[i][0]-(\sum _{k\in so{n}_i}dp[k][!col[n]])$$
At the back of the subtraction is minus i 为根节点,And select only a subtree of,Here is not in conformity with the question;

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1e9 + 7;
vector<int> rod[300005];
ll col[300005];
ll dp[300005][2];
ll ans;
void dfs(int x, int f)
{
    
    ll tmp1 = 1, tmp0 = 1, sum = 0;
    for (auto y : rod[x])
    {
    
        if (y == f)
            continue;
        dfs(y, x);
        sum += (dp[y][col[x] ^ 1]);
        sum %= M;
        tmp1 *= (1 + dp[y][1]) % M;
        tmp1 %= M;
        tmp0 *= (1 + dp[y][0]) % M;
        tmp0 %= M;
    }
    dp[x][1] = tmp1 - (col[x] != 1) + M;
    dp[x][0] = tmp0 - (col[x] != 0) + M;
    dp[x][1] %= M;
    dp[x][0] %= M;
    ans += dp[x][1] + dp[x][0] - sum + M;
    ans %= M;
}
int main()
{
    
    int n;
    while (cin >> n)
    {
    
        for (int i = 1; i <= n; i++)
            rod[i].clear();
        ans = 0;
        string g;
        cin >> g;
        for (int i = 0; i < n; i++)
        {
    
            col[i + 1] = g[i] - '0';
        }
        for (int i = 1; i < n; i++)
        {
    
            int u, v;
            scanf("%d%d", &u, &v);
            rod[u].push_back(v);
            rod[v].push_back(u);
        }
        dfs(1, 0);
        cout << ans << endl;
    }
}

F A Stack of CDs

计算几何

题意

洛谷原题,Changing the input sequence and output digits can be

思路

For the amount of data,We can for each dish for the covered range,And interval and calculate the covered general;
Pay attention to the plate to be upper containing;

Accumulative surplus length each dish is the answer;

代码

#include <bits/stdc++.h>
using namespace std;
#define double long double
const double eps = 1e-16;
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); }
};
struct Line
{
    
    Point a, v;
    Line(Point x = Point(), Point y = Point()) {
     a = x, v = y; }
};
struct Circle
{
    
    Point o;
    double r;
    Circle(Point x = Point(), double y = 0) {
     o = x, r = y; }
};
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;
}
double distance_to_line(Point p, Line m) {
     return fabs(cross(p - m.a, m.v) / get_length(m.v)); }
pair<Point, Point> line_circle_intersection(Line l, Circle c)
{
    
    Point h = get_line_intersection(l, Line(c.o, Point(-l.v.y, l.v.x)));
    if (sign(distance_to_line(h, l) - c.r) > 0)
        return {
    Point(), Point()};
    Point e = l.v / get_length(l.v);
    double k =
        sqrt(c.r * c.r - fabs(cross(c.o - l.a, l.v)) * fabs(cross(c.o - l.a, l.v)) / dot(l.v, l.v));
    return {
    h - e * k, h + e * k};
}
Circle ccl[1003];
int n;
int circle_relation(Circle p, Circle q)
{
    
    double d = get_length(p.o - q.o), l = fabs(p.r - q.r);
    if (sign(d - p.r - q.r) > 0)
        return 5;
    else if (sign(d - p.r - q.r) == 0)
        return 4;
    else if (sign(d - l) > 0)
        return 3;
    else if (sign(d - l) == 0)
        return 2;
    else
        return 1;
}
pair<Point, Point> circle_circle_intersection(Circle a, Circle b)
{
    
    double d = get_length(a.o - b.o);
    double d1 = a.r * (a.r * a.r + d * d - b.r * b.r) / (2 * a.r * d);
    double h1 = sqrt(a.r * a.r - d1 * d1);
    Point ed = b.o - a.o;
    Point h = a.o + ed / get_length(ed) * d1;
    return {
    h + Point(ed.y, -ed.x) / get_length(ed) * h1,
            h - Point(ed.y, -ed.x) / get_length(ed) * h1};
}
double get_angle(Point a, Point b) {
     return acos(dot(a, b) / get_length(a) / get_length(b)); }
int main()
{
    
    cin >> n;
    for (int i = 0; i < n; i++)
    {
    
        scanf("%Lf%Lf%Lf", &ccl[i].o.x, &ccl[i].o.y, &ccl[i].r);
    }
    vector<pair<double, double>> lim;
    double ans = 0;
    for (int i = 0; i < n; i++)
    {
    
        lim.clear();
        double ers = 0;
        bool zero = 0;
        for (int j = i + 1; j < n; j++)
        {
    
            int tmp = circle_relation(ccl[i], ccl[j]);
            if (tmp == 1 && ccl[i].r < ccl[j].r)
            {
    
                zero = 1;
                break;
            }
            else if (tmp == 3)
            {
    
                auto pii = circle_circle_intersection(ccl[i], ccl[j]);
                Point to = ccl[j].o - ccl[i].o;
                pair<double, double> deg = {
    
                    atan2((pii.first - ccl[i].o).y, (pii.first - ccl[i].o).x),
                    atan2((pii.second - ccl[i].o).y, (pii.second - ccl[i].o).x)};
                if (deg.first > deg.second)
                {
    
                    swap(deg.first, deg.second);
                }
                if (sign(fabs(deg.first - atan2(to.y, to.x)) - PI) >= 0 ||
                    sign(fabs(deg.second - atan2(to.y, to.x)) - PI) >= 0)
                {
    
                    lim.push_back({
    deg.second, PI});
                    lim.push_back({
    -PI, deg.first});
                }
                else
                {
    
                    lim.push_back(deg);
                }
            }
        }
        if (zero)
            continue;
        if (lim.empty())
        {
    
            ers = 0;
        }
        else
        {
    
            sort(lim.begin(), lim.end());
            double st = lim[0].first, ed = lim[0].second;
            for (int i = 1; i < lim.size(); i++)
            {
    
                if (sign(lim[i].first - ed) <= 0)
                {
    
                    ed = max(lim[i].second, ed);
                }
                else
                {
    
                    ers += ed - st;
                    st = lim[i].first, ed = lim[i].second;
                }
            }
            ers += ed - st;
        }
        ans += (2 * PI - ers) * ccl[i].r;
// printf("*%Lf %Lf %d\n", ers, ans, lim.size());
    }
    printf("%.10Lf", ans);
}

G KFC Crazy Thursday

Manacher（马拉车算法）

题意

给定长度为 n 的小写字母串,Respectively for how much k , f, c At the end of the text string back;

思路

As a cart is each character as the center of the longest palindrome string,We only need to be enumerated to some point as the center,All string of radius less than or equal to that point the longest palindrome palindrome string,Determine whether conform to the conditions and counting can be;

The original also worryT,Can actually be a~

代码

#include <bits/stdc++.h>
using namespace std;
const int M = 998244353;
const int maxn = 5e5 + 5;
char s[maxn * 2], str[maxn * 2];
int d[maxn * 2], len;
void getstr()
{
     //重定义字符串
    int k = 0;
    str[k++] = '@'; //开头加个特殊字符防止越界
    for (int i = 0; i < len; i++)
    {
    
        str[k++] = '#';
        str[k++] = s[i];
    }
    str[k++] = '#';
    len = k;
    str[k] = 0; //字符串尾设置为0,防止越界
}
int k, f, c;

int manacher()
{
    
    int mx = 0, id; // mx为最右边,id为中心点
    int maxx = 0;
    for (int i = 0; i < len; i++)
    {
    
        if (i < mx)
            d[i] = min(mx - i + 1, d[2 * id - i]); 
        else
            d[i] = 1; 
        while (str[i + d[i]] == str[i - d[i]])
            d[i]++; 
        if (d[i] + i - 1 > mx)
        {
     
            mx = d[i] + i - 1;
            id = i;                 
            maxx = max(maxx, d[i]); 
        }
    }
    return (maxx - 1);
}

int main()
{
    
    while (cin >> len)
    {
    
        scanf("%s", &s);
        getstr();
        memset(d, 0, sizeof d);
        manacher();
        k = f = c = 0;
        for (int i = 1; i < len; i++)
        {
    
            for (int j = 1; j <= d[i]; j++)
            {
    
                if (str[i - j + 1] == 'k')
                    k++;
                if (str[i - j + 1] == 'f')
                    f++;
                if (str[i - j + 1] == 'c')
                    c++;
            }
        }
        printf("%d %d %d\n", k, f, c);
    }
}

H Cutting Papers

计算几何

题意

给定图形 $|x|+|y|+|x+y|⩽n$ 和 $x^2+y^2⩽n^2/4$ Beg the area;

思路

经过matplotlib绘制,Found that the former shape as follows：


Can directly show area~

代码

Teammates as follows

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

const double PI = acos(-1);

int main() {
    
   double n;
   cin >> n;
    double r = n / 2;
    printf("%.8f\n" , r * r * PI / 2 + 2 * r * r);
}

K Headphones

题意

现有 n-k The headset,Randomly pick a（不是一对）,How many times at least take headphones can make hand logarithmic greater thank;

思路

如果存在解,先考虑最坏情况：
If take out n-k A headset is not right,You will need to get k+1 To meet the question;
The need to take at least n+1 个;

代码

#include <bits/stdc++.h>
using namespace std;
const int M = 998244353;

int main() {
    
   long long n,k;
   while(cin>>n>>k)
   {
    
    if(n-k>=k+1)printf("%lld\n",n+1);
    else printf("-1\n");
   }
}

ed

The difficulty of the gradient is a bit strange