2023牛客寒假基础集训营2

题解 2023牛客寒假

题解

发布日期: 2023-11-29

2023牛客寒假算法基础集训营2

链接

A Tokitsukaze and a+b=n (easy)

A

—— 简单

题意

给定一个整数 n，两个区间$[L_1,R_1]$，$[L_2,R_2]$。现在想知道从两个区间内分别取一个数 a 和 b，使得 a + b = n，问有多少种不同的取法。

解题思路

我们让第一个区间取值为 a，那么第二个区间取值就为 n - a，然后取两个区间的交集即可。

A与B的区别在于 A的数据范围小，可以暴力

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;

void solve()    
{
    int n, l1, r1, l2, r2;
    cin >> n >> l1 >> r1 >> l2 >> r2;

    int x = n - l1, y = n - r1;

    int l = max(l2, y), r = min(r2, x);

    cout << max(r - l + 1, 0) << endl;
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin >> t; while (t -- )
    solve();

    return 0;
}

B Tokitsukaze and a+b=n (medium)

B

—— 简单

—— 推式子

题意

同 A

解题思路

同 A

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;

void solve()    
{
    int n, l1, r1, l2, r2;
    cin >> n >> l1 >> r1 >> l2 >> r2;

    int x = n - l1, y = n - r1;

    int l = max(l2, y), r = min(r2, x);

    cout << max(r - l + 1, 0) << endl;
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin >> t; while (t -- )
    solve();

    return 0;
}

C Tokitsukaze and a+b=n (hard)

C

—— 中等

—— 差分，算贡献

题意

从上一题的基础上进行了修改。两个区间变成了m 个区间，i，j，a，b 有一个数不同，视为不同的选法。

解题思路

可以利用差分来找到每个数出现的次数，也就是每个数的贡献。但可能存在这样的情况：同一个区间里的两个数相加，显然这是不被允许的。所以我们需要一步去重的操作。

写的时候被去重给拦住了，唉，唉唉。

其实就是根据 B 的写法，从自己区间中找一个数 a ，然后在从自己的区间内找出 n - a的数，如果存在这样的数，就需要去重，就是去掉交集的部分。(看来写的还是太少了，输输输)

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long ll;
typedef pair<int, int> PII;

const long long N = 1e6 + 10, mod = 998244353;

int n, m;
ll a[N];

void solve()    
{
    cin >> n >> m;

    ll sum = 0;
    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        cin >> l >> r;
        a[l] ++ , a[r + 1] -- ;
        int a = n - r, b = n - l;
        //如果有相交的地方，就需要去重
        if (!(b < l || a > r)) sum = sum - (min(r, b) - max(l, a) + 1);
    }

    //差分后取前缀和
    for (int i = 1; i <= n; i ++ ) a[i] += a[i - 1];

    //然后加上一般情况
    for (int i = 1; i < n; i ++ )
    {
        sum += a[i] * a[n - i];
    }

    cout << sum % mod;

}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    //int t; cin >> t; while (t -- )
    solve();

    return 0;
}

D Tokitsukaze and Energy Tree

D

—— 偏简单

—— 树DFS

题意

给定一个有 n 个节点的能量树，根为 1。先给定每个节点的父节点，然后给定 n 个能量球，并给出每个能量球的能量 v 。现在把 n 个能量球放在树的每个节点上，使每个节点恰好有一个能量球。自下而上，每个节点都能额外获得子节点的能量(可向上累加)。问最大的总能量为多少。

解题思路

其实不难想到，既然子节点的能量可以向上传递，那么只要保证越深的节点能量越大，就可以使得总能量越大。此时，我们只需要求出每个节点的深度就可以，因为深度就是一个节点的能量的使用次数。(初始深度为 1)

第一次做这样的题，有思路，甚至非常清晰，但就是想不出如何去解决。不过现在学到了，或许还不晚？大概。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 2e5 + 10;

int n, m; 
int v[N];
vector<int> f[N];
int d[N];

//更新节点深度
void dfs(int u)
{
    for (int v : f[u])
    {
        d[v] = d[u] + 1;
        dfs(v);
    }
}

void solve()    
{
    cin >> n;
    //从节点2开始，给出父节点(1没有父节点)
    for (int i = 2; i <= n; i ++ )
    {
        int x;
        cin >> x;
        f[x].pb(i);     
    }

    //能量球的能量
    for (int i = 1; i <= n; i ++ ) cin >> v[i];
    sort(v + 1, v + n + 1);

    d[1] = 1;
    dfs(1);

    //求和
    ll sum = 0;
    for (int i = 1; i <= n; i ++ ) sum += 1ll * d[i] * v[i];

    cout << sum;
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    //int t; cin >> t; while (t -- )
    solve();

    return 0;
}

E Tokitsukaze and Function

E

—— 偏难

—— 数学，均值不等式，二分

题意

给定一个函数 $f(x)= [\frac{n}{x}]+x-1$ ，现在想在一个区间$[L,R]$ 内找一个最小的整数 t ，使得函数$f(t)$ 最小。

解题思路

题意很简单，甚至第一眼会感觉题也很简单，然后上手，直接寄 (我好像上手都没上手来着)。我是数学低手。唉唉。

然后经过一顿数学的分析，就是取极值什么的。找到了最小值在$\sqrt{x}$ 附近，但并不确定在哪里。所以我们就需要在 $f(l),f(r),f(\lfloor \sqrt{x} \rfloor) f(\lceil \sqrt{x} \rceil)$ 四个数中找一个最小值，作为要找的区间的右端点。新的区间就是$[L,new]$ 。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10;

ll n, l, r, mid;
//函数计算
ll f(ll x)
{
    return n / x + x - 1;
}

void solve()    
{
    cin >> n >> l >> r;

    //从上取整f(sqrt(n))，下取整f(sqrt(n))，f(l), f(r)四个数中取一个最小值，f(x)中的x即是二分的右端点
    vector<pair<ll,ll>> a;
    ll m = sqrt(n);
    if (m + 1 >= l && m + 1 <= r) a.pb({f(m + 1), m + 1});
    if (m >= l && m <= r) a.pb({f(m), m});
    a.pb({f(l), l});
    a.pb({f(r), r});

    sort(a.begin(), a.end());
    r = a[0].second;

    //在那个可能最小值的范围中去二分，找到最小值
    while (l < r)
    {
        mid = l + r >> 1;
        if (f(mid) <= a[0].first) r = mid;
        else l = mid + 1;
    }

    cout << l << endl;
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin >> t; while (t -- )
    solve();

    return 0;
}

F Tokitsukaze and Gold Coins (easy)

F

—— 偏难？

—— BFS

题意

给定一个 n * 3的迷宫，起点是$(1, 1)$，终点是 $(n, 3)$，只能向下或者向右走。每个格子(除了起点)都有一个金币，有些格子有怪物不能走。走到终点后，可以多次回到起点重新走。问能获得的最大金币是多少。

解题思路

第一眼以为就一个简单的BFS嘛，然后样例测试，寄。因为只能向下或者向右走，也就是不能走回头路。所以单纯暴搜肯定是不行的。我感觉很妙的方法(佬都说很简单)：终点起点各自BFS一下，两边都能到的地方，就是可以拿到金币的格子了。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 5e5 + 10;

int n, k; 
int g[N][5], vis1[N][5], vis2[N][5];

queue<PII> q;
void bfs()
{
    //从起点出发
    q.push({0, 0});
    while (!q.empty())
    {
        auto t = q.front();
        int x = t.first, y = t.second;
        q.pop();
        if (x >= n || y >= 3 || vis1[x][y] || g[x][y]) continue;
        vis1[x][y] = 1;
        q.push({x + 1, y});
        q.push({x, y + 1});
    }

    //从终点出发
    q.push({n - 1, 2});
    while (!q.empty())
    {
        auto t = q.front();
        int x = t.first, y = t.second;
        q.pop();
        if (x < 0 || y < 0 || vis2[x][y] || g[x][y]) continue;
        vis2[x][y] = 1;
        q.push({x - 1, y});
        q.push({x, y - 1}); 
    }
}

void solve()    
{
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < 3; j ++ ) 
            g[i][j] = vis1[i][j] = vis2[i][j] = 0;

    cin >> n >> k;

    //初始化怪物
    while (k -- )
    {
        int x, y;
        cin >> x >> y;
        g[x - 1][y - 1] ^= 1;
    }

    bfs();
    //起点没有金币
    vis1[0][0] = 0;

    //如果两边都能到达，那就是能到达。
    int res = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < 3; j ++ )
            if (vis1[i][j] && vis2[i][j]) res ++ ;

    cout << res << endl;
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin >> t; while (t -- )
    solve();

    return 0;
}

G Tokitsukaze and Gold Coins (hard)

G

—— 难

—— 模拟线段树/树状数组/set

说是个大模拟。不会，不懂，逃

H Tokitsukaze and K-Sequence

H

—— 中等

—— 思维，单独考虑算贡献

题意

给定一个长度为 n 的序列 a，现在想把这个序列分成 k 个非空子序列。定义序列的值为：这个序列中只出现一次的数字的个数。对于每一个 k = 1 ~ n，求出子序列值的最大是多少。

解题思路

感觉我的想法也可以。开 map 记录每个数的初始个数，每经过一层，我们就把每一个数字在上一层放一个，就能保证最大值，然后剩下的都塞到当前层。这样只需要一直更新就可以，然后根据层数，和每个数出现的个数，及时删除数即可。

写的时候不会写如何删除容器中的数，然后当时就没写出了。唉唉。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10;

int n, m; 

void solve()    
{
    cin >> n;
    map<int,int> mp;
    for (int i = 1; i <= n; i ++ )
    {
        int x; cin >> x;
        mp[x] ++ ;
    }

    int cnt = 0;
    //更新到第i层
    for (int i = 1; i <= n; i ++ )
    {
        //遍历map
        for (auto t = mp.begin(); t != mp.end();)
        {
            //比如到了第3层，这个数只有3个，那么就要删去这个数，然后贡献+1
            if (t->second == i) 
            {
                cnt ++ ;
                t = mp.erase(t);
            }
            //否则，就向下继续遍历
            else t ++ ;
        }
        //先输出当前总和
        cout << cnt << endl;
        //该到下一层了，每个数在这一层留下一个，也就是每一个数贡献+1
        cnt += mp.size();
    }
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin >> t; while (t -- )
    solve();

    return 0;
}

I Tokitsukaze and Musynx

I

—— 偏难

离散化？

题意

给定 n 个音符，每个音符根据区间有一个判定分 x 。区间分别为：$(-\infty,a),[a,b),[b,c),[c,d],(d,+\infty)$ ，每个区间有一个判定分，然后可以使用一个整数来修正游戏的所有判定分：$x_i=x_i+h(1 \leq i \leq n)$ ，h可以为任意整数。

解题思路

数的范围较大，暴力枚举肯定是要挂的。但我们可以观察到，总的变化其实并不多，所以想到离散化？但又感觉不太像。

正解为：将所有的数减去一个很大的值，整体移动到最左的区间。然后根据每一个让判定分变化的 h ，我们去枚举一遍。因为总的变化不多，所以是不会超时的。

代码

//类似离散化？总变化并不多，但因为数的范围大，所以不能暴力枚举。
//只需要记录每个数的区间变化后的对应的值即可
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 2e5 + 10;

int n, m; 
ll x[N];
int abcd[5];
int v[5];

void solve()    
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> x[i];
        x[i] -= 3e9;
    }
    for (int i = 1; i <= 4; i ++ ) cin >> abcd[i];
    for (int i = 1; i <= 5; i ++ ) cin >> v[i];

    //左为变化的值，右边为变动的区间
    map<ll,vector<int>> mp;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= 4; j ++ )
        {

            mp[abcd[j] - x[i] + (j == 4)].pb(j + 1);
        }
    }

    //res为当前总值
    ll res = 1ll * v[1] * n;
    //ans存储最大值
    ll ans = res;
    //遍历每一个变化的值
    for (auto t : mp)
    {
        //遍历每一个变化的区间
        for (auto tt : t.second)
        {
            res -= v[tt - 1];
            res += v[tt];
        }
        ans = max(ans, res);
    }
    cout << ans << endl;
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin >> t; while (t -- )
    solve();

    return 0;
}

J Tokitsukaze and Sum of MxAb

J

—— 简单

—— 思维

题意

给定一个长度为 n 的序列 a。定义：$MxAb(i,j)=max(\vert a_i-a_j \vert , \vert a_i+a_j \vert)$ 。现在要求出对于所有的 i, j , MxAb(i, j) 的和为多少。

解题思路

我们先把序列中的所有数取一遍绝对值，这样公式就变成了$MxAb(i,j)=a_i+a_j$ 。那么对于总和而言，每个数出现的次数就是固定的了，也就是 2n 次。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;

void solve()    
{
    map<int,int> mp;
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int x;
        cin >> x;
        mp[abs(x)] ++ ;
    }

    ll sum = 0;
    for (auto t = mp.begin(); t != mp.end(); t ++ )
    {
        sum = sum + 1ll * 2 * n * t->second * t->first;
    }
    cout << sum << endl;
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin >> t; while (t -- )
    solve();

    return 0;
}

K Tokitsukaze and Synthesis and Traits

K

—— 偏难

—— 图论

题意

总结下来，就是给定 n 个点，m 条边。q 次询问，每次询问 k 个点中有多少条边。

解题思路

不是很懂根号分治，所以选择更巧妙地办法。

因为初始是无向图，所以单纯枚举暴力肯定是不可以的。于是，巧妙地方法就来了：将无向图，连接成有向图。度小的点连向度大的点，这样每个点的出边就是一个小于$\sqrt{n}$ 的数。证明略。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 2e5 + 10;

int n, m, q; 
//edge存储原始无向图
vector<PII> edge;
//g存储有向图
vector<int> g[N];
//deg存储原图点的度，vis表示在每次询问中备选特征
int k, deg[N], vis[N];

void solve()    
{
    cin >> n >> m >> q;
    for (int i = 0; i < m; i ++ )
    {
        int u, v;
        cin >> u >> v;
        deg[u] ++ , deg[v] ++ ;
        edge.pb({u, v});
    }

    //连成有向图，度小点连向度大点
    for (auto t : edge)
    {
        int u = t.first, v = t.second;
        if (deg[u] > deg[v]) g[v].pb(u);
        else g[u].pb(v);
    }

    while (q -- )
    {
        int k;
        cin >> k;
        //存点，标记为备选特征
        vector <int> node(k);
        for (int i = 0; i < k; i ++ )
        {
            cin >> node[i];
            vis[node[i]] = 1;
        }

        //枚举每个点所连的有向边
        int res = 0;
        for (int u : node)
            for (int v : g[u])
                if (vis[v]) res ++ ;

        cout << res << endl;
        //清除备选特征
        for (int u : node) vis[u] = 0;
    }
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    //int t; cin >> t; while (t -- )
    solve();

    return 0;
}

L Tokitsukaze and Three Integers

L

—— 中等

—— 预处理，容斥？

题意

给定一个长度为 n 的序列 a 和一个正整数 p。对于每一对互不相等的 i ，j ，k，满足 $(a_i*a_j+a_k) \equiv x(mod \;p)$ 。

解题思路

给定的数据范围较小，可以接受O($n^2$) 的时间复杂度。给定的公式可以分成三部分，我们选择预处理出来$a_i*a_j$ 的部分，然后枚举$x和a_k$的值即可。记得去重 (去掉三个重复的，两个重复的)。

(写的时候没想到，我反思，不应该太顾虑模 p)

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 5010;
int a[N];
//c[x]表示x=ai*aj的数量。f[i][x]表示以包含i的x=ai*aj的数量，用于去重。
int c[N], f[N][N];

void solve()    
{
    int n, p;
    cin >> n >> p;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        a[i] %= p;
    }

    //预处理ai*aj的值
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= n; j ++ )
        {
            //需要保证i!=j，也就是减去了三个相同的
            if (i == j) continue;
            c[a[i] * a[j] % p] ++ ;
            //记录，用于去重，去掉两个相同的 i=k 一次，j=k 一次。
            f[i][a[i] * a[j] % p] += 2;
        }
    }

    //枚举x的值
    for (int i = 0; i < p; i ++ )
    {
        ll res = 0;
        //枚举a_k的值
        for (int k = 1; k <= n; k ++ )
        {
            //经典(+p)%p，防止负数
            int now = (i - a[k] + p) % p;
            res += c[now] - f[k][now];
        }
        cout << res << " ";
    }
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    //int t; cin >> t; while (t -- )
    solve();

    return 0;
}

han yue

https://ich-liebe.github.io/2023/11/29/2023%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A52/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 han yue !

题解 2023牛客寒假

CodeTON Round 7 (Div. 1 + Div. 2)

2023-11-30 题解

cf 题解

Codeforces Round 909(Div.3)

2023-11-28 题解

cf 题解

2023牛客寒假基础集训营2

A

题意

解题思路

代码

B

题意

解题思路

代码

C

题意

解题思路

代码

D

题意

解题思路

代码

E

题意

解题思路

代码

F

题意

解题思路

代码

G

H

题意

解题思路

代码

I

题意

解题思路

代码

J

题意

解题思路

代码

K

题意

解题思路

代码

L

题意

解题思路

代码

你的赏识是我前进的动力