2025寒假专场1

compaq · 2025-01-06 18:17:56 · 题解

101相同矩阵

因为可以上移，左移，所以对于每一行的字符串都复制一遍，然后接到后面，然后再垂直复制一遍。

也就是原来字符串的大小是h行w列，现在是2h \times 2w

答案就在这个2h \times 2w中能否找到B字符串即可，数据范围较小，直接暴力匹配，时间复杂度为h^2 \times w^2

#include<bits/stdc++.h>
using namespace std;
const int N = 100;

string a[N], b[N], mycp[N];
int h, w;

bool check(int x, int y){
    for(int i = 1; i <= h; i++){
        if(mycp[x].substr(y, w) == b[i]){
            x++;
            if(x > 2 * h) return false;
        }
        else
            return false;
    }
    return true;
}

int main(){

    cin >> h >> w;

    for(int i = 1; i <= h; i++) cin >> a[i];

    for(int i = 1; i <= h; i++) cin >> b[i];

    for(int i = 1; i <= h; i++) mycp[i] = a[i] + a[i];

    for(int i = h + 1; i <= h + h; i++) mycp[i] = mycp[i - h];

    for(int i = 1; i <= h + h; i++){
        for(int j = 0; j < 2 * w; j++){
            if(j + w - 1 > 2 * w) break;
            if(check(i, j)){
                puts("Yes");
                return 0;
            }
        }
    }
    puts("No");
    return 0;
}

102交叉

枚举每个'#'，然后进行X扩展即可

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;

int h, w;
char c[N][N];
int s[N];

int main(){
    cin >> h >> w;

    for (int i = 1; i <= h; i ++)
        for (int j = 1; j <= w; j ++)
            cin >> c[i][j];

    for (int i = 2; i < h; i ++)
        for (int j = 2; j < w; j ++)
            if (c[i][j] == '#'){
                int deep = 0;
                while (i + deep + 1 <= h && i - deep + 1 >= 1 && 
                j - deep + 1 >= 1 && j + deep + 1 <= w && 
                c[i + deep + 1][j - deep - 1] == '#' && 
                c[i + deep + 1][j + deep + 1] == '#' && 
                c[i - deep - 1][j - deep - 1] == '#' && 
                c[i - deep - 1][j + deep + 1] == '#')
                    deep ++;
                s[deep] ++;
            }

    for (int i = 1; i <= min(h, w); i ++)
        cout << s[i] << " ";

    return 0;
}
/*
枚举每一个 # ,进行X扩展即可，注意边界 
*/

103AABCC

筛选出质数范围：因为N \leq 10^{12}, 所以筛出10^6以内的质数。

根据条件，a^5 \leq N ,则a是不超过300的质数。 再根据条件范围枚举即可。

#include <bits/stdc++.h>

#define int long long 

using namespace std;

const int  N = 1e6 + 10;

int n;
vector<int> prime;
bool st[N];

void div(int x){
    for (int i = 2; i <= x; i ++){
        if (!st[i]) prime.push_back(i);
        for (int j = 0; prime[j] <= x / i; j ++){
            st[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

signed main(){
    cin >> n;   

    div(N);

    //cout << prime.size() << endl;
    int res = 0;
    for (int i = 0; i < 62; i ++)
        for (int j = i + 1; prime[i] * prime[j] * prime[j] * prime[i] * prime[j] <= n; j ++)
            for (int k = j + 1; prime[i] * prime[j] * prime[k] * prime[i] * prime[k] <= n; k ++)
                res ++;

    cout << res << endl;
    return 0;
}

104更多的假期

假设原S中的'x'的数量为p，若k > p，则需要k/p个完整的S，剩余的k \% p个'x'的数量，一部分在最前面的一段S中，一部分在最后一段的S中。

枚举在最前面的S的开始位置L, 再二分枚举最后一段中结束的位置R。

注意计算[L, R]之间的‘x’的数量。

时间复杂度为nlog(n*m)

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 3e5 + 10;

int n, m, k, p;
int f[N], r[N];
string s;

bool check(int L, int R){
    int cnt;
    if(R <= n) cnt = f[R] - f[L - 1];
    else cnt = r[L] + f[R % n] + (R - n) / n * p; // R比你大的话，则第一段的个数，最后一段的个数，再加上中间的个数 
    return cnt <= k;
}

signed main(){

    cin >> n >> m >> k >> s;

    s = ' ' + s;
    for (int i = 1; i <= n; i ++)
        f[i] = f[i - 1] + (s[i] == 'x'), p += (s[i] == 'x');

    for (int i = n; i >= 1; i --)
        r[i] = r[i + 1] + (s[i] == 'x');

    int res = 0, ans = 0;
    for (int i = 1; i <= n; i ++){
        int  L = i, R = n * m;
        while (L <= R){
            int mid = (L + R) / 2;
            if (check(i, mid)) ans = mid, L = mid + 1; // 从i开始的，到mid这段区间内x的数量 
            else R = mid - 1;
        }
        res = max(res, ans - i + 1);
    }

    cout << res << endl;
    return 0;
}

105P-smoonth数