搜索结果
查询Tags标签： ybtoj，共有 14条记录-
YbtOJ 「基础算法」第3章 二分算法
例题1.数列分段 二分每段和的最大值。check 时从左往右扫，如果当前段的和大于限制则新开一段。code #include<bits/stdc++.h> using namespace std; const int N=1e5+5; int n,m,a[N]; int maxn,s; int check(int x) {int cnt=1,sum=0;for(int i=1;i<=n;i++){if…
2022/8/15 1:55:03 人评论 次浏览 -
YbtOJ 递推算法 做题记录
例题 1 错排问题 \(f_i\) 表示前 \(i\) 个数的错排。易得递推式为 \(f_i=(i-1)\times(f_{i-1}+f_{i-2})\)。code #include<bits/stdc++.h> #define int long longusing namespace std; int n,f[25]; signed main() {scanf("%lld",&n);f[1]=0,f[2]=1;f…
2022/8/13 14:25:25 人评论 次浏览 -
CF700E Cool Slogans / YbtOJ「字符串算法」第3章 后缀自动机 G. 重复子串 题解--zhengjun
题目大意 选出一个字符串序列 \(s\)，使得对于每一个 \(s_i\)，都是原串的子串，且每个 \(s_i\) 在 \(s_{i-1}\) 中都出现过至少两次，求最大的序列长度。 思路 发现其实可以做到让所有选出的字符串都是上一个字符串的后缀，因为如果后面留了一个尾巴，那么前面的字符串把…
2022/6/12 1:20:13 人评论 次浏览 -
「YbtOJ」递推算法
划分数列 题目地址 Solution 考虑递推。 设\(f_i\)表示\(a_1\sim a_i\)的最少划分段数，\(p_i\)代表以\(i\)结尾单调不降的一段的起点，\(q_i\)则表示以\(i\)结尾单调不升的一段的起点，注意：起点代表这一段第一个数的前一个坐标。 我们可以得到以下转移方程： \[\large …
2021/8/4 22:09:50 人评论 次浏览 -
「YbtOJ」递推算法
划分数列 题目地址 Solution 考虑递推。 设\(f_i\)表示\(a_1\sim a_i\)的最少划分段数，\(p_i\)代表以\(i\)结尾单调不降的一段的起点，\(q_i\)则表示以\(i\)结尾单调不升的一段的起点，注意：起点代表这一段第一个数的前一个坐标。 我们可以得到以下转移方程： \[\large …
2021/8/4 22:09:50 人评论 次浏览 -
【YBTOJ】【国家集训队】彩色圆环
彩色圆环： 题目大意： 一个环上有 \(n\) 个点，每个点随机染为 \(m\) 种颜色之一。求环上同色连续段长度之积的期望值。 思路： 破环为链，就有 \(f_{i,[0,1]}\) 表示到第 \(i\) 个数，环首尾是否同种颜色的期望值。则有： \[\begin{aligned} f_{i,1}&=\sum_{j=0}^{i…
2021/7/15 23:18:01 人评论 次浏览 -
【YBTOJ】【国家集训队】彩色圆环
彩色圆环： 题目大意： 一个环上有 \(n\) 个点，每个点随机染为 \(m\) 种颜色之一。求环上同色连续段长度之积的期望值。 思路： 破环为链，就有 \(f_{i,[0,1]}\) 表示到第 \(i\) 个数，环首尾是否同种颜色的期望值。则有： \[\begin{aligned} f_{i,1}&=\sum_{j=0}^{i…
2021/7/15 23:18:01 人评论 次浏览 -
【YBTOJ】【Luogu P6218】[USACO06NOV] Round Numbers S
【YBTOJ】【Luogu P6218】[USACO06NOV] Round Numbers S 链接： 洛谷 题目大意： 在 \([l,r]\) 中找到二进制中零数大于等于一数的数的个数。 正文： 数位 DP 板子题。设 \(f_{len,A,B,pos}\) 表示当前 \(len\) 位 \(A\) 个零、\(B\) 个一，碰没碰顶的方案数。 代码： con…
2021/7/11 23:17:38 人评论 次浏览 -
【YBTOJ】【Luogu P6218】[USACO06NOV] Round Numbers S
【YBTOJ】【Luogu P6218】[USACO06NOV] Round Numbers S 链接： 洛谷 题目大意： 在 \([l,r]\) 中找到二进制中零数大于等于一数的数的个数。 正文： 数位 DP 板子题。设 \(f_{len,A,B,pos}\) 表示当前 \(len\) 位 \(A\) 个零、\(B\) 个一，碰没碰顶的方案数。 代码： con…
2021/7/11 23:17:38 人评论 次浏览 -
ybtoj【字符串算法】1章2题【移位包含】
移位包含 题目解析 直接暴力移位，然后用find判一下即可 code: #include<iostream> #include<cstdio> #include<string> using namespace std; string x,y; int main() {cin>>x>>y;if(x.size()<y.size())swap(x,y);for(register int l=x…
2021/6/12 20:27:27 人评论 次浏览 -
P3373&&ybtoj【数据结构】4章4题【【模板】线段树2】
【模板】线段树2 题目 P3373解析 前置知识：线段树区间加区间求和 好的，现在我们考虑设计懒标记：一个乘，一个加，当然是先乘再加才不会对加产生影响 加法直接按区间加下传，乘法就需要两个懒标记一起乘 注意：乘法的懒标记初始为1 还有就是下传时要先下传乘法，再下传加…
2021/6/11 19:02:47 人评论 次浏览 -
【YBTOJ】【Luogu P2444】[POI2000]病毒
链接： 洛谷 题目大意： 构造一个无限长的文本串，使得此串不能被匹配。 正文： 好题。我的一开始的思路是，像 01trie 求最大异或那样跑 trie，然后跳失配指针判断合法。但显然假了。 于是得深度思考题意，“不能被匹配”说明跑 trie 时尽量失配，那么在求出失配指针后被…
2021/6/3 18:22:48 人评论 次浏览 -
【YBTOJ】【Luogu P3121】[USACO15FEB]Censoring G
链接： 洛谷 题目大意: 【Luogu P4824】[USACO15FEB]Censoring S的强化版。 在 \(S\) 中从头开始寻找屏蔽词，一旦找到一个屏蔽词，就删除它，然后又从头开始寻找（而不是接着往下找）。 有 \(n\) 个屏蔽词。 正文： 多模式串匹配，考虑用 AC 自动机。详见弱化版。 但是按…
2021/6/2 18:29:43 人评论 次浏览 -
【ybtoj 高效进阶 3.2】【最小生成树】 新的开始
【ybtoj 高效进阶 3.2】【最小生成树】 新的开始 题目解题思路 将建设发电站的费用看作是连向超级点的边权 从超级点开始跑一边prim即可代码 #include <iostream> #include <cstring> #include <cstdio> using namespace std; int n, x, tot , mi = 1, …
2021/5/4 10:29:01 人评论 次浏览
