Educational Codeforces Round 23 题解

A. Treasure Hunt

题意：给定一个起点一个终点坐标，然后用题目中给的四种方法走任意次（X,Y的值在下一行输入）能从起点走到终点就输出YES，反之NO。解法：容易发现，(a,b)变换成了(a+k1x, b+k2y)，那么k1和k2的奇偶性一定是相同的，还有一种特殊情况就是k1，k2不是整数，这个可以特判一下就行。

#include <bits/stdc++.h>
using namespace std;
int x1,y1,x2,y2,x,y;

int main(){
    scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x,&y);
    if(abs(x1-x2)%x==0&&abs(y1-y2)%y==0&&(abs(x1-x2)/x)%2==(abs(y1-y2)/y)%2){
        puts("YES");
    }
    else{
        puts("NO");
    }
    return 0;
}

B. Makes And The Product

题意：求三元组(i,j,k)的个数，其中满足a[i]*a[j]*a[k]要最小。
解法：简单排列组合，排序之后算出最小的3个数是什么，然后统计下这3个数的出现次数，然后简单排列组合算就可以了。

#include <bits/stdc++.h>
using namespace std;
long long ans,n,a[100010],cnt1,cnt2,cnt3;

int main(){
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    long long mx1=a[1], mx2 = a[2], mx3 = a[3];
    for(int i=1; i<=n; i++){
        if(a[i]==mx1) cnt1++;
        if(a[i]==mx2) cnt2++;
        if(a[i]==mx3) cnt3++;
    }
    ans = 1;
    long long t = cnt1;
    if(mx2 != mx1){
        t += cnt2;
    }
    if(mx3 != mx2){
        t += cnt3;
    }
    if(t <= 3){
        puts("1");
        return 0;
    }
    if(mx1==mx2&&mx2==mx3){
        ans = cnt1*(cnt1-1)*(cnt1-2)/6;
    }
    else if(mx2==mx3){
        ans=cnt1*(cnt2*(cnt2-1)/2);
    }
    else if(mx1==mx2){
        ans=cnt3*(cnt1*(cnt1-1)/2);
    }
    else{
        ans=cnt1*cnt2*cnt3;
    }
    printf("%lld\n", ans);
}

C. Really Big Numbers
题意：找一个数n，ans为n的各个位之和，n-ans>=s才能称为大数
解法：水题，二分去check就可以了。

#include <bits/stdc++.h>
using namespace std;
long long n, s;
long long f(long long x){
    long long sum=0;
    while(x){
        sum+=x%10;
        x/=10;
    }
    return sum;
}
bool check(long long mid){
    long long x = n-mid+1;
    long long t = f(x);
    if(x-t>=s){
        return true;
    }
    else{
        return false;
    }
}
int main(){
    while(~scanf("%lld%lld",&n,&s)){
        long long l=0, r=n, ans = 0;
        while(l<=r){
            long long mid = (l+r)/2;
            if(check(mid)) ans=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

D. Imbalanced Array
题意：给你n个数a[1..n]定义连续子段imbalance值为最大值和最小值的差，要你求这个数组的imbalance总值
解法：考虑每个位置作为最值向两边的最大拓展，最小值取负号，最大值取正号，求和即可。怎么去找呢？可以维护一个单调递增栈、单调递减栈。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
int n, a[maxn], lmax[maxn], rmax[maxn], lmin[maxn], rmin[maxn];
int stk[maxn];
int main()
{
    while(~scanf("%d", &n)){
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        int top=0;
        for(int i=1; i<=n; i++){
            while(top>0&&a[stk[top-1]]<=a[i]) top--;
            if(top==0) lmax[i]=1;
            else lmax[i]=stk[top-1]+1;
            stk[top++] = i;
        }
        top = 0;
        for(int i=n; i>=1; i--){
            while(top>0&&a[stk[top-1]]<a[i]) top--;
            if(top==0) rmax[i]=n;
            else rmax[i]=stk[top-1]-1;
            stk[top++]=i;
        }
        top = 0;
        for(int i=1; i<=n; i++){
            while(top>0&&a[stk[top-1]]>=a[i]) top--;
            if(top==0) lmin[i]=1;
            else lmin[i]=stk[top-1]+1;
            stk[top++]=i;
        }
        top = 0;
        for(int i=n; i>=1; i--){
            while(top>0&&a[stk[top-1]]>a[i]) top--;
            if(top==0) rmin[i]=n;
            else rmin[i]=stk[top-1]-1;
            stk[top++]=i;
        }
        long long ans = 0;
        for(int i=1; i<=n; i++){
            ans -= 1LL*a[i]*(rmin[i]-i+1)*(i-lmin[i]+1);
            ans += 1LL*a[i]*(rmax[i]-i+1)*(i-lmax[i]+1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

E. Choosing The Commander

题意：1增加一个数，2删除一个数，3求所有数^k

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e6+7;
struct node{
    int ch[maxn][2], val[maxn], root, L;
    int newnode(){
        ch[L][0]=ch[L][1]=-1;
        return L++;
    }
    void init(){
        L=0,root=newnode();
    }
    void insert(int x){
        int now=root;
        for(int j=30; j>=0; j--){
            int go = (x&(1<<j))?1:0;
            if(ch[now][go]==-1){
                ch[now][go]=newnode();
                now = ch[now][go];
            }
            else{
                now=ch[now][go];
            }
            val[now]++;
        }
    }
    void del(int x){
        int now=root;
        for(int j=30; j>=0; j--){
            int go = (x&(1<<j))?1:0;
            if(ch[now][go]==-1){
                ch[now][go]=newnode();
                now = ch[now][go];
            }
            else{
                now=ch[now][go];
            }
            val[now]--;
        }
    }
    int query(int x, int y){
        int num1[32]={0}, num2[32]={0}, cnt1 = 0, cnt2 = 0;
        while(x){
            num1[cnt1++]=x%2;
            x/=2;
        }
        while(y){
            num2[cnt2++]=y%2;
            y/=2;
        }
        int ans = 0;
        int now=root;
        for(int j=30; j>=0; j--){
            if(num2[j]==0){
                if(ch[now][num1[j]]==-1) break;
                now = ch[now][num1[j]];
            }
            else{
                if(ch[now][num1[j]]) ans+=val[ch[now][num1[j]]];
                if(ch[now][!num1[j]]==-1) break;
                now = ch[now][!num1[j]];
            }
        }
        return ans;
    }
}trie;

int main(){
    int q;
    scanf("%d", &q);
    trie.init();
    for(int i=1; i<=q; i++){
        int op, x, y;
        scanf("%d %d", &op, &x);
        if(op == 1) trie.insert(x);
        else if(op == 2) trie.del(x);
        else{
            scanf("%d", &y);
            printf("%d\n", trie.query(x,y));
        }
    }
    return 0;
}

F. MEX Queries
题意：如题：http://codeforces.com/contest/817/problem/F
解法：这道题首先要离散化，这道题唯一需要注意的也就是离散化，我们考虑一下答案可能是什么，只可能是1，l, r+1。所以我们把这3个点丢进去离散化就可以了。接下来就remove操作就是将l-r区间赋值为0， add操作就是将l-r区间赋值为1，而invert操作就是区间取xor，通过重新计算区间和值进行实现。然后每次询问就是查询最左边的0的位置，可以通过维护区间和值进行查询.。时间复杂度O(qlog(q)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
typedef long long LL;
int n;
struct Q{
    int op;
    LL l,r;
}q[maxn];
struct node{
    int l,r,len,tag,rev,sum;
}tree[maxn*50];
int cnt = 0;
unordered_map <LL, int> mp;
LL x[10*maxn];
void build(int l, int r, int rt)
{
    tree[rt].l=l,tree[rt].r=r,tree[rt].tag=-1,tree[rt].sum=0,tree[rt].rev=0, tree[rt].len = r-l+1;
    if(l==r) return;
    int mid = (l+r)/2;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
}
void pushup(int rt){
    tree[rt].sum = tree[rt*2].sum + tree[rt*2+1].sum;
}
void pushdown(int rt){
    if(tree[rt].tag!=-1){
        tree[rt*2].tag=tree[rt].tag;
        tree[rt*2+1].tag=tree[rt].tag;
        tree[rt*2].sum=tree[rt*2].len*tree[rt].tag;
        tree[rt*2+1].sum=tree[rt*2+1].len*tree[rt].tag;
        tree[rt*2].rev=tree[rt*2+1].rev=0;
        tree[rt].tag = -1;
    }
    if(tree[rt].rev){
        tree[rt*2].rev^=tree[rt].rev;
        tree[rt*2+1].rev^=tree[rt].rev;
        tree[rt*2].sum=tree[rt*2].len-tree[rt*2].sum;
        tree[rt*2+1].sum=tree[rt*2+1].len-tree[rt*2+1].sum;
        tree[rt].rev = 0;
    }
}
void update1(int L, int R, int val, int rt){//区间改成val
    if(L<=tree[rt].l&&tree[rt].r<=R){
        tree[rt].sum = val*(R-L+1);
        tree[rt].tag = val;
        tree[rt].rev = 0;
        return;
    }
    pushdown(rt);
    int mid = (tree[rt].l + tree[rt].r)/2;
    if(R<=mid) update1(L,R,val,rt*2);
    else if(L>mid) update1(L,R,val,rt*2+1);
    else{
        update1(L,mid,val,rt*2);
        update1(mid+1,R,val,rt*2+1);
    }
    pushup(rt);
}
void update2(int L, int R, int rt){//区间翻转
    if(L <= tree[rt].l && tree[rt].r <= R){
        tree[rt].sum = (R-L+1) - tree[rt].sum;
        tree[rt].rev ^= 1;
        return ;
    }
    pushdown(rt);
    int mid = (tree[rt].l+tree[rt].r)/2;
    if(R<=mid) update2(L,R,rt*2);
    else if(L>mid) update2(L,R,rt*2+1);
    else{
        update2(L,mid,rt*2);
        update2(mid+1,R,rt*2+1);
    }
    pushup(rt);
}
int query(int rt)
{
    if(tree[rt].l == tree[rt].r) return tree[rt].l;
    pushdown(rt);
    if(tree[rt*2].sum == tree[rt*2].len){
        return query(rt*2+1);
    }
    else{
        return query(rt*2);
    }
}
int main()
{
    int T;
    while(~scanf("%d", &n)){
        mp.clear();
        cnt = 0;
        for(int i=1; i<=n; i++){
            scanf("%d %lld %lld", &q[i].op,&q[i].l,&q[i].r);
            x[++cnt] = q[i].l;
            x[++cnt] = q[i].l+1;
            x[++cnt] = q[i].r;
            x[++cnt] = q[i].r+1;
        }
        x[++cnt] = 1;
        x[++cnt] = 1e18+5;
        sort(x+1, x+cnt+1);
        cnt = unique(x+1, x+cnt+1)-x-1;
        for(int i=1; i<=cnt; i++){
            mp[x[i]]= i;
        }
        build(1, cnt, 1);
        for(int i=1; i<=n; i++){
            int l = mp[q[i].l];
            int r = mp[q[i].r+1]-1;
            if(q[i].op == 1){
                update1(l, r, 1, 1);
            }
            else if(q[i].op == 2){
                update1(l, r, 0, 1);
            }
            else{
                update2(l,r,1);
            }
            printf("%lld\n", x[query(1)]);
        }
    }
    return 0;
}