CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » namespace » 2020洛谷多校day1
2020-2021:teams:namespace:2020洛谷多校day1

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:namespace:2020洛谷多校day1 [2020/05/11 20:34]
great_designer [样例] 		2020-2021:teams:namespace:2020洛谷多校day1 [2020/05/18 18:07] (当前版本)
great_designer
行 394: 行 394:
 ====题解==== ====题解====
  
-原题题解如下：+我一开始直觉是统计圈的个数（破圈），但后来发现当同时到达顶点的时候，只统计一次爆炸而不是多次，最后只好打算模拟bfs……
  
-在点上爆炸意味着存在至少两个点可以是他最短路上的前驱；在边上爆炸意味着这条边不在最短路里。因此求出最短路即可。 +题解放进了这个页面：[[广度优先搜索_bfs_与标数最短路_dijkstra]]
- +
-边权≤ 9 并不意味着可以使用SPFA。本题的本意是使用O(nw) 的桶排序Dijkstra,​ 但是由于vector实现的桶排Dijkstra 和邻接表+ priority_queue 实现的O(mlogm) Dijkstra 速度在使用输入随机数生成器的方法开大数据后没法拉开差距，因此为了避免卡常数都放了过去。 +
- +
-本题真的不卡常数，测出来时限不宽是因为读入太慢了。 +
- +
-（以上） +
- +
-总之大概的意思是，这东西恰好是最短图标记图后直接算出来。 +
- +
-我们总共有三门课讲到最短路：数据结构、离散II、算法。大概就是把BFS里面的queue换成priority_queue就行了。也就是说，如果所有的边权都为1，priority_queue也可以用queue替代。 +
- +
-（推荐任韩图论，一本跨越了数竞和计竞的高中数竞书） +
- +
-<​del>​然而就是没想到这层。我一开始直觉是统计圈的个数（破圈），但后来发现当同时到达顶点的时候，只统计一次爆炸而不是多次，最后只好打算模拟bfs……</​del>​ +
- +
-去年的水专栏：[[https://​www.bilibili.com/​read/​cv4136755|Dijkstra的板子分析]] +
- +
-<code C++> +
- +
-#​include<​stdio.h>​ +
-#​include<​string.h>​ +
-#​include<​queue>​ +
- +
-using namespace std; +
- +
-struct node +
-{ +
- int to,​next,​val;​ +
-}; +
- +
-struct node e[10000050];​ +
- +
-int head[1000005],​cnt,​n,​m,​K;​ +
- +
-void add(int first,int second,int z) +
-{ +
- e[cnt]=(struct node){second,​head[first],​z};​ +
- head[first]=cnt++;​ +
-} +
- +
-priority_queue<​pair<​int,​int>​ > q; +
- +
-int dis[1000005],​vis[1000005],​ans,​used[1000005];​ +
- +
-void Dijkstra() +
-{ +
- q.push(make_pair(0,​1));​ +
- memset(dis,​0x3f,​sizeof(dis));​ +
- dis[1]=0;​ +
- while(!q.empty()) +
- { +
- int first = q.top().second;​ +
- q.pop();​ +
- if(vis[first]) +
- { +
- continue;​ +
- } +
- vis[first] = 1; +
- int i; +
- for(i=head[first];​i!=-1;​i=e[i].next) +
- { +
- int to1 = e[i].to; +
- if(dis[to1]>​dis[first]+e[i].val) +
- { +
- dis[to1]=dis[first]+e[i].val;​ +
- used[to1]=1;​ +
- q.push(make_pair(-dis[to1],​to1));​ +
- } +
- else if(dis[to1]==dis[first]+e[i].val) +
- { +
- used[to1]++;​ +
- } +
- } +
- } +
-} +
- +
-int main() +
-{ +
- scanf("​%d%d",&​n,&​m);​ +
- memset(head,​-1,​sizeof(head));​ +
- int i,x,y,z;  +
- for(i=1;​i<​=m;​i++) +
- { +
- scanf("​%d%d%d",&​x,&​y,&​z);​ +
- add(x,​y,​z);​ +
- add(y,​x,​z);​ +
- } +
- Dijkstra();​ +
- for(i=1;​i<​=n;​i++) +
- { +
- if(used[i]>​=2) +
- { +
- used[i]--;​ +
- } +
- m-=used[i];​ +
- } +
- printf("​%d\n",​m);​ +
-} +
- +
-</​code>​+
  
 =====C===== =====C=====
行 750: 行 650:
  
 123570404 123570404
 +
 +====题解====
 +
 +本题找到了“逆变换”结论：给定值，判断是第几个。因此最终就是一个二分查找。
 +
 +我想新开一个页面来讲解本题。题解也先放进去了。
 +
 +[[裴蜀定理与一次不定方程]]
 +
  
 =====H===== =====H=====
行 789: 行 698:
  
 8 2 0 0 0 8 2 0 0 0
 +
 +====题解====
 +
 +这个题解就很高端了……
 +
 +采用支持合并的数据结构，下标维护标号，信息维护深度总和与点数，在每个点合并子树信息并维护答案。合并的两端的某个颜色的信息分别为(dep1,​ cnt1), (dep2, cnt2)，当前点深度为d，则合并时产生贡献：
 +
 +$$dep_1cnt_2 + dep_2cnt_1 − 2d \ cnt_1cnt_2$$
 +
 +采用线段树合并等的时间复杂度为O(n log n)，采用启发式合并的set(map) 也能够以O(n log2 n) 的复杂度通过。
 +
 +给了两份代码：
 +
 +<code C++>
 +
 +#​include<​stdio.h>​
 +#​include<​vector>​
 +
 +using namespace std;
 +
 +struct Node
 +{
 + long long dep;
 + int l, r, cnt;
 +}; 
 +
 +struct Node t[201111 * 19];
 +
 +vector <int> E[201111];
 +
 +int n, tcnt;
 +int a[201111], rt[201111], dep[201111];​
 +
 +long long sc[201111], delta;
 +int curdep;
 +
 +int Merge(int x, int y, int l, int r)
 +{
 + if (!y) return x;
 + if (!x) return y;
 + if (l == r)
 + {
 + delta += t[x].dep * t[y].cnt + t[y].dep * t[x].cnt - 2ll * curdep * t[x].cnt * t[y].cnt;
 + t[x].dep += t[y].dep;
 + t[x].cnt += t[y].cnt;
 + }
 + else
 + {
 + int mid = (l + r) / 2;
 + t[x].l = Merge(t[x].l,​ t[y].l, l, mid);
 + t[x].r = Merge(t[x].r,​ t[y].r, mid + 1, r);
 + }
 + return x;
 +}
 +
 +int init(int p, int l, int r)
 +{
 + int x = ++tcnt;
 + if (l < r)
 + {
 + int mid = (l + r) / 2;
 + if (p <= mid) t[x].l = init(p, l, mid);
 + else   t[x].r = init(p, mid + 1, r);
 + }
 + else t[x].dep = curdep, t[x].cnt = 1;
 + return x;
 +}
 +
 +
 +
 +void dfs(int x, int fa)
 +{
 + curdep = dep[x];
 + rt[x] = init(a[x], 1, n);
 + for (auto v : E[x])
 + {
 + if (v != fa)
 + {
 + dep[v] = dep[x] + 1;
 + dfs(v, x);
 + sc[x] += sc[v];
 + delta = 0;
 + curdep = dep[x];
 + rt[x] = Merge(rt[x],​ rt[v], 1, n);
 + sc[x] += delta;
 + }
 + }
 +}
 +
 +int main()
 +{
 + scanf("​%d",​ &n);
 + int i;
 + for(i = 1; i <= n; i++)
 + {
 + scanf("​%d",​ a + i);
 + }
 + for(i = 1; i < n; i++)
 + {
 + int u, v;
 + scanf("​%d%d",​ &u, &v);
 + E[u].push_back(v);​
 + E[v].push_back(u);​
 + }
 + dfs(1, -1);
 + for(i = 1; i <= n; i++)
 + {
 + printf("​%lld ", sc[i]);
 + }
 +}
 +
 +</​code>​
 +
 +<code C++>
 +
 +#​include<​stdio.h>​
 +#​include<​vector>​
 +#​include<​map>​
 +
 +using namespace std;
 +
 +vector <int> E[101111];
 +
 +int n;
 +int a[101111], dep[101111];​
 +
 +map<int, pair<​long long, int> > rt[101111];
 +
 +long long sc[101111], delta;
 +int curdep;
 +
 +void Merge(map<​int,​ pair<​long long, int> >& a, map<int, pair<​long long, int> >& b)
 +{
 + if (a.size() < b.size()) swap(a, b);
 + for (auto& v : b)
 + {
 + int col = v.first;
 + auto it = a.find(col);​
 + if (it != a.end())
 + {
 + long long d1 = it->​second.first,​ c1 = it->​second.second;​
 + long long d2 = v.second.first,​ c2 = v.second.second;​
 + delta += d1 * c2 + d2 * c1 - 2LL* curdep * c1 * c2;
 + it->​second.first += d2;
 + it->​second.second += int(c2);
 + }
 + else
 + {
 + a.insert(v);​
 + }
 + }
 +}
 +
 +void init(map<​int,​ pair<​long long, int>>&​ r, int p)
 +{
 + r[p] = { curdep, 1 };
 +}
 +
 +
 +
 +void dfs(int x, int fa)
 +{
 + curdep = dep[x];
 + init(rt[x],​ a[x]);
 + for (auto v : E[x])
 + {
 + if (v != fa)
 + {
 + dep[v] = dep[x] + 1;
 + dfs(v, x);
 + sc[x] += sc[v];
 + delta = 0;
 + curdep = dep[x];
 + Merge(rt[x],​ rt[v]);
 + sc[x] += delta;
 + }
 + }
 +}
 +
 +int main()
 +{
 + scanf("​%d",​ &n);
 + int i; 
 + for(i = 1; i <= n; i++)
 + {
 + scanf("​%d",​ a + i);
 + }
 + for(i = 1; i < n; i++)
 + {
 + int u, v;
 + scanf("​%d%d",​ &u, &v);
 + E[u].push_back(v);​
 + E[v].push_back(u);​
 + }
 + dfs(1, -1);
 + for(i = 1; i <= n; i++)
 + {
 + printf("​%lld ", sc[i]);
 + }
 +}
 +
 +</​code>​
  
  
2020-2021/teams/namespace/2020洛谷多校day1.1589200467.txt.gz · 最后更改: 2020/05/11 20:34 由 great_designer

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3