codeforces1301解题报告

A.Three Strings

【题意】

给出三个长度为 $n$ 的字符串 $a$ , $b$ , $c$ 。对于 $c$ 的每个字符都要和 $a$ 或 $b$ 中对应位置的字符交换，问是否有一种交换方法使得最终 $a$ , $b$ 两个字符串相同。

【思路】

如果 $c$ 中的每个字符都与 $a$ 或 $b$ 中对应位置的字符相同，那么肯定存在解。否则无解。

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N =  1110;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char a[N],b[N],c[N];
void solve() {
    scanf("%s",a + 1);
    scanf("%s",b + 1);
    scanf("%s",c + 1);
    int n = strlen(a + 1);
    for(int i = 1;i <= n;++i) {
        if(c[i] != a[i] && c[i] != b[i]) {
            puts("NO");return;
        }
    }
    puts("YES");
}
int main() {
    int T = read();
    while(T--) {
        solve();
    }

    return 0;
}

B. Motarack's Birthday

【题意】

有一个长度为 $n$ 的数列a，其中包含一部分-1。现在需要将所有的-1替换为k。需要求出一个k使得最大的相邻两个元素之差的绝对值最小。

【思路】

找到所有与-1相邻的位置中的最大值mx，和最小值mn。显然当 $k=\frac{mx + mn}{2}$ $时答案最小

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 100010,INF = 1e9 + 2;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int a[N];
void solve() {
    int n = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    int mx = -INF,mn = INF;
    a[n + 1] = 0;
    for(int i = 1;i <= n;++i) {
        if(a[i] == -1) continue;
        if(a[i - 1] == -1 || a[i + 1] == -1) {
            mx = max(mx,a[i]);
            mn = min(mn,a[i]);
        }
    }

    int K = (mx + mn) >> 1;
    if(a[1] == -1) a[1] = K;
    int ans = 0;
    for(int i = 2;i <= n;++i) {
        if(a[i] == -1) a[i] = K;
        ans = max(ans,abs(a[i] - a[i - 1]));
    }
    printf("%d %d\n",ans,K);

}
int main() {
    int T = read();
    while(T--) {
        solve();
    }

    return 0;
}

C. Ayoub's function

【题意】

找到一个长度为n并且包含m个1的01串，使得包含1的连续子串数量最大。

【思路】

考虑将问题取反，总子串个数为 $\frac{n(n+1)}{2}$ ，然后找到最少有多少不包含1的子串就好了。

问题也就变为将 $(n-m)$ 个0分成 $m+1$ 段，使得 $\sum\limits_{i=1}^{m+1}\frac{len_i(len_i+1)}{2}$ 最小。

显然将1尽量平均分配时答案最大。

设 $t1=\lfloor\frac{n-m}{m+1}\rfloor，t2 = \lceil\frac{n-m}{m+1}\rceil$ ，求出t1的个数和t2的个数，然后统计答案即可。

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

int main() {
    int T = read();
    while(T--) {
        ll n = read(),m = read();
        ll ans = (n + 1) * n / 2;
        ll t = (n - m) / (m + 1);
        ll k = n - m - (m + 1) * t;
        ans -= (t * (t + 1) / 2) * (m + 1 - k);
        ans -= ((t + 1) * (t + 2) / 2) * k;
        printf("%I64d\n",ans);
    }

    return 0;
}

D. Time to Run

【题意】

对于一个包含n行m列的网格，每相邻的两个格子之间都包含两条方向恰好相反的边。每个格子可以走多次，每条边只能走一次。构造一种方案，使得恰好走k次。

【思路】

每条边都可以被走一次。方案如下：

1.对于每一行都按照‘右下上’的方式走到当前行的最右边，然后再向左走m-1步走回来。

2.向下走1步，重复步骤1.

3.对于最后一行，直接走到最右边，然后走回来

4.向上走n-1步回到原点。

注意细节

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

#define pi pair<int,int>
pi ans[3010];
int n,m,K,a[N][N],anss;
void print() {
    printf("%d\n",anss);
    for(int i = 1;i <= anss;++i) {
        printf("%d ",ans[i].first);
        char c = ans[i].second;
        if(c == 'W') puts("RDU");
        else if(c == 'X') puts("RD");
        else printf("%c\n",c);
    }
    exit(0);
}
void solve() {
    // printf("%d\n",K);
    int p = 1;
    for(;p < m;) {
        // printf("%d\n",K);
        if(K >= 3) {
            K -= 3;
            ++p;
        }
        else {

            if(p - 1) ans[++anss] = make_pair(p - 1,'W');//T = 'RDU'

            if(K == 0) print();
            if(K == 1) {
                ans[++anss] = make_pair(1,'R');
                print();
            }
            if(K == 2) {
                ans[++anss] = make_pair(1,'X');//X = 'RD'
                print();
            }
        }
    }
    if(p - 1)
    ans[++anss] = make_pair(p - 1,'W');
    if(!K) print();
    int t = min(m - 1,K);
    if(t)
    ans[++anss] = make_pair(t,'L');
    K -= t;

}
int main() {
    n = read(),m = read(),K = read();

    if(K > 4 * n * m - 2 * n - 2 * m) {
        puts("NO");return 0;
    }

    puts("YES");
    for(int i = 1;i < n;++i) {
        solve();
        if(K) {
            ans[++anss] = make_pair(1,'D');
            --K;
        }
        else print();
    }

    if(!K) print();

    int t = min(m - 1,K);
    if(t)
    ans[++anss] = make_pair(t,'R');
    K -= t;

    if(!K) print();    
    t = min(m - 1,K);
    if(t)
    ans[++anss] = make_pair(t,'L');
    K -= t;
    if(!K) print();

    t = min(n - 1,K);
    if(t)
    ans[++anss] = make_pair(t,'U');

    K -= t;
    print();
    return 0;
}

E. Nanosoft

【题意】

给出一个 $n\times m$ 的包含4中颜色的布，有Q次询问，每次询问一个子矩阵内有多少个“logo”

logo的形态如下

【思路】

显然每个格子只能作为一个logo的左上角。那么就枚举每个格子，计算出他是多长的logo的左上角。

这个的实现方法，可以给每种颜色赋值，然后二维前缀和一下，然后枚举logo长度，判断每种颜色是否符合条件即可。

然后对于每种logo长度开一个 $n\times m$ 的数组。将符合条件的位置赋为1，然后二位前缀和。

对于每次询问，枚举一下logo长度，然后判断是否存在答案即可。

【代码】

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 510;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char s[N][N];
int f[N][N][N];
ll a[N][N];
ll t1 = 1,t2 = 500 * 500 + 1,t3 = t2 * t2;
ll get(int xl,int yl,int xr,int yr) {
    return a[xr][yr] - a[xr][yl - 1] - a[xl - 1][yr] + a[xl - 1][yl - 1];
}
int check(int k,int xl,int yl,int xr,int yr) {
    return f[k][xr][yr] - f[k][xr][yl - 1] - f[k][xl - 1][yr] + f[k][xl - 1][yl - 1];
}
int main() {

    int n = read(),m = read(),Q = read();
    for(int i = 1;i <= n;++i) {
        scanf("%s",s[i] + 1);
        for(int j = 1;j <= m;++j) {
            if(s[i][j] == 'G') a[i][j] = t1;
            if(s[i][j] == 'Y') a[i][j] = t2;
            if(s[i][j] == 'B') a[i][j] = t3;
        }
    }

    for(int i = 1;i <= n;++i) for(int j = 1;j <= m;++j) a[i][j] += a[i][j - 1];
    for(int i = 1;i <= n;++i) for(int j = 1;j <= m;++j) a[i][j] += a[i - 1][j];


    // for(int i = 1;i <= n;++i) {
    //     for(int j = 1;j <= m;++j) {
    //         printf("%lld ",a[i][j]);
    //     }
    //     puts("");
    // }
    // cout<<get(1,3,2,4)<<endl;
    for(int i = 1;i < n;++i) {
        for(int j = 1;j < m;++j) {
            for(int k = 2;i + k - 1 <= n && j + k - 1 <= m;k += 2) {
                int t = k / 2;
                if(i == 1 && j == 1 && k == 4) {
                    // printf("%lld\n",get(i,j + t,i + t - 1,j + k - 1));
                }
                // if(get(i,j,i + t - 1,j + t - 1)) continue;
                if(get(i,j + t,i + t - 1,j + k - 1) != t1 * t * t) continue;
                if(get(i + t,j,i + k - 1,j + t - 1) != t2 * t * t) continue;
                if(get(i + t,j + t,i + k - 1,j + k - 1) != t3 * t * t) continue;

                // printf("%d %d %d\n",i,j,k);                

                f[k][i][j] = 1;break;
            }
        }
    }

    for(int k = 2;k <= min(n,m);k += 2) {
        for(int i = 1;i <= n;++i) for(int j = 1;j <= m;++j) f[k][i][j] += f[k][i][j - 1];
        for(int i = 1;i <= n;++i) for(int j = 1;j <= m;++j) f[k][i][j] += f[k][i - 1][j];
    }

    while(Q--) {
        int xl = read(),yl = read(),xr = read(),yr = read();
        int ans = 0;
        for(int k = 2;k <= min(xr - xl,yr - yl) + 1;k += 2)
            if(check(k,xl,yl,xr - k + 1,yr - k + 1)) ans = k;

        printf("%d\n",ans * ans);
    }

    return 0;
}