题意：抗日时期，八路军擅用地道把村落连起来，现指挥官要知道一些信息：对地道的操作如下
D x 表示销毁x这个地道
Q x 表示查询有多少个地道与x相连
R 修复最后被摧毁的地道
思路：线段路，记录每个结点左边 中间，右边 连续的地道数量。
//3412K
266MS
#include <stdio.h>
#define M 50050
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
struct data
{
int
l,r,state; //state
-1表示空，1...
阅读全文
题意：给一块长8000米的板上色 问最后能看见几种颜色 而每种颜色的几段
思路：线段树。这道题有很多细节
eg： 0 2 1
3 4 1
output 应该是 1 2 因为中间隔了一段空的
具体见代码
#include <stdio.h>
#include <string.h>
#define M 8005
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
struct data
{
int
l,r,col;
//col 等于 -1 表示什么色都没有
}node[M*3];
int
color[M];
/...
阅读全文
题意：一棵具有n个节点的树，一开始，每个节点上都有一个苹果。现在给出m组动态的操作：(C,i)是摘掉第i个节点上面的苹果(若苹果不存在，则为加上一个苹果)，(Q,i)是查询以第i个节点为根的子树有几个苹果(包括第i个节点)。
思路：
树状数组。这道题重点怎么建立树到树状数组的映射关系：利用dfs遍历树，对每个节点进行两次编号，第一次搜到第i个节点时的深度dep，为这个节点管辖区间的上限low[i](也为这个节点的下标)，然...
阅读全文
题意思路见上一篇 主要难在建树上，有人说这不一定是根二叉树 但我却用二叉树 做对了，可能是他代码写得不对吧
//8184K
563MS
#include <stdio.h>
#include <string.h>
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
#define M 100010
int head[M],vis[M],low[M],high[M];
int p,dep,n;
struct data
{
int
to,next;
}edge[M];
struct tree
{
int
l,r,pick;
//pick 为1 表示...
阅读全文
题意：给出每个star的坐标，求出在它左下方这个区域里有多个星星
思路：用树状数组做 简洁明了。。。。
//420K
157MS
#include <stdio.h>
#include <string.h>
#define lowbit(x) (x&(-x))
#define M 32010
int ar[M],n;
void add (int u,int w)
{
while (u
< M)
{
ar[u] += w;
u += lowbit(u);
}
}
int sum (int u)
{
int ans =
0;
while (u
> 0)
{
...
阅读全文
学习了！！
原文地址：poj 2777 : Count Color (线段树)作者：依然
题意：长度为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).
思路：很经典的线段树。学习到了很多的新知识，最...
阅读全文
不会做，看了别人的想法 做的
详见原文 http://blog.sina.com.cn/s/blog_6635898a0100kzpx.html
#include <stdio.h>
#define M 100005
struct data
{
int
l,r,max;
}node[3*M];
struct da
{
int
start,end;
}seg[M];
int num[M],hash[M];
int Max (int a,int b)
{
return a
> b?a:b;
}
void C_Tree (int left,int right,int u)
{
node[u].l =
left;
node[u].r =
right;
if (left ==
righ...
阅读全文
题意：有多栋建筑 它们有不同的高度 从一个面看进入 能看到的总面积
思路：线段树+离散化 因为它们的宽度太大，无法存储 所以得离散
PS：这道题又学到了一些新知道 1、另一种离散化的方法 2、unique 函数的使用
unique(first,last)
参数 first, last:指出要剔除连续重复元素的迭代器区间[first,last)
右边是开区间
返回值 返回剔除元素后的新区间的最后一个元素的迭代器位置
//
4028K
204MS
#include <stdio.h...
阅读全文
题意：四个柱子的汉诺塔 A B C D 开始A上有N个disk 全部移到D上最少的步数
思路： 首先你得明白三个柱子的汉诺塔 n个disk从A 到 C的最少步数 F(n) = 2^n
-1;
那四个呢？？ 其实题目已经告诉我们解法了 At first k >= 1 disks on tower
A are fixed and the remaining n-k disks are moved from tower A to
tower B using the algorithm for four towers.Then the remaining k
disks from tower A are moved to tower D...
阅读全文
题意：有一串 求最少加入多少个字母使它变成回文串。
思路：这个问题可以转换成求LCS 要使最少 则加入的字符的对称位置不可能是加入的字符（即应为原S串中的）
再想一下，就是求S中最长的回文子串（不一定连续） 然后用n - max就是ans
这就成了经典的LCS问题了
//49172K
782MS
#include <stdio.h>
#define M 5002
short int
c[M][M];
// 这里用short int 不然超内存了。。。
char s1[M],s2[M]; //s1 为...
阅读全文