「CF639X」VK Cup 2016 – Round 1

2016年3月29日4,2053

今天早上起来看到挂了两题又掉分QAQ

昨晚赛前几个小时本来想睡个觉结果失眠，只能又起来写了作业，比赛虽然有点累但是最后看C过了pre还是很开心的

没料到在debug的时候删掉了某行代码后来没发现

看了下记录也打了50+场了，还是这样半吊子水平唉，算了大学再抱神犇大腿吧

目前每天刷理综抢救文化课，也没啥时间，好多坑没填，博客留言没回的神犇们对不住了

B. Bear and Forgotten Tree 3

构造深度为h，最长链为d的树

应该大家都会做0。0

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define eps 1e-13
#define mod 10000007
#define inf 1000000000
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,h,d;
int fa[1000005];
int main()
{
    n=read();d=read();h=read();
    for(int i=2;i<=h+1;i++)fa[i]=i-1;
    for(int i=1;i<=d-h;i++)
        if(i==1)fa[i+h+1]=1;
        else fa[i+h+1]=i+h;
    if(d==1&&n!=2)
    {
        puts("-1");
        return 0;
    }
    if(d>2*h||d<h||d+1>n)
    {
        puts("-1");
        return 0;
    }
    for(int i=d+2;i<=n;i++)fa[i]=h;
    for(int i=2;i<=n;i++)
        printf("%d %d\n",i,fa[i]);
    return 0;
}

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define eps 1e-13

#define mod 10000007

#define inf 1000000000

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,h,d;

int fa[1000005];

int main()

{

n=read();d=read();h=read();

for(int i=2;i<=h+1;i++)fa[i]=i-1;

for(int i=1;i<=d-h;i++)

if(i==1)fa[i+h+1]=1;

else fa[i+h+1]=i+h;

if(d==1&&n!=2)

{

puts("-1");

return 0;

}

if(d>2*h||d<h||d+1>n)

{

puts("-1");

return 0;

}

for(int i=d+2;i<=n;i++)fa[i]=h;

for(int i=2;i<=n;i++)

printf("%d %d\n",i,fa[i]);

return 0;

}

C.Bear and Polynomials 多项式

在差绝对值为K范围内修改一个多项式Q的某一系数，使得Q(2)=0

先全部进位一下，然后找出最低位的1，不可能改动比它高位的系数

比它低位的系数依次枚举一下

注意超过2K就直接退出

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define eps 1e-13
#define mod 10000007
#define inf 1000000000
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,K;
int a[200005],b[200005],ans;
int main()
{
    n=read();K=read();
    for(int i=0;i<=n;i++)a[i]=read();
    b[0]=a[0];
    for(int i=1;i<=n;i++)
    {
        b[i]=a[i]+b[i-1]/2;
        b[i-1]%=2;
    }
    int fir=0;
    ll res=0;
    for(int i=0;i<=n;i++)
        if(b[i])
        {
            fir=i;break;
        }
    for(int i=n;i>=fir;i--)
    {
        res*=2;
        res+=b[i];
        if(abs(res)>2*K){puts("0");return 0;}
    }
    if(fir==n&&a[n]==res)ans--;
    for(int i=fir;i>=0;i--)
    {
        if(abs(a[i]-res)<=K)ans++;
        res*=2;
        if(abs(res)>2*K)break;
    }
    printf("%d\n",ans);
    return 0;
}

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define eps 1e-13

#define mod 10000007

#define inf 1000000000

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,K;

int a[200005],b[200005],ans;

int main()

{

n=read();K=read();

for(int i=0;i<=n;i++)a[i]=read();

b[0]=a[0];

for(int i=1;i<=n;i++)

{

b[i]=a[i]+b[i-1]/2;

b[i-1]%=2;

}

int fir=0;

ll res=0;

for(int i=0;i<=n;i++)

if(b[i])

{

fir=i;break;

}

for(int i=n;i>=fir;i--)

{

res*=2;

res+=b[i];

if(abs(res)>2*K){puts("0");return 0;}

}

if(fir==n&&a[n]==res)ans--;

for(int i=fir;i>=0;i--)

{

if(abs(a[i]-res)<=K)ans++;

res*=2;

if(abs(res)>2*K)break;

}

printf("%d\n",ans);

return 0;

}

D. Bear and Contribution

如果b > c * 5，就让 b = c * 5

那么可以直接计算出将某个人贡献增加到某个x值的代价

可以容易得知，最终一定存在某个人的贡献，满足最优解的x值与他相差不超过4

那么x的取值有5 * n种情况

发现如果第i个人在X0时比j代价小，则在X+5时i也比j优

对于 mod 5 意义下同余的x，从小到大排列之后，依次计算代价

用堆加标记维护最优的K个人即可

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define eps 1e-13
#define mod 10000007
#define inf 1000000000
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll n,K,b,c,now,last;
ll t[200005],q[1000005];
ll mn=(ll)1e60,ans;
ll cal(int x,int y) //x->y
{
    return (y-x)/5*b+(y-x)%5*c;
}
priority_queue<ll,vector<ll> >pq;
void solve(int x)
{
    ll Add=(x-now)/5*b,res=(ll)1e60;
    while(t[last+1]<=x&&last+1<=n)
    {
        pq.push(cal(t[last+1],x)-Add);
        ans+=cal(t[last+1],x)-Add;
        if(pq.size()>K)
        {
            ans-=pq.top();
            pq.pop();
        }
        if(pq.size()==K)
            res=min(res,Add*K+ans);
        last++;
    }
    mn=min(mn,res);
}
int main()
{
    n=read();K=read();b=read();c=read();
    if(c*5<b)b=c*5;
    for(int i=1;i<=n;i++)
        t[i]=read();
    sort(t+1,t+n+1);
    int m=0;
    for(int i=1;i<=n;i++)
        for(int j=t[i];j<=t[i]+4;j++)
            q[++m]=j;
    sort(q+1,q+m+1);
    for(int i=0;i<=4;i++)
    {
        now=i-inf;last=0;
        ans=0;
        while(!pq.empty())pq.pop();

        for(int j=1;j<=m;j++)
            if((q[j]%5+5)%5==i)
                solve(q[j]);
    }
    cout<<mn<<endl;
    return 0;
}

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define eps 1e-13

#define mod 10000007

#define inf 1000000000

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll n,K,b,c,now,last;

ll t[200005],q[1000005];

ll mn=(ll)1e60,ans;

ll cal(int x,int y) //x->y

{

return (y-x)/5*b+(y-x)%5*c;

}

priority_queue<ll,vector<ll> >pq;

void solve(int x)

{

ll Add=(x-now)/5*b,res=(ll)1e60;

while(t[last+1]<=x&&last+1<=n)

{

pq.push(cal(t[last+1],x)-Add);

ans+=cal(t[last+1],x)-Add;

if(pq.size()>K)

{

ans-=pq.top();

pq.pop();

}

if(pq.size()==K)

res=min(res,Add*K+ans);

last++;

}

mn=min(mn,res);

}

int main()

{

n=read();K=read();b=read();c=read();

if(c*5<b)b=c*5;

for(int i=1;i<=n;i++)

t[i]=read();

sort(t+1,t+n+1);

int m=0;

for(int i=1;i<=n;i++)

for(int j=t[i];j<=t[i]+4;j++)

q[++m]=j;

sort(q+1,q+m+1);

for(int i=0;i<=4;i++)

{

now=i-inf;last=0;

ans=0;

while(!pq.empty())pq.pop();

for(int j=1;j<=m;j++)

if((q[j]%5+5)%5==i)

solve(q[j]);

}

cout<<mn<<endl;

return 0;

}

« Manthan, Codefest 16 「小奇模拟赛2」[BZOJ3784] 小奇的树 »

orz黄学长实在太神(moe)啦

%%%黄学长黄学长快去看bzoj discuss有人推您当萌王~

hzwer

我资瓷Po姐和CA娘

Menci

我资瓷CA娘

hzwer.com _ Home | http://hzwer.com

「CF639X」VK Cup 2016 – Round 1

分类目录

热门文章

Myfriends

近期评论