得物 秋招 2023.08.29 编程题目与题解

1、Cheems的漂亮糖葫芦

小狗Cheems在街边买到了一串糖葫芦，这串糖葫芦是由\(n\)个大写字母构成的。Cheems觉得这申糖葫芦虽然美味，却并不一定能称得上漂亮。当糖葫芦中包含了一串长度为\(x\)的连续子串，满足正序读与倒序读一模一样时（即是一串回文串），它会觉得这整串糖葫芦是漂亮的。

输入

第一行两个以空格隔开的正整数\(n\)和\(x\)，表示糖葫芦串长度和Cheems对于子串要求的长度。

第二行一个长为\(n\)的仅包含大写字母的字符串\(s\)，代表糖葫芦。

\(1\le n,x\le 5000\)

输出

如果这串糖葫芦是漂亮的，输出\(1\)，否则输出\(0\)。

样例

输入：
6 2
AACBBE

输出：
1

提示：
可以找到存在子串"AA"，长度为2，且正着读与倒着读一模一样。

解答

直接使用暴力的方式判断是否存在长度至少为\(x\)的回文串即可。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5004;
char s[N];
int n,x;
int main(){
    scanf("%d %d %s",&n,&x,s+1);
    int ok=0;
    for(int i=1;i<=n&&!ok;i++){
        int l=i,r=i;
        for(;1<=l&&r<=n&&s[l]==s[r];--l,++r);
        if(r-l-1>=x) ok=1;
        if(i<n){
            l=i,r=i+1;
            for(;1<=l&&r<=n&&s[l]==s[r];--l,++r);
            if(r-l-1>=x) ok=1;
        }
    }
    printf("%d\n",ok);
}

2、最高的楼

市容市貌建设是一个很重要的课题，在某市的规划中有这样一条要求，位于一条街道上的相邻位置的楼的高度差不能招过\(1\text{m}\)。每栋楼的高度都是整数。某同学第一次来到这个城市，他听人提起在一条街上，有\(n\)栋连续的建筑，这些建筑的总高度是\(m\)米，他想知道在这条街道上，第\(x\)栋建筑可能的最高高度是多少，不存在高度为0的建筑，也就是说这\(n\)栋建筑至少高\(1\text{m}\)。

输入

输入仅有一行，包含三个整数\(n,m,x\)。\((1\le x\le n\le m\le 10^9)\)

输出

输出仅包含一个正整数，请你输出第\(x\)栋建筑可能的最高高度是多少。

样例

输入：
5 6 1

输出：
2

提示：
5个建筑物，总高6米，可以按如下分配：2 1 1 1 1，此时最高高度为2

解答

这道题可以使用二分法进行求解。接下来判断第\(x\)栋楼是否可以有高度\(h\)。

为了确保第\(x\)栋楼能够到达\(h\)，那么其他楼的高度尽可能低。于此同时为了维持这\(n\)栋楼的相邻高度差不超过\(1\)这个性质，对于第\(y\)栋楼，如果\(y>x\)，那么这栋楼就要比左边那栋楼矮\(1\)米；如果\(x<y\)，那么这栋楼就要比右边那栋楼矮\(1\)米，直到恰好高\(1\)米。

这种情况是最节省米数的消耗的，我们可以通过逐渐补充每栋楼的高度，直到总和\(m\)米，如果总和达不到\(m\)米，那么这栋楼必定不止高\(h\)米。因此，我们不需要考虑米数消耗的上界。

更一般的来说，如果第\(x\)栋楼高\(h\)米，那么最节省材料的方法的形状如下：

\[1,1,\dots,1,2,3,\dots,h-1,h,h-1,h-2,\dots 3,2,1,\dots,1\]

注意，两端可能没有取到\(1\)就结束了。

由于两边的处理方式是一样的，因此只需要考虑其中一侧。令\(f(x,h)\)表示现在有\(x\)栋楼，其中最后一栋高度为\(h\)时，最少需要消耗的米数。按照等差数列求和公式，那么可以写出

\(f(x,h)= \left \{\begin{aligned} &\dfrac{(2h-x+1)x}{2} & & \text{if}\quad h\ge x \\ &\dfrac{(h+1)h}{2}+x-h & & \text{if}\quad h<x \\ \end{aligned}\right.\)

因此，判断第\(x\)栋楼高度是否为至少\(h\)，只需要判断\(f(x,h)+f(n-x+1,h)-h\le m\)是否满足即可。

代码

n, m, x = map(int, input().split())


def cal2(x, h):
    if h >= x:
        return (h + h - x + 1) * x // 2
    else:
        return (h + 1) * h // 2 + x - h


def cal(h):
    return cal2(x, h) + cal2(n - x + 1, h) - h


l, r = 1, m
while l < r:
    mid = (l + r + 1) >> 1
    if cal(mid) <= m:
        l = mid
    else:
        r = mid - 1
print(l)