0%

牛客2023寒假集训 - 4

Rank 445/3193. AC 6/13.

A. 清楚姐姐学信息论

题意

给定 进制和 进制,用该进制下的一定数量的号码牌表示数字。输出用哪个进制可以用 张号码牌表示更多的数。

思路

显然,我们只需比较 的大小,但我们无需模拟计算,因为只有 组合的时候,,其余情况均为 。所以对该情况特判即可。

时间复杂度:

对应AC代码

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt(), b = scanner.nextInt();
        if ((a == 2 && b == 3) || (a == 3 && b == 2)) System.out.println(3);
        else System.out.println(Math.min(a, b));
    }

}

淦,还有特判,被坑了

B. 清楚姐姐学构造

题意

给定数组 和质数 ,构造两个数组 ,满足下面的同余方程组:

$\left{\begin{aligned}
ai \equiv a{N-i-1}\ (mod\ m) \
bi \equiv -b{N-i-1}\ (mod\ m) \
c_i \equiv a_i+b_i\ (mod\ m)
\end{aligned}
\right.$

若可构造,输出 以及一种构造,否则输出

一句话题意

在模系下构造两个数列,一个满足奇函数性质,另一个满足偶函数性质,两个数列的和为任意给定数列。

思路

考虑到对称性,我们不妨设 $ai=a{N-i-1}=x,bi=m-b{N-i-1}=y$。

那么,$ai+b_i=x+y,a{N-i-1}+b_{N-i-1}=x+m-y$。

代入第三个式子,我们可以得到 $x+y \equiv ci\ (mod\ m),x-y \equiv c{N-i-1}\ (mod\ m)$。

两式相加,$2x \equiv ci+c{N-i-1}\ (mod\ m)x=\frac{ci+c{N-i-1}+km}{2},k \in Z$。

因而,我们只需判断分子的奇偶性,然后即可计算出

同理可得

若数组的长度为奇数,那么将会多出来一项 ,观察可得 符合题意。

遍历输出即可。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

#define int long long

int a[N], b[N], c[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i=0;i<n;i++) cin >> c[i];
    for(int i=0;i<n/2;i++){
        int k1 = c[i] + c[n - i - 1], k2 = c[i] - c[n - i - 1], x, y;
        if(k1 % 2 == 0){
            if(m == 2) {
                x = m + k1;
                y = m + k2;
            }
            else {
                x = m * 2L + k1;
                y = m * 2L + k2;
            }
        }else{
            if(m == 2){
                cout << "NO\n";
                return 0;
            }else {
                x = m + k1;
                y = m + k2;
            }
        }
        x /= 2;
        y /= 2;
        a[i] = a[n - i - 1] = x;
        b[i] = y;
        b[n - i - 1] = m - y;
    }
    if(n % 2 == 1) {
        a[n / 2] = c[n / 2];
        b[n / 2] = 0;
    }
    cout << "YES\n";
    for(int i=0;i<n;i++) cout << a[i] << ' ';
    cout << '\n';
    for(int i=0;i<n;i++) cout << b[i] << ' ';
}

不会有人暴力吧((

C. 清楚姐姐学01背包(Easy Version)

题意

给定 个物品以及总容量 ,第 个物品的体积为 $wiv_im01Val{max}$。

现在,枚举每个物品,将该物品去除后,得到最大价值 $Val’iVal’_i<Val{max}0xx$ 后该物品必选。

均不超过

思路

鉴于本题数据量很小,我们可以直接按照题面进行暴力模拟,对每个物品去掉后的情况进行 背包,若非必选,那么再以去掉该物品后的容量为总容量跑一遍 背包,将结果与 做差 即可得到答案。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110, inf = 0x3f3f3f3f;

#define int long long

int n, m;

int w[N], v[N], dp[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; i++)
        for (int l = m; l >= w[i]; l--) {
            dp[l] = max(dp[l], dp[l - w[i]] + v[i]);
        }
    int maxx = dp[m];
    for(int i=1;i<=n;i++){
        memset(dp, 0, sizeof dp);
        for (int p = 1; p <= n; p++) {
            int cw = p == i ? 0 : w[p], cv = p == i ? 0 : v[p];
            for (int l = m; l >= cw; l--) {
                dp[l] = max(dp[l], dp[l - cw] + cv);
            }
        }
        if(maxx > dp[m]) cout << 0 << '\n';
        else{
            memset(dp, 0, sizeof dp);
            for (int p = 1; p <= n; p++) {
                int cw = p == i ? 0 : w[p], cv = p == i ? 0 : v[p];
                for (int l = m - w[i]; l >= cw; l--) {
                    dp[l] = max(dp[l], dp[l - cw] + cv);
                }
            }
            cout << maxx - dp[m - w[i]] - v[i] + 1 << '\n';
        }
    }
}

令人感慨

D. 清楚姐姐学01背包(Hard Version)

题意

题,但 不超过

思路

暴力解决不了问题了。

我们回到 背包的二维实现:枚举所有物品,以及所有可能的最大容量,取 该状态的价值 和 前一个状态加上当前物品的价值 的最大值。

那么,我们自然可以发现,只要将 题的代码改成二维背包,那么至少最后一个 循环是不必要的,因为对于前 个物品,以 为最大容量的 值 我们已经 在前面 以 的复杂度 推得了。

那么 后面物品的怎么办?从上面的分析我们可以知道,任意小于 的背包容量对应的答案均可通过 的“预处理”得到,那么我们不妨从后往前跑一遍 背包,于是乎,对于第一维为 数组,我们只需枚举容量即可。

更具体地

  1. 从前往后跑一遍 背包,得到二维数组 ;再从后往前跑一遍 背包,得到二维数组
  2. 枚举每一个物品:维护对于 前一位的状态下容量的前缀最大值数组 ,对于 后一位的状态下容量的后缀最大值数组 。然后,遍历前 个的最大容量 ,剩余的分给去掉前 个物品后剩下物品的最大容量,那么, 的最大值即为 去掉 后的最大价值
  3. 综合步骤 和暴力做法的最后一个 循环,我们只需将 前 个物品,第 个物品,剩下的物品 抽象为三个物品,然后利用 背包的第二层循环计算出必须将 选中的最大值
  4. 输出 即可。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 5010;

#define int long long

int n, m;

int w[N], v[N], dpz[N][N], dpf[N][N], mxz[N], mxf[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            dpz[i][j] = dpz[i - 1][j];
            dpf[i][j] = dpf[i - 1][j];
            if (j >= w[i]) dpz[i][j] = max(dpz[i][j], dpz[i - 1][j - w[i]] + v[i]);
            if (j >= w[n - i + 1]) dpf[i][j] = max(dpf[i][j], dpf[i - 1][j - w[n - i + 1]] + v[n - i + 1]);
        }
    for (int i = 1; i <= n; i++) {
        memset(mxz, 0, sizeof mxz);
        memset(mxf, 0, sizeof mxf);
        for (int j = 1; j <= m; j++) {
            mxz[j] = max(mxz[j - 1], dpz[i - 1][j]);
            mxf[j] = max(mxf[j - 1], dpf[n - i][j]);
        }
        int vi = 0, vp = 0;
        for (int j = 0; j <= m; j++) {
            vi = max(vi, mxz[j] + mxf[m - j]);
            if (m - j >= w[i])
                vp = max(vp, max(mxz[j] + mxf[m - j - w[i]] + v[i],
                                 mxf[j] + mxz[m - j - w[i]] + v[i]));
        }
        cout << max(0ll, vi - vp + 1) << '\n';
    }
}

居然有点想出来了,毕竟背包就是贪心嘛

E. 清楚姐姐打怪升级

题意

给定 只怪物,第 只怪物的生命值上限为 ,生命恢复速度为 。主角的攻击间隔为 ,攻击力为

对于每个怪物,每个时刻初,恢复 点生命值,直至上限

时刻末,主角挑选一只怪物,扣除 点生命值,若剩余生命值为非正数,则判定怪物死亡。

输出在哪个时刻末可杀死所有怪物。若永远无法杀死则输出

思路

贪心。

我们采取将一只怪物杀死再去杀另一只的做法,使每只需要杀死的怪物能恢复的生命值最小。

显然,在下次攻击前,怪物能恢复 点血量,如果恢复的血量大于主角攻击力 ,那么直接输出

否则:

  1. 如果一击秒杀,时刻
  2. 否则,在每次砍怪物之后,有效扣血为 ,将其与第一次剩余的血量 进行除法运算即可。注意需要特判可能出现的一次砍完的情况。

因最后一只怪物的计算会多出一个单位等待时间,所以我们将其减去。

时间复杂度:

对应AC代码

import java.math.*;
import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong(), t = scanner.nextLong(), a = scanner.nextLong();
        long tick = 0;
        for(int i=0;i<n;i++){
            long h = scanner.nextLong(), v = scanner.nextLong();
            if(h <= a) {
                tick ++;
                continue;
            }
            if(v * t >= a){
                System.out.println(-1);
                return;
            }else {
                if ((h - a) % (a - v * t) == 0) tick += ((h - a) / (a - v * t) + 1);
                else tick += ((h - a) / (a - v * t) + 2);
            }
        }
        System.out.println((tick - 1) * t + 1);
    }

}

模拟+贪心呐

F. 清楚姐姐学树状数组

题意

构建一个 的树状数组对应的二叉树,二叉树的中序遍历为节点编号,如下图:img

给定 个查询,输出询问的节点在前、中、后序遍历中分别是第几个。

思路

我们从 开始向下遍历,根据树状数组的特性,我们可以知道下一个需要遍历的点的值:

若向左,;若向右,

接着,我们先来看前序遍历的规律:对于下一个节点,若向左子树移动,那么前序遍历的值会 ,否则会

而对于后序遍历,类似于前序:对于下一个节点,若向子树移动,那么后序遍历的值会 ,否则会

特别地,在后续遍历中,从 移动到 时,后序遍历只相差 ,特判即可。

注: 当然,我们也可以用递推的方式,初始化数组后按照找对称点的方式解题。

时间复杂度:

#include <bits/stdc++.h>

using namespace std;

#define int long long

int ans, maxx, x;

int lb(int x){
    return x & (-x);
}

void dfs(int now, bool inc) {
    if (now == x) return;
    if (now > x) {
        if (inc) ans++;
        else ans -= (now == maxx ? 1 : lb(now));
        dfs(now - lb(now) / 2ll, inc);
    } else {
        if (inc) ans += lb(now);
        else ans--;
        dfs(now + lb(now) / 2ll, inc);
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int k, q;
    cin >> k >> q;
    maxx = (1ll << k);
    while(q --){
        cin >> x;
        ans = 1;
        dfs(maxx, true);
        cout << ans << ' ' << x << ' ';
        ans = maxx;
        dfs(maxx, false);
        cout << ans << '\n';
    }
}

你说你这个蠢人怎么连找规律都找不出来呢.jpg

G. 清楚姐姐逛街(Easy Version)

题意

给定一个迷宫,终点按照固定方式移动,以题给字符确定方向。给定多个查询,包括一个起点,输出从起点开始到可变终点的最短路。

思路

考虑到查询数量很少,我们采用暴力的做法:

  1. 从起点开始 ,确定能到达的每个点的最短路径长度。
  2. 模拟终点移动,若遍历到的点存在路径长度小于等于当前终点移动的长度,那么输出答案。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 810;

#define int long long

char mp[N][N];
int dis[N][N], dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m, xs, ys, Q;
    cin >> n >> m >> xs >> ys >> Q;
    for(int i=0;i<n;i++) cin >> mp[i];
    memset(dis, 0x3f, sizeof dis);
    queue<pair<int, int>> q;
    q.emplace(xs, ys);
    dis[xs][ys] = 0;
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        int px = t.first, py = t.second;
        for(int i=0;i<4;i++){
            int x = px + dx[i], y = py + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m && mp[x][y] != '#' && dis[x][y] > dis[px][py] + 1) {
                dis[x][y] = dis[px][py] + 1;
                q.emplace(x, y);
            }
        }
    }
    while(Q --){
        int x, y, ans, step = 1;
        cin >> x >> y;
        while(true){
            char cur = mp[x][y];
            if(cur == 'L' && mp[x][y - 1] != '#') y --;
            else if(cur == 'R' && mp[x][y + 1] != '#') y ++;
            else if(cur == 'U' && mp[x - 1][y] != '#') x --;
            else if(cur == 'D' && mp[x + 1][y] != '#') x ++;
            else {
                if(dis[x][y] == -1) {
                    ans = -1;
                    break;
                }
            }
            if(dis[x][y] <= step) {
                ans = step;
                break;
            }
            step ++;
        }
        cout << ans << '\n';
    }
}

为啥BFS要这么写才对捏

H. 清楚姐姐逛街(Hard Version)

待补充,倍增+二分答案

I. 清楚姐姐采蘑菇

待补充,莫队+单调性

J. 清楚姐姐学排序

题意

给定数组 对元素大小关系,求顺序确定的位置和该位置的元素。

即对于位置 ,若确定位置在第 位,那么 ,否则 。输出顺序数组

思路

显然,如果对于一个数,有 个数小于它, 个数大于它,那么如果满足 ,该数的位置就一定唯一确定。

因此,我们直接枚举每个点即可。因为可能存在包含关系 ,所以我们需要

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

#define int long long

vector<int> e[N][2];
int res[N], vis[N];

int dfs(int x, int t){
    if(vis[x]) return -1;
    vis[x] = true;
    int ans = 0;
    for(int each : e[x][t]){
        ans += dfs(each, t) + 1;
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int x, y;
        cin >> x >> y;
        e[x][0].emplace_back(y);
        e[y][1].emplace_back(x);
    }
    memset(res, -1, sizeof res);
    for(int i=1;i<=n;i++){
        memset(vis, 0, sizeof vis);
        int cntl = dfs(i, 1);
        vis[i] = false;
        int cntr = dfs(i, 0);
        if(cntl + cntr == n - 1) res[cntl + 1] = i;
    }
    for(int i=1;i<=n;i++) cout << res[i] << ' ';
    cout << '\n';
}

不该不做这题…

K. 清楚姐姐玩翻翻乐

待补充

L. 清楚姐姐的三角形I

题意

对于 ,顶点对应的边分别为 。记 ,给定 ,输出 。无解输出

思路

显然,,那么我们只需判断两边之和大于第三边以及分子是否为偶数即可。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 500010, inf = 0x3f3f3f3f;

#define int long long

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t, va, vb, vc;
    cin >> t;
    while(t -- > 0){
        cin >> va >> vb >> vc;
        int la = vb + vc - va, lb = va + vc - vb, lc = va + vb - vc;
        if(la % 2 == 1 || lb % 2 == 1 || lc % 2 == 1){
            cout << "NO\n";
        }else{
            la /= 2;
            lb /= 2;
            lc /= 2;
            if(la + lb > lc && la + lc > lb && lb + lc > la){
                cout << "YES" << '\n' << la << ' ' << lb << ' ' << lc << '\n';
            }else cout << "NO\n";
        }
    }
}

怎么可以暴力呢

M. 清楚姐姐的三角形II

题意

给定数组长度 ,构造一个数组,满足相邻三个数不能构成三角形。

思路

输出即可

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 500010, inf = 0x3f3f3f3f;

#define int long long

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for(int i=0;i<n/3;i++){
        cout << "1 1 2 ";
    }
    if(n % 3 == 1) cout << "1";
    if(n % 3 == 2) cout << "1 1";
}

差点斐波那契((