Educational Codeforces Round 22 题解

A. The Contest

题目比较长，读懂后，模拟即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int n, m, x, l, r, sum;
int main()
{
    while(~scanf("%d",&n)){
        sum=0;
        for(int i=0; i<n; i++){
            scanf("%d",&x);
            sum+=x;
        }
        scanf("%d",&m);
        int ans = 0;
        bool flag = 0;
        for(int i=0; i<m; i++){
            scanf("%d%d",&l,&r);
            if(flag) continue;
            if(l>=sum&&r>=sum){
                ans = l;
                flag = 1;
            }
            else if(r>=sum&&l<sum){
                ans = sum;
                flag = 1;
            }
        }
        if(flag==1) printf("%d\n", ans);
        else printf("-1\n");
    }
    return 0;
}

B. The Golden Age

枚举暴力

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL x,y,l,r;
LL mul(LL x, LL y){
    if(double(x)*(double)y>=1e18) return r+1;
    return x*y;
}
vector <LL> v;
int main(){
    while(~scanf("%lld%lld%lld%lld", &x,&y,&l,&r))
    {
        v.clear();
        for(LL i=1; i<=r; i=mul(i,x)){
            for(LL j=1; i+j<=r; j=mul(j,y)){
                if(l<=i+j){
                    v.push_back(i+j);
                }
            }
        }
        v.push_back(l-1);
        v.push_back(r+1);
        sort(v.begin(), v.end());
        LL ans = 0;
        for(int i=0; i<v.size()-1; i++){
            ans = max(ans, v[i+1]-v[i]-1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

C. The Tag Game

题意：给你一个无向有根树，根节点为1，有两个人，A在节点1，B在节点X，AB轮流走，B先走，每次可以原地不动或是向相邻节点移动一次。A想最快抓到B，B想最慢被抓到，问什么时候A抓到B。
解法：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+7;
vector <int> v[maxn];
int n, x, dep[maxn], ans;
void dfs1(int u, int pa, int d){
    dep[u] = d;
    for(int son : v[u]){
        if(son == pa) continue;
        dfs1(son, u, d+1);
    }
}
int maxdep;
void dfs2(int u, int pa){
    if(dep[u]<=maxdep) return;
    ans = max(ans, dep[u]);
    for(int son : v[u]){
        if(son == pa) continue;
        dfs2(son, u);
    }
}
int main()
{
    scanf("%d %d", &n, &x);
    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs1(1,1,0);
    ans = 0;
    maxdep = dep[x]/2;
    dfs2(x,x);
    printf("%d\n", ans<<1);
    return 0;
}

D. Two Melodies

题意：求两个不相交的子集长度之和最大是多少，能放入同一子集的条件是首先顺序不能变，然后每一个相邻的要么相差1或者相差7的倍数。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int n,a[maxn],dp[maxn][maxn],maxmod[8],maxnum[100010];

int main()
{
    while(~scanf("%d", &n)){
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        memset(dp, 0, sizeof(dp));
        int ans = 0;
        for(int i=0;i<=n; i++){
            memset(maxnum,0,sizeof(maxnum));
            memset(maxmod,0,sizeof(maxmod));
            for(int j=1; j<=i; j++){
                maxmod[a[j]%7] = max(maxmod[a[j]%7], dp[i][j]);
                maxnum[a[j]] = max(maxnum[a[j]], dp[i][j]);
            }
            for(int j=i+1; j<=n; j++){
                dp[i][j] = max(dp[i][j], dp[i][0]+1);
                dp[i][j] = max(dp[i][j], maxmod[a[j]%7]+1);
                dp[i][j] = max(dp[i][j], maxnum[a[j]-1]+1);
                //dp[i][j] = max(dp[i][j], maxnum[a[j]]+1);
                dp[i][j] = max(dp[i][j], maxnum[a[j]+1]+1);
                maxmod[a[j]%7] = max(maxmod[a[j]%7], dp[i][j]);
                maxnum[a[j]] = max(maxnum[a[j]], dp[i][j]);
                dp[j][i] = dp[i][j];
                ans = max(ans, dp[i][j]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

E. Army Creation

题意：n个数a[i],q次询问,n,a[i],q<=1e5。每次问[l,r]内最多可以选多少个数,满足同一个数的出现次数不超过k?

解法：设b[i] 从i开始数k个和a[i]相同的数的位置,不存在设为n+1。则[l,r] 只要b[i]>r的数都能可以被选上,转化为求区间[l,r]内有多少个数>=r。题目要求在线所以套用主席树，建立权值线段树,前缀i内,第[l,r]大的数有多少个,ans=前缀r内[r,inf]个数-前缀i-1内[r,inf]个数。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, q, k, a[maxn], b[maxn];
vector <int> pos[maxn];
struct node{
    int l,r,sum;
}T[maxn*40];
void pre_deal(){
    for(int i=n; i>=1; i--){
        int sz = pos[a[i]].size();
        if(sz < k) b[i] = n+1;
        else b[i] = pos[a[i]][sz-k];
        pos[a[i]].push_back(i);
    }
}
int cnt, root[maxn];
int build(int l, int r){
    int rt = ++cnt;
    T[rt].sum = 0, T[rt].l = T[rt].r = 0;
    if(l == r) return rt;
    int mid = (l+r)/2;
    T[rt].l = build(l, mid);
    T[rt].r = build(mid+1, r);
    return rt;
}
void update(int l, int r, int &x, int y, int pos){
    T[++cnt] = T[y], T[cnt].sum++, x = cnt;
    if(l == r) return;
    int mid = (l+r)/2;
    if(pos <= mid) update(l, mid, T[x].l, T[y].l, pos);
    else update(mid+1, r, T[x].r, T[y].r, pos);
}
int query(int l, int r, int c, int L, int R){
    if(L <= l && r <= R) return T[c].sum;
    int mid = (l+r)/2, ans=0;
    if(L <= mid) ans += query(l, mid, T[c].l, L, R);
    if(mid < R) ans += query(mid+1, r, T[c].r, L, R);
    return ans;
}
int main()
{
    while(~scanf("%d %d", &n,&k)){
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        pre_deal();
        cnt = 0;
        root[0] = build(1, n+1);
        for(int i=1; i<=n; i++) update(1, n+1, root[i], root[i-1], b[i]);
        scanf("%d", &q);
        int l, r, last = 0;
        while(q--){
            scanf("%d %d", &l, &r);
            l = (l+last)%n+1;
            r = (r+last)%n+1;
            if(l > r) swap(l, r);
            int ans = query(1, n+1, root[r], r+1, 2e5) - query(1, n+1, root[l-1], r+1, 2e5);
            printf("%d\n", ans);
            last = ans;
        }
        return 0;
    }
}

F. Bipartite Checking

蒟蒻不会啊，暂时补不了。QAQ