scmmm's blog

个人认为比较好理解的线段树代码 因为是异或，并且只有1 和 0 两个状态，所以每次区间异或后，我们只需要把该区间0的数量和1的数量交换一下就好了。 另外注意pushdown是cg（change）需要每次异或一下，单纯的赋值会出现这种问题： 1^1=0 1^1^1=1 而单纯赋值，则会变成1^1^1出现0的情况。 另外没什么问题，很好的一道线段树题目 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293//头文件您就自己写吧 #define lson i*2,l,mid#define rson i*2+1,mid+1,r#define ls i*2#define rs i*2+1using namespace std;int n,m,a[200500];struct tree
...

智商不够线段树来凑 虽然是一个差分的裸题，但是线段树也是可以过的。 原来题解有篇动态开点的线段树，不过这道题直接离散化然后用线段树做区间修改即可。 对了，stl是个好东西，用对了代码短50行不是问题。 另外说一下，去重后不是在[1,n][1,n][1,n]中排，而是对问题的不同区间端点排序。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include<touwenjian.h>// 由于每次都卡我头文件，所以我不打了#define lson i<<1,l,mid#define rson i<<1|1,mid+1,r#define ls i<<1#define rs i<<1|1using namespace std;int n,m;struct tree{ ...

看了下题解，发现思路和其他题解大佬们的都不一样啊 本题是一个简单的模拟题。 需要注意的几个问题： 1.for 循环里面 n在右边才能算 是不是感觉很玄学啊，然而的确是这样的，如果n在左边的话就说明n小于这个常数于是者就变成了常数级别的算法。 但是搞不清楚这样这么处理，不过CCF也应该注意到了这个问题，于是数据没有太毒瘤，比如以下这种 1 4 O(n^1) F i n 3 F j 4 n E E 按道理答案既可以是O（1）也可以是O（n^1）,很奇怪的是，我的代码如果是O（1）也能输出Yes，O（n^1）也能输出Yes，第一篇题解是O（1）才能输出yes 这个东西太玄学了，这个O(1),O(N)也是要看N的 2.循环变量名怎么判断重复。 目前看起来循环变量名只有一位，本人在做题的时候感觉有可能出现好几位的变量名（毕竟长度不超过100），于是写了个哈希。 其实只需要加一个标记数组标记一下就好了。 3.循环结束后怎样取消被标记的变量 开一个栈，随着循环F加到栈顶E弹出栈的时候同时取消标记即可。 其实这块地方我用了两个栈，第一个（st）存变量名，第二个（looker）存这个变量是否对这个循 ...

开头扯蛋 DP的骚操作太多了，和 线段树一样。 因此本文带你看一些dp好题。 正文部分 一.普通的 DP LCS/LIS问题 LIS 原来的f[i]f[i]f[i] 表示的是$ [1,i] $的LIS 现在改一下，用$ f[i] $ 表示 长度为 iii 的LIS 最后结尾的最小值。 此时贪心，i从前向后枚举。 加上一个当前长度的变量k AAA 为原来的数组 构造出以下代码 getplace是指找fff中第一个大于等于a[i]a[i]a[i] 的位置 123456789int a[],f[]; register int i,j; int k=1; f[1]=a[1]; for(i=1;i<=n;i++) { if(f[k]<a[i]) f[++k]=a[i]; else f[getplace(a[i])]=a[i]; } LCS 和LIS的处理很像，只需要加一个标记数组map $map[a[i]] $指向 $a[i] $ 在 a的位置 (听起来很傻) 然后就可以用 map[b[i]]map[b[i]]map[b[i]]来表示LIS代码中的AAA ...

UVA12511 Virus 一个O(N2)(N^2)(N2)的 LCIS DP f [i] [j] 为 A的前i个元素和B的前J个元素的LCIS。 O(N3)(N^3)(N3) 做法： 此时的代码 12345678910for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(a[i]==b[j]) { for(k=0;k<j;k++) if(a[i]>b[k]&&f[i][j]<f[i-1][k]+1) f[i][j]=f[i-1][k]+1; } else f[i][j]=f[i-1][j]; } 优化思路 发现f[i−1][k]f [i-1] [k]f[i−1][k] 被 重复访问了多次。 因此我们的思路是让k=[1，j）k=[1，j）k=[1，j），每个k只访问一次 因此我们可以找到之前最大的f[i−1][k]f[i-1] [k]f[i−1][k] 令它为mxmxmx 接下来只需要判断A[i]是否比B[j]大，如果大了，就尝试更新 mx=max( ...

这道题做的我 七窍生烟 半死不活 怒斥UVA无人性 明白了longlong 的重要性 题目大意 给一个真分数a/b,把他拆分成1/x1+1/x2+1/x3…… 若有多种情况，输出拆分出分数最少的一种 如果还有多种情况，输出分母第一大最小，如果还不行，第二大最小，以此类推。 第一行输入数据组数 t 注意，每行输入这几个数 ： 分子a 分母b 不能用的分母k个 然后后面会有k个不能用给的整数 解题过程 被卡了两个半小时，代码越来越题解化。 不过下面那个题解没说的太清楚，这里附上几个证明。 证明1. 分母下界取值 ∵ a/b 为真分数 ，a,b,k均为整数 ∴ a<b 设正整数x,y ax+y=b 发现 floor(b/a)=floor( (x * a+y) /a )=floor(x * a/a)+floor(y/a) = x 以及 floor(b/a)<=b/a ∴ floor(b/a)=x ∴ x+1 > b/a , ∴floor(b/a)+1>b/a ∴ 1/(x+1) < a/b 又 1/floor(b/a)=1/x & ...

数学 多项式 拉格朗日插值 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include<iostream>#include<cmath>#include<stdio.h>#include<cstring>#include<queue>#include<stack>#include<vector>#include<set>#include<map>#include<algorithm>#define int long long using namespace std;const int maxn=5050;const int modp=998244353;int h[maxn],y[maxn]; int n,m,ans;inline int ksm(int x,int y)&# ...

前言 侧边栏炸了 短期的目标 笛卡尔树 容斥 带标号联通无向图计数 带标号欧拉图计数 dp套dp 斜率优化dp 树剖换根 很多数据结构 数据结构 树剖 实质 是一个重链剖分，寻找lcalcalca的时候每次规模减半，故时间复杂度O(nlogn)O(nlogn)O(nlogn) 用处 求lcalcalca或者水LCTLCTLCT的部分分 操作 dfs1dfs1dfs1 得到深度关系以及重儿子，父子关系 dfs2dfs2dfs2 进行剖分，得到重链 换根 本质上并不需要换根，我们完全可以用之前求得的id序列来描述这个树，因为重新换根来重建这棵树是完全没必要的(在复杂度上面不太占优势) 首先我们考虑换根后怎么求得lcalcalca，显然是可以 线段树 主席树 beautiful pair 题意就是找到满足 形如 al∗ar<=max⁡i=lraia_l*a_r<=\max\limits_{i=l}^{r}a_ial​∗ar​<=i=lmaxr​ai​ 的个数 题面的确挺简洁，然而想了好久也不知道怎么做，因为要考虑 ai,aj,amaxa_i,a_j,a_{max}ai ...