写在前面

本次给大家带来10月15日的百度笔试题的3道题，本套题目

第一题:分类讨论，优先选完得分位置再选其他位置，特判一下偶数有一个位置不得积分也不减积分即可 第二题:模拟题。模拟每次移动字符的过程,不难发现每次本质是把前一次移动位置的后面第二位字符往后移动，每次标记使用过的字符，模拟该过程n次即可 第三题:组合数。打表可得当n为偶数时最后一列的系数为杨辉三角,加减取决于n是否是4的倍数，如果n为奇数可以转换成偶数来做,预处理组合数计算即可

第1题-计算积分

题目内容

整数 ~ ，计算选择 个数最多能获得多少积分。

计分规则:初始积分为 ，对于被选取的整数 ，如果 没选，则积分加 。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 代表数据组数，每组测试数据描述如下:

在一行上输入两个整数 ，含义和题面描述一致。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表最多能获得的积分。

样例1

输入

2
1 1
4 2

输出

1
2

说明

第一个样例选择 ，积分为 。

第二个样例一种可行方案为 ，积分为 。

思路

对于奇数偶数分开讨论

1.n是奇数的情况如果优先选择奇数可以获得(n+1)/2个积分，偶数则是(n-1)/2个积分，那么我们优先填奇数，如果还有剩余的数则都是减回去的。

2.n是偶数的情况优先奇数优先偶数都是一样的，假设我们优先选择偶数，那么剩余的数-1则是需要减回去的(因为再选择1的话不会导致积分变少)

详细实现看代码

#include <bits/stdc++.h>
using namespace std;

long long n, k, res;  // 定义全局变量n、k和res，n表示总数，k表示选择的个数，res表示结果（最多能获得的积分）
int t;  // 定义全局变量t，表示测试数据的组数

int main() {
    int t;  // 测试数据组数
    cin >> t;  // 输入测试数据的组数
    while(t--) {  // 循环遍历每一组测试数据
        cin >> n >> k;  // 输入每组数据中的n和k，n是数的范围，k是要选择的个数
        
        // 如果n是奇数
        if(n % 2 == 1) {
            // res先计算为(n+1)/2与k中较小的那个数
            // 这一步的意思是优先选择前面一半的数，因为选择一个整数i并且i+1没有被选的话，可以得1分
            res = min((n+1)/2, k);
            
            // 更新k，扣除已经选中的数量
            k -= res;
            
            // 如果还剩下要选择的数量（即k大于0），说明选了后面的数，扣分
            if(k > 0) {
                res -= k;  // 选了后面的数会扣除相应的积分
            }
        } 
        // 如果n是偶数
        else {
            // res先计算为n/2与k中较小的那个数
            // 这一步的意思是选择前面的一半数（因为它们更容易得分）
            res = min(n/2, k);
            
            // 更新k，扣除已经选中的数量
            k -= res;
            
            // 如果k大于0，说明还有剩余需要选择的数，这些会影响积分
            if(k > 0) {
                res -= k - 1;  // 对于n为偶数的情况，剩余的k会扣掉一些积分
            }
        }
        
        // 输出每组测试数据的结果，即最多能获得的积分
        cout << res << '\n';
    }

    return 0;  // 返回0，程序正常结束
}

python

t = int(input())  # 输入测试数据组数
for _ in range(t):  # 循环遍历每一组测试数据
    n, k = map(int, input().split())  # 输入每组数据中的n和k，n是数的范围，k是要选择的个数
    
    # 如果n是奇数
    if n % 2 == 1:
        # res先计算为(n+1)//2与k中较小的那个数
        res = min((n + 1) // 2, k)
        # 更新k，扣除已经选中的数量
        k -= res
        
        # 如果还剩下要选择的数量（即k大于0），说明选了后面的数，扣分
        if k > 0:
            res -= k  # 选了后面的数会扣除相应的积分
    # 如果n是偶数
    else:
        # res先计算为n//2与k中较小的那个数
        res = min(n // 2, k)
        # 更新k，扣除已经选中的数量
        k -= res
        
        # 如果k大于0，说明还有剩余需要选择的数，这些会影响积分
        if k > 0:
            res -= (k - 1)  # 对于n为偶数的情况，剩余的k会扣掉一些积分
    
    # 输出每组测试数据的结果，即最多能获得的积分
    print(res)

java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 进行快速输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();  // 用于快速输出结果
        int t = Integer.parseInt(br.readLine());  // 输入测试数据组数
        
        while (t-- > 0) {
            // 读取每组数据
            String[] input = br.readLine().split(" ");
            long n = Long.parseLong(input[0]);  // 输入n，n是数的范围
            long k = Long.parseLong(input[1]);  // 输入k，k是要选择的个数
            long res;
            
            // 如果n是奇数
            if (n % 2 == 1) {
                // res先计算为(n+1)/2与k中较小的那个数
                res = Math.min((n + 1) / 2, k);
                // 更新k，扣除已经选中的数量
                k -= res;
                
                // 如果还剩下要选择的数量（即k大于0），说明选了后面的数，扣分
                if (k > 0) {
                    res -= k;  // 选了后面的数会扣除相应的积分
                }
            }
            // 如果n是偶数
            else {
                // res先计算为n/2与k中较小的那个数
                res = Math.min(n / 2, k);
                // 更新k，扣除已经选中的数量
                k -= res;
                
                // 如果k大于0，说明还有剩余需要选择的数，这些会影响积分
                if (k > 0) {
                    res -= (k - 1);  // 对于n为偶数的情况，剩余的k会扣掉一些积分
                }
            }
            
            // 将结果追加到 StringBuilder 中
            sb.append(res).append("\n");
        }
        
        // 最终输出所有结果
        System.out.print(sb.toString());
    }
}

第2题-字符串

题目内容

长度为 只包含小写字母的字符串 ，下标 开始。

进行 次操作第 次操作将 移动到字符串末尾。输出 次操作后的字符串。

例如字符串""，第一步""，第二步""，第三步""，第四步""，第五步""。

输入描述

在一行上输入一个由小写字母构成的字符串，长度记为 。

输出描述

在一行上输出一个字符串，表示操作后的字符串。

样例1

输入

paectc

输出

accept

说明

第一步 ，第二步 ，第三步 ，第四步 ，第五步 ，第六步 。

样例2

输入

abqde

输出

bdaeq

解题思路

本题的关键在于如何有效地模拟每一次的字符移动。本质是每次都要往后移动两次，每一次操作都要将当前下标的字符移动到字符串末尾并标记已用，重复这个过程直到完成 ( n ) 次操作。考虑到字符串的长度可能达到 ( 10^6 )，我们需要采用高效的方法以避免超时。

c++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main()
{
	ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    string s;
    cin>>s;
    int n=s.size();
    int pos=0;
    for(int i=0;i<n;i++)
    {
        s+=s[pos];
        s[pos]='?';//标记已经用过的
        int c=0;
        if(i==n-1)break;
        while(c<2)//找下一个要移动到末尾的
        {
            c+=s[pos]!='?';
            pos++;
            if(c==2)
            {
                pos--;
                break;
            }
        }
    }
    for(int i=0;i<s.size();i++)
    {
        if(s[i]!='?')cout<<s[i];
    }
}

python

def main():
    s = input().strip()
    n = len(s)
    pos = 0
    
    # 转换字符串
    for i in range(n):
        s += s[pos]  # 追加 pos 位置的字符
        s = s[:pos] + '?' + s[pos + 1:]  # 标记该字符为已用
        c = 0
        
        if i == n - 1:
            break
        
        # 找下一个要移动到末尾的字符
        while c < 2:
            if s[pos] != '?':
                c += 1
            pos += 1
            
            if c == 2:
                pos -= 1  # 移回到上一个有效位置
                break

    # 打印转换后的字符串
    result = ''.join([char for char in s if char != '?'])
    print(result)

if __name__ == "__main__":
    main()

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int n = s.length();
        int pos = 0;

        // 转换字符串
        for (int i = 0; i < n; i++) {
            s += s.charAt(pos);  // 追加 pos 位置的字符
            s = s.substring(0, pos) + '?' + s.substring(pos + 1);  // 标记该字符为已用
            int c = 0;

            if (i == n - 1) {
                break;
            }

            // 找下一个要移动到末尾的字符
            while (c < 2) {
                if (s.charAt(pos) != '?') {
                    c++;
                }
                pos++;

                if (c == 2) {
                    pos--;  // 移回到上一个有效位置
                    break;
                }
            }
        }

        // 打印转换后的字符串
        StringBuilder result = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (ch != '?') {
                result.append(ch);
            }
        }
        System.out.println(result.toString());
    }
}

第3题-数组交替

题目内容

由个整数构成的数组{}，我们有如下操作:

• 你必须在这些整数之间交替写下加减符号，例如假设数组初始值 {}，交替写下加减符号变为;

• 此时会生成第二行数组{}，即{};随后，再次交替写下加减符号变为(由于上一行末尾是，所以这一行的开头是);

• 此时会生成第三行数组{}，继续重复上述操作;

• 直到最后只剩下唯一一个数字时，中止操作，在上方的样例中，最后剩下的数字为。

  现在，你需要独立求出给定的数组剩下的最后一个值是多少。

输入描述

第一行输入一个整数()代表数组中的元素数量。

第二行输入个整数 ()代表数组元素。

输出描述

在一行上输出一个整数，表示剩下的最后一个值。由于答案可能很大，只需要输出答案对取模的结果。

样例1

输入

4
1 2 3 4

输出

1000000005

说明

该样例已在题面中说明，注意，负数也需要取模。

本题直接看很难看出规律，打表可以发现当为偶数时规律很明显,如下图:

不难看出最后每个的系数跟杨辉三角有关,手玩几个样例可以发现当为的倍数时最后一列是相减,非的倍数时最后一列是相加,当为奇数时可以先算一列转换成偶数来做.

记组合数,那么当n为偶数时最后一列的系数每两个数一组依次为,直接预处理组合数再根据上述规律算即可

c++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
ll a[N],f[N],g[N];
int n;
ll qmi(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
void init()//预处理
{
    g[0]=f[0]=1;
    for(int i=1;i<N;i++)
    {
        f[i]=f[i-1]*i%mod;
        g[i]=g[i-1]*qmi(i,mod-2)%mod;
    }
}
ll c(ll n,ll m)
{
    if(n<m)return 0;
    return f[n]*g[n-m]%mod*g[m]%mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init();
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    if(n<=2)//特判n<=2的情况
    {
        cout<<(a[1]+a[2])%mod<<endl;
        return 0;
    }
    if(n&1)//n为奇数时可以转化成偶数来做
    {
        int mk=1;
        for(int i=1;i<n;i++)
        {
            a[i]=a[i]+a[i+1]*mk;
            mk=-mk;
        }
        n--;
    }
    int mk=(n%4)?1:-1;//打表可得
    ll res=0;
    for(int i=1;i<=n;i+=2)
    {
        ll temp=c(n/2-1,i/2);//本质是杨辉三角
        res=(res+(a[i]+mk*a[i+1])*temp+mod)%mod;
    }
    cout<<(res+mod)%mod<<endl;
}

python

import sys
sys.setrecursionlimit(10**5)
MOD = 10**9 + 7
N = 10**5 + 10
a = [0] * N
f = [0] * N
g = [0] * N

def qmi(a, b):
    res = 1
    while b:
        if b & 1:
            res = res * a % MOD
        b >>= 1
        a = a * a % MOD
    return res

def init():  # 预处理
    g[0] = f[0] = 1
    for i in range(1, N):
        f[i] = f[i - 1] * i % MOD
        g[i] = g[i - 1] * qmi(i, MOD - 2) % MOD

def c(n, m):
    if n < m:
        return 0
    return f[n] * g[n - m] % MOD * g[m] % MOD

def main():
    init()
    n = int(input())
    input_list = list(map(int, input().split()))  # 将一行输入按空格分割并转为整数列表
    for i in range(1, n + 1):
        a[i] = input_list[i - 1]  # 把输入列表的值赋给 a 数组

    if n <= 2:  # 特判n<=2的情况
        print((a[1] + a[2]) % MOD)
        return

    if n & 1:  # n为奇数时可以转化成偶数来做
        mk = 1
        for i in range(1, n):
            a[i] = a[i] + a[i + 1] * mk
            mk = -mk
        n -= 1

    mk = 1 if (n % 4) else -1  # 打表可得
    res = 0
    for i in range(1, n + 1, 2):
        temp = c(n // 2 - 1, i // 2)  # 本质是杨辉三角
        res = (res + (a[i] + mk * a[i + 1]) * temp + MOD) % MOD

    print((res + MOD) % MOD)

if __name__ == "__main__":
    main()

java

import java.util.*;
public class Main {
    static final int N = 100010, mod = 1000000007;
    static long[] a = new long[N], f = new long[N], g = new long[N];
    static int n;

    static long qmi(long a, long b) {
        long res = 1;
        while (b != 0) {
            if ((b & 1) != 0) res = res * a % mod;
            b >>= 1;
            a = a * a % mod;
        }
        return res;
    }

    static void init() { // 预处理
        g[0] = f[0] = 1;
        for (int i = 1; i < N; i++) {
            f[i] = f[i - 1] * i % mod;
            g[i] = g[i - 1] * qmi(i, mod - 2) % mod;
        }
    }

    static long c(long n, long m) {
        if (n < m) return 0;
        return f[(int) n] * g[(int) (n - m)] % mod * g[(int) m] % mod;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        init();
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) a[i] = sc.nextLong();
        if (n <= 2) { // 特判n<=2的情况
            System.out.println((a[1] + a[2]) % mod);
            return;
        }
        if ((n & 1) != 0) { // n为奇数时可以转化成偶数来做
            int mk = 1;
            for (int i = 1; i < n; i++) {
                a[i] = a[i] + a[i + 1] * mk;
                mk = -mk;
            }
            n--;
        }
        int mk = (n % 4 != 0) ? 1 : -1; // 打表可得
        long res = 0;
        for (int i = 1; i <= n; i += 2) {
            long temp = c(n / 2 - 1, i / 2); // 本质是杨辉三角
            res = (res + (a[i] + mk * a[i + 1]) * temp + mod) % mod;
        }
        System.out.println((res + mod) % mod);
    }
}