2019 Multi-University Training Contest 4

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int sum,ans[N],base,now,n;
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        sum=0;
        scanf("%d",&n);
        for (int i=2; i<=n; i++)
        {
            if (i%2==0)
            {
                ans[i]=1;
            }
            else
            {
                base=1;
                now=i;
                while (now)
                {
                    if ((now&1)==0)
                    {
                        break;
                    }
                    base<<=1;
                    now>>=1;
                }
                if (base>n)
                {
                    sum++;
                    ans[i]=1;
                }
                else
                {
                    ans[i]=base;
                }
            }
        }
        printf("%d\n",sum);
        for (int i=2; i<n; i++)
        {
            printf("%d ",ans[i]);
        }
        printf("%d\n",ans[n]);
    }
}

　

 

 

 

 

#include<bits/stdc++.h>

using namespace std;

int a[100],res,k;

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        for (int i=0; i<16; i++)
        {
            scanf("%d",&a[i]);
        }
        res=0;
        for (int i=0; i<16; i++)
        {
            for (int j=i+1; j<16; j++)
            {
                if (a[i]>0&&a[j]>0&&a[i]>a[j])
                {
                    res++;

                }
            }
        }
        for (int i=0; i<16; i++)
        {
            if (!a[i])
            {
                k=i/4;
                break;
            }
        }
        if (((3-k)%2)==(res%2))
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }

    }
}

　　

 

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll ans,prime[10010],v[10010],tot,n,k;

void get_prime()
{
    for (ll i=2; i<=10000; i++)
    {
        if (!v[i])
        {
            prime[tot++]=i;
        }
        for (ll j=0; prime[j]*i<=10000; j++)
        {
            v[prime[j]*i]=1;
            if (i%prime[j]==0)
            {
                break;
            }
        }
    }
}

ll check(ll l,ll r,ll n)
{
    while (l<r)
    {
        ll mid=(l+r)>>1;
        if (mid*mid*mid<n)
        {
            l=mid+1;
        }
        if (mid*mid*mid>n)
        {
            r=mid-1;
        }
        if (mid*mid*mid==n)
        {
            return mid;
        }
    }
    return l;
}
int main()
{
    ll T;
    get_prime();
    scanf("%lld",&T);
    while (T--)
    {
        ans=0x3f3f3f3f;
        scanf("%lld",&n);
        for (ll i=0; i<tot; i++)
        {
            k=0;
            while (n%prime[i]==0)
            {
                n=n/prime[i];
                k++;
            }
            if (k) ans=min(ans,k);
        }
        if (n>1)
        {
            ll k2=sqrt(n);
            ll k4=sqrt(k2);
            if (k2*k2==n)
            {
                if (k4*k4*k4*k4==n)
                {
                    ans=min(ans,4ll);
                }
                else
                {
                    ans=min(ans,2ll);
                }
            }
            else
            {
                ll k3=check(1,1e6,n);
                if (k3*k3*k3==n) ans=min(ans,3ll);
                else ans=1;
            }
        }
        printf("%lld\n",ans);
    }
}

　

 

#include <bits/stdc++.h>

using namespace std;
const int N = 1000001;
const int maxn=1e6+10;
const int maxm=maxn*10;
struct Node
{
    int val,l,r;
} node[maxm];
int tot,root[maxn];

int build(int l,int r)
{
    int x=++tot;
    if (l<r)
    {
        int mid=(l+r)>>1;
        node[x].l=build(l,mid);
        node[x].r=build(mid+1,r);
    }
    node[x].val=0;
    return x;
}

int update(int rt,int l,int r,int x,int v)
{
    node[++tot]=node[rt];
    rt=tot;
    if (l==r)
    {
        node[rt].val+=v;
        return rt;
    }
    else
    {
        int mid=(l+r)>>1;
        if (x<=mid) node[rt].l=update(node[rt].l,l,mid,x,v);
        else
        {
            node[rt].r=update(node[rt].r,mid+1,r,x,v);
        }
        node[rt].val+=v;
        return rt;
    }
}

int query(int rt1,int rt2,int l,int r,int L,int R)
{
    if (L<=l&&r<=R)
    {
        return node[rt2].val-node[rt1].val;
    }
    else
    {
        int mid=(l+r)>>1,ans=0;
        if (L<=mid) ans+=query(node[rt1].l,node[rt2].l,l,mid,L,R);
        if (mid<R) ans+=query(node[rt1].r,node[rt2].r,mid+1,r,L,R);
        return ans;
    }
}
int a[maxn],n,m,l,r,p,k;

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&m);
        tot=0;
        root[0]=build(1,N);
        for (int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            root[i]=update(root[i-1],1,N,a[i],1);
        }
        int ans=0;
        while (m--)
        {
            scanf("%d%d%d%d",&l,&r,&p,&k);
            l^=ans;
            r^=ans;
            p^=ans;
            k^=ans;
            if (l>r)
            {
                swap(l,r);
            }
            int L=0,R=N;
            while (L<R)
            {
                int mid=(L+R)>>1;
                int sum=query(root[l-1],root[r],1,N,max(0,p-mid),min(N,p+mid));
                if (sum<k)
                {
                    L=mid+1;
                }
                else
                {
                    R=mid;
                }
            }
            ans=R;
            printf("%d\n",R);
        }
    }
}