一开始以为求第0-12个问题的解决概率懵逼了很久 一道简单的概率dp/dfs问题 我们先求出每个问题的解决概率。 我们运用正难则反的思想，先求出我们不能解决第i个问题的概率，即： 然后，用1减去这个概率就是第i个题可以解决的概率了，设为 那么，现在就可以随便乱搞了。 注意到，n很小，可以直接dfs搞，每个点成功和失败都枚举一次，复杂度 还有更优秀的就是用概率dp来解决。 我们设表示前i个问题中，对了j个问题的概率。初始化 那么，直接类似0/1背包转移即可（需要注意的是，到这里不能直接转移,还要乘上失败概率） 那么就有转移方程: 【因为这个情况第i个问题不可能成功，所以单独讨论】 【分第i个问...

一.闲话 本来打的挺开心的，A题速度挺快的。然后。。。G题被疯狂卡精度。。。（绝望），罚时一大堆qwq。我好菜啊qwq 由于打比赛的时候，打的比较快，很多代码都比较粗糙，还请见谅~ 二.题解 A.AOE还是单体？ 明显是个单峰函数求极值问题（应该可以直接推式子，但是懒）~ 我们三分群体攻击次数，然后计算求极值即可~ 代码: #include<bits/stdc++.h> using namespace std; #define int long long const int N=2e5+1; int a[N],n,T; inline int calc(int x){ int...

本来打算只写一种解法的，不过感觉太水了，就多写点吧 解法一.暴力 按照题目说的模拟去做，复杂度,期望得分：70-100(数据有点弱啊qwq) 解法二.带优化的暴力 我们设a[i][j]表示i,j点的正下面中，包含i,j的k格格子中是否至少存在一个1。 这个直接暴力统计就好了，当然，你要把存在改成有几个的话，就可以直接计算了 然后，我们枚举每个k*k矩形的左上角，设为(x,y)，那么，我们只要中有一个1，那么这个k*k的矩形中就会有一个1。直接暴力统计或者跟上面的方法一样计算也行。 复杂度：,期望得分:100 解法三.二维前缀和 我们直接预处理出二维前缀和（每个点到1,1所构成的矩阵中，元素之和...

发现这个比赛忘写题解了，来补题解辣qwq A.牛牛的三角形 总所周知，三条边可以拼出三角形的充要条件是：最小的两条边长度之和大于第三条边。 看数据范围，n<=100,于是直接一个n^3枚举再判断就行辣！代码： #include<bits/stdc++.h> using namespace std; int a[101]; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&a[i]); } sort(a+1,a+...

这道题其实就是一道化式子的题，化完式子后就可以乱搞了/x 我们设pos[i]表示i号点的位置，特别的，pos[1]=0,那么，我们就可以根据i到i+1的距离，分别算出每个点的位置了。 那么，我们就开始化式子吧。 我们假设将i号点的物品搬到j号点去，那么代价就是： 那么， 如果将l-r号点的物品搬到x号点去，代价就是： 我们发现，绝对值太烦了，于是我们想办法化掉绝对值，那么，我们只需要分情况讨论就行了： 1.x<=l，那么，对于任意的来说，都有,于是式子变为： 注意到，对于任意的点i来说，是个常数，所以，我们设,那么，我们就相当于求所有的b[i]的和，然后，后面的式子，明显就是所有的...

这道题，因为传送阵需要3s，所以，我们如果打普通的bfs可能会挂，于是，为了满足正确性，就可以类比01bfs之类的，搞个优先队列做。。。 但是，个人觉得有点麻烦，我们不妨从"这道题是一个搜索题"这个想法中解放出来，那么，这题就变成了一道明显的最短路问题啦！我们先利用网络图连边，然后再把传送阵的q条边添加进来就好辣！ 因为有网格图，所以不建议打spfa（除非进行些玄学优化），剩下的就是dijkstra板子了！ （注意清空数组） 代码： #include<bits/stdc++.h> using namespace std; const int N=301,M=300*300*4+10...

一.闲话 这次比赛挺简单的，我就来写下其中有意思的题目的题解吧。。。（罚时太高，排名直降，我太菜了qwq） 二.题解 C.Game 这道题明显是一道博弈论问题，那么，就需要搞sg函数之类的。。。 算了吧！/xk 我们直接暴力dp吧。。。 我们设dp[i]=0/1表示有i个石块的情况是必输/胜 那么，考虑转移。 我们每次选i的一个非1约数j,那么，就被分成了j和i/j两部分 考虑两部分的状态的值，有： 1.dp[j]=0,dp[i/j]=0 那么，我们模拟下，我们取拿j的话，就必输，然后再作为先手拿i/j，也必输，所以，先做j和i/j的必输，不过，先手已经将i分成了j和i/j，那么，就轮到后手作...

精选原创/改编数论题题单，欢迎大佬们顺手AK std及题解(提取码：sefu) 如有任何语文数学上的错误，欢迎指正orzzzzz

一道比较经典的区间dp题目 首先我们设dp[i][j]表示我们用i-j这些点构造树的最大收益是多少 首先dp[i][i]=a[i]（只有一个点，最大价值即点本身价值） 现在，我们考虑转移： 因为一颗子树的价值=左子树价值*右子树价值+根价值 那么，如果我们知道了根，左子树，右子树后，就可以进行转移了 于是，我们先枚举根，但是，如果再枚举哪些点放左子树，哪些放右子树的话，明显复杂度就爆炸了，怎么办呢？ 注意到，题目有个条件：树的中序遍历为1...n，那么，就有一个小性质： i的左子树都是编号比i小的点，i的右子树都是编号比i大的点。 于是，如果我们枚举了根的话，假设为k，那么就有: 左子树组成的...

很简单的一个联通块题目 首先，我们把同一个阵营中，会相互波及到的大炮放进一个连通块中，这样的话，很容易可以发现，如果连通块中有一个大炮被攻击了的话，那么，整个连通块的大炮都会被波及。 现在，假设我们将双方的联通块个数及大小求出来了，分别为： 司机: 齐齐: 那么，对于齐齐来说，每次攻击就相当于用一个联通块抵消掉司机的一个联通块（最后一个不算） 那么很明显，要让剩下的大炮最多，这就是一个简单贪心问题了，我们用最小的k-1个联通块去把司机的联通块抵消的（第k个保留就行），然后，统计剩下连通块中大炮的数量之和即为答案。 而如果t<k,那么，齐齐的联通块就不能够抵消掉司机的所有联通块，输出-...

一.闲话 英文题真难受，盯google盯了好久qwq，输入部分还是看样例解释看出来的qwq,英语菜鸡没人权qwq 二.题解 这道题，题意是： 有n场电影，每场电影都有若干场。 给你每个电影的播放时间以及每场的开始时间，问你，要连续不断的看电影直到看到l为止，最少需要看几部电影（每部电影最多看一场） 明显的dp/贪心题目，仔细分析后，发现并不能贪心，所以考虑dp 注意到，l很大，所以直接dp的话是不行的，但是，n很小（n<=20）,于是我们从这里入手，n<=20的话，那么一般考虑搜索或者状压dp(复杂度正好合适)，首先，搜索的话，我们只能枚举看哪些电影，至于看哪场，就又需要考虑了，所...

qwq，rt，菜鸡刚刷了这道题，然后发现当a=b=0的时候会卡掉绝大多数的代码qwq，因为计算时模数变成0了，虽然就一个if的事，但菜鸡觉得还是考虑完整比较好qwq

这道题，常规做法的突破点在于:（R-L<=1e5）这个条件 那么，如果我们把这个条件去掉，询问数据为：1000000000 1 1 1000000000该怎么做呢？ 一开始，我们先按套路，将L-R取最大公约数为k，化成 到取最大公约数为1 然后开始做题。 首先，我们先来将答案表达式划出来： (L和R为化过之后的) 那么根据套路带入莫比乌斯函数的性质 然后更改枚举项，枚举k 然后，我们通过观察可以发现，是可以通过整数分块实现的，于是我们整数分块来搞后面部分，至于前面，我们就需要求u的一个区间之和了，这时，我们想到，我们可以求u的前缀和来算区间之和，而快速求u的前缀和的方法，不正是杜教...

一.闲话 qwq，太菜了有情况没考虑到，使用了出题人给的hack数据后才明白。 出题人给的hack数据:13 10 21 10 14 ans=42 二.题解 这题中，我们不难证明，那么最后我们一定会在两个点直接徘徊或者直达某个点。 证明如下： 若不在两点间徘徊有最短距离，设我们走的点的序列为: (对于) 那么走的距离就是: 那么，对于其中的最小的那个 我们如果一直在t-1和t两个点间徘徊直到走的点的个数等于m这个策略用的距离就是: 明显的这个距离是小于等于上面的距离的，与我们假设不符合，所以，我们最后一定是在两点间徘徊的（若k=t的话，就是直达某个点了） 所以，我们可以考虑枚举在哪两个点间徘...