Codeforces Round #687/12.2

A.一个n，m的监狱，每个格子都有人，一个时间每人都可往以上下左右移动一格，允许一个格子多个人，问所有人都到(r,c)需要的时间是多少？
x，y坐标分开考虑x最远是abs(x-r)与abs(r-1)的最大值y坐标最远是abs(y-c)与abs(c-1)的最大值，二者都取最大即可得到花费时间最长的坐标点

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n, m, r, c;
        cin >> n >> m >> r >> c;
        int x1 = abs(n-r);
        int y1 = abs(m-c);
        int x2 = abs(1-r);
        int    y2 = abs(1-c);
        cout << max(x1,x2) + max(y1,y2) << endl;
    }
}

B.
1-n的房子，每个房子都有自己的颜色，为了让所有房子变成一个颜色，你每次可以选取一个长度不超过k的区间[l,r]然后对这个区间的每个房子都粉刷成任意颜色。问最少的次数。
颜色种类数据不超过100，暴力枚举即可。每次遇到颜色不一样的就粉刷一个长度为k的区间就行。

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int c[N];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;
        for(int i=1; i<=n; i++)
            cin >> c[i];
        int ans = 1e9;
        for(int i=1; i<=100; i++){
            int s = 0;
            for(int j=1; j<=n; j++){
                if(c[j] != i) s++, j+=k-1;
            }
            ans = min(ans, s);
        }
        cout << ans << endl;
    }
}

C.
你在设计一个游戏,有n个格子，1代表格子上一开始有平台，0代表没有,游戏会给你一个小球，小球一开始弹到序号为p的然后接着往后弹到p+k...，小球只能打到有平台的格子，为了让小球能够到达或超过终点，你花时间x在格子设置平台，或是花时间y删除第一个格子(序号将重新标记)。问最少花费多少时间
看错题了，原来是删第一个格子...
那么dp[i]表示经过i到最后的花费，在所有dp[i]+y*(i-p)中取个最小就行了。有点后缀和的意思。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char a[100005];
ll dp[100005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n, p, k, x, y;
        memset(dp, 0, sizeof(dp));
        ll ans = 1e18;
        scanf("%d%d%d",&n,&p,&k);
        scanf("%s", a+1);
        scanf("%d%d",&x,&y);
        for(int i=n; i>=p; i--){
            dp[i] = x*(1-a[i]+'0');
            if(i+k <= n)
            dp[i] += dp[i+k];
            ans = min(ans, dp[i]+(i-p)*y);
        }
        printf("%lld\n",ans);
    }
}

D.现在有一个非递减的数列，你可以把其中连续的两个数字异或，并用异或的值代替这两个数字原来位置，数列长度会减少1，问最少多少次可以将这个数列打破非递减规则。
构造发现如果有连续3个的最高位1位置一样，总可以1次达成目的。那么只需要考虑同一最高位至多出现2次的情况，那么在最大值1e9的情况下，当序列中数字不冲突的时候，至多有60个数字，那么题目就被剪枝到60以下了。
考虑两种情况：一种情况是一个区间直接异或起来。
还有一种情况是两个区间分别异或再合并起来的情况。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cout << #x << ":" << x <<endl;
#define N 200005
int a[N], b[N];
signed main()
{
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        b[i] = b[i-1]^a[i];
    }
    if(n>60){
        cout << 1 << endl; return 0;
    }
    int ans = 1e18;
    for(int l=1; l<n; l++){
        for(int i=1; i+l-1<=n; i++){
            int tmp = b[i+l-1]^b[i-1];
            if(tmp >= a[i-1])
            {
                if(i+l-1 == n || tmp <= a[i+l])
                    continue;
            }
            ans = min(ans, l-1);
        }
    }

    for(int l=1; l<=n-1; l++){
        for(int i=1; i+l-1 <= n; i++){
            for(int j=i+l; j<=n; j++){
                int t1 = b[i+l-1]^b[i-1];
                int t2 = b[j]^b[i+l-1];
                if(t1 <= t2) continue;
                ans = min(ans, l-1+j-i-l);
            }
        }
    }

    if(ans == 1e18)
        cout << -1 << endl;
    else
        cout << ans << endl;
}