1020LCA模拟赛

· · 个人记录

比赛网址

A

观察可得，汉语操作实质上是在 N 后面插入 V，英语操作为在 N 前面或后面插入 V。所以，汉语和英语都不合法的情况只有有两个连续的 N 或者字符串全为 V。汉语还有一种不合法的情况是第一个字符为 V。

void solve(){
    string s;
    cin>>s;
    int a=1,b=1;
    if(s[0]=='V'){
        b=0;
    }
    int ff=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='N') ff=1;
    }
    if(!ff){
        cout<<"0 0\n";
        return ;
    }
    for(int i=0;i<s.size()-1;i++){
        if(s[i]=='N'&&s[i+1]=='N'){
            a=b=0;
            break;
        }
    }
    cout<<a<<' '<<b<<endl;
}

B

考虑dp，设 dp_{i,j} 为走到 (i,j) 的最小翻转次数。

我们考虑什么时候会产生贡献，不难发现，如果我们走的这一步是从0走到1，必须翻转一次矩阵使得能走。

所以dp转移方程为：

dp_{i,j}=\min(dp_{i-1,j}+[a_{i-1,j}=0 \land a_{i,j}=1],dp_{i,j-1}+[a_{i,j-1}=0 \land a_{i,j}=1] )

最后输出 dp_{n,m} 即可。

但是，题目中有个条件，是翻转面积大于1的矩形，那么我们需要特判所有 n=1 的情况。

void solve(){
    memset(dp,0x3f,sizeof dp);
    cin>>n>>m;
    int f=0;
    int cnt0=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) {
            cin>>a[i][j];
            if(a[i][j]==1) cnt0++;
        }
    }
    if((n==1&&m==1&&a[1][1]==1)||(n==1&&m==2&&cnt0==1)||(m==1&&n==2&&cnt0==1)){
        cout<<"Impossible\n";
        return ;
    }
    if(n==1){
        if(m>=3){
            if(cnt0==1){
                cout<<2<<endl;
                return ;
            }
        }
    }
    if(m==1){
        if(n>=3){
            if(cnt0==1){
                cout<<2<<endl;
                return ;
            }
        }
    }
    dp[0][1]=dp[1][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=min(dp[i][j],dp[i-1][j]+(!a[i-1][j]&&a[i][j]));
            dp[i][j]=min(dp[i][j],dp[i][j-1]+(!a[i][j-1]&&a[i][j]));

        }
    }  
    cout<<dp[n][m]<<endl;
}

C

这道题的代码还没有写。

不妨我们首先考虑对操作次数分讨。

如果不进行操作，那么答案就是树的直径。

如果进行一次操作，考虑删掉根节点与其儿子的一条边，然后再连，观察特殊性质可得，进行一次的答案即为根节点子树中的最大直径与从根节点到最低端的一个最长链。

如果进行两次操作，即把两个直径改成了链，所以我们找出两个子树最长直径即可。

还有一种情况是两个直径在一个子树内。

树形dp解决即可。

D

只会 h=1 的情况。

由于题目中说明了输入的图的黑色联通块一定为四联通，所以只有两种情况，一种为全是黑点，另一种为其他情况。

全是黑点很好考虑，无论几级分型都只有一个联通块。

其他情况，设输入的图中有 c 个黑点，求 k 级分型，那么答案即为 c^{k-1}。