笔试——Day36

第一题

题目

提取不重复的整数

思路

模拟

使用哈希表统计当前数字出现的次数，当次数为1时，加入结果；

代码

#include <iostream>
#include <string>
using namespace std;string str;int main() 
{cin >> str;string res;int n = str.size();int hash[10] = {0};for(int i = n - 1; i >= 0; i--){hash[str[i] - '0']++;if(hash[str[i] - '0'] == 1) res += str[i];}cout << res << endl;return 0;
}
// 64 位输出请用 printf("%lld")

第二题

题目：

哈夫曼编码

思路

代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using LL = long long;
int main() 
{int n; cin >> n;priority_queue<LL, vector<LL>, greater<LL>> pq;for(int i = 0; i < n; i++){LL x; cin >> x;pq.push(x);}LL res = 0;while(pq.size() > 1){LL a = pq.top(); pq.pop();LL b = pq.top(); pq.pop();res += (a + b);pq.push(a + b);}cout << res << endl;return 0;
}
// 64 位输出请用 printf("%lld")

第三题

题目：

abb

思路

动态规划

• 状态表示：dp[i]表示以i为结尾的所有子序列，有多少个abb形式的序列

• 状态转移方程：

  • dp[i]：表示以第i个字符为结尾的所有abb形式子序列的数量
  • f[x]：表示截止到当前位置，以字符x结尾的 ab形式子序列的数量（即第一个字符与第二个字符x不同）
  • g[x]：表示截止到当前位置，字符x出现的总次数

• 返回值：整张dp表的和

代码

#include <iostream>
#include <string>
using namespace std;const int N = 1e5 + 10;int f[26];  // f[x]表示以字符x结尾的"ab"形式子序列数量
int g[26];  // g[x]表示字符x出现的总次数
int dp[N];  // dp[i]表示以i为结尾的"abb"形式子序列数量int main() 
{int n = 0; cin >> n;string s; cin >> s;long long res = 0;  // 存储最终结果，使用long long避免溢出for(int i = 0; i < n; i++){int x = s[i] - 'a';  // 将字符转换为0-25的索引// 累加当前字符作为最后一个b时能形成的abb子序列数量res += f[x];// 更新以当前字符为结尾的ab子序列数量f[x] = f[x] + i - g[x];// 更新当前字符的出现次数g[x] = g[x] + 1;}cout << res << endl;return 0;
}