这一题题目有些长，不过这不影响它是一道水题。
题意描述：
题中描述了两种情况，当输入数据以'P'开头时，表示输入的是1~N的一个排列，要求输出每个数前面比该数大的数字的个数，输出结果时顺序为数字1的在前，数字N的在最后。第二种情况正好相反，给出每个数字前面比该数大的数字的个数，要求输出原序列。
第一种情况好说，主要是第二种情况。情况二的解法是按从后往前顺序确定原序列，即先确定数字N的位置，再确定数字N-1的位置……直到所有数字位置确定。期间主要是元素的插入操作。
#include<stdio.h>
#include<stdlib.h>
#define LEN 60
int num[LEN]; //输入，
int rs[LEN];//所求结果，两种情况的结果都用rs[]记录。
int N;
void fP()
{
int i, j, k;
int ps;
for(i = 1; i <= N; i++)
{
ps = 0;
while(num[++ps] != i);
int count = 0;
for(k = 1; k < ps; k++)
if(num[k] > i)
count++;
rs[i] = count;
}
}
void Insert(int ps, int insertnum, int len)//插入函数
{
int i, j;
for(i = len; i >= ps; i--)
rs[i + 1] = rs[i];
rs[ps] = insertnum;
}
void fI()
{
int i, j;
int len;
rs[1] = N;
len = 1;
for(i = N - 1; i >= 1; i--)
{
int ps = num[i] + 1;
Insert(ps, i, len);
len++;
}
}
int main()
{
int i, j;
char c;
scanf("%d", &N);
while(N != 0)
{
getchar();
c = getchar();
for(i = 1; i <= N; i++)
scanf("%d", &num[i]);
if(c == 'P')
fP();
else
fI();
for(i = 1; i < N; i++)
printf("%d ", rs[i]);
printf("%d\n", rs[i]);
scanf("%d", &N);
}
//system("pause");
}posted @
2012-08-02 16:19 小鼠标 阅读(206) |
评论 (0) |
编辑 收藏二分查找，是一种针对有序序列的查找方式，每次迭代会缩小一半的查找范围，一次查找的时间复杂度为O(logN)。
简单说一下二分查找过程：在有序序列seq[]中找一个数n，假设这个序列的起始下标分别为a，b，mid=(a+b)/2，那么n要么就是seq[mid]（n=seq[mid]），要么在mid左边（n<seq[mid]），要么在mid右边（n>seq[mid]），要么这个数根本不在seq[]中。
下面这道题是二分查找的典型应用：
zoj1101
题意描述：在给定整数序列（<=1000）中找出四个不同的数，使得三个数的和等于另外一个数。
直接用四层循环铁定超时，这里采用了一种拿空间换时间的方式。
假设有a+b+d=c，这等价于a+b=c-d，我们可以把所有的a+b存起来（<=10^6个），把所有的c-d也存起来（<=10^6个），当拿到每一个a+b时我们只需要在所有c-d的序列中查找就行了。先把c-d序列排序，排序时间复杂度O(NlogN)，查找过程可以用二分，这样就不会超时啦。
以下是本题代码：
#include<stdio.h>
#include<stdlib.h>
#define MAX 2100000000
#define LEN 1000010
#define LEN1 1010
typedef struct
{
int rs;
int a;
int b;
}Node;
Node addseq[LEN];
Node subseq[LEN];
int num[LEN1];
int seqlen;
int wagamount;
int binSch(int n, int bg, int ed)//二分查找——递归方式
{
if(bg > ed)
return -1;
if(bg == ed)
{
if(n == subseq[bg].rs)
return bg;
return -1;
}
int mid = (bg + ed) / 2;
if(n == subseq[mid].rs)
return mid;
if(n < subseq[mid].rs)
return binSch(n, bg, mid - 1);
if(n > subseq[mid].rs)
return binSch(n, mid + 1, ed);
}
int binSch2(int n, int bg, int ed)//二分查找——非递归方式
{
while(bg <= ed)
{
int mid = (bg + ed) / 2;
if(n == subseq[mid].rs)
return mid;
if(n < subseq[mid].rs)
ed = mid - 1;
else
bg = mid + 1;
}
return -1;
}
int findWinner()
{
int i, j;
int n;
for(i = 0; i < seqlen; i++)
{
n = addseq[i].rs;
int a = addseq[i].a;
int b = addseq[i].b;
int find = binSch(n, 0, seqlen - 1);
if(find != -1)
{
int c = subseq[find].a;
int d = subseq[find].b;
if(a != b && a != c && a != d && b != c && b != d && c != d)
{
if(c > wagamount)
wagamount = c;
}
}
}
}
int cmp(const void *a, const void *b)
{
Node *a0 = (Node*)a;
Node *b0 = (Node*)b;
return a0 -> rs - b0 -> rs;
}
int main()
{
int i, j;
int n;
scanf("%d", &n);
while(n != 0)
{
for(i = 0; i < n; i++)
scanf("%d", &num[i]);
seqlen = 0;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
if(j != i)
{
addseq[seqlen].rs = num[i] + num[j];
addseq[seqlen].a = num[i];
addseq[seqlen].b = num[j];
subseq[seqlen].rs = num[i] - num[j];
subseq[seqlen].a = num[i];
subseq[seqlen].b = num[j];
seqlen++;
}
qsort(subseq, seqlen, sizeof(Node), cmp);
wagamount = -MAX;
findWinner();
if(wagamount != -MAX)
printf("%d\n", wagamount);
else
printf("no solution\n");
scanf("%d", &n);
}
//system("pause");
}
posted @
2012-08-01 21:39 小鼠标 阅读(1020) |
评论 (0) |
编辑 收藏
今天写C代码的时候用到了字符串结束标记，猛然感觉有些陌生，索性复习一下C语言的转义字符。
转义字符——当然也是字符，引用的时候要加单引号。C语言中之说以会出现转义字符，无非处于以下几个原因：
1.有些字符是不可见的，无法通过键盘输入（比如换行符、回车符、响铃等）。
2.有些字符已经有特殊的用途，无法直接引用（比如:'\'，单引号、双引号等）。
3.使用转义字符能够使意图更清楚（比如字符串结束标志，我们更倾向于写成'\0'，而不是直接赋0值）。
下表列出了C语言中所有的转义字符：
| 转义字符 |
意义 |
ASCII码值（十进制） |
| \a |
响铃(BEL) |
007 |
| \b |
退格(BS) ，将当前位置移到前一列 |
008 |
| \f |
换页(FF)，将当前位置移到下页开头 |
012 |
| \n |
换行(LF) ，将当前位置移到下一行开头 |
010 |
| \r |
回车(CR) ，将当前位置移到本行开头 |
013 |
| \t |
水平制表(HT) （跳到下一个TAB位置） |
009 |
| \v |
垂直制表(VT) |
011 |
| \\ |
代表一个反斜线字符''\' |
092 |
| |
|
|
| \' |
代表一个单引号（撇号）字符 |
039 |
| \" |
代表一个双引号字符 |
034 |
| \0 |
空字符(NULL) |
000 |
| \ddd |
1到3位八进制数所代表的任意字符 |
三位八进制 |
| \xhh |
1到2位十六进制所代表的任意字符 |
二位十六进制 |
posted @
2012-07-31 23:09 小鼠标 阅读(1690) |
评论 (0) |
编辑 收藏
线段树题，本题对线段树的操作有建树（MakeTree()）、查找（Query()）、更新（update()）。
建树一次完成，时间花费为O(LogN)；查询的时间复杂度鄙人还不会分析O(∩_∩)O~，最坏可能是O(N)，不过这种情况应该很难出现；更新的算法值得商榷，不同的策略时间复杂度会相差很大。下面讲解两种比较用以想到的更新策略。
更新方法一：
每次都将所有能更新的节点更新，这种方式最坏情况下将会更新树中所有节点，此时时间复杂度为O(N)。本题使用这种方法会TLE。
更新方法二：
每次都尽量少的更新节点信息，与第一种方法相比，Node内会多一个变量en，我把它形象的称之为“势能”，计算结果时要将该的所有父节点的“势能”也考虑在内。这种方法的时间复杂度也不好分析，但明显优于第一种方法。
这一题对时间卡的很紧，主要是花在树的更新上。
关于线段树可以先参阅：
http://www.cppblog.com/hoolee/archive/2012/07/29/185531.html以下是本题代码：
#include<stdio.h>
#include<stdlib.h>
#define LEN 100010
#define LEN0 6550000
typedef struct
{
int a, b;
int l, r;
long long sum;//记录该区间内的部分和
long long en;//记录该节点“势能”。
}Node;
int count;
Node A[LEN0];
int allNum[LEN];
void MakeTree(int i)
{
A[i].en = 0;
int a = A[i].a;
int b = A[i].b;
int mid = (a + b) / 2;
if(a == b)
{
A[i].sum = allNum[a];
return;
}
int l = ++count;
int r = ++count;
A[l].a = a;
A[l].b = mid;
A[r].a = mid + 1;
A[r].b = b;
MakeTree(l);
MakeTree(r);
A[i].sum = A[l].sum + A[r].sum;
A[i].l = l;
A[i].r = r;
}
long long Query(int t, int aa, int bb, long long en)
{
int a = A[t].a;
int b = A[t].b;
if(a == aa && b == bb)//1
{
return A[t].sum + en * (bb - aa + 1);
}
int mid = (a + b) / 2;
if(bb <= mid)//2
return Query(A[t].l, aa, bb, en + A[t].en);
if(aa >= mid + 1)//3
return Query(A[t].r, aa, bb, en + A[t].en);
long long suml = Query(A[t].l, aa, mid, en + A[t].en);//4
long long sumr = Query(A[t].r, mid + 1, bb, en + A[t].en);
return suml + sumr;
}
void Update(int t, int aa, int bb, int c)
{
int a = A[t].a;
int b = A[t].b;
int mid = (a + b) / 2;
int l = A[t].l;
int r = A[t].r;
A[t].sum += (bb - aa + 1) * c;
if(aa == a && bb == b)
{
A[t].en += c;
return;
}
if(bb <= mid)
Update(l, aa, bb, c);
else if(aa >= mid + 1)
Update(r, aa, bb, c);
else
{
Update(l, aa, mid, c);
Update(r, mid + 1, bb, c);
}
}
int main()
{
int i, j;
int N, Q;
int a, b, c;
scanf("%d%d", &N, &Q);
for(i = 1; i <= N; i++)
scanf("%d", &allNum[i]);
count = 0;
int t = ++count;
A[t].a = 1;
A[t].b = N;
MakeTree(t);
char str[50];
getchar();
for(i = 0; i < Q; i++)
{
gets(str);
if(str[0] == 'Q')
{
sscanf(&str[1], "%d%d", &a, &b);
long long sum = Query(1, a, b, 0);
printf("%lld\n", sum);
}
else if(str[0] == 'C')
{
sscanf(&str[1], "%d%d%d", &a, &b, &c);
Update(1, a, b, c);
}
}
//system("pause");
}posted @
2012-07-31 20:40 小鼠标 阅读(3596) |
评论 (0) |
编辑 收藏
即使是没有算法的题，也应该想清楚了再写，特别是关于字符串处理的，细节很多，稍不注意就会发生错误。
下面这道题是经典的“回文”题，要求输出每句话中每个单词的回文，但是单词在句子中的位置不变。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 20000
void Reversal(char *str)
{
int i, j;
int len = strlen(str);
int bg;
for(i = 0; i <= len; i++)//跳过句首的空格
if(str[i] == ' ')
putchar(str[i]);
else
{
bg = i;
break;
}
for(; i <= len; i++)
{
if(str[i] == ' ' || i == len)//一个单词结束，输出该单词的回文
{
for(j = i - 1; j >= bg; j--)
putchar(str[j]);
if(i != len)
putchar(str[i]);
}
if(str[i] == ' ' && str[i + 1] != ' ')//新单词的开始标志
bg = i + 1;
}
}
int main()
{
int i, j;
int N, M;
int gard;
char str[LEN];
scanf("%d", &N);
gard = 0;
for(i = 0; i < N; i++)
{
if(gard++ != 0)
printf("\n");
scanf("%d", &M);
getchar();
for(j = 0; j < M; j++)
{
gets(str);
Reversal(str);
putchar(10);
}
}
//system("pause");
}
posted @
2012-07-31 16:58 小鼠标 阅读(315) |
评论 (1) |
编辑 收藏彻底的水题，因为没有说数据量，我把数组开小了，SF了四次，最后把数字串长
度开到4000才过，真是坑爹啊。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define LEN 4000
int isZero(char *str)
{
int len = strlen(str);
for(int i = 0; i < len; i++)
if(str[i] != '0')
return 0;
return 1;
}
int RootOne(int n)
{
int sum = 0;
while(n != 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
int Root(char *str)
{
int i, j;
int n = 0;
int len = strlen(str);
for(i = 0; i < len; i++)
{
n += str[i] - '0';
}
int sum = n;
while(sum / 10)
{
sum = RootOne(sum);
}
return sum;
}
int main()
{
int i, j;
char str[LEN];
while(scanf("%s", str) != NULL && !isZero(str))
{
int n = Root(str);
printf("%d\n", n);
//scanf("%s", str);
}
//system("pause");
}
posted @
2012-07-31 16:15 小鼠标 阅读(157) |
评论 (0) |
编辑 收藏
摘要: 这是我写的第一道线段树，思路还算清晰，不过之前走了不少弯路。主要错在：误以为线段树是一棵满二叉树，建树时吃了苦头。//线段树除了最后一层可能不满足满二叉树性质外，上面的所有层构成完全二叉树，因此仍然可以用满二叉树的性质：如果树根节点从1开始编号，则对任意编号的节点t，左子树编号为t*2，右子树编号为t*2+1，父节点编号为t/2。这样，建树的时候节点内就不用记录儿子或父节点的信息了。下面结合poj...
阅读全文
posted @
2012-07-29 10:44 小鼠标 阅读(1833) |
评论 (2) |
编辑 收藏
科学家发明了一种新的生物，这种生物能够两两合并，重量为m1的生物与重量为m2的生物合并后变为一个生物，该生物的重量为2*sqrt(m1*m2)。求给定数量的生物合并成一个生物后的最小重量。
贪心算法，每次选取重量最大的两个生物合并成一个即可。下面的代码是有优先队列（大顶堆）实现的。
不过，深入分析一下，由数学公式可以证明：m1+m2 >= 2*sqrt(m1*m2)，因此当两个生物合并后，重量一定是剩余生物中最大的，由此只要将原重量按降序排序一次，然后依次合并即可。
优先队列有些大材小用了。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN 110
void f(double *a, int top, int r)
{//筛选函数，保持大顶堆的性质。
int i, j;
for(j = 2 * top; j <= r; j *= 2)
{
if(j < r && a[j] < a[j + 1])
j++;
if(a[j] <= a[j / 2])
break;
double t = a[j];
a[j] = a[j / 2];
a[j / 2] = t;
}
}
double DeQueue(double *a, int *r)
{
double t = a[1];
a[1] = a[*r];
--*r;
f(a, 1, *r);
return t;
}
void EnQueue(double *a, int *r, double num)
{
++*r;
a[*r] = num;
int i = *r;
while(1)
{
if(i > 1 && a[i] > a[i / 2])
{
double t = a[i];
a[i] = a[i / 2];
a[i / 2] = t;
i /= 2;
}
else
break;
}
}
int main()
{
int i, j;
int N;
int r;
double a[LEN];
double w;
while(scanf("%d", &N) != EOF)
{
for(i = 1; i <= N; i++)
scanf("%lf", &a[i]);
for(i = N / 2; i >= 1; i--)//建立大顶堆，即是初始化队列
f(a, i, N);
r = N;
while(r > 1)
{
double m1 = DeQueue(a, &r);
double m2 = DeQueue(a, &r);
w = 2.0 * sqrt(m1 * m2);
EnQueue(a, &r, w);
}
printf("%.3lf\n", a[1]);
}
}
posted @
2012-07-21 22:22 小鼠标 阅读(767) |
评论 (0) |
编辑 收藏
摘要: 优先队列，其实我一直不愿承认“优先队列”是一种“队列”，现实世界的队列（比如排队）告诉我们，队列最明显的性质就是先进先出。而优先队列，似乎跟这个规则没什么关系……
阅读全文
posted @
2012-07-20 10:36 小鼠标 阅读(3277) |
评论 (0) |
编辑 收藏
摘要: 单调队列，顾名思义就是具有单调性的队列O(∩_∩)O~，一般的队列只能从队尾入队、队首出队；为了保持单调队列的单调性，单调队列除具有这两种性质外，还可以从队尾出队……
阅读全文
posted @
2012-07-19 12:21 小鼠标 阅读(5463) |
评论 (0) |
编辑 收藏