BestCoder Round #1 1001 && 1002 hdu 4857 4858-白红宇

BestCoder Round #1 1001 && 1002 hdu 4857 4858

阅读量：6296 次

发布时间：2019-06-22

本文共 3605 字，大约阅读时间需要 12 分钟。

hdu 逃生

第一题是拓扑排序，不是按照字典序最小输出，而是要使较小的数排在最前面。。赛后弄了好久，才比较明白，我一直以为反向建图，i从1到n，开始深搜dfs( i )，对i点的边，由小到大继续搜一下，同时标记搜过的数，搜过之后就不再搜，搜到底之后ans[cnt++] = u;这样顺序输出就是答案，后来经过超哥指点，才明白深搜贪心是错的。只有反向建图，用优先队列把较大的数尽量排在前面，然后反序输出才是正解。。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 10 using namespace std; 11 12 #define mnx 104000 13 #define ll long long 14 #define inf 0x3f3f3f3f 15 #define lson l, m, rt << 1 16 #define rson m+1, r, rt << 1 | 1 17 18 vector
              
                vet[mnx]; 19 int cnt, ans[mnx], vis[mnx]; 20 int main(){ 21 int cas; 22 scanf( "%d", &cas ); 23 while( cas-- ){ 24 for( int i = 0; i < mnx; i++ ){ 25 vet[i].clear(); 26 } 27 memset( vis, 0, sizeof(vis) ); 28 cnt = 0; 29 int n, m; 30 scanf( "%d%d", &n, &m ); 31 for( int i = 0; i < m; i++ ){ 32 int u, v; 33 scanf( "%d%d", &u, &v ); 34 vis[u]++; 35 vet[v].push_back( u ); 36 } 37 priority_queue
               
                 que; 38 for( int i = 1; i <= n; i++ ){ 39 if( !vis[i] ) que.push( i ); 40 } 41 while( !que.empty() ){ 42 int u = que.top(); que.pop(); 43 for( int i = 0; i < vet[u].size(); i++ ){ 44 vis[vet[u][i]]--; 45 if( vis[vet[u][i]] == 0 ){ 46 que.push( vet[u][i] ); 47 } 48 } 49 ans[cnt++] = u; 50 } 51 for( int i = cnt-1; i >= 0; i-- ){ 52 if( i == 0 ){ 53 cout<
                
                 <

, greater

> q;104 for( int i = 1; i <= n; i++ ){105 if( d[i] == 0 ) q.push( i );106 }107 while( !q.empty() ){108 int u = q.top(); q.pop();109 ans[cnt++] = u;110 for( int i = first[u]; i != -1; i = nxt[i] ){111 int v = vv[i];112 d[v]--;113 if( d[v] == 0 ) q.push( v );114 }115 for( int i = 0; i < n; i++ ){116 cout<

<<" ";117 }118 cout<

View Code

hdu 项目管理

第二题数据比较水，暴力可以就过了。。赛后问了超哥正解，好像是图的分块：按点的度数和sqrtn分块，度数大于sqrtn的点最多有sqrtn个，把大点和大点建图，更新首先直接更新自己的值，然后更新小点的时候，一并更新小点连接的所有大点的答案，更新大点的时候，把相邻的大点也更新答案，询问的话，小点直接for循环累加val值，大点直接返回答案。。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 10 using namespace std;11 12 #define mnx 10400013 #define ll long long14 #define inf 0x3f3f3f3f15 #define lson l, m, rt << 116 #define rson m+1, r, rt << 1 | 117 18 vector
              
                g1[mnx], g2[mnx];19 int d[mnx], val[mnx], ans[mnx], n, m;;20 void init(){21 for( int i = 1; i <= n; i++ ){22 if( d[i] > 333 )23 for( int j = 0; j < g1[i].size(); j++ )24 if( d[g1[i][j]] > 333 ) 25 g2[i].push_back( g1[i][j] );26 }27 }28 void upd(){29 int u, v;30 scanf( "%d%d", &u, &v );31 val[u] += v;32 if( ans[u] <= 333 ){33 for( int i = 0; i < g1[u].size(); i++ ){34 int V = g1[u][i];35 if( d[V] > 333 ) ans[V] += v;36 }37 }38 else for( int i = 0; i < g2[u].size(); i++ ){39 ans[ g2[u][i] ] += v;40 }41 }42 void cal(){43 int u;44 scanf( "%d", &u );45 if( d[u] > 333 ) printf( "%d\n", ans[u] );46 else{47 int sol = 0;48 for( int i = 0; i < g1[u].size(); i++ ){49 sol += val[ g1[u][i] ];50 }51 printf( "%d\n", sol );52 }53 }54 int main(){55 int cas;56 scanf( "%d", &cas );57 while( cas-- ){58 for( int i = 0; i < mnx; i++ ){59 g1[i].clear(), g2[i].clear();60 }61 memset( ans, 0, sizeof(ans) );62 memset( d, 0, sizeof(d) );63 memset( val, 0, sizeof(val) );64 scanf( "%d%d", &n, &m );65 for( int i = 0; i < m; i++ ){66 int u, v;67 scanf( "%d%d", &u, &v );68 g1[u].push_back( v ), g1[v].push_back( u );69 d[u]++, d[v]++;70 }71 init();72 int q;73 scanf( "%d", &q );74 while( q-- ){75 int cmd;76 scanf( "%d", &cmd );77 if( cmd == 0 ){78 upd();79 }80 else cal();81 }82 }83 return 0;84 }

View Code

转载于:https://www.cnblogs.com/LJ-blog/p/3859595.html

你可能感兴趣的文章