1.22-1.28 部分补题

[蓝桥杯 2016 省 A] 密码脱落

题意：给定一个回文串，但是有一些字母消失不见了。

问：至少补全多少个字母，使得字符串变回回文串

最开始想一个一个枚举，但是无论怎么写都是错的。

后来被提醒回文串的特性，反转之后还是一样的。

所以要求最少的需要补全的字母，直接求一个正着和反着的字符串的最长公共子序列就行。

void solve() {
    string s1,s2;
    cin >> s1;
    int n = s1.size();
    s2 = ' ' + s1;
    reverse(s1.begin() , s1.end());
    s1 = ' ' + s1;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            f[i][j] = max(f[i-1][j] , f[i][j-1]);
            if(s1[i]==s2[j]) f[i][j] = max(f[i][j] , f[i-1][j-1]+1);
        }
    }
    cout << n-f[n][n] << endl;
}

[蓝桥杯 2022 省 A] 爬树的甲壳虫

甲虫从 i-1 的位置爬到 i 有 Pi 的概率失败。问甲虫爬到树顶的期望值是多少

是个dp递推式，用到了几何概型求期望。

E(x) = 1 / (1 - p)

对于每一步，如果当前一步要前往下一步，可能会掉回去，也可能走上去。

res = (res+1) * 1 / (1 - x/y)。代码如下：

int ksm(int base,int power, int mod) {
    int ans=1;
    while(power) {
        if(power & 1) ans = ans * base % mod;
        base = base * base % mod;
        power >>= 1;
    }
    return ans;
}

void solve() {
    int n;
    cin >> n;
    int res = 0 , mod = 998244353;;
    for(int i=1;i<=n;i++) {
        int x,y;
        cin >> x >> y;
        res=(res+1)*y%mod*ksm(y-x,mod-2,mod)%mod;
    }
    cout << res << endl;
}

PTA：锦标赛

用的胜者树的另一点：败者树

利用两个数组存储值，一个数组存放当前下标值，另一个数组存放当前下标右边的可放置坐标。

然后利用满二叉树的性质，一层一层的往上的递推，若当前位置的两个子节点都不满足条件，输出no

否则更新当前点的值，可放置下标值和最大值。

void solve() {
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=(1<<(n-i));j++) {
            cin >> k[i][j];
            if(i==1) {
                ans[j*2-1]=k[i][j] , id[i][j]=j*2;
            }
            else {
                int maxx = max({k[i][j],k[i-1][j*2-1],k[i-1][j*2]});
                if(k[i][j]<k[i-1][j*2-1] && k[i][j]<k[i-1][j*2]) {
                    cout << "No Solution" << endl;
                    return ;
                }
                if(k[i][j]>=k[i-1][j*2]) {
                    ans[id[i-1][j*2]]=k[i][j];
                    id[i][j]=id[i-1][j*2-1];
                }
                else {
                    ans[id[i-1][j*2-1]]=k[i][j];
                    id[i][j]=id[i-1][j*2];
                }
                k[i][j]=maxx;
            }
        }
    }
    int w;
    cin >> w;
    if(k[n][1]>w) {
        cout << "No Solution" << endl;
        return ;
    }
    ans[id[n][1]]=w;
    for(int i=1;i<=(1<<n);i++) cout << ans[i] << " \n" [i==(1<<n)];
}

CF：

C. Engineer Artem

给出一个原数组，要求一个新数组

新数组的值要么等于该值，要么等于该值加一

只需要让每个紧邻的数奇偶性不同就行了。

但是我当时在傻傻的去想枚举脑子宕机了属于是。

void solve() {
    int n,m;
    cin >> n >> m;
    vector<vector<int>> k(n+10,vector<int>(m+10));
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) cin >> k[i][j];
    }
    for(int i=2;i<=n;i++) {
        if(k[i-1][1]&1) {
            if(k[i][1]&1) k[i][1]++;
        }
        else {
            if(k[i][1]%2==0) k[i][1]++;
        }
    }
 
    for(int j=2;j<=m;j++) {
        if(k[1][j-1]&1) {
            if(k[1][j]&1) k[1][j]++;
        }
        else {
            if(k[1][j]%2==0) k[1][j]++;
        }
    }
 
    for(int i=2;i<=n;i++) {
        for(int j=2;j<=m;j++) {
            if(k[i-1][j]&1 && k[i][j-1]&1) {
                if(k[i][j]&1) k[i][j]++;
            }
            else if(k[i][j]%2==0) k[i][j]++;
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) cout << k[i][j] << (j==m ? endl : ' ');
    }
}