EducationalCodeforcesRound115(RatedforDiv.2)（题解）xiaodangao

###Educational Codeforces Round 115 (Rated for Div. 2)

#####A - Computer Game

思路：dfs暴力搜索。

$Code:$

const int N = 1010;
int _,n;
char  a[3][N];
bool st[3][N];
int l[] = {0,0,-1,1,1,1,-1,-1},r[] = {1,-1,0,0,1,-1,1,-1};
void dfs(int x,int y){
    
    st[x][y] = true;
    for(int i=0;i<=7;++i){
        int idx = l[i] + x,idy = r[i] + y;
        if(idx > 2 or idx <= 0 or idy > n or idy <= 0)continue;
        if(st[idx][idy])continue;
        if(a[idx][idy] == '1')continue;
        dfs(idx,idy);
    }
}
void solve(){
    read(_);
    while(_--){
        read(n);
        memset(a,-1,sizeof a);
        memset(st,0,sizeof st);
        scanf("%s%s",a[1]+1,a[2]+1);
        if(a[1][1] == '0')
        dfs(1,1);
        if(st[2][n] == 1)puts("YES");else puts("NO");
    }
}

B - Groups

思路：暴力枚举答案，然后设答案为$(l,r)$ 那么检测答案是否合法。只有当所有人都至少在$(l,r)$其中一天内有空，并且在这两天有空的总人数均大于等于$\frac{n}{2}$ ，那么答案就合法。如果不理解可以自己画图感受一下。

$Code:$

const int N = 100100;
int _,n;
int  a[N][6];
bool st[33];
int l[] = {0,0,-1,1,1,1,-1,-1},r[] = {1,-1,0,0,1,-1,1,-1};
 
void solve(){
    read(_);
    while(_--){
        read(n);
        rep(i,1,n){
            rep(j,1,5){
                read(a[i][j]);
            }
        }
        bool flag = false;
        for(int i=1;i<(1<<5);++i){
            int cnt = 0;
            int now[55],hh = 0;
            for(int j=0;j<=4;++j){
                if((i>>j)&1){
                    now[++hh] = j+1;cnt++;
                }
            }
            bool judge = true;
            int x[33];x[1] = x[2] = 0;
            if(cnt == 2){
                //rep(j,0,4)write((i>>j)&1);pc('\n');
                for(int j=1;j<=n;++j){
                    if(!a[j][now[1]] and !a[j][now[2]]){
                        judge = false;break;
                    }
                    x[1] += (a[j][now[1]] == 1);
                    x[2] += (a[j][now[2]] == 1);
                }
            }else continue;
            if(x[1] < n/2 or x[2] < n/2)judge = false;
            if(judge){flag = true;break;}
        }
        if(flag)puts("YES");else puts("NO");
    }
}

C - Delete Two Elements

思路：因为他让选择两个数，我们首先判断是否有答案，由平均数定义可得：

$\frac{\sum_1^n a[i]}{n} = \frac{a[x] + a[y]}{2}$

所以：

$a[x] + a[y] = \frac{2\sum_1^na[i]}{n}$

因为数组$a$是整数，那么首先判断是否$a[x] + a[y]$可以为整数，然后开个桶记录所有个数，依次枚举每一个$a[i]$作为答案。即可得到答案

复杂度$O(nlogn)$

$Code:$

const int N = 200100;
int _,n;
ll  a[N];
bool st[33];
int l[] = {0,0,-1,1,1,1,-1,-1},r[] = {1,-1,0,0,1,-1,1,-1};
map<ll,ll>S;
void solve(){
    read(_);
    while(_--){
        S.clear();
        read(n);
        ll Sum = 0ll;
        rep(i,1,n){
            read(a[i]);S[a[i]]++;
            Sum += a[i];
        }
        if((Sum * (2ll))%n){
            puts("0");continue;
        }
        ll x = (Sum * (2ll))/n;
        //printf("%lld\n",x);
        ll ans = 0;
        rep(i,1,n){
            ll now = x - a[i] ;
            ll res = S[now];
            if(now == a[i]){
                res--;
            }
            ans+=res;
        }
        write(ans/2);pc('\n');
    }
}

D - Training Session

思路：这个题是让我们选合法三元组数，那么正难则反，我们考虑不符合的个数。首先我们发现如果三元组有一个属性全部相同，那么该三元组一定合法。比如属性$A[x,x,x]$ ，那么属性$B$一定是不相同的，因为如果相同就不满足题目所给限制：任意两个问题$A$属性和$B$属性至少有一个不同。那么我们不符合的个数里只有这种形式$A[x,x,y]，B[a,b,b]$，即两个属性是两个相同的，那我们发现我们可以枚举作为中间的，因为在中间的元素右边必定与其$A$属性相同，左边必定与其$B$属性相同，开个桶分别记录两个属性满足的个数，所以不符合的个数应该是两边相乘得到的结果。最后用总个数减去不符合的个数。

复杂度$O(n)$

$Code:$

const int N = 200100;
int _,n;
ll  a[N];
bool st[33];
int l[N],r[N];
map<ll,ll>S;
pair<int,int>arr[N];
void solve(){
    read(_);
    while(_--){
        read(n);
        fill(l,l+1+n,0);fill(r,r+1+n,0);
        ll sum = (1ll *n*(n-1)*(n-2))/6;
        rep(i,1,n){
            int x,y;
            read(x);read(y);
            l[x]++;r[y]++;
            arr[i] = {x,y};
        }
        ll res = 0ll;
        rep(i,1,n){
            int x = arr[i].first,y = arr[i].second;
            res += 1ll*(l[x]-1)*(r[y]-1);
        }
        write(sum-res);pc('\n');
    }
}

E - Staircases

思路：这个题感觉比较好想，重点应该在代码实现上，将梯子向上、向下搜索。然后在第一个不自由的格子停住，然后相乘维护答案。因为询问$10^4$，并且每次询问暴力复杂度为$O(n)$ 总复杂度为$O(n*q)$ ，可以通过。

$Code:$

const int N = 1010;
int _, n, m, q;
bool st[N][N];
ll a[N];
int l[] = {-1, 0, 1, 0}, r[] = {0, -1, 0, 1};
ll ans;
void work(int x, int y) {
    // 2~3 1~4
    int idx = x, idy = y;
    ll a1 = 0, a2 = 0, b1 = 0, b2 = 0;
    int now = 0;
    bool tmp = st[x][y];
    st[x][y] = false;
    while (idx >= 1 and idx <= n and idy >= 1 and idy <= m and
           st[idx][idy] == false) {
        a1++;
        idx += l[now];
        idy += r[now];
        now++;
        if (now >= 2) now = 0;
    }
    now = 1;
    idx = x, idy = y;
    while (idx >= 1 and idx <= n and idy >= 1 and idy <= m and
           st[idx][idy] == false) {
        a2++;
        idx += l[now];
        idy += r[now];
        now++;
        if (now >= 2) now = 0;
    }
    now = 2;
    idx = x, idy = y;
    while (idx >= 1 and idx <= n and idy >= 1 and idy <= m and
           st[idx][idy] == false) {
        b2++;
        idx += l[now];
        idy += r[now];
        now++;
        if (now >= 4) now = 2;
    }
    idx = x;
    idy = y;
    now = 3;
    while (idx >= 1 and idx <= n and idy >= 1 and idy <= m and
           st[idx][idy] == false) {
        b1++;
        idx += l[now];
        idy += r[now];
        now++;
        if (now >= 4) now = 2;
    }
    if (tmp == true) {
        ans += a1 * b1 + a2 * b2 - 1;
    } else {
        ans -= a1 * b1 + a2 * b2 - 1;
    }
    st[x][y] = !tmp;
}
void solve() {
    read(n);
    read(m);
    read(q);
    rep(i, 1, max(n, m)) {
        ll x1 = max(1ll * (n - i + 1) * (m - i + 1), 0ll);
        if (i != 1) x1 *= 2ll;
        ll x2 = max(1ll * (n - i + 1) * (m - (i + 1) + 1), 0ll) +
                max(0ll, 1ll * (n - (i + 1) + 1) * (m - i + 1));
        // printf("%d:: %lld %lld\n",i,x1,x2);
        ans += x1 + x2;
    }
 
    rep(test, 1, q) {
        int x,y;
        read(x);read(y);
        work(x,y);
        write(ans);pc('\n');
    }
}

F - RBS

思路：我们定义$ “(”$的权值为1， $")"$的权值为-1。我们定义合法字符串$s$为$s$的所有前缀的权值和的最小值大于等于0。只有合法字符串才能够更新答案，否则该字符串的答案就已经确定了，就没必要再进行更新。

• 例如：$(()))$是一个非法字符串，$(())($是一个合法字符串。

考虑动态规划，因为最多只有20个串，所以我们可以用二进制$01$来表示集合。设$f[i]$表示选择集合$i$的最佳答案。我们再维护一个$g$数组，表示在当前集合取最佳答案时的权值和为多少。特别的，如果为非法字符串，那么$g[i] = -1$。考虑转移，根据一般动态规划特性，我们应该枚举该集合中哪一个串是出现在最后。然后用这个来更新答案。我们假设枚举的串编号为$t$ 那么我们转移的集合应该是$i \bigoplus (1<<t)$，那么分类讨论：

• $g[i \bigoplus (1<<t)] = -1$，那么说明已经是非法字符串了，答案不会再增加，所以不用转移。
• $g[i\bigoplus(1<<t)] + min[t] < 0$，注：这里的$min[t]$是指字符串$t$的最小前缀和。那么这表明，虽然$1\bigoplus(1<<t)$并不是非法字符串，但是最后加入字符串$t$之后，就变成了非法字符串，那么我们可以更新$ans$ ,维护两个桶，第一个桶简单代表前缀和的出现次数，第二个桶代表第一次出现比$i$小的前缀和时，$i$的个数。我们这里主要是用第二个桶来完成更新。因为我们已经知道该集合的权值和，那么又知道了经过这一次更新，将变为非法字符串，那么在字符串$t$中，肯定有一个位置，在这个位置之前，原串是合法字符串，在这个位置之后，原串是非法字符串，那我们第二个桶记录$i$总是在第一个桶第一次记录$i-1$时，就是表明在前缀和最低降到$i$时，有多少个位置的前缀和为$i$。我们不难写出转移方程$sum = f[i\bigoplus(1<<t)] + S2[t][-g[i\bigoplus(1<<t)]]$ 。
• $g[1\bigoplus(1<<t] + min[t] \geq 0$ ，这说明经过这轮更新之后，依旧是合法字符串，那么我们可以更新该字符串的$f,g$数组，并且用第一个桶进行维护答案。

因为维护桶用的是$unorderedmap$，所以复杂度$O(n2^{20})$

$Code:$

string a[33];
int n;
int mi[33], Sum[33];
int f[(1 << 21)], g[(1 << 21)];
unordered_map<int, int> S1[22], S2[22];
void solve() {
    ios::sync_with_stdio(false);
    cin >> n;
    rep(i, 0, n - 1) {
        cin >> a[i];
        int now = 0;
        for (auto j : a[i]) {
            if (j == '(')
                now++;
            else
                now--;
            mi[i] = min(mi[i], now);
            //记录前缀个数
            S1[i][now]++;
            //记录第一次不能统计now+1时的数量
            if (S1[i][now] == 1) {
                S2[i][now + 1] = S1[i][now + 1];
            }
        }
        Sum[i] = now;
    }
    int ans = 0;
    for (int i = 1; i < (1 << n); ++i) {
        g[i] = -1;
        //枚举第j个做集合i的最后一个字符串
        for (int j = 0; j < n; ++j) {
            if ((i >> j) & 1) {
                int id = i ^ (1 << j);
                if (g[id] < 0) {
                    continue;
                } else if (g[id] + mi[j] < 0) {
                    int sum = S2[j][-g[id]] + f[id];
                    ans = max(ans, sum);
                } else {
                    int res = S1[j][-g[id]] + f[id];
                    if (f[i] < res) {
                        f[i] = res;
                        
                    }g[i] = Sum[j] + g[id];
                    ans = max(ans,f[i]);
                }
            }
        }
    }
    write(ans);pc('\n');
}

The Sum of Good Numbers

思路：设$A+B=X$且$A \geq B$，那么$A,B$的长度可以有以下几种

• $|A| = |X|-1,|B| = |X|-1$
• $|A| = |X|$

那么第一种情况，我们可以枚举在$a$串中所有长度为$|X|-1$的串来作为答案。重点考虑第二种情况，我们枚举所有长度为$|X|$的串为$A$来判断，我们可以发现确定$A,X$之后，$B$的长度其实是由$X$与$A$的最长公共前缀决定的，因为没有$0$的存在，所以$|A|-lcp(A,X)_{len}$即为$B$的长度，在确定$B$的长度以及$B$的位置后，我们可以取出$B$来进行判断。$B$长度可以在$|A|-lcp(A,X)_{len} \pm2$的范围内都试一下。

那么我们取出$A,B$之后，接下来需要判断$A+B$是否等于$X$，高精度复杂度$O(n^2)$明显不行，我们发现可以利用字符串哈希的方式$O(1)$的判断是否合法。问题就解决了。

复杂度$O(n)$

（摆烂了，代码不写了

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章