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:27]
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=====
行 551: 行 451:
  
 575218836 575218836
 +
 +====题解====
 +
 +这是本套题最难的题目。难点在于细节特别多。
 +
 +原题题解如下：
 +
 +首先考虑p 与k 不互素的情况。这种情况下，整除只与最后一位有关，且有$$\frac{k}{p}-1$$种取法，其余位任取。注意k = p 时答案为[n = 1]，可能会导致部分没有特判的程序挂掉。
 +
 +现在考虑(p,​ k) = 1 的情况。考虑暴力：dpi,​j 表示前i 位和后i 位填好了，其余位取0 时mod p = j的方案数。更新一位的复杂度是O(kp) 的，总复杂度是O(nkp) 的。
 +
 +考虑优化，由费马小定理，ki mod p 存在长度为p − 1 循环节，因此$$k^{i} + k^{n−i−1}\quad mod \ p$$ 也有长度为p − 1 的循环节。按p − 1 分块后，每块的贡献是相同的，而块的背包合并可以通过类似多项式乘法的循环卷积来实现，因此就可以快速幂了。
 +
 +预处理一个块和处理边缘的零散部分的复杂度是O(kp2),​ 一次块的暴力卷积是O(p2) 的，因此总复杂度为O(kp2 + p2(log n − log p))。
 +
 +标程使用vector 实现，不开O2 也只跑了一秒，应该是不卡常的。
 +
 +以上。
 +
 +好。我可以明确地宣布，到“快速幂”之前的部分还是能看懂的。之后就不知道怎么个递推法了。
 +
 +标程代码如下：
 +
 +<code C++>
 +
 +#​include<​iostream>​
 +#​include<​vector>​
 +
 +using namespace std;
 +
 +long long MOD=998244353;​
 +
 +long long power(long long first, long long second, long long z)
 +{
 + long long ret = 1;
 + for(first %= z; second; second >>= 1)
 + {
 + if(second & 1)
 + {
 + ret = ret * first % z;
 + }
 + first = first * first % z;
 + }
 + return ret;
 +}
 +
 +long long n;
 +int p, K;
 +
 +void init(vector <int> & a)
 +{
 + a.clear();
 + a.resize(p);​
 + a[0] = 1;
 +}
 +
 +void upd(vector <int> &a, long long b, int st = 0)
 +{
 + int first;
 + if (b == n - b - 1)
 + {
 + first = int(power(K,​ b, p)) % p;
 + }
 + else
 + {
 + first = int(power(K,​ b, p) + power(K, n - b - 1, p)) % p;
 + }
 + vector <int> c;
 + c.resize(p);​
 + int i;
 + for(i = st; i < K; i++)
 + {
 + int j;
 + for(j = 0; j < p; j++)
 + {
 + (c[(j + i * first) % p] += a[j]) %= MOD;
 + }
 + }
 + swap(a, c);
 +}
 +
 +void mul(vector <int> &a, vector <int> &b)
 +{
 + vector <int> c;
 + c.resize(p);​
 + int i;
 + for(i = 0; i < p; i++)
 + {
 + int j;
 + for(j = 0; j < p; j++)
 + {
 + int first = (i + j) % p;
 + c[first] = int((c[first] + (long long)a[i] * b[j]) % MOD);
 + }
 + }
 + swap(a, c);
 +}
 +
 +void power(vector <int> &a, long long b)
 +{
 + vector <int> ret;
 + init (ret);
 + for(;​b;​b>>​=1)
 + {
 + if(b & 1)
 + {
 + mul(ret, a);
 + }
 + mul(a, a);
 + }
 + swap(a, ret);
 +}
 +
 +vector <int> ans, tr;
 +
 +int main()
 +{
 + scanf("​%lld%d%d",​ &n, &p, &K);
 + if(n == 1)
 + {
 + int aa = 0;
 + int i;
 + for(i = 0; i < K; i++)
 + {
 + if (i % p == 0)
 + {
 + aa ++;
 + }
 + }
 + cout << aa << endl;
 + return 0;
 + }
 + long long sz = n / 2 - 1;
 + if (K % p == 0)
 + {
 + cout << (K / p - 1) * power(K, sz + (n & 1), MOD) % MOD << endl;
 + return 0;
 + }
 + init(ans);
 + init(tr);
 + long long tot = sz / (p - 1); 
 + if(tot)
 + {
 + int i;
 + for(i = 2; i <= p; i++)
 + {
 + upd(tr, i - 1);
 + }
 + power(tr, tot);
 + mul(ans, tr);
 + }
 + upd(ans, 0, 1);
 + long long i;
 + for(i = 2 + tot * (p - 1); i <= (n + 1) / 2; i++)
 + {
 + upd(ans, i - 1);
 + }
 + printf("​%d\n",​ ans[0]);
 +}
 +
 +</​code>​
 +
 +总之这是道值得好好研究的题目。
  
 =====D===== =====D=====
行 587: 行 650:
  
 123570404 123570404
 +
 +====题解====
 +
 +本题找到了“逆变换”结论：给定值，判断是第几个。因此最终就是一个二分查找。
 +
 +我想新开一个页面来讲解本题。题解也先放进去了。
 +
 +[[裴蜀定理与一次不定方程]]
 +
  
 =====H===== =====H=====
行 626: 行 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.1589200022.txt.gz · 最后更改: 2020/05/11 20:27 由 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