//前序中序求后序
#include<iostream>
#include<string>
using namespace std;
void cc(int s,int e);
char a[26],b[26];
int main()
{
while(cin>>a>>b)
{
int len=strlen(a);
cc(0,len-1);
cout<<endl;
}
return 0;
}
void cc(int s,int e)
{
for(int i=0;i<26;i++)
for(int j=s;j<=e;j++)
if(a[i]==b[j])
{
cc(s,j-1);
cc(j+1,e);
cout<<a[i];
return;
}
}
//结构体typedef
#include<stdio.h>
typedef struct tree_node{
char value;
struct tree_node* left;
struct tree_node* right;
} node;
//素数
#include<iostream>
#include<cmath>
using namespace std;
int is_prime(int x)
{
if(x == 1)return 0;
int t = (int)sqrt(x);
for(int i=2; i<=t; i++)
if(x%i == 0)
return 0;
return 1;
}
//动态规划 矩阵链 2118
#include<iostream>
using namespace std;
int a[10][2];
long long f[10][10];
int kay[10][10];
int c(int i,int j)
{
if(i==j){kay[i][j]=i;return 0;}
int u=c(i,i)+c(i+1,j)+a[i][0]*a[i][1]*a[j][1];
kay[i][j]=i;
for(int k=i+1;k<j;k++)
{
int r=c(i,k)+c(k+1,j)+a[i][0]*a[k][1]*a[j][1];
if(r<u)
{
u=r;
kay[i][j]=k;
}
}
return u;
}
void traceback(int i,int j)
{
if(i==j)cout<<'A'<<i+1;
else
{
cout<<'('; //int p;cin>>p;
traceback(i,kay[i][j]);
cout<<" x ";
traceback(kay[i][j]+1,j);
cout<<')';
}
}
int main()
{
int n;int k=0;
while(cin>>n&&n!=0)
{
memset(kay,0,sizeof(kay));
memset(f,0,sizeof(f));
for(int i=0;i<n;i++)
cin>>a[i][0]>>a[i][1];
c(0,n-1);
cout<<"Case "<<++k<<": ";
traceback(0,n-1); //int p;cin>>p;
cout<<endl;
}
return 0;
}
//最长公共子串
#include<iostream>
using namespace std;
char s1[1000];
char s2[1000];
int dp[1000][1000];
int main()
{
while(cin>>s1>>s2)
{
int len1 = strlen(s1);
int len2 = strlen(s2);
for(int i=0;i<=len1;i++)
dp[i][0]=0;
for(int i=0;i<=len2;i++)
dp[0][i]=0;
for(int i=0;i<len1;i++)
for(int j=0;j<len2;j++)
{
if(s1[i]==s2[j])
dp[i+1][j+1]=dp[i][j]+1;
else
{
dp[i+1][j+1] = dp[i][j+1]>dp[i+1][j]?dp[i][j+1]:dp[i+1][j];
}
}
cout<<dp[len1][len2]<<endl;
}
return 0;
}
//The Tower of Babylon
#include<iostream>
using namespace std;
int a[90][3];
int dp[90];
int main()
{
int n,cnt=0;
while(cin>>n&&n)
{
int x;
for(int i=0;i<n;i++)
for(int j=0;j<3;j++)
{
cin>>x;
for(int k=0;k<3;k++)
a[i*3+k][(j+k)%3]=x;
}
for(int i=0;i<3*n;i++)
if(a[i][0]>a[i][1])
swap(a[i][0],a[i][1]);
for(int i=0;i<3*n;i++)
for(int j=i+1;j<3*n;j++)
if(a[i][1]>a[j][1])
for(int k=0;k<3;k++)
swap(a[i][k],a[j][k]);
dp[0]=a[0][2];
int maxmax=0;
for(int i=1;i<3*n;i++)
{
int max=0;
for(int j=0;j<i;j++)
if(a[j][0]<a[i][0]&&a[j][1]<a[i][1]&&max<dp[j])
max=dp[j];
dp[i]=max+a[i][2];
if(maxmax<dp[i])maxmax=dp[i];
}
cout<<"Case "<<++cnt<<": maximum height = "<<maxmax<<endl;
}
return 0;
}
//二进制数中1的个数
#include<iostream>
using namespace std;
int main()
{
int n;
while(cin>>n&&n)
{
int k = 0;
while(n)
{
n &= (n-1);
k++;
}
cout<<k<<endl;
}
}
//二分搜索
#include<iostream>
using namespace std;
int binarysearch(int t);
int n,a[100];//sorted
int main()
{
while(cin>>n&&n)
{
int t;
for(int i=0;i<n;i++)
cin>>a[i];
cin>>t;
cout<<binarysearch(t)<<endl;
}
}
int binarysearch(int t)
{
int l=0,u=n-1,m;
while(l<=u)
{
m=(l+u)/2;
if(a[m]<t)
l = m+1;
else if(a[m]==t)
return m;
else
u = m-1;
}
return -1;
}
//归并排序mergesort
#include<iostream>
using namespace std;
const int MAXN = 1000;
int a[MAXN], b[MAXN];
void merge(int left, int mid, int right)
{
int i=left, j=mid+1, k=left;
while(i<=mid && j<=right)
if(a[i] < a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
while(i<=mid)
b[k++] = a[i++];
while(j<=right)
b[k++] = a[j++];
for(i=left; i<=right; i++)
a[i] = b[i];
}
void mergeSort(int left, int right)
{
if(left<right)
{
int mid=(left+right)/2;
mergeSort(left, mid);
mergeSort(mid+1, right);
merge(left, mid, right);
}
}
int main()
{
int i, n;
cin >> n;
for(i=0; i<n; i++)
cin >> a[i];
mergeSort(0, n-1);
for(i=0; i<n; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
//快速排序
#include<iostream>
using namespace std;
int n,a[100];
void qsort1(int l, int u);
int main()
{
int n;
while(cin>>n&&n)
{
for(int i=0;i<n;i++)
cin>>a[i];
qsort1(0,n-1);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
}
return 1;
}
void qsort1(int l, int u)
{
if(l>=u)
return;
int m = l;
for(int i=l+1;i<=u;i++)
{
if(a[i]<a[l])
swap(a[++m],a[i]);
}
swap(a[l],a[m]);
qsort1(l,m-1);
qsort1(m+1,u);
}
//找出n个数中第k大的数，复杂度为：O(N*logK)
#include<iostream>
using namespace std;
int kmax(int l, int u, int k);
int n,a[100];
int main()
{
int k,n;
while(cin>>n&&n)
{
cin>>k;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<kmax(0,n-1,k)<<endl;
}
return 1;
}
int kmax(int l, int u, int k)
{
if(l==u)
return a[l];
int m = l;
for(int i=l+1;i<=u;i++)
{
if(a[i]<a[l])
{
swap(a[++m],a[i]);
}
swap(a[l],a[m]);
}
if(m-l<k)
return kmax(m+1,u,k-(m-l+1));
else if(m-l==k)
return a[m];
else return kmax(l,m-1,k);
}
//生成n以内随机序列
//注意保证：第i个数出现在自己的位置上
#include<iostream>
using namespace std;
int a[100];
int main()
{
int n;
while(cin>>n&&n)
{
a[1]=1;
for(int i=2;i<=n;i++)
{
a[i]=i;
swap(a[rand()%i+1],a[i]);
}
for(int i=1;i<=n;i++)
cout << a[i] << " ";
cout<<endl;
}
return 0;
}
//生成n以内m个有序列
#include<iostream>
using namespace std;
int a[100];
int main()
{
int n,m;
while(cin>>n>>m&&n)
{
for(int i=0;i<n;i++)
if((rand()%(n-i))<m)
{
cout<<i<<"";
m--;
}
cout<<endl;
}
return 0;
}
//堆排序
#include<iostream>
using namespace std;
int heap[100],len;
void insert(int value)
{
int parent,child;
heap[len] = value;
child = len++;
parent = (child-1)/2;
while(child != 0)
{
if(heap[parent]>value)
{
swap(heap[child],heap[parent]);
child = parent;
parent = (child-1)/2;
}
else
return;
}
}
int remove()
{
int root = heap[0];
heap[0] = heap[--len];
int parent = 0, child, left, right;
while(true)
{
left = parent * 2 + 1;
right = parent * 2 + 2;
if(left>=len) break;
if(right>=len) child = left;
else
child = heap[left]>heap[right]?right:left;
if(heap[parent]>heap[child])
{
swap(heap[parent], heap[child]);
parent = child;
}
else
break;
}
return root;
}
int main()
{
int k;
while(cin>>k&&k)
{
len=0;
for(int i=0;i<k;i++)
{
int a;
cin>>a;
insert(a);
}
for(int i=0;i<k;i++)
cout<<remove()<<" ";
}
}
/**//*最长重复子串
**共分3步
**1.得到后缀数组
**2.对后缀数组按字母顺序排序
**3.比较相邻两个，并且一定是从开头就开始比较，得到两个的最长公共长度。
**4.取所有比较结果的最大值。
*/
#include<iostream>
using namespace std;
char a[100],b[100][100];
int comlen(char *p, char *q)
{
int i=0;
while(*p&&(*p++==*q++))
i++;
return i;
}
//qsort要求的cmp参数格式
int cmp(const void *p, const void *q)
{
return strcmp((const char*)p, (const char*)q);
}
int main()
{
while(cin>>a)
{
int len = strlen(a);
for(int i=0;i<len;i++)
{
int j = i;
int k = 0;
while(a[j])
b[i][k++]=a[j++];
}
qsort(b,len,sizeof(b[0]),cmp);
int re = 0;
for(int i=0;i<len-1;i++)
{
int com = comlen(b[i], b[i+1]);
re = max(re, com);
}
cout<<re<<endl;
}
return 0;
}
posted on 2010-09-05 16:08
胖胖泡泡 阅读(420)
评论(0) 编辑 收藏