发表于

颓废好久
开始newtrain之后每道题都要写题解！！
区间限制数量是经典问题，向前连边即可
此题是求区间出现次数大于1的数的个数
两种求法：
1.对pre+1处-1,1处+1，query为左端点及其左的和，相当于对区间+1，要撤回操作。
2.对pre处+1，pre[pre]处-1，query为右端点-（左端点-1），相当于统计每个点对区间的贡献。
犯了一个小错误:把n和qn弄错了

阅读全文 »

发表于

1.点双的缩点 点双中的边全部去掉，连向一个新点
2.有向图至少加几条边变成强连通图
（易证明，无环的有向图至少存在一个入度为0/出度为0的点）先缩点，ans=max(入度为0的点数，出度为0的点数)（只有一个点说明已经是强连通图，要特判掉）
注意一个点的时候，是否算作强连通，要看题目！！
有向图至少加几条边使得每条边都在某个强连通分量内：和上面的问题一样，不过要把单点去掉。
3.无向图至少加几条边变成边双
先缩点，ans=ceiling(度数为1的点的数量/2)+度数为0的点的数量（特判只有一个点）
证明（简略）：一条边可以干掉两个叶子 叶子干光了就是双联通 一个点可以插入到一条边里去
无向图至少加几条边变成点双？
4.设f[u][i]为在节点u的子树内，费用限制为i的条件下能取到的最大价值
5.树上莫队
6.//return dcmp(cross(a-p,b-p))==0&&dcmp(dot(a-p,b-p))<0;//ac
return dcmp(length(a-p)+length(b-p)-length(a-b))==0&&!(p==a)&&!(p==b);//wa，误差巨大
7.double在g++中的输入是%lf,输出时%f。什么时候用什么？
g++中abs一定要有cstdlib，c++不用。
8.printf(“%.3f”,0);有错？
9.线和凸包是否有交、凸包和凸包是否有交
线和凸包：找线上一个远一些的点，找到两条切线，判断线是否在切线之间
凸包是否有交：？
10.点和凸包的切线
凸包外的点p向凸包上一点连线，有的是入凸包，有的是出凸包。则cross(a[i]-p,a[i+1]-a[i])的方向是不同的。找到最后一个入凸包的点，那么下一个点就是切点。左右切线找的时候只需要把方向判断反一下即可。
判断一个点在凸包内：找不到切线，即找不到入凸包的点。
11.二维区间和 树套树？
12.函数内新建pq？在函数结束时会自动清空吗 会吧
13.dp of dp
14.异或hash？ 冲突概率1/个数
15.并查集 撤销？拆并查集？不能拆
16.判断两个点在一个点的不同子树中？
17.矩阵转移？
18.决策单调性的写法
19.prufer编码
20.指针和迭代器
21.O(n)找第k大
22.遍历set是O(n)
23.long double怎么用啊
24.int128怎么用
25.float128怎么用
26.01覆盖问题是npc吗 反正不可做
27.保留x位小数变成-0.00000?

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
区间中有多少个数的题目
和pku的夏令营题目挺像的
这种题目好像都可以用差分约束做
不过卡时
这题spfa只能过6个点
d[i]表示从1到i的个数
d[i]和d[i+1]的关系为
d[i]=d[i+1]或d[i]+1=d[i+1]
拆成不等式为
d[i]=d[i+1] => d[i]<=d[i+1] d[i]>=d[i+1]
d[i]+1=d[i+1] => d[i]<=d[i+1]-1 d[i]+1>=d[i+1]
合并为下面两个（若a<=b，则要让b尽量大）
d[i]<=d[i+1]
d[i]+1>=d[i+1]
初始情况为d[0]=0，其他无穷大
（
松弛大于n次就有负环一点都不靠谱，随便构造出反例
入队大于n次才是正确的，因为
假如没有负环，bfs一层就能至少确定一个点的dis
所以最多做n(其实n-1，但是要考虑1个点)轮，>n就无解(其实>=n)
每个点在每一层最多入队1次(可能被松弛很多次)
所以入队次数大于n就无解
）
正解dp
f[i]表示前i个已经满足条件，第i个放了的最大个数
f[i]=max(f[j])+1
j的范围是关键
设i对应的j满足l[i]<=j<=r[i]
有且只有1个这个条件拆成
至少1个和至多1个
l[i]为区间右端点在i左边的左端点的最大值（因为至少1个）
r[i]为i所在的区间的左端点的最小值-1（因为至多1个）
注意到l[i]和r[i]都是单调不降的
所以转移可以用单调队列优化
求l[i]和r[i]也可以利用单调性的特点做到O(n)
阅读全文 »

发表于 
1
2
3
简单的dp
对于已经走过的区域，不管有没有选择，都不会管了
对于当前的i和j，一定是考虑选这个i或j，而不是之前的（因为之前的在之前被考虑）
阅读全文 »

发表于

我的dp实在太差了（不忍直视
写一个总结和提醒一样的东西（不定时更新

dp的几个重要的东西
状态（纬度，空间时间，哪些状态合法）
转移（转移条件，转移范围，转移顺序，所有合法状态要被考虑）
初始状态（边界）
最终状态（目标）
确定的顺序应该是从上到下

把做得不顺的题记下来

luogu2157 [SDOI2009]学校食堂(状压)

调了好久
错误在于两个细节
一是for(int j=0;j<256;++j) 0="" 1="" 3="" 4="" 这里我一开始写成for(int="" j="0;j<(1<<(b[i]+1));++j)" 这样写的话会少考虑很多情况="" 一旦当前i用过后，后面的值是可以取的="" 我想的是这些状态在i+1的时候会被考虑(?="" （="" dfpmts熬夜搞明白了原因orz="" 比如b[]="3" 顺序可以为2="" 但是在处理2的时候只会考虑1="" 2取了，3="" 4没取的情况="" 合法的状态在转移后没有被考虑="" 这就是我错误的原因="" ）="" 二是枚举下一个选取的位置的时候="" 应该判是否与没有出现过的点冲突="" if(((t="">>(i-x))&1)==0&&i+b[i]<y) return 0;
前一个判断不能少

单调性

[USACO13OPEN]照片Photo

等于可以拆成两句话，大于等于和小于等于
有单调性的话很多都可以O(n)做了

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
好题
发现了两个v的做法
但是没发现一个v的
按照之前的思路死活做不出来，这时候要跳出之前的思维模式（重点！重点！重点！）
不再是按照对位的边形成的树上找了
而是考虑有没有环
题解：
1个v：现在题意变成了要求多组单向可达关系加最少有向边的问题。考虑每
个弱联通子图，如果是个dag的话最少需要v-1个魔法（构造方法：用链将拓扑序串起
来），否则的话至少需要v个魔法（一个大环）。然后加起来就好了。
发现不会找弱连通子图哇哇哇
dfs3+dfs2，再开两个vis数组
丑的不行的代码
阅读全文 »

发表于 
1
2
3
4
5
6
7
风吹云走
其实云是不动的
是月亮在走
这就是第一步
然后将时间作为第二轴画出来
A picture is worth a thousand words.
阅读全文 »

发表于 
1
2
3
4
5
6
序列自动机本质上就是dp
所以这题考虑dp
f[i]表示到以i结尾的子序列的合法的概率数
c[i][ch]表示到第i位为止没有用到的ch全被删除的子序列的合法的概率数
发现c的第一维无意义可以省去
dp的含义要搞清楚
阅读全文 »