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

我不是女神ヾ 2022-09-20 15:10 147阅读 0赞

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

**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;
    }

D和E没搞出来……

元旦时群里组织过一次“元旦欢乐赛”。

比赛链接：https://www.contesthunter.org/contest/%E5%85%83%E6%97%A6%E6%AC%A2%E4%B9%90%E8%B5%9B

我知道这个比赛的时候都已经快结束了……不过还是学到了一些姿势

[冒泡排序（优化版）的比较次数和交换数字次数 逆序数+树状数组 - 九野的博客 - 博客频道 - CSDN.NET][_ - _ - _ - CSDN.NET]

[_ - _ - _ - CSDN.NET]: http://blog.csdn.net/acmmmm/article/details/17662865