Codeforces Round #428 (Div. 2)

终于上蓝名了，hahahahaha，虽然这场的 B 题因为脑抽了，少考虑一种情况终判错了，还是很可惜的。。

B题本来过来1500个人，终判之后只剩下了200多个，真的有毒！！！！

题目大意：你需要k个糖果，你每天最多拿8个，有n天，每天提供你a[ i ]个糖果，如果糖果大于8个多出来的

可以储存下来，问你能不能在n天内拿到k个糖果。

思路：模拟就行了。

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[105];
int main()
{
    cin>>n>>k;
    int sum=0;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];
    if(sum<k)
    {
        puts("-1");
        return 0;
    }
    int ans=0;
    int now=1,res=0;
    while(ans<k)
    {
        if(now>n)
        {
            puts("-1");
            return 0;
        }
        if(a[now]<=8)
        {
            ans+=a[now];
            int p=8-a[now];
            if(p<=res)
            {
                ans+=p;
                res-=p;
            }
            else
            {
                ans+=res;
                res=0;
            }
        }
        else
        {
            ans+=8;
            res+=a[now]-8;
        }
        if(ans>=k) break;
        now++;
    }
    cout<<now<<endl;
    return 0;
}

View Code

B - Game of the Rows

题目大意：有n艘船，每艘船有8个位置，一种两个两连坐，一个四连坐。现在又k个团，分别有a[ i ]个士兵，

要求不同团的士兵不是坐相邻的位置，问你能不能将所有士兵安排到船上。

这确实是个毒题。

思路：看到题目就想到肯定是贪心，我们的首要目标就是要空着的位置尽可能地少，而且四连坐如果坐满

肯定都是一个团的，那么我们先将四连坐能坐满的全部坐满，坐不满的我们就将四连坐分成一个两连坐

和一个单个座位，再用两连坐和单个座位模拟就简单多了，但是我注意了单个座位用完用两连坐代替，

却忘了两连坐用完也能用单个座位代替，GGGGGGG。

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[105];
int main()
{
    cin>>n>>k;
    int c1=n*2,c2=n,c3=0;
    for(int i=1;i<=k;i++) scanf("%d",&a[i]);
    for(int i=1;i<=k;i++)
    {
        int w=a[i]/4;
        if(c2>=w)
        {
            c2-=w;
            a[i]-=w*4;
        }
    }
    c1+=c2;
    c3+=c2;
    for(int i=1;i<=k;i++)
    {
        if(a[i])
        {
            if(a[i]&1)
            {
                if(c3) c3--;
                else c1--;
            }
            int w=a[i]/2;
            if(c1>=w) c1-=w;
            else c3-=2;
            if(c3<0)  //这里GG了
            {
                puts("NO");
                return 0;
            }
        }
        //cout<<c1<<endl;
    }
    puts("YES");
    return 0;
}

View Code

C - Journey

题目大意：给你一颗树，有一个球从 1 好节点还是等概率地向他的子节点转移，如果没有子节点了则停止，

问你球通过的路径长度的期望是多少。（从一个节点转移到其子节点的长度为 1 ）。

思路：刚开始以为每一条路都是等概率地错了一发，直接 dfs 每一条路到底将期望加上去。

#include<bits/stdc++.h>
using namespace std;
const int N=100003;
vector<int> e[N];
int vis[N],sum,len[N];
double ans;
void dfs(int u,int pre,int l,double p)
{
    bool flag=false;
    for(int i=0;i<len[u];i++)
    {
        int to=e[u][i];
        if(to!=pre)
        {
            flag=true;
            if(pre==-1) dfs(to,u,l+1,p/len[u]);
            else dfs(to,u,l+1,p/(len[u]-1));
        }
    }
    if(!flag)
    {
        //cout<<u<<endl;
        //cout<<p<<endl;
        ans+=p*l;
    }
}
int main()
{
    int n;
    cin>>n;
    ans=0;
    for(int i=1;i<n;i++)
    {
        int f,t;
        scanf("%d%d",&f,&t);
        e[f].push_back(t);
        e[t].push_back(f);
        len[f]++;
        len[t]++;
    }
    dfs(1,-1,0,1);
    printf("%.12f
",ans);
    return 0;
}

View Code