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)

题意

给定个物品以及总容量，第个物品的体积为 $wi $，价值为$ v_i $。任选若干个物品放入背包，满足物品总体积小于容量$ m $，运用$ 01 $背包求出最大价值$ Val{max}$。

现在，枚举每个物品，将该物品去除后，得到最大价值 $Val’i $，若$ Val’_i<Val{max} $，那么该物品必选，输出$ 0 $；否则输出$ x $，满足该物品加上价值$ x$ 后该物品必选。

均不超过。

思路

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

时间复杂度：

对应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)

题意

同题，但不超过。

思路

暴力解决不了问题了。

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

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

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

更具体地

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

时间复杂度：

对应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. 清楚姐姐打怪升级

题意

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

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

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

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

思路

贪心。

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

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

否则：

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

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

时间复杂度：

对应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. 清楚姐姐学树状数组

题意

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

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

思路

。

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

若向左，；若向右，。

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

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

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

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

时间复杂度：

#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)

题意

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

思路

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

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

时间复杂度：

对应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";
}

差点斐波那契（（

本文作者 Floating Ocean
本文链接 https://floating-ocean.github.io/blog_old/posts/127583546/
版权声明本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！