算法练习专栏——牛客练习——牛客round40

A:小红进地下城

题目描述

小红来到了一个地下城的入口，她准备进入地下城，但门口有个机关锁。小红必须使用正确的密码才可以打开。
已知机关锁为一个4位的数字，小红想知道，自己能否成功进入。

输入描述:

1 2	`第一行输入一个长度为4的数字串，代表小红尝试的密码。第二行输入一个长度为4的数字串，代表正确的密码。`

输出描述:

1	`如果小红可以成功进入，则输出"Yes"。否则输出"No"。`

示例1

输入

复制

1 2	`8745 8745`

输出

复制

Yes

示例2

输入

复制

1 2	`9876 6789`

输出

复制

No

代码

#include <iostream>
using namespace std;
int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    if (s1 == s2) cout << "Yes";
    else cout << "No";
    return 0;
}

B:小红打怪

链接

题目描述

小红来到了地下城的一个房间，房间被分成nnn行mmm列的格子，小红站在其中一个格子上，她可以向一个方向攻击整条直线的所有格子（小红不能改变自己的位置和朝向）。
小红想知道，自己可以攻击到多少只怪物？

输入描述:

1
2
3

第一行输入两个正整数n,mn,mn,m，代表矩阵的行数和列数。
接下来的nnn行，每行输入一个字符串，代表矩阵。字符串仅由'.'、'*'和大写字母组成。其中'.'代表空地，'*'代表该格子上有一只怪物。大写字母有且仅有一个，且为'W'、'S'、'A'、'D'中的一种，代表小红面朝的方向。'W'代表向上，'S'代表向下，'A'代表向左，'D'代表向右。
1≤n,m≤10001\leq n,m \leq 10001≤n,m≤1000

输出描述:

1	`小红可以攻击到的怪物数量。`

示例1

输入

复制

4 5
..***
.****
**.**
*.*A*

输出

复制

说明

1	`小红向左攻击，可以攻击到两个怪物。`

代码(模拟)

#include <iostream>
using namespace std;
const int N = 1010;
int n, m, x, y;
char c;
char a[N][N];

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if (a[i][j] != '.' && a[i][j] != '*') {
                c = a[i][j];         
                x = i;
                y = j;
            }
        }
    }
    
    int res = 0;
    if (c == 'A') {
        while (y--) {
            if (a[x][y] == '*') res ++;
        }
    }
    
    if (c == 'W') {
        while (x--) {
            if (a[x][y] == '*') res++;
        }
    }
    
    if (c == 'D') {
        while (y++ != m) {
            if (a[x][y] == '*') res ++;
        }
    }
    
    if (c == 'S') {
        while (x++ != n) {
            if (a[x][y] == '*') res++;
        }
    }
    
    cout << res;
}

C:小红的排列构造

链接

题目描述

小红拿到了一个长度为nnn的数组aaa，她希望你构造两个排列ppp和qqq，满足对于i∈[1,n],aii∈[1,n],a_ii∈[1,n],ai为pip_ipi或qiq_iqi二选一。你能帮帮她吗？

定义排列是一个长度为nnn的数组，其中1到nnn每个元素恰好出现1次。

输入描述:

第一行输入一个正整数n，代表两个数组的长度。
第二行输入n个正整数ai。
1≤n≤105
1≤ai≤n

输出描述:

1 2	`如果无解，请输出-1。否则第一行输出n个正整数pi，第二行输出n个正整数qi，代表小红构造的两个排列。有多解时输出任意即可。`

示例1

输入

复制

1
2

3
2 3 2

输出

复制

1 2	`2 3 1 1 3 2`

示例2

输入

复制

1 2	`4 1 1 1 1`

输出

复制

-1

代码（构造模拟）

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N], b[N];
bool sta[N], stb[N];

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    bool flag = false;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (!sta[x]) {
            a[i] = x;
            sta[x] = true;
        }
        else if (!stb[x]){
            b[i] = x;
            stb[x] = true;
        } else {
            flag = true;
        }
    }
    
    if (flag) cout << "-1";
    else {
        int k = 1;
        for (int i = 1; i <= n; i++) {
            if (!sta[i]) {
                if (!a[k]) {
                    a[k] = i;
                    sta[i] = true;
                    cout << a[k++] << " ";
                } else if (a[k] != 0) {
                    i--;
                    cout << a[k] << " ";
                    ++k;
                }
            } 
            if (a[k]) cout << a[k++] << " ";
            
        }
        if (a[k]) cout << a[k] << '\n';
        
        cout << '\n';
        k = 1;
        
        for (int i = 1; i <= n; i++) {
            if (!stb[i]) {
                if (!b[k]) {
                    b[k] = i;
                    stb[i] = true;
                    cout << b[k++] << " ";
                } else if (b[k] != 0) {
                    i--;
                    cout << b[k] << " ";
                    ++k;
                }
            } 
            if (b[k]) cout << b[k++] << " ";
            
        }
        if (b[k])cout << b[k] << '\n';
        
    }
}

D:小红升装备

链接

题目描述

小红准备去打boss了，为了强化自己的战力，小红准备精心打磨自己的装备。
现在给定了每个装备初始的战力，购买每个装备的价格，每个装备强化一级花费的金币和可以提升的战力，以及每个装备最大可以提升的等级。（装备刚购买的时候为初始状态：0级）
小红最初的金币为xxx，她想知道，自己可以通过强化装备最多达到多少战力？
请注意，装备只有购买了才可以强化！

输入描述:

第一行输入两个正整数n,x，代表装备数量和小红初始拥有的金币。
接下来的n行，每行输入5个正整数atti,pricei,costi,upgradei,lvmaxi，分别代表装备初始战力，购买该装备需要的金币、升1级花费的金币、升1级提升的战力、最高可以提升的等级。
1≤n,x≤300
1≤atti,pricei,costi,upgradei,lvmaxi≤109

输出描述:

1	`一个整数，代表小红可以达到的最大战力。`

示例1

输入

复制

3 10
10 3 5 2 100
100 20 5 4 100
20 2 1 10 1

输出

复制

说明

1
2

小红购买第一个和第三个装备，花费5金币，然后花费1金币给第三个装备升1级，该装备的战力提高到30。此时还剩4金币已经无法再升级装备。
最终的战力为40。

代码(板子)

#include <iostream>
using namespace std;
const int N = 310;
long long f[N][N];

int n, x;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> x;
    
    for (int i = 1; i <= n; i++) {
        int a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        for (int j = 0; j <= x; j++){
            f[i][j] = max(f[i][j],f[i - 1][j]);
            for (int k = 0; b + k * c <= j && k <= e; k++){
                f[i][j] = max(f[i][j], f[i - 1][j - b - k * c] + a + d * k);
            }
        }
    }    
    
    cout << f[n][x];
    return 0;
}

E:小红的矩阵划分

链接

题目描述

小红拿到了一个n∗n的方格矩阵。她准备划分成若干个大小为3的’L’型连通块和若干个大小为4的2*2连通块。已知每个’L’型连通块可以获得x分，每个2 * 2的连通块可以获得y分。小红想知道自己最多可以得到多少分？

输入描述:

1
2
3

三个正整数n,x,y，用空格隔开。
1≤n,x,y≤106
保证n是偶数。

输出描述:

1	`小红最大的得分。`

示例1

输入

复制

2 4 3

输出

复制

说明

1	`可以划分一个'L'型连通块。`

示例2

输入

复制

4 4 5

输出

复制

说明

1	`如下图，可以划分出4个'L'型连通块和一个2*2的连通块，这样的得分是最高的。`

代码（思维）

#include<bits/stdc++.h>
#define endl '\n';
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
void solve() {
    ll n, x, y;
    cin >> n >> x >> y;
    if (n % 3 == 0) {
        cout << max(n * n / 3 * x, n * n / 4 * y);
    }
    else {
        cout << max({ n * n / 3 * x,n * n / 3 * x - x + y,n * n / 4 * y });
    }
}
 
int main() {
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

算法练习专栏——牛客练习——牛客小白月赛91 上一篇

算法练习专栏——牛客练习——牛客round39 下一篇