题解counting t399753 problem

考虑建出 AC 自动机，朴素做法是高斯消元，$f_i=\sum\limits_{j=0}^{k-1}f_{to_{i,j}}p_j+1$，复杂度 $O(n^3m^3)$，不能接受。 考虑优化高斯消元的过程，我们定义以下节点为“关键点”： - 根节点 - 对于一个 trie 树（也就是未经过 AC 自 ......

1.成绩 原题：https://www.luogu.com.cn/problem/P3954 代码： #include<bits/stdc++.h> #define ll long long using namespace std; int a,b,c; int main(){ cin>>a>>b> ......

显然，两个序列本质不同等价于它们的笛卡尔树不同。而题目这个关于 $m$ 的限制等价于，每个叶子节点到根路径上，满足“该点是其父亲的左儿子“的节点数不超过 $m-1$。 考虑 $dp$。$dp_{m,n}$ 表示有多少个长度为 $n$ 的序列，满足每个叶子节点到根路径上左儿子个数不超过 $m-1$，那 ......

[原题链接](https://www.luogu.com.cn/problem/U297943) 我第一次出的一道比较正经的菜题，欢迎大家来切哦。 感谢魔法少女老干妈 GM_Joanna_ 的支持 对于操作 1，3： >注意到 1e9 的数据至多 5 此操作就能把一个位置变为 0，这个次数可视为常数 ......

# [Manga](https://vjudge.csgrandeur.cn/problem/AtCoder-abc271_c) ## 题意 有一部连载漫画，共 $10^9$ 卷，你手上有 $n$ 卷漫画，第 $i$ 卷是连载中的第 $a_i$ 卷。 **你在看漫画之前**，可以执行以下操作若干次（ ......

[题目传送门](https://www.luogu.com.cn/problem/AT_abc230_d) 一道贪心题。 我们可以将每一堵墙的右端点从小到大进行排序，然后我们从第 $1$ 堵墙开始看，将在第 $1$ 堵墙的右端点打破后会倒塌的墙全部跳过，去看下一堵还没被打破的墙。可以证明这是最优解。 ......

一、题目描述： 给你 $n$ 个集合 ，第 $i$ 个集合有 $A_i$ 个数，集合里的数都小于等于 $m$。 你可以选择两个至少有一个相同元素的集合，生成它们的并集，然后这两个集合消失。 求最少多少次合并之后，数字 $1$ 和 $m$ 在同一个集合中。如果不可能，请输出 $-1$ 。 数据范围：$ ......

## CF1200 143B 题解 #### 题目大意 给我们一个字符串，统一输出规则，也就是保留两位小数，但是不遵守四舍五入法则（简言之就是不进），比较重要的就是除非整数部分是零，否则开头不会是零，此外还有负数的情况 #### 思路 也就是单纯的模拟，先寻找负号和小数点，分四种情况讨论（太蠢了只能 ......

完全不会 G 和 Ex，这些套路还是要积累一下的。 ## F.Merge Set ### 题目描述： 给定 $n$ 个集合，每次可以合并两个有交的集合，问最少多少次合并可以让 $1$ **和** $m$ 位于同一个集合中。 ### 题目分析： 一开始将题读成了将 $[1,m]$ 位于同一个集合中，然 ......

球钟问题描述:球钟是一个利用球的移动来记录时间的简单装置。它有三个可以容纳若干个球的指示器：分钟指示器，五分钟指示器，小时指示器。若分钟指示器中有2个球，5分钟指示器中有6个球，小时指示器中有5个球，则时间为5:32。 工作原理:每过一分钟，球钟就会从球队列的队首取出一个球放入分钟指示器，分钟指示器 ......

1.标题统计 原题：https://www.luogu.com.cn/problem/P5015 #include<bits/stdc++.h> #define ll long long using namespace std; string s;int ans=0; int main(){ get ......

令 $loc[i]$ 为 $i$ 的位置，我们看看经过操作后会变成什么。 初始时 $loc[i] = i$。如果有 $r$ 操作，那么 $loc[i] ++$，如果是 $f$ 操作，那么 $loc[i]$ 变为 $n-loc[i]+1$ 即可。 最终的每个 $loc[i]$ 都可以表示为 $sign ......

# 题目大意 构造一个01网格图，1能走0不能走 使得从左上走到右下（只能走右或走下）的方案数恰好为x n=当前p[i]就减p[i]，a[i]+1（也类似**进制转换**） （也可以理解成让**ai尽量小**，所以一次**减的数尽量大**，每次**减最大的能减的数** # code ```cpp # ......

本文建议通过对连续transition进行线性插值来合成新的transition用于训练。为了保持构建的transition的真实性，还开发了一个鉴别器来自动指导构建过程 ......

打的还行，加的分不多。 # [A](https://atcoder.jp/contests/abc302/tasks/abc302_a "A") 直接除完上取整即可。 ```cpp #include using namespace std; typedef long long LL; const i ......

简单版（P2347）[传送门](https://www.luogu.com.cn/problem/P2347) 原题[传送门](https://www.luogu.com.cn/problem/P8742) 有一道**类似**的题目（P2347），先扯一扯~ # 1.P2347 ## 题目分析 动态 ......

# [P3863] 序列 题解 ## 题目描述 给定一个长度为 $n$ 的序列，给出 $q$ 个操作，形如： $1~l~r~x$ 表示将序列下标介于 $[l,r]$ 的元素加上 $x$ （请注意，$x$ 可能为负） $2~p~y$ 表示查询 $a_p$ 在过去的多少秒时间内不小于 $y$ （不包括这 ......

[本文章同步发表于洛谷](https://www.luogu.com.cn/blog/fxy-blog/cf1833d-ti-xie) ### 思路 这是一道水题，但细节很多...... 首先，要求字典序最大，显然就想到了让最大的数字在第一位。 于是就进一步得出了应该让最大数字在翻转区间的后一位，初 ......

## 题意 给定一个$1\sim N$的排列，在这个排列中选出两段互不重叠的区间，求使选出的元素排序后构成公差为1的等差数列的方案数。选出的两段区间中元素构成的集合相同时视为同一种方案。$1\le N\le 3\times 10^5$。 [传送门](https://www.luogu.com.cn/ ......

## 题目描述 给你四个正整数 $a,\,b,\,c,\,d$ ，求一个最简分数 $\frac{p}{q}$ 满足 $\frac{a}{b} \dfrac{r}{s}$。那么有以下结论： $$\dfrac{r}{s} \leq \dfrac{r + u}{s + v} \leq \dfrac{u}{ ......

1.分糖果 原题：https://www.luogu.com.cn/problem/P7909 原代码： #include<bits/stdc++.h> #define ll long long using namespace std; ll n,l,r; int main(){ cin>>n>>l ......

[$\text{link}$](https://www.luogu.com.cn/problem/CF1781F) 。也是一道非常巧妙的 $\texttt{dp}$ 。 容易想到把括号变成 $\pm 1$。考虑括号序列合法等价于前缀和 $\ge 0$，我们可以想加入 $()$ 或 $)($ 对前缀的 ......

左偏树维护动态区间中位数。 [传送门 P4331 BalticOI 2004 Sequence 数字序列](https://www.luogu.com.cn/problem/P4331)。 ## Solution ### 1 我的思路和题解前半部分完全重合了（（ 如果按照单调不增去分割 $a$ 序列 ......

1.植树节 原题：https://www.luogu.com.cn/problem/U285015 代码： #include<bits/stdc++.h> #define ll long long using namespace std; const int N = 1e6+255; int a[N ......

1.数字游戏 原题： https://www.luogu.com.cn/problem/P5660 代码： #include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstring> #include<algorithm ......

git -commit 报错： 原因：npm缓存造成的 解决方案： 删除packpackage-lock.json,删除所有依赖，执行 npm cache clean --force npm install ......

问题描述 新建表或者修改表varchar字段长度的时候，出现这个错误 Row size too large. The maximum row size for the used table type, not counting BLOBs, is 65535. This includes stora ......

怪异题。 阈值分治。权值不超过 $2^{16}=65536$，于是把前后八位砍开。把每个点和上边 $256$ 个点分成一块，那么每块内的 $dis$ 的前八位是相同的，因此可以分开考虑。 前边 $8$ 位设一个 $f_{x,i}$ 表示跳了 $i$ 块跳到 $x$，这一块的前八位最大值。这个暴力把这 ......

题意: 给定一个长度为 $n$ 的整数数组 $a$，求 $a$ 中前 $k$ 大的异或区间和之和。 首先对 $a$ 处理一个异或前缀和数组 $s$，这样区间 $[l,r]$ 的异或和就转化成了 $s_{l-1} \oplus s_r$。题目就变为求 $n+1$ 个数（包含一个空前缀）两个数异或前 $ ......

传送门 交通运输（Wormhole Transportaion） 题目大意 有 $n$ 个点和 $m$ 个点对，你需要构造一张 $m-1$ 条边的无向图，使得 $m$ 个点对间最短路之和最小。 求最小值及取到最小值的方案数。 $2 \le n \le 2000,2 \le nm \le 2 \tim ......