2022牛客多校1补题

题解：A,C,D,G,I,J

A题：Villages: Landlines

题目大意：

转化题意后，便是求给定多个(a,b)形式（包括a，b）的区间，求（min，max）区间里没有被覆盖的区域的长度和。

解题思路：

难度不大，就是需要把题意读懂，能够转化题意。

首先将所有区间合并为不重叠的大区间，具体操作就是按a进行排序，将当前最大right > a的所有小区间与前面的区间合并，当前最大right

随后遍历所有大区间，计算所有大区间的长度，用（min，max）区间长度减去即可得到ans，输出即可

AC代码

#include 
using namespace std;
#define INF 0x3f3f3f3f
#define int long long

const int N = 200010;

vector> merge(vector> &intervals)
{
    if (intervals.size() == 0)
    {
        return {};
    }
    sort(intervals.begin(), intervals.end());
    vector> merged;
    for (int i = 0; i < intervals.size(); ++i)
    {
        int L = intervals[i][0], R = intervals[i][1];
        if (!merged.size() || merged.back()[1] < L)
        {
            merged.push_back({L, R});
        }
        else
        {
            merged.back()[1] = max(merged.back()[1], R);
        }
    }
    return merged;
}

signed main()
{
    int n;
    cin >> n;
    vector> a;
    int minx = INF, maxx = -INF;
    for (int i = 0; i < n; i++)
    {
        int x, r;
        cin >> x >> r;
        minx = min(x - r, minx);
        maxx = max(x + r, maxx);
        a.push_back((vector){x - r, x + r});
    }
    int ans = maxx - minx;
    vector> merged_a = merge(a);
    for (vector p : merged_a)
    {
        ans -= p[1] - p[0];
    }
    cout << ans << endl;
}

C题：Grab the Seat!

题目大意：

就是在一象限，有一块n*m的区域是教室，y轴上(0,m)区域是黑板，有k个人已经坐在教室了，此外有q次更改座位，更改座位后求没有任何视野阻挡的作为还有多少个

解题思路：

可以利用ans数组存放每行，也就是1-m行每行还剩下多少个座位没有被阻挡，方便起见我们将y轴上移一位，也就是对题所给所有y有y新= y - 1，我们知道，被阻挡的区域便是(0，0)点和(0，m)点与所有有人的座位所形成的的射线包括的扇形类型区域。

如这后面的所有区域便是被阻挡的区域

具体来说，我们需要两次遍历。

一次从0-m-1遍历，遍历斜率为正数的那条线，记录在第i次及之前所遇到的最大斜率那条线，因为与y=i所形成的射线只会影响y=i+a(a=0,1……)之后的线，特别的，与y=0所形成的射线只会影响y=0这一行。
另一次类似，可通过镜像反转，复用代码

AC代码

#include 

using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 1e9;
int n, m, k, q, a[N], b[N];
int p[N], ans[N];

signed main()
{
    cin >> n >> m >> k >> q;
    for (int i = 1; i <= k; i++)
        cin >> a[i] >> b[i]; // a表示x坐标，b表示y坐标
    int x, v;
    while (q--) {
        cin >> x;
        cin >> a[x] >> b[x];

        // p[i] 表示第i行坐在最前面的人的x轴坐标 初始相当于每个人都坐在n以外的点，不会对答案产生影响
        for (int i = 0; i < m; i++)
            p[i] = n + 1;
        for (int i = 1; i <= k; i++) // 遍历所有坐人的坐标，记录最左边的列
            p[b[i] - 1] = min(p[b[i] - 1], a[i]); // 所有y轴坐标 - 1，目的是计算斜率只需要和0，0计算即可，非常方便
        for (int i = 0; i < m; i++)
            ans[i] = p[i] - 1; // 记录答案,记录每行最前面的没被挡住的点，是最靠前的人的坐标-1，因为坐人的地方也相当于被挡住了

        int x = n + 1, y = 0; // x,y表示前i行最能挡的人的坐标(斜率最大的坐标)
        for (int i = 0; i < m; i++) { // 遍历每一行，也就是遍历所有y坐标
            int x1 = p[i], y1 = i; // 当前行的最靠前的人为位置 x1，y1
            if (y1 * x >= y * x1)
                x = x1, y = y1; // 判断斜率是否更大，更新x，y
            int temp; // 防止除0
            if (y != 0)
                temp = ceil(x * i * 1.0 / y) - 1; // -1是为了把人坐的地方给去掉，计算当前斜率最大的射线与当前行的交点
            else
                temp = n;
            ans[i] = min(ans[i], temp); // 更新答案
        }

        reverse(p, p + m);
        x = n + 1, y = 0; // 翻转再更新
        for (int i = 0; i < m; i++) {
            int x1 = p[i], y1 = i;
            if (y1 * x >= y * x1)
                x = x1, y = y1;
            int temp;
            if (y != 0)
                temp = ceil(x * i * 1.0 / y) - 1;
            else
                temp = n;
            ans[m - i - 1] = min(ans[m - i - 1], temp); // 更新反转的答案，注意边界
        }
        int sum = 0;
        for (int i = 0; i < m; i++)
            sum += ans[i];
        cout << sum << endl; // 累计答案即可
    }
    return 0;
}

D题：Mocha and Railgun

题目大意：

已知一个圆心在原点的圆，半径为r。给一个Q点(x,y)，求解过Q点的长度为2d的线段投影到圆上所形成的弧长的最大值。

解题思路：

这道题，就一个字，猜，我无法证明，我也没时间证明，猜最优的线段过圆心和Q点即可，然后直接利用几何知识求解即可。

AC代码

import math

t = int(input())
for _ in range(t):
    r = int(input())
    x, y, d = map(int, input().split())
    edd = x * x + y * y
    dd = math.sqrt(edd)
    x1 = dd - d
    x2 = dd + d
    y1 = math.sqrt(r * r - x1 * x1)
    y2 = math.sqrt(r * r - x2 * x2)
    xyd = math.sqrt((x1 - x2)**2 + (y1 - y2)**2)
    sina = xyd * 0.5 / r
    ans = math.asin(sina)
    print(ans * r * 2)

G题：Lexicographical Maximum

题目大意：

很简单，就是给定一个数n，求解1-n中字典序最大的数。

解题思路：

n最大为10^1000000，因此这个数量级排序应该不太行。只需要判断前len-1个数是否为’9’，如果除了最后一个数都是’9’或者len=1直接输出n以外，其他全部输出len-1个’9’即可。

AC代码

#include 

using namespace std;

signed main()
{
    string n;
    cin >> n;
    bool flag = true;
    for (int i = 0; i < n.length()-1; i++) {
        if (n[i] != '9') {
            flag = false;
            break;
        }
    }
    if (n.length() == 1 || flag)
        cout << n << endl;
    else {
        for (int i = 0; i < n.length() - 1; i++)
            cout << '9';
    }
    return 0;
}

I题：Chiitoitsu

题目大意：

有34中牌，每种牌都有4张。起手有13张牌，其中每种类型的牌最多有2张，求起手牌到胡牌期望次数(胡牌被定义为有7个不同的对子牌)。

解题思路：

起手牌不会有超过两张相同的牌，那么在这种情况下，我们将手上的牌分为pair和single两个种类，当抽到一张pair中的牌时，由于这个pair已经存在，所以抽到的牌实际上没有用，直接弃掉；当抽到single中的牌时，两个相同的single就形成了一个pair，这就离目标7个pair更近了，所以这张牌需要保留；当抽到的牌啥也不是时，实际上弃掉此牌一定是一种最优策略（本质上相同牌数的single牌都是等价的，因为以它再来凑的话就相当于把之前某个single丢弃凑另一个single）。这里就需要观察到，在最优策略下，single牌在牌堆中永远有3张，因为我们不会用pair牌换掉single牌，而一旦抽到single就会形成pair。

那么就可以考虑使用动态规划。

定义一个数组为 d p [ i ] [ j ] dp[i][j] dp[i][j]为抽取第 i i i 次牌之后剩余 j j j 张单牌的概率。

d p [ i [ j ] = d p [ i − 1 ] [ j ] ∗ 124 − i − 3 j 124 − i + d p [ i − 1 ] [ j + 2 ] ∗ 3 ∗ ( j + 2 ) 124 − i dp[i[j]=dp[i−1][j]∗frac{124−i−3j}{124−i}+dp[i−1][j+2]∗frac{3∗(j+2)}{124−i} dp[i[j]=dp[i−1][j]∗124−i124−i−3j​+dp[i−1][j+2]∗124−i3∗(j+2)​

前一个代表的是第 i i i 次抽取的牌不是手中单牌（其中一种）一样类型的牌，后一个代表的是抽到的是和手中单牌（其中一种）一样类型的牌。

初始化 d p [ 0 ] [ c n t ] = 1 dp[0][cnt] = 1 dp[0][cnt]=1，代表不抽取牌时剩余任何张单牌的概率都是1。

我们易知 i < = 121 i <= 121 i<=121，因为抽取121次后必定有每种类型的牌都抽取了至少2个。 j < = 13 j <= 13 j<=13，因为初始手牌里面的单牌数量可能有1，3，5，7，9，11，13这几种。

注意因为要取余，所以在运算过程中要使用快速幂一直保持

AC代码

#include 
#define ll long long
using namespace std;
map mp;
map book;
const ll mod = 1e9 + 7;
ll dp[150][16];
ll res[15];

ll ksm(ll a, ll b)
{
    ll res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

void init()
{
    for (int k = 1; k <= 13; k += 2) {
        memset(dp, 0, sizeof dp);
        dp[0][k] = 1;
        for (int i = 1; i <= 121; i++) {
            for (int j = 1; j <= 13; j += 2) {
                dp[i][j] = (dp[i - 1][j] * (124 - i - 3 * j) % mod + dp[i - 1][j + 2] * (3 * j + 6) % mod) % mod * ksm(124 - i, mod - 2) % mod;
            }
        }

        ll ans = 0;
        for (int i = 1; i <= 121; i++) {
            ans = (ans + i * dp[i - 1][1] * 3 % mod * ksm(124 - i, mod - 2) % mod) % mod;
        }
        res[k] = ans;
    }
}

void solve(int id)
{
    string s;
    cin >> s;
    int tot = 0;
    book.clear();
    for (int i = 1; i <= 34; i++)
        mp[i] = 0;
    string tmp;
    for (int i = 0; i < s.size(); i++) {
        tmp += s[i];
        if (i & 1) {
            int k;
            if (!book[tmp])
                book[tmp] = ++tot;
            k = book[tmp];
            mp[k]++;
            tmp = "";
        }
    }

    int cnt = 0;
    for (int i = 1; i <= 34; i++)
        if (mp[i] == 1)
            cnt++;
    cout << "Case #" << id << ": " << res[cnt] << 'n';
}

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
        solve(i);
    return 0;
}

J题：Serval and Essay

题目大意：

就是给了一个有向无环图，包括 n n n个点，其中只有选择一个起点，求解所能到达的所有点的最大值。

具体的，如果要达到一个点 u u u，那么需要到达指向 u u u的所有点 v i v_i vi​。

解题思路：

首先这个题一转换就有点是拓扑排序的感觉，但是当时跟榜，没有写到。题目的题意也有点难以理解，不太会，贴个并查集的解法吧。

#include 

using namespace std;

#define x first
#define y second

typedef pair PII;

const int N = 2e5 + 10;

int fa[N], Size[N]; //维护并查集
int n, m;
int k[N];
set from[N]; // from[i]记录推出i点需要的点
set to[N]; // to[i]记录i点可以推出的点

int find(int u)
{
    //并查集寻根函数
    if (u != fa[u])
        fa[u] = find(fa[u]);
    return fa[u];
}

void Merge(int a, int b)
{
    // b依赖a
    int ha = find(a), hb = find(b);
    if (ha == hb)
        return;
    if (to[ha].size() < to[hb].size())
        swap(ha, hb); //将较少的集合放入大的
    fa[hb] = ha;
    Size[ha] += Size[hb]; //由于此时只要确定了ha就能确定hb，所以所有需要依赖hb的点都可以改为需要ha的点，就是将两者数量合并
    vector tmp; //记录所有可以入度为1的点
    for (auto u : to[hb]) { //遍历所有依赖hb的点，现在这些点都是依赖a的(所有依赖b的点在之前的hb和b的合并过程中已经转为依赖hb，所以这里遍历的是from[hb]
        from[u].erase(hb); //将点u依赖hb的关系消除
        from[u].insert(ha); //加上点u依赖ha(可能这个关系本来就存在，set会自动去重)
        to[ha].insert(u); //记录ha能推出u
        if (from[u].size() == 1) { //记录入度为1的点
            tmp.push_back({ ha, u });
        }
    }

    for (int i = 0; i < tmp.size(); i++) {
        Merge(tmp[i].x, tmp[i].y);
    }
}

int main()
{
    int T;
    cin >> T;
    for (int iu = 1; iu <= T; iu++) {
        cin >> n;
        for (int i = 1; i <= n; i++) { //清空状态记录
            fa[i] = i;
            Size[i] = 1;
            to[i].clear();
            from[i].clear();
        }

        for (int i = 1; i <= n; i++) {
            int k;
            cin >> k;
            for (int j = 0; j < k; j++) {
                int a;
                cin >> a;
                from[i].insert(a); //记录a对i的依赖关系
                to[a].insert(i); //记录i对a的被依赖关系
            }
        }

        for (int i = 1; i <= n; i++) {
            if (from[i].size() == 1) {
                Merge(i, *from[i].begin());
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = max(ans, Size[i]);
        }
        cout << "Case #" << iu << ": " << ans << endl;
    }
    return 0;
}

记录a对i的依赖关系
                to[a].insert(i); //记录i对a的被依赖关系
            }
        }

        for (int i = 1; i <= n; i++) {
            if (from[i].size() == 1) {
                Merge(i, *from[i].begin());
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = max(ans, Size[i]);
        }
        cout << "Case #" << iu << ": " << ans << endl;
    }
    return 0;
}