或许以后会有D。

A (link)

题目大意：给定两个整数 \(a,b\) ，每次可以进行一下任意一个操作：

\(a\) 加上任意一个正奇数
\(b\) 减去任意一个正偶数

问是否可以通过若干次操作把 \(a\) 变成 \(b\)

考虑，对于一个比 \(b\) 小的 \(a\) ，若 \(b-a\) 是一个奇数，那么一定可以通过加上一个奇数使 \(a==b\) ；若差为偶数，则一定可以把 \(a\) 加上一个奇数再减去一个偶数使之满足条件。

\(a>b\) 同理。

#include <iostream>

#include <stdio.h>

using namespace std;

long long t, a, b;

int main()

{

    scanf("%lld", &t);

    while (t--)

    {

        scanf("%lld%lld", &a, &b);

        if (a > b)

        {

            if ((a - b) % 2 == 0)

            {

                printf("1\n");

                continue;

            }

            else

            {

                printf("2\n");

                continue;

            }

        }

        else if (a < b)

        {

            if ((b - a) % 2 != 0)

            {

                printf("1\n");

                continue;

            }

            else

            {

                printf("2\n");

                continue;

            }

        }

        else

            printf("0\n");

    }

    return 0;

}

B （link）

题目大意：给定一个长度为 \(n\) 的序列 \(a\) ，另外给定一个长度为 \(m\) 的序列 \(p\) ，您可以进行若干次操作，每次只能交换 \(a_{p_i}\) 和 \(a_{p_{i+1}}\) ，其中 \(i\ \in\ [1,m]\) 。问是否可以在若干次操作后使序列 \(a\) 单调递增。\(1\leq\ m,n,a_i\leq 100\)

注意到数据范围很小，而交换的方式又很像冒泡排序，所以考虑首先冒泡排序，然后用一个 \(s\) 数组记录每次交换的 \(i\) 是否在序列 \(p\) 中出现过，若没有，则直接判定为失败，立即结束；否则在最后输出 YES 即可。时间复杂度 \(\mathcal{O}(n^2)\)。需要注意冒泡排序循环变量的控制。

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

int t,n,m,a[101],p[101],s[10001];

int main()

{

    scanf("%d",&t);

    nzhtl1477:

    while(t--)

    {

        memset(s,0,sizeof(s)); //清空 清空 清空 ！ ！ ！

        scanf("%d%d",&n,&m);

        for(int i=1;i<=n;i++) scanf("%d",&a[i]);

        for(int i=1;i<=m;i++)

        {

            scanf("%d",&p[i]);

            s[p[i]]++;

        }

        for(int i=1;i<=n;i++)

        {

            for(int j=1;j<=n-i;j++)

            {

                if(a[j]>a[j+1])

                {

                    if(s[j])

                    {

                        swap(a[j],a[j+1]);

                    //    printf("a[%d] can swap with a[%d]\n",j,j+1);

                    }

                    else

                    {

                        printf("NO\n");

                        goto nzhtl1477;

                    }

                }

            }

        }

        printf("YES\n");

    }

    return 0;

}

C (link)

题目大意：

给定一个长度为 \(n\) 的字符串 \(s\)，另给一个长度为 \(m\) 的序列 \(p\) ，要求遍历 \(s\) ，若此时遍历到 \(s_i\) ，且 \(i\) 存在于 \(p\) 中，则需要从头遍历 \(s\) 。问最后 \(a\) ~ \(z\) 这26个字符各出现了几遍。

请注意：

一开始的遍历也算一遍
若 \(p\) 序列中有重复的值则也要遍历。

思路：

设答案为 \(ans\) 数组，\(vis\) 数组记录 \(p\) 序列中每个数出现了多少次，\(vis\) 数组记录 \(s\) 中每个字母出现了多少次。

然后从头扫描 \(s\) ，假如当前下标在 \(p\) 中出现过，则更新所有字母的答案。具体请看代码：

#include <bits/stdc++.h>

using namespace std;

int n, m, t, p[200005],vis[200005];

char s[200005];

//注意数组不能开太大，否则会超时

int main()

{

    cin >> t;

    while (t--)

    {

        memset(vis,0,sizeof(vis));

        map<char, int> ans;

        map<char, int> pre;

        //STL map更方便

        cin >> n >> m;

        cin >> s+1; //细节：这里输入“s+1”就会把整个字符串往前移动一维，这样 s 就从1开始了

        for (int i = 1; i <= m; i++)

        {

            cin >> p[i];

            vis[p[i]]++;

        }

        for (int i = 1; i <= n; i++)

        {

            ans[s[i]]++;

            pre[s[i]]++;

            if(vis[i])

                for(int j=97;j<97+26;j++)

                    ans[char(j)] += vis[i]*pre[char(j)]; //当前答案为错误的次数乘上这个字母目前出现的次数

                    //这样可以做到不重不漏

        }

        for (int i = 97; i < 97 + 26; i++)

            cout << ans[char(i)] << " ";

        printf("\n");

    }

    return 0;

}

（未完）

巴特西

【做题笔记】CF1311A、B、C

A (link)

B （link）

C (link)

最新文章

热门文章