CF-575-3

Codeforces Round #575 (Div. 3)

A.Three Piles of Candies

傻逼题，一人拿一堆，剩下一堆还能随便分，加起来除2

B.Odd Sum Segments

一个序列里只有奇数个奇数时和才是奇数

所以如果奇数个数少于序列数，或者剩下的奇数个数是偶数是不能的

能得话就一个区间放一个奇数，最后一个区间都塞进去

C.Robot Breakout

真气呀，我明明知道怎么做，就是写不出来

维护四个值ansxmin，ansxmax，ansymin,ansymax

ansxmin:x不能比（机器人不能向左走中的）原始x坐标中最大的小

ansxmax:x不能比（机器人不能向右走中的）原始x坐标中最小的大

ansymin:y不能比（机器人不能向上走中的）原始y坐标中最小的大

ansymax:y不能比（机器人不能向下走中的）原始y坐标中最大的小

要注意的是必须不能走的时候，才给这四个数赋初始值，否则是+-INF

当min > max时说明不能找到坐标下x，y

否则就输出min与max之间的一个数就行

D1.RGB Substring (easy version)

这个以看数据范围，暴力就可以了，每一种方案都试一下

D2.RGB Substring (hard version)

算是dp吧啊哈哈哈，其实就是优雅的遍历

从每一个字母出发，有三种形态把他分别作为’R’,’G’,’B’

dp的状态转移就是先找到前M需要修改的数

然后往后递推，往后一位的时候如果舍去的一位是修改过的，就-1，新加的一位如果是需要修改的就+1

三种形态同时维护

因为他是rgb这三个字母循环，所以说我们只要确定了开头的字母，后面只要用（index+开头）% 3就能知道那里应该对应的是哪个字母

题目代码：

/*-------------------------------------------------------------------------------------------*/
int dp[3][MAX];
string rgb = "RGB";
/* ------------------------------------------------------------------------------------------*/
 
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* --------------------------------------------------------------------------------------*/
    cin >> T;
    string str;
    while(T--)
    {
        cin >> N >> M;
        cin >> str;
        int ans = INF;
        dp[0][0] = (str[0] != rgb[0] ? 1 : 0) ;
        dp[1][0] = (str[0] != rgb[1] ? 1 : 0) ;
        dp[2][0] = (str[0] != rgb[2] ? 1 : 0) ;
        for(int i = 1;i < M;i++)
        {
            dp[0][i] = (str[i] != rgb[i % 3]     ? 1 : 0 ) + dp[0][i-1];
            dp[1][i] = (str[i] != rgb[(i+1) % 3] ? 1 : 0 ) + dp[1][i-1];
            dp[2][i] = (str[i] != rgb[(i+2) % 3] ? 1 : 0 ) + dp[2][i-1];
        }
        for(int i = 0;i < 3;i++)
        {
            ans = min(ans,dp[i][M-1]);
            if(ans == 0) break;
        }
        for(int i = M;i < N;i++)
        {
            dp[0][i] = dp[0][i-1] - (str[i - M] != rgb[(i - M) % 3] ? 1 : 0)  + (str[i] != rgb[i % 3]? 1 : 0);
            dp[1][i] = dp[1][i-1] - (str[i - M] != rgb[(i - M+1) % 3]? 1 : 0) + (str[i] != rgb[(i+1) % 3]? 1 : 0);
            dp[2][i] = dp[2][i-1] - (str[i - M] != rgb[(i - M+2) % 3]? 1 : 0) + (str[i] != rgb[(i+2) % 3]? 1 : 0);
            for(int j = 0;j < 3;j++)
            {
                ans = min(ans,dp[j][i]);
            }
            if(ans == 0) break;
        }
        cout << ans <<endl;
    }
    return 0;
}

其实dp不用数组的，前面的状态不保存也可以

E.Connected Component on a Chessboard

题目思路：

本以为是个难题，但是发现很好构造

如果b和w是相等的，一个配一个就很好构造，困难的是b，w相差很多的时候

通过画图我们可以发现当我们先把相等的b,w匹配为一条链的时候，然后再在链的上下添加多出来的颜色，这样可以容纳的差值是最大的

这个链很像一条C-H链

我们发现这个差值最大为2 * k+1（k为一白一黑匹配的数量，图中为3）

代码就是先构造主链（紫），再添支链（蓝）

题目代码：

void mycout(int a,int b,int d,int c)
{
    if(c > 2*d+1)
    {
        cout << "NO" <<endl;
        return ;
    }
    else
    {
        cout << "YES" <<endl;
    }
    for(int i = 0;i < 2*d;i++)
    {
        cout << a << " " << b+i << endl;
    }
    if(c == 2*d+1)
    {
        cout << a << " " << b-1 <<endl;
        c--;
    }
    int cnt = 0;
    for(int i = 0;;i+=2)
    {
        if(cnt == c) break;
        cout << a-1 << " " << b+i <<endl;
        cnt++;
        if(cnt == c) break;
        cout << a+1 << " " << b+i <<endl;
        cnt++;
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* --------------------------------------------------------------------------------------*/
    cin >> T;
    while(T--)
    {
        cin >> N >> M;//heibai
        if(N > M)
        {
            mycout(2,2,M,N-M);
        }
        else
        {
            mycout(2,3,N,M-N);
        }
    }
    return 0;
}