🗑️Doごみ箱2.1🐾
🐙 文章 🌠 系列 📂 分类 🏷︎ 标签 🧸 友链 🍅 关于 留言
🗑️Doごみ箱2.1🐾
/img/dodola.png

一只小菜鸡的Blog

Codeforces Round 927(div3)

DODOLA  发布于  更新于 ,  收录于  类别 在学算法的日子里 和 系列 题解记录

A-Thorns and Coins

长度为$n$的单元格路径，每个单元格有空、有金币、荆棘三种可能，人物从最左边开始向右移动，每次步长不多于2格，求能获得的最多金币数。

$t(1≤t≤1000)$

$n(1≤n≤50)$​

.代表空，*代表荆棘，@代表金币

从左往右，寻找第一个含有2个以上*的*连通块，其前的金币都可以达到。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void solve() {
    int n;cin >> n;
    string s;cin >> s;
    int cnt = 0;
    bool f = true;
    for (int i = 0;i < n;i++) {
        if (s[i] == '@')cnt++;
        if (i > 0 && s[i] == '*' && s[i - 1] == '*'){
            break;
        }
    }
    cout << cnt << '\n';
}

B-Chaya Calendar

查亚部落相信世界末日有$n$个征兆，第$i$个征兆每隔$a_i$年出现一次，当观测到第$i-1$个征兆后才会等待第$i$个征兆。给出每个征兆的出现间隔，询问观测到所有$n$个征兆所需要的年数。

阅读全文
 算法, CF

2024牛客寒假营6||补题

DODOLA  发布于  更新于 ,  收录于  类别 在学算法的日子里 和 系列 题解记录

在$[l,r]$中寻找某个恰好是三个不同素数的乘积的数，并输出任意一个合法答案即可。

$1\leq l\leq r \leq 100$

数据小，模拟即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void solve() {
    vector<bool>isprime(101, true);    // 判断素数
    isprime[0] = isprime[1] = false;
    for (int i = 2;i <= 100;i++) {
        if (isprime[i]) {
            for (int j = i + i;j <= 100;j += i) {
                isprime[j] = false;
            }
        }
    }

    int l, r;
    cin >> l >> r;
    for (int i = 2;i <= r;i++) {
        for (int j = 2;j <= r;j++) {
            for (int k = 2;k <= r;k++) {
                if (isprime[i] && isprime[j] && isprime[k] && i != j && j != k && i != k) {
                    if (i * j * k >= l && i * j * k <= r) {
                        cout << i * j * k;return;
                    }
                }
            }
        }
    }
    cout << -1;
}

定义两个等长数组的亲密值：$|a_i-b_i|(1\leq i\leq n)$的最小值。给定2个数组，可以任意排列$a$数组的元素顺序，输出一个亲密度最小的方案（数组$a$的操作结果）。

阅读全文
 2024寒假训练, 算法, 牛客

2024牛客寒假营4||补题

DODOLA  发布于  更新于 ,  收录于  类别 在学算法的日子里 和 系列 题解记录

输入$a,b,k$，判断$a\ge k\times b$是否成立

$a,b,k(1\leq a,b,k\leq 100)$

简单判断

1
2
3
4
5

void solve() {
    int a, b, k;cin >> a >> b >> k;
    if (a >= k * b)cout << "good\n";
    else cout << "bad\n";
}

有$n$堆石子，每次选择某堆石子，选一个整数$y(2\leq y\leq x)$，将石子分为$\lfloor \frac{x}{y} \rfloor$和$x-\lfloor \frac{x}{y} \rfloor$，直到某人不能操作时结束，不能操作者输。

阅读全文
 2024寒假训练, 算法, 牛客

2024牛客寒假营5||补题

DODOLA  发布于  更新于 ,  收录于  类别 在学算法的日子里 和 系列 题解记录

一个由$n$个正整数组成的数组，求其中质数和合数共有几个。

$n(1\leq n\leq 100)$

$a_i(1\leq a_i\leq 100)$

1不是质数也不是合数。

1
2
3
4
5
6
7
8
9

void solve() {
    int n;cin >> n;
    int ans = 0;
    for (int i = 0;i < n;i++) {
        int x;cin >> x;
        if (x>1)ans++;
    }
    cout << ans << '\n';
}

给一个数组中一些位置插入$0$，要求插入后任意不是全$0$子段的平均值大于等于$1$，询问最多插入多少个$0$

$n(1\leq n\leq 10^5)$

$a_i(1\leq a_i\leq 10^9)$

从第一位开始贪，统计在每一位前最多可以插入多少个0，考虑两数之间的0的数目不能大于这2位之间允许的最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

void solve() {
    int n;cin >> n;
    vector<ll>a(n + 2);
    vector<ll>b(n + 2);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        b[i] = a[i] - 1;
    }
    b[0] = 1e9 + 50;
    b[n + 1] = 1e9 + 50;
    ll ans = 0;

    for (int i = 0;i <= n;i++) {
        // for (int j = 0;j <= n + 1;j++)cout << b[j] << ' ';cout << endl;
        if (b[i] >= b[i + 1]) {
            ans += b[i + 1];
            ll tmp = b[i + 1];
            b[i + 1] = 0;
            b[i] -= tmp;
        }
        else {
            ans += b[i];
            ll tmp = b[i];
            b[i] = 0;
            b[i + 1] -= tmp;
        }
    }

    cout << ans << endl;
}

有一个长为$n$的数组$a$

阅读全文
 2024寒假训练, 算法, 牛客

2024牛客寒假营3||补题

DODOLA  发布于  更新于 ,  收录于  类别 在学算法的日子里 和 系列 题解记录

在不考虑单词词性的前提下，只要求两个单词的首字母忽略大小写相同时就认为它们可能是一组ubuntu代号，请你编写程序判断给定的两个单词是否可能是一个ubuntu代号。

$T(1\leq T \leq 10^5)$

$S,T(1\leq |S|,|T|\leq 50)$

按题意判断即可

1
2
3
4
5
6
7

void solve() {
    string s, t;cin >> s >> t;
    if (s[0] == t[0] || abs(s[0] - t[0]) == abs('a' - 'A')) {
        cout << "Yes\n";
    }
    else cout << "No\n";
}

一个首尾相连的数组，若相邻的两个数之和为偶数选择拿走一个然后可以随意交换一对数，轮流操作，不能再操作的一方输。清楚姐姐先手。

$T(1\leq T \leq 10^4)$

$N(1\leq N\leq 26)$

$a_i(0\leq a_i \leq 10^9)$

只有1个数时直接取走，先手赢。

2个数时：奇偶/奇奇/偶偶，都是后手赢。

3个数时：奇偶奇/偶奇偶/奇奇奇/偶偶偶，都是先手赢。

阅读全文
 2024寒假训练, 算法, 牛客