Tree 前言 树上启发式合并好啊，可惜还不太会啊 分析 1.凡事始于朴素：根据题目，我得在每一个子树内部去寻找答案。假设是这样的一棵树。首先在3节点的子树中去找，首先遍历4节点，统计一下，这时的lca是3，记录一个k并求出 表示另一个数的出现次数，同时 。然后去到5节点,同样的，首先找到满足 的数的个数，同时将 。然后进入10号节点....这个时候我们发现已经统计完了3节点的子树，向上走一步同时vis数组清零，到达2号，根据统计3节点子树的方法一样，先把3节点所有子树加入贡献(注意，是把vis清零后再重新跑一遍3节点的子树)然后再进入6节点，统计答案.... 2.会发现，有许多不...

最优的连续子段 分析 因为是区间问题，我们先选择一个定点，即枚举右端点r，那么我们要求的就是左端点在[1,r]，出现次数为1的数字最大个数。具体看图假设当前已确定右端点r，且此时 ，可以确定，当左端点 时，这些区间中出现次数为1的数字的个数都会加1，而小于等于j的，就会全部减1 那为什么减一的区间是 ,明显，当右端点是j的时候，区间 已经被减过一次，自然不能再减 代码 #include<bits/stdc++.h> #define ls now<<1 #define rs now<<1|1 using namespace std; const in...

变强的秘药 分析 确定这是一个dp，设f[i]为吃完前i个秘药能增加的最大码力值，先写出暴力的转移方程 memset(f,-0x3f,sizeof(f));f[0]=0; for (int i=k;i<=n;i++) for (int j=i-k;j>=0;j--) f[i]=max(f[i],f[j]+a[i]*a[i-1]*a[i-2]-a[j+1]*a[j+2]*a[j+3]); 可以发现，当我们确定了一个i之后， 是不变的，如果要求最大，那么 就得最大。那不就完了吗？我们用一个数组p，令 ，然后每次更新因为要连续k个要一起...

每日咕咚 分析 考虑每一个人对答案的贡献。假设当前为第个人，那么我们肯定可以统计出他在所有位置跑到队首的总时间因为这个人的占位有n种情况，所以t还要除以n，所以再求一个总和即可 代码 #include<bits/stdc++.h> #define R register #define ll long long #define inf INT_MAX #define dl double using namespace std; const int N=1010; int n; dl x,v,ans=0.0; dl f[N][N]; int main() { s...

锯锯锯锯锯锯锯锯锯锯锯锯锯锯 分析 牛客评测机挺快。这道题，千万不要无脑开1e8的数组(比如我)，把所有的询问离线下来，以次数为关键字排一个序，然后就按顺序扫着走，记录答案即可 代码 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+10; const int mod=1e9+7; ll n,tot; ll ans[N],cnt[N]; struct nkl { ll x,id; }s[N<<2]; inline void add(l...

友人 分析 先掏出式子可以发现，如果确定了 的值，那么z的合法范围就可以求出来，并且 ,完全可以 枚举。接下来考虑右边的括号。首先我们已经有了z的范围[1,max]，如果k第i位为1，那么z的第i位在满足 的条件下也得为1，这样原式相当于就会减小 ,如果k这一位为0，z这一位也应为0，因为如果为1，根据异或的性质，前面的异或结果会增加 ，而后面的会减少 ，什么也没变，但是我z却变大了，不就亏了吗。 代码 /* (写点什么吧...) */ #include<bits/stdc++.h> #define R register #define ll long long #defin...

我是A题 分析： 还是一个贪心，能合并就合并因为一个子节点如果不符合条件，那么他一定会和他的根节点合并起来，不然就会不符合条件，也就是说，我们求出以每一个节点为根的子树内部的w值模k的总和,如果这个子树中的w值为0，说明他可以自成一体，不用再与父节点合并了，反之，则要加上那一条边 代码 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e6+10; ll n,k,tot,ans; ll h[N],nex[N<<1],ver[N<<1],pr...

除2！ 分析 贪心思路：每次选一个偶数出来，如何才能使总和的减少量最大？明显，取出最大的那一个偶数，除二，直到所有的数不能被2整除或是k=0 代码 /* (写点什么吧...) */ #include<bits/stdc++.h> #define R register #define ll long long #define inf INT_MAX using namespace std; const int N=1e5+10; int n,k;ll ans; priority_queue<ll>q; int main() { scanf("%d%...

dfs序专题 Before the content 很多好题 收获颇丰 something of dfs序 概念：在对树进行深度优先遍历时,对于每个节点,在刚进入递归后以及即将回溯前记录一次该点的编号，最后产生的长度为2*N的节点序列就称为树的dfs序 void dfs(int x) { a[++m]=x; v[x]=1; for (int i=h[x];~i;i=nex[i]) { int j=ver[i]; if(v[j]) continue; ...

CF786B 题意： 一张图上有 n 个点，现在做 m 次操作，操作总共有 3 种： 1 a b c： 从 a 到 b 连一条权值为 c 的单向边。(t=1) 2 a b c d：从 a 到 [b, c]中的每个点都连一条权值为 d 的单向边。(t=2) 3 a b c d：从 [b, c]中的每个点都往 a 连一条权值为 d 的单向边。(t=3) 最后给你一个起点 s 分析： n比较大，并且有区间建边的操作，抛弃 建边的思想。 那就通过数据结构实现区间建边。假设我们从 1 号点往 [2, 9] 中的点连边。我们需要线段树建一棵树，每个点可以到达它的两个子节点。因为是单向边，所以得建两棵...

B Load Balancing(Platinum) 前言 赛时发现此题没有太多AC，就先放着了，事后发现这的确是一道好题 分析 画个图了解一下题意设M为这四个区域中点数的最大数量，求一个划分方案是的M最小 正经东西：那么M=max(a,b,c,d)，如何求到每一个格子中点的数量呢？首先考虑简单一点的——如何维护一个范围内点的数量。这样肯定能用离散+树状数组维护。假设我们将坐标 y 离散，这个树状数组(1号)维护的是纵坐标小于等于 y 的点的数量，那么当前我们知道的即是 c + d ，a + b 。 但是不够啊，我得知道单个的QwQ，不然没法儿算。于是就来了一个方法——枚举横坐标x，将横...

Fence 分析： 暴力dp： 设f [ i ] [ j ] 为安排前 i 个工匠刷前 j 块木板 如果第 i 个什么也不做， 如果第 j 块木板可以空着不刷， 反之，枚举合法区间for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) f[i][j]=max(f[i][j-1],f[i-1][j]); for (int j=s[i];j<s[i]+len[i];j++)//枚举终点 for (int k=j-len[i];k<s[i];k++)//枚举起点 if(k>=0) ...

金字塔 前言 一大早上A了的第二道水题 分析 针对一类模拟(我也很少打)，可先判断题目中要求的最终结果，将抽象过程转化为实际朴素的过程，这个时候就不要考虑代码会码多长了，保持一颗清醒的头脑，理好思路 要输出一个图形，会发现每一层'*'的数量与' '都是有一定规律的，那就照着这个规律，那他们分别输出即可 代码 #include<bits/stdc++.h> using namespace std; int n; int main() { while(scanf("%d",&n)!=EOF) { int len=2*n-1; ...

小A与欧拉路 分析 欧拉路： 该路径经过图的每一条边且仅经过一次。如果路径起点和终点相同，则称“欧拉回路”。具有欧拉回路的图称“欧拉图”。 即因为要求最短，那么path(x,y)最长即可。就是一个树的直径的模板 代码 /*树的直径*/ #include<bits/stdc++.h> #define R register #define ll long long #define inf INT_MAX using namespace std; const int N=2e5+10; int n,tot,ans,sum; int h[N],nex[N<<1]...