2022-2023:teams:loaf_on_contest:front_page:st2

差别

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

到此差别页面的链接

--- 2022-2023:teams:loaf_on_contest:front_page:st2 [2022/08/28 14:19]
toby-shi
+++ 2022-2023:teams:loaf_on_contest:front_page:st2 [2022/08/31 22:08] (当前版本)
yuki
@@ 行 2: / 行 2: @@
 =====D=====
+ n 位长的十进制数字，在其中可以任意插入分割线，分割后，要使每一段不为空，并且可以整除 m ，合法分割的方案数.
+若A,B都能被m整除，则AB=A*100...+B一定能被m整除.
+求有多少个前缀能恰好被m整除. 若有m个(不包括末尾)，结果就是 2^m. (相当于枚举每个位置分割or不分割).
 =====A=====
 签到题。就是只需要将点阵换为数，数换为点阵即可。完完全全是模拟。没什么好说的。
 =====K=====
+有两个队的骑士1到n和n+1到2n，每个骑士只能互相攻击对手队的一个骑士。kernel的意思是在这个kernel里的骑士不会互相攻击，在kernel外的骑士被kernel里的骑士攻击。
+现在告诉你所有骑士攻击的骑士，求一个kernel。
+没人攻击的骑士一定在kernel里，把没人攻击的加入队列，然后被他攻击的骑士一定在kernel外。
+kernel外的骑士的攻击无效，因为如果一个骑士如果只被外面的骑士攻击，他就是kernel里的。
+于是 被 外面的骑士攻击 的骑士 的被攻击次数 -1，如果被攻击次数为0了就加入队列。
+WA是由于一些愚蠢的手误呜呜~，RE是因为数组大小没有乘2
 =====B=====
+一个非常简单的暴力签到题，T掉的原因是没有使用输出优化QAQ
 =====F=====
+又是奇妙的数学题。
+题意是一个二元函数。递推式是$F[i,j]=a*F[i,j-1]+b*F[i-1,j]+c$，递推边界是$F[k,1]=l_k$和$F[1,k]=t_k$。\\
+给定$\{l_k\},\{t_k\},a,b,c$以及一个正整数$n(2\le n\le 200000)$，求$F[n,n]$。
+这个题经过简单的递推迭代之后，可以轻松的得出$l_k,t_k$前的系数，但是常数项却很难得出。$l_k,t_k$前的系数分别是（$\forall k(2 \le k \le n-1)$）：
+$$
+C_{2n-k-2}^{n-k}a^{n-1}b^{n-k},\\
+C_{2n-k-2}^{n-k}b^{n-1}a^{n-k}
+$$
+$k=1$时系数为0，$当k=n时$，上面公式中$2n-k-2$改成$n-1$。
+而c的系数比较复杂，前半段是$(a+b)$的某个次幂，后半段则是可以整体递推的，具体结果有点复杂就不写了，贴一个[[https://codeforces.com/group/UitskjLDCx/contest/393097/submission/166884391|代码]]吧
 =====J=====
+你被雇佣升级一个旧果汁加工厂的橙汁运输系统。系统有管道和节点构成。每条管道都是双向的，且每条管道的流量都是1升每秒。管道可能连接节点，每个节点最多可以连接3条管道。节点的流量是无限的。节点用整数1到n来表示。在升级系统之前，你需要对现有系统进行分析。对于两个不同节点s和t，s-t的流量被定义为：当s为源点，t为汇点，从s能流向t的最大流量。以下面的第一组样例数据为例，1-6的流量为3，1-2的流量为2。计算每一对满足a<b的节点a-b的流量的和。
+答案显然只有0 1 2 3
+:分别处理联通块
+:同个联通块的不同边双
+和3: 考虑依次删掉每一条边，再求边双，如果两个点不论删除哪一条边，都一直在同一个边双联通分量里，那么流量就为3，否则为2
+每次把边双联通分量的id hash起来就可以了。
 =====E=====

2022-2023/teams/loaf_on_contest/front_page/st2.1661667554.txt.gz · 最后更改: 2022/08/28 14:19 由 toby-shi