cavenkaka
- 浏览: 202433 次
- 性别:
- 来自: 武汉
-
文章列表
搞了这么久，看了自己以前制定的工作计划，大体上算是完成了，在数据结构方面又做了进一步的研究，但是距自己对自己的要求还有一大段距离，特别是算法方面，还有待加强。为此，下一步的学习计划如下：
a:复习以前自己所写的知识，总结总结，抽象出概念。
b: 学习算法的东西，不只是数据结构课本上的算法，这种东西都要强化训练，包括DP，贪心，背包问题，搜索等等，都需要自己强化训练。
c:关于应用层的东西自己还不是完全那么明白，在看书的同时还要跟着一两个项目去看，可以看别人做过的东西，也可以自己尝试去写一些小的应用，这样也是为了找工作做准备的。
d:现在回过头来看看自己还是有这个实力去完成这样的东西的 ...
题意：Professor Hopper专门研究bug的生活习性，他表示若两只bugs的生活习性差别很大，则说明他们可能为不同的性别，但如果出现三只bugs的习性两两差别很大，则有可能出现同性恋的bug了。现在有n只bugs，和生活习性差别很大的m对bugs的编号，问这些bugs中，有没有可能出现同性恋者。题目中给出的数对比如（1 2 ，2 3 ，1 3）是表示交配关系的，而且交配的都默认为理解为异性，这里如果有矛盾的情况，就表明有同性恋存在。比如1和2是异性，2和3为异性，那就表明1和3是同性，但是给出的数对是1和3异性表明有矛盾存在，则有同性恋存在，则输出Suspicious bugs fou ...
题意：
给两串DNA序列，按照给定的方法找他们最大的相似度。比如序列AGTGATG和GTTAG，化为AGTGATG和-GTTA-G，相似度最大，为14。
思路：
由低到高的往上递推，动态规划。
设dp(i,j)为第一个序列(s1)的前i个数和第二个序列(s2)的前j个数的相似度的最大值。当s1[i-1]==s2[j-1]时，由题目给出的表显然可以得出dp(i,j)=dp(i-1,j-1)+p[s1[i-1]][s2[j-1]];score数组为题目中给出的那个表格。当s1[i-1]!=s2[j-1]时，反证法显然有dp(i,j)=max(d(i-1,j)+score[ ...
题意：FJ有n头牛，排列成一条直线(不会在同一个点)，给出每头牛在直线上的坐标x。另外，每头牛还有一个自己的声调v，如果两头牛(i和j)之间想要沟通的话，它们必须用同个音调max(v[i],v[j])，沟通起来消耗的能量为：max(v[i],v[j]) * 它们之间的距离。问要使所有的牛之间都能沟通(两两之间)，总共需要消耗多少能量。 思路：树状数组。很好的一道题。把牛按x升序排列，然后：(很难表示清楚，囧...)1：把沟通分成向左和向右，向左就是：v[右] > v[左]，它们之间取右边牛的声调。2：先求向左的总能量：运用2个树状数组，都以牛的声调做下标，arNum[]用于求某个声调范围内 ...
题意：一个n*n的01矩阵，和几种动态操作，包括对子矩阵(x,y,xx,yy)的所有元素异或，查询某一点(x,y)的元素值。 思路：二维树状数组。异或操作不难修改，重点这道题目与普通的树状数组不同的是：普通的树状数组一般是修改点，查询区域；而这里是修改区域，查询点。所以要对普通的add()函数和sum()函数进行对调修改，这里要对两个函数的性质了解清楚，可以先从一维的树状数组理解入手，再按二维的模板去写。
代码如下：
#include<iostream>
using namespace std;
const int Max = 1005;
int n, m;
...
题意：这道题目只是题意自己就去理解了半天，大概题意如下：给出i一个n*n的矩阵，初始化为均为0，还有关于这个矩阵的几种操作，操作如下：命令1：(X Y A)对位于坐标（X Y）的值加A；命令2：（L B R T）求出位于L<=x<=R，B<=y<=T的值的和；命令3：退出不做任何操作。
思路分析如下：二维树状数组，典型的动态操作题目。查询子矩阵(x,y,xx,yy)的元素和，注意一下就可以了:sum(xx, yy)-sum(x-1, yy)-sum(xx, y-1)+sum(x-1,y-1);
代码如下：
#include<ios ...
题意：字符的全排列（顺序：'A'<'a'<'B'<'b'<...<'Z'<'z'）。
思路：STL中next_permutation的运用，多写一个比较函数。
源代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 15;
int val(char c) // 按照'A'<'a'<'B'<'b'<...<'Z'<'z'的顺序，每个字母赋一个固定的权值。
{
...
题意:输出一个字符串从小到大的全排列,而且不能输出重复的排列。。。
思路：传说中勤劳的小孩应该用递归....我承认我很懒,还是用STL吧!有一个神奇的函数叫做next_permutation(a,a+n)返回值为bool型，用来判断还有没有排列。记住先是字典序，才能用它产生去全排列。
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 205;
int main()
{
char str[MAX];
wh ...
题意：日本岛东海岸与西海岸分别有N和M个城市，现在修高速公路连接东西海岸的城市，求交点个数。
做法：记每条告诉公路为(x,y), 即东岸的第x个城市与西岸的第y个城市修一条路。当两条路有交点时，满足（x1-x2）*（y1-y2） < 0。所以，将每条路按x从小到达排序，若x相同，按y从小到大排序。 然后按排序后的公路用树状数组在线更新，求y的逆序数之 和 即为交点个数。
上面说的可能有点难理解，详细说明如下。
记第i条边的端点分别为xi,yi。
由于x是从小到大排序的，假设当前我们在处理第k条边，那么第1~k-1条边的x必然是小于（等于时候暂且不讨论）第k条边的 ...
题意：FJ有n头牛(编号为1~n)，每一头牛都有一个测验值[S, E]，如果对于牛i和牛j来说，它们的测验值满足下面的条件则证明牛i比牛j强壮：Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj。现在已知每一头牛的测验值，要求输出每头牛有几头牛比其强壮。
思路：树状数组。需要对牛i比牛j强壮的条件进行理解。把牛群按照测验值E的降序排序，(E相等按S的升序)，那么接着就只需考虑S值，如果当前牛的测验值为[s, e]，那么比它强壮的牛的个数，就等于排序在它前面的，S值在[0,s]区间的牛数量(E相等的话为[0,s-1])。下面的就是树 ...
树状数组
第01讲 什么是树状数组？
树状数组用来求区间元素和，求一次区间元素和的时间效率为O(logn)。有些同学会觉得很奇怪。用一个数组S[i]保存序列A[]的前i个元素和，那么求区间i,j的元素和不就为S[j]-S[i-1]，那么时间效率为O(1)，岂不是更快？但是，如果题目的A[]会改变呢？例如：我们来定义下列问题：我们有
题意：有n(1~10000)个市长的候选人，这个城市专门为他们安排了一个长为10000000的墙，他们每人可以按顺序帖自己的竞选海报到墙上，所有的海报与墙一样高，分别帖在墙的[a[i],b[i]]区间上。问最后能露出来被看到的海报有多少张。
思路：线段树+离散化。由于长度太大，无法直接建树，而n最大只有10000，故因考虑离散化。
例：区间[1,6], [1,7], [2,10], [8,18]
离散化后的结果为：区间[1,3], [1,4], [2,6], [5,7]。
题意：一个hotel，有n间连续的房间，现在有m组操作：
type 1: '1, a, b': 第a个房间起的b个房间有旅客入住。 type 2: '2, a, b': 第a个房间起的b个房间的旅客离开。 type 3: '3': 问最长的连续空房间有多少间。
思路：线段树。这道题很好的利用线段树递归的性质，加深了对线段树递归的理解。复习了一下延迟的操作，学会了与延迟操作相反的操作，即利用递归，在递归回来的时候，由于左右子结点性质的改变，即时对父结点
题意：一个具有n(1~100000)个点的序列，从大到小排序，有一些点的大小是相等的，问区间[a,b]上，相等大小的点最多是几个。
思路：线段树+离散化。离散的运用：将连续的相等的一个区间的点集，聚集为线段树的一个节点，并且在这个节点上有信息能体现出这个区间的性质。
代码如下：
#include<iostream>
using namespace std;
const int Max = 100050;
struct
{
int l, r, max;
}node[3*Max];
struct
{
int sta, end;
...
题意：长度为n(1~100000)个单位的画板，有t(1~30，位运算的可能性)种颜料。现在叫你完成m组操作：
1. "C A B C" Color the board from segment A to segment B with color C. 2. "P A B" Output the number of different colors painted between segment A and segment B (including).
思路：很经典的线段树。学习到了很多的新知识，最重要的是三点：1.延迟覆盖 ...