Educational Codeforces Round 33 (Rated for Div. 2)A-F

时间:2021-11-18 11:33:35

总的来说这套题还是很不错的,让我对主席树有了更深的了解

A:水题,模拟即可

Educational Codeforces Round 33 (Rated for Div. 2)A-FEducational Codeforces Round 33 (Rated for Div. 2)A-F
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pii pair<int,int>

using namespace std;

const double g=10.0,eps=1e-12;
const int N=200+10,maxn=200000+10,inf=0x3f3f3f3f;

int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    int p1=1,p2=2;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)
    {
        if(a[i]!=p1&&a[i]!=p2)
        {
            cout<<"NO"<<endl;
            return 0;
        }
        else
        {
            if(a[i]==p2)swap(p1,p2);
            if(p1==1)
            {
                if(p2==2)p2=3;
                else p2=2;
            }
            else if(p1==2)
            {
                if(p2==1)p2=3;
                else p2=1;
            }
            else if(p1==3)
            {
                if(p2==1)p2=2;
                else p2=1;
            }
        }
    }
    cout<<"YES"<<endl;
    return 0;
}
/********************

********************/
A

B:给一个数n,找最大的n的余数是特定数,特定数是二进制前面k+1个1后面k个0的数,公式给出了,直接算出来然后从大到小遍历

这题没给公式的话可能还可以做做,不过也不难推,但是给了公式就相当水了

Educational Codeforces Round 33 (Rated for Div. 2)A-FEducational Codeforces Round 33 (Rated for Div. 2)A-F
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pii pair<int,int>

using namespace std;

const double g=10.0,eps=1e-12;
const int N=200+10,maxn=200000+10,inf=0x3f3f3f3f;

int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i=1;i<=10;i++)
        a[i]=((1<<i)-1)*(1<<(i-1));
    int n;
    cin>>n;
    for(int i=10;i>=1;i--)
    {
        if(n%a[i]==0)
        {
            cout<<a[i]<<endl;
            return 0;
        }
    }
    return 0;
}
/********************

********************/
B

C:找每个连通图里点权值最小相加即可,简单dfs

Educational Codeforces Round 33 (Rated for Div. 2)A-FEducational Codeforces Round 33 (Rated for Div. 2)A-F
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pii pair<int,int>

using namespace std;

const double g=10.0,eps=1e-12;
const int N=100000+10,maxn=200000+10,inf=0x3f3f3f3f;

vector<int>v[N];
bool vis[N];
ll c[N],cnt;
void dfs(int u)
{
    vis[u]=1;
    cnt=min(cnt,c[u]);
    for(int i=0;i<v[u].size();i++)
    {
        if(!vis[v[u][i]])
        {
            dfs(v[u][i]);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            cnt=1e18;
            dfs(i);
            ans+=cnt;
        }
    }
    cout<<ans<<endl;
    return 0;
}
/********************

********************/
C

D:题意:刚开始账户里余额为0,余额不能超过k,每天早上你可以存钱,晚上有交易,可能增减,如果晚上交易为0,那么就需要查询账户,此时的账户余额不能为负数,问最少需要几天存钱,不行输出-1

题解:先求一遍前缀和,然后对前缀和求一遍后缀最大值,然后从前往后扫,每次查询到余额为负的时候就根据后缀最大值来判断,然后加上最大能加的钱数,不能就输出-1

Educational Codeforces Round 33 (Rated for Div. 2)A-FEducational Codeforces Round 33 (Rated for Div. 2)A-F
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pii pair<int,int>

using namespace std;

const double g=10.0,eps=1e-12;
const int N=100000+10,maxn=200000+10,inf=0x3f3f3f3f;

ll a[N],sum[N],maxx[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;ll d;
    cin>>n>>d;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+a[i];
        if(sum[i]>d)
        {
            cout<<-1<<endl;
            return 0;
        }
    }
    maxx[n+1]=-1e18;
    for(int i=n;i>=1;i--)maxx[i]=max(maxx[i+1],sum[i]);
    ll cnt=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0&&sum[i]+cnt<0)
        {
            ll x=max(d-maxx[i]-cnt,(ll)0);
        //    cout<<i<<"++++"<<x<<" "<<cnt<<" "<<maxx[i]<<" "<<d-maxx[i]-cnt<<endl;
            cnt+=x;
         /*   if(sum[i]+cnt>d)
            {
                cout<<-1<<endl;
                return 0;
            }*/
            ans++;
            if(a[i]==0&&sum[i]+cnt<0)
            {
           //     cout<<i<<" "<<sum[i]+cnt<<endl;
                cout<<-1<<endl;
                return 0;
            }
        }
        else if(sum[i]+cnt>d)
        {
            cout<<-1<<endl;
            return 0;
        }
    }
    cout<<ans<<endl;
    return 0;
}
/********************
3 4
-5 3 0
3 5
-5 -5 0
********************/
D

E:题意:给你x,y要求y个数相乘等于x的情况数

题解:组合数,求出x的所有质因数的个数a,然后每次乘上C(y-1+a,y-1),,因为是隔板法,相当于y个盒子中放a个小球,有y-1个隔板,y-1+a个地方放y-1个隔板,所有情况就是C(y-1+a,y-1),没有放的地方就放上1,最后考虑有负数的情况,因为C(n,2)+C(n,4)+...=2^(n-1)乘上这个就好了

Educational Codeforces Round 33 (Rated for Div. 2)A-FEducational Codeforces Round 33 (Rated for Div. 2)A-F
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define pii pair<int,int>
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

using namespace std;

const int g=10.0,eps=1e-9;
const int N=2000000+10,maxn=5000000+10,inf=0x3f3f3f3f;

ll fac[N];
ll quick(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    /*ios::sync_with_stdio(false);
    cin.tie(0);*/
    fac[0]=1;
    for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
    int q;
    scanf("%d",&q);
    while(q--)
    {
        ll x,y,ans=1;
        scanf("%lld%lld",&x,&y);
        for(ll i=2;i*i<=x;i++)
        {
            if(x%i==0)
            {
                ll cnt=0;
                while(x%i==0)cnt++,x/=i;
             //   cout<<cnt<<endl;
                ll inv=quick(fac[y-1]*fac[cnt]%mod,mod-2);
                ans=ans*fac[y-1+cnt]%mod*inv%mod;
            }
        }
        if(x!=1)
        {
            ll cnt=1;
            ans=ans*y%mod;
        }
        printf("%lld\n",ans*quick(2,y-1)%mod);
    }
    return 0;
}
/*******************
C(y-1+x,y-1)*2^(y-1)%mod;
(y-1+x)!
(y-1)!(x)!
*******************/
E

F:给你一棵树,每个节点有一个权值,q个查询每次查询x的子树中与x距离不超过k的权值最小的那个节点,强制在线

题解:主席树维护,先dfs序建树,然后按照树节点深度从小到大来插入每个点,最后查询的时候找1到d【x】+k的那颗主席树,然后查询l【x】到r【x】的最小值就是答案了

总结:主席树一般就是用来维护从1到x(x<=n)的所有区间的,可以方便的维护某一区间的权值,本质来说还是一颗线段树,主要是通过rt来访问是哪颗主席树

Educational Codeforces Round 33 (Rated for Div. 2)A-FEducational Codeforces Round 33 (Rated for Div. 2)A-F
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
//#define ls l,m,rt<<1
//#define rs m+1,r,rt<<1|1
#define pii pair<int,int>

using namespace std;

const double g=10.0,eps=1e-12;
const int N=100000+10,maxn=200000+10,inf=0x3f3f3f3f;

int a[N],d[N],l[N],r[N],num;
int maxd,pos[N],res;
int rt[N*20],ls[N*20],rs[N*20],value[N*20],tot;
vector<int>v[N];
void dfs(int u,int c,int f)
{
    ++num;
    l[u]=num;
    d[u]=c;
    maxd=max(maxd,c);
    for(int i=0;i<v[u].size();i++)
    {
        int x=v[u][i];
        if(x==f)continue;
        dfs(x,c+1,u);
    }
    r[u]=num;
}
void build(int &o,int l,int r)
{
    o=++tot;
    value[o]=1e9+10;
    if(l==r)return ;
    int m=(l+r)>>1;
    build(ls[o],l,m);
    build(rs[o],m+1,r);
}
void update(int &o,int l,int r,int last,int p,int va)
{
    o=++tot;
    ls[o]=ls[last];
    rs[o]=rs[last];
    if(l==r)
    {
        value[o]=va;
        return ;
    }
    int m=(l+r)>>1;
    if(p<=m)update(ls[o],l,m,ls[last],p,va);
    else update(rs[o],m+1,r,rs[last],p,va);
    value[o]=min(value[ls[o]],value[rs[o]]);
}
int query(int o,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)return value[o];
    int ans=1e9+10;
    int m=(l+r)>>1;
    if(L<=m)ans=min(ans,query(ls[o],l,m,L,R));
    if(R>m) ans=min(ans,query(rs[o],m+1,r,L,R));
    return ans;
}
void bfs(int n,int root)
{
    queue<int>q;
    q.push(root);
    res=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
     //   cout<<u<<endl;
        pos[d[u]]=res;//对应深度在哪颗主席树中
        update(rt[res],1,n,rt[res-1],l[u],a[u]);
        res++;
        for(int i=0;i<v[u].size();i++)
        {
            int x=v[u][i];
            if(d[x]==d[u]+1)q.push(x);
        }
    }
}
void print(int o,int l,int r)
{
    cout<<l<<" "<<r<<" "<<value[o]<<endl;
    if(l==r)return ;
    int m=(l+r)>>1;
    print(ls[o],l,m);
    print(rs[o],m+1,r);
}
int main()
{
    /*ios::sync_with_stdio(false);
    cin.tie(0);*/
    int n,root;
    scanf("%d%d",&n,&root);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        v[a].pb(b);
        v[b].pb(a);
    }
    num=tot=0;
    dfs(root,1,-1);
   /* for(int i=1;i<=n;i++)
        cout<<l[i]<<" "<<r[i]<<" "<<d[i]<<endl;*/
    build(rt[0],1,n);
  //  print(rt[0],1,n);
    bfs(n,root);
 /*   for(int i=1;i<=n;i++)
        printf("%d\n",pos[i]);*/
    int q,last=0;
    scanf("%d",&q);
    while(q--)
    {
        int x,k;
        scanf("%d%d",&x,&k);
        x=((x+last)%n)+1,k=(k+last)%n;
        k=k+d[x];k=min(k,maxd);
        last=query(rt[pos[k]],1,n,l[x],r[x]);
        printf("%d\n",last);
    }
    return 0;
}
/********************
5 2
1 3 2 3 5
2 3
5 1
3 4
4 1
2
1 2
2 3
********************/
F