acm数据结构题解(3)

//下面为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();