题目大意 你需要构造个长度为的字符串，并且保证。 Solution 考点：模拟 我们先不考虑输出顺序，只考虑是否能够构建，我们把变成的形式进行一次排序。 那么我们可以想到下图这样的构建方式是最合理的： 接下来就是找出最小的字母，然后确定这三个字符串的位置了。 int solve() { string s1, s2, s3; int a = read(), b = read(), c = read(), n = read(); int maxi = max({ a,b,c }); int mini = min({ a,b,c }); int tmp...

题目大意 你有一个随机数生成器，他会随机生成到之间某个数，生成的概率为。 现在分为大体步操作： 随机生成一个。 如果这个​是已经生成的数中最大的，返回步骤一继续生成新的数，否则进入步骤三 游戏结束，本局游戏的得分为生成序列的长度的平方​。 现在要你求出这局游戏的得分期望。 Solution 考点：期望dp 这个期望不是很好求，我们优先考虑求出。 我们假设​​​是随机到​​​​后还能进行的期望抽取次数，那么我们知道​​，那么我们把之后的抽取分为​​​这三类，可以知道，抽到​​​之后就无法进行了这时候的期望次数就是​​​，如果抽到了相同的数​​​，这时候他带来的期望次数就是​​​，如果抽到了​...

B、Black and white 题目大意 地图规模为级别，点权依靠公式生成，你可以花费点权那么多钱涂黑一个点，如果长方形中个顶点被涂黑了，那么剩下的顶点可以免费涂黑，询问将整张图涂黑的最小代价是多少？ Solution 考点：并查集 我们如何看待涂黑个点第四个点可以免费这个是我们解题的关键。 将个点沿着轴轴方向一路延申，你会发现选中的三个点才会联通在一起，并且我们可以免费填涂的第四个点也在他们的连通块之中。 那么我们把每个看成连接了​这样行列两个点的权值，做一次特殊一点的最小生成树即可。 #include <bits/stdc++.h> using namespace std;...

C、Draw Grids 题目大意 给出​的点矩阵，两名玩家，每次玩家要连接一条边，并且保证图中没有成环的地方。 Solution 考点：树形结构 我们知道我们看成个点构成的一片树林的话，最终就是一人连接一条边，最终构成一棵树。 直接判断节点的奇偶性即可。下面的是代码。 n,m=map(int,input().split()) p=n*m-1 if p&1: print("YES") else: print('NO') D、Er Ba Game 题目大意 给出两个的比较逻辑，输出两个数的大小关系。 Solution 考点：逻辑 这里赛后看见一个写的挺...

A、Alice and Bob 题目大意 存在两堆石子，石子个数分别是和，数量级在，现在每个人轮流进行挑选，必须任选一堆拿走个石子，再从另外一堆拿走个石子，也就是第二次选的可以拿走个石子。先手，后手，第一个无法操作的人就输了，询问比赛谁胜利了。 Solution 考点：博弈 首先我们来考虑用​代表第一堆有​个石子，第二堆有​个石子的先手必胜还是必败态。 初始化。 接下来暴力枚举第一堆石子，第二堆石子，如果某个点是现在必败态，说明把它加上若干个符合要求的左右石子数一定是必胜态。 但是这样一看复杂度有，我们再仔细观察，假设对于两个局面都是必败态，并且假设，那么我们就可以在局面的时候拿掉个石子，让局...

L-WeChat Walk 给出一张图，一共有个时刻，每个时刻只有一个点的权值会增大。并且保证最终图里面最大的点权值。 一个人某个时刻成为冠军是和他相连的全部点这个时刻权值严格小于当前点，如果某个时刻不满足条件了那么这个人就失去了冠军，输出所有点成为冠军的时长。 Solution 题目关键信息1.每次只有一个点权值改变，2.最大权值。 那么我们按照这个边界对图中的点进行分点，记为。 我们将度数大于的叫做大点，我们将度数小于等于的叫做小点。 如果当前遍历的点他是小点，那么暴力维护他连接的点叫做，并且维护和相连的最值情况，以便以后维护的得冠情况。 对于大点，我们首先判断他和他相邻的大点，接下来就...

题目大意 一个合法的序列是一个长度为并且和为的非负整数序列，并且对于给出的序列还需要满足任意位置，给出询问共有多少个合法的序列，对取模。 Solution 看到运算，就需要往二进制拆分上面靠，那么对于一个他的第位二进制位是，那么从到每一个数的第个二进制位都应该为。 那么题目就变成了你可以用任意的幂次去构造，并且每个的幂次最多使用次，问构造出的方案数。 等价于存在购买上限的多重背包问题，可以使用容斥解决问题，时间复杂度，是可选的二进制幂次数量，是题目给出的，因为所以 #include <bits/stdc++.h> using namespace std; #define js io...

笛卡尔树 - OI Wiki 用来访问查询多次区间最值的数据结构，数中每个节点存在，符合二叉搜索树的特性，左边值小于节点右边值大于节点，符合堆的特性，节点值小于(大于)全部的子节点。 最大子矩形 我们把每个矩形的下标当作，矩形高度当作，构造出笛卡尔树，从上到下求解树形即可。 我们构造的笛卡尔树满足左右区间连续。 我们构造的笛卡尔树满足当前节点的高度一定小于它全部的子节点。 所以我们从根(最小的高度)出发，求解取最大值就是答案了。代表当前节点的子节点个数。 那么我们还能稍加变形，如果给出的矩形宽度不是，而是，我们也可以使用树形求解全部子节点的宽度，返回到父节点那里去。 const int ...

问题描述：n个人（编号1~n)，从1开始报数，报到m的退出。按顺序输出列者编号。 时间复杂度 void solve() { int n = read(), m = read(); int i = 0, p; while (++i <= n) { p = i * m; while (p > n) p = p - n + (p - n - 1) / (m - 1); print(p); } }问题描述：n个人（编号1~n)，从1开始报数，报到m(m<<n)的退出，求胜利者...

中文题意 你要选择个长度是的字符串，这些字符串要满足字典序大于小于，在输入的第二行和第三行给出，求本质不同的前缀一共有几个。 Solution 如果我们把看作的话，我们就可以构建一颗满二叉树。那么其实我们对应的在满二叉树中有自己的对应编号。 其实就是问你给你两个这样的端点前面你可以选择的节点数一共有多少个。 那么当我们当前可选的区间长度一直都不足的时候，我们就可以把这一层全部的可选节点数都加上。 当我们当前可选区间的长度第一次大于等于之后，因为你上方全部的节点都已经被你计算过了，所以你最多只能在当前层选择个节点，那么这种时候你就不能把这一层可选的节点都拿上去了，只能选择其中的个，那么与之对...

参考学习的题解 P3376 【模板】网络最大流 因为只是一道模板题，不涉及建图这里就不展开介绍。 实现最大流，不会的可以参考这篇文章用上了弧优化以及优化。 #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" #define pai pair<int, int> #de...

Solution 首先观察题目中的定义可以得知，在不区分前后关系的时候判断很复杂。 我们对于这种环形的办法一般都是断环成链，复制一份。 那么这样处理之后，就可以永远保证按照这种的方式求解不会漏掉情况，并且每次我们每次往前选择的 。接下来就是维护转换方程了。 我们要求解的答案是 定长区间的最值问题，使用单调队列求解。 #include <bits/stdc++.h> using namespace std; #define rep(i, sta, en) for(int i=sta; i<=en; ++i) #define repp(i, sta, en) for(int i=...

题目大意 组输入，每次有个点条边的有向图。首先如果从起点不能到达终点，那么输出一个，如果可以到达求解出最短路的距离记录为。那么我在保证最多另外让你走个距离的情况下，问你从起点到终点的方式有几种？并且方案数要对取模。因为我们存在边权为的边，所以如果有一个环它的权值和都是，那么直接输出。 Solution 题目告诉我们可以在最短路的基础上多走距离，那么我们先求到最短路的花费。这里注意，我们建立一张反图，再从跑向各个点，就可以知道如果到了这个点去到还需要的最小距离是多少，我们使用算法求解。 接下来我们套上记忆化搜索，使用数字代表我们走在节点，还可以多走的额外距离是的方案数。那么转移的方程式就是找到一...

Solution 交汇地铁类型的图，一般都考虑分层建图或者借助额外的点建图。我们把起始的站点用表保留编号，上下地铁的位置建立额外的编号，这样就可以保证我们每次上下地铁计算到正确的票价。 所以我们再把地铁路线上的点拆分成向左向右两边的点，那么很明显边权存在两个(票价，时间)，那么从起始站点上地铁我们开销就是，从地铁下来开销，同一个地铁上的不同站点，注意这里不能连接到了起始站点，这和地铁路线上的站点已经被我们分隔开来了，这些开销是。 那么从的最小票价，就是通过第一权值求解最短路，使用算法。 从的最大时间就是把最短路图中的边挑选出来，最短路图的概念就是在求解单源最短路之后的边，根据最短路图的性质很明...