这是蒟蒻在摸鱼许久之后的题解(图论还是不会....A这是一个签到题 思考移动会带来哪些影响后有了以下思路先求出未移动的美丽值和a[i]的前缀和经思考证明（贪心思路） 把所有向前移动k步的值算出来 最大的即最大美丽值算的过程依靠之前求的 当你移动时是相当于有一部分没动 有一部分增加了一倍 等等建议不懂的手动推导下 #include <bits/stdc++.h> #define ll long long using namespace std; int const maxn=1e5+5; ll n,k,a[maxn],t,cnt[maxn],ans,z; int main() { s...

这是紫书上的一道经典题（是道比较简单的队列题我们使用两个优先队列 一个存较大的一半 一个存较小的一半保持两个队列数量相等或者差一：：记得每次要清空队列：： #include <bits/stdc++.h> #define ll long long using namespace std; priority_queue <int,vector<int>,less<int> >a; ///从大到小 顶端为最大的 priority_queue <int,vector<int>,greater<int> > b; //...

这是一个用树来提升难度的贪心题（蒟蒻理解首先当你来到一个新节点时有两种情况1、此节点能被已染色的子节点覆盖 这时只要更新理论最大覆盖范围2、此节点不能被已染色的子节点覆盖 选择那个提供最大覆盖范围的子节点染***r>菜鸡的其他理解全在代码里面了QAQ #include <bits/stdc++.h> #define ll long long ll const maxn=1e5+5; using namespace std; struct M{///链式前向星存图 ll to,next,val;///终点，同起点的上一条边的编号，边权 }edge[maxn<<1];...

这题是一个树上二维dpdp[i][j] 表示从某个叶节点出发包括i个点 涂j种颜***r>当你加一个点时只有两种方式 涂用过的 和 没用过的涂同样的颜色只能跟父节点以上相同 所以为 dp[i-1][j]涂不同的颜色可能从未涂过的颜色中选 所以为 (k-j+1)*dp[i-1][j-1]注意随时取模 #include <bits/stdc++.h> #define ll long long using namespace std; ll const maxn=3e2+5; ll const mod=1e9+7; ll n,k,ans,dp[maxn][maxn]; ///dp[...

蒟蒻的学习题解这题一开始我是只会暴力求每个数的约数的 然后肯定超时了经学习后 我写出了以下程序主要用了分段处理和把区间转化 x/i就是1-x中含有i的因数的数的个数（重点）详细的解释在代码里 #include<bits/stdc++.h> using namespace std; #define ll long long ll l,r,ans,s,w; ll f(ll r,ll x) ///x/i就是1-x中含有i的因数的数的个数 { ans=r/x; ///计算当约数最高位为x时的次数 s=x*10,w=min(r,x*10+9); ///确定区间上界和下界 s 下 w 上 fo...

这题咋一看以为是图论题 在看n个点与n-1条边那就是树了 题目要分成两边后边权最小首先我们分析是平均分 那么一棵树的子树（包括他自己）是奇数的话 一定有一个点被分给另一边然后再结合样例手动推到 当一颗树的子树是奇数那么他父亲节点的边权值一定会被用到于是程序就出来了 统计子树节点 判断是否为奇数 然后决定是否加入答案代码有详细注释 #include <bits/stdc++.h> #define ll long long using namespace std; #define inf 1e18 ll const maxn=2e5+10; struct M{///链式前向星存图 ll...

这是一道简单的字符串题目我们用一个二维数组来记录字符每个位置 并用来比较 #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e6 + 7; char s[maxn]; int pos[maxn][30]; ///pos[i][j] 表示i位置后j字符首次出现的位置 int main(void){ scanf("%s", s+1); int len1=strlen(s+1); for (int i=len1-1;i>=0;--i) { for (int j =...

这题乍一看是一个图论 我不会啊啊啊 但看到m=n-1 发现这是一颗树 要度为一 百度一下发现树上度为一的节点那就只有叶节点了 于是这变成了一个树上dp（因为是求最优解）如何不能到达 那就是切直接连的边或者子节点的边 求最小就判断一下谁更小就切谁于是这个题就出来了 代码有详细注释QAQ 使用链式前向星存图  #include <bits/stdc++.h> #define ll long long using namespace std; #define inf 1e18 ll const maxn=2e5+10; struct M{///链式前向星存图 ll to,next,val...

这题一看 图论题 不会…… 那咋办呢 只能慢慢看 慢慢学然后发现这题好像是使用了倍增数组的相关知识（这个还是有点熟的 学lca的时候弄了半天）这题的关键就是那句 保证 v 在 u 前往首都的最短路径上 （v一定是u的祖先）于是那个熟悉的方程就出来了 f[i][j]=f[f[i][j-1]][j-1]这题具体实现如下（附备注）输出方式还是坑了我一次（傻傻的输出的空格.....） #include <bits/stdc++.h> #define ll long long using namespace std; int const N = 2e5 + 5; int n,q,val[N]...

这是单调队列的模板题 #include <bits/stdc++.h> #define ll long long using namespace std; ll const maxn=1e6+5; int a[maxn],q[maxn]; int main() { int n, k; scanf("%d%d", &n, &k); for(int i=1; i<=n; i++) scanf("%d", &a[i]); int h=1, t=0; for(int i=1; i<=n; i++){///维护最小值 while(h<=t&&...

本蒟蒻这次只过了三题 赛后学习了一下出题人巨佬的标码(码风比我好多了 贴的代码有些是仿出题人)现在将自己的理解写下来与大家分享博客相同题解 https://www.cnblogs.com/yurenwuyu/A这个题一分析就是每个数字都会与所有数字&一下 (a&a=a)&字操作是二进制同位都为一才为一 这时解法就变成统计每个二进制位上1的次数  #include<bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 1e5; const ll maxm = 30; l...

                                       平面最接近点对&&二维凸包&&最小覆盖圆  模板   首先要知道两个基础知识   叉积与基础运算符重载   二维叉积可以用来判断点与点的位置关系与面积  （三维叉积可算平面的法向量）   这些模板都是二维的  我想想看能不能化为三维的题 空间最小点对 三维凸包 最小覆盖球   例题   P4894、 P3744、P2785               平面最接近点对模板讲解       最容易想到的方法是n2暴力法  但一分析数据范围就会发现肯定会t  于是我们有了下面一个思路  先将...

搜索是一种及其基础的算法 掌握其基本内容是必要的  而其衍生的题目也可以十分复杂 光看是不行的 所有每种题目后面我都推荐了一些题目 其实搜索考的是思维  引用黄大佬的说法就是结构简单就思维难  因为基本套路大家都知道 搜索其实是一种相当暴力的思路 枚举所有状态来找出其中符合题目要求的并记录下来  搜索的方法有DFS（深度优先搜索）、BFS（广度优先搜索）、二分搜索、双向搜索、启发式搜索等等 洛谷 P1665、P1019、P1088 DFS的基本过程其实相当于走迷宫时你朝着一个方向走 如果是死路就返回到最近的岔路口选择另一个方向 直到你到达了出口 其缺点是显而易见的  会花费大量的时间 这时就需...

我（菜鸡）的想法是先从起始点开始扫描然后直到有字母达到k个 达不到就输出-1用数组储存字符个数 用ans记录最短长度然后维护这一子串 从起始点开始删减字符 直到不满足 从终止点添加字符直到满足如此重复这样把字符串走完 最短长度就出来了 蒟蒻的代码 #include <bits/stdc++.h> #define ll long long using namespace std; ll n,k; ll q[1000]; string a; ll ff() { for(int i='a';i<='z';++i) if(q[i]==k) return 1; return 0; } ...