目录
1.哈夫曼编码
【问题描述】读入n个字符所对应的权值，自底向上构造一棵哈夫曼树，自顶向下生成每一个字符对应的哈夫曼编码，并依次输出。另，求解某字符串的哈夫曼编码，求解某01序列的译码。
【输入形式】输入的第一行包含一个正整数n，表示共有n个字符需要编码。其中n不超过100。第二行中有n个用空格隔开的正整数，分别表示n个字符的权值，依次按照abcd...的默认顺序给出。然后是某字符串和某01序列。
【输出形式】前n行，每行一个字符串，表示对应字符的哈夫曼编码。然后是某字符串的哈夫曼编码，某01序列的译码。
【注意】保证每次左子树比右子树的权值小；如出现相同权值的，则先出现的在左子树，即下标小的在左子树。
【样例输入】
8
5 29 7 8 14 23 3 11aabchg
00011110111111001
【样例输出】
0001
10
1110
1111
110
01
0000
001000100011011100010000
acdef
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define x first
#define y second
#define mp make_pair
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
const int N = 1e3 + 10;
struct node
{
int w, parent, lc, rc;
}ht[N];
int a[N], n, s1, s2;
void choose(int pos) {
int max1 = INF, max2 = INF;
for(int i = 1; i <= pos; i++) {
if(ht[i].w < max1 && ht[i].parent == 0) {
max2 = max1;
s2 = s1;
max1 = ht[i].w;
s1 = i;
}
else if(ht[i].w < max2 && ht[i].parent == 0) {
max2 = ht[i].w;
s2 = i;
}
}
}
void creat() {
for(int i = 1; i <= n; i++) ht[i] = {a[i], 0, 0, 0};
int m = 2 * n - 1;
for(int i = n + 1; i <= m; i++) ht[i] = {0, 0, 0, 0};
for(int i = n + 1; i <= m; i++) {
choose(i - 1);
ht[i].w = ht[s1].w + ht[s2].w;
ht[s1].parent = i; ht[s2].parent = i;
ht[i].lc = s2; ht[i].rc = s1;
}
}
vector<char> cd[N];
void HuffmanCode() {
for(int i = 1; i <= n; i++) {
// cout << ht[i].parent << endl;
for(int c = i, p = ht[i].parent; p != 0; c = p, p = ht[p].parent) {
if(ht[p].lc == c) {
cd[i].push_back('1');
}
else {
cd[i].push_back('0');
}
}
reverse(cd[i].begin(), cd[i].end());
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
creat();
HuffmanCode();
for(int i = 1; i <= n; i++) {
// cout << cd[i].size() << endl;
for(int j = 0; j < cd[i].size(); j++) {
cout << cd[i][j];
}
cout << endl;
}
char ch[N];
cin >> ch;
for(int i = 0; i < strlen(ch); i++) {
int tmp = ch[i] - 'a' + 1;
for(int j = 0; j < cd[tmp].size(); j++) {
cout << cd[tmp][j];
}
}
cout << endl;
char ch1[N];
cin >> ch1;
for(int i = 0; i < strlen(ch1); i++) {
for(int j = 1; j <= n; j++) {
int tmp = i;
int k = 0;
while(tmp < strlen(ch1) && k < cd[j].size() && ch1[tmp] == cd[j][k]) {
tmp ++;
k++;
}
if(k == cd[j].size()) {
i = tmp - 1;
// cout << i << " ";
char ans = j + 'a' - 1;
cout << ans;
break;
}
}
}
}2.?带权路径长度?
?
【问题描述】 输入一串正整数，正整数之间用空格键分开，请建立一棵哈夫曼树，以输入的数字作为叶子节点，求这棵哈夫曼树的带权路径长度。
【输入形式】 首先输入正整数的个数n，然后是对应的n个正整数，正整数个数不超过10个
【输出形式】 输出创建的哈夫曼树的带权路径总长度
【样例输入】?
5
4 5 6 7 8
【样例输出】?
69
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define x first
#define y second
#define mp make_pair
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
const int N = 1e3 + 10;
struct node
{
int w, parent, lc, rc;
}ht[N];
int a[N], n, s1, s2;
void choose(int pos) {
int max1 = INF, max2 = INF;
for(int i = 1; i <= pos; i++) {
if(ht[i].w < max1 && ht[i].parent == 0) {
max2 = max1;
s2 = s1;
max1 = ht[i].w;
s1 = i;
}
else if(ht[i].w < max2 && ht[i].parent == 0) {
max2 = ht[i].w;
s2 = i;
}
}
}
void creat() {
for(int i = 1; i <= n; i++) ht[i] = {a[i], 0, 0, 0};
int m = 2 * n - 1;
for(int i = n + 1; i <= m; i++) ht[i] = {0, 0, 0, 0};
for(int i = n + 1; i <= m; i++) {
choose(i - 1);
ht[i].w = ht[s1].w + ht[s2].w;
ht[s1].parent = i; ht[s2].parent = i;
ht[i].lc = s2; ht[i].rc = s1;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
creat();
int ans = 0;
for(int i = 1; i <= 2 * n - 2; i++) {
// cout << ht[i].w << " " << ht[i].lc << " " << ht[i].rc << endl;
ans += ht[i].w;
}
cout << ans << endl;
}
?3.图的遍历及连通性
?【问题描述】
?根据输入的图的邻接矩阵A，判断此图的连通分量的个数。请使用邻接矩阵的存储结构创建图的存储，并采用BFS优先遍历算法实现，否则不得分。
【输入形式】
?第一行为图的结点个数n，之后的n行为邻接矩阵的内容，每行n个数表示。其中A[i][j]=1表示两个结点邻接，而A[i][j]=0表示两个结点无邻接关系。
【输出形式】
?输出此图连通分量的个数。
【样例输入】
?5
?0 1 1 0 0
?1 0 1 0 0
?1 1 0 0 0
?0 0 0 0 1
?0 0 0 1 0
【样例输出】
?2
【样例说明】
?邻接矩阵中对角线上的元素都用0表示。(单个独立结点，即与其它结点都没有边连接，也算一个连通分量)
#include<iostream>
using namespace std;
const int N = 1e3 + 10;
//template<typename T>
//struct pair{
// T x;
// T y;
//};
template<typename T>
struct queue{
int head;
int tail;
T data[N];
void push(T x){
data[tail++] = x;
}
T front(){
return data[head];
}
void pop() {
head++;
}
bool empty() {
return tail == head;
}
queue() {
head = 0;
tail = 0;
}
};
int n;
bool mp[N][N];
int cnt = 0;
int color[N];
void bfs(int pos) {
cnt++;
queue<int> q;
q.push(pos);
color[pos] = cnt;
while(!q.empty()) {
int tmp = q.front();
// cout << tmp << endl;
q.pop();
for(int i =1; i <= n; i++) {
if( mp[tmp][i] && !color[i] ) {
color[i] = cnt;
q.push(i);
}
}
}
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> mp[i][j];
}
}
for(int i = 1; i <= n; i++) {
if(!color[i]) {
bfs(i);
}
}
cout << cnt << endl;
}
?4.犯罪团伙
【题目描述】
此题必须采用邻接表的存储结构，建立图的存储，然后采用DFS遍历实现求解。否则不给分。
警察抓到了 n 个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从 1 至 n。
【输入】
第一行：n（<=1000,罪犯数量），第二行：m（<5000，关系数量）以下若干行：每行两个数：I 和 j，中间一个空格隔开，表示罪犯 i 和罪犯 j 相互认识。
【输出】
一个整数，犯罪团伙的数量。
【样例输入】
11
8
1 2
4 3
5 4
1 3
5 6
7 10
5 10
8 9
【输出】
3
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define x first
#define y second
#define mp make_pair
#define INF 0x3f3f3f3
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
const int N = 5e3 + 10;
int n, m, cnt, vis[N], tot, head[N], Next[N], ver[N];
void add(int x, int y) {
ver[++tot] = y;
Next[tot] = head[x], head[x] = tot;
}
void dfs(int pos) {
// cout << pos << endl;
for(int j = head[pos]; j ; j = Next[j]) {
if(!vis[ver[j]]) {
vis[ver[j]] = 1;
dfs(ver[j]);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif
cin >> n >> m;
for(int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
add(x, y);
add(y, x);
}
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
vis[i] = 1;
dfs(i);
cnt++;
}
}
cout << cnt;
}?5.?图形窗口问题
【问题描述】
在某图形操作系统中，有N个窗口，每个窗口都是一个两边与坐标轴分别平行的矩形区域。窗口的边界上的点也属于该窗口。窗口之间有层次的区别，在多于一个窗口重叠的区域里，只会显示位于顶层的窗口里的内容。
当你点击屏幕上一个点的时候，你就选择了处于被点击位置的最顶层窗口，并且这个窗口就会被移到所有窗口的最顶层，而剩余的窗口的层次顺序不变。如果你点击的位置不属于任何窗口，则系统会忽略你这次点击。
现在我们希望你写一个程序模拟点击窗口的过程。
【输入形式】
输入的第一行有两个正整数，即N和M。（1<=N<=10，1<=M<=10）接下来N行按照从最下层到最顶层的顺序给出N个窗口的位置。每行包含四个非负整数x1,y1,x2,y2，表示该窗口的一对顶点坐标分别为(x1,y1)和(x2,y2)。保证x1<x2，y1<y2。
接下来M行每行包含两个非负整数x,y，表示一次鼠标点击的坐标。题目中涉及到的所有点和矩形的顶点的x,y坐标分别不超过2559和1439。
【输出形式】
输出包括M行，每一行表示一次鼠标点击的结果。如果该次鼠标点击选择了一个窗口，则输出这个窗口的编号（窗口按照输入中的顺序从1编号到N）；如果没有，则输出"IGNORED"（不含双引号）。
【样例输入】
3?4
0?0?4?4
1?1?5?5
2?2?6?6?
1?1
0?0
4?4
0?5
【样例输出】
2
1
1
IGNORED
【样例说明】
第一次点击的位置同时属于第1和第2个窗口，但是由于第2个窗口在上面，它被选择并且被置于顶层。
第二次点击的位置只属于第1个窗口，因此该次点击选择了此窗口并将其置于顶层。现在的三个窗口的层次关系与初始状态恰好相反了。第三次点击的位置同时属于三个窗口的范围，但是由于现在第1个窗口处于顶层，它被选择。
最后点击的(0,5)不属于任何窗口。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define ull unsigned long long
#define x first
#define y second
#define mp make_pair
#define INF 0x3f3f3f3
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
struct node
{
int x1, y1, x2, y2, id;
};
int n, m;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif
cin >> n >> m;
vector<node> v;
v.push_back({0, 0, 0, 0, 0});
for(int i = 1, x1, y1, x2, y2; i <= n; i++) {
cin >> x1 >> y1 >> x2 >> y2;
v.push_back({x1, y1, x2, y2, i});
}
for(int i = 1; i <= m; i++) {
int x, y, ans = 0;
bool flag = 1;
cin >> x >> y;
for(int j = n; j >= 1; j--) {
if(x >= v[j].x1 && x <= v[j].x2 && y >= v[j].y1 && y <= v[j].y2) {
cout << v[j].id << endl;
node tmp = v[j];
v.erase(v.begin() + j);
v.push_back(tmp);
flag = 0;
break;
}
}
if(flag) cout << "IGNORED\n";
}
}?
