Codeforces Round #806 (Div. 4) 题解-阿里云开发者社区

比赛链接: Codeforces Round #806 (Div. 4)

A YES or YES?

题目

大意：给你一个有大写和小写的字符串，如果不看是否大小写的话能否等于"YES"

思路：字符串+枚举

将小写转换成大写，在看转换后的字符串是否和"YES"相等
也可以枚举的时候忽视大小写，只要是“YES”中的字母的大小写即可

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e6 + 10;
void solve()
{
    string s;
    cin >> s;
    if (s.size() != 3)
    {
        puts("NO");
        return;
    }
    if ((s[0] == 'Y' || s[0] == 'y') && (s[1] == 'E' || s[1] == 'e') && (s[2] == 'S' || s[2] == 's'))
    {
        puts("YES");
        return;
    }
    puts("NO");
    return;
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

B. ICPC Balloons

题目

大意：给你一个由大写英文字母组成的字符串，每个字符第一次出现的时候给你两个气球，其他时候都只给你一个气球，问最后有多少个气球

思路：字符串+枚举

枚举字符串的时候，判断这个字母是否出现过了
出现过就加1，没出现过就加2，并且记录出现过了

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e6 + 10;
int a[26];
void solve()
{
    memset(a, 0, sizeof a);
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (a[s[i] - 'A'] == 0)
        {
            cnt++;
        }
        cnt++;
        a[s[i] - 'A'] = 1;
    }
    cout << cnt << endl;
    return;
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

D. Double Strings

题目

题目大意：给你n个字符串(长度不超过8），问每个字符串是否可以由其他的字符串中选两个拼接而成

思路：字符串+hash

如果计算所有可以拼接成字符串来判断一定会超时，所以我们逆向思维一下，由于每个字符串长的超度不超过8，所以可以将某个字符串分解成两个字符串，看这两个字符串是否在集合中出现即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e5 + 10;
int a[N];
string s[N];
void solve()
{
    int n;
    cin >> n;
    map<string, int> ma;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        ma[s[i]] = 1;
        a[i] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < s[i].size(); j++)
        {
            string a1 = s[i].substr(0, j), b1 = s[i].substr(j);
            if (ma.count(a1) && ma.count(b1))
                a[i] = 1;
        }
    }
    for (int i = 1; i <= n; i++)
        cout << a[i];
    cout << '\n';
    return;
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

E. Mirror Grid

题目

题目大意：给你一个由0和1构成正方形数组里面，然后将数组向右选择90度，180度，270度。问如何改变原数组中的某些值，使得四种形态的数组里的值都一样。求改变最少次数。
我们

思路：思维

原二维数组中的一个位置旋转三次后，总共会出现在四个位置上，所以我们只需要将这四个位置的值都变相同，那么就是最少值了。
a[i][j] ==》a[j][n-i+1] ==》 a[n-i+1][n-j+1] ==> a[n-j+1][j]

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e2 + 10;
char a[N][N];
bool st[N][N];
void solve()
{
    int n;
    cin >> n;
    memset(st, 0, sizeof st);
    for (int i = 1; i <= n; i++)
        scanf("%s", a[i] + 1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j && n % 2 == 1)
                continue;
            if (!st[i][j])
            {
                int cnt = 0;
                if (a[i][j] == '1')
                    cnt++;
                st[i][j] = 1;
                if (a[j][n - i + 1] == '1')
                    cnt++;
                st[j][n - i + 1] = 1;
                if (a[n - i + 1][n - j + 1] == '1')
                    cnt++;
                st[n - i + 1][n - j + 1] = 1;
                if (a[n - j + 1][i] == '1')
                    cnt++;
                st[n - j + 1][i] = 1;
                ans += min(cnt, 4 - cnt);
            }
        }
    }
    cout << ans << endl;
    return;
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

F. Yet Another Problem About Pairs Satisfying an Inequality

题目

题目大意：给你一个数组，找到所有的满足 a[i]<i<a[j]<j的索引对数量

思路：二分/树状数组

a[i]范围很大，但是i的范围不大，所以我们著需要保留所有a[i]<i 的索引即可，针对每个满足a[j]<j的元素，我们可以找到在它之前的满足所有a[i]<i<a[j]的全部元素，这里我们可以用二分或者时树状数组来做
二分：从前往后依次枚举，我们用一个vector来存满足的下标，枚举到某一位时，只需要在vector中找到比a[i]-1小的有多少个就行了

树状数组：快速查找一个区间内的全部元素，add操作中，我们只需要将i位置加1即可，因为后面的所有都要比i大，而不是比a[i]大，query查找中，我们只需要查询1-a[j]-1的区间即可

代码：二分：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 2e5 + 10;
int a[N];
int n;
void solve()
{
    cin >> n;
    ll ans = 0;
    vector<int> v;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] < i)
        {
            ans += (ll)(lower_bound(v.begin(), v.end(), a[i]) - v.begin());
            v.push_back(i);
        }
    }
    cout << ans << endl;
    return;
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

代码：树状数组

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 2e5 + 10;
int a[N];
int tr[N];
int n;
int lowbit(int x)
{
    return x & -x;
}
void add(int x)
{
    while (x <= n)
    {
        tr[x] += 1;
        x += lowbit(x);
    }
}
ll query(int x)
{
    ll ans = 0;
    while (x > 0)
    {
        ans += tr[x];
        x -= lowbit(x);
    }
    return ans;
}
void solve()
{
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        tr[i] = 0;
    for (int i = 1; i <= n; i++)
    {

        cin >> a[i];
        if (a[i] < i)
        {
            ans += query(a[i] - 1);
            add(i);
        }
    }
    cout << ans << endl;
    return;
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

G. Good Key, Bad Key

题目

题目大意：有n宝箱，每一个宝箱都有一个价值，只能从小到大依次打开每个箱子，且每个箱子必须打开。可以用两种钥匙打开：

好钥匙：花费k元

坏钥匙：不花钱，但是后面每个箱子内的价值/2向下取整

思路：动态规划

状态表示：f[i][j]表示前i个宝箱中用了多少把坏钥匙，我第一次这样想的时候，觉得这样不爆内存了吗，n最大1e5，后来我才发现，每一个宝箱的价值最大是1e9，最多需要用30把坏钥匙后价值就变为0了，不用在管30把钥匙之后的情况了。所以这样很多人写这道题疑惑的一个点吧。

状态计算：
j == 0，表示从1到现在没用过一把坏钥匙，所以f[i][j] = f[i-1][j] + a[i] - k
j != 0 ，表示从1到现在总共用了j把坏钥匙，但是这里还要分两种情况：
-   第i个箱子用了第j把坏钥匙：`f[i][j] = f[i-1][j-1] + a[i]/(2^j) - k` 
-   第i个箱子没用坏钥匙：`f[i][j] = f[i-1][j] + a[i]/(2^j)`

两个取最大值即可。
写动态规划的题就主要在如何将状态转移上。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e5 + 10;
int a[N];
ll f[N][35];
int n, k;
ll p[35];
void solve()
{
    cin >> n >> k;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= 32; j++)
            f[i][j] = -0x3f3f3f3f;
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = f[i - 1][0] + a[i] - k;
        for (int j = 1; j <= 30; j++)
            f[i][j] = max(f[i - 1][j] + (a[i] / p[j]) - k, f[i - 1][j - 1] + a[i] / p[j]);
        for (int j = 0; j <= 30; j++)
            ans = max(ans, f[i][j]);
    }

    cout << ans << endl;
    return;
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    p[0] = 1;
    for (int i = 1; i <= 32; i++)
        p[i] = p[i - 1] * 2;
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Codeforces Round #806 (Div. 4) 题解

A YES or YES?

B. ICPC Balloons

D. Double Strings

E. Mirror Grid

F. Yet Another Problem About Pairs Satisfying an Inequality

G. Good Key, Bad Key

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

Codeforces Round #806 (Div. 4) 题解

A YES or YES?

B. ICPC Balloons

D. Double Strings

E. Mirror Grid

F. Yet Another Problem About Pairs Satisfying an Inequality

G. Good Key, Bad Key

热门文章

最新文章

相关电子书