0%

牛客2023寒假集训 - 6

Rank 663/3064. AC 7/12.

A. 阿宁的签到题

题意

根据分数输出等级。

思路

一门编程语言的基础之基础。

时间复杂度:

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long x = scanner.nextLong();
        if(1 <= x && x <= 7) System.out.println("very easy");
        else if(x <= 233) System.out.println("easy");
        else if(x <= 10032) System.out.println("medium");
        else if(x <= 114514) System.out.println("hard");
        else if(x <= 1919810) System.out.println("very hard");
        else System.out.println("can not imagine");
    }

}

送分还不写快点啊((

B. 阿宁的倍数

题意

给定一个长度为 的数组 ,下标从 开始,对于 次操作,输出需要输出的内容。

操作分为两种:

  1. 修改操作:数组末尾增加一个数
  2. 询问操作:对于所有 ,输出有多少 的倍数。

思路

我们考虑维护两个数组

其中, 表示整个序列有多少数是 的倍数, 表示 区间内有多少数是 的倍数。

那么,对于每次查询的 ,输出 即可。

我们来考虑一下这两个数组如何构建:

我们可以从前往后遍历,枚举 的所有因数 ,将所有 加上 ,那么我们可以保证最后得到的 是我们想要的数组,与此同时, 按照上述遍历方法, 就是 的值。

在修改操作时,我们只需在加入新加的数 的同时,更新 即可。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 400010;

int a[N], tot[N], pre[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        for(int j=1;j<=a[i]/j;j++){
            if(a[i] % j == 0){
                tot[j] ++;
                if(j != a[i] / j) tot[a[i] / j] ++;
            }
        }
        pre[i] = tot[a[i]];
    }
    while(q --){
        int op, x;
        cin >> op >> x;
        if(op == 1){
            a[++ n] = x;
            for(int j=1;j<=a[n]/j;j++){
                if(a[n] % j == 0){
                    tot[j] ++;
                    if(j != a[n] / j) tot[a[n] / j] ++;
                }
            }
            pre[n] = tot[a[n]];
        }else cout << tot[a[x]] - pre[x] << '\n';
    }
    return 0;
}

比较暴力但又不太暴力的做法

C. 阿宁的大背包

题意

给定背包的数量 个背包的大小构成一个 的排列,按照将相邻背包合成一个新的大背包的方式,经过 次合并,得到一个大背包。输出一个排列,满足最终背包最大,并输出值。

合并方式:

思路

我们直接来考虑 个物品时的合并结果:

我们不妨留意一下从第二次合并后每项的系数,没错,就是杨辉三角。

于是,构建数组就非常明显了:我们只要按 中间向两侧递减 排列即可。

接着,考虑到数据范围并不大,于是下列两种方法均可行:

  1. 暴力合并;
  2. 计算出杨辉三角,作为系数和数组相乘。

考虑到暴力合并更不用脑子,这边采取方案

时间复杂度:

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int n = console.nextInt();
        long mod = 1000000007;
        int[] a = new int[n];
        for(int i=0;i<n/2;i++) a[i] = i * 2 + 1;
        if(n % 2 == 1) a[n / 2] = n;
        for(int i=0;i<n/2;i++) a[n - i - 1] = (i + 1) * 2;
        List<Integer> ans = new ArrayList<>();
        for(int i=0;i<n;i++) ans.add(a[i]);
        for(int t=n;t>=2;t--){
            List<Integer> now = new ArrayList<>();
            for(int i=0;i<t-1;i++) now.add((int)(((long) ans.get(i) + ans.get(i + 1)) % mod));
            ans = now;
        }
        console.println(ans.get(0));
        for(int i=0;i<n;i++) console.print(a[i] + " ");
        console.close();
    }

    //快读模板,此处略去
    //public static class Console implements Closeable {}

}

优雅的暴力

D. 阿宁的毒瘤题

题意

给定一个字符串 ,修改任意一个字符为其他字符,让子序列 的数量最小,子序列不一定连续。输出修改后的

思路

不是 !!!!

首先,如果不删掉字符的话,做法就是很简单的 ,但这题如果用 解的话,会特别麻烦,~且我无法证明正确性~。

反而,这题是一道偏模拟的前缀和。

我们分别考虑删掉一个 和删掉一个 的代价:

  1. 对于一个 ,它的价值为 $u{pre} \times u{suf}$;
  2. 对于一个 ,它的价值为 $ud{pre} + du{suf}$。

于是,我们可以考虑前缀和的方法,统计正方向第 位前面有多少 ,反方向后面有多少 即可。

注意,不止有 这两个字符,不要偷懒不写

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 200010, inf = 0x3f3f3f3f;

int pre[N], ps[N], ss[N];
string s;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> s;
    int n = s.length();
    int cu = 0;
    for(int i=0;i<n;i++) if(s[i] == 'u') cu ++;
    int maxx = 0, maxi = 0;
    for(int i=0;i<n;i++){
        if(i > 0) {
            pre[i] = pre[i - 1];
            ps[i] = ps[i - 1];
        }
        if(s[i] == 'u'){
            pre[i] ++;
        }else if(s[i] == 'd'){
            if(maxx < pre[i] * (cu - pre[i])){
                maxx = pre[i] * (cu - pre[i]);
                maxi = i;
            }
            ps[i] += pre[i];
        }
    }
    for(int i=n-1;i>=0;i--){
        ss[i] = ss[i + 1];
        if(s[i] == 'd') ss[i] += (cu - pre[i]);
        else if(s[i] == 'u'){
            if(maxx < ps[i] + ss[i]){
                maxx = ps[i] + ss[i];
                maxi = i;
            }
        }
    }
    for(int i=0;i<n;i++) cout << (maxi == i ? 'a' : s[i]);
}

做了一个小时dp,最后10分钟才大彻大悟,人快哭出来力

E. 阿宁的生成树

待补充

F. 阿宁的二进制

题意

给定一个长度为 的数组 ,下标从 开始,定义 。如

对于独立的 次询问,定义一次操作为选定任意一个 ,执行 。给定操作数 ,输出 整个数组的最大值 的最小值。

每次询问输出答案后,数组 恢复原样。

思路

我们不妨来考虑 范围内二进制下 最多的数,它总共有

对于最大值 ,我们可以知道,第二次操作后最多只会有

继续操作,剩下最多

继续操作,剩下

也就是说,对于任意 范围内的数,我们最多也只能进行 次操作,之后值就为固定的

换句话说,题给 的范围是唬人的,真正 的范围应为

那么,我们不妨先将所有询问都读入,然后桶排序一下,再枚举操作 次后的答案,若次数和询问相同,那么记录答案。我们不妨用大根堆来存储,让时间复杂度降到

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 200010;

pair<int, int> qs[N];
int ans[N];

int F(int x) {
    int cnt = 0;
    while (x != 0) {
        if ((x & 1) == 1) cnt++;
        x >>= 1;
    }
    return cnt;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    priority_queue<int> pq;
    for(int i=0;i<n;i++) {
        int t;
        cin >> t;
        pq.emplace(t);
    }
    for(int i=0;i<q;i++){
        int t;
        cin >> t;
        qs[i] = {t, i};
    }
    sort(qs, qs + q, [](pair<int, int> o1, pair<int, int> o2){return o1.first < o2.first;});
    int i = 0, to = 0;
    while(to < q){
        int t = pq.top();
        if(t == 1) break;
        pq.pop();
        i ++;
        pq.push(F(t));
        while(to < q && qs[to].first == i) ans[qs[to ++].second] = pq.top();
    }
    for(int t=0; t < q; t++) {
        if(ans[t] == 0) cout << 1 << '\n';
        else cout << ans[t] << '\n';
    }

}

自从上次做过某题后,老想着会不会可以收敛((

G. 阿宁的整数配对

题意

给定一个长度为 的数组 ,选出 对整数,输出每对整数相乘并求和的最大值。

思路

排一个序,从两端取即可。

时间复杂度:

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), k = scanner.nextInt();
        long[] a = new long[n];
        for(int i=0;i<n;i++) a[i] = scanner.nextInt();
        Arrays.sort(a);
        int l = 0, r = n - 1;
        long ans = 0;
        for(int i=0;i<k;i++){
            if(a[l] * a[l + 1] > a[r] * a[r - 1]){
                ans += a[l] * a[l + 1];
                l += 2;
            }else{
                ans += a[r] * a[r - 1];
                r -= 2;
            }
        }
        System.out.println(ans);
    }

}

打卡打卡~

H. 阿宁讨伐虚空

题意

给定 个敌人,在 内随机选一个 ,若 ,那么敌人能被攻击到。输出能被攻击到的概率。

思路

如题,分类讨论算一下概率即可。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 100010;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int x, l, r;
    cin >> x >> l >> r;
    if(l > x - 1) cout << 0; 
    else if(r < x) cout << 1;
    else cout << ((double) (x - l) / (double) (r - l + 1));
}

简简单单签到题

I. 阿宁前往沙城

题意

给定一个无向图,定义操作为选定两条边,将一条边删除,并将另一条边的长度改为 。在 操作可在任意时间可执行无限次 的条件下,输出 的最短路。

思路

很显然,从第二条路开始,我们直接把前面的路毁掉即可。

所以我们不妨直接把所有边改成 ,用 跑一遍最短路即可。

但得到的答案会出现一种特殊情况:最短路将所有边都覆盖了。

在该情况下,第一条只能用原来的长度替代了。

因此,直接套板子然后略微修改一下即可。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 200010;

struct edge {
    int v, w;
};

struct node {
    int dis, u;
    bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[N];
int dis[N], vis[N], cnt[N];
priority_queue<node, vector<node>, greater<> > q;

void dijkstra(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        int u = q.top().u;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                q.push({dis[v], v});
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    int minn = 0x3f3f3f3f;
    for(int i=0;i<m;i++){
        int u, v, w;
        cin >> u >> v >> w;
        if(u == 1 || v == 1) minn = min(minn, w);
        e[u].push_back({v, 1});
        e[v].push_back({u, 1});
    }
    dijkstra(1);
    cout << (cnt[n] < m ? cnt[n] : dis[n] + minn - 1);
}

oi-wiki的板子真好用(划掉

J. 阿宁指指点点

待补充

K. 阿宁大战小红

待补充

L. 阿宁睡大觉

题意

给定一个 列的地图(正方形的左上角),每行的最后一个格子是美梦格子,除 个噩梦格子外,其余格子都可以通过,输出从 走到美梦格子的方案总数。

注意,

思路

这题有一个很明显的特点:障碍数远小于总格子数。

不考虑噩梦格子的话,总方案数很好求,即为 。但若用类似于 的方法去枚举能走的路径,显然是过于复杂的。

有没有一种算法,可以用类似于取补集的方法来大大降低时间复杂度呢?

也许我们可以枚举不能走的路径,但暴力枚举也是不行的。

这里需要用到 容斥

对于两个噩梦格子,它们之间的方案数可以用组合数来求:

每条路径的节点数量是一致的,为 ,而每条路径一定会有 个节点是在 轴方向移动的,所以方案数即为

于是,我们只需枚举所有选择即可,这里我们可以考虑用二进制进行状态压缩,直接用二进制位是否是 来考虑这个噩梦节点是否选上。当然也可以无脑递归套 ,但状压会更好写。

还有一个问题,若我们每次都算一遍两个节点的方案数,未免有些复杂,所以我们可以用 复杂度的组合数求法

容斥

我们来考虑三个集合,它们两两相交,且有一部分三个相交在一起,如下图:

容斥原理 - venn 图示例

对,这是一个韦恩图,而且我们可以很容易的得到下面这个式子:

推广之后,对于 个集合的并集,我们只需按上述式子写,其中符号取决于选了几个集合,奇数为正偶数为负。

因而,对于所有噩梦格子的走法,利用容斥即可解决。

线性复杂度的组合数求法

显然,当数据量过大的时候,每次都用一遍 循环是不合理的,那么我们可以考虑预处理阶乘。

由于存在除法取模,我们需要用到乘法逆元,将除法取模转化为乘法取模。

逆元有一个很简单的求法,即费马小定理:对于 ,乘法逆元

但每次用一遍快速幂也会提高时间复杂度,因而我们考虑线性求逆元,用到如下递推式:

对于阶乘的逆元,满足

满足上述条件后,

线性求逆元的证明

img

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 400010, mod = 1e9 + 7;

pii a[N], b[N];
int n, m, inv[N], fac[N], facInv[N], pow2[N];

//O1复杂度求组合数
int c(int n, int m){
    return fac[n] * facInv[m] % mod * facInv[n - m] % mod;
}

signed main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0;i<m;i++) cin >> a[i].first >> a[i].second;
    inv[1] = fac[0] = fac[1] = facInv[0] = facInv[1] = pow2[0] = 1;
    for(int i=2;i<=n*2;i++){
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        fac[i] = fac[i - 1] * i % mod;
        facInv[i] = facInv[i - 1] * inv[i] % mod;
    }
    for(int i=1;i<=n;i++) pow2[i] = pow2[i - 1] * 2 % mod;
    int ans = pow2[n - 1];
    for(int i=1;i<(1 << m);i++){
        int t = 0;
        b[t ++] = {1, 1};
        int sign = 1;
        for(int j=0;j<m;j++){
            if((i >> j) & 1){
                b[t ++] = a[j];
                sign = -sign;
            }
        }
        sort(b, b + t);
        int now = pow2[n - 1 - (b[t - 1].first + b[t - 1].second - 2)];
        for(int j=1; j < t; j++){
            if(b[j - 1].second <= b[j].second){
                int x = b[j].first - b[j - 1].first + 1, y = b[j].second - b[j - 1].second + 1;
                now = now * c(x + y - 2, x - 1) % mod;
            }else{
                now = 0;
                break;
            }
        }
        ans += sign * now;
    }
    ans = (ans % mod + mod) % mod;
    cout << ans << '\n';
    return 0;
}

有点震撼的说…