本文主要是介绍九度OJ 1376(最近零子序列、DP) 1377(序列、贪心) 1380(位运算) 1384(二分法查找) 1385(二叉树遍历)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1376：最近零子序列
http://ac.jobdu.com/problem.php?pid=1376
题意
给定一个整数序列，求其最接近0的连续子串和。
思路
DP类题目，注意考虑正数负数两种情况，略复杂一些。
代码
#include <stdio.h>
#include <stdlib.h>
#include <math.h>#define N 100000struct st {int s;int i;
};int cmp(const void *a, const void *b)
{struct st *c = (struct st *)a;struct st *d = (struct st *)b;if (c->s != d->s)return c->s - d->s;elsereturn c->i - d->i;
}int main(void)
{int n, i;int a;struct st sum[N];while (scanf("%d", &n) != EOF){int min = 0;for (i=0; i<n; i++){scanf("%d", &a);if (i == 0){min = a;sum[i].s = a;sum[i].i = i;continue;}sum[i].s = sum[i-1].s + a;sum[i].i = i;if (abs(sum[i].s) < abs(min))min = sum[i].s;else if (abs(sum[i].s) == abs(min) && sum[i].s > min)min = sum[i].s;}qsort(sum, n, sizeof(sum[0]), cmp);for (i=1; i<n; i++){int tmps = sum[i].s-sum[i-1].s;int tmpi = sum[i].i-sum[i-1].i;if (tmps < abs(min)){if (tmpi > 0)min = tmps;elsemin = -tmps;}else if (tmps == abs(min) && min < 0){if (tmpi > 0)min = tmps;}}printf("%d\n", min);}return 0;
}
/**************************************************************Problem: 1376User: liangrx06Language: CResult: AcceptedTime:180 msMemory:2304 kb
****************************************************************/1377：缓变序列
http://ac.jobdu.com/problem.php?pid=1377
题意
如何将给定的整数序列变换成缓变序列：即任意两个相邻的元素相差均为1，第1个元素和最后一个元素相差也为1. 变换是指改变原整数序列中各元素的顺序。
思路
- 出现的数一定是连续的,也就是说,一定是k,k+1,k+2这样的序列,不可能k出现了,k+2出现了,k+1却没有出现
- 根据1中的性质, 不妨设数是1,2,3,…m,且i出现的次数是X(i),显然X(i)>= 1
- 定义数组S,有S(1)=X(1),S(i)=X(i)-S(i-1),显然有S(1),S(2)…S(m-1)>0且S(m)=0
- 3中定义的S满足的条件即是充要条件
代码
#include <stdio.h>
#include <string.h>#define N 100000
#define M 10000int main(void)
{int n, i, k;int c[M+1];int min, max;while (scanf("%d", &n) != EOF){memset(c, 0, sizeof(c));min = M;max = 0;for (i=0; i<n; i++){scanf("%d", &k);min = (k < min) ? k : min;max = (k > max) ? k : max;c[k] ++;}for (i=min+1; i<max; i++){c[i] -= c[i-1];if (c[i] <= 0)break;}if (c[i] == c[i-1])printf("YES\n");elseprintf("NO\n");}return 0;
}
/**************************************************************Problem: 1377User: liangrx06Language: CResult: AcceptedTime:30 msMemory:912 kb
****************************************************************/1380：lucky number
http://ac.jobdu.com/problem.php?pid=1380
题意
每个人有自己的lucky number，小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话，都是他的lucky number。但是，现在这个序列很大，他无法快速找到所有lucky number。既然这样，他就想找到那些不是lucky number。
思路
这类题目用位运算往往有奇效，详见代码。
代码
#include <stdio.h>int main()
{
int i, j, n, m, t;
int sum[32];
int result; while(scanf("%d%d", &n, &m) != EOF)
{
for (j=0; j<32; j++)
sum[j] = 0; for (i=0; i<m; i++)
{
scanf("%d", &t);
for (j=0; j<32 && t; j++)
{
sum[j]+=((t)&0x01);
sum[j]%=n;
t >>= 1;
}
} result = 0;
for (j=0; j<32; j++)
{
if (sum[j] % n != 0)
result += 1<<j;
}
printf("%d\n", result);
}
return 0;
}
/**************************************************************
Problem: 1380
User: liangrx06
Language: C
Result: Accepted
Time:1450 ms
Memory:912 kb
****************************************************************/1384：二维数组中的查找
http://ac.jobdu.com/problem.php?pid=1384
题意
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路
二分法查找，但二维有序数组的二分法有些区别，详见代码。
代码
#include <stdio.h>#define N 1000int binarySearch(int a[N][N], int is, int ie, int js, int je, int k)
{if (is > ie || js > je)return 0;if (is == ie && js == je){if (a[is][js] == k)return 1;elsereturn 0;}int im=(is+ie)/2, jm=(js+je)/2;int result = 0;//printf("is=%d, im=%d, ie=%d, js=%d, jm=%d, je=%d\n", is, im, ie, js, jm, je);if (a[im][jm] == k)return 1;if (k < a[im][jm]){result |= binarySearch(a, is, im-1, js, jm-1, k);if (result == 1) return 1;result |= binarySearch(a, is, im-1, jm, je, k);if (result == 1) return 1;result |= binarySearch(a, im, ie, js, jm-1, k);}if (k > a[im][jm]){//printf("%d, %d, %d, %d\n", im+1, ie, jm+1, je);//printf("%d, %d, %d, %d\n", is, im, jm+1, je);//printf("%d, %d, %d, %d\n", im+1, ie, js, jm);result |= binarySearch(a, im+1, ie, jm+1, je, k);if (result == 1) return 1;result |= binarySearch(a, is, im, jm+1, je, k);if (result == 1) return 1;result |= binarySearch(a, im+1, ie, js, jm, k);}return result;
}int main(void)
{int m, n, i, j;int a[N][N];int k;while (scanf("%d%d", &m, &n) != EOF){scanf("%d", &k);for(i=0; i<m; i++)for(j=0; j<n; j++)scanf("%d", &a[i][j]);int result = binarySearch(a, 0, m-1, 0, n-1, k);if (result == 1)printf("Yes\n");elseprintf("No\n");}return 0;
}
/**************************************************************Problem: 1384User: liangrx06Language: CResult: AcceptedTime:610 msMemory:4744 kb
****************************************************************/1385：重建二叉树
http://ac.jobdu.com/problem.php?pid=1385
题意
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
思路
抓住前序遍历和中序遍历的特点。
代码
#include <stdio.h>
#include <string.h>#define N 1000int getAfter(int *b, int *m, int *a, int len)
{if (len == 1){if (b[0] != m[0])return 0;a[0] = b[0];return 1;}int root = b[0];int i;int res;for (i=0; i<len; i++){if (m[i] == root)break;}if (i == len)return 0;a[len-1] = root;if (i > 0){res = getAfter(b+1, m, a, i);if (res == 0)return 0;}if (len-1-i > 0){res = getAfter(b+1+i, m+1+i, a+i, len-1-i);if (res == 0)return 0;}return 1;
}
int main(void)
{int n, i, res;int b[1000], m[1000], a[1000];while (scanf("%d", &n) != EOF){for (i=0; i<n; i++)scanf("%d", &b[i]);for (i=0; i<n; i++)scanf("%d", &m[i]);res = getAfter(b, m, a, n);if (res == 0)printf("No");else{for (i=0; i<n; i++)printf("%d ", a[i]);}printf("\n");}return 0;
}
/**************************************************************Problem: 1385User: liangrx06Language: CResult: AcceptedTime:0 msMemory:912 kb
****************************************************************/这篇关于九度OJ 1376(最近零子序列、DP) 1377(序列、贪心) 1380(位运算) 1384(二分法查找) 1385(二叉树遍历)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
