题目描述
请输出数字序列的最大间隔。
请使用以下伪随机数生成函数 rand32 () 生成伪随机数
int seed ;
int rand(){ return((( seed = seed * 214013L + 2531011L) >> 16) & 0x7fff); }
int rand32(){
return ((rand() << 16) + (rand() << 1) + rand() % 2);
}
Input Format
2个整数，n seed 其中 2<n<=20000000，seed为随机数种子。
Output Format
整数序列的最大间隔
Example
Input
2000000
1
Output
15737
样例
输入:
1959000 4910
输出:
16709
注意：O(nlogn)以上的时间复杂度至少会有一个案例超时。
#include<iostream>
#include<string.h>
using namespace std;
int n,seed;
int randI() {
return(((seed = seed * 214013L + 2531011L) >> 16) & 0x7fff);
}
int rand32() {
return ((randI() << 16) + (randI() << 1) + randI() % 2);
}
int maxGap(int arr[]) {
int minN = arr[0], maxN = arr[0];
//遍历找到数组中最大值最小值。
for (int i = 0; i < n; ++i)
{
if (arr[i] > maxN)maxN = arr[i];
if (arr[i] < minN)minN = arr[i];
}
if (maxN == minN)return 0;
//构造n+1个桶。
bool* hasNum = new bool[n + 1];
memset(hasNum, 0, sizeof(bool) * (n + 1));
int* mins = new int[n + 1];
int* maxs = new int[n + 1];
//遍历数组 找到每个桶中max min。
for (int i = 0; i < n; ++i)
{
//double gap = double(maxN - minN + 1) / (n + 1);
double gap = double(maxN - minN) / (n - 1);
int index = int((arr[i] - minN) / gap); //几号桶。
if (!hasNum[index])
{
mins[index] = maxs[index] = arr[i];
hasNum[index] = true;
}
else
{
mins[index] = min(arr[i], mins[index]);
maxs[index] = max(arr[i], maxs[index]);
}
}
int maxGap = 0;
int lastMax = maxs[0];
for (int i = 1; i <= n; i++)
{
if (hasNum[i]) //不是空桶。
{
maxGap = max(maxGap, (mins[i] - lastMax));
//cout << mins[i] << ' ' << lastMax << endl;
lastMax = maxs[i];
}
}
delete[]hasNum;
delete[]maxs;
delete[]mins;
return maxGap;
}
int main() {
cin >> n >> seed;
int* arr = new int[n];
for (int i = 0; i < n; ++i)
arr[i] = rand32();
cout << maxGap(arr) << endl;
delete[]arr;
return 0;
}
题目描述
给定一个非最简的Linux文件绝对路径，将其简化为标准的Linux文件绝对路径。
在Linux文件路径中，一个英文句号 . 表示当前目录，两个连续的英文句号 … 表示返回到上一级目录。
标准的Linux文件绝对路径具有以下特点
第一个字符为斜杠 /
两个目录名称直接有且仅有一个斜杠 /
除根目录外，路径结尾不能为斜杠 /
不会出现一个英文句号 . 或者两个连续的英文句号 …
Input Format
输入由一行字符串组成，为非最简的Linux文件绝对路径。
Output Format
输出一行，为最简化的Linux文件绝对路径。
Example
Input
/aaa/…/…/bbb/ccc/…///./…
Output
/
说明
路径从根目录开始从左往右进行解析
aaa 表示进入根目录下 aaa 目录
… 表示返回上一级目录，即返回根目录
… 表示返回上一级目录，但当前目录为根目录，无上一级目录。故仍处于根目录。
bbb 表示进入根目录下 bbb 目录
ccc 表示进入 bbb 目录下 ccc 目录
… 表示返回上一级目录，即返回 bbb 目录
后续若干个连续的斜杠 / 间没有目录名称，直接删除
. 表示当期文件夹，故仍处于 bbb 目录
… 表示返回上一级目录，即返回根目录
根目录用斜杠 / 表示，故输出斜杠 /
样例1
输入:
/aaa/…/…/bbb/ccc/…///./…
输出:
/
样例2
输入:
/home/
输出:
/home
#include <iostream>
#include <string>
#include <stack>
using namespace std;
string simplifyPath(string path)
{
stack<string> temp;
int i=0,j=0;
while(i<path.size()-1)
{
j=i+1;
//读取一个完整的目录名称。
while(path[j] != '/') ++j;
if(i+1 == j)
{
i=j;
continue;
}
string s=path.substr(i,j-i);
if("/." == s)
{
i=j;
continue;
}
if("/..." == s && !temp.empty()) temp.pop();
else if("/..." == s && temp.empty()) ;
else
temp.push(s);
i=j;
}
if(temp.empty()) return "/";
else
{
string res;
while(!temp.empty())
{
res=temp.top()+res;
temp.pop();
}
return res;
}
}
int main()
{
string s;
cin>>s;
cout<<simplifyPath(s);
}
题目描述
给定一个常数项为0的二元一次多项式，求该多项式的幂。
设未知数为x,y，输入为x和y的整数系数a,b以及整数幂n，输出形如以下样式
求幂运算的结果，按照x的幂降序排列
Input Format
输入未知数整数系数 a,b (-100<a,b<100),n (1<n<6)
Output Format
幂运算的结果的多项式，按照x幂降序排列
Example
Input
2 3 2
Output
4x^2+12xy+ 9y ^2
说明
幂为1时不输出^1
系数为1时不输出系数，-1只输出负号。
样例输入输出
样例1
输入:
2 3 2
输出:
4x^2+12xy+ 9y ^2
#include <iostream>
#include <queue>
using namespace std;
int main()
{
long long a,b;
long long t,w;
int x,y,n;
cin >> a >> b >> n;
x = n;
y = 0;
queue <long long> q;
q.push(0);
q.push(a);
q.push(b);
for (int i = 1 ; i < n ; i++)
{
q.push(0);
for (int j = 1 ; j <= i + 2 ; j++)
{
t = q.front();
q.pop();
w = q.front();
q.push(b * t + a * w);//计算系数，利用杨辉三角
}
}
q.pop();
while (!q.empty())
{
if(q.front() == 1){}
else if(q.front() == -1)
{
cout << "-";
}
else
{
cout << q.front();
}
if (x == 1)
{
cout << "x";
}
else if (x == 0){}
else
{
cout << "x^" <<x;
}
if (y == 1)
{
cout << "y";
}
else if (y == 0){}
else
{
cout << "y^" << y;
}
x--;
y++;
q.pop();
if (!q.empty() && q.front() > 0)
cout << "+";
}
}
题目描述
给定一个常数项为0的二元一次多项式，求该多项式的幂。
设未知数为x,y，输入为x和y的整数系数a,b以及整数幂n，输出形如以下样式
求幂运算的结果，按照x的幂降序排列
Input Format
输入未知数整数系数 a,b (-1000<a,b<1000),n (2<n<20)
Output Format
幂运算的结果的多项式，按照x幂降序排列
Example
Input
99 100 15
Output
860058354641288524893953951499x15+13031187191534674619605362901500x14y+92139707414891638724482363950000x13y2+403305116630838822699754455000000x12y3+1222136717063147947575013500000000x11y4+2715859371251439883500030000000000x10y5+4572153823655622699495000000000000x9y6+5937862108643665843500000000000000x8y7+5997840513781480650000000000000000x7y8+4712108147752005000000000000000000x6y9+2855823119849700000000000000000000x5y10+1311213553650000000000000000000000x4y11+441486045000000000000000000000000x3y12+102910500000000000000000000000000x2y13+14850000000000000000000000000000xy14+1000000000000000000000000000000y15
说明
幂为1时不输出^1
系数为1时不输出系数，-1只输出负号。
#include<iostream>
#include<queue>
#include<string>
#include<string.h>
using namespace std;
//将数字的非符号部分存入字符串
string getNum(const string& s) {
int t = s.size();
string str = "";
if (s[0] == '-')
{
for (int i = 1; i < t; i++)
str += s[i];
}
else
{
for (int i = 0; i < t; i++)
str += s[i];
}
return str;
}
//乘法，逐位计算，将结果存入数组再转为字符串
string multi(const string& a, const string& b)
{
int len1, len2;
int isNeg = 0;
if (((a[0] == '-' && b[0] != '-') || (a[0] != '-' && b[0] == '-')) && (a != "0" && b != "0")) isNeg = 1;
string num1 = getNum(a);
string num2 = getNum(b);
len1 = num1.size();
len2 = num2.size();
int* res = new int[len1 + len2];
memset(res, 0, sizeof(int) * (len1 + len2));
for (int i = len1 - 1; i >= 0; --i)
{
for (int j = len2 - 1; j >= 0; --j) {
res[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
}
}
for (int i = len1 + len2 - 1; i >= 0; --i)
{
if (res[i] >= 10) {
res[i - 1] += res[i] / 10;
res[i] %= 10;
}
}
string ans = "";
for (int i = 0; i < len1 + len2; ++i) ans += res[i] + '0';
if (isNeg) ans = '-' + ans;
return ans;
}
//加法
string plusNum(const string& num1, const string& num2)
{
int len1 = num1.size(), len2 = num2.size();
int len = max(len1, len2) + 1;
int length = len;
string ans = "";
int* res = new int[length];
memset(res, 0, sizeof(int) * length);
while (len1 > 0 && len2 > 0)
{
res[len - 1] = (num1[len1 - 1] - '0') + (num2[len2 - 1] - '0');
len1--;
len2--;
len--;
}
while (len1 > 0)
{
res[len - 1] = (num1[len1 - 1] - '0');
len1--;
len--;
}
while (len2 > 0)
{
res[len - 1] = (num2[len2 - 1] - '0');
len2--;
len--;
}
for (int i = length - 1; i >= 0; --i)
{
if (res[i] >= 10)
{
res[i - 1] += res[i] / 10;
res[i] %= 10;
}
}
int k;
for (k = 0; k < length; k++)
if (res[k] != 0)break;
if (k == length)ans = "0";
else
{
for (int i = k; i < length; i++)
ans += res[i] + '0';
}
return ans;
}
//减法
string minusNum(string& num1, string& num2)
{
int len1 = num1.size();
int len2 = num2.size();
int len;
if (len1 >= len2)
{
for (int i = 1; i <= len1 - len2; i++)
num2 = '0' + num2;
len = len1;
}
if (len2 > len1)
{
for (int i = 1; i <= len2 - len1; i++)
num1 = '0' + num1;
len = len2;
}
int* num_a = new int[len];
int* num_b = new int[len];
for (int i = 0; i < len; ++i)
{
num_a[i] = num1[i] - '0';
num_b[i] = num2[i] - '0';
}
int q = 0;//记录退位
for (int i = len - 1; i >= 0; --i)
{
num_a[i] -= q;
if (num_a[i] < num_b[i]) {
num_a[i] += 10;
q = 1;
}
num_b[i] = num_a[i] - num_b[i];
}
int k;
string ans = "";
for (k = 0; k < len; k++)
if (num_b[k] != 0)break;
if (k == len)ans = "0";
else
{
for (int i = k; i < len; i++)
ans += num_b[i] + '0';
}
return ans;
}
//判断两数相减结果是否为非负
bool isPos(const string&str1, const string str2)
{
if (str1.size() > str2.size())
return true;
if (str1.size() == str2.size())
return str1 > str2;
return false;
}
//计算系数
void powerFun(queue<string>& q, int n, const string& a, const string& b)
{
string t = "0";
string s;
string num1, num2;
string ans;
for (int i = 2; i <= n; i++)
{
q.push(to_string(0));
for (int j = 1; j <= i + 1; j++)
{
s = q.front();
q.pop();
num1 = multi(t, b);
num2 = multi(s, a);
if (num1[0] != '-' && num2[0] != '-')
ans = plusNum(num1, num2);
else if (num1[0] == '-' && num2[0] == '-')
{
ans = plusNum(getNum(num1), getNum(num2));
ans = '-' + ans;
}
if (num1[0] == '-' && num2[0] != '-')
{
num1 = getNum(num1);
if (isPos(num2, num1))
{
ans = minusNum(num2, num1);
}
else
{
ans = '-' + minusNum(num1, num2);
}
}
if (num1[0] != '-' && num2[0] == '-')
{
num2 = getNum(num2);
if (isPos(num1, num2))
{
ans = minusNum(num1, num2);
}
else
{
ans = '-' + minusNum(num2, num1);
}
}
q.push(ans);
t = s;
}
}
}
//表达式输出处理
void showRes(queue<string>& q, int n)
{
int k = n;
int flag = 1;
while (!q.empty())
{
if (q.front() == "0" )
{
q.pop();
k--;
flag = 0;
continue;
}
else if (q.front() == "1")
{
if (flag != 0 && k < n)cout << '+';
flag = 1;
}
else if (q.front()[0] != '-')
{
if (k < n)cout << '+';
cout << q.front();
}
else if (q.front() == "-1") cout << '-';
else if (q.front()[0] == '-') cout << q.front();
if (k == 1) cout << 'x';
else if (k != 0) cout << "x^" << k;
if (k == n - 1) cout << 'y';
else if (k != n) cout << "y^" << n - k;
q.pop();
k--;
}
cout << endl;
}
int main()
{
int a, b, n;
cin >> a >> b >> n;
queue<string>q;
string str1 = to_string(a);
string str2 = to_string(b);
q.push(str1);
q.push(str2);
powerFun(q, n, str1, str2);
showRes(q, n);
return 0;
}
题目描述
给出一棵二叉树的先序遍历和中序遍历序列，计算该二叉树的高度。其中，二叉树的先序和中序遍历序列为不包含重复英文字母（区别大小写）的字符串。
Input Format
二叉树结点的总个数n<=50
然后输入先序和中序遍历序列，两个序列长度均为n。
Output Format
二叉树高度（整数） ，叶子结点高度为1
Example
Input
9
ABDGHCEIF
GDHBAEICF
Output
4
#include<iostream>
using namespace std;
int GetHeight(char* pre,char* in,int n) //求二叉树的高度
{
if(n == 0) //若没有结点，为空树
{
return 0;
}
int i;
for(i = 0; i < n; i++)
{
if(in[i] == pre[0]) //找到根结点在中序的位置
{
break;
}
}
int left = GetHeight(pre + 1, in, i); //左子树的深度
int right = GetHeight(pre + i + 1, in + i + 1, n - i - 1); //右子树的深度
return max(left, right) + 1; //返回左右子树深度的较大值中的较大值+根结点
}
int main()
{
int n;
cin >> n;
char pre[n + 1], in[n + 1]; //先序和中序
cin >> pre >> in;
cout << GetHeight(pre, in, n) << endl;
return 0;
}
题目描述
在AVL树中，任何节点的两个子树的高度最多相差1；如果它们高度相差不止1，则需要重新平衡以恢复这种属性。
现在给定一个插入序列， 一个一个地将键值插入初始为空的AVL树中，输出得到的AVL树的层次顺序遍历序列，并判断它是否是一个完全二叉树。
输入格式：
第一行包含一个正整数N(<= 20)。然后在下一行给出N个不同的整数键。所有数字都用空格隔开。
输出格式：
第一行打印得到的AVL树的层次顺序遍历序列。所有数字都必须用空格隔开，并且行尾必须没有多余的空格。然后在下一行中，如果树为完全二叉树，则打印“Yes”;如果不是，则打印“No”。
样例1
输入：
5
88 70 61 63 65
输出：
70 63 88 61 65
Yes
样例2
输入：
10
62 88 58 47 35 73 51 99 37 93
输出：
62 47 88 35 58 73 99 37 51 93
No
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
typedef struct AVLNode
{
struct AVLNode *left,*right;
int val,height;
}*Node;
int getHeight(Node root)
{
if(root == NULL) return 0;
else return root->height;
}
Node rightrotate(Node root)
{
Node tmp = root->left;
root->left = tmp->right;
tmp->right = root;
root->height = max(getHeight(root->left),getHeight(root->right)) + 1;
tmp->height = max(getHeight(tmp->left),getHeight(tmp->right)) + 1;
return tmp;
}
Node leftrotate(Node root)
{
Node tmp = root->right;
root->right = tmp->left;
tmp->left = root;
root->height = max(getHeight(root->left),getHeight(root->right)) + 1;
tmp->height = max(getHeight(tmp->left),getHeight(tmp->right)) + 1;
return tmp;
}
Node rightleftrotate(Node root)
{
root->right = rightrotate(root->right);
return leftrotate(root);
}
Node leftrightrotate(Node root)
{
root->left = leftrotate(root->left);
return rightrotate(root);
}
Node insert(Node root,int key)
{
if(root == NULL)
{
root = new AVLNode();
root->val = key;
root->left = root->right = NULL;
root->height = 1;
return root;
}
else
{
if(key < root->val)
{
root->left = insert(root->left, key);
if(getHeight(root->left) - getHeight(root->right) == 2)
{
if(key < root->left->val) root = rightrotate(root);
else root = leftrightrotate(root);
}
}
else if(key > root->val)
{
root->right = insert(root->right, key);
if(getHeight(root->right) - getHeight(root->left) == 2)
{
if(key > root->right->val) root = leftrotate(root);
else root = rightleftrotate(root);
}
}
}
root->height = max(getHeight(root->left),getHeight(root->right)) + 1;
return root;
}
void level_order_traverse(Node root)
{
queue<Node>q;
vector<int>ans;
q.push(root);
bool flag = false,flag2 = false;
while(!q.empty())
{
Node p = q.front();
q.pop();
ans.push_back(p->val);
if(p->left != NULL)
{
q.push(p->left);
if(flag) flag2 = true;
}
else flag = true;
if(p->right != NULL)
{
q.push(p->right);
if(flag) flag2 = true;
}
else flag = true;
}
for(int i = 0; i < ans.size(); i++)
{
if(i == ans.size() - 1) cout << ans[i] << endl;
else cout << ans[i] << ' ';
}
if(!flag2) cout << "Yes" << endl;
else cout << "No" << endl;
}
int main()
{
int n;
cin >> n;
Node root = NULL;
for(int i = 1; i <= n; i++)
{
int x;
cin >> x;
root = insert(root, x);
}
level_order_traverse(root);
return 0;
}
题目描述
请判断输入的整数序列是否为堆。
如果为最大堆，请输出“max ”以及整理后的最小堆，整数序列数字之间有空格，最后无空格。
如果为最小堆，请输出“min ” 以及整理后的最大堆，整数序列数字之间有空格，最后无空格。
如果不为堆，请输出整理后的最大堆，整数序列数字之间有空格，最后无空格。
如果既是最大堆也是最小堆，请只输出“max min ”
Input Format
先输入整数序列个数n 0<n<1000
然后输入n个整数序列，整数取值范围【-100000，100000】
Output Format
最大堆或最小堆序列
Example
Input
10
-8 8 -9 10 -2 1 -6 -9 7 2
Output
10 8 1 7 2 -9 -6 -9 -8 -2
Input
10
10 8 1 7 2 -9 -6 -9 -8 -2
Output
max -9 -9 -6 -8 -2 1 10 7 8 2
Input
10
-9 -9 -6 -8 -2 1 10 7 8 2
Output
min 10 8 1 7 2 -9 -6 -9 -8 -2
Input
3
1 1 1
Output
max min
注意：序列最后无空格,max和min后面均有空格。
如案例，定义以下实现约束：两个相等子节点情况下，整理过程中，父节点下沉时，选择右沉。
10
10 8 1 7 2 -9 -6 -9 -8 -2
两个相等子节点情况下，整理过程中，父节点下沉时，选择右沉。
#include<iostream>
using namespace std;
int flag = 0;
void IsHeap(int num[], int n)
{
bool isMax = true, isMin = true;
int lChild, rChild;
for (int i = 1; i <= n; ++i)
{
lChild = i * 2;
rChild = i * 2 + 1;
if (rChild <= n)
{
if (num[i] == num[lChild] && num[i] == num[rChild])continue;//结点与孩子相等，可以是最大堆也可以是最小堆。
else if (num[i] <= num[lChild] && num[i] <= num[rChild])//结点的左右孩子都不比它小，故不是最大堆。
isMax = false;
else if (num[i] >= num[lChild] && num[i] >= num[rChild])//结点的左右孩子都不比它大，故不是最小堆。
isMin = false;
else
{
isMax = isMin = false;
break;
}
}
else if (lChild <= n)
{
if (num[i] == num[lChild])continue;
else if (num[i] < num[lChild])
isMax = false;
else if (num[i] > num[lChild])
isMin = false;
else
{
isMax = isMin = false;
break;
}
}
}
//四种结果
if (isMax == true)
{
if (isMin == false)flag = 1;
if (isMin == true)flag = 3;
}
else
{
if (isMin == true)flag = 2;
if (isMin == false)flag = 4;
}
}
void BuildMaxHeap(int num[], int n) //生成最大堆
{
for (int i = n / 2; i >= 1; --i)
{
int t = num[i];//结点
int c = i * 2;//左孩子
while (c <= n)
{
if (c < n && num[c] <= num[c + 1])
c++;
if (t < num[c]) //结点小于右孩子
{
num[c / 2] = num[c];//将右孩子的值赋给结点
c *= 2;//到下一层
}
else break;
}
num[c / 2] = t;//将原结点的值赋给右孩子
}
}
void BuildMinHeap(int num[], int n) //生成最小堆
{
for (int i = n / 2; i >= 1; --i)
{
int t = num[i];
int c = i * 2;
while (c <= n)
{
if (c < n && num[c] >= num[c + 1])
c++;
if (t > num[c])
{
num[c / 2] = num[c];
c *= 2;
}
else break;
}
num[c / 2] = t;
}
}
void BuildHeap(int num[], int n)
{
if (flag == 1)
{
cout << "max ";
BuildMinHeap(num, n);
}
if (flag == 2)
{
cout << "min ";
BuildMaxHeap(num, n);
}
if (flag == 3)
{
cout << "max min" << endl;
return;
}
if (flag == 4)
{
BuildMaxHeap(num, n);
}
for (int i = 1; i <= n; ++i)
{
if (i == n)cout << num[i];
else cout << num[i] << " ";
}
}
int main() {
int n, num1[1001];
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> num1[i];
IsHeap(num1, n);
BuildHeap(num1, n);
return 0;
}
样例
输入:
5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2
输出:
8
#include<iostream>
#include<algorithm>
using namespace std;
//用kruskal算法计算留下的边权重和，再用总权重减掉剩下的边的权重得到去除边的权重和。
struct Edge
{
int u, v, w;
bool operator <(struct Edge& edge) //因为要用sort()进行排序，重载运算符'<'。
{
return w < edge.w;
}
}e[10005];
int n, m, par[10005];
int unionfind(int x) //查找元素的根节点。
{
return x == par[x] ? x : par[x] = unionfind(par[x]);
}
int kruskal()
{
int cnt = 0, ans = 0;
sort(e, e + m);
for (int i = 0; i < m; ++i)
{
int fu = unionfind(e[i].u), fv = unionfind(e[i].v);
if (fu != fv) //根节点不同。
{
ans += e[i].w;
par[fu] = fv;
if (++cnt == n - 1)return ans;// 已有n-1条边。
}
}
}
int main()
{
int sum = 0;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> e[i].u >> e[i].v >> e[i].w;
sum += e[i].w;
}
for (int i = 1; i <= n; i++)
par[i] = i;
cout << sum - kruskal() << endl;
}
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int m, n;
while(cin >> m >> n)
{
vector<vector<int>> res(m, vector<int>(n));
/*定义了一个vector容器，元素类型为vector<int>，
初始化为包含m个vector<int>对象，
每个对象都是一个新创立的vector<int>对象的拷贝，
而这个新创立的vector<int>对象被初始化为包含n个0。*/
for(int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++) cin >> res[i][j];
}
int row = res.size();
int col = res[0].size();
int left = 0, right = col-1, top = 0, bottom = row-1;
vector<int> s;
while(left <= right && top <= bottom)
{
//顺时针。
for(int i = left; i <= right; i++) s.push_back(res[top][i]);
for(int i = top + 1; i <= bottom; i++) s.push_back(res[i][right]);
if(top != bottom)
{
for(int i = right - 1; i >= left; i--) s.push_back(res[bottom][i]);
}
if(left != right)
{
for(int i = bottom - 1;i >= top + 1 ; i--) s.push_back(res[i][left]);
}
left++, top++, right--, bottom--;
//逆时针。
if(left < right && top < bottom)
{
for(int i = top; i <= bottom ; i++) s.push_back(res[i][left]);
for(int i = left + 1; i <= right ; i++) s.push_back(res[right-1][i]);
if(left != right)
{
for(int i = bottom - 1; i >= top; i--) s.push_back(res[i][right]);
}
if(top != bottom)
{
for(int i = right - 1; i >= left + 1; i--) s.push_back(res[top][i]);
}
left++, top++, right--, bottom--;
}
}
for(int i = 0; i < s.size(); i++)
{
if (i == s.size() - 1)
cout << s[i] << endl;
else
cout << s[i] << ' ';
}
}
return 0;
}
Example
Input
4 4
1 2 3 4
12 13 16 5
11 14 15 6
10 9 8 7
Output
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Input
3 4
1 2 3 4
10 11 12 5
9 8 7 6
Output
1 2 3 4 5 6 7 8 9 10 11 12
题目描述
给出一棵完全二叉树的先序遍历，输出其后序遍历。结点均为不重复的单个英文字母，区分大小写。结点总数小于52。
Input Format
输入先序字符串
Output Format 后序遍历字符串
Example Input ABDGHCEIF
Output GHDCBIFEA
附件
样例1
输入:
ABDGHCEIF
输出:
GHDCBIFEA
样例2
输入:
a
输出:
a
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
class node
{
public:
node* lChild;
node* rChild;
char value;
node(char v = NULL, node* l = NULL, node* r = NULL)
{
value = v;
lChild = l;
rChild = r;
}
};
void postorder(node* Tree)
{
if (Tree == NULL)
{
return;
}
else
{
postorder(Tree->lChild);
postorder(Tree->rChild);
cout << Tree->value;
}
}
int main()
{
string s;
cin >> s;
node* Tree = new node[s.size() + 1];//Tree[0]没有用到，从1开始。
int n = 1;
int m = 1;
//求s为满二叉树时的元素个数m。
while ((int)s.size() > m)
{
double u = (double)n;
m += pow(2, u);
n++;
}
for (int q = 1; q <= s.size(); q++)
{
if (2 * q <= (int)s.size()) Tree[q].lChild = &Tree[2 * q];
if (2 * q + 1 <= (int)s.size()) Tree[q].rChild = &Tree[2 * q + 1];
}
Tree[1].value = s[0];
for (int i = 1, j = 1; i < (int)s.size();)
{
while (Tree[j].value != NULL && Tree[j].lChild != NULL && i < (int)s.size())
{
j = 2 * j;
Tree[j].value = s[i++];
}
if (Tree[j / 2].rChild != NULL && Tree[j / 2].rChild->value == NULL)
{
j = j + 1;
Tree[j].value = s[i++];
}
else if (Tree[j / 2].rChild != NULL && Tree[j / 2].rChild->value != NULL)
{
j = j / 2;
while (j > 1 && Tree[j / 2].rChild != NULL && Tree[j / 2].rChild->value != NULL) j = j / 2;
j = j + 1;
Tree[j].value = s[i++];
}
else if (Tree[j / 2].rChild == NULL)
{
j = j / 2 ;
while (j > 1 && Tree[j / 2].rChild != NULL && Tree[j / 2].rChild->value != NULL) j = j / 2;
j = j + 1;
Tree[j].value = s[i++];
}
}
postorder(&Tree[1]);
delete[]Tree;
return 0;
}
样例
输入:
8 10
1 6 10
1 5 5
6 3 1
6 5 2
3 4 4
4 1 7
4 3 6
5 6 3
5 3 9
5 4 2
1
输出:
No.1 : 1 -> 5 , d = 5
No.2 : 1 -> 5 -> 4 , d = 7
No.3 : 1 -> 5 -> 6 , d = 8
No.4 : 1 -> 5 -> 6 -> 3 , d = 9
No.5 : No Path to 2 7 8
#include<iostream>
#include<stack>
using namespace std;
struct edge
{
int bg, ed, val;
edge(int p = 0,int q = 0,int v = -1):bg(p), ed(q), val(v){}
};
struct Node
{
int flag;//标示结点是否已被访问。
Node(int f = 0):flag(f){}
};
//存储距离该结点最近的点以及路径长
struct path
{
int length, k;
path(int l = 101,int kk = 0):length(l),k(kk){}
path(const path& p)
{
length = p.length;
k = p.k;
}
};
//得到距离该点最近的点的路径长度
int minpath(int bg, int ed, edge* e, int m)
{
if(bg == ed)return 0;
int min = 101;
for(int i = 0;i < m; i++)
if(e[i].bg == bg && e[i].ed == ed && e[i].val < min)
min = e[i].val;
return min;
}
int main()
{
int n, m, t1, t2, t3, s;
cin >> n >> m;
edge* e = new edge[m];
Node* N = new Node[n];
int* pre = new int[n];//与当前结点相连的前一个点。
path* p = new path[n];
for(int i = 0; i < n; i++)
p[i].k = i;
for(int i = 0; i < n; i++)
pre[i] = -1;
for(int i = 0; i < m; i++)
{
cin >> t1 >> t2 >> t3;
e[i].bg = t1 - 1;
e[i].ed = t2 - 1;
e[i].val = t3;
}
cin >> s;
s -= 1;
pre[s] = s;
p[s].length = 0;
N[s].flag = 1;
int* key = new int[n];
for(int i = 0; i < n; i++)
{
p[i].length = minpath(s, i, e, m);
key[i] = p[i].length;//暂存各结点的最短路径。
}
int c1, c2;
c1 = s;//从源点开始搜寻。
for(int i = 0; i < n - 1; i++)
{
for(int j = 0; j < n; j++)
{
if(N[j].flag == 1)continue;//已访问，直接跳到下一个结点。
if(key[j] > (key[c1] + minpath(c1, j, e, m)))
{
key[j] = key[c1] + minpath(c1, j, e, m);
pre[j] = c1;
}
}
int min = 101, j = 0;;
for(;j < n; j++)
{
if(N[j].flag == 1)continue;
if(key[j] <= min)
{
min = key[j];
c2 = j;
}
}
N[c2].flag = 1;
if(i == 0)pre[c2] = c1;
p[c2].length = key[c2];
c1 = c2;
}
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(p[j].length < p[i].length)
{
path pp = p[j];
p[j] = p[i];
p[i]= pp;
}
int count = 1, flag = 0;
for(int i = 0; i < n; i++)
{
int num = p[i].k;
if(p[i].k == s)continue;
if(p[i].length == 101)
{
flag++;
continue;
}
stack<int> st;
st.push(num);
while(pre[num] != s)
{
st.push(pre[num]);
num = pre[num];
}
cout << "No." << count++ << " : " << s + 1 << " ";
while(!st.empty())
{
cout << "-> " << st.top() + 1 << " ";
st.pop();
}
cout << ", d = " << p[i].length << endl;
}
if(flag > 0)
{
cout << "No." << count << " : No Path to";
int *np = new int[flag];
int q = 0;
for(int i = 0; i < n; i++)
{
if(p[i].length == 101) np[q++] = p[i].k + 1;
}
for(int i = 0;i < flag; i++)
for(int j = i + 1; j < flag; j++)
if(np[j] < np[i])
{
int tmp = np[j];
np[j] = np[i];
np[i] = tmp;
}
for(int i = 0; i < flag; i++)cout << " " << np[i];
}
return 0;
}
题目描述
根据KMP算法的next数组值，推断模式字符串。
假设模式字符串中只存在0，1两种字符。给出首字符和next数组。请输出模式字符串。如果next数组不合法则输出ERROR
Input Format
先输入模式字符串首字符0或者1，然后输入尾字符0或者1
再输入 模式字符串长度n，n<=30
最后输入n个以 -1，0，起始的整数。
Output Format
模式字符串 或者 ERROR
Example
Input
1 0 10
-1 0 1 2 3 4 0 1 2 3
Output
1111101110
Input
1 1 6
-1 0 0 0 0 0
Output
100001
Input
1 1 6
-1 0 2 0 0 0
Output
ERROR
说明
以传统未优化的KMP算法推导的next数组。
#include <iostream>
using namespace std;
int kmp(int* next, int f, int l, int n)
{
int cur;
int* tmp = new int[n];
tmp[0] = f;
for (int i = 2; i < n; i++)
{
if (next[i] == 0)//最大匹配长度为0
{
if (f == 1) cur = 0;//当前字符的前一个字符与首字符相异
else cur = 1;
}
else
{
if (next[i] >= i || ( i != next[i] + 1 && tmp[i - next[i] - 1] == tmp[0])) //错误：最大匹配长度过长或字符不匹配时不能回溯到正确位置
{
cout << "ERROR" << endl;
return 0;
}
cur = tmp[next[i] - 1];
}
tmp[i - 1] = cur;
}
for (int i = 0; i < n - 1; i++)
{
cout << tmp[i];
}
cout << l;
cout << endl;
return 0;
}
int main()
{
int f, l, n;
cin >> f >> l >> n;
int* next = new int[n];
for (int i = 0; i < n; i++)
cin >> next[i];
kmp(next, f, l, n);
return 0;
}
样例1
输入:
1 1 6
-1 0 0 0 0 0
输出:
100001
样例2
输入:
1 1 6
-1 0 2 0 0 0
输出:
ERROR
样例3
输入:
1 1 7
-1 0 1 2 3 4 2
输出:
ERROR
题目描述
村庄中存在一些路，根据输入的相邻村庄的路，判断某两个村庄是否能够联通。n个村庄使用0到n-1的不同整数标识。路使用取值范围【0，n-1】的整数对表示。例如 3 5，代表村庄3和5之间有一条路。
Input Format
村庄个数 n， 0<n<=20
路的条数 m，0<m<=50
m条路，即为2m个范围在【0，n-1】的整数
需要判断是否相连的村庄对数 p 0<p<=10
需要判断是否相连的p对村庄，即为2p个范围在【0，n-1】的整数。
Output Format
能够连通输出
true
不可连通输出
false
#include<iostream>
using namespace std;
class unionfind
{
private:
int* parent;
int size;
public:
unionfind(int s)
{
size = s;
parent = new int[size];
for (int i = 0; i < size; i++)
{
parent[i] = i;
}
}
int find(int x)
{
while (parent[x] != x)
x = parent[x];
return x;
}
void combine(int v1, int v2)
{
int par1 = find(v1);
int par2 = find(v2);
if (par1 == par2)
return;
else
{
if (par1 > par2)
parent[par2] = par1;
else if (par1 < par2)
parent[par1] = par2;
return;
}
}
bool isconnect(int v1, int v2)
{
return (find(v1) == find(v2));
}
};
int main() {
int n, m, p;
int v1, v2;
int result;
cin >> n >> m;
unionfind u(n);
for (int i = 0; i < m; i++)
{
cin >> v1 >> v2;
u.combine(v1, v2);
}
cin >> p;
int* num = new int[2 * p];
for (int i = 0; i < 2*p;)
{
cin >> num[i] >> num[i+1];
i += 2;
}
for (int i = 0; i < 2 * p;)
{
result = u.isconnect(num[i], num[i + 1]);
if (result == 0)
cout << "false" << endl;
else
cout << "true" << endl;
i += 2;
}
return 0;
}
样例1
输入:
5
4
0 4
2 4
0 2
1 3
2
3 4
2 4
输出:
false
true
题目描述
给定一个仅含有英文大小写字母的字符串序列 s，若其中任意两个相邻字符都不是同一个字母的大小写形式，则称其为互斥字符串。
程序需要将给定的字符串转换为互斥字符串。aa为互斥，aA和Aa为非互斥。
程序的每次操作可以从字符串中选出满足上述条件的两个相邻字符并删除，直到字符串整理好为止。
注：若最终结果为空字符串，请输出 -1。
要求时间复杂度O(n)
Input Format
输入由一行字符串组成。测试样例保证答案唯一。
Output Format
输出一行，为输入字符串经过若干次删除操作得到的互斥字符串。
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
string s;
cin>>s;
stack<char>a;
stack<char>b;
a.push(s[0]);
int i=1;
while(s[i]!='\0')
{
if(a.empty())
{
a.push(s[i]);
}
else if ((a.top()==s[i]+32)||(a.top()==s[i]-32))
{
a.pop();
}
else
{
a.push(s[i]);
}
i++;
}
if (a.empty())
cout<<-1;
else
{ while(!a.empty())
{
b.push(a.top());
a.pop();
}
while(!b.empty())
{
cout<<b.top();
b.pop();
}
return 0;
}
}
Example
Input
abBAcCc
Output
c
说明
该样例存在多种转换路径，但最终输出相同
“abBAcCc” --> “aAcCc” --> “cCc” --> “c”
“abBAcCc” --> “abBAc” --> “aAc” --> “c”
样例1
输入:
abBAcCc
输出:
c
样例2
输入:
AaBbCcDd
输出:
-1
题目描述
给出一个工程中N个阶段的时间消耗和依赖关系，试求出工程的最短时间消耗。
Input Format
输入N 0<N<=20。
随后输入N行数据，每行包含从1起始的阶段编号S、时间消耗T、以及用分号隔开的所依赖的不同阶段编号【如果不依赖其他阶段则此项为空】
Output Format
输出一行，为完成N个阶段的时间消耗。如果依赖关系不为DAG则输出"error"
样例1
输入:
4
1 3
2 4
3 5 1;2;
4 3 3;
输出:
12
样例2
输入:
4
1 3 3;
2 4
3 5 1;2;
4 3 3;
输出:
error
#include<iostream>
#include<string>
#include<queue>
using namespace std;
int loop(int a[20][20],int N)//判断依赖关系是否成立
{
queue<int> q;
int* in = new int[N];
int* visit = new int[N];
for(int i = 0; i < N; i++)
{
in[i] = 0;
visit[i] = 0;
}
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
if(a[i][j] != -1)
in[j]++;
}
}
for(int i = 0; i < N; i++)
{
if(in[i] == 0)
{
q.push(i);
visit[i] = 1;
break;
}
}
while(!q.empty())
{
int t = q.front();
for(int i = 0; i < N; i++)
{
if(a[t][i] != -1) in[i]--;
}
for(int i = 0; i < N; i++)
{
if(in[i] == 0 && visit[i] == 0)
{
q.push(i);
visit[i] = 1;
}
}
q.pop();
}
for(int i = 0; i < N; i++)
{
if(visit[i] == 0)return -1;
}
return 0;
}
int maxpath(int s, int a[20][20], int N, int* e)
{
int* et = new int[N];
int* flag = new int[N];
for(int i = 0; i < N; i++)
{
et[i] = 0;
flag[i] = 0;
}
queue<int> q;
q.push(s);
while(!q.empty())
{
int t = q.front();
for(int i = 0; i < N; i++)
if(a[t][i] != -1)
{
q.push(i);
et[i] = (et[i] > et[t] + a[t][i]) ? et[i] : et[t] + a[t][i];
flag[t] = 1;//后面的时间已包括该阶段消耗时间;
}
q.pop();
}
for(int i = 0; i < N; i++)
et[i] += e[i];
int max = 0;
for(int i = 0; i < N; i++)
{
if(flag[i] == 0 && et[i] > max)
{
max = et[i];
}
}
return max;
}
int main()
{
int N;
string s;
cin >> N;
getchar();
int a[20][20];
int* e = new int[N];
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
a[i][j] = -1;
}
for(int i = 0; i < N; i++)
{
getline(cin, s);//istream& getline ( istream &is , string &str , char delim );默认的char delim为'\n';
int k = 2;
if(s[k] == ' ') k++;
if((k + 1 < s.length() && s[k + 1] == ' ') || k == s.length() - 1)
{
e[i] = s[k] - '0';//存入活动消耗的时间
k += 2;
}
else
{
e[i] = 10 * (s[k] - '0') + s[k + 1] - '0';
k += 3;
}
while(k + 1 < s.length())
{
if(s[k+1] == ';')
{
a[s[k] - '0' - 1][i] = s[k] - '0' - 1;
k += 2;
}
else
{
a[(s[k] - '0' - 1) * 10 + s[k + 1]- '0' - 1][i] = (s[k] - '0' -1 ) * 10 + s[k + 1] -'0' - 1;
k += 3;
}
}
}
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
if(a[i][j] != -1) a[i][j] = e[a[i][j]];
}
}
if(loop(a,N) == -1)
{
cout << "error" << endl;
return 0;
}
else
{
int max = 0;
for(int i = 0; i < N; i++)
{
int flag = 0;
for(int j = 0; j < N; j++)
{
if(a[j][i] != -1)
{
flag = 1;
break;
}
}
if(flag == 0)
{
int t = maxpath(i, a, N, e);
if(t > max)max = t;
}
}
cout << max << endl;
return 0;
}
}
题目描述
设计一个表达式求值的程序。该程序必须可以接受包含（，），+，-，*，/，%和^(求幂)的中缀表达式，并求出结果。如果表达式正确，则输出表达式的值，如果表达式非法，则输出错误信息。
注意223转为后缀应为223^^
操作数均转为double运算。
幂运算可以直接使用pow(a,b)
%,操作数转为Int再进行计算。
输入要求：
多个表达式，每个表达式占一行。
输出要求：
对每个表达式，如果为正确表达式则输出结果（精确到小数点后两位），如果为错误表达式则输出“ERROR IN INFIX NOTATION”
样例1
输入:
(2-4)^3
输出:
-8.00
样例2
输入:
(35(4+8)%2)
输出:
0.00
样例3
输入:
1+2(
输出:
ERROR IN INFIX NOTATION
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cmath>
#include <iomanip>
using namespace std;
char s[1000];
int g_pos; // 字符数组的下标
/* 字符转数字 */
double Translation(int & pos)
{
double integer = 0.00; // 整数部分
double remainder = 0.00; // 小数部分
while (s[pos] >= '0' && s[pos] <= '9')
{
integer *= 10;
integer += (s[pos] - '0');
pos++;
}
if (s[pos] == '.')
{
pos++;
int c = 1;
while (s[pos] >= '0' && s[pos] <= '9')
{
double t = s[pos] - '0';
t *= pow(0.1, c);
c++;
remainder += t;
pos++;
}
}
return integer + remainder;
}
/* 返回运算符级别 */
int GetLevel(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
case '%':
return 3;
case '(':
return 0;
case '#':
return -1;
};
}
/* 对两个数进行运算 */
double Operate(double a1, char op, double a2)
{
int a = a1;
int b = a2;
switch (op)
{
case '+':
return a1 + a2;
case '-':
return a1 - a2;
case '*':
return a1 * a2;
case '/':
return a1 / a2;
case '%':
return a % b;
case '^':
return pow(a1,a2);
};
}
/* 利用两个栈进行模拟计算 */
double Compute()
{
stack<char> optr; // 操作符栈
stack<double> opnd; // 操作数栈
optr.push('#'); //置于符栈顶
int len = strlen(s);
bool is_minus = true; // 判断是不是负号
for (g_pos = 0; g_pos < len;)
{
//1. 负号
if (s[g_pos] == '-' && is_minus) // 是负号
{
opnd.push(0);
optr.push('-');
g_pos++;
}
//2. 是右括号 )
else if (s[g_pos] == ')')
{
is_minus = false;
g_pos++;
while (optr.top() != '(' && optr.size() > 1)
{
double a2 = opnd.top();
opnd.pop();
double a1 = opnd.top();
opnd.pop();
char op = optr.top();
optr.pop();
double result = Operate(a1, op, a2);
opnd.push(result);
}
optr.pop(); // 删除'('
if (optr.size() < 1)
{
cout << "ERROR IN INFIX NOTATION" << endl;
return 0;
}
}
//3. 数字
else if (s[g_pos] >= '0' && s[g_pos] <= '9')
{
is_minus = false;
opnd.push(Translation(g_pos));
}
//4. ( 左括号
else if (s[g_pos] == '(')
{
is_minus = true;
optr.push(s[g_pos]);
g_pos++;
}
//5. + - * / ^ %
else if (s[g_pos] == '+' || s[g_pos] == '-' || s[g_pos] == '*' || s[g_pos] == '/' || s[g_pos] == '^' || s[g_pos] == '%' )
{
while (GetLevel(s[g_pos]) <= GetLevel(optr.top())) //当前优先级小于栈顶优先级
{
double a2 = opnd.top();
opnd.pop();
double a1 = opnd.top();
opnd.pop();
char op = optr.top();
optr.pop();
double result = Operate(a1, op, a2);
opnd.push(result);
}
optr.push(s[g_pos]);
g_pos++;
}
//6.输入字符不属于数字或规定运算符
else
{
cout << "ERROR IN INFIX NOTATION" << endl;
return 0;
}
}
//对剩余的运算符及操作数进行计算
while (optr.top() != '#' && opnd.size() >= 2)
{
double a2 = opnd.top();
opnd.pop();
double a1 = opnd.top();
opnd.pop();
char op = optr.top();
double result = Operate(a1, op, a2);
opnd.push(result);
optr.pop();
}
optr.pop();
//计算结束并弹出#后运算符栈仍不为空，说明最后弹出的不为#，有多余运算符
if (!optr.empty())
{
cout << "ERROR IN INFIX NOTATION" << endl;
return 0;
}
else if(opnd.size() != 1)
{
cout << "ERROR IN INFIX NOTATION" << endl;
return 0;
}
else
{
cout << setiosflags(ios::fixed) << setprecision(2) << opnd.top() << endl;
return 0;
}
}
int main()
{
cin >> s;
Compute();
return 0;
}
题目描述
自然界有一种物质，同种两个物质结合需要消耗的能量为两个物质的质量和。假设只能两两结合，根据输入的该类物质碎片质量，求全部碎片结合成一个整体，需要的最小能量。
Input Format
碎片总个数0<n<=50
n个碎片的质量【取值范围（0，10000）的n个整数】
Output Format
两两结合需要的最小能量
Example
Input
5
1 4 5 2 6
Output
39
样例1
输入:
5
1 4 5 2 6
输出:
39
样例2
输入:
2
7 8
输出:
15
样例1
输入:
3 5
0 1 6
0 2 13
1 0 10
1 2 4
2 0 5
输出:
0 6 10
9 0 4
5 11 0
样例2
输入:
6 0
输出:
0 -1 -1 -1 -1 -1
-1 0 -1 -1 -1 -1
-1 -1 0 -1 -1 -1
-1 -1 -1 0 -1 -1
-1 -1 -1 -1 0 -1
-1 -1 -1 -1 -1 0