戳我传送  A、最短路   思路：   Code：  #include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define dis(a,b,c,d) sqrt((a-c)*(a-c)+(b-d)*(b-d)) #define ll long long using namespace std; int main() { js; double x1,y1,x2,y2,x3,y3,r; cin>>x1>>y1>>x2>>y2...

戳我传送  题意：n根木棍中截取k根长度一样的木棍，多余的木棍舍去。 思路： 先用最简单的方法从长度1开始一个一个枚举，直到达不到题目要求，这样的复杂度 (n^2)，显然会超时。我们就可以选区间的中点，如果不行答案一定比这个小，如果可以我们继续试试大一点可不可以，一步步缩小区间，这是二分的思路。以前属于完全套一个模板，现在才了解了一点二分：因为我是把答案存在l上，所以如果当前mid可行，那么l=mid，否则r=mid-1，直到l==r。l左区间，r右区间，mid要取l+r+1，刘大佬和吴大佬说是为了防止除数为0，这个我没想到，还有一点是使mid偏大一点，避免死循环，如果是mid=l+r，当r-...

小白月赛20戳我传送 题目大意：输出前斐波那契数列前n项平方和，1<=n<=1e18。前备知识：快速幂和矩阵，可以进我的博客了解一下，小白非常容易理解：戳我了解 思路： 斐波那契数列前n项平方和有递推式：前n项平方和等于 f[n] * f[n+1]。因为n非常大，用递归的思路去求肯定超时，所以想办法用 (log n)的方法去解，用矩阵转化为乘法，然后快速幂求解就可以了。一道模板题，难度适宜。 Code： （那个时候学的代码） #include<bits/stdc++.h> #define ll long long using namespace std; const l...

快速幂： 1.求5^19，19个5相乘当然可以算出来，但是当指数特别大的时候O(n)就不行了，必须要O(logn)的算法，也就是根据位运算来求解。19的二进制是（10011）5^19=5^1 * 5^2 * 5^16;指数对应的二进制如下：1---00001,2---00010,16---10000于是我们可以设temp=5(底数),我们求出来的结果是ans；那么我们可以设置一个循环，起始条件是1，边界是n=5(指数的二进制的位数)，每循环一次temp就乘一次temp(乘一次就是5^2,两次就是5^4....)，同时如果此时的这一位是1，ans就乘上这个temp（根据这个步骤再结合上面的例子就...

前面的碎碎念：菜鸡不敢打这个比赛，赛后看题解有“水题”就补了题。戳我传送 A、勇者比武 大意：H * W的格子上放了J,O,I三种字符，求满足条件(i,j,k,l)的四元组的数量，(i,j)上是J，(i,l)上是O，(k,j)上是I。其中l大于j，k大于i，也就是说问有多少JOI的组合满足O在J的右边，I在J的下边。 思路： 前缀和变形一下，从行末和列末往前计算当前位置右边出现了多少O下面出现了多少I，这个位置如果出现了J，那么这个J的贡献就是两个集合的组合数，将全部J的贡献求和就是结果了，复杂度 (m*n)。 Code； #include<bits/stdc++.h> using...

戳我传送  思路：  方法一：因为每条边的权值都是一样，所以可以用LCA求得每个结点想对于根结点1的深度，在这里深度就是距离。从偶数层到偶数层和从奇数层到奇数层的路径都是偶数。这里可以用链式向前星存图，然后dfs统计有多少个奇数层a和偶数层b，不必要区分偶数层和奇数层，答案就是 + 。如果1e5-1个结点都连在根结点1上，这时的答案最大，需要用long long。复杂度： (log n)。Code戳我 方法二：设f[i][0/1]表示以i为根的子树中，与根节点i的距离为偶数(0)奇数(1)的点的数量。转移方程显然是f[u][x]+=f[v][x^1]，f[u][x^1]+=f[v][x]。答案...

戳我传送 solution： 大佬们一看到1e18就知道要找规律，本菜鸡还想着递推。方法一：刘大佬说可以在n个位置里找出2个组成1 0，有 种方案，其它位置有 种可能，答案就是* 。这太神仙了，递推菜鸡的我看了好久。刘大佬原话----0就是没有贡献，1的话会在选这个位置是1后面是0算到。看了邓老师的题解后感觉自己傻到了，比刘大佬的说法更清楚，就是选出一对逆序对，他能对个01串做出贡献，而01的逆序对可以找出个，那有这个逆序对的01串里还有逆序对不用算吗，是不用的，已经在求别的方案的时候就算到了。方法二：可以枚举每个位置i的贡献，第i个位置为1时没有贡献，为0时的贡献为前i-1个位置1的个数，前...

前面的碎碎念菜鸡被碾压的一场比赛，就会一题。比赛传送门 A、相反数 思路： 签到题，直接枚举每一位， (n)能过，我写这一题的时候居然慌了。 Code： #include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; char s[20]; int ans=0; int main() { js; cin>>s; for(int i=0,j=strlen(s)-1;s[i];++i,--j) { ans=ans*10+s[i...

Accumulation Degree 题意：不知道题目讲什么真的要命，水从根结点往下流，流量不能超过边的权值,sum[i]表示i结点最多可以流出多少水（流量），这个需要从叶子节点一直回溯来求，父结点的流量sum[u]+=min(w,sum[v]),w表示u和v边的权值，特别的当v是叶子结点的时候，sum[v]=0,sum[u]+=w。知道了换根dp的模板后难的就是不理解题意 思路： 如果对每一个结点都dfs一次复杂度为O(n^2)，显然是不可以的，所以要用到换根dp。前要是：每个结点的流量sum[]初始化为0，每个结点最后一次出现的位置head[]也初始化为0。用链式前向星存储所有结点，然后...

戳我传送 思路： 前缀和sum[i]保存前i个数的异或值，sum[i]=sum[i-1]^a[i]，[L,r]的异或值显然是sum[r]^sum[L-1]。试着枚举右端点i从1到n，得到以i为右端点的全部全部区间的异或值。为避免重复可以二分一下，同时枚举全部以i+1为左端点的全部区间的异或值，如果和前面的值相等就加上相等的区间个数。因为n比较小 (n^2)可以过。注意：ans比较大，要开ll Code: #include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) usin...

传送门戳我 Solution： 将完全二分图匹配问题转化为n*n棋盘的涂色问题，初始颜色都为绿色，在棋盘上选一些格子替换成红色或者绿色，同时任意一行任意一列不能同时出现红色或者蓝色。1、首先我们先考虑只涂一种颜色的情况。假设当前染了k条边，因为棋盘的对称性，可以选择k行，这部分的方案数为 ;对于k列就不是组合而是排列了，这部分方案数为 ;所以，n个点的完全二分图只连k条红色/蓝色边的方案数为f[k]= * 。2、红蓝颜色都涂时，枚举红蓝边重复的边数x，根据容斥的思想可得 * f[n-x] * f[n-x]。最终的答案就是ans= * f[n-x] * f[n-x]注意到f[n]需要 (n)的复...

前面的碎碎念： 菜鸡差点爆0，题目有点不对胃口传送门 A、打怪 签到题，差点没签到成功 思路： 计算勇士砍死一个怪需要的次数，从而得到砍死一个怪需要消耗的血量，于是能砍死的怪物数量就等于自身血量除于需要消耗的血量，如果能整除则答案数减一，特判自身血量为0；复杂度： (1)。 Code： #include<bits/stdc++.h> #define ll long long #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; int t,n,m,a,b; int mai...

小结： 这个比赛最有意思了，对小白来说很友好，都是一些基础的算法，第一题就是我在学习前缀和的时候写过的，当时非常高兴直接秒提交了，E题打表简直不要太爽，就是题目长了点，还是不够冷静读题。传送门 题解部分 A、Maximize The Beautiful Value 题意： 输入t组数据，每组数据给定n个递增的数，选择任意一个数(必须在第k个数后面)向前移动k步，美丽值f就是每个数与下标之积的和，求最大的美丽值f是多少 难度： 前缀和的基础题。题目类型：前缀和 思路： 解法是前缀和。对比移动前和移动后美丽值f的表达式：5 31 1 3 4 5f=a1 * 1 + a2 * 2 + a3 * 3 ...

题目大意：给一个文本串和一个n，接着n个模板串，问文本串中是否有子序列和模板串相等 传送门 难度 暴力枚举一定超时的，要想到和AC自动机一样预处理的方法来优化暴力枚举 思路 预处理得到一个数组，从A数组的首字符开始获取B的首字符第一次出现的位置（如果第一个都不可以那么后面的也都不可以），再从这个位置开始找B下一个字符第一次出现的位置，一直下去直到失配或者匹配成功就结束了。在这里定义一个数组nt[i][k],k [0,26-1],表示a[i]之后第一次出现'a'+k的位置，还有数组last[i],表示'a'+1最后一次出现的位置，那么就要从后往前遍历A，同时维护a[i]; 复杂度： 直接暴力的复...