笔试强训week6

day1

Q1   难度⭐⭐

小红的口罩_牛客小白月赛41 (nowcoder.com)

题目
疫情来了,小红网购了 n 个口罩。
众所周知,戴口罩是很不舒服的。小红每个口罩戴一天的初始不舒适度为 ai​。
小红有时候会将口罩重复使用(注:这是非常不卫生的!),每次重复使用时,该口罩的不舒适度会翻倍!
小红想知道,自己在不舒适度总和不超过 k 的情况下,最多能用现有的口罩度过多少天?

输入描述:第一行输入两个正整数 n 和k ,分别代表口罩的总数、以及小红最多能忍受的不舒适度
                  总和。 第二行输入 n 个正整数 ai,用空格隔开。分别代表每个口罩初始的不舒适度。

输出描述:一个整数,代表小红最多能度过的天数。

思路

小根堆,每次用k减堆顶元素,将堆顶弹出并插入2倍堆顶

#include <vector>
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    int n, k, x;
    cin >> n >> k;
    priority_queue<int, vector<int>, greater<int> > a;
    while(n --)
    {
        cin >> x;
        if(x > k)
            continue;
        else
            a.push(x);
    }
    int ans = 0;
    while(k > 0)
    {
        int z = a.top();
        k -= z;
        a.pop();
        a.push(z * 2);
        ans ++;
    }
    cout << ans - 1 << endl;
    return 0;
}

Q2   难度⭐⭐⭐

春游 (nowcoder.com)

题目
盼望着,盼望着,东风来了,春天脚步近了
值此大好春光,老师组织了同学们出去划船,划船项目收费如下:
双人船最多坐两人,也可以坐一人,收费a元
三人船最多坐三人,也可以坐两人或者一人,收费b元
本次出游加上带队老师共n人,如何安排能使得花费最小呢?

输入描述:第一行给出一个正整数 T(1<T<1000),代表测试数据的组数。
                  接下来 T 行每行给出三个正整数n,a,b,含义如题。

输出描述:每组输入输出一行,代表最小的花费

思路

先判断a和b的人均消费哪个低,将a或b安排满人并将剩下的人分类安排

#include <iostream>
using namespace std;

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        long long n, a, b;
        cin >> n >> a >> b;
        if(n <= 2)
        {
            if(a > b) cout << b << endl;
            else cout << a << endl;
            continue;
        }
        long long ans = 0;
        if(a / 2 < b / 3)
        {
            ans += (n / 2) * a;
            n %= 2;
            if(n)
                ans += min(a, b - a);
        }
        else
        {
            ans += (n / 3) * b;
            n %= 3;
            if(n == 1) 
                ans += min(min(a, b), 2 * a - b);
            else if (n == 2)
                ans += min(a, b);
        }
        cout << ans << endl;
    }
    return 0;
}

Q3   难度⭐⭐⭐

数位染色_牛客题霸_牛客网 (nowcoder.com)

题目
小红拿到了一个正整数 𝑥 。她可以将其中一些数位染成红色。然后她想让所有染红的数位数字之和等于没染色的数位数字之和。
她不知道能不能达成目标。你能告诉她吗?

输入描述:一个正整数 𝑥
输出描述:如果小红能按要求完成染色,输出"Yes"。否则输出"No"。

思路

定义k为每一位是否染色的所有情况,分别遍历数组判断有没有可能按要求完成染色

#include <iostream>
using namespace std;

bool fun(string num)
{
    int sum = 0;
    for(char c : num)
        sum += c - '0';
    int n = num.size();
    for(int k = 0; k < (1 << n); k ++)
    {
        int yes_sum = 0;
        for(int i = 0; i < n; i ++)
            if(k & (1 << i))
                yes_sum += num[i] - '0';
        int no_sum = sum - yes_sum;
        if(yes_sum == no_sum)
            return true;
    }
    return false;
}

int main()
{
    string s;
    cin >> s;
    if(fun(s))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

day2

Q1   难度⭐⭐

素数回文_牛客题霸_牛客网 (nowcoder.com)

题目
现在给出一个素数,这个素数满足两点:
1、  只由1-9组成,并且每个数只出现一次,如13,23,1289。
2、  位数从高到低为递减或递增,如2459,87631。
请你判断一下,这个素数的回文数是否为素数(13的回文数是131,127的回文数是12721)。

输入描述:输入只有1行。第1行输入一个整数t,保证t为素数。

输出描述:输出一行字符串,如果t的回文数仍是素数,则输出“prime”,否则输出"noprime"。

思路

 生成回文,判断素数

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool isPrime(long long n)
{   
    for(long long i = 2; i <= n / i; i ++)
        if(n % i == 0)
            return false;
    return true;
}

int main()
{
    string s;
    cin >> s;

    for(int i = s.size() - 2; i >= 0; i --)
        s += s[i];
    long long ss = stoll(s);

    if(isPrime(ss))
        cout << "prime" << endl;
    else
        cout << "noprime" << endl;
    
    return 0;
}

Q2   难度⭐⭐⭐

活动安排_牛客题霸_牛客网 (nowcoder.com)

题目
给定𝑛n个活动,每个活动安排的时间为[𝑎𝑖,𝑏𝑖)。求最多可以选择多少个活动,满足选择的活动时间两两之间没有重合。

输入描述:第一行输入一个整数𝑛,表示可选活动个数。
                  接下来的𝑛行,每行输入两个整数𝑎𝑖,𝑏𝑖,表示第𝑖个活动的时间。

输出描述:输出一行一个整数,表示最多可选择的活动数。

思路

先排序,再遍历判断同时安排的最多的活动数

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(vector<int>& a, vector<int>& b) 
{
    return a[1] < b[1];
}

int maxActivities(vector<vector<int> >& a) 
{
    if (a.empty())
        return 0;

    sort(a.begin(), a.end(), compare);

    int k = 1;
    int prevEnd = a[0][1];

    for (int i = 1; i < a.size(); i ++)
        if (a[i][0] >= prevEnd) 
        {
            k ++;
            prevEnd = a[i][1];
        }

    return k;
}

int main() 
{
    int n;
    cin >> n;

    vector<vector<int>> a(n, vector<int>(2));
    for (int i = 0; i < n; i ++)
        cin >> a[i][0] >> a[i][1];

    int ans = maxActivities(a);
    cout << ans << endl;

    return 0;
}

Q3   难度⭐⭐⭐⭐⭐

合唱团_牛客题霸_牛客网 (nowcoder.com)

题目
有 n 个学生站成一排,每个学生有一个能力值,牛牛想从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k 个学生的能力值的乘积最大,你能返回最大的乘积吗?

输入描述:每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50),表示学生的个数,接下来的一行,包含 n 个整数,按顺序表示每个学生的能力值 ai(-50 <= ai <= 50)。接下来的一行包含两个整数,k 和 d (1 <= k <= 10, 1 <= d <= 50)。

输出描述:输出一行表示最大的乘积。

思路

二维动态规划:
dp_max[i][j]表示选取前i个学生,最后一个学生的位置为j时的最大乘积;
dp_min[i][j]表示选取前i个学生,最后一个学生的位置为j时的最小乘积。

状态转移方程为:

dp_max[i][j] = max(dp_max[i][j], max(dp_max[i-1][j-l]*a[j], dp_min[i-1][j-l]*a[j]))

dp_min[i][j] = min(dp_min[i][j], min(dp_max[i-1][j-l]*a[j], dp_min[i-1][j-l]*a[j]))

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    int k, d;
    cin >> k >> d;
    
    vector<vector<long long>> dp_max(k, vector<long long>(n));
    vector<vector<long long>> dp_min(k, vector<long long>(n));
    
    for (int i = 0; i < n; i ++)
        dp_max[0][i] = dp_min[0][i] = a[i];
    
    long long ans = 0;
    
    for (int i = 1; i < k; i ++)
        for (int j = 0; j < n; j ++)
            for (int l = 1; l <= d; l ++)
                if (j - l >= 0) 
                {
                    dp_max[i][j] = max(dp_max[i][j], max(dp_max[i-1][j-l]*a[j], dp_min[i-1][j-l]*a[j]));
                    dp_min[i][j] = min(dp_min[i][j], min(dp_max[i-1][j-l]*a[j], dp_min[i-1][j-l]*a[j]));
                }

    for (int i = k - 1; i < n; i ++)
        ans = max(ans, dp_max[k-1][i]);
    
    cout << ans << endl;
    
    return 0;
}

day3

Q1   难度⭐⭐

跳台阶扩展问题__牛客网 (nowcoder.com)

题目
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

数据范围:1≤𝑛≤20

输入描述:本题输入仅一行,即一个整数 n 

输出描述:输出跳上 n 级台阶的跳法

思路

状态转移方程:dp[i] = dp[i] + dp[j]

#include <iostream>
using namespace std;

int dp[21] = {1, 1, 2};

int main()
{
    int n;
    cin >> n;

    for(int i = 3; i <= n; i ++)
        for(int j = 0; j < i; j ++)
            dp[i] = dp[i] + dp[j];

    cout << dp[n];
    return 0;
}

Q2   难度⭐⭐⭐

包含不超过两种字符的最长子串__牛客网 (nowcoder.com)

题目
给定一个长度为 n 的字符串,找出最多包含两种字符的最长子串 t ,返回这个最长的长度。

输入描述:仅一行,输入一个仅包含小写英文字母的字符串

输出描述:输出最长子串的长度

思路

unordered_map存,双指针遍历计算

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main()
{
    string s;
    cin >> s;

    int n = s.size();
    if(n <= 2)
    {
        cout << n << endl;
        return 0;
    }

    unordered_map<char, int> m;
    int l = 0, r = 0, len = 0;
    int cnt = 0;

    while(r < n)
    {
        if(m[s[r]] == 0)
            cnt ++;
        m[s[r ++]] ++;
        while(cnt > 2)
        {
            m[s[l]] --;
            if(m[s[l ++]] == 0)
                cnt --;
        }
        len = max(len, r - l);
    }
    
    cout << len << endl;
    return 0;
}

Q3   难度⭐⭐⭐⭐

字符串的排列_牛客题霸_牛客网 (nowcoder.com)

题目
输入一个长度为 n 字符串,打印出该字符串中字符的所有排列,你可以以任意顺序返回这个字符串数组。

例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

输入描述:输入一个字符串,长度不超过10,字符只包括大小写字母。

思路

DFS交换字母顺序的结果,记得用set去重

class Solution 
{
public:
    void dfs(string& s, int start, vector<string>& result) 
    {
        if (start == s.size()) 
        {
            result.push_back(s);
            return;
        }

        set<char> charSet;
        for (int i = start; i < s.size(); ++i) 
        {
            if (charSet.find(s[i]) != charSet.end()) 
                continue;
            charSet.insert(s[i]);

            swap(s[start], s[i]);
            dfs(s, start + 1, result);
            swap(s[start], s[i]);
        }
    }

    vector<string> Permutation(string str) 
    {
        vector<string> result;
        dfs(str, 0, result);
        return result;
    }
};

day4

Q1   难度⭐

[NOIP2008]ISBN号码 (nowcoder.com)

题目
每一本正式出版的图书都有一个ISBN号码与之对应,ISBN码包括9位数字、1位识别码和3位分隔符,其规定格式如“x-xxx-xxxxx-x”,其中符号“-”是分隔符(键盘上的减号),最后一位是识别码,例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言,例如0代表英语;第一个分隔符“-”之后的三位数字代表出版社,例如670代表维京出版社;第二个分隔之后的五位数字代表该书在出版社的编号;最后一位为识别码。
识别码的计算方法如下:
首位数字乘以1加上次位数字乘以2……以此类推,用所得的结果mod 11,所得的余数即为识别码,如果余数为10,则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的:对067082162这9个数字,从左至右,分别乘以1,2,…,9,再求和,即0×1+6×2+……+2×9=158,然后取158 mod 11的结果4作为识别码。
你的任务是编写程序判断输入的ISBN号码中识别码是否正确,如果正确,则仅输出“Right”;如果错误,则输出你认为是正确的ISBN号码。

输入描述:只有一行,是一个字符序列,表示一本书的ISBN号码(保证输入符合ISBN号码的格式要求)。

输出描述:共一行,假如输入的ISBN号码的识别码正确,那么输出“Right”,否则,按照规定的格式,输出正确的ISBN号码(包括分隔符“-”)。

思路

输入->求和->比对

#include <iostream>
using namespace std;

int main()
{
    char ISBN[14];
    int sum = 0, k = 1;
    cin >> ISBN;
    for(int i = 0; i < 12; i ++)
        if(ISBN[i] >= '0' && ISBN[i] <= '9')
        {
            sum += (ISBN[i] - '0') * k;
            k ++;
        }
    sum %= 11;
    char ans = '0';
    if(sum == 10)
        ans = 'X';
    else
        ans = sum + '0';
    if(ISBN[12] == ans)
        cout << "Right";
    else
    {
        ISBN[12] = ans;
        cout << ISBN << endl;
    }
    return 0;
}

Q2   难度⭐⭐⭐⭐⭐

kotori和迷宫 (nowcoder.com)

题目
kotori在一个n*m迷宫里,迷宫的最外层被岩浆淹没,无法涉足,迷宫内有k个出口。kotori只能上下左右四个方向移动。她想知道有多少出口是她能到达的,最近的出口离她有多远?

输入描述:第一行为两个整数n和m,代表迷宫的行和列数 (1≤n,m≤30)
                  后面紧跟着n行长度为m的字符串来描述迷宫。'k'代表kotori开始的位置,'.'代表道
                  路,'*'代表墙壁,'e'代表出口。保证输入合法。

输出描述:若有出口可以抵达,则输出2个整数,
                  第一个代表kotori可选择的出口的数量,
                  第二个代表kotori到最近的出口的步数。(注意,kotori到达出口一定会离开迷宫)
                  若没有出口可以抵达,则输出-1。

思路

BFS 遍历时更新最短距离

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int N = 110;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int n, m, sx, sy;
int dis[N][N];
char str[N][N];

void bfs() 
{
    queue<pair<int, int> > Q;
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    dis[sx][sy] = 0;
    Q.push(make_pair(sx, sy));
    while (! Q.empty()) {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        for (int i = 0; i < 4; i++)  
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (0 <= xx && xx < n && 0 <= yy && yy < m && str[xx][yy] != '*' && dis[xx][yy] > 1e8) 
            {
                dis[xx][yy] = dis[x][y] + 1;
				if (str[xx][yy] != 'e')
					Q.push(make_pair(xx, yy));
            }
        }
    }
    int a1 = 0, a2 = 0x3f3f3f3f;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (str[i][j] == 'e' && dis[i][j] < 1e8) 
            {
                a1++;
                a2 = min(a2, dis[i][j]);
            }
    if (a1 == 0) puts("-1");
    else printf("%d %d\n", a1, a2);
}

int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) 
    {
        scanf("%s", str[i]);
        for (int j = 0; j < m; j++)
            if (str[i][j] == 'k')
                sx = i, sy = j;
    }
    bfs();
    return 0;
}

Q3   难度⭐⭐⭐⭐

矩阵最长递增路径_牛客题霸_牛客网 (nowcoder.com)

题目
给定一个 n 行 m 列矩阵 matrix ,矩阵内所有数均为非负整数。 你需要在矩阵中找到一条最长路径,使这条路径上的元素是递增的。并输出这条最长路径的长度。

这个路径必须满足以下条件:
1. 对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外。
2. 你不能走重复的单元格。即每个格子最多只能走一次。

思路

DFS 遍历时更新最长路径

class Solution 
{
private:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    vector<vector<int>> memo;
    int n,m;
public:
    int dfs(vector<vector<int> >& matrix, int i, int j)
    {
        if(memo[i][j] != 0)
            return memo[i][j];
        int ans = 1;
        int num = matrix[i][j];
        for(int k = 0; k < 4; k ++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && y >= 0 && x < m && y < n && num < matrix[x][y])
                ans = max(ans, 1 + dfs(matrix, x, y));
        }
        memo[i][j] = ans;
        return ans;
    }
    int solve(vector<vector<int> >& matrix) 
    {
        m = matrix.size();
        n = matrix[0].size();
        memo.resize(m, vector<int>(n));
        int ans = 1;
        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                ans = max(ans, dfs(matrix, i, j));
        return ans;
    }
};

day5

Q1   难度⭐⭐⭐

奇数位丢弃_牛客题霸_牛客网 (nowcoder.com)

题目
对于一个由 0...n 的所有数按升序组成的序列,我们要进行一些筛选,每次我们丢弃去当前所有数字中第奇数位个的数。重复这一过程直到最后剩下一个数。请求出最后剩下的数字。

数据范围: 1≤𝑛≤1000,本题有多组输入

输入描述:每组数据一行一个数字,为题目中的n(n小于等于1000)。

输出描述:一行输出最后剩下的数字。

思路

数学公式

#include <iostream>
#include <cmath>
using namespace std;

int main() 
{
    int n;
	while(cin >> n)
	{
		int m = log(n + 1) / log(2);
		cout << ((1 << m) - 1) << endl;	
	}
	return 0;
}

Q2   难度⭐⭐⭐

求和_好未来笔试题_牛客网 (nowcoder.com)

题目
输入两个整数 n 和 m,从数列1,2,3.......n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来

输入描述:每个测试输入包含2个整数,n和m

输出描述:按每个组合的字典序排列输出,每行输出一种组合

思路

DFS

#include <iostream>
#include <vector>
using namespace std;

vector<int> a;
vector<vector<int>> ans;

void dfs(int n, int m, int start) 
{
    if (m == 0) 
    {
        ans.push_back(a);
        return;
    }

    for (int i = start; i <= n; ++i) 
    {
        if (i > m) break;

        a.push_back(i);
        dfs(n, m - i, i + 1);
        a.pop_back();
    }
}

int main() 
{
    int n, m;
    cin >> n >> m;

    dfs(n, m, 1);

    for (const auto& x : ans) 
    {
        for (int num : x)
            cout << num << " ";
        cout << endl;
    }

    return 0;
}

Q3   难度⭐⭐⭐⭐

计算字符串的编辑距离_牛客题霸_牛客网 (nowcoder.com)

题目
Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的,故又叫 Levenshtein Distance 。
例如:
字符串A: abcdefg
字符串B: abcdef
通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
要求:给定任意两个字符串,写出一个算法计算它们的编辑距离。

数据范围:给定的字符串长度满足 1≤𝑙𝑒𝑛(𝑠𝑡𝑟)≤1000

输入描述:每组用例一共2行,为输入的两个字符串

输出描述:每组用例输出一行,代表字符串的距离

思路

DP
状态转移方程为:dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int levenshteinDistance(const string &s1, const string &s2) 
{
    int m = s1.size();
    int n = s2.size();

    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

    for(int i = 0; i <= m; i ++) dp[i][0] = i;
    for(int j = 0; j <= n; j ++) dp[0][j] = j;

    for(int i = 1; i <= m; i ++) 
        for(int j = 1; j <= n; j ++) 
        {
            if(s1[i - 1] == s2[j - 1]) 
                dp[i][j] = dp[i - 1][j - 1];
            else 
                dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
        }

    return dp[m][n];
}

int main() 
{
    string s1, s2;
    cin >> s1 >> s2;
    
    int distance = levenshteinDistance(s1, s2);
    
    cout << distance << endl;
    return 0;
}

day6

Q1   难度⭐⭐

提取不重复的整数_牛客题霸_牛客网 (nowcoder.com)

题目
输入一个 int 型整数,按照从右向左的阅读顺序,返回一个不含重复数字的新的整数。
保证输入的整数最后一位不是 0 。

输入描述:输入一个int型整数
输出描述:按照从右向左的阅读顺序,返回一个不含重复数字的新的整数

思路

倒序遍历并用unorder_set存答案

#include<iostream>
#include <unordered_set>
using namespace std;

int main()
{
    string str;
    cin >> str;

    unordered_set<char> set;

    for(auto i = str.rbegin(); i != str.rend(); i ++)
    {
        if(set.count(*i))
            continue;
        set.insert(*i);
        cout<<*i;
    }
    
    return 0;
}

Q2   难度⭐⭐⭐

【模板】哈夫曼编码 (nowcoder.com)

题目
给出一个有n种字符组成的字符串,其中第i种字符出现的次数为ai​。请你对该字符串应用哈夫曼编码,使得该字符串的长度尽可能短,求编码后的字符串的最短长度。

输入描述:第一行输入一个整数n,表示字符种数。
                  第二行输入n个整数ai,表示每种字符的出现次数。

输出描述:输出一行一个整数,表示编码后字符串的最短长度。

思路

构造哈夫曼树并计算每次结合的两节点的和

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef long long LL;

int main()
{
    int n;
    cin >> n;
    priority_queue<LL, vector<LL>, greater<LL> > h;
    while(n --)
    {
        LL x;
        cin >> x;
        h.push(x);
    }
    
    LL ans = 0;
    while(h.size() > 1)
    {
        LL a = h.top(); h.pop();
        LL b = h.top(); h.pop();
        h.push(a + b);
        ans += a + b;
    }
    cout << ans << endl;
    return 0;
}

Q3   难度⭐⭐⭐⭐

abb_牛客题霸_牛客网 (nowcoder.com)

题目
leafee 最近爱上了 abb 型语句,比如“叠词词”、“恶心心”
leafee 拿到了一个只含有小写字母的字符串,她想知道有多少个 "abb" 型的子序列?
定义: abb 型字符串满足以下条件:

  1. 字符串长度为 3 。
  2. 字符串后两位相同。
  3. 字符串前两位不同。

输入描述:第一行一个正整数 𝑛

                  第二行一个长度为 𝑛 的字符串(只包含小写字母)

输出描述:"abb" 型的子序列个数。

思路

动态规划 + 哈希表

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n;
char s[N];
LL f[26];
LL g[26];

int main()
{
    cin >> n >> s;
    LL ans = 0;
    for(int i = 0; i < n; i ++)
    {
        int x = s[i] - 'a';
        ans += f[x];

        f[x] = f[x] + i - g[x];
        g[x] = g[x] + 1;
    }
    cout << ans << endl;
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/653370.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

表空间[MAIN]处于脱机状态

达梦数据库还原后&#xff0c;访问数据库报错&#xff1a;表空间[MAIN]处于脱机状态 解决方法&#xff1a; 1&#xff1a;检查备份文件 DMRMAN 中使用 CHECK 命令对备份集进行校验&#xff0c;校验备份集是否存在及合法。 ##语法&#xff1a;CHECK BACKUPSET <备份集目录…

育菁桌面式数控机床助力教育装备

桌面式数控机床是一种小型化的数控机床&#xff0c;它通常具有紧凑的设计和较小的体积&#xff0c;可以放置在桌面上进行操作。 这种车床结合了数控技术&#xff0c;通过计算机编程来控制机床的运动和加工过程&#xff0c;以实现高精度、高效率的工件加工。 桌面式数控车床是一…

Linux服务器配置ssh证书登录

1、ssh证书登录介绍 Linux服务器ssh登录有密码登录和证书登录两种。如果使用密码登录&#xff0c;容易遭受密码泄露或者暴力破解&#xff0c;我们可以使用ssh证书登录并禁止使用密码登录&#xff0c;ssh证书登录通过公钥和私钥来完成整个连接过程&#xff0c;公钥保存在服务器…

君正X2100 RTOS 修改UVC友好名称

修改UVC友好名称 SDK中默认的名称为"UVC Camera"。 相关文件f_uvc.c&#xff0c;具体内容&#xff1a; static struct usb_string uvc_en_us_strings[] {[UVC_STRING_CONTROL_IDX].s "UVC Camera",[UVC_STRING_STREAMING_IDX].s "Video Streamin…

埃文科技携数据要素产品亮相第七届数字中国建设峰会

第七届数字中国建设峰会&#xff08;以下简称“峰会”&#xff09;于2024年5月24日至25日在福建省福州市举办。此次峰会是国家数据工作体系优化调整后举办的首次数字中国建设峰会。本届峰会由国家发展改革委、国家数据局、国家网信办、科技部、国务院国资委、福建省人民政府共同…

fyne表单布局

fyne表单布局 layout.FormLayout就像一个 2 列网格布局 。 package mainimport ("image/color""fyne.io/fyne/v2/app""fyne.io/fyne/v2/canvas""fyne.io/fyne/v2/container""fyne.io/fyne/v2/layout" )func main() {myApp…

幼儿园老师投稿渠道

幼儿园老师投稿通常指的是教师为了分享自己的教学经验、教育活动设计、儿童发展研究等内容&#xff0c;向专业杂志、教育平台或在线论坛提交文章或资料的过程。以下是一些关于幼儿园老师投稿的步骤和建议&#xff1a; 一、准备工作 选择合适的平台 研究不同平台的读者群体&a…

javaee---IO代码练习

实现一个小程序要求: 扫描指定目录,并找到名称中包含指定字符的所有普通文件(不包含目录),并且要求询问用户是否要删除这个文件 代码示例 public static void main(String[] args) {//1.先让用户指定一个要扫描的目录Scanner scanner new Scanner(System.in);System.out.pri…

ubuntu安全加固

知识背景&#xff1a; 项目背景&#xff1a; 常用命令&#xff1a; useradd: adduser: getent passwd: getent group: id username: adduser newname sudo: 修改shell为/bin/bash 新用户默认为/bin/sh&#xff0c;可以通过echo $SHELL查询&#xff0c;默认不能使用TAB…

Linux系统之touch命令的基本使用

Linux系统之touch命令的基本使用 一、touch命令介绍1. touch命令简介2. touch命令作用 二、touch命令帮助1. touch命令的帮助信息2. touch命令的选项解释 三、touch命令的基本使用1. 查看touch工具版本2. 创建空文件3.查看空文件属性4. 修改文件时间戳5. 文件不存在时不创建 四…

剪画小程序:”霸屏各大平台“的黏土滤镜是怎么制作的呢?

最近&#xff0c;网上出现大量“黏土”风格的人物照片。尤其是在社交平台&#xff0c;这类型的分享数量急剧上升。 这是马斯克开车的样子 还有这张是周杰伦七里香的专辑图片 一张照片&#xff0c;十几秒钟&#xff0c;就能还原出你在黏土世界的样子。 以上这些照片是用-【剪画…

B站尚硅谷git学习记录

文章目录 一、Git概述1.何为版本控制2.为什么需要版本控制3.版本控制工具 二、Git常用命令1.设置用户签名1.1 基本语法1.2 案例实操 2.初始化本地库2.1 基本语法2.2 案例实操 3.查看本地库状态3.1基本语法3.2 案例实操&#xff08;1&#xff09;首次查看&#xff08;工作区没有…

共筑信创新生态:DolphinDB 与移动云 BC-Linux 完成兼容互认

近日&#xff0c;DolphinDB 数据库软件 V2.0 与中国移动通信集团公司的移动云天元操作系统 BC-Linux 完成兼容性适配认证。经过双方共同严格测试&#xff0c;DolphinDB 性能及稳定性等各项指标表现优异&#xff0c;满足功能及兼容性测试要求。 此次 DolphinDB 成功通过移动云 B…

Linux——Linux服务管理

服务管理大作业要求&#xff1a; 基本拓扑如下&#xff1a; 按照要求完成基本的系统管理任务&#xff1a; 完成所有系统的主机名、网络配置&#xff1b; 本次作业共需要3台虚拟机&#xff0c;分别作为客户端、综合应用服务器、存储服务器。三台虚拟机操作系统均为CentOS-Stream…

文件IO(一)

文件IO&#xff08;一&#xff09; 文件IO文件的分类在文件IO下&#xff0c;文件分类按存储的内容分按照操作分 标准IO和文件IO的区别系统调用和库函数的区别 文件IO 把程序暂存在内存的数据&#xff0c;存储到本地外存上 文件的分类 在Linux系统下&#xff0c;文件共分为7类…

基于 RNNs 对 IMDB 电影评论进行情感分类

前言 系列专栏:【深度学习&#xff1a;算法项目实战】✨︎ 涉及医疗健康、财经金融、商业零售、食品饮料、运动健身、交通运输、环境科学、社交媒体以及文本和图像处理等诸多领域&#xff0c;讨论了各种复杂的深度神经网络思想&#xff0c;如卷积神经网络、循环神经网络、生成对…

效果炸裂!使用 GPT-4o 快速实现LLM OS

使用 GPT-4o 快速实现LLM OS 什么是 LLM OS&#xff1f;LLM OS 主要有以下5个部分组成&#xff1a; LLM OS 开源实现运行 LLM OS 开源实现 什么是 LLM OS&#xff1f; 关于 LLM OS 的最初构想源自karpathy 在2023年11月11日发布的一条Twitter 动态&#xff0c;这是 LLM OS 概念…

git工作流程

以财务开发为例子&#xff1a; 1. 新建分支 1.1. upstream新建分支&#xff1a;finance-feature 1.2. origin新建对应分支&#xff1a;finance-feature 1.3 新建本地分支 git branch finance-feature 注&#xff1a; 同步远程分支&#xff1a;git fetch upstream feature…

YonBuilder移动开发基础教程——云修复

1 使用场景 在项目开发中&#xff0c;我们经常会遇到一种场景&#xff0c;对于一些已经上架应用市场对外发布的应用&#xff0c;我们需要修改其中部分页面的部分内容样式或功能逻辑&#xff0c;通常的做法是我们修改后&#xff0c;重新编译一个新的版本&#xff0c;然后提交应…

【NumPy】使用NumPy计算相关系数:详解numpy.corrcoef函数及应用

&#x1f9d1; 博主简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟&#xff0c;欢迎关注。提供嵌入式方向…