2025寒假专场7

compaq · 2025-01-17 13:45:19 · 题解

回文字符串

入门模拟

重叠薄片

模拟，枚举A和B的相对位置，然后与C进行匹配

#include<bits/stdc++.h>
using namespace std;

int ha,hb,hc,wa,wb,wc;
int a[15][15], b[15][15], c[35][35];
int ans[35][35];
char s[15];

int main(){
    cin >> ha >> wa;
    for(int i = 1;i <= ha; i ++ ){
        cin >> (s + 1);
        for(int j = 1;j <= wa; j ++ )
            a[i][j] = (s[j] == '#');
    }
    cin >> hb >> wb;
    for(int i = 1;i <= hb; i ++ ){
        cin >> (s + 1);
        for(int j = 1;j <= wb; j ++ )
            b[i][j] = (s[j] == '#');
    }
    cin >> hc >> wc;
    for(int i = 1;i <= hc; i ++ ){
        cin >> (s + 1);
        for(int j = 1;j <= wc; j ++ )
            c[i + 10][j + 10] = (s[j] == '#'); //将目标图放在中间的位置，防止合成图出界
    }

    for(int i = 1;i <= hc + 10; i ++ )
        for(int j = 1;j <= wc + 10; j ++ )
            for(int k = 1;k <= hc + 10; k ++ )
                for(int l = 1;l <= wc + 10; l ++ ){
                    memset(ans, 0, sizeof ans);
                    //a图覆盖 (i,j)为a图最左上端点放的位置
                    for(int p = 1;p <= ha; p ++ )
                        for(int q = 1;q <= wa; q ++ )
                            if(a[p][q]) ans[i + p - 1][j + q - 1] = 1; 
                    //b图覆盖 （k,l)为b图最左上端点放的位置
                    for(int p = 1;p <= hb; p ++ )
                        for(int q = 1;q <= wb; q ++ )
                            if(b[p][q]) ans[k + p - 1][l + q - 1] = 1;

                    int f = 1;
                    for(int p = 1;p <= 30; p ++ )
                        for(int q = 1;q <= 30; q ++ )
                            if(ans[p][q] != c[p][q]) f = 0;
                    if(f){
                        cout << "Yes\n";
                        return 0;
                    }
                }
    cout << "No\n";
    return 0;
}

去括号

利用栈进行模拟

右括号也是有可能进入栈，当之前没有左括号的时候，右括号就可以入栈，比如样例4.所以还需要记录左括号数量。

我们维护一个栈，遇到左括号进栈并让计数器加一，遇到右括号，若左括号个数不为0 就弹栈直到遇到左括号，并让计数器减一。由于栈内元素总个数为n，所以总时间复杂度为

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=998244353;
int n,m,f[N][2];
signed main(){
    scanf("%lld%lld",&n,&m);
    f[1][0]=m;
    for(int i=2;i<=n;i++){
        f[i][0]=f[i-1][1];
        f[i][1]=(f[i-1][0]*(m-1)%mod+f[i-1][1]*(m-2)%mod)%mod;
    }
    printf("%lld",f[n][1]);
    return 0;
}

病毒感染

因为有多个起点，我们建立一个超级源点s，它与所有已感染病毒的点连一条边权为 0的无向边。

考虑第一天，我们从超级源点 s开始dijkstra，所有距离不超过 x的点都会被感染病毒。然后新感染的点又会与超级源点s连一条边权为 0的边。很显然当跑到距离大于x时我们就无需继续跑 dijkstra了。

之后第二天重复跑dijkstra，依次类推，时间复杂度是 O(dnlogm)，是无法通过的。

优化，做一遍dijkstra。

假设第一天有k个感染源，我们只需要更新这些新感染的点邻接点点中未被感染的即可。将其加入到优先队列里。第二天就继续从这个优先队列开始dijkstra。

具体的说，假设第i天距离感染源最近的距离为x.