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. 阿宁的倍数

题意

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

操作分为两种：

修改操作：数组末尾增加一个数。
询问操作：对于所有，输出有多少是的倍数。

思路

我们考虑维护两个数组。

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

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

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

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

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

时间复杂度：

对应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. 阿宁的大背包

题意

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

合并方式：

思路

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

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

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

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

暴力合并；
计算出杨辉三角，作为系数和数组相乘。

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

时间复杂度：

对应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. 阿宁的毒瘤题

题意

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

思路

不是 !!!!

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

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

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

对于一个，它的价值为 $u{pre} \times u{suf}$；
对于一个，它的价值为 $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. 阿宁睡大觉

题意

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

注意，。

思路

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

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

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

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

这里需要用到容斥。

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

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

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

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

容斥

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

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

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

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

线性复杂度的组合数求法

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

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

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

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

对于阶乘的逆元，满足

满足上述条件后，。

线性求逆元的证明

时间复杂度：

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

有点震撼的说…

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