2023年9月11日

前面几天去建模，虽然感觉根本过不了。。。。。哎，我们继续回归受制了系列。最近也会总结知识。今天是第二次AK周赛。

ACWING5148 字符串匹配

题目理解，本题是个贪心。题目一点是`B`串可以随意调整顺序，那就非常EZ了。

我们只需要进行对A串B串做一个字符出现次数的统计
先去匹配是否有完全相同的，然后打标记，证明已经被算过了
然后再匹配大小写即可

代码实现

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 200, M = 2e5;

int a[N];
int b[N];
string n, m;
bool st[M];

int main()
{
    cin >> n >> m;


    for(int i = 0 ; i < m.size(); i++)
    {
        int p = int(m[i]);
        b[p]++;
    }

    int resa = 0, resb = 0;
    for(int i = 0 ; i < n.size(); i++)
    {
        int p = int(n[i]);

        if(b[p])
        {
            resa++;
            b[p]--;
            st[i] = true;
        }
    }

    for(int i = 0; i < n.size(); i++)
    {
        if(!st[i])
        {
            int p = int(n[i]);
            if(p < 97 && b[p + 32])
                resb++, b[p + 32]--;
            else if(p >= 97 && b[p - 32])
                resb++, b[p - 32]--;
        }
    }

    cout << resa << " " << resb;

    return 0;
}

ACWING5147 数量

题目理解

该题是DFS，我们枚举各种长度的4和7串的组合即可。

代码实现

#include<iostream>
#include<cstring>
using namespace std;

const int N = 10;

int n, u = 1;
int st[N];
int res;


void dfs(int p)
{
    if(p == u)
    {
        int sum = 0;

        for(int i = 0; i < p; i++)
            sum =  sum * 10 + st[i];

        if(sum <= n)
            res++;

        return;
    }

    st[p] = 4;
    dfs(p+1);
    st[p] = 7;
    dfs(p+1);
}


int main()
{
    cin >> n;
    int t = n;
    while(t)
    {
        memset(st, 0, sizeof st);
        dfs(0);
        t /= 10;
        u += 1;
    }

    cout << res;
    return 0;
}

最大GCD

题目理解

简单数论？？？应该不算吧，就理解题目，就是n / 2。因为1 ~ n中两数，且不相同的最大公约数就是n / 2。

因为最大值是n，如果n是偶数，那么n的越大公约数就是n / 2。
如果n是奇数，那么就是(n - 1) / 2，int自带下取整，所以就是n / 2。

代码实现

#include<iostream>
using namespace std;

int main()

{
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;
        cout << a / 2 << endl;
    }


    return 0;
}

ACWING5199 现代艺术

题目理解

对于我来说，这个题非常棒！是我完全没有做过的类型题。该题目需要完成一个目的就是让移动的消耗最少。
这个题的知识点是三分，因为我之前接触的二分，么办法解决，因为我没法确定是往左移损耗最小还是往右移动损耗最小。
我们经过分析题目可以得到如下图示结果：
每一个人的移动消耗图解

我们可以看出，只有在这个长度为D的区间，损耗是0，往两边都会增加。是一个下凸函数。
下凸函数有个性质，就是多个下凸函数求和，仍为下凸函数。
然后我们就可得到总的损耗变化趋势，如下图。
得到这个趋势，我们取三等分点。我们首先规定，左边的三等分点一定是大于等于右边的三等分点。那么就会有以下两种情况。

很明显根据图示，橘色部分一定不会是答案，那么就可以把我的左边界，赋值为左三等分点！！
右三等分点的情况相同。可以将右三等分点右边的部分去掉！那么最后就可以找到答案啦！！
这个题非常不错！学到了新东西！

代码实现

#include<iostream>
#include<cstring>
using namespace std;

const int N = 5e6;

int a[N], b[N];
int n, m, k;
int main()
{
    cin >> n >> m >> k;

    while(k -- )
    {
        char c;
        int p;
        cin >> c >> p;
        if(c == 'R')
            a[p]++;
        else
            b[p]++;
    }

    int res = 0;
    for(int i = 1; i <= n ; i++)
        for(int j = 1; j <= m; j++)
            if((a[i] + b[j]) % 2)
                res++;

    cout << res;
    return 0;
}