Codeforces Round #219 (Div. 2) + 元旦欢乐赛-蒲公英云

Codeforces Round #219 (Div. 2) + 元旦欢乐赛

抽出时间补一下做过的题。

Codeforces 373A Collecting Beats is Fun

题意：面板上有16个灯,每个灯会在一个时间量，一只手可以同时关掉k个，问是否可以及时关掉
思路：找到最多的那个，和2＊k比较即可

#include <cstdio>
#include <cstring>
char str[10];
int hash[15];
int main ()
{
    int k,i;
    scanf("%d",&k);
    memset(hash,0,sizeof(hash));
    for (i=0;i<4;i++)
    {
        scanf("%s",&str);
        for (int j=0;j<4;j++)
            if (str[j]!='.')
            {
                int tmp=str[j]-'0';
                hash[tmp]++;
            }
    }
    bool flag=true;
    for (i=0;i<10;i++)
        if (hash[i]>2*k)
            flag=false;
    if (flag)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

Codeforces 373B Making Sequences is Fun

题意：给出三个整数w,m,k,得到一个数字的代价是这个数字的位数乘以k.总价为w
问你可以得到多少个以m起始的数字序列，这个序列需要是连续的，也就是(m, m+1, m+2, …)
思路:二分列举扩充序列的最后一个整数ans，算出m到ans共有多少个字符num,若是num <= w/k 则接受

#include <cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
__int64 w,m,k;
__int64 bit[20];
void Init ()
{
    bit[1]=1;
    for (int i=2;i<20;i++)
        bit[i]=bit[i-1]*10;
}
int size (__int64 a)
{
    int cnt=0;
    while (a)
    {
        cnt++;
        a/=10;
    }
    return cnt;
}
__int64 Cal (__int64 x)
{
    __int64 num=0;
    while (x>=m)
    {
        int len=size(x);
        __int64 tmp=max(bit[len],m);
        num+=(x-tmp+1)*len;
        x=tmp-1;
    }
    return num;
}
int main ()
{
    Init ();
    while (~scanf("%I64d%I64d%I64d",&w,&m,&k))
    {
        __int64 ans=m-1;
        __int64 left=m,right=1e17,mid;
        while (left<=right)
        {
            mid=(left+right)>>1;
            if (Cal(mid)<=w/k)
                left=mid+1,ans=mid;
            else
                right=mid-1;
        }
        printf("%I64d\n",ans-m+1); //输出个数
    }
    return 0;
}

Codeforces 373C. Counting Kangaroos is Fun

题意：给出n只袋鼠袋子的大小,若一只袋鼠的袋子的2倍不大于另一个袋鼠袋子的大小,那么大袋鼠就可以装小袋鼠。
每个袋鼠只能装一只袋鼠，且只能装袋子为空的袋鼠,问最少能看到多少只袋鼠。
思路:贪心.显然至少有一半是可以看见的，于是排序后从第一个和中间同时开始向后扫，如果满足2倍关系就同时后移，否则只有中间的后移。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=500005;
int data[N];
int main ()
{
    int n,i,j;
    scanf("%d",&n);
    for (i=0;i<n;i++)
        scanf("%d",&data[i]);
    sort(data,data+n);
    int limit=n/2,ans=n;
    for (i=0,j=n/2 ; i<limit && j<n;j++)
        if (data[i]*2 <= data[j])
        {
            ans--;
            i++;
        }
    printf("%d\n",ans);
    return 0;
}