xxb3.1415-CSDN博客

原创历届蓝桥杯省赛，国赛大题--个人题解目录 c++版，已更新[2018-2019]（太懒

只包含大题，代码均通过了c语言网上的数据（数据应该是一样的2019届人物相关性分析

2020-08-19 09:36:10 1347

原创东软杯-进制转换（求质因子的乘积）

题目这是一道简单的进制转换题，给出一个十进制的分数，求出能将它化为有限小数形式的最小进制数。为了更好的理解，我们给出一些例子：13\frac{1}{3}31 在十进制下为0.3333…，在三进制下为0.112\frac{1}{2}21 在十进制下为0.5，但是在二进制下为0.178\frac{7}{8}87 在十进制下为0.875，但是在二进制下为0.111数据范围及复杂度分析TTT数据，分子分母不超过10910^9109，使用O(Tn)O(T\sqrt{n})O(Tn

2021-11-05 10:41:24 282

原创 [2019蓝桥杯国赛B组c++][最优包含][排列数][解谜游戏][第八大奇迹]

个人题解链接，蓝桥杯历届试题，正在更新中~文章目录个人题解链接，蓝桥杯历届试题，正在更新中~最优包含排列数第八大奇迹最优包含题目链接：点击思路：显然的dp.设状态为dp[i][j]代表前i个包含前j个要改变的次数设状态为dp[i][j] 代表前i个包含前j个要改变的次数设状态为dp[i][j]代表前i个包含前j个要改变的次数转移方程:ifs[i]==t[j]:dp[i][j]=dp[i−1][j−1]if s[i]==t[j] :dp[i][j]=dp[i-1][j-1]ifs[i]==t[j

2020-11-12 23:33:29 1604 3

原创天梯赛训练赛(一）

这里写目录标题7-1 Hello World!7-2 计算摄氏温度7-3 念数字7-4 求整数段和7-5 个位数统计7-6 考试座位号7-7 打印沙漏7-8 连续因子7-9 城市间紧急救援7-10 月饼7-11 链表去重7-12 搜索树判断7-13 凑零钱7-14 社交集群7-15 特殊堆栈7-1 Hello World!思路：无坑点：无#include<bits/stdc++.h>using namespace std;int main() { cout << "He

2020-11-01 23:56:42 641 3

原创邮票面值设计 dfs+dp

题目链接题目大意给定一个信封，最多只允许粘贴NNN张邮票，计算在给定K(N+K≤15)K(N+K≤15)K(N+K≤15)种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAXMAXMAX,使在111至MAXMAXMAX之间的每一个邮资值都能得到。思路一开始并没有啥思路，然后瞎想另一个问题，给定的k个数，最多使用n个，求MAXMAXMAX该要怎么求。然后发现这个问题可以用dpdpdp来解决，dp[i]dp[i]dp[i]代表iii最少使用多少个数字组成，那么转移方程为mi

2020-10-16 23:15:11 164

原创 P2602 [ZJOI2010]数字计数数位dp

题目链接题目大意给定两个正整数 aaa 和 bbb，求在 [a,b][a,b][a,b] 中的所有整数中，每个数码(digit)(digit)(digit)各出现了多少次。做法一道简单的数位dp，头铁想要执行一次dfs就可以把[0−9][0-9][0−9]筛出来。于是定义了一个结构体。具体含义见注释struct node { LL a[11], v;// [0-9]就是题目里的含义，a[10]代表有多少个数，v用于记忆化判断 node() { _rep(0, 10, i) a[i]

2020-10-15 22:43:10 252

原创 P4290 [HAOI2008]玩具取名区间dp

题目链接题目大意第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。接下来W行，每行两个字母,表示W可以用这两个字母替代。接下来I行，每行两个字母,表示I可以用这两个字母替代。接下来N行，每行两个字母,表示N可以用这两个字母替代。接下来G行，每行两个字母,表示G可以用这两个字母替代。最后一行一个长度不超过Len的字符串。表示这个玩具的名字。做法我们把WING映射为1234区间dpdpdp，我们用dp[l][r][k][l][r][k][l][r][k]代表区间[l,r]能

2020-10-13 22:23:06 123

原创 P2513 [HAOI2009]逆序对数列

题目地址文章目录题目大意思路题目大意求出一个长度为nnn的全排列中有多少个逆序对为kkk的全排列。思路我们很容易想出一个朴素的状态:dp[i][j]dp[i][j]dp[i][j]为长度为iii的全排列中逆序对为jjj的数量。那么转移方程也很好想，我们考虑把iii插入到一个为i−1i-1i−1的全排列中，逆序对的变化，当把iii放在最后面时，逆序数不变，放在倒数第111个的前面，逆序对增加了111，放在倒数第222个的前面，逆序数增加了222。那么总结起来就是dp[i][j]=∑k=max(0

2020-10-12 22:37:38 272 1

原创 Educational Codeforces Round 96 E. String Reversal 树状数组+序列自动机

地址题目大意每次交换相邻的字符，使字符串反转。求最少的交换次数思路题目意思等价于交换相邻的字符使得两个字符串相等，两个字符串为原串和逆序串。交换相邻的字符代表着要贪心，每次把最近相等的字符移动过去，代价就是之间有多少个字符。举个例子：注意：我们有一些约定。1.下面出现的最前面指的是第一个还会变的位置，看下面解释理解。2.当一个字符移动到最前面之后我们就把它删除。相当于每次找前面有多少个字符，要把已经用过的去掉。abacc 反转后是 ccaba先把最近的c移到最前面，交换了3次把当前最近

2020-10-11 19:58:02 190

原创 CF388B Fox and Minimal path 构造

题目大意要求构造一个含有N(1≤N≤1000)N(1\le N\le 1000)N(1≤N≤1000)个节点的简单无向图，使得从111号节点到222号节点恰有KKK条最短路径（1≤K≤109）（1\le K\le 10^9）（1≤K≤109）。输出你构造图的邻接矩阵表示。思路对于这种要构造出含有KKK个最优解的问题优先考虑构造数据选择器（口胡的名字。数据选择器大概就是只要我们选择了某条边我们就可以得到xxx个最优解。然后这个xxx一般都是一个222的幂，我们选择构造2的幂的数据选择器也是有道理的，

2020-10-10 20:32:11 185

原创 CF414B Mashmokh and ACM DP

题目大意：如果一个数列中，后一个数都能被前面一个数整除，那么就叫这个数列为好数列。输入n，k，求数列中最大元素为n，数列长度为k的好数列的种数（对1000000007取模）思路状态设计：dp[i][j]dp[i][j]dp[i][j] 结尾为数字iii，长度为jjj方程：dp[i][j]=dp[d][j−1]dp[i][j]=dp[d][j-1]dp[i][j]=dp[d][j−1]，ddd为iii的约数初始化：dp[i][1]=1dp[i][1]=1dp[i][1]=1递推方式：dp[d][j

2020-10-09 17:00:25 158

原创 P3431 [POI2005]AUT-The Bus 树状数组+DP

题目链接题目大意：Byte City 的街道形成了一个标准的棋盘网络 – 他们要么是北南走向要么就是西东走向. 北南走向的路口从 1 到 n编号, 西东走向的路从1 到 m编号. 每个路口用两个数(i, j) 表示(1 <= i <= n, 1 <= j <= m). Byte City里有一条公交线, 在某一些路口设置了公交站点. 公交车从 (1, 1) 发车, 在(n, m)结束.公交车只能往北或往东走. 现在有一些乘客在某些站点等车. 公交车司机希望在路线中能接到尽量多的

2020-10-08 19:34:26 133

原创 P1486 [NOI2004]郁闷的出纳员 fhq-Treap

题目链接维护四个操作I k 新建一个工资档案，初始工资为 k。如果某员工的初始工资低于工资下界，他将立刻离开公司。A k 把每位员工的工资加上k 。S k 把每位员工的工资扣除 k。F k 查询第 k 多的工资。对于A和S操作，我们直接用一个值lazy来记录所有数变化是多少，当插入一个数的时侯我们改为插入k-lazy。k小于min的不加入，查询第k多的记得加上lazy。删除操作就直接分裂然后删除即可，记录每次删除的数的个数。#include<bits/stdc++.h

2020-10-07 21:43:21 140

原创 CF1425D Danger of Mad Snakes 二维前缀和+组合数

题目链接题意1000*1000的矩阵中n条蛇，你有m个武器可以攻击蛇，武器只能放在有蛇的地方，每个武器有r的攻击距离，对于每种可能的武器放置方案，产生的攻击值是所有蛇的攻击力的和的平方，求所有方案的攻击值的和。做法显然我们不能单独考虑每种方案，方案数太多了。我们每次枚举两条蛇，计算包含这两条蛇的方案数，这两条蛇产生的贡献是总方案数*两条蛇的攻击力的积。包含两条蛇的总方案数 = 所有的方案数-不包含第一条蛇的方案，-不包含第二条蛇的方案+不包含两条蛇的方案。就是一个简单的容斥。不包含某条蛇的方案=C

2020-10-06 19:40:29 150

原创 fhq-Treap题目记录

文章目录模板P6136 【模板】普通平衡树（数据加强版）文艺平衡树可持久化平衡树书架P3850 [TJOI2007]书架模板自己用的可持久化Treap的板子，改掉split的可持久化就可以当成普通的来用了。// 使用前插入-INF, 和INF。若不需插入，涉及的排名的地方有加一减一的问题普通版fhq-treap在split中去掉可持久化就可以。struct fhq_Treap{ struct { int val, siz, l, r, rnd;}T[N*60]; int cnt, x

2020-10-06 17:00:06 138

原创 Splay学习笔记，每个操作都会执行splay。

文章目录前言平衡树Zig和Zag引入splay操作前言之前学了fhq—Treap，一种靠分裂与合并维护平衡的一种树，期望复杂度是logn，常数也较大。Treap也有带旋转版本的，但是为了早日学会LCT还是先学Splay。也建议初学者先学不带旋转的平衡树，当然还有更简单的替罪羊树也可以先学。先借简单的来了解为什么要这样做。然后学更难的就跟好理解了。平衡树BST（二叉搜索树）的缺点是容易被卡成链，所以我们想要通过某种方法来使它的树高不那么任意被卡。我理解的平衡树就是为了使BST保持平衡，即树的高度期望是

2020-10-06 00:45:46 374

原创 CF5E Bindian Signalizing 单调栈

题目链接题目大意是，一个环上有n个点，当且仅当这两个点之间没有比这两个数中任意一个数大的数时，这两个点可以相互看见。求可以相互看见的点的对数。思路：遇到环的问题我们一般都是把环拆成链，但是这里如果只是简单的把数组复制一遍的话，我们发现很难去重。环有一个特性就是可以循环移位，我们把最大的数放在最左边，这样的话从逆时针找，找到的最大的数的位置不可能大于1.利用这个性质我们就可以写出这题。其实还是写了一上午，需要考虑很多细节。我们用单调栈维护一个递减栈，重复的数我们不再重复的放入，而是用一个数组标记它出

2020-10-04 14:09:39 154

原创 CF4D Mysterious Present 二维偏序+dp

题目求一个二维的严格递增序列。我们先排个序，然后再dp严格递增子序列，记录一下是从哪里转移过来的。然后再递归输出路径即可。#include<bits/stdc++.h>using namespace std;typedef long long LL;const int INF = 0x3f3f3f3f;const double Pi = acos(-1);namespace { template <typename T> inline void read(T &amp

2020-10-03 15:23:02 155

原创 [蓝桥杯][2018年第九届真题]防御力

个人题解链接，蓝桥杯历届试题，正在更新中~文章目录个人题解链接，蓝桥杯历届试题，正在更新中~开篇废话开篇废话这两题放在最后写，不是说它难。而是它有问题。基本可以确定防御力是错了，答案没有按照字典序排序。然后去知乎翻了一波往年的评价，发现那次比赛有三次勘误，可能包括这个（因为也没有人提到）。采油这题无意中发现有人说了做法，但是其实是有缺陷的，虽然可以过蓝桥杯的数据，但是构造了一组样例把它hack了。所以可能是数据比较弱。也可能是我太菜了，没理解到题目意思。暂时没有想到比较好的方法过这题，先放个可以过蓝桥

2020-10-02 22:40:52 1155 1

原创 P3768 简单的数学题杜教筛

题目链接简单数学题题意为求下列式子。(∑i=1n∑j=1ni∗j∗gcd(i,j))%p(\sum_{i=1}^n\sum_{j=1}^ni*j*gcd(i,j))\%p(i=1∑nj=1∑ni∗j∗gcd(i,j))%p先化个简ans=∑i=1n∑j=1ni∗j∗gcd(i,j)=∑d=1n∑i=1⌊nd⌋∑j=1⌊nd⌋i∗d∗j∗d∗d∗[gcd(i,j)]=∑d=1nd3∑i=1⌊nd⌋∑j=1⌊nd⌋i∗j∗[gcd(i,j)]\begin{aligned}ans&=\s

2020-10-01 23:44:41 98

原创 FHQ-Treap P3369 【模板】普通平衡树

Treap是二叉搜索树（BST）和二叉堆（Heap）的结合。二叉搜索树支持Treap的所有一般功能，例如查排名，查第k大，前驱，后继，删除，插入。它的特点是左子树小于等于根，右子树大于等于根。但是它的复杂度依赖于树的高度，而树的高度很容易被数据卡成链。Heap是一种完全二叉树，它的树高为log(n)。一般有小根堆和大根堆。我们以小根堆为例，它的特点是根节点小于等于子节点。其实到这里我们会发现两种树的性质是矛盾的，BST要求左儿子小于等于根，右儿子大于等于根，Heap要求根既小于等于左儿子，又小于等于右

2020-09-30 23:55:38 589

原创杜教筛题目记录

文章目录杜教筛套路杜教筛套路f(n)f(n)f(n)为积性函数，要求积性函数的前缀和，即∑i=1nf(i)\sum_{i=1}^nf(i)∑i=1nf(i)设S(n)=∑i=1nf(i)S(n)=\sum_{i=1}^nf(i)S(n)=∑i=1nf(i),你需要寻找两个积性函数hhh和ggg，使得h=f∗g(∗为狄利克雷卷积),h和g需要尽量好求。h=f*g(*为狄利克雷卷积),h和g需要尽量好求。h=f∗g(∗为狄利克雷卷积),h和g需要尽量好求。开始推一波：∑i=1nh(i)=∑i=1n

2020-09-22 21:05:36 186 1

原创主席树（可持久化数组）题目记录

文章目录P3834 【模板】可持久化线段树 2（主席树）P3834 【模板】可持久化线段树 2（主席树）P3834 【模板】可持久化线段树 2（主席树）经典的入门题，静态区间第k小

2020-09-09 18:33:19 147

原创 [蓝桥杯][2018年第九届真题]三体攻击

个人题解链接，蓝桥杯历届试题，正在更新中~文章目录个人题解链接，蓝桥杯历届试题，正在更新中~三体攻击三体攻击题目描述三体人将对地球发起攻击。为了抵御攻击，地球人派出了 A × B × C 艘战舰，在太空中排成一个 A 层 B 行 C 列的立方体。其中，第 i 层第 j 行第 k 列的战舰（记为战舰 (i, j, k)）的生命值为 d(i, j, k)。三体人将会对地球发起 m 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地，第 t 轮攻击用 7 个参数 lat, r

2020-08-22 17:55:55 825

原创 [蓝桥杯][2018年第九届真题]迷宫与陷阱、版本分支、自描述序列

个人题解链接，蓝桥杯历届试题，正在更新中~文章目录个人题解链接，蓝桥杯历届试题，正在更新中~迷宫与陷阱版本分支自描述序列迷宫与陷阱题目描述小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由NxN个格子组成的2D迷宫。小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。迷宫中有些格子小明可以经过，我们用’.‘表示；有些格子是墙壁，小明不能经过，我们用’#'表示。此外，有些格子上有陷阱，我们用’X’表示。除非小

2020-08-21 22:47:42 1023 2

原创 [蓝桥杯][2018年第九届真题]调手表、搭积木、矩阵求和、交换次数、整理玩具

个人题解链接，蓝桥杯历届试题，正在更新中~文章目录调手表搭积木矩阵求和交换次数整理玩具调手表题目描述小明买了块高端大气上档次的电子手表，他正准备调时间呢。在 M78 星云，时间的计量单位和地球上不同，M78 星云的一个小时有 n 分钟。大家都知道，手表只有一个按钮可以把当前的数加一。在调分钟的时候，如果当前显示的数是 0 ，那么按一下按钮就会变成 1，再按一次变成 2 。如果当前的数是 n - 1，按一次后会变成 0 。作为强迫症患者，小明一定要把手表的时间调对。如果手表上的时间比当前时间多1

2020-08-21 15:19:01 695

原创 [蓝桥杯][2018年第九届真题]小朋友崇拜圈、耐摔指数、堆的计数、缩位求和、约瑟夫环

个人题解链接，蓝桥杯历届试题，正在更新中~文章目录个人题解链接，蓝桥杯历届试题，正在更新中~小朋友崇拜圈耐摔指数堆的计数缩位求和约瑟夫环小朋友崇拜圈题目描述班里N个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。在一个游戏中，需要小朋友坐一个圈，每个小朋友都有自己最崇拜的小朋友在他的右手边。求满足条件的圈最大多少人？小朋友编号为1,2,3,…N输入输入第一行，一个整数N（3<N<100000）接下来一行N个整数，由空格分开。输出要求输出一个整数，表示满足条件的

2020-08-21 13:15:05 509

原创 [蓝桥杯][2018年第九届真题]航班时间、倍数问题、付账问题、次数差、等腰三角形

个人题解链接，蓝桥杯历届试题，正在更新中~题目目录个人题解链接，蓝桥杯历届试题，正在更新中~航班时间倍数问题付账问题次数差等腰三角形航班时间题目描述小h前往美国参加了蓝桥杯国际赛。小h的女朋友发现小h上午十点出发，上午十二点到达美国，于是感叹到“现在飞机飞得真快，两小时就能到美国了”。小h对超音速飞行感到十分恐惧。仔细观察后发现飞机的起降时间都是当地时间。由于北京和美国东部有12小时时差，故飞机总共需要14小时的飞行时间。不久后小h的女朋友去中东交换。小h并不知道中东与北京的时差。但是小h得到了

2020-08-21 11:21:14 418

原创 HDU多校10_1011_ Task Scheduler(证明过程）

题目链接题目大意是：有m个工人在线，有k个工人不在线，要给n个任务分配工人，第iii个任务要tit_iti个工人，如果选到不在线的工人就要重新选，每个工人选择的概率相同，要使得分配次数的期望尽量小，输出字典序最小的分配方案。第iii个任务分配合法的概率服从超几何分布为：C(m−∑j=1i−1tj,ti)C(m+k−∑j=1i−1tj,ti)\frac{C(m-\sum_{j=1}^{i-1}t_j,t_i)}{C(m+k-\sum_{j=1}^{i-1}t_j,t_i)}C(m+k−∑j=1i−1t

2020-08-21 10:26:12 467

原创 [蓝桥杯][2018年第九届真题] 递增三元组、螺旋折线、日志统计、全球变暖、乘积最大

个人题解链接，历届试题，正在更新中~题目目录递增三元组螺旋折线日志统计全球变暖乘积最大递增三元组给定三个整数数组A = [A1, A2, … AN],B = [B1, B2, … BN],C = [C1, C2, … CN]，请你统计有多少个三元组(i, j, k) 满足：1 <= i, j, k <= NAi < Bj < Ck【输入格式】第一行包含一个整数N。第二行包含N个整数A1, A2, … AN。第三行包含N个整数B1, B2, … BN。第

2020-08-20 22:45:32 262

原创 [蓝桥杯][2019年第十届真题]组合数问题（数位dp，卢卡斯定理）

个人题解链接，历届试题，正在更新中~题目描述给n,m,k，求有多少对(i,j)(i,j)(i,j)满足1≤i≤n,0≤j≤min(i,m)1 ≤ i ≤ n,0 ≤ j ≤ min(i,m)1≤i≤n,0≤j≤min(i,m)且C(i,j)≡0(modk)C(i,j) ≡ 0(mod k)C(i,j)≡0(modk)，k 是质数。其中 C(i,j)C(i,j)C(i,j) 是组合数，表示从 i 个不同的数中选出j个组成一个集合的方案数。输入第一行两个数 t, k，其中 t 代表该测试点包含 t 组

2020-08-19 12:22:39 2727 9

空空如也

空空如也