acm数据结构题解

ZOJ1610

Painting some colored segments on a line, some previously painted segments may be covered by some the subsequent ones.

Your task is counting the segments of different colors you can see at last.

Input

The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.

Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:

x1 x2 c

x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicates the color of the segment.

All the numbers are in the range [0, 8000], and they are all integers. Input may contain several data set, process to the end of file.

Output

Each line of the output should contain a color index that can be seen from the top, following the count of the segments of this color, they should be printed according to the color index.

If some color can't be seen, you shouldn't print it. Print a blank line after every dataset.

Sample Input 5 0 4 4 0 3 1 3 4 2 0 2 2 0 2 3 4

0 1 1 3 4 1 1 3 2 1 3 1 6 0 1 0 1 2 1 2 3 1 1 2 0 2 3 0 1 2 1

Sample Output 1 1 2 1 3 1 1 1 0 2 1 1

#include #include #include #include #include #include #include #include #include #include #define L(x) (x << 1)

#define R(x) (x << 1 | 1)

using namespace std;

const int MAX = 8010; struct Tnode{ int col; int l,r;}; Tnode node[MAX*3]; int col[MAX],len[MAX];; void init() {

memset(node,0,sizeof(node)); memset(col,-1,sizeof(col)); }

void Build(int t,int l,int r) {

node[t].l = l; node[t].r = r; node[t].col = -1; if( l == r - 1 ) return ; int mid = ( l + r ) >> 1; Build(L(t), l, mid); Build(R(t), mid, r); }

void Updata(int t,int l,int r,int col) {

if( node[t].l >= l && node[t].r <= r ) {

node[t].col = col; return ; }

if( node[t].col == col ) return ; if( node[t].col >= 0 ) {

node[R(t)].col = node[t].col; node[L(t)].col = node[t].col; node[t].col = -1; }

int mid = (node[t].l + node[t].r) >> 1; if( l >= mid )

Updata(R(t),l,r,col); else

if( r <= mid )

Updata(L(t),l,r,col); else {

Updata(L(t),l,mid,col); Updata(R(t),mid,r,col);

} }

void Compute(int t,int l,int r) {

if( node[t].col >= 0 ) {

for(int i=l; i

if( node[t].l == node[t].r - 1 ) return ;// 如果父亲节点已经是这种颜色了，就没必要再染色了

int mid = (node[t].l + node[t].r) >> 1; if( l >= mid )

Compute(R(t),l,r); else

if( r <= mid )

Compute(L(t),l,r); else {

Compute(L(t),l,mid); Compute(R(t),mid,r); } }

int main() {

int n,x,y,color;

while( ~scanf(\ { init();

Build(1,0,8000); while( n-- ) {

scanf(\ Updata(1,x,y,color); }

Compute(1,0,8000); memset(len,0,sizeof(len)); for(int i=0; i

if( col[i+1] != col[i] && col[i] != -1 ) len[col[i]]++; for(int j=0; j

printf(\ printf(\ }

return 0; } ZOJ1610

求N个矩形覆盖的面积

#include #include #include #include using namespace std;

#define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1

const int maxn = 2222;

int cnt[maxn << 2]; //对于rt，若cnt[rt]>0，则对应子树的线段区间被完全覆盖；若cnt[rt]==0，则被部分覆盖/完全没有覆盖 double sum[maxn << 2]; //对于rt,sum[rt]为对应子树覆盖的到线段区间的长度

double X[maxn]; //所有矩形的左右边界“直线”（每个矩形有两条这种直线，分别占用本数组的两个元素）

//（矩形）上/下边界“线段” struct Seg {

double h , l , r; //h高度, l左端点, r右端点 int s; //s==1为下边界线段； s==-1为上边界线段

Seg(){}

Seg(double a,double b,double c,int d) : l(a) , r(b) , h(c) , s(d) {}

//需要按照上/下边界线段的高度来排序

bool operator < (const Seg &cmp) const {//看运算符重载??? return h < cmp.h; } }ss[maxn];

void PushUp(int rt,int l,int r) {

if (cnt[rt]) sum[rt] = X[r+1] - X[l]; //子树rt的线段区间完全覆盖

else sum[rt] = sum[rt<<1] + sum[rt<<1|1]; //子树rt的线段区间没有完全覆盖（没有覆盖/部分覆盖） }

//需要插入/移出线段树的“上/下边界线段”： 左端点X[L], 右端点X[R+1], c==1下边界/c==-1上边界 //待插入/移除的线段树子树范围

void update(int L,int R,int c,int l,int r,int rt) { if (L <= l && r <= R) { cnt[rt] += c; PushUp(rt , l , r); return ;

}

int m = (l + r) >> 1;

if (L <= m) update(L , R , c , lson); if (m < R) update(L , R , c , rson);

PushUp(rt , l , r); }

int Bin(double key,int n,double X[]) { int l = 0 , r = n - 1; while (l <= r) {

int m = (l + r) >> 1;

//1. 第1个分支是“递归终止条件” if (X[m] == key) return m;

//2. 第2、3个分支是“二分后的两个子问题” if (X[m] < key) l = m + 1; else r = m - 1; }

return -1; }

int main() { int n , cas = 1;

while (~scanf(\

int m = 0; while (n --) {

double a , b , c , d;

scanf(\ X[m] = a;

ss[m++] = Seg(a , c , b , 1); X[m] = c;

ss[m++] = Seg(a , c , d , -1); }

sort(X , X + m); sort(ss , ss + m);

//X[]已经递增排序后，如下操作使得X[]中不等的数字依次放在靠前

//例如X[]={1,2,2,5,5,7} --> X[]={1,2,5,7,5,7} //处理后，其中X[0, ... ,k-1]为不等的数字 int k = 1;

for (int i = 1 ; i < m ; i ++) { if (X[i] != X[i-1]) X[k++] = X[i]; }

memset(cnt , 0 , sizeof(cnt)); memset(sum , 0 , sizeof(sum));

//下面为m-1轮扫描的过程 double ret = 0;

for (int i = 0 ; i < m - 1 ; i ++) { //i=0-->m-2 int l = Bin(ss[i].l , k , X); int r = Bin(ss[i].r , k , X) - 1;

//“上/下边界线段”长度不为0时，采取更新线段树。否则，这种“上/下边界线段”横向收缩为一个点

if (l <= r) update(l , r , ss[i].s , 0 , k - 1, 1);

//每轮扫描：更新线段树后，累计本轮扫描新增的面积大小 ret += sum[1] * (ss[i+1].h - ss[i].h); }

printf(\++ , ret); }

return 0; } ZOJ 1038 T9

#include #include #include #include using namespace std; const int MAX = 1000000000; struct Trie {

int val; char c;

Trie *next[26], *f; }tree[100000],*root; int k; Trie* New() {

Trie* p = tree + k++; p->val = 0;

for(int i = 0; i < 26; i++) {

p->next[i] = NULL; }

p->f = NULL; return p; }

void insert(char s[], int w) {

int len = strlen(s); Trie *p = root;

for(int i = 0; i < len; i++) {

if(!p->next[s[i]-'a']) {

p->next[s[i]-'a'] = New(); p->next[s[i]-'a']->f = p; p->next[s[i]-'a']->c = s[i]; }

p = p->next[s[i]-'a']; p->val += w; }

}

Trie *p,*q;

/*q用来存放频率最高的字符串*/ int m; bool flag; queue Q;

void solve(int b, int e) {

for(int i = b; i <= e; i++) {

if(p->next[i]) {

flag = true; Q.push(p->next[i]); if(m < p->next[i]->val) {

m = p->next[i]->val; q = p->next[i]; } } } }

void output() {

char s[105]; int top = 0; while(q->f) {

s[top++] = q->c; q = q->f; }

while(top) {

putchar(s[--top]); }

putchar('\\n'); }

/*处理435561*/ void bfs(char s[]) {

int len = strlen(s); Q.push(root);

for(int i = 0; s[i] != '1'; i++) {

m = 0; q = NULL; flag = false; int size = Q.size();

while(size--) {

p = Q.front(); Q.pop(); switch(s[i]) {

case '2':solve(0,2);break; case '3':solve(3,5);break; case '4':solve(6,8);break; case '5':solve(9,11);break; case '6':solve(12,14);break; case '7':solve(15,18);break; case '8':solve(19,21);break; case '9':solve(22,25);break; default:return; } }

if(!flag)puts(\ else output(); } }

int main() {

int t,n,u,w;

char s[105]; scanf(\

for(int c = 1; c <= t; c++) {

printf(\ k = 0; root = New(); scanf(\ while(n--) {

scanf(\ insert(s,w); }

scanf(\ while(u--) {

getchar(); scanf(\ bfs(s); putchar('\\n'); }

putchar('\\n'); }

return 0;

}

本文来源：https://www.bwwdw.com/article/8qx3.html