T1 儒略日 分为两种情况。 在1582年10月4日以前 每4年有一个闰年，我们先确定在答案前4年内的某一年（的1月1日），然后一年一年增加，再一月一月增加，再一日一日增加。 我们可以把公元前x年当作公园-x+1年。 在1582年10月15日以后 每400年有97个闰年，就确定答案前400年的某一年（的1月1日），跟上面一样这么干就OK了。 代码 #include<bits/stdc++.h> using namespace std; #define open(s) freopen( s".in", "r", stdin ), fre...

简单地说，AC自动机就是可以匹配好多字符串的东西。。。。其实就是在Trie树上做KMP。fail[i]表示的是i节点代表的串的意义就是在Trie上出现过的最长后缀（当然不包括自己）所在的节点。如果暴力找fail[i]的话会超级慢，所以我们可以把值为0的tr[i][j]赋为tr[fail[i]][j]。注意要按BFS序求fail[i]，因为dep[i]>dep[fail[i]]。然后就可以快乐地匹配啦！TJOI2013 单词 #include<bits/stdc++.h> using namespace std; #define fp(i, b, e) for ( int i ...

#牛客守护神#

#2020对我好一点# 希望明年节操社不要把炮姐做崩😣

思路 题目又臭又长,其实没有什么卵用....真正有用的只有那个式子.根据乘法原理,我们可以转换成这样: 于是设计状态 表示当前进行到 场,有 场 为 ,有 场 为 .因为 都是 级别的,所以总复杂度为 .最终结果可能会很大,最好不要用 double,用 long double,或者利用 来求.因为最终结果也要求取 ,于是用后一种就OK了. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define f80 long double #define rgt re...

好多省选题似乎都没有数据范围.... 像下面两题.... https://ac.nowcoder.com/acm/problem/20575 https://ac.nowcoder.com/acm/problem/20589

思路 首先,我们可以忽略平局的情况.因为如果我们过滤掉平局的情况,最终结果仍然不变. 我们记Alice赢的概率为 ,输的概率为 , 当Alice手头有 颗糖果时,最终获胜的概率是 . 然后我们就可以列出转移方程: 很明显这玩意不能直接转移,如果 比较小的时候我们可以高斯消元解方程,但是这题数据范围是,用高斯消元会. 于是我们手动解方程.(滑稽 把每一个表示成的形式. ,因此. 于是我们就可以 推出所有的 了. 因为 ,我们可以倒推出所有的 . 最终答案就是 .注意特判 的情况. 代码 #include<bits/stdc++.h> using namespace...

思路 首先,期望是线性的. 于是我们可以求出连接每一个农村所需长度的期望,然后全部加起来就OK了. 记 表示第 个城市, 表示第 个农村, 表示 与 相连的概率, 表示 与 的距离. 那么 现在我们依次处理每一个农村 . 先考虑城市的贡献.很明显只有离最近的城市才会有贡献. 对于与它最近的城市 ,如果更近的农村有个(不包括),那么与连接的概率为. 至于为什么,可以考虑所有农村的全排列(即连接的顺序),考虑其中更近的 个农村与 的相对位置,肯定是 在最前面,后面 个农村怎么排就没有关系了. 排在第 个,第 个...第 个的概率是相等的,因此排在最前面的概率就...

#1024# 手拿两把锟斤拷 口中直呼烫烫烫

#1024# 坐标浙江义乌 我 自 闭 了

#1024# 许愿CSP一等奖

初赛见祖宗qwq 在ZJ表示虚得一批

Day 0 能出去玩了好兴奋啊大家好我是还在学校学习文化课の菜鸡louhc qwq回想起来16年太菜了虽然有初赛一等,但是不能去复赛,17年撑过了初赛却跪在了复赛(那时候不怎么会搜索,不怎么会单调队列,差几分没有省一哭惹,不像Venus这么强初二拿省一).PJ省一在我们这边有特殊的意义.(Venus,xiaomin,hovny,ydk...应该懂的 笑)今年DX还有两个同志和我一起去复赛,还是比较exciting的.不过最恶心的就是回来还要月考ToT.自闭自闭. Day 1 本来以为上午能颓废一下的,结果到的时候已经差不多中午了(似乎去年也是这么认为的?).YW的占了一个看起来像是会议室的地方...

思路 比较套路的一道数位DP题.按照套路转换成前缀和.先预处理出表示第位为,位为,位及之前不需要考虑(可以看做全是)满足条件的数的个数.我们枚举位到最高位与相同,位小于的答案.发现不满足条件记得及时退出.最后答案别忘+1.复杂度为. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) for ( int i(b), I(e); i ...