Educational Codeforces Round 72 Editorial(Rated for Div. 2)（A、B、C）

缺乏、安全感 2024-04-18 13:19 78阅读 0赞

[A. Creating a Character][]  
水题考虑的情况不够 **Wrong answer on test 3**

思路：3种情况  
1.如果str>int+esp 答案为esp+1  
2.如果str<int 答案为max（0，（str+esp-int+1）/2）  
3.如果str>=int 答案为（str+esp-int+1）/2  
合并3种情况答案最多为esp+1 所以最终表达式为min( esp+1 , max( (ll)0 , ( str+esp-in+1)/2 ) )  
其中（str+esp-int+1）/ 2 可以理解为 把经验全部给str ，str+esp-int为比临界值str=int时多的经验，这时候只需要分配这些经验值就行了，比如多出来6 分配为 （6，0）（5，1）（4，3）  
多出来的经验有奇数偶数，需要向上取整，不大懂得可以模拟下。

[B. Zmei Gorynich][]  
**Accepted**  
贪心  
维护两个最值，一个是最大打击的数，另一个最大掉头的数。  
如果最大掉头=0 说明不可能胜利。  
否则，每次都减去最大的掉头数，一直减到最大打击的数，如果最大打击数>最大掉头数，最后一下直接用最大打击数打，否则用最大掉头数打。

#include<iostream>
    #include<algorithm> 
    #include<cstring>
    #include<vector>
    #include<cstdio>
    #include<map>
    const int mmax=1e6+10;
    using namespace std;
    typedef long long ll;
    int read()
    {
        int num = 0;
        char c = getchar();
        while(c > '9' || c < '0')c = getchar();
        while(c >= '0'&& c<= '9')
        {
            num=num*10+c-'0';
            c = getchar();
        }
        return num;
    }
    void write(int x)
    {
    	if(x<0)
    	{
    		putchar('-');
    		x=-x;
    	}
    	if(x>9)	
    		write(x/10);
    	putchar(x%10+'0');
    }
    int main()
    {
    	ios::sync_with_stdio(false);
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		ll n,x,ans=0,k,pp=0;
    		cin>>n>>x;
    		for(int i=1;i<=n;i++)
    		{
    			ll a,b,num;
    			cin>>a>>b;
    			num=b-a;
    			if(a>pp)
    				pp=a;
    			if(num<ans)
    			{
    				ans=num;
    				k=a;
    			}
    		}	
    		if(x<=pp)
    			cout<<"1"<<endl;
    		else if(ans==0)
    			cout<<"-1"<<endl;
    		else
    		{
    			ll qq;
    			ans*=(-1);
    			ll ans0=x-pp;
    			if(ans0%ans==0)
    				qq=ans0/ans+1;
    			else
    				qq=ans0/ans+2;
    			if(x%ans==0)
    				cout<<min(qq,(x/ans))<<endl; 
    			else
    			{
    				cout<<qq<<endl;
    			}
    		}
    	}
    	return 0;
    }

[C. The Number Of Good Substrings][]  
赛后补题

因为是字串的问题，首先考虑hahs字符串，敲了一发发现字符串太长，hash值太大，可能有冲突，Wrong answer on test 2 hash函数不能解决

#include<iostream>
    #include<cstring>
    #include<algorithm> 
    #include<cstring>
    using  namespace std;
    typedef unsigned long long ull;
    const int mm=1e6+10;
    ull f[mm],p[mm];
    char  s[100];
    int read()
    {
        int num = 0;
        char c = getchar();
        while(c > '9' || c < '0')c = getchar();
        while(c >= '0'&& c<= '9')
        {
            num=num*10+c-'0';
            c = getchar();
        }
        return num;
    }
    void write(int x)
    {
    	if(x<0)
    	{
    		putchar('-');
    		x=-x;
    	}
    	if(x>9)	
    		write(x/10);
    	putchar(x%10+'0');
    }
    int main()
    {
    	int t;
    	t=read();
    	p[0]=1;
    	for(int i=1;i<=20;i++)
    	{
    		p[i]=p[i-1]*2;
    	}
    	while(t--)
    	{
    		scanf("%s",s+1);
    		int len=strlen(s+1);
    		for(int i=1;i<=len;i++)
    		{
    			f[i]=f[i-1]*2+(s[i]-'0');
    		}
    		for(int i=1;i<=len;i++)
    		{
    			cout<<f[i]<<" ";
    		}
    		cout<<endl;
    		int sum=0;
    		for(int i=1;i<=20;i++)
    		{
    			for(int j=1;j<=len;j++)
    			{
    				if(j+i-1<=len&&f[j+i-1]-f[j-1]*p[i]==i)
    				{
    					sum++;
    				}
    			}
    		}
    		write(sum);
    		printf("\n");
    		printf("\n");
    	}
    	return 0;
    }

题解：题目保证二进制字符串不超过2e5 所以不超过20位数，暴力枚举  
我们首先计算前导0的数，比如00001000——>8 满足题目要求这也算其中一种情况。  
然后从第1个1开始计算二进制的数res，，只需要跑20位，如果res<=字符串长度+前导0的个数 sum++，这就是满足题目的情况。

#include<iostream>
    #include<cstring>
    #include<algorithm> 
    #include<cstring>
    using  namespace std;
    typedef long long ll;
    const int mm=1e6+10;
    char  s[mm];
    int read()
    {
        int num = 0;
        char c = getchar();
        while(c > '9' || c < '0')c = getchar();
        while(c >= '0'&& c<= '9')
        {
            num=num*10+c-'0';
            c = getchar();
        }
        return num;
    }
    void write(int x)
    {
    	if(x<0)
    	{
    		putchar('-');
    		x=-x;
    	}
    	if(x>9)	
    		write(x/10);
    	putchar(x%10+'0');
    }
    int main()
    {
    	ll t;
    	t=read();
    	while(t--)
    	{
    		ll sum=0,sum_0=0;
    		scanf("%s",s+1);
    		ll len=strlen(s+1);
    		for(int i=1;i<=len;i++)
    		{
    			if(s[i]=='0')
    				sum_0++;
    			else
    			{
    				ll res=0;
    				for(int j=i;j<=len&&j<=i+20;j++)
    				{
    					res=res*2+(s[j]-'0');
    					if(res<=(j-i+1)+sum_0)
    						sum++;
    				}
    				sum_0=0;
    			}
    		}
    		write(sum);
    		printf("\n");
    	}
    	return 0;
    }

[A. Creating a Character]: http://codeforces.com/contest/1217/problem/A
[B. Zmei Gorynich]: http://codeforces.com/contest/1217/problem/B
[C. The Number Of Good Substrings]: http://codeforces.com/contest/1217/problem/C