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/10 23:53]
great_designer [题面] 		2020-2021:teams:namespace:2020洛谷多校day1 [2020/05/18 18:07] (当前版本)
great_designer
行 47: 行 47:
  
 输出：到有1 000 000 000块钱的时候的日期 输出：到有1 000 000 000块钱的时候的日期
 +
 +====样例====
 +
 +输入
 +
 +2
 +
 +999999999 2020 2 29
 +
 +114514 1919 8 10
 +
 +输出
 +
 +2020 3 1
 +
 +2042 1 15
  
 ====解答==== ====解答====
行 209: 行 225:
  
 如果有多个答案，请打印任何答案。 如果有多个答案，请打印任何答案。
 +
 +====样例====
 +
 +输入
 +
 +4
 +
 +输出
 +
 +2 2
 +
 +输入
 +
 +6
 +
 +输出
 +
 +3 3
 +
 +输入
 +
 +8
 +
 +输出
 +
 +3 5
 +
 +第三个输出5 3也是正确的。
  
 ====解答==== ====解答====
行 295: 行 339:
  
 </​code>​ </​code>​
- 
-以下四题是未AC的题目。接下来几天看看题解。（待施工） 
  
 =====A===== =====A=====
行 349: 行 391:
  
 2 2
 +
 +====题解====
 +
 +我一开始直觉是统计圈的个数（破圈），但后来发现当同时到达顶点的时候，只统计一次爆炸而不是多次，最后只好打算模拟bfs……
 +
 +题解放进了这个页面：[[广度优先搜索_bfs_与标数最短路_dijkstra]]
  
 =====C===== =====C=====
行 369: 行 417:
  
 输出应答模块998244353。 输出应答模块998244353。
 +
 +====样例====
 +
 +输入
 +
 +1 2 10
 +
 +输出
 +
 +5
 +
 +输入
 +
 +2 7 16
 +
 +输出
 +
 +2
 +
 +输入
 +
 +16 7 10
 +
 +输出
 +
 +12866400
 +
 +输入
 +
 +16 7 16
 +
 +输出
 +
 +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=====
行 389: 行 634:
  
 对于每个测试用例，在单独的一行上打印一个表示第K个最小不公平价格的整数。 对于每个测试用例，在单独的一行上打印一个表示第K个最小不公平价格的整数。
 +
 +====样例====
 +
 +输入
 +
 +2
 +
 +2 3 1
 +
 +314159 233333 123456789
 +
 +输出
 +
 +1
 +
 +123570404
 +
 +====题解====
 +
 +本题找到了“逆变换”结论：给定值，判断是第几个。因此最终就是一个二分查找。
 +
 +我想新开一个页面来讲解本题。题解也先放进去了。
 +
 +[[裴蜀定理与一次不定方程]]
 +
  
 =====H===== =====H=====
行 409: 行 679:
 输出n行，在第i行打印一个整数，表示子树i的危险分数。 输出n行，在第i行打印一个整数，表示子树i的危险分数。
  
 +====样例====
  
 +输入
 +
 +5
 +
 +1 2 1 1 2
 +
 +1 2
 +
 +2 3
 +
 +2 4
 +
 +5 1
 +
 +输出
 +
 +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.1589126010.txt.gz · 最后更改: 2020/05/10 23:53 由 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