牛客多校第五场补题记录

A Don't Starve

题意：给定平面上 $nn$ 个点，从原点出发直线前往这些点收集食物，收集完再前往下一个点。每当离开一个有食物的点后该点食物刷新，每次移动距离严格下降。问最多收集到多少食物。$n\le 2\times 10^{3}n\; \backslash leq\; 2\backslash times\; 10^3$。

解法：根据距离作为边权构建完全图，按照边权从大到小排序。记 $f_{i}f\_\{i\}$ 为到达 $ii$ 点时收集到的最大食物数量，则当边距离从大到小考虑时，对于边 $(u,v)(u,v)$，其唯一可行转移为 $f_v\leftarrow \max (f_v,f_u+1)f\_v\; \backslash leftarrow\; \backslash max(f\_v,f\_u\; +1)$，因为此时从原点到达 $vv$ 的路径上边权一定大于等于 $(u,v)(u,v)$ 边权。对于边权相等的一系列边，需要同时处理，因为距离严格相等，不可以互相转移。总时间复杂度 $\mathcal{O}(n^2\log n+n^2)\backslash mathcal\; O(n^2\; \backslash log\; n\; +n^2)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 2000;
const int inf = 0x3f3f3f3f;
int x[N + 5], y[N + 5], f[N + 5], g[N + 5];
struct line
{
    int from, to;
    int dis;
    bool operator<(const line &b)const
    {
        return dis > b.dis;
    }
    line(int _from, int _to, int _dis)
    {
        from = _from;
        to = _to;
        dis = _dis;
    }
};
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n;i++)
        scanf("%d%d", &x[i], &y[i]);
    vector<line> que;
    for (int i = 0; i <= n;i++)
        for (int j = 1; j <= n;j++)
            if (i != j)
                que.emplace_back(i, j, (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
    sort(que.begin(), que.end());
    for (int i = 1; i <= n;i++)
        f[i] = -inf;
    int m = que.size();
    for (int i = 0; i < m;)
    {
        int j = i;
        while (j < m && que[i].dis == que[j].dis)
        {
            g[que[j].to] = -inf;
            j++;
        }
        for (int k = i; k < j;k++)
            g[que[k].to] = max(g[que[k].to], f[que[k].from] + 1);
        for (int k = i; k < j;k++)
            f[que[k].to] = max(f[que[k].to], g[que[k].to]);
        i = j;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, f[i]);
    printf("%d", ans);
    return 0;
}

C Bit Transmission

题意：有一个长度为 $nn$ 的 01 串，进行 $3n3n$ 次询问，得到位置 $xx$ 是否为 $11$ 的回答。若回答机器只会回答错误一次，问能否确定这一字符串。$n\le 1\times 10^{5}n\; \backslash leq\; 1\backslash times\; 10^5$。

解法：对于每一位单独考虑，记第 $ii$ 位答案为 $00$ 次数为 $c_{0}c\_0$，$11$ 次数为 $c_{1}c\_1$。

1. $c_0=c_1=0c\_0=c\_1=0$。则该位无法判断。
2. $c_0,c_1\ge 2c\_0,c\_1\; \backslash geq\; 2$。说谎次数必然超过一次，无解。
3. $c_{0}c\_0$ 与 $c_{1}c\_1$ 中有一个为 $11$ 另一个为 $00$。根据有无说谎判断，无说谎则无解。
4. $c_0,c_{1}c\_0,c\_1$ 中有一个大于等于 $22$ 另一位为 $00$。必然没说谎。
5. $c_0,c_{1}c\_0,c\_1$ 中有一个大于等于 $22$，另一个为 $11$。必然说谎。

#include <bits/stdc++.h>
using namespace std;
const int N = 300000;
int cnt[N + 5][2];
char buf[10];
char s[N + 5];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1, x; i <= 3 * n;i++)
    {
        scanf("%d%s", &x, buf);
        if (x < n)
            cnt[x][buf[0] == 'Y']++;
    }
    bool flag = 1, once = 0;
    int lie = -1;
    for (int i = 0; i < n;i++)
    {
        if(!cnt[i][0] && !cnt[i][1])
        {
            printf("-1");
            return 0;
        }
        if ((cnt[i][0] >= 2 && cnt[i][1] >= 2) || (cnt[i][0] == 1 && cnt[i][1] == 1))
        {
            printf("-1");
            return 0;
        }
        if(cnt[i][0] == 0 && cnt[i][1])
        {
            once |= cnt[i][1] == 1;
            s[i] = '1';
        }
        else if(cnt[i][1] == 0 && cnt[i][0])
        {
            once |= cnt[i][0] == 1;
            s[i] = '0';
        }
        else
        {
            if (lie != -1)
            {
                printf("-1");
                return 0;
            }
            lie = i;
            if(cnt[i][0] >= 2)
                s[i] = '0';
            else
                s[i] = '1';
        }
    }
    if (lie == -1 && once)
        printf("-1");
    else
        printf("%s", s);
    return 0;
}

D Birds in the tree

题意：给定 $nn$ 个节点的树，树上每个点为 $0,10,1$ 两种颜色之一。问树上连通块满足该连通块构成的生成子图中度为 $11$ 节点均同色的方案数。$n\le 3\times 10^{5}n\; \backslash leq\; 3\backslash times\; 10^5$。

解法：考虑 $f_{u,0\mathrm{/}1}f\_\{u,0/1\}$ 表示 $uu$ 子树下，必然含有 $uu$ 在连通块内，连通块叶子颜色为 $0\mathrm{/}10/1$ 的连通块个数。设 $uu$ 的颜色为 $00$（$11$ 同理），则有

其中 $f_{u,0}f\_\{u,0\}$ 的含义为：每个子树中连通块叶子颜色为 $00$ 的方案必然均可选，并且可以不选；

$f_{u,1}f\_\{u,1\}$ 则必然要求在大于等于两个子树内均有选择 $11$ 作为叶子颜色的，使得 $uu$ 不作为叶子节点出现，因而减去仅在一个子树内任取的方案。并且不能以 $uu$ 一个单节点作为叶子颜色为 $11$ 的情况出现。最后答案为 ${\displaystyle \sum _{i=1}^n{f}_{i,0}+f_{i,1}}\backslash displaystyle\; \backslash sum\_\{i=1\}^n\; f\_\{i,0\}+f\_\{i,1\}$。

#include <bits/stdc++.h>
using namespace std;
const int N = 300000;
const long long mod = 1000000007;
long long ans;
struct line
{
    int from;
    int to;
    int next;
};
struct line que[2 * N + 5];
int cnt, headers[N + 5];
void add(int from, int to)
{
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
int col[N + 5];
char s[N + 5];
long long f[N + 5][2];
void dfs(int place, int father)
{
    long long sum = 0;
    f[place][0] = f[place][1] = 1;
    for (int i = headers[place]; i; i = que[i].next)
        if (que[i].to != father)
        {
            dfs(que[i].to, place);
            f[place][0] = f[place][0] * (1 + f[que[i].to][0]) % mod;
            f[place][1] = f[place][1] * (1 + f[que[i].to][1]) % mod;
            sum = (sum + f[que[i].to][col[place] ^ 1]) % mod;
        }
    f[place][col[place] ^ 1]--;
    ans = (ans + f[place][0] + f[place][1] - sum + mod) % mod;
}
int main()
{
    int n;
    scanf("%d%s", &n, s + 1);
    for (int i = 1; i <= n;i++)
        col[i] = s[i] == '1';
    for (int i = 1, u, v; i < n;i++)
    {
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dfs(1, 1);
    printf("%lld", ans);
    return 0;
}

E Fraction Game

题意：给定 $n\times nn\; \backslash times\; n$ 的三角形数组，问 $k\times kk\backslash times\; k$ 的三角形区域内最大值的和。$1\le k\le n\le 1\times 10^{3}1\backslash leq\; k\; \backslash leq\; n\; \backslash leq\; 1\backslash times\; 10^3$。

解法：考虑倍增。朴素的倍增为二倍增，即覆盖区域边长扩大两倍。但是容易发现，如果只是朴素的转移，即 $f_{i,j}\leftarrow \max (f_{i-k,j},f_{i,j},f_{i,j+k})f\_\{i,j\}\; \backslash leftarrow\; \backslash max(f\_\{i-k,j\},f\_\{i,j\},f\_\{i,j+k\})$，这样会有一个倒三角区域无法覆盖。此处有两种解决方案：

1. 扩大转移范围。想要完全覆盖，可以改写方程为：

   $f_{i,j}=\max \left(f_{i-k,j}\underset{l=0}{\overset{k}{}}{f}_{i+l,j}\right)f\_\{i,j\}=\backslash max\backslash left(f\_\{i-k,j\}\backslash max\_\{l=0\}^k\; f\_\{i+l,j\}\backslash right)$

   这样就可以实现完全覆盖，但是这样每次转移量是 $O(k)O(k)$ 的。注意到这样的转移每次长度是固定的，因而考虑滑动窗口去解决，均摊 $nn$ 次转移项仅需 $O(n)O(n)$ 次。

2. 修改倍增大小。考虑可以完全覆盖的最大倍数：下图中三个大三角形完全相似，因而容易计算出最外侧的三角形与三个大三角形的相似比为 ${\displaystyle \frac{3}{2}}\backslash dfrac\{3\}\{2\}$，因而覆盖边长为 $xx$ 扩张到 $\lceil {\displaystyle \frac{3x}{2}}\rceil \backslash left\; \backslash lceil\; \backslash dfrac\{3x\}\{2\}\backslash right\; \backslash rceil$。

对于恰好为 $kk$ 的转移只需要单独做一次扩张即可。总复杂度 $\mathcal{O}(n^2\log n)\backslash mathcal\; O(n^2\; \backslash log\; n)$。

// 1.5 倍增
#include <bits/stdc++.h>
#define fp(i, a, b) for (int i = a, i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = (b) - 1; i > i##_; --i)

using namespace std;
const int N = 1005;
using ll = int64_t;
struct Frac {
    ll x, y;
    Frac(ll a = 0, ll b = 1) { y = __gcd(a, b), x = a / y, y = b / y; }
    bool operator<(const Frac a) const { return x * a.y < y * a.x; }
    Frac operator+(const Frac a) const { return Frac(x * a.y + y * a.x, y * a.y); }
} f[N][N];
int n, k, pw[20], Log[N];
void Solve() {
    scanf("%d%d", &n, &k);
    Frac ans;
    fp(i, 1, n) fp(j, 1, i)
        scanf("%lld/%lld", &f[i][j].x, &f[i][j].y);
    fp(t, 1, Log[k]) {
        int pk = pw[t] - pw[t - 1];
        fp(i, 1, n - pk) fp(j, 1, i)
            f[i][j] = max({f[i][j], f[i + pk][j], f[i + pk][j + pk]});
    }
    int pk = pw[Log[k]];
    fp(i, 1, n - k + 1) fp(j, 1, i)
        ans = ans + max({f[i][j], f[i + k - pk][j + k - pk], f[i + k - pk][j]});
    printf("%lld/%lld\n", ans.x, ans.y);
}
int main() {
    pw[0] = 1;
    fp(i, 1, 15) Log[pw[i] = (3 * pw[i - 1] + 1) >> 1] = i;
    fp(i, 2, N - 1) Log[i] = max(Log[i], Log[i - 1]);
    int t = 1;
    while (t--) Solve();
    return 0;
}

//二倍增+单调队列
#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
struct Frac {
    long long x, y;
    Frac(long long a = 0, long long b = 1) { y = __gcd(a, b), x = a / y, y = b / y; }
    bool operator==(const Frac a) const { return x * a.y == y * a.x; }
    bool operator<(const Frac a) const { return x * a.y < y * a.x; }
    Frac operator+(const Frac a) const { return Frac(x * a.y + y * a.x, y * a.y); }
    bool operator<=(const Frac a) const { return *this < a || *this == a; }
    bool operator>(const Frac a) const { return x * a.y > y * a.x; }
    bool operator>=(const Frac a) const { return *this > a || *this == a; }
} f[N + 5][N + 5];
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= i;j++)
            scanf("%lld/%lld", &f[i][j].x, &f[i][j].y);
    int p = 2;
    for (; p < k; p *= 2)
        for (int x = 1; x <= n - p + 1; x++)
        {
            deque<int> q;
            for (int i = 1; i <= p / 2; i++)
            {
                while (!q.empty() && f[x + p / 2][i] >= f[x + p / 2][q.back()])
                    q.pop_back();
                q.push_back(i);
			}
            for (int y = 1; y <= x; y++)
            {
                while (!q.empty() && q.front() < y)
                    q.pop_front();
                while (!q.empty() && f[x + p / 2][y + p / 2] >= f[x + p / 2][q.back()])
                    q.pop_back();
                q.push_back(y + p / 2);
                f[x][y] = max(f[x][y], f[x + p / 2][q.front()]);
			}
		}
    p /= 2;
    Frac ans;
    for (int x = 1; x <= n - k + 1; x++)
    {
        deque<int> q;
        for (int i = 1; i <= k - p; i++)
        {
            while (!q.empty() && f[x + k - p][i] >= f[x + k - p][q.back()])
                q.pop_back();
            q.push_back(i);
		}
        for (int y = 1; y <= x; y++)
        {
            while (!q.empty() && q.front() < y)
                q.pop_front();
            while (!q.empty() && f[x + k - p][y + k - p] >= f[x + k - p][q.back()])
                q.pop_back();
            q.push_back(y + k - p);
            // printf("X:%d Y:%d ANS:%lld\n", x, y, max(f[x][y], f[x + k - p][q.front()]));
            ans = ans + max(f[x][y], f[x + k - p][q.front()]);
        }
	}
    printf("%lld/%lld", ans.x, ans.y);
    return 0;
}

F A Stack of CDs

题意：给定平面 $nn$ 个圆，后面的圆会覆盖遮挡前面的圆。问这些圆从上面能看到的周长。$n\le 1\times 10^{3}n\; \backslash leq\; 1\backslash times\; 10^3$。

解法：考虑对于第 $ii$ 个圆能看到的周长，只由 $j(j>i)j(j>i)$ 的圆决定。对于一对圆 $(i,j)(i,j)$，若 $ii$ 圆被完全覆盖则看不到，相离则没有影响，否则考虑相交的情况。

记两圆距离为 $dd$，则 $\beta =\mathrm{\angle }A{O}_i{O}_j\backslash beta=\backslash angle\; AO\_iO\_j$ 由余弦定理得到：$\cos \mathrm{\angle }A{O}_i{O}_j={\displaystyle \frac{r_i^2+d^2-r_j^2}{2d{r}_i}}\backslash cos\; \backslash angle\; AO\_iO\_j=\backslash dfrac\{r\_i^2+d^2-r\_j^2\}\{2dr\_i\}$。同时计算 $O_i{O}_{j}O\_iO\_j$ 的极角 $\alpha \backslash alpha$，则遮挡角度范围为 $[\alpha -\beta ,\alpha +\beta ][\backslash alpha-\backslash beta,\backslash alpha+\backslash beta]$。注意将其化到 $[-\pi ,\pi ][-\backslash pi,\backslash pi]$ 的范围即可。剩下的就是对于每个圆的遮挡部分进行线段合并再求和，与第一场 A 题完全相同。

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
struct circle
{
    double x, y;
    double r;
    vector<pair<double, double>> ban;
};
int main()
{
    int n;
    scanf("%d", &n);
    vector<circle> que(n);
    for (int i = 0; i < n;i++)
        scanf("%lf%lf%lf", &que[i].x, &que[i].y, &que[i].r);
    for (int i = 0; i < n;i++)
        for (int j = i + 1; j < n;j++)
        {
            double r1 = que[i].r, r2 = que[j].r, x1 = que[i].x, x2 = que[j].x, y1 = que[i].y, y2 = que[j].y;
            double dis = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
            if (dis <= r1 + r2 && abs(r1 - r2) <= dis)
            {
                double cen = atan2(y2 - y1, x2 - x1);
                double ang = acos((dis * dis + r1 * r1 - r2 * r2) / (2 * dis * r1));
                double low = cen - ang, high = cen + ang;
                if (cen - ang < -pi)
                {
                    que[i].ban.emplace_back(cen - ang + 2 * pi, pi);
                    low = -pi;
                }
                if(cen + ang > pi)
                {
                    que[i].ban.emplace_back(-pi, cen + ang - 2 * pi);
                    high = pi;
                }
                que[i].ban.emplace_back(low, high);
            }
            else if(dis < abs(r1 - r2) && r1 <= r2)
                que[i].ban.emplace_back(-pi, pi);
        }
    double ans = 0;
    for (auto &cir : que)
    {
        sort(cir.ban.begin(), cir.ban.end());
        if(cir.ban.empty())
        {
            ans += cir.r * 2 * pi;
            continue;
        }
        int m = cir.ban.size();
        double len = 0;
        for (int i = 0; i < m;)
        {
            int j = i;
            double nowr = cir.ban[i].second;
            while (j < m && cir.ban[j].first <= nowr)
            {
                nowr = max(nowr, cir.ban[j].second);
                j++;
            }
            len += nowr - cir.ban[i].first;
            assert(i < j);
            i = j;
        }
        ans += (2 * pi - len) * cir.r;
    }
    printf("%.10lf", ans);
    return 0;
}

I Board Game

题意：$nn$ 个士兵要分为 $mm$ 组，每次每一个活着的士兵可以对敌人造成 $11$ 点伤害，敌人会选择一组杀掉至多 $kk$ 个士兵。当士兵死完后游戏结束，敌人以最优打法打，问最大造成的伤害。$n\le 1\times 10^{9}n\; \backslash leq\; 1\backslash times\; 10^9$，$m,k\le 1\times 10^{7}m,k\; \backslash leq\; 1\backslash times\; 10^7$。

解法：敌人的最优解永远都是挑最多的一组，能杀多少杀多少，因而当两组士兵人数均不足 $kk$ 人时，若人数为 $x_1,x_{2}x\_1,x\_2$，则最优解一定是 $x_1=x_{2}x\_1=x\_2$ 或 $x_1=x_2+1x\_1=x\_2+1$。

首先人数超过 $2mk2mk$ 人是没有意义的：每组多加 $kk$ 人只会拖延敌人 $mm$ 轮进攻。因而首先将这部分人抹去，仅考虑 $n^{\mathrm{\prime }}=n-(\lfloor {\displaystyle \frac{n}{mk}}\rfloor -1)mkn\text{'}=n-\backslash left(\backslash left\; \backslash lfloor\; \backslash dfrac\{n\}\{mk\}\backslash right\; \backslash rfloor-1\backslash right)mk$ 人。考虑接下来的这些人中有多少组会超过 $kk$ 人，假设有 $ii$ 组，则剩余的 $n^{\mathrm{\prime }}-kin\text{'}-ki$ 人一定是均匀分配——根据刚刚的推论，当每一组超过 $kk$ 人的都死了，剩下的一定是均匀分配。因而只需要枚举这个 $ii$ 即可。时间复杂度 $\mathcal{O}(m)\backslash mathcal\; O(m)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 3;
long long n, m, k, lim, ans, Max;
long long js(long long n)
{
    long long x = n / m, y = n - m * x, z = m - y;
    return x * z * (z + 1) / 2 + (x + 1) * y * (y + 1) / 2 + y * z * x;
}
int main()
{
    scanf("%lld%lld%lld%lld", &n, &m, &k, &lim);
    if (n < k * m)
    {
        ans = js(n);
        if (ans >= lim)
            printf("YES %lld", ans);
        else
            printf("NO");
        return 0;
    }
    long long tu = m * k, cnt = n / tu;
    n %= tu;
    n += k * m, --cnt;
    ans = k * (cnt * m) * (cnt * m + 1) >> 1;
    ans += n * cnt * m;
    for (int i = 1; i <= m; ++i)
    {
        long long res = n - i * k, now = 0;
        if (res >= m * k || res < 0)
            continue;
        now += js(res);
        now += k * i * (i + 1) / 2;
        now += i * res;
        Max = max(Max, now);
    }
    ans += Max;
    if (ans >= lim)
        printf("YES %lld", ans);
    else
        printf("NO");
    return 0;
}