daicon

分类

题解(9)

/ 注册

全部文章（共9篇）

2020牛客暑期多校训练营（第一场）J. Easy Integration

oeis的并不会证答案为补：欧拉积分，最后即可得到上式

微积分数学

2020-09-19

1 414

2020牛客暑期多校训练营（第一场）I. 1 or 2

题解我们考虑匹配问题，每条边会关联两个点，那么肯定是点和边有关联；每个点需要减的度数是，因此每个点拆成个点，然后每条边拆成两个点和，连完边之后这就是一个二分图，跑完图匹配之后必定还有某些边没有匹配上（因为每一个拆出来的点都会连条边，最大的情况也不过是全部都匹配上）；但是我们对于边拆出来的点也有限制...

二分图图论网络流

2020-09-19

0 463

2020牛客暑期多校训练营（第一场）H. Minimum-cost Flow

题解由于所有边的容量相同，所以可以得到一个性质，的流量在图中形成了k条1-n的路径，每多u的流量多形成一条路径（可能会导致原路径改变，但是只会在到时发生改变），这u的流量所用的花费是相同的，所以考虑u和v的倍数关系，预处理出u为1，v从1到100的花费，然后询问时直接求出对应的花费代码 #inc...

图论网络流

2020-09-19

0 457

2020牛客暑期多校训练营（第一场）G. BaXianGuoHai, GeXianShenTong

题解可以证明该三元组满***换律和结合律，同时单位元为(1,0,0),满足快速幂，但是幂次可以达到存不下，使用JAVA或者PYTHON大数也显然会T，然后选择将幂次对进行取模（别问我为什么，我也不知道），然后就好做了。###代码 #include <bits/stdc++.h> usi...

树模拟数学

2020-09-19

0 522

2020牛客暑期多校训练营（第一场）F. Infinite String Comparision

题解做法令两循环节分别为。模拟题意，比较两字符串直到第个字符为止。证明以下记号不区分串和串长首先给出 Periodicity Lemma：假设一个字符串有循环节（不需要是完整循环节）和，并且满足，那么也是一个循环节。证明见张晴川知乎专栏叉姐给出了一个数论证...

字符串数论

2020-09-19

1 589

2020牛客暑期多校训练营（第一场）E. Counting Spanning Trees

答案为：代码 #include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(auto i=(a);i<=(b);++i) #define dep(i,a,b) for(auto i=(a);i>=(...

论文题数学矩阵树定理

2020-09-19

0 419

2020牛客暑期多校训练营（第一场）D. Domino

考虑使用拉格朗日乘数法$$求偏导可得代入运算可得代码 #include <bits/stdc++.h> using namespace std; #define paii pair<int,int> #define fr first #define sc second ...

拉格朗日乘数法数学

2020-09-19

0 485

2020牛客暑期多校训练营（第一场）B. Infinite Tree

题解可以认为u是，同时是递减的，即为从根1走到后再走到，那么考虑枚举质数和每种质数的个数，考虑走到某个地方能否使得答案是减少的，可以确定该答案是一个区间，在不断缩小后即可以得到答案代码 #include <bits/stdc++.h> using namespace std; #de...

树数论

2020-09-19

0 420

2020牛客暑期多校训练营（第一场）A. B-Suffix Array

做法对于字符串的第个字符，定义对偶函数，其含义为：对于原串的第个字符，找到它之后与它相同的字符位置，结果的第个元素即为。如果不存在这样的字符，相应的结果为。就像题中的函数，一个字符串的函数就是由每个位置的组成。定义上的小于关系为字典序从大到小，并且前缀优先。举例...

论文题字符串后缀数组 SA

2020-09-19

0 454