1.栈的压入与压出
/*
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。n<=100000 用一个栈作辅助，顺序描述压入序列和弹出序列，如果当前位置上压入序列和弹出序列值相等，直接都向后移一个元素；比较栈顶元素和弹出序列当前值，如果相等，出栈，弹出序列后移一个元素；其余情况，将压入序列当前值压栈，压入序列后移一个元素。如果到最后，弹出序列都处理不完，说明弹出序列不合法。时间复杂度为O(n)。
*/
#include <stdio.h>
#include <stack>
using namespace std; int qin[];
int qout[];
int main(void)
{
int n;
int i,j;
while(scanf("%d", &n) == )
{
for(i=; i<n; ++i)
scanf("%d", &qin[i]);
for(i=; i<n; ++i)
scanf("%d", &qout[i]); stack<int> s;
i = ;
j = ;
while(i<n || j<n)
{
if(i<n && j<n && qin[i]==qout[j])
{
++i;
++j;
}
else
{
if(s.empty())
{
if(i<n)
s.push(qin[i++]);
}
else if(s.top() == qout[j])
{
s.pop();
++j;
}
else if(i<n)
{
s.push(qin[i++]);
}
else
{
break;
}
}
} if(j==n)
printf("Yes\n");
else
printf("No\n");
} return ;
}
2.二叉搜索书的后续遍历序列
/*
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。n<=10000。 二叉搜索树的性质之一为：根结点值大于左子树，小于右子树。设后序遍历顺序为 A B C，则有A<C<B。因此，从根结点（遍历的最后一个结点）出发，向前找到所有连续的大于根结点的值作为右子树，再往前的所有连续小于根结点的作为左子树，如果往前还有大于根结点的，则不是二叉搜索树的后序遍历结果。递归处理左子树和右子树。时间复杂度约为O(nlogn)。
*/
#include <stdio.h> int seq[];
bool valid(int x, int y)
{
if(x >= y)
return true; int i=y-;
while(i>=x && seq[i]>seq[y])
{
--i;
}
int j = i;
while(i>=x && seq[i]<seq[y])
{
--i;
}
if(i>=x)
return false; if(!valid(x, j))
return false; if(!valid(j+, y-))
return false; return true;
} int main(void)
{
int n;
while(scanf("%d", &n) == )
{
for(int i=; i<n; ++i)
scanf("%d", &seq[i]); if(valid(, n-))
printf("Yes\n");
else
printf("No\n");
} return ;
}
3.数组中出现次数超过一半的数字
/*
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。n<=100000 将出现一半的数与其他数两两抵消，剩余的最后一个数即是答案。具体做法是每次选两个不同的数两两抵消，要么会抵消一个答案数字和一个非答案数字，要么抵消两个非答案数字，到最后剩余的一定是答案。时间复杂度为O(n)。
*/
#include <stdio.h> int f[];
int main(void)
{
int i,n;
while(scanf("%d", &n) == )
{
int ans = ;
int count = ;
for(i=; i<n; ++i)
{
scanf("%d", &f[i]);
if(count == )
{
ans = f[i];
count = ;
}
else if(f[i] == ans)
{
++count;
}
else
{
--count;
}
} count = ;
for(i=; i<n; ++i)
{
if(f[i] == ans)
++count;
} if(count > n/)
printf("%d\n", ans);
else
printf("-1\n");
} return ;
}
4.整数中1出现的次数
/*
求两个整数间的数，10进制各个位上1出现的总次数，0<=a,b<=1,000,000,000 按位统计，统计每位上1出现的次数。当前位刚好是1和刚好是0需要单独考虑。
*/
#include <stdio.h> long long CountOne(long long x)
{
long long base = ;
long long ans = ;
long long temp;
long long rec = ;
while(x)
{
temp = x/;
ans += temp * base;
if(x% > )
ans += base;
else if(x% == )
{
ans += rec + ;
}
rec += x% * base;
base *= ;
x /= ;
}
return ans;
} int main(void)
{
long long a,b;
while(scanf("%lld%lld", &a, &b) == )
{
long long sa = , sb = ;
if(a>b)
{
a += b;
b = a - b;
a = a - b;
}
if(a>)
sa = CountOne(a-);
sb = CountOne(b);
printf("%lld\n", sb-sa);
}
return ;
}
5.数组中的逆袭对
/*
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 归并排序，在merge的时候统计逆序对，设需要merge的数组为A，B，A大小为n，B大小为m。如果A[i]>B[j]，则逆序数将增加n-i。
*/
#include <stdio.h> int f[];
int g[];
long long ans;
void Sort(int x, int y)
{
if(x >= y)
return ; int mid = (x+y)>>;
Sort(x, mid);
Sort(mid+, y); int i = x;
int j = mid+;
int k = x;
while(i<=mid || j<=y)
{
if(i>mid)
{
g[k++] = f[j++];
}
else if(j>y)
{
g[k++] = f[i++];
}
else if(f[i]<=f[j])
{
g[k++] = f[i++];
}
else if(f[i]>f[j])
{
ans += mid - i + ;
g[k++] = f[j++];
}
}
for(k=x; k<=y; ++k)
f[k] = g[k];
} int main(void)
{
int n;
while(scanf("%d", &n) == )
{
for(int i=; i<n; ++i)
scanf("%d", &f[i]); ans = ;
Sort(, n-);
printf("%lld\n", ans);
} return ;
}
6.和为s的两个数字
/*
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S。n<=1000000 用两个游标，一个从头开始A[i]，一个从尾开始A[j]，如果A[i]+A[j]<S，则i后移一格，否则j前移一格，如果相等，则记录结果。算法复杂度为O(n)。
*/
#include <stdio.h> long long num[];
int main(void)
{
int n;
long long m;
while(scanf("%d%lld", &n, &m) == )
{
int i,j;
for(i=; i<n; ++i)
scanf("%lld", &num[i]); i = ;
j = n-;
long long x=-, y=-;
long long v;
long long res = num[j]*num[j];
while(i<j)
{
v = num[i] + num[j];
if(v == m)
{
if(num[i]*num[j] <= res)
{
x = num[i];
y = num[j];
res = num[i]*num[j];
}
++i;
--j;
}
else if(v < m)
{
++i;
}
else
{
--j;
}
}
printf("%lld %lld\n", x, y);
} return ;
}
7.猜数字游戏
/*
给定n个骰子，每个骰子点数为m，求按概率排序前3的点数和。 概率值按 4 舍 5 入要求保留 2 位小数， n(0<=n<=10),m(6<=m<=8)。 递推，令f[i][j]表示前i个骰子，点数和为j的次数。有f[i][j] = f[i-1][j-1]+....+f[i-1][j-m]。也可直接用一维的轮换数组进行计算，即g[j] = f[j-1]+...+f[j-m], f=g。
*/
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std; struct T
{
int id;
double v;
}; bool cmp(const T &a, const T &b)
{
if(a.v>b.v)
return true;
else if(a.v<b.v)
return false;
else
return a.id<b.id;
} int main(void)
{
int n,m;
bool first = true;
while(scanf("%d", &n)== && n)
{
scanf("%d", &m);
int f[] = {};
int g[] = {};
int i,j,k;
for(i=; i<=m; ++i)
f[i] = ; for(i=; i<n; ++i)
{
for(j=; j<=; ++j)
g[j] = ; for(j=; j<=; ++j)
{
for(k=; k<=m; ++k)
{
if(j-k>)
{
g[j] += f[j-k];
}
}
} for(j=; j<=; ++j)
f[j] = g[j];
} int sum = ;
vector<T> ans;
T t;
for(i=; i<=; ++i)
{
if(f[i] > )
{
sum += f[i];
t.id = i;
t.v = f[i];
ans.push_back(t);
}
}
for(i=; i<ans.size(); ++i)
{
ans[i].v = ((int)(100.0*ans[i].v/sum+0.5))/100.0;
}
sort(ans.begin(), ans.end(), cmp); if(first)
first = false;
else
printf("\n"); for(i=; i<; i++)
{
printf("%d %.2lf\n", ans[i].id, ans[i].v);
}
} return ;
}