如题。 我们发现，F 题的数据对 时的判断有误，std 的答案似乎为 ，但根据题意，答案应为 。 请问 F 题是否会会修改数据并重测？

Update on 2022.10.22： 出题人已经修改数据并重测了。 Update on 2022.10.21： 实践检验表明数据确实锅了，对 k=1k=1k=1 的数据请输出 000！ 完蛋了交了 101101101 发要被封号了。 不管了，先胡一下这个过不去的做法，供后人观赏。 倒开人表示很亏啊，被这题浪费了这么久…… 如果正解是什么高明稳定正确做法当我没说。 考虑 hash。 我们把每个数往 [0,264)[0,2^{64})[0,264) 上做随机映射，取和自然溢出。 然后，淀粉质维护信息，直接用 map 更新答案。 这个复杂度是 O(n2n)O(n\log^2n)O(nlo...

大家好这里是赛时调不出代码的小丑 myee。 这里我给出 T4 一个理论线性但肯定没人会去写的垃圾做法。 当然，如果你懒了，可以和我一样带只 log⁡\loglog，反正也能过。 首先容斥，贡献为 ∑l=1n∑r=l+1n[f(l,r)=al∨f(l,r)=ar]l≤i≤rai=∑l=1n∑r=l+1n[f(l,r)=al]l≤i≤rai+∑l=1n∑r=l+1n[f(l,r)=ar]l≤i≤rai−∑l=1n∑r=l+1n[f(l,r)=al=ar]l≤i≤rai\sum_{l=1}^n\sum_{r=l+1}^n[f(l,r)=a_l\lor f(l,r)=a_r]\max_{l\le i...

大家都知道 KMPAM 吧？ 对这题，考虑一个 dp 套 dp。 内层为你目前在 KMP 自动机上的位置，外层为到当前点已经匹配了多少个。 顺着 KMPAM 转移边的方向转移即可。 p.s. KMPAM 就是 KMP 匹配的过程写成自动机的形式，使得可以 O(1)O(1)O(1) 转移。 上代码~ // KMPAM // wa 了 qwq #include <algorithm> #include <stdio.h> #include <vector> typedef long long llt; typedef unsigned uint;typedef...

放一个常数巨大不能通过的做法。 首先子序列信息显然可以动态 dp。 然后有插入操作，于是显然得用平衡树来维护区间信息。 打的 WBLT，然后结果实测不加平衡措施还更快？？？（除掉 S=0 外，均有数据随机） struct Info{ullt O,R,Z,OR,RZ,ORZ;__always_inline friend Info operator+(Info a,Info b){return Info{a.O+b.O,a.R+b.R,a.Z+b.Z,a.OR+b.OR+a.O*b.R,a.RZ+b.RZ+a.R*b.Z,a.ORZ+b.ORZ+a.O*b.RZ+a.OR*b.Z};}}; str...

为啥 G 题 MTT 能跑 呀。 牛客机子为！什！么！这！么！快！ 是我的一直以来的观念错了吗......

预处理枚举答案位置，然后用卷积得到询问答案。 ∑ifi(xi)(m−xn−i)=∑ifix!(m−x)!i!(n−i)!(x−i)!(m−x−n+i)!=x!(m−x)!∑ifii!(n−i)!(x−i)!(m−x−n+i)!=x!(m−x)!∑ifii!(n−i)!1(x−i)!(m−x−n+i)!\sum_if_i\binom xi\binom{m-x}{n-i} \\=\sum_if_i{x!(m-x)!\over i!(n-i)!(x-i)!(m-x-n+i)!} \\=x!(m-x)!\sum_i{f_i\over i!(n-i)!(x-i)!(m-x-n+i)!} \\={x!(m...

LCT 板子，不多说了。 复杂度是可以均摊的。 typedef std::pair<ullt,uint>Pair; struct LCT { struct node { Pair val,max;node*son[2],*fath;bol tag; node(Pair v=Pair()):val(v),max(v),fath(NULL),tag(false){son[0]=son[1]=NULL;} voi pushup() { pushdown(); m...

一个结论是一段区间可行当且仅当其总石子个数是偶数且最多者不超过总数一半。 笛卡尔树上启发式合并即可。 （听说数据水，乱搞也能过。） // 笛卡尔树毁我青春 // 隐式构建.jpg ullt S[100005]; uint Cnt[2][100005]; uint A[100005]; struct Seg { uint len;uint v;Seg*L,*R; Seg(uint*Bgn,uint*End):L(NULL),R(NULL){if((len=End-Bgn)>1)L=new Seg(Bgn,Bgn+(len>>1)),R=new Seg(Bgn+(...

直接树形 dp，记录当根节点颜色假如已经被确定时的两种方案对应方案数即可。 std::vector<uint>Way[1000005]; modint x,y; modint Kind[1000005][2]; voi dfs(uint p,uint f) { Kind[p][0]=Kind[p][1]=1; for(uint s:Way[p])if(s!=f) { dfs(s,p); Kind[p][0]*=Kind[s][0]*x+Kind[s][1]*y; Kind[p][1]*=Kind[s][0]*x...

反悔贪心即可。 llt A[100005],P[100005];uint Op[100005]; int main() { uint n,m;scanf("%u%u",&n,&m); for(uint i=0;i<n;i++)scanf("%lld",A+i),_max(A[i],0ll); for(uint i=0;i<n;i++)scanf("%lld",P+i); for(uint i=0;i<n;i++)scanf("%u",Op+i); llt ans=0; for(uint op=0;op<=1...

对于一个 lll，显然和它对应有贡献的 rrr 必定满足 albitor⁡al+1bitor⁡...bitor⁡ar−1<albitor⁡al+1bitor⁡...bitor⁡ara_l\operatorname{bitor}a_{l+1}\operatorname{bitor}...\operatorname{bitor}a_{r-1}<a_l\operatorname{bitor}a_{l+1}\operatorname{bitor}...\operatorname{bitor}a_ral​bitoral+1​bitor...bitorar−1​<al​bitoral+1...

直接分奇偶贪心排序，然后判断即可。 uint A[105]; std::vector<uint>V[2],P[2]; int main() { uint n;scanf("%u",&n); for(uint i=0;i<n;i++) { uint v;scanf("%u",&v); V[v&1].push_back(v),P[v&1].push_back(i); } std::sort(V[0].begin(),V[0].end()); std::sort(V[1]...

前言 打得不错？ 你发现这 777 题基本上全是套路题，所以并不很困难。 下面是口胡题解。 代码分开到了 777 篇题解。 思路 A 直接分奇偶贪心排序，然后判断即可。 B 对于一个 lll，显然和它对应有贡献的 rrr 必定满足 albitor⁡al+1bitor⁡...bitor⁡ar−1<albitor⁡al+1bitor⁡...bitor⁡ara_l\operatorname{bitor}a_{l+1}\operatorname{bitor}...\operatorname{bitor}a_{r-1}<a_l\operatorname{bitor}a_{l+1}\oper...