Codeforces Round ＃809 (Div. 2) A~D

比赛链接

A.Another String Minimization Problem

题意：一共T组数据，每次给定一个n,m，n表示数组a的大小，m表示一个所有字符为B的字符串S的长度。
每次有两种操作：1.将s[a[i]]改为A 或者 将s[m+1+a[i]]改为A。
输出操作之后的字典序最小的S。
其中：1<=t<=2000, 1 <= n, m <= 50, 1 <= a[i] <= m;
思路：暴力，对于每一个a[i]，考虑一下a[i]和a[m+1-a[i]]哪个更小，就执行哪个操作，以达到字典序最小的目的。

#include <bits/stdc++.h>

using namespace std;

int T;
int n, m;
int main()
{
    
    cin >> T;
    while(T --)
    {
    
        cin >> n >> m;
        string s(m, 'B');//定义一个长度为m,且全部字符为B的字符串s;
        
        //每次读入一个数操作即可，不用存数组
        while (n -- )
        {
    
            int x;
            cin >> x;
            x --;//题目下标是从1开始，但是我们定义的字符串下标从0开始。
            x = min(x, m - 1 - x);//为什么这里不是题目中的x和m + 1 - x呢。
            //x和m + 1 - x关于中点对称（从下标1开始的时候）
            //x和m - 1 - x关于中点对称（从下标0开始的时候）
            if(s[x] == 'B') s[x] =  'A';
            else s[m - 1 - x] =  'A';
        }
        cout << s << endl;
    }
    return 0;
}

总结：对于一个长度为n的数组a,其中关于中点对称的点的下标之间的关系为：

• x 和 m + 1 - x关于中点对称（下标从1开始的时候）
• x 和 m - 1 - x关于中点对称（下标从0开始的时候）
• 中点对称：从左边和右边数过来相同的距离。

B. Making Towers

事实证明，当且仅当i和j具有不同的奇偶性时，它们才能被这样放置。首先，如果它们具有相同的奇偶性，就不可能这样放置它们。我们将遍历所有方块$a[i]$，保持$dp[p][c]$，其中包含颜色为c的塔的最大尺寸，其中塔中包含的最后一个区块的索引为奇偶性p（p=0表示偶数索引，p=1表示奇数索引）。如果当前索引是偶数，我们设置$dp[0][c[i]]$=$max（dp[0][c[i]],dp[1][c[i]]+1）$。如果是奇数，我们设置$dp[1][c[i]]=max(dp[1][c[i]],dp[0][c[i]]+1)$ 。该解决方案在线性时间内运行。

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;
typedef long long ll;

int t, n;
int dp[2][N];//dp[i][j]:颜色为j且最后一块的索引的奇偶性为i（0是偶数索引，1是奇数索引）的塔的最大塔长。


int main()
{
    
    cin >> t;
    while(t --)
    {
    
        cin >> n;
        //dp数组初始化
        for(int i = 0; i < 2; i ++)
            for(int j = 1; j <= n; j ++)//每种颜色一开始的最长塔都是0个
            dp[i][j] = 0;
        //对于要放的n个方块
        for(int i = 1; i <= n; i ++)
        {
    
            int x;
            cin >> x;
            //只有奇偶性不一样才可以放在一起。
            dp[i & 1][x] = max(dp[i & 1][x], dp[(i ^ 1) & 1][x] + 1);
        }
        
        for(int i = 1; i <= n; i ++)
            cout << max(dp[0][i], dp[1][i]) << " ";
          
          cout << endl;
    }
    return 0;
}

C. Qpwoeirut And The City

题意：一共T组数据，每一组数据有一个n表示一共有n栋房子，然后输入每一栋房子的层数$h_i$；如果第$i$栋楼的层数大于第$i-1$和第$i+1$栋楼的层数时，说明第$i$栋楼是凉爽的。现在可以在原有的楼上面建楼层，请问要使凉爽的楼的数量最多且需要建的楼层数最少需要建多少楼层。（第1和第n栋楼不会成为凉爽的楼）
其中：1 <= t <= $10^4$, 3 <= n <= $10^5$,1 <= $h_i$ <= $10^9$
思路：
首先，没有两个相邻的建筑可以同时凉爽，说明对于奇数n来说凉爽的建筑最多有$(n-1)/2$个，对于偶数来说最多有$(n-2)/2$个。
1.当n为奇数的时候，要让凉爽的建筑最多只有一种方案。
01010…01010（0代表不凉爽，1代表凉爽）
2.当n为偶数的时候，方案有多种，这意味着城市中正好有一对相邻的建筑是正常的，也就是说，这些建筑必须以下列配置之一排列…
01010…010100
01010…010010
01010…001010
⋮
010100…01010
010010…01010
001010…01010
对于奇数n，解决方案相对简单。只要找到使每座交替的建筑（从第二座开始）变凉所需的总楼层，这就是答案。
对于偶数n，解决起来就比较复杂了。首先，找出达到上述第一种配置所需的楼层数。然后，在随后的每个配置中进行循环，每次都使用之前的配置，在O(1)时间内得到新配置所需的楼层数。这样就能在O(n)时间内找到解决方案。
比如第四个样例。
4 2 1 3 5 3 6 1
4 2 1 3 5 3 6 1
4 2 1 3 5 3 6 1
4 2 1 3 5 3 6 1
对此我们可以发现一个规律，相邻两行之间只用一个点不一样。所以可以之间用上一个方案的答案减去不同的加上当前的即可。
第一个配置：（5-2）+（6-3）+（7-3）=10。
第二种配置。10 - (7 - 3) + (6 - 6) = 6.
第3种配置。6 - (6 - 3) + (5 - 5) = 3.
第4种配置。3 - (5 - 2) + (4 - 1) = 3.
答案是这些数值的最小值，也就是3。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

const int N = 100100;

int T, n;
ll a[N];
ll get(int n)
{
    
    return (max(0ll,max(a[n - 1], a[n + 1]) + 1 - a[n]));
}
int main()
{
    
    cin >> T;
    while(T --)
    {
    
        cin >> n;
        for(int i = 1; i <= n; i ++)
            scanf("%lld", &a[i]);
        //如果是奇数的话
        if(n & 1)
        {
    
            ll ans = 0;
            for(int i = 2; i < n; i += 2)
                ans += get(i);
            cout << ans << endl;
            continue;
        }
        //如果是偶数的话
        ll tot = 0;//第一种方案的花费
        for(int i = 2; i < n;  i += 2)
            tot += get(i);
        ll ans = tot;//最优解
        for(int i = n - 1; i > 1; i -= 2)
        {
    
            tot -= get(i - 1);//减去上一个。
            tot += get(i);//加上当前的。
            ans = min(ans, tot);
        }
        cout << ans << endl;
    }
    return 0;
}

D1. Chopping Carrots (Easy Version)

题意：一共T组数据，每组数据给出一个n,k,其中n为数组的长度，然后给出数组a的每一个元素。现在构造一个数组p的花费是$ma{x}_{1\le i\le n}\lfloor (a[i]/p[i])\rfloor$ - $mi{n}_{1\le i\le n}\lfloor (a[i]/p[i])\rfloor$。
其中$1\le p_i\le n,1\le i\le n,1\le t\le 300,1\le n,k\le 3000,$。数组a递增。
思路：
假定v是$\lfloor (a[i]/p[i])\rfloor$的min值，根据数据范围我们可以知道v的取值范围是[0.a[0]]的。
所以，先枚举v,对于每一个a[i],都可以通过公式$p[i]=\lfloor (a[i]/v)\rfloor$,得到p之后，再计算
$max\lfloor (a[i]/p[i])\rfloor$取一个最大值。然后将最大值和最小值的差值和ans最优解取最小。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 3030;

int t, n, k;
int a[N];//序列a;
int main()
{
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> t;
    while(t --)
    {
    
        cin >> n >> k;
        for(int i = 0; i < n; i ++) cin >> a[i];
        
        int ans = 1e9;
        //枚举ai/pi的最小值定为v 最小值的取值范围[0,a[0];
        for(int v = 0; v <= a[0]; v ++)
        {
    
            int cm = v;
            //一次考虑每一个a[i]
            for(int i = 0; i < n; i ++)
            {
    
                int p = min(k, (v ? (a[i]) / v : k));
                cm =  max(cm, a[i] / p);
            }
            ans = min(ans, cm - v);
        }
        cout << ans << endl;
    }
    return 0;
}