Educational Codeforces Round 65 (Rated for Div. 2)题解

Educational Codeforces Round 65 (Rated for Div. 2)题解

题目链接

A. Telephone Number

水题，代码如下：

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int a[N] ;
int n, T;
char s[N] ;
int main() {
    cin >> T;
    while(T--) {
        cin >> n;
        scanf("%s", s + 1) ;
        int fir = 1;
        for(;fir <= n; fir++) if(s[fir] == '8') break ;
        if(n - fir + 1 >= 11) cout << "YES" << '
' ;
        else cout << "NO" << '
' ;
    }
    return 0;
}

B. Lost Numbers

现在cf B题都开始交互了= =。
这个题直接询问((1,2),(2,3),(3,4),(4,5))即可解出前5个，剩下一个就确定了。
判断是否成立的话我是直接随机的，毕竟长度比较小。
代码如下：

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10;
// 0 3, 1 1  = 64
int b[N][N] ;
int c[N] ;
int n, T;
int main() {
    srand(time(NULL));
    for(int i = 1; i <= 4; i++) {
        printf("? %d %d
", i, i + 1);
        fflush(stdout);
        cin >> b[i - 1][i] ;
    }
    vector <int> a;
    a.push_back(4);
    a.push_back(8);
    a.push_back(15);
    a.push_back(16);
    a.push_back(23);
    a.push_back(42);
    while(1) {
        int f = 1;
        for(int i = 0; i < 4; i++) {
            if(a[i] * a[i + 1] != b[i][i + 1]) f = 0;
        }
        if(f) break ;
        random_shuffle(a.begin(), a.end());
    }
    printf("!");
    for(auto v : a) printf(" %d",v);
    printf("
") ;
    fflush(stdout) ;
    return 0;
}

C. News Distribution

并查集水题，维护每个集合拥有元素的个数即可。
代码如下：

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
int n, m;
int f[N], sum[N];
int find(int x) {
    return f[x] == x ? f[x] : f[x] = find(f[x]) ;
}
void Union(int x, int y) {
    int fx = find(x), fy = find(y) ;
    if(fx != fy) {
        f[fx] = fy;
        sum[fy] += sum[fx] ;
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0) ;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) f[i] = i, sum[i] = 1;
    for(int i = 1; i <= m; i++) {
        int k, last = -1;
        cin >> k;
        int x;
        for(int i = 1; i <= k; i++) {
            cin >> x;
            if(last == -1) last = x;
            else Union(last, x) ;
        }
    }
    for(int i = 1; i <= n; i++) {
        int fa = find(i);
        cout << sum[fa] << ' ';
    }
    return 0;
}

D. Bicolored RBS

我这个一开始也写的并查集来找，最后还是一直没有A。。。后面发现其实简单的，我原来的写法则要讨论很多的情况。
因为给定的括号串一定是合法的，所以配对的两个括号它们所在位置的奇偶性一定是相同的。
因为我们要求深度最大最小，那么我们对于左括号，一个给1，一个给0就行了，这样可以使得尽量两边都最小。如果对于一个')'，给它的颜色为0，那么后面也接着从0开始染色，因为如果把中间已经匹配了的消去，那么就可以保证染色是1，0，1，0...这样。
代码如下：

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n;
char s[N] ;
int main() {
    int c = 0;
    cin >> n;
    scanf("%s", s + 1) ;
    for(int i = 1; i <= n; i++) {
        if(s[i] == '(') {
            ++c;
            cout << (c & 1);
        } else {
            cout << (c & 1);
            --c;
        }
    }
    cout << '
' ;
    return 0;
}

E. Range Deleting

删去值域为([l,r])的数后，如果剩下的数满足条件，那么我们就可以得到(down[l-1]<up[r+1])，这里的(down[i])表示值为i并且满足前面的值满足单调分布时的最大位置，(up[i])则表示最小位置。
然后我们枚举枚举下界，来确定上界就行了，下界增大时，上界不会减小，所以复杂度是(O(n))的。
这个题的关键就是能够想到维护值域的前缀、后缀信息。

代码如下：

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f;
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int n, m;
int a[N], up[N], dw[N], mn[N], mx[N];
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) mn[i] = n + 1;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] ;
        mn[a[i]] = min(mn[a[i]], i) ;
        mx[a[i]] = max(mx[a[i]], i) ;
    }
    dw[0] = 0;
    for(int i = 1; i <= m; i++) {
        if(dw[i - 1] < mn[i]) {
            dw[i] = max(dw[i - 1], mx[i]) ;
        } else dw[i] = n + 2;
    }
    up[m + 1] = n + 1;
    for(int i = m; i >= 1; i--) {
        if(up[i + 1] > mx[i]) {
            up[i] = min(mn[i], up[i + 1]);
        } else up[i] = -1;
    }
    int j = 2;
    ll ans = 0;
    for(int i = 0; i < m; i++) {
        while(j <= m && (i + 1 >= j || dw[i] > up[j])) ++j;
        if(dw[i] < up[j]) ans += m - j + 2;
    }
    cout << ans;
    return 0;
}

F. Scalar Queries

填坑来了...
这是一个十分巧妙的题。反正我没想出来...
题目中定义了(f(l,r)=sum_{i=1}^{r-l+1}b_i*i)，这里的(b_i)就是原数组(a_1,a_2,cdots,a_n)中的(a_l,a_{l+1},cdots,a_{r})排序过后的值。
然后题目要求计算(sum_{1leq lleq rleq n}f(l,r))。

直接考虑有点麻烦，我们就可以考虑每一个数的贡献。
假设现在考虑的为(a_i)，那么包含它的区间就有(i*(n-i+1))个，对于每一个区间，假设比(a_i)小的数的个数为(x_i)，那么此时(a_i)的贡献就为((x_i+1)*a_i)，我们对于每个区间的1提出来，那么总共就是(i*(n-i+1)*a_i)。易知最终的答案就为((sum_{j=1}^{i*(n-i+1)}x_j)*a_i)。
现在我们的任务就是统计包含(a_i)的所有区间中，比(a_i)小的数的个数。
此时我们也转换一下，考虑每一个数的贡献，对于在(a_i)左边的数，其贡献就为(j*(n-i+1));在右边的贡献就为(k*i)，这里(j,k)分别指从左边开始第几个，从右边开始第几个。因为左右两边等价，我们分析左边：((n-i+1)*sum_{j=1}^{i}j*[a_j<a_i])。
右边求和的式子，我们用树状数组就可以解决了。

关键在于这两次转化。cf题解里面全是用的数学公式来推导，其实也没有那么麻烦，但感觉这进一步加深了我对数学思维在竞赛中应用的理解吧...
代码如下：

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5, MOD = 1e9 + 7;
int n;
ll a[N], b[N], c[N];
ll s[2][N] ;
int lowbit(int x) {
    return x & (-x) ;
}
ll query(int x) {
    ll ans = 0;
    for(ll i = x; i > 0; i -= lowbit(i)) ans += c[i] ;
    return ans ;
}
void update(int x, int val) {
    for(int p = x; p < N; p += lowbit(p)) c[p] += val ;
}
void add(ll &x, ll y) {
    x += y;
    if(x >= MOD) x %= MOD ;
}
ll mul(ll x, ll y) {
    x *= y;
    if(x >= MOD) x %= MOD ;
    return x;
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
    sort(b + 1, b + n + 1);
    int D = unique(b + 1, b + n + 1) - b - 1;
    ll ans = 0;
    for(int k = 0; k < 2; k++) {
        memset(c, 0, sizeof(c)) ;
        for(int i = 1; i <= n; i++) {
            int p = lower_bound(b + 1, b + D + 1, a[i]) - b;
            s[k][i] = query(p) ;
            update(p, i) ;
        }
        reverse(a + 1, a + n + 1) ;
    }
    reverse(s[1] + 1, s[1] + n + 1) ;
    for(int i = 1; i <= n; i++) {
        add(ans, mul(a[i], mul(i, n - i + 1))) ;
        add(ans, mul(a[i], mul(s[0][i], n - i + 1))) ;
        add(ans, mul(a[i], mul(s[1][i], i))) ;
    }
    cout << ans;
    return 0;
}