Educational Codeforces Round 176 (Rated for Div. 2)(A-D)

A. To Zero

思路：签到题，分类讨论就行。

void solve()
{
    int n, k;
    cin >> n >> k;
    int num = 0;
    if ((n&1) && (k&1)){
        num = 1;
        n-=k;
        k--;
        num+=((n+k-1)/k);
    }
    else if ((n&1) &&!(k&1)){
        num = 1;
        n-=(k-1);
        num += ((n+k-1)/k);
    }
    else if (!(n&1) && (k&1)){
        k--;
        num += ((n+k-1)/k);
    }
    else {
        num = ((n+k-1)/k);
    }
    cout << num << endl;
}

B. Array Recoloring

思路：感觉这题题意不是很好理解，所以看半天样例，题意是这样：先选k个涂蓝，再从任意的这k个相邻开始将红色的涂蓝，因此所有的栅栏都会被涂蓝。

其实是cost为最先选出的k个加上最后一个被涂蓝的代价，所以我们举几个例子就能发现性质，当k>1时，任何前k+1大的可以被涂，当k=1时，最后一个被涂的一定是最后一个或者第一个，再比较一下大小就可以了。

void solve()
{
    int n, m, k;
    cin >> n >> k;
    vi a(n);
    for (int i = 0; i < n; ++i){
        cin >> a[i];
    }
    int sum = 0;
    if (k == 1){
        int l = *max_element(a.begin(), a.end()-1);
        int r = *max_element(a.begin()+1, a.end());
        sum = max(l+a[n-1], r+a[0]);
    }else {
        sort(a.begin(), a.end(), greater<int>());
        sum = accumulate(a.begin(), a.begin()+k+1, 0ll);
    }
    cout << sum << endl;
    
}

C. Two Colors

思路：由于要保证 有两种颜色，所以我们可以遍历1到n块木板，看前i部分有几种颜色满足，再看后n-i个木板有几种满足，这里想成乘，但会对于少的一部分可能会与自己结合，再将其减去。

void solve()
{
    int n, m, k;
    cin >> n >> m;
    vector<int> a(m+1);
    for (int i = 1; i<=m; i++) {
        cin >> a[i];
    }
    sort(a.begin()+1, a.end());
    int res = 0;
    for (int i = 1; i<n; i++){
        int l = lower_bound(a.begin(), a.end(), i) - a.begin();
        l = m-l+1;
        int rem = n-i;
        int r = lower_bound(a.begin(), a.end(), rem) - a.begin();
        r = m-r+1;
        if (l==0 || r==0){
            continue;
        }
        res += l*r-min(l, r);
    }
    cout << res << endl;
}

D. Equalization

思路：首先我们要知道对于除去代表将该数的二进制向右移k位，这里我们转换成二进制来叙述，比如9除去将其二进制向右移2位为2。所以我们要让x、y相等就是要让其前缀一样，我们就可以出去其后缀，但又考虑到代价问题，比如大于,而其又可以由来代替，所以这里就得求出最优的组合，这就很想一个背包问题，1到k里一个只能取一次，对于二进制问题因为数据不超过，我们可以事先做个预处理来求出最优的方案。

这里dp[i][j]表示第一个数去除i位，第二个数去除j位的最优的代价，k表示当最后一位取k是的最优策略，中间用了一个tdp数组，这里是为了去除后效性，表示是由k-1结尾传来的数组，防止对于一种组合使用了两次或多次k。

const int INF = 1e18;
vector<vector<int>> dp(61, vector<int>(61, INF));
void init()
{
    dp[0][0] = 0;
    for (int k = 1; k <= 60; k++)
    {
        vector<vector<int>> tdp = dp;
        for (int i = 0; i <= 60; i++)
        {
            for (int j = 0; j <= 60; j++)
            {
                if (i + k <= 60)
                    tdp[i + k][j] = min(tdp[i + k][j], dp[i][j] + (1ll << k));
                if (j + k <= 60)
                    tdp[i][j + k] = min(tdp[i][j + k], dp[i][j] + (1ll << k));
            }
        }
        dp = tdp;
    }
}
void solve()
{
    int x, y, k;
    cin >> x >> y;
    auto decimalToBinaryUsingBitset = [&](int num) -> string
    {
        bitset<64> binary(num); // 假设输入的是32位整数
        string binaryStr = binary.to_string();
        // 移除前导零
        binaryStr.erase(0, binaryStr.find_first_not_of('0'));
        return binaryStr;
    };
    string sx = decimalToBinaryUsingBitset(x), sy = decimalToBinaryUsingBitset(y);
    // cout << sx << " " << sy << endl;
    int lenx = sx.length(), leny = sy.length();
    int pre = 0;
    while (pre < min(lenx, leny))
    {
        if (sx[pre] == sy[pre])
            pre++;
        else
            break;
    }
    // cout << pre << endl;
    int ans = INF;
    for (int i = 0; i <= pre; i++)
    {
        ans = min(ans, dp[lenx - pre + i][leny - pre + i]);

    }
    for (int i = lenx; i <= 60; i++)
    {
        for (int j = leny; j <= 60; j++)
        {
            ans = min(ans, dp[i][j]);
        }
    }
    cout << ans << endl;
}