多校A层冲刺NOIP2024模拟赛24\(T1\)A.选取字符串\(100pts\)考虑建出失配树，然后等价于询问\(\sum\limits_{S\sube\{0,1,2,\dots,n\},|S|=k}dep_{\operatorname{LCA}\{S\}}^{2}\)。不妨从\(\operatorname{LCA}\)的角度考虑，统计\(x\)能作为多少个\(|S|\)

NOIP2024加赛5题目来源：2023NOIPA层联测31\(T1\)HZTG5777.暴力操作（opt）\(40pts\)先将\(\{a\}\)升序排序。因为\(\left\lfloor\dfrac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor=\left\lfloor\dfrac{a}{bc}\right\rfloor\)，先钦定\(

NOIP2024（欢乐）加赛3\(T1\)CF2033BSakurakoandWater\(100pts\)枚举主对角线取\(\max\)即可。点击查看代码lla[510][510];intmain(){ llt,n,ans=0,maxx,i,j,k,h; cin>>t; for(h=1;h<=t;h++) { cin>>n; ans=0; for(i=1;i<=n;i++) { for(

P4381[IOI2008]Island由于每个点只能向外连一条边，\(n\)个点\(n\)条边，中间有环，故不能再向外连边，所以构成基环内向树森林。叶子节点入度为\(0\)，故可以判断叶子结点，倒推回环根，存每个子树的最大深度。最终dp处理每个基环树的环，分两种情况：经过环：分两种情况：顺时针和逆时针，

购物（buy）1#include<bits/stdc++.h>2usingnamespacestd;3intn,m,w;4inta[200010];5intmain(){6cin>>n>>m>>w;7for(inti=1;i<=n;i++)cin>>a[i];8sort(a+1,a+1+n,greater<int>());9

多校A层冲刺NOIP2024模拟赛12\(T1\)A.Alice和璀璨花\(65pts/65pts/65pts\)部分分测试点\(1\sim10\)：设\(f_{i,j}\)表示前\(i\)位中生长趋势子序列长度为\(j\)时的末尾最小元素，然后进行暴力转移。测试点\(11\sim13\)：观察到至多选择\(\left\lceil\log_

题解#include<bits/stdc++.h>usingnamespacestd;structedge{ intto,nxt;}e[1000010<<1];intn,cnt,id;inthead[1000010];longlongans;longlongf[1000010],dep[1000010],size[1000010];inlinevoidadd(intu,intv){ e[++cnt].nxt=head[u];

首先，这题最好的一个地方，在于它给出的关于next的讲解实在是妙极!!!!!这题比我讲的好100倍！赞美lg捧lg的话到此为止，进入正文题解#include<bits/stdc++.h>usingnamespacestd;constlonglongMOD=1e9+7;intn,fail[1000010],ans[1000010];longlongcnt;chara[1000010];

多校A层冲刺NOIP2024模拟赛05\(T1\)A.好数（number）\(100pts/100pts\)枚举两数之和，开个桶维护即可。点击查看代码inta[5010];unordered_map<int,bool>s;intmain(){ freopen("number.in","r",stdin); freopen("number.out","w",stdout)

题解QOJ1869【PowerStationofArt】/SS241006B【结论题】PetrozavodskSummer2021.Day6.XJTUContest,GPofXJTUXXIIOpenCupnamedafterE.V.Pankratiev,GrandPrixofXi'an题目描述给出一个无向图，每个点有点权\(a\)和颜色\(c\)，其中颜色只会有红蓝两种。

Description给定一个长为\(n\)的序列\(a_{1\dotsn}\)，需要对它进行两种操作共\(n-1\)次。对一个长度为\(l\)的序列\(b_{1\dotsl}\)进行一次操作将会把序列变为一个长为\(l-1\)的序列\(c_{1\dotsl-1}\)：操作一中，\(\foralli\in[1,l),c_i=\max(b_i,b_{i+1})\)；操作

题目传送门前置知识AC自动机|树状数组解法一次性将所有模式串加入AC自动机，然后处理加入和删除，考虑单次操作对答案的贡献。因为模式串\(T\)在文本串\(S\)中出现的次数之和等价于\(T\)在\(S\)的所有前缀中作为后缀出现的次数之和。这就很和\(fail\)树上跳到根节

前言题目链接：洛谷。在上一题之后，模拟赛又放了一道KMP重定义相等的问题，但是寄了，故再记之。题意简述现在给出\(1\simn\)的排列\(p\)和序列\(h_1,h_2,\cdots,h_m\)​​，请你求出哪些\(h\)的子串符合排列\(p\)。串\(a_i\)符合一个排列被定义为其从小到大排序后得

题目传送门前置知识Tarjan算法|最短路解法缩点后原图就成为了一个有向无环图，此时每个点最多被经过一次，故在求最长路的过程中可以将点权和边权混着转移。上篇题解用拓扑实现查找两点间最长路的做法正确性不会证，遂写了份Dijkstra求最长路。代码#include<bits/stdc++.h

多组测试数据，每组测试数据给你一个正整数\(n\)，让你求满足\(\gcd(i,j)=1\)并且\(1\lei<j\len\)的数对个数。随便想一想，得出一个递推式：\(F_n=F_{n-1}+\varphi(n)\)。证明很简单：\(F_n\)是包含\(F_{n-1}\)的，多出来的部分就是小于\(n\)并且和\(n\)互质的数的个

题目链接戳这Solution因为n很小所以可以n方枚举左右端点，然后实际上就是判断前面一半将69交换后是否是个回文且这个回文不存在反转后没意义的数，对于那几个翻转后没意义的数字随便用字母代替即可，对于前缀和后缀分别哈希然后判断是否相等即可。#include<bits/stdc++.h>#defin

题意简化求一种分配方案：最大化队伍总数；在满足1的情况下最小化最多人的队伍人数。题目思路由于本题目的数据量高达\(10^6\)，且贪心算法也许不成立，所以需要考虑\(n\logn\)的算法！具体的，对于一个人的需求\(a_i\)，如果小于\(a_i\)的数先被选走，那么\(a_i\)可能问题：不

记录23:402024-2-51.字符串hash将字符串转换为hash值。以p=131/13331，将字符串看成P进制数，取一固定值M，求出该P进制数对M的余数，作为该字符的hash值。可以取M=\(2^{64}\)用unsignedlonglong存储这个hash值，这样不用取模，因为如果溢出了就相当于对\(2^{64}\)取模了除了在

分析坑点：（你需要覆盖整个区间，而非只覆盖整数点，例如\(n=3\)，\([0,1],[2,3]\)是不够的。）翻译没把这个写上去，搞得我思考了很久样例。看到这个之后，题目可以转化为每个灯可以覆盖\([x,x+l)\)，你需要覆盖区间\([0,n)\)中的整数点。如果没有障碍物，我们直接枚举每个灯放哪，复杂度\(O

题目要求：给定一个数n，求1—n之间有多少对互质的数，phi【i】数组表示i之前有多少个和i互质的数，a【i】表示前phi【1】+phi【2】+……+phi【i】；a【n】数组就是1---n之间互质的数的对数。。#include<stdio.h>#include<string.h>longlonga[1000010],phi[1000010];longlongn,i,j;i

D.MatrixCascade题目描述：有一个大小为\(n\timesn\)的矩阵，由0和1组成。行的编号从上到下依次为\(1\)到\(n\)，列的编号从左到右依次为\(1\)到\(n\)。第\(x\)行与第\(y\)列交叉处的单元格记为\((x,y)\)。水月想把矩阵的所有元素都变成0。她可以一步完成以下操作：选择任意

题目描述输入输出样例输入abaabaa样例输出17样例解释：f[2][a]=1f[3][a]=1f[4][a]=1f[4][b]=2f[5][a]=1f[5][b]=2f[6][a]=3f[7][a]=4f[7][b]=2以上为>0的f[][]，求和=17数据范围限制这一篇同上一篇，都是从以前博客搬过来的，所以真的是

没有模的版本constintN=1000010;constintm=131;constintmod=1e9+7;intn,T;chars[N];intf[N],p[N];intmain(){ scanf("%s",s+1);n=strlen(s+1); p[0]=1; for(inti=1;i<=n;i++){ f[i]=f[i-1]*m

传送门题意是给你个数字序列，现在让你把这个序列分成m个连续的子序列，且要求这m个子序列的累加和最大。思路：这道题的题意可以理解为问在序列为末尾时，把序列分为m个子序列这个状态时的最大累加和，那么可以得出这个状态应该是由上一个状态转移得来：（因为dp[i][j]表示数到第j个字符时，前j个

题面题意：给出字符串s和t，每次操作将s中出现的第一个t删去，直到不能删为止。求最后的串。|s|<=1e6题解：hash做法。（此题也有kmp和权值线段树做法）因为涉及到删除操作，所以我们要动态的实现这个过程。所以考虑开一个栈来存储当前留下的字符。然后每有一个字符入栈，就拿当前