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

还是终于能有这么一场最后一题会做了……
比赛页面(1282)


A-Temporarily unavailable
这题麻烦地方就在于情况有点多,包括圆含不含左右端点这些。其实稍微整理一下就行。

#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int N=200050;
int n;
int main()
{
    int Test;cin>>Test;
    while(Test--)
    {
        int a,b,c,r;
        cin>>a>>b>>c>>r;
        if(a>b)swap(a,b);
        int ans1=max(min(b,c-r)-a,0);
        int ans2=max(b-max(a,c+r),0);
        cout<<ans1+ans2<<endl;
    }
    return 0;
}

B1-K for the Price of One (Easy Version)
B2-K for the Price of One (Hard Version)
直接说Hard Version吧…
其实我也没怎么看这题,xydg出的

#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int N=200050;
int n,p,k;
int ans;
int a[N],z[N],s[N];
int main()
{
    int Test;cin>>Test;
    while(Test--)
    {
        ans=0;
        scanf("%d%d%d",&n,&p,&k);
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&a[i]);
        }
        sort(a+1,a+n+1);
        for(int i=0;i<=n+5;++i)z[i]=s[i]=0;
        for(int i=1;i<=k;++i)s[i]=a[i];
        for(int i=2;i<=k;++i)s[i]+=s[i-1];
        s[k]=a[k];
        int now=0;
        for(int i=1;i<=n;++i)
        {
            int pos=i%k;if(pos==0)pos=k;
            z[pos]+=a[i];
            if(i>=k)
            {
                now=z[pos]+s[pos]-a[pos];
            }
            else now=s[i];
            if(now<=p)ans=i;
        }
        cout<<ans<<endl;
    }
    return 0;
}

C-Petya and Exam
嘛这题其实就按照$t_i$从小到大贪心就行了……
总的来说,一个思路是先做简单题再做大题,这样必须做的题就变少了,当然具体怎么做还是要贪贪的……
我们在$t_i-1$处离开考场是可以更优的,因为你少做一道必须的题,而之前的题你都能做,所以花费的总时间也算得出来,所以就这么贪就行……

#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int N=200050;
int n;
ll T;
ll a,b;
struct problems
{
    int type;
    ll t;
}p[N];
bool cmp(const problems &x,const problems &y)
{
    return x.t<y.t;
}
int cntEasy,cntHard;
int ans;
int main()
{
    int Test;scanf("%d",&Test);
    while(Test--)
    {
        scanf("%d%lld%lld%lld",&n,&T,&a,&b);
        cntEasy=cntHard=ans=0;
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&p[i].type);
            if(p[i].type)cntHard++;
            else cntEasy++;
        }
        for(int i=1;i<=n;++i)
        {
            scanf("%lld",&p[i].t);
            p[i].t--;
        }
        sort(p+1,p+n+1,cmp);
        p[n+1].t=T;
        int ans=0,tmp=0;
        int cnt1=0,cnt2=0;
        for(int i=1;i<=n+1;++i)
        {
            ll now=p[i].t-(a*cnt1+b*cnt2);
            tmp=(cnt1+cnt2);
            if(now>=0)
            {
                ll t1=min(now/a,(ll)cntEasy-cnt1);
                tmp+=t1;now-=t1*a;
                ll t2=min(now/b,(ll)cntHard-cnt2);
                tmp+=t2;now-=t2*b;
                ans=max(ans,tmp);
            }
            if(p[i].type==1)cnt2++;else cnt1++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

D-Enchanted Artifact
交互题都是人类智慧,还好这题不难。
一种构造方案是,先构造一个长度为$300$的全是a的串,这样可以问出串中b的个数。同样的道理,可以问出串中a的个数,这样串长就确定了。
然后就让答案串和询问串先全设为a,然后第i次询问将第i个a变为b,看编辑距离是增加还是减少,这样可以确定这个位置的答案。
另外,最后那个位置其实是不需要询问的,因为可以通过前面a的个数和b的个数直接得出来,这样就做完了。

#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define ls id<<1
#define rs id<<1|1
using namespace std;
int cnta,cntb,n;
char ans[305];
char s[305];
int main()
{
    for(int i=0;i<300;++i)s[i]='a';
    printf("%s\n",s);fflush(stdout);
    int d;scanf("%d",&d);
    if(d==0)
    {
        printf("%s\n",ans);
        fflush(stdout);
        return 0;
    }
    cnta=300-d;
    for(int i=0;i<300;++i)s[i]='b';
    printf("%s\n",s);fflush(stdout);
    scanf("%d",&d);cntb=300-d;
    if(d==0)
    {
        printf("%s\n",ans);
        fflush(stdout);
        return 0;
    }
    n=cnta+cntb;
    s[n]='\0';
    for(int i=0;i<n;++i)
    {
        s[i]=ans[i]='a';
    }
    int D=cntb;
    for(int i=0;i<n-1;++i)
    {
        s[i]='b';
        printf("%s\n",s);fflush(stdout);
        int now;scanf("%d",&now);
        if(now==0)
        {
            printf("%s\n",ans);
            fflush(stdout);
            return 0;
        }
        if(now<D)ans[i]='b';
        else ans[i]='a';
        s[i]='a';
    }
    for(int i=0;i<n-1;++i)
    {
        if(ans[i]=='a')cnta--;
        else cntb--;
    }
    if(cnta)ans[n-1]='a';else ans[n-1]='b';
    printf("%s\n",ans);fflush(stdout);
    return 0;
}

E-The Cake Is a Lie
(蛋糕是个谎言!)
这题其实思路很简单……就是实现有点麻烦。
如果我们把三角形抽象为点,这题要好写一些。
观察到最后的图形,有若干个三角形,其中最外层的三角形(即删除后剩下的图形还是一个凸多边形)一定与剩下的多边形只有一个公共边,将三角形抽象为点后,发现这个点的度数为1,于是剩下的工作就是建图,然后做一遍拓扑排序,就可以解决第二问。
第一问的话我的解法是:不把三角形抽象为点,而是顶点为点,像这样动态加边,因为最外层的三角形的一个顶点出现次数一定为1(因为只有一个三角形以其为顶点),所以我们就可以把这个点删除后,与这个顶点相连的两个点各加一条边。但加边是有限制的,如果这两个点已经在同一连通分量里面,那就不加这条边。像这样,用一个队列进行bfs的话,最后加出来的图一定是一条链,这样就解决了第一问。
代码先留着,后面再补。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注