当前位置：首页 -> 基础 -> c++编程基础

Codeforces Round #221 (Div. 1)

2014-11-24 07:27:21 · 作者: · 浏览: 0
标签: Codeforces Round #221 Div.

题目链接

C：

bfs 　+　射线

一个闭合路径用bfs就可以搜出来，只不过还要在搜的过程中判断是否包围了某些点，用射线法就好了，想象有一条射线从某个点往一个边界射出去，然后这个点被某条路径包围与否在路径经过其下方的时候改变一次（我是射往下方）

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       struct node { int x, y, st; node(int x = 0, int y = 0, int st = 0) :x(x),y(y),st(st){} }; int f[20][20][1<<8]; //x y bomb treasure int n, m, object[8][2], cntOfobject, value[8], number[8]; char mp[21][21]; bool valid(int x,int y) { return x >= 0 && x < n && y >= 0 && y < m && mp[x][y] == '.' || mp[x][y] == 'S'; } int get(int x,int y,int ny,int st) { for(int i = 0; i < cntOfobject; i++) { if(x > object[i][0] && (y == object[i][1] && ny > object[i][1] || ny == object[i][1] && y > object[i][1])) st ^= 1 << i; } return st; } int dx[] = {1,0,0,-1}; int dy[] = {0,1,-1,0}; int bfs(int sx,int sy) { std::queue
      
        Q; memset(f,-1,sizeof(f)); Q.push(node(sx, sy, 0)); f[sx][sy][0] = 0; while(!Q.empty()) { node fr = Q.front(); Q.pop(); for(int i = 0; i < 4; i++) { int tx = fr.x + dx[i]; int ty = fr.y + dy[i]; if(valid(tx, ty)) { int newst = get(tx, ty, fr.y, fr.st); if(f[tx][ty][newst] == -1) { f[tx][ty][newst] = f[fr.x][fr.y][fr.st] + 1; // printf(%d %d %d %d ,tx,ty,newst,f[tx][ty][newst]); Q.push(node(tx, ty, newst)); } } } } int ans = 0; for(int i = 0; i < (1<
       
        > j & 1){ if(number[j] != -1) sum += value[number[j]]; else bomb = true; } if(bomb) continue; ans = std::max(ans, sum - f[sx][sy][i]); } return ans; } int main() { scanf(%d%d,&n,&m); int sx, sy, mx = 0; for(int i = 0; i < n; i++) { scanf(%s,mp[i]); for(int j = 0; j < m; j++) { if(mp[i][j] >= '1' && mp[i][j] <= '8' || mp[i][j] == 'B') { object[cntOfobject][0] = i; object[cntOfobject][1] = j; if(mp[i][j] == 'B') { number[cntOfobject] = -1; } else number[cntOfobject] = mp[i][j] - '1', mx = std::max(mx,mp[i][j]-'0'); cntOfobject++; } if(mp[i][j] == 'S') { sx = i; sy = j; } } } for(int i = 0; i < mx; i++) scanf(%d,&value[i]); printf(%d ,bfs(sx, sy)); return 0; }


D：

一棵树，每个节点有颜色，ｍ个询问，问某个节点的子树内出现次数=ki的颜色的种类数

如果能知道一棵子树的所有信息，然后递归回去的时候能合并子树间的信息就可以了

需要维护的信息是子树内每种颜色出现的次数，然后再把次数插入一棵平衡树

采用启发式合并，合并的时候把size 小的往size大的合并

类似的题：

http://acm.hdu.edu.cn/showproblem.php pid=4358

#include
#include #include #include #include #include #include const int N = 100010; struct node; node* null; struct node { node *c[2], *fa; int key, sz, count, is; node(int key=0,int sz=0,int count=0,int is=0,node *fa = null): key(key), sz(sz), count(count),is(is),fa(fa){ c[0] = c[1] = null; } bool d() { return fa->c[1] == this; } void setc(int s,node *who) { c[s] = who; who->fa = this; } void rot() ; void up(); void splay(); node *piv; bool f; void insert(node* &x,int k,int delta) { if(x == null) { x = new node(k, 1, 1, 1, fa); f = true; piv = x; return ; } if(x -> key == k) { x->count += delta; } else if(x->key > k) c[0]->insert(c[0], k, delta); else c[1]->insert(c[1], k, delta); up(); } int query(int value); }*tree[N]; void node::rot() { node *y = fa; bool f = d(); y->setc(f,c[!f]); fa = y->fa; if(y->is) y->is = 0, is = 1; else fa->c[y->d()] = this; this->setc(!f,y); } void node::up() { sz = c[0]->sz + c[1]->sz + count; } void node::splay() { for(;!is;) { if(fa->is) rot(); else if(fa->d() == d()) fa->rot(),rot(); else rot(),rot(); } } int node::query(int value) { if(this == null) return 0; if(key < value) return c[1]->query(value); return c[0]->query(value) + count + c[1]->sz; } int n, m; int firstEdge[N], previousEdge[N*2], pointTo[N*2]; int totalEdge; int color[N], ans[N]; std::vector > query[N]; std::map mp[N];// void add(int a,int b) { pointTo[totalEdge] = b; previousEdge[totalEdge] = firstEdge[a]; firstEdge[a] = totalEdge ++; } void merge_small_to_big(int x,int y) { if(mp[x].size() < mp[y].size()) { mp[x].swap(mp[y]); std::swap(tree[x], tree[y]); } for(std::map ::iterator it = mp[y].begin(); it != mp[y].end(); it++) { if(mp[x].count(it->first)) { tree[x]->f = false; tree[x]->insert(tree[x], mp[x][it->first], -1); if(tree[x]->f) tree[x]->piv->splay(); } mp[x][it->first] += it->second; tree[x]->f = false; tree[x]->insert(tree[x], mp[x][it->first], 1); if(tree[x]->f) tree[x]->piv->splay(); } } void dfs(int u,int fa) { tree[u] = new node(1, 1, 1, 1); mp[u].clear(); mp[u][color[u]] = 1; for(int i = firstEdge[u]; i != -1; i = previousEdge[i]) { int v = pointTo[i]; if(v == fa) continue; dfs(v,u); merge_small_to_big(u, v); } // for(int i = 1; i <= 4; i++) // printf(mp[%d][%d]=%d ,u,i,mp[u][i]); for(int i = 0; i < query[u].size(); i++) { ans[query[u][i].second] = tree[u]->query(query[u][i].first); } } int main() { null = new node(); while(scanf(%d%d,&n,&m)!=EOF) { for(int i = 1; i <= n; i++) scanf(%d,&color[i]); std::fill(firstEdge,firstEdge + n + 1, -1); totalEdge = 0; for(int i = 1,a,b; i < n; i++) { scanf(%d%d,&a,&b); add(a,b), add(b,a); } for(int i = 0,a,b; i < m; i++) { scanf(%d%d,&a,&b); query[a].push_back(std::make_pair(b, i)); } dfs(1,-1); for(int i = 0; i < m; i++) printf(%d ,ans[i]); } return 0; }

Ｅ：坑