美团春招笔试-3

A 枚举左上角点判断右下角是否越界和=2即可

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
char a[N][N];
int n, m;
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (i + 1 <= n && j + 1 <= m)
            {
                int res = (a[i][j] - '0') + (a[i + 1][j] - '0') + (a[i][j + 1] - '0') + (a[i + 1][j + 1] - '0');
                if (res == 2)
                    ans++;
            }
        }
    }
    cout << ans;
}

B 没有偶数回文串本质上是不存在两个相邻字符一样找出所有连续相同字符数量-1 求和即可

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
char a[N][N];
int n, m;
int main()
{
    cin >> n;
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 0, j = 0; i < s.size(); i++)
    {
        while (j + 1 < s.size() && s[j + 1] == s[i])
            j++;
        ans += (j - i);
        i = j;
    }
    cout << ans;
}

C 位置为W一定不能交换先判断该位置是否i=ai 否直接-1 交换下标将i与目标位置ai连边最后会形成环比如样例2要和3交换连边 2-3-2这个环交换次数为环的大小-1 最后有多个环将环的所有贡献相加即可找环的大小可以dfs 也可以并查集维护

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], st[N];
vector<int> g[N];
int ans;
void dfs(int x, int s, int cnt)
{
    if (st[x])
    {
        if (x == s)
        {
            ans += cnt - 1;
        }
        return;
    }
    st[x] = 1;
    for (auto v : g[x])
        dfs(v, s, cnt + 1);
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    string s;
    cin >> s;
    s = ' ' + s;
    for (int i = 1; i < s.size(); i++)
    {
        if (s[i] == 'R')
        {
            g[i].push_back(a[i]);
        }
        else
        {
            if (i != a[i])
            {
                cout << -1;
                return 0;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!st[i] && s[i] == 'R')
        {
            dfs(i, i, 0);
        }
    }

    cout << ans << endl;
}

D 首先将每个字母和数量取出来从左往右双指针贪心 sum为当前长度 cnt为当前字符个数若sum*cnt<k 则继续往前走，直到找到一个下标j 满足i-j中的字符串长度*种类数>=k 在j中二分取出最小字符数量满足再往右贪心即可不知道哪些细节写错了。。。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
#define int long long
int a[N], s[N];
char c[N];
int n, k, ans;
bool check(int idx, int sum, unordered_map<char, int> mp)
{
    int val = sum + a[idx];
    mp[c[idx]]++;
    int x = mp.size();
    if (--mp[idx] == 0)
        mp.erase(idx);
    // cout << idx << " " << x << " " << val << " " << k << endl;
    if (__int128(x * val) < __int128(k))
        return 1;
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    string s;
    cin >> s;
    int cc = 0, ca = 0, ss = 0;
    unordered_map<char, int> mp, tmp;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] >= 'a' && s[i] <= 'z')
        {
            c[++cc] = s[i];
            tmp[s[i]] = 1;
        }
        if (s[i] >= '0' && s[i] <= '9')
        {
            int tmp = s[i] - '0';
            int j = i;
            while (j + 1 < s.size() && s[j + 1] >= '0' && s[j + 1] <= '9')
            {
                tmp = tmp * 10 + (s[j + 1] - '0');
                j++;
            }
            a[++ca] = tmp;
            ss += tmp;
            i = j;
        }
    }
    if (ss * tmp.size() < k)
    {
        cout << -1;
        return 0;
    }
    int sum = 0;
    for (int i = 1; i <= cc; i++)
    {
        if (a[i] >= k)
        {
            int res = a[i] / k;
            ans += res;
            a[i] -= res * k;
        }
        if (a[i] == 0)
            continue;
        mp.clear();
        int j = i, sum = a[i];
        mp[a[i]] = 1;
        while (j + 1 <= cc && check(j + 1, sum, mp))
        {
            sum += a[j + 1];
            mp[c[j + 1]]++;
            j++;
        }
        cout << i << " " << j << " " << sum << " " << mp.size() << endl;
        if (j + 1 <= cc)
        {
            int l = 1, r = a[j + 1];
            int cnt = mp.count(c[j + 1]) ? mp.size() : mp.size() + 1;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (__int128(mid + sum) * __int128(cnt) >= __int128(k))
                    r = mid;
                else
                    l = mid + 1;
            }
            a[j + 1] -= l;
            ans++;
        }
        i = j;
    }

    cout << ans;
}