Educational Codeforces Round #76(Div.2)解题报告

发布于 2019-11-14  68 次阅读



A - Two Rival Students
贪心一下就可以了......

#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int main()
{
    int T;cin>>T;
    while(T--)
    {
        int x,y;
        cin>>x>>y;
        if(y<=x){puts("yes");continue;}
        if(x==1)
        {
            if(y==1)puts("yes");
            else puts("no");
        }
        else if(x<=3)
        {
            if(y<=3)puts("yes");
            else puts("no");
        }
        else puts("yes");
    }
    return 0;
}

B - Magic Stick
不难发现,当$x$大于等于$4$的时候,不论多大的数我们都可以得到。
所以判断一下$x$小于等于$3$的情况就可以了。

#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int main()
{
    int T;cin>>T;
    while(T--)
    {
        int x,y;
        cin>>x>>y;
        if(y<=x){puts("yes");continue;}
        if(x==1)
        {
            if(y==1)puts("yes");
            else puts("no");
        }
        else if(x<=3)
        {
            if(y<=3)puts("yes");
            else puts("no");
        }
        else puts("yes");
    }
    return 0;
}

C - Dominated Subarray
这题没怎么看......

#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=200050;
vector <int> vec[N];
int n,ans;
int main()
{
    int Test;cin>>Test;
    while(Test--)
    {
        scanf(
        for(int i=0;i<=n;++i)vec[i].clear();
        for(int i=1;i<=n;++i)
        {
            int num;
            scanf(
            vec[num].push_back(i);
        }
        ans=INT_MAX;
        for(int i=0;i<=n;++i)
        {
            int sz=vec[i].size()-1;
            for(int j=0;j<sz;++j)
            {
                ans=min(ans,vec[i][j+1]-vec[i][j]);
            }
        }
        if(ans==INT_MAX)puts("-1");
        else printf(
    }
    return 0;
}

D -  Yet Another Monster Killing Problem
qnm的边界啊啊啊啊啊
每一天怪物能杀就杀,杀得越多越好,所以我们需要二分。
怎么二分呢?先用线段树或者st表维护怪物的区间最大值,勇者按$s$为第一关键字从大到小排序,再维护一个$p$的前缀最大值就可以check了。
(这题因为多组数据+边界清空卡了半天......)

#include <bits/stdc++.h>
#define ll long long
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=200500;
int n,m;
int mxkill[N];
int vec[N],cnt;
struct node
{
    int p;
    int s;
}c[N];
int a[N];
struct segtree
{
    int mx;
}t[N<<3];
void build(int l,int r,int id)
{
    if(l==r)
    {
        t[id].mx=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    t[id].mx=max(t[ls].mx,t[rs].mx);
}
int query(int l,int r,int id,int L,int R)
{
    if(l>=L&&R>=r)
    {
        return t[id].mx;
    }
    int mid=(l+r)>>1;
    if(R<=mid)return query(l,mid,ls,L,R);
    else if(L>mid)return query(mid+1,r,rs,L,R);
    else return max(query(l,mid,ls,L,mid),query(mid+1,r,rs,mid+1,R));
}
inline bool cmp(const node &x,const node &y)
{
    return x.s>y.s;
}
inline bool check(int pos,int x)
{
    int nowR=pos+x-1;
    int nowmx=query(1,n,1,pos,nowR);
    int xx=lower_bound(vec+1,vec+cnt+1,x)-vec;
    if(mxkill[vec[xx]]>=nowmx)return true;
    else return false;
}
int main()
{
    int T;cin>>T;
    while(T--)
    {
    	cnt=0;
    	memset(t,0,((n+5)<<2)*sizeof(int));
        scanf(
        for(int i=0;i<=n+50;++i)mxkill[i]=0;
        for(int i=1;i<=n;++i)
        {
            scanf(
        }
        scanf(
        for(int i=1;i<=m;++i)
        {
            scanf(
        }
        sort(c+1,c+m+1,cmp);
        for(int i=1;i<=m;++i)
        {
        	vec[++cnt]=c[i].s;
            mxkill[c[i].s]=max(mxkill[c[i].s],c[i].p);
        }
        vec[cnt+1]=0;
        sort(vec+1,vec+cnt+1);
        for(int i=1;i<=m;++i)
        {
            mxkill[c[i].s]=max(mxkill[c[i-1].s],mxkill[c[i].s]);
        }
        build(1,n,1);
        int ans=0,monster=1;
        while(monster<=n)
        {
            int L=1,R=n-monster+1,tmp=-1;
            while(L<=R)
            {
                int mid=(L+R)>>1;
                if(check(monster,mid))tmp=mid,L=mid+1;
                else R=mid-1;
            }
            if(tmp==-1){ans=-1;break;}
            monster+=tmp;
            ans++;
        }
        printf(
    }
    return 0;
}

EFG暂补