作文 题解 令sss为题中的重要串，mmm为sss的长度，显然我们需要维护写出的字符串与sss的匹配。 考虑用 dp\text{dp}dp 来求解该题。令 fif_ifi​ 表示已经匹配到 sss 的第 iii 位时，在结束前匹配整个sss串的概率。由于 sss 在第一次出现以后，就无需考虑后继的情况，那么边界条件就是 fm=1f_m=1fm​=1，答案就是 f0f_0f0​。 考虑状态iii接上句子jjj的转移，设这个后继状态为toi,jto_{i,j}toi,j​： 如果在接上句子jjj的中途就出现了sss串整串，则toi,j=mto_{i,j}=mtoi,j​=m； 否则，令 t...

牛牛选路径 约定：称度数为奇数的点为奇点，称度数为偶数的点为偶点。 贪心策略： 对于每一个连通块，考虑以下两种情况： 如果不存在奇点，则选择点权最小的点作为头尾连接一条路径。 存在奇点，则必然有偶数个奇点，只需要选出这些奇点之间的最优匹配， 而这个最优匹配就是：排序之后不断取最小值和最大值匹配。 证明： 没有奇点时，可以直接提取一条欧拉回路。 存在奇点时，对于任何一个合法的匹配，均存在方案，使得以匹配为头尾的链组，将每条边覆盖奇数次。 下面给出了一个合法的构造： 设匹配点集合为{ui,vi}i=1k\{u_i,v_i\}_{i=1}^k{ui​,vi​}i=1k​，在u...

牛牛玩 generals 题解 操作111：由于每头牛扩展的时候留下的兵是相同的，所以我们用set维护所有兵力相同的区间。 扩展时消耗的兵力就是 (r−l+1)×p+∑别人的兵力−∑自己的兵力(r-l+1)\times p +\sum 别人的兵力-\sum自己的兵力(r−l+1)×p+∑别人的兵力−∑自己的兵力。 直接在 set 中遍历这些区间统计区间和。如果某个区间的一部分在 l∼rl\sim rl∼r 中，将其拆成两段即可。 而每次操作，除了两边的两个区间，中间被包含的区间访问后就会被删去。 每次操作111只额外增加O(1)O(1)O(1)个区间，在整个过程中的区间总数为O(n)O(n...

点权 题解 题解提供两种写法，先讲贪心写法。 这虽然是一个树上的题目，但是在图上它也同样可以写。 因为这实质上是最短路模型。 与一般最短路不同的是，这题一个点要从两个点转移过来。 我们假设iii的答案是从j,kj,kj,k转移过来的，ansians_iansi​为iii号结点点权变为2的答案。 那么有，若iii的度数小于222,则ansi=0ans_i=0ansi​=0,ansi=ansj+ansk+w1+w2ans_i=ans_j+ans_k+w1+w2ansi​=ansj​+ansk​+w1+w2,其中w1,w2w1,w2w1,w2表示对应两条边的边权。 由于边权非负，那么我们有ansi&...

斗地主 题解 ​ 由于这一回合选什么牌对之后回合选牌并没有影响，所以我们可以考虑使用 dp\text{dp}dp来解决问题。 ​ 我们设计这么一种状态 fi,jf_{i,j}fi,j​ 表示前 iii 回合，选的牌分值是 jjj 的方案数。 ​ 那么枚举这一回合的牌，dp\text{dp}dp转移式就是： fi,j=∑x=1mfi−1,(j−ax)mod  kf_{i,j}=\sum_{x=1}^{m}{f_{i-1,(j-a_x)\mod k}}fi,j​=x=1∑m​fi−1,(j−ax​)modk​ ​ 关于答案的统计，我们发现 kkk 的值域很小，所以暴力统计的复杂度为O(nmk)O...

根据题目意思模拟，取掏手机打开健康码和排队的时间的较大值。 最终答案为 max⁡(x×y,a+b)+c\max(x\times y,a+b)+cmax(x×y,a+b)+c。 #include<bits/stdc++.h> using namespace std; #define ll long long int t; void solve(){ ll x,y,a,b,c; scanf("%lld%lld%lld%lld%lld",&x,&y,&a,&b,&c); printf("%lld\n",max(x*y,a+b)+c); } i...

这题目也太好出了吧,牛客还缺出题人吗

T3数据什么东西呀!!!!!这数据强度,搞的我一个老实人直接垫底了