2022牛客暑期多校训练营5（BCDFGHK）

题集链接；

B Watches

二分

题意

手表店有 n 块手表出售，第 i 个手表售价 $a_i$ 。若购买 k 个手表，那么第 i 个手表需要花费 $a_i+ki$ 元。现有 m 元，求最多可购买多少块手表；

思路

我们考虑到每个手表的花费与购买总数有关，不方便直接贪心处理，我们便选择二分出 k 后，按照实际花费进行排序并贪心；

代码

队友代码如下

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

C Bit Transmission

题意

机器人有一长度为 n 的字符串，现在向机器人询问 3n 次某位是否为 1 ，但是在所有询问中，机器人会返回最多一个错误。对于机器人的回答，若存在唯一的字符串则输出，否则返回 -1 ；

思路

首先排除一些明显无唯一答案的情况，比如某一位没有被询问过；

由于是否有错未知，我们需要首先定位错误的发生，对于某被询问大于两次的位，若其结果出现一次不同，则可以断定错误发生在此处；

若无法定位错误，除所有位均被询问大于两次且答案相同外，其余情况均无唯一原串；

代码

队友代码如下

#include 
#include 
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)//没有问到
            {
                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)//同一位上至少两个错误
                    {
                        f = false;
                        break;
                    }
                    if (cnt == 2)//多个错误
                    {
                        f = false;
                        break;
                    }
                }
            }
        }
        if (f)
        {
            if (cnt == 0)//若无法定位错误
            {
                for (int i = 0; i < n; i++)
                {
                    if (a[i].first == 1 || a[i].second == 1)//无法确定结果真实性
                    {
                        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;
}
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

D Birds in the tree

树状DP

题意

给出一个 n 个节点的树，每个节点有颜色 0 或 1 ，求其有多少连通子图，满足度数为 1 的节点颜色相同；

思路

构造状态表示：$dp[i][j]$ 为以节点 i 为根的子树中，有多少连通子图，度数为 1 的节点（若 i 不是唯一一个则不考虑 i ）颜色为 j；
推导状态转移方程：
$$dp[i][j]=\prod _{k\in so{n}_i}(1+dp[k][j])-[col[i]!=j]$$
前面的连乘式显然为乘法计数原理，对于每一个子节点k，有 $dp[k][j]$ 种选择，还可以不选该子节点；
对于后面的减数，则表示若 i 节点颜色与目标相异，则需要去除仅选择 i 一个点的情况；

答案即为
$$\sum _{i}dp[i][1]+dp[i][0]-(\sum _{k\in so{n}_i}dp[k][!col[n]])$$
后面的减法是减去以 i 为根节点，并且仅选择了一个子树的情况，此处不符合题意；

代码

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

F A Stack of CDs

计算几何

题意

洛谷原题，更改输入顺序和输出位数即可

思路

对于这个数据量，我们可以对每一个盘寻找其被覆盖的区间，并进行区间和并算出被覆盖总长；
注意盘被上层内含的情况；

累加每个盘的剩余总长即是答案；

代码

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

G KFC Crazy Thursday

Manacher（马拉车算法）

题意

给定长度为 n 的小写字母串，分别求有多少以 k , f, c 结尾的回文子串；

思路

由于马拉车求的是以每个字符为中心的最长回文串，我们只需要枚举以某点为中心，所有小于等于该点最长回文串半径的回文串，判断是否符合条件并计数即可；

最初还担心T，实际上可以过~

代码

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

H Cutting Papers

计算几何

题意

给定图形 $|x|+|y|+|x+y|⩽n$ 和 $x^2+y^2⩽n^2/4$ 求两者交面积；

思路

经过matplotlib绘制，发现前者形状如下：


便可以直接表示出面积~

代码

队友代码如下

#include 
#include 
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);
}
1
2
3
4
5
6
7
8
9
10
11
12

K Headphones

题意

现有 n-k 对耳机，每次随机拿一个（不是一对），求最少拿多少次能使手中耳机对数大于k；

思路

如果存在解，先考虑最坏情况：
若先拿出的 n-k 个耳机都是不成对的，那么还需要再拿 k+1 个才能满足题意；
即至少需要拿 n+1 个；

代码

#include 
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");
   }
}
1
2
3
4
5
6
7
8
9
10
11
12

ed

这场的难度梯度有点怪