第一题：珠宝展示

在线测评链接：https://www.sspnote.com/oj/3/268

题目描述

薯条哥是一位珠宝设计师，她正在准备一场珠宝展。她有一系列独特的珠宝作品，每件都有其独特的价值。为了让展览更有趣，薯条哥决定按照特殊的顺序展示她的作品。她想按照以下规则来决定展示顺序：

a.首先选择价值居中的作品（如果作品数量为奇数）或两个中间价值的作品中较小的一个（如果作品数量为偶数）。

b.展示选中的作品，并将其从列表中移除。

重复步骤a和b，直到所有作品都被展示。

薯条哥想知道按照这个规则，她的珠宝作品会以什么顺序被展示。

输入描述

第一行包含一个正整数 $n(1\le n\le 10^5)$ ，表示珠宝作品的数量。

第二行包含 $n$ 个正整数 $a_1,a_2,...a_n(1\le a_i\le 10^9)$ ，表示每件珠宝作品的价值。

输出描述

输出一行，包含 $n$ 个整数，表示珠宝作品展示的顺序。

样例

4
1 9 8 5

5 8 1 9

题解：双指针

本题其实我们把问题拆解出来，就是求中位数。

但是需要注意，找到中位数之后，需要把当前的数字从数组移除。

因此，我们首先可以把数组进行排序，然后我们定义两个指针指向数组初始的中位数的位置。

如果两个指针 $l,r$ 指向的是同一个位置，那么只需要输出一个珠宝，然后把 $l$ 指针左移， $r$ 指针右移

如果指向的是不同的位置，那么需要按照大小顺序输出 $a[l],a[r]$ ，然后把 $l$ 指针左移， $r$ 指针右移

#include<bits/stdc++.h>
using namespace std;
const int N=1E5+10;
int n,a[N];
int main() {
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    int l=(n-1)/2,r=n/2;
    while(l>=0&&r<n){
        if(l==r){  //如果作品数量为奇数
            cout<<a[l]<<" ";
        }
        else{
            cout<<a[l]<<" "<<a[r]<<" ";
        }
        l--;
        r++;
    }
    return 0;
}

import java.util.*;

public class Main {
    static final int N = (int)1e5 + 10;
    static int n;
    static int[] a = new int[N];

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for(int i = 0; i < n; i++) a[i] = scanner.nextInt();
        Arrays.sort(a, 0, n);
        int l = (n - 1) / 2, r = n / 2;
        while(l >= 0 && r < n){
            if(l == r){  //如果作品数量为奇数
                System.out.print(a[l] + " ");
            }
            else{
                System.out.print(a[l] + " " + a[r] + " ");
            }
            l--;
            r++;
        }
    }
}

n = int(input().strip())
a = list(map(int, input().strip().split()))
a.sort()
l = (n - 1) // 2
r = n // 2
while l >= 0 and r < n:
    if l == r:  #如果作品数量为奇数
        print(a[l], end=" ")
    else:
        print(a[l], a[r], end=" ")
    l -= 1
    r += 1

第二题：非空子序列

在线测评链接：https://www.sspnote.com/oj/3/270

题目描述

给定一个仅由小写字母组成、长度为 $n$ 的字符串 $s$ 则字符串有 $2^n-1$ 个非空子序列。请你求出所有子序列中不同字符的个数总和，由于答案较大，你需要输出对 $10^9+7$ 取模后的结果。

输入描述

第一行输入一个只由小写字母组成的字符串 $s(1\le |s|\le 10^5)$

输出描述

在一行上输出一个整数，代表所有子序列中不同字符的个数总和对 $10^9+7$ 取模后的结果

样例1

aaaa

样例解释

每一个非空子序列都只有一个不同的字符，因此总共有 $2^4-1$ 个非空子序列，答案为15。

样例2

abcde

题解：贡献法计数+乘法原理

大家看到把结果对 $10^9+7$ 取模，一般不是数论的题就是动态规划，本题是前者，是一个贡献法计数的问题。

我们可以考虑每一个字母对答案的贡献，因此首先我们可以使用一个数组 $cnts[i]$ 来记录每一个字母出现的次数

考虑任意一个字母 $i$ ，它对整个答案的贡献就是：至少包含一个字母 $i$ 的子序列个数

对于字母 $i$ 而言，它出现的次数为 $cnts[i]$ ，那么显然，包含字母 $i$ 的子序列个数为 $2^{cnts[i]}-1$

而至于其他字母，它们的总个数为 $2^{n-cnts[i]}$ ，对于它们来说，可以选择，也可以不选择，因此对应的方案数为 $2^{n-cnts[i]}$ （因为可以一个字母都不选，所以不需要-1）

根据乘法原理，我们可以知道，字母 $i$ 的贡献为 $(2^{cnts[i]}-1)\times 2^{n-cnts[i]}$

#include<bits/stdc++.h>
using namespace std;
const int N=1E5+10,mod=1e9+7;
int cnts[26];
int pow_2[N];  //预处理2的次幂
int main() {
    string s;
    cin>>s;
    int n=s.size();
    pow_2[0]=1;
    for(int i=1;i<=n;i++){
        pow_2[i]=(1ll*pow_2[i-1]*2)%mod;
    }
    for(auto &ch:s){   //统计每一个字母出现的次数
        cnts[ch-'a']++;
    }
    int res=0;
    for(int i=0;i<26;i++){
        int num=cnts[i];
        res=(res+1ll*(pow_2[num]-1)*pow_2[n-num]%mod)%mod;
    }
    cout<<res<<endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    static final int N = 100010;
    static final int mod = (int)1e9+7;
    static int[] cnts = new int[26];
    static int[] pow_2 = new int[N];  //预处理2的次幂

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int n = s.length();
        pow_2[0] = 1;
        for(int i = 1; i <= n; i++){
            pow_2[i] = (int)((1L * pow_2[i-1] * 2) % mod);
        }
        for(char ch : s.toCharArray()){   //统计每一个字母出现的次数
            cnts[ch - 'a']++;
        }
        int res = 0;
        for(int i = 0; i < 26; i++){
            int num = cnts[i];
            res = (int)((res + 1L * (pow_2[num] - 1) * pow_2[n - num]) % mod);
        }
        System.out.println(res);
    }
}

mod = 10**9+7
cnts = [0]*26
s = input()
n = len(s)
pow_2 = [0]*(n+1)  #预处理2的次幂
pow_2[0] = 1
for i in range(1, n+1):
    pow_2[i] = (pow_2[i-1]*2)%mod

for ch in s:   #统计每一个字母出现的次数
    cnts[ord(ch)-ord('a')] += 1

res = 0
for i in range(26):
    num = cnts[i]
    res = (res + (pow_2[num]-1)*pow_2[n-num])%mod

print(res)

第三题：幸运数字

在线测评链接：https://www.sspnote.com/oj/3/269

题目描述

薯条哥是一位数学爱好者,她相信每个人都有自己的幸运数字。最近她发现,任何一个正整数 $n$ 都可以表示成若干个不同的2的次幂与3的次幂之和的形式，即：

$n=2^{a_1}\times 3^{b_1}+2^{a_2}\times 3^{b_2}+...+2^{a_m}\times 3^{b_m}$

现在，薯条哥希望你能帮她找到给定正整数 $n$ 的这样一个表示法，并将其中的 $m$ 个不同的整数 $\left \{ 2^{a_1}\times 3^{b_1},2^{a_2}\times 3^{b_2},2^{a_m}\times 3^{b_m} \right \}$ 从大到

小依次输出。

输入描述

第一行包含一个正整数 $T(1\le T\le 100)$ ，表示测试数据的组数。

接下来 $T$ 行,每行包含一个正整数 $n(1\le n\le 10^9)$ ，表示给定的初始数字。

输出描述

对于每组测试数据，第一行输出一个正整数 $m(1\le m\le 100)$ ,表示2的次幂项的个数。

第二行按照从大到小的顺序输出 $m$ 个不同的整数 $\left \{ 2^{a_1}\times 3^{b_1},2^{a_2}\times 3^{b_2},2^{a_m}\times 3^{b_m} \right \}$ ，相邻两项之间用一个空格隔开。

如果存在多种合法的表示法，你可以输出任意一种。

样例

样例解释

$10=2^3\times 3^0+2^1\times 3^0$

$15=2^2\times 3^1+2^0\times 3^1$

$123=2^5\times 3^1+2^3\times 3^1+2^0\times 3^1$

$33=2^3\times 3^1+2^1\times 3^1+2^0\times 3^1$

$321=2^5\times 3^2+2^3\times 3^1+2^1\times 3^1+2^0\times 3^1$

题解：位运算

本题看似很难，实际上非常easy。

我们知道，对于任何一个数字，都可以分解为若干个2的幂次的和，例如 $7=2^2+2^1+2^0,9=2^3+2^0$ ，因此我们完全可以忽略本题的

3的幂次，直接把整数 $n$ 拆分成若干个2的幂次的和，然后从大到小输出即可。

注意，输出结果需要按照从大到小来输出。

#include<bits/stdc++.h>
using namespace std;
int n,T;
void solve(){
    cin>>n;
    vector<int>res;
    for(int i=31;i>=0;i--){
        if(n>>i&1){
            res.push_back(1<<i);
        }
    }
    cout<<res.size()<<endl;
    for(int &x:res){
        cout<<x<<" ";
    }
    puts("");
}
int main() {
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static int n, T;

    public static void solve() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 31; i >= 0; i--) {
            if ((n >> i & 1) == 1) {
                res.add(1 << i);
            }
        }
        System.out.println(res.size());
        for (int x : res) {
            System.out.print(x + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        while (T-- > 0) {
            solve();
        }
    }
}

def solve():
    n = int(input())
    res = []
    for i in range(31, -1, -1):
        if n >> i & 1:
            res.append(1 << i)
    print(len(res))
    for x in res:
        print(x, end=" ")
    print()

T = int(input())
while T > 0:
    solve()
    T -= 1

25届秋招-科大讯飞算法岗笔试真题卷（1）

第一题：珠宝展示

在线测评链接：https://www.sspnote.com/oj/3/268

题目描述

输入描述

输出描述

样例

题解：双指针

第二题：非空子序列

在线测评链接：https://www.sspnote.com/oj/3/270

题目描述

输入描述

输出描述

样例1

样例2

题解：贡献法计数+乘法原理

第三题：幸运数字

在线测评链接：https://www.sspnote.com/oj/3/269

题目描述

输入描述

输出描述

样例

题解：位运算