Educational Codeforces Round 82 (Rated for Div. 2)

A.
题意：就是删去多少个零使得所有的1连在一起

思路：我的思路是记录每个1出现的位置，然后在进行遍历得到每相邻的1之间的距离。然后都加起来输出就行了

我看我cao lao的思路是得到1最开始出现的位置跟最后出现的位置，然后计算之间的零。这里我觉得还可以改进，就是从找到第一个1的位置到最后一个1的位置之间的0，1串累加，然后末减初，计算差值就是解了
可以试试

#include<bits/stdc++.h>

#define inf 0x3f3f3f3f


using namespace std;

int b[105];
string s;

int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>s;
		int k = 0;
		int l = s.length();
		//int flag = 0;
		for(int i=0;i<l;i++){
		   if(s[i] == '1'){
		   	  b[k] = i;//记录每个1的位置 
		   	  k++;
		   }
		}
		if(k == 0){//没有出现1 
			cout<<0<<endl;
			continue;
		}
		int res;//每对1之间距离 
		int ans = 0;//总的删去的0 
		for(int i=0;i+1<k;i++){
			res =  b[i+1]-b[i]-1; 
			ans += res;
		}
		if(!ans) cout<<0<<endl; 
		else{
			cout<<ans<<endl;
		}
	}
	return 0;
} 

B
题意：就是修公路，n长，然后天好修得到的是高质量的路，天不好修得到的是低质量的路，G天好,B天不好，你想得到一半以上的高质量的路，然后问你至少需要多少天

思路;先计算需要高质量的公路多长，然后如果G>=所需要的高质量的路的话，那么就至少需要N天，因为从一开始就把你的要求完成了，后面的质量怎么样也无所谓了。如果不是的话。那么这个时候我们需要判断的是需要多少个G，这里也存在两种情况，一者正好是G的倍数，那么需要…不想解释了，看代码吧

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n,g,b;
ll ans;
        
int main()
{   
    ll t;
	cin>>t;
	while(t--)
    {   
        
		cin>>n>>g>>b;
		ll res=(n+1)/2;
		
		if(res<=g)
			cout<<n<<endl;
		else 
		{
			ll num=res/g;
			
			if(res%g==0)
				ans=(num-1)*(g+b)+g; 
			else 
				ans=(num)*(g+b)+res%g;
				
			cout<<max(ans,n)<<endl;
		}
	}
	
	return 0;
}

C.题意：就是把26个英文字母排序，好在输入密码的时候可以密码的字母都是挨着的

思路：这个题啊，我写了近100行，愣是把自己写迷了，我简单说下我的思路，就是我首先把小写字母都转换成了数字，然后我就先判断每次相邻两个数字是否相等，这里以来，相等的话打破循环然后输出NO，cnotinue;进入下组数据，然后后面的话，我是每次取两个数，…然后不记得怎么了，把自己搞迷了，算了算了

后来又写了个W2…

结束了有dalao说是双向链表！！！
好吧，确实没想到

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char str[205],ans[105];
bool vis[105];

int main()
{
	int T;  scanf("%d",&T);
	while (T--)
	{
		scanf("%s",str+1);
		int n=strlen(str+1),l=27,r=27,now=27,flag=0;
		ans[l]=str[1];
		memset(vis,0,sizeof(vis));
		vis[str[1]-'a']=1;
		for (int i=2;i<=n;i++)
		{
			if (now>l&&ans[now-1]==str[i])
                now--;
			else if (now<r&&ans[now+1]==str[i])
                now++;
			else if (now==l&&!vis[str[i]-'a'])
                ans[--l]=str[i],now--,vis[str[i]-'a']=1;
			else if (now==r&&!vis[str[i]-'a'])
                ans[++r]=str[i],now++,vis[str[i]-'a']=1;
			else
			{
			    flag=1;
                break;
            }
		}
		if (flag)
            puts("NO");
		else
		{
			puts("YES");
			for (int i=l;i<=r;i++)
                putchar(ans[i]);
			for (int i=0;i<26;i++)
				if (!vis[i]) putchar(i+'a');
			puts("");
		}
	}
	return 0;
}

D.题意就是给一个袋子跟N个元宝，然后元宝可以对半分割，问能否将袋子装满。

思路：贪心

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	int t;cin>>t;
	while (t--)
    {
        ll s,n,m,x,ans;
		cin>>n>>m;
		s=ans=0;
		multiset<ll,greater<ll>> f;
		while (m--)
        {
            cin>>x;
            s+=x;
            f.insert(x);
        }
		if (s<n)
            cout<<"-1"<<endl;
		else
		{
			while(n)
			{
				m=*f.begin();
				f.erase(f.begin());
				if(m<=n)
				{
				    n-=m;
				    s-=m;
				}
				else if(s-m<n)
                {
                    ans++;
                    f.insert(m/2);
                    f.insert(m/2);
                }
				else
                    s-=m;

			}

			cout<<ans<<endl;
		}
	}
}