A:

题面：

输入一个01字符串，问你最少需要将多少个0变成1，才能使得字符串所有的1都是连续的

solution：

先统计1的个数，记录第一个1的下标i以及最后一个1的下标j，输出j-i+1-sum(1)

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        int sum = 0,cnt1 = 0,cnt2 = 0,l = s.length();
        for(int i=0;i<l;i++)
        {
            if(s[i] == '1')
                sum++;
        }
        for(int i=0;i<l;i++){
            if(s[i] == '1')
            {
                cnt1 = i;
                break ;
            }
        }
        for(int i=l-1;i>=0;i--){
            if(s[i] == '1')
            {
                cnt2 = i;
                break ;
            }
        }
        if(sum == 0){
            cout<<"0"<<endl;
            continue ;
        }
        cout<<cnt2 - cnt1 + 1 - sum<<endl;
    }
    return 0;
}

B:

题面：

输入n，a，b。n代表道路的长度，每天可以铺设1m，a代表连续a天铺设符合标准的道路，b代表连续b天铺设不符合标准的道路的天数，工人可以选择某天不铺设道路，但是天数也要计算在内，要求符合标准的道路>=floor(n/2)。即7m的道路至少需要4m，问工人们最少需要多少天才能铺设完所有的道路？

solution：

自己想多了，写了很多if，其实可以二分，也可以直接求

std：

直接求：

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

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        ll n , g , b;
        cin>>n>>g>>b;
        ll x = (n+1)/2;
        ll y = x/g;
        ll z = x%g;
        if(z == 0)
        {
            z = g;
            y--;
        }
        cout<<max(n , y*(g+b) + z)<<endl;
    }
    return 0;
}

二分：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,b,g;
int solve(ll sum)
{
    ll len = (n+1)/2;
    ll cnt = sum/(g+b);
    ll res = sum%(g+b);
    ll gcnt = g*cnt + min(g , res);
    return gcnt >= len;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>g>>b;
        ll l = 0 , r = 1e18,ans = 1e18;
        while(l <= r)
        {
            ll mid = (l+r)>>1;
            if(solve(mid)){
                ans = min(ans , mid);
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        cout<<max(n , ans)<<endl;
    }
    return 0
}

C:

题面：

有一种键盘，只有一行组成，a-z，键盘只能连续敲击相邻的字母，给出敲击出的字符串，请你构造出键盘，如果不存在这样的键盘，输出-1

solution：

拓扑排序思想，我们首先记录相邻的字母，存到vector，如果size>2,输出-1，否则遍历a-z，如果入度等于1，则dfs这个字母，如果入度等于0也要记得输出，

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1005;
vector<int> g[maxn];
int vis[maxn],cnt[maxn];
string ans ;
void init()
{
    for(int i=0;i<maxn;i++){
        g[i].clear();
        vis[i] = 0;
    }
    ans = "";
}
void dfs(int x)
{
    vis[x] = 1;
    ans += ('a' + x);
    for(int i=0;i<g[x].size();i++){
        if(!vis[g[x][i]]){
            dfs(g[x][i]);
        }
    }
    return ;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        init();
        cin>>s;
        map< pair<int ,int > , int > mp;
        for(int i=1;i<s.length();i++)
        {
            int a = s[i] - 'a';
            int b = s[i-1] - 'a';
            if(a > b)
                swap(a , b);
            if(mp[make_pair(a,b)] == 0){
                g[a].push_back(b);
                g[b].push_back(a);
                mp[make_pair(a,b)] = 1;
            }
        }
        int flag = 0;
        for(int i=0;i<26;i++){
            if(g[i].size() > 2){
                cout<<"NO"<<endl;
                flag = 1;
                break ;
            }
        }
        if(flag == 1){
            continue ;
        }
        for(int i=0;i<26;i++)
        {
            if(!vis[i] && g[i].size() < 2){
                dfs(i);
            }
        }
        if(ans.length() == 26){
            cout<<"YES"<<endl;
            cout<<ans<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

D:

题面：

给出一个书包的容量，给出n个盒子，每个盒子都是2的次幂，每个盒子都可以平均分成2部分，每部分都是原来的一半，问你最少需要分几次使得盒子可以恰好装满书包？

solution：

看到了2的次幂，就想到了二进制，如果所有盒子加起来小于容量，输出-1，否则肯定有解，下面考虑二进制贪心，将每一个盒子转成二进制，记录每一个位置上的数，从低位相比，如果该为为0，但是书包容量该为为1，那肯定就要去高位借一个1~按照这个思路，如果有两个或以上，记得进位

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
ll a[maxn];
ll b[100],c[100];
void init()
{
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
}
void solve()
{
    ll n , m ,sum = 0;
    int ans = 0;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i];
        sum += a[i];
        ll x = a[i];
        int j = 0;
        while(x){
            if(x%2){
                b[j] += 1;
            }
            j++;
            x /= 2;
        }
    }
    if(sum < n){
        cout<<"-1"<<endl;
        return ;
    }
    ll x = n;
    int k = 0;
    while(x)
    {
        if(x%2)
            c[k] = 1;
        k++;
        x /= 2;
    }
    for(int i=0;i<60;i++)
    {
        if(c[i]){
            if(!b[i]){
                for(int j=i+1;j<60;j++){
                    if(b[j]){
                        b[j]--;
                        int now = j;
                        while(now != i){
                            now--;
                            b[now]++;
                            ans++;
                        }
                        b[now]++;
                        break ;
                    }
                }
            }
            b[i]--;
        }
        b[i+1] += b[i]/2;
    }
    cout<<ans<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        init();
        solve();
    }
    return 0;
}