Fujihara's Blog

「余計な霊魂は全て斬る!」 && 博客的代码块渲染炸了,直接点Copy按钮复制下来的是没问题的。

Fujihara's Blog

Better reading experience?

某些恶心题就不补了

Codeforces #734

在学校和整个机房一起VP的。

A

一眼题。

要 $|c_1-c_2|$ 最小说白了就是尽量平均。

那么就尽量的用一个 $1$ 的同时也用一个 $2$。

所以把 $n$ 除以 $3$,得到 $c_1$ 和 $c_2$ 各自必须要有的个数(此时 $c_1=c_2$)。

然后 $n$ 无非就是剩下 $0,1,2$ 这三种情况。

如果不剩那么直接输出。

如果余 $1$ 那么多加一个 $1$ 元。

如果余 $2$ 那么多加一个 $2$ 元。

B1

首先考虑第一个条件。

转化一下也就是说每一种字母最多只能有两个被涂上颜色。

所以我们开一个桶统计一下每一个字母的出现次数并对其进行判断。

再考虑第二个条件。

因为只会有两种颜色,所以涂上颜色的点的个数必须是偶数( $2$ 的倍数)。

那么思路就出来了,统计一下每一个字母出现的次数,并且统计它最多有多少个字母可以被涂上颜色。

对于每一种字母,如果它的个数小于等于 $2$ 那么就都可以被涂色,如果大于等于 $3$ 就只有两个可以被涂上颜色。

因为有两种颜色,所以答案就是可以被涂上颜色的字母个数除以 $2$。

如果最后可以被涂上颜色的字母个数是个奇数,就需要先减 $1$ 再除 $2$。

B2

从B1的角度考虑,现在有 $k$ 种不同颜色。

我们仍旧是统计每一个不同的元素出现多少次。

如果大于 $k$ 那么就只有 $k$ 个可以被涂色。

反之都可以。

然后统计完之后我们按 $a[i]$ 的大小排个序。

也就是把同一种都扔到一起处理。

对于每一种,我们只涂前 $k$ 个(保证不重复而且涂够),就可以了。

但是我们要输出方案,所以需要记录一下元素的位置。

C

看到只有五个字母,我直接高兴了起来。

看到时限4s,我的嘴角就直接扬了起来。

这不明摆着让你打暴力吗?

所以直接统计每个字符的出现次数。

然后对于每种字符我们排序贪心一下,如果说可以选当前单词,即更新答案。

(说是简单暴力+贪心,我却写了半小时,wtcl)

D1 D2 E F

待补

Codeforces #735

五题场,我居然有ABCD。

A

问你一个序列的所有长度不小于 $2$ 的子区间的最大值和最小值乘积的最大值

从数据范围就能发现,一定是个 $\text{O}(T\times n)$ 的算法。

所以想到了单调队列或者单调栈维护。

但是仔细想想,这个子区间的长度只能为 $2$。

为何?

我们就先从长度为 $2$ 的区间开始考虑。

那么很明显权值就是 $a[l] \times a[r]$ 。

考虑一个长度为 $3$ 的区间,且里面的元素是 ${a,b,c}$ (按顺序)。

  • 假设 $b$ 是最大的,那么它就会和 $\min(a,c)$ 结合,那么就和长度为 $2$ 的没有任何区别。

  • 假设 $a$ 是最大的,那么有如下两种情况。

    1. $b$ 比 $c$ 小,那么这个区间的权值一定是 $a \times b$ ,转化成了长度为 $2$ 的情况。
    2. $b$ 比 $c$ 大,那么这个区间的权值就是 $a \times c$ ,但是很明显, $a\times b $ 也就是长度为 $2$ 的时候绝对比这个 $a\times c$ 更优(因为我们最终要求的是最大值)

反过来同理,然后把这个结论扩展到 $n=4,5,6…$ 就能证明结论正确。

所以现在只需要读入的时候让相邻的元素两两相乘,求乘积的最大值,这个最大值就是答案。

B

待补

C

待补

D

我目前做过最傻逼的构造。

容易发现 aaba+k 形式的构造是对的。

就是前面一段 a 比后面一段多一个,然后在中间插一个 b

如果 n 是奇数在后面补一个非 a\b 的字符就行。

注意特判 $\text{length}=1$

E

待补

Edu #112

A B C D E F

待补

Codeforces #736(div1+2)

其他的根本不会

div2A

傻逼送分题。

让你找一对 $(a,b)$ 满足 $a \operatorname{mod} P = b \operatorname{mod} P$

$P$ 是一个大于等于 $5$ 的质数。

所以 $P$ 不可能是偶数,也就是说 $P-1$ 一定是偶数。

那么直接找 $P-1$ 的随便两个大于等于二的因子。

为了方便直接输出 $2$ 和 $(p-1)/2$ 即可。

div2B

依旧是送分题。

考虑一下可以发现对于在第 $i$ 列的卒要想到达对面一定满足一下两个条件:

  • 第一排的第 $i$ 列没有敌兵,直接走过去即可。

  • 第一排的第 $i-1$ 或 $i+1$ 列有敌兵且之前没有我方兵去吃。

然后稍微模拟一下就行了。

div1A

待补

div1B

待补

根据个人写题的错误累计更新,感谢Imakf,他所撰写的博客激发了我的这个想法。

转载,引用注明链接(qwq)

Better reading experience?

如果有自己犯过的SB错误都可以评论在下面,一起学习(

灵感来源:https://www.luogu.com.cn/blog/Imakf/oier-cuo-wu-ge-ji

(人家↑是通用版,我就只能写这种菜鸡才会犯的错误)\kk

有一些引用注明了提出错误的OIer【一部分来自Imakf的博客评论区】。

如果您的名字在上面并且您不希望被写在上面可以联系我,我会第一时间删除。


ntmd

解决利器:-Wall

  • for(register int i=e[u].head;i;i=e[**u**].Next)

  • for(int i=1;i<=n;++i) for(int j=1;j<=m;++i)

  • for(int i=1;i<=n;--i) [From 路卡利欧 ]

  • 多组数据不清空型

    • 图论题不清 cnthead
    • 数组不清 0
    • vector 不 clear()
    • 线段树 tag() 不清零。
    • for(1->n) 清零,init却写在读入 n 的前面。
  • 段错误(RE)型

    • 数组开小
      • 线段树四倍空间
      • 树的两倍空间
      • 无向图的两倍空间
    • scanf() 不是读字符数组但是不写 &
    • long long 开了吗?
    • 负数考虑了么?
    • 最简单的矩阵类型dfs不写continuereturn (没写边界)
  • printf 写了一个 &

  • queue 和 stack 不写 pop

  • operator 不写 const

  • vectorsize() 不写 (int) 然后就减了一个数。

  • tmp[i]++=cnt[j]-- (垃圾UB)

  • POJ交 bits/stdc++.h

  • 你写线段树 pushdown 了吗?

  • Trie 树的 insert 写成这个鬼样子:

    for(register int k=0;k<len;++k){
    int ch=str[k]-'a';
    if(trie[p][ch]==0){
    trie[p][ch]=++tot;
    p=trie[p][ch];
    }
    end[p]=true;
    }
  • Tarjan 的 dfn[u]==low[u] 写到了 for 里面去。

  • 写树形DP的时候不写 vis 或者 if(v==fa) continue;

  • 单调队列写成:

      	while(head1<=tail1 && q1[tail1]+k<=i) head1++;
    while(head1<=tail1 && a[i]<=a[q1[head1]]) tail1--;
  • 缩完点之后如果可能有重边判了吗??!!!11 [From leexzq & NGC5457]

  • 自环判了吗?

  • heap-dijkstra 不写 -dis[v](贪心变谦虚)**[From leexzq]**

  • 到底是 scanf("%d%d%d",&n,&m,&q); 还是scanf("%d%d%d",&n,&m,&q);还是scanf("%d%d%d",&q,&n,&m); ??(读题)。

  • 线段树合并,如果你的merge返回类型是int那么一定记得root[x]=merge(root[x],root[y]),必须加前面的root[x]= [From tongyf]

  • ans[siz][2] ,for(i,1->n),printf("%d ",ans[1][i]);

  • dep[1]没设为1,dfs的时候忘记 dep[v]=dep[u]+1

  • int a[siz][0];

  • f[i][j]=clac(f[i-1][j-pos[i]],f[i-1][j],w[i]) mod 0

  • printf("%d",x/0);

  • unsigned long long qwq; 然后 printf("%ull",qwq);

(实际上是 %llu

  • 库函数自带maxmin 要求两个参数变量类型相同。

  • int time,y1;

  • OLE型

    • 您调试的代码删了么?
    • if(!cnt[i]) cout<<cnt[i]<<" ";,您的代码真的能保证该是 0 的是 0 吗?
  • 读一个 n*m 的矩阵:

    for(i;1->n)
    for(j;1->n)
  • Linux\POJ 下使用 INT_MAX 但不写 #include<climits>(万能头再见)

  • 要求 $\min$ 却res=INT_MIN ,要求 $\max$ 却 res=INT_MAX

  • int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    for(int k=1;k<=n;++k)
    {
    在这里忘记循环变量,试图调用输入的k
    }

[From 天机星(pxz)]

  • UB+O2 -> MLE [From 天机星(pxz)]

  • long long n;scanf("%d",&n);

  • 位运算不知道运算优先级的情况下不打括号。

  • 分类讨论题不考虑特殊解导致的做法出错。

  • 1ll 乘了吗?

十分感谢 $\texttt{darkbzoj}$ 所提供的的数据qq

没有这个数据我估计调不出来。

description

描述
欢乐岛上有个非常好玩的游戏,叫做“紧急集合”。在岛上分散有 n 个等待点,有 n−1 条道路连接着它们,每一条道路都连接某两个等待点,且通过这些道路可以走遍所有的等待点,通过道路从一个点到另一个点要花费一个游戏币。
参加游戏的人三人一组,开始的时候,所有人员均任意分散在各个等待点上(每个点同时允许多个人等待),每个人均带有足够多的游戏币(用于支付使用道路的花费)、地图(标明等待点之间道路连接的情况)以及对话机(用于和同组的成员联系)。当集合号吹响后,每组成员之间迅速联系,了解到自己组所有成员所在的等待点后,迅速在 n 个等待点中确定一个集结点,组内所有成员将在该集合点集合,集合所用花费最少的组将是游戏的赢家。
小可可和他的朋友邀请你一起参加这个游戏,由你来选择集合点,聪明的你能够完成这个任务,帮助小可可赢得游戏吗?
输入格式
第一行两个正整数 n 和 m,分别表示等待点的个数(等待点也从 11 到 nn 进行编号)和获奖所需要完成集合的次数。
随后 n-1n−1 行,每行两个正整数 a,b表示编号为 a 和编号为 b 的等待点之间有一条路。
随后 m 行,每行用三个正整数 x,y,z表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。
输出格式
输出共 m 行,每行两个用空格隔开的整数 p,c。其中第 i 行表示第 i 次集合点选择在编号为 p 的等待点,集合总共的花费是 c 个游戏币。
Input
6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
Output
5 2
2 5
4 1
6 0

Hint
1<=x,y,z,n,m<=5e5

solution

说实话这个样例给的真的很有迷惑性。

WrdCpd.png

这个数据(↑)让我以为 $lca(x,lca(y,z))$ 就是 $p$。

(当然也因为我没认真读题)

后面手玩了一组数据:

然后回去看样例发现,诶不对啊。

为什么 query_p(4,5,6)=5

然后发现这个是在中间的.

于是我觉得要看三个 $\texttt{LCA}$ 里面 $depth$ 最大的那一个。

为什么?

WrBb4O.png

如图,绿边是真正的树边。

很明显我们不是去 $lca(x,y)$ 集合就是去 $lca(x,z) \operatorname{or} ,lca(y,z)$。

那么边 $,alpha, beta, ceta$ 边都是必须走的。

相当于先让 $x,y$ 跳到 $lca(x,y)$ ,让 $z$ 跳到最上面那个公共的 $\texttt{LCA}$

但如果让 $x,y$ 同时去最上面的话,$c$ 会加上 $2\times delta$。

如果只让 $z$ 到 $lca(x,y)$ 的话只会加上 $delta$。

明显更优,所以集合点 $p$ 是深度更大的 $\texttt{LCA}$。

那么就把 $x,y,z$ 的 $depth$ 分别和这个 $depth$ 最大的的 $\texttt{LCA}$ 的 $depth$ 分别作差然后求和。

(相等就特判)

于是又挂了 cy

画了下面这个图之后我分析了一下:

WrdpfH.png

假设查询是这样子的

WrdhjI.png

很明显 $depth$ 最大的那个 $\texttt{LCA}$ 是 $y$

但是 $depth[z]=depth[y]$ ,而实际上 $z$ 还要先到 $root$ 再到 $y$去,。

所以深度相等的时候直接减会错。

要稍微改写一下式子。

那么设 $depth$ 更大的 $\texttt{LCA}$ 为 $p$,

设 $lca(x,z)=rxz,lca(y,z)=ryz,lca(x,y)=rxy(p)$

$c=c_x+c_y+c_z$

$c_z=dep[z]-dep[root]+dep[p]-dep[root]$

$c_x=dep[x]-dep[p]$

$c_y=dep[y]-dep[p]$

那么

$c=dep[z]-dep[root]+dep[p]-dep[root]+dep[x]-dep[p]+dep[y]-dep[p]$

$=dep[x]+dep[z]+dep[y]-dep[p]-2\times dep[root]$

所以

$c=dep[x]+dep[y]+dep[z]-dep[p]-dep[ryz]-dep[rxz]$

$c=\sum_{i \in {x,y,z}} dep[i]-\sum_{j \in {rxy,rxz,ryz}} dep[j]$

因为 $x,y,z$ 的顺序不影响式子(只需要在code里判一下),所以这就是通项公式。

那么代码就很简单了


#include<bits/stdc++.h>
using namespace std;

const int si=5e5+8;
int n,m,root;
struct Tree{
int ver,head,Next;
}e[si<<1];
int cnt=0;
void add(int u,int v){
e[++cnt].ver=v;e[cnt].Next=e[u].head;
e[u].head=cnt;
}
int dep[si];
int f[si][20];

void dfs(int i,int fa){
dep[i]=dep[fa]+1;
f[i][0]=fa;
for(register int j=1;j<18;++j){
f[i][j]=f[f[i][j-1]][j-1];
}
for(register int j=e[i].head;j;j=e[j].Next){
int v=e[j].ver;
if(v==fa) continue;
dfs(v,i);
}
}

int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(register int i=19;i>=0;--i){
if(dep[f[u][i]]>=dep[v]) u=f[u][i];
}
if(u==v) return u;
for(register int i=19;i>=0;--i){
if(f[u][i]!=f[v][i]){
u=f[u][i],v=f[v][i];
}
}
return f[u][0];
}

pair<int,int> query(int x,int y,int z){
int p,c;
int rxy=lca(x,y),rxz=lca(x,z),ryz=lca(y,z);
int mx=max(max(dep[rxy],dep[rxz]),dep[ryz]);
if(rxy==rxz && rxz==ryz) p=rxy,c=(dep[x]-dep[p])*3;
else if(mx==dep[rxy]) p=rxy;
else if(mx==dep[rxz]) p=rxz;
else if(mx==dep[ryz]) p=ryz;
c=dep[x]+dep[y]+dep[z]-dep[rxy]-dep[ryz]-dep[rxz];
return make_pair(p,c);
}

int main(){
scanf("%d%d",&n,&m);
for(register int i=1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs(1,0);
for(register int i=1;i<=m;++i){
int p1,p2,p3;
scanf("%d%d%d",&p1,&p2,&p3);
pair<int,int>ans=query(p1,p2,p3);
printf("%d %d\n",ans.first,ans.second);
}
return 0;
}

「冥界の土地も有限よ、余計な霊魂は全て斬る!」

单调队列

单调队列是一种神奇的数据结构。

一般我们用来优化这一类决策有单调性的问题:

比如:一个元素很明显不可能进入决策的时候,我们可以用单调队列来做到 $\text{O}(1)$ 的决策。

这里来一道题(来自WC2016 by 宋新波)

c4rLCV.png

这里相当于是在保质期之内,求每一天最大能吃到的值。

这里考虑维护一个队列,队列当中单调不上升。

那么队头就是我们所想要的结果(最优)。

  • Day1:
--------------
80
--------------

这里队头是80.

  • Day2:
-------------
80 75
-------------

这里队头仍然是80.

  • Day3

这里开始就要注意了,我们放入78,但是放进去之后就不满足条件了。

为什么?

不是因为后面小了就是前面大了(这里是单调不上升所以是这样,其他同理)。

不过我们一般考虑后面小了(从后面进队出队)。

那么在插入78 之前,我们就要弹出75 (从后方)

-------------
80 75(pop) --->
-------------

-------------
80 <------ 78(push)
-------------

-------------
80 78
-------------

此时队头仍然是 80。

这里我们不难看出,如果存在 $a_i <a_j$

那么 $a_i$ 一定会被 $a_j$ 替换掉。

因为 $a_i$ 不仅时间靠前(更快过期),价值也不大。

所以 $a_i$ 就是 冗杂的多余决策。

那么单调队列在维护的时候的意义就是去除这些冗杂的元素。

因为每个元素只会入队一次(所以要小心某些题的条件),所以 复杂度是 $\text{O}(n)$ 的。

  • Day 4
-------------
80 78 73
-------------
  • Day 5

这里根据 Day3,我们需要把78,73弹出来让更好的 79 入队。

所以队列就变成了这样:

-------------
80 79
-------------
poped:78 73

但是注意!这里80过期了,所以要把80也弹出(从队头弹出)

那么就是这样的:

       -------------
<---80 79
-------------

所以第五天就是 79 为最值。

那么我们就可以知道,在这道题使用单调队列时,要注意一下几点:

  1. 队列中始终单调

  2. 队首为最优情况

  3. 及时去除冗杂情况

那么我们每一次循环的时候,都检查一下队首是否过期还有新入队元素会不会造成更新就好了。

总结一下:也就是这样的

c4cvJ1.png

这里给出维护一个长度为 $k$ 的滑动窗口中的最值的代码。


#include<bits/stdc++.h>
using namespace std;

const int si=1e6+10;
int n,k;
int a[si];

int q1[si],head1=1,tail1=0; //这样子赋值是为了让第一个元素能入队。
int q2[si],head2=1,tail2=0;
int ans[si][2]; //0->min 1->max

int main(){
scanf("%d%d",&n,&k);
for(register int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(register int i=1;i<=n;++i){
while(head1<=tail1 && q1[head1]+k<=i) head1++;//排除队头过期
while(head1<=tail1 && a[i]<=a[q1[tail1]]) tail1--;//排除队尾冗杂。
q1[++tail1]=i;
while(head2<=tail2 && q2[head2]+k<=i) head2++;
while(head2<=tail2 && a[i]>=a[q2[tail2]]) tail2--;
q2[++tail2]=i;
ans[i][0]=a[q1[head1]],ans[i][1]=a[q2[head2]];//注意这里q存的是下标,所以要将其作为下标。
}
for(register int i=k;i<=n;++i){//k是因为它的区间长度已经固定,所以前面的那些长度不满足,要去掉。
printf("%d ",ans[i][0]);
}puts("");
for(register int i=k;i<=n;++i){
printf("%d ",ans[i][1]);
}
return 0;
}

在每道题使用单调队列之前需要看清题目的端点取舍和条件。

比如 求m区间内的最小值 那道题就是求 $[i-k-1,i)$ 的最小值.

所以说最好在用之前手玩一下数据。

单调队列优化DP

Example

题目描述
在幻想乡,琪露诺是以笨蛋闻名的冰之妖精。

某一天,琪露诺又在玩速冻青蛙,就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多,在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。

小河可以看作一列格子依次编号为0到N,琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动,当她在格子i时,她只移动到区间[i+l,i+r]中的任意一格。你问为什么她这么移动,这还不简单,因为她是笨蛋啊。

每一个格子都有一个冰冻指数A[i],编号为0的格子冰冻指数为0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数A[i]。琪露诺希望能够在到达对岸时,获取最大的冰冻指数,这样她才能狠狠地教训那只青蛙。

但是由于她实在是太笨了,所以她决定拜托你帮它决定怎样前进。

开始时,琪露诺在编号0的格子上,只要她下一步的位置编号大于N就算到达对岸。

输入格式
第1行:3个正整数N, L, R

第2行:N+1个整数,第i个数表示编号为i-1的格子的冰冻指数A[i-1]

输出格式
一个整数,表示最大冰冻指数。保证不超过2^31-1

输入输出样例
输入
5 2 3
0 12 3 11 7 -2
输出
11

说明/提示
对于60%的数据:N <= 10,000

对于100%的数据:N <= 200,000

对于所有数据 -1,000 <= A[i] <= 1,000且1 <= L <= R <= N

这题明显的是一个线性DP。

首先我们考虑 60pts 的数据怎么做。

设 $f[i]$ 表示Cirno走到第 $i$ 个格子的时候可以取得的最大值。

那么很明显方程式这样子的:

$$f[i]=\max { f[j]+ice[i] } ,(i \in [l,n],j \in [i-r,i-l])$$

转移应该是 $\text{O}(n^2)$ 的。 60% 数据勉强过。

现在考虑对它进行优化。

WUw2Sf.png

仔细想想,我们每次更新都是这样子的。

你会发现 $[i-r,i-l]$ 这个区间的上下界是随 $i$ 不断后移的(区间平移,具有单调性)

而且对于每一个决策它只会进入这个区间一次并且只出去一次(区间不会平移回来)。

所以我们想到了“滑动窗口” 这个东西。

那么就可以使用单调队列进行决策的优化。

我们首先维护队列里的单调性,保证队头一定是当前可以转移过来的状态的最优状态。

另外,当队头无法到达当前决策点 $i$ 的时候,我们把队头出队。

这样子我们就做到了 $\text{O}(1)$ 让每一次转移时都取最优值(并且这个状态是合法的)。

说白了就是使用单调队列代替 for 来决策。

注意,按照我的这种写法,单调队列维护的是 $[head,tail]$ 这个闭区间的元素。

Code:


#include<bits/stdc++.h>
using namespace std;

const int si=2e5+10;
int n,l,r;
int a[si];
int f[si];
int q[si],head=1,tail=0;

int main(){
scanf("%d%d%d",&n,&l,&r);
if(l>r) swap(l,r);
for(register int i=0;i<=n;++i){
scanf("%d",&a[i]);
}
memset(f,-0x3f,sizeof f);
int ans=-INT_MAX;//attention here
f[0]=0;//init
for(register int i=l;i<=n;++i){ start from 0,so the first point we can arrive is l.
while(head<=tail && q[head]<=(i-r-1)) head++;
while(head<=tail && f[q[tail]]<f[i-l]) tail--;
q[++tail]=i-l;
f[i]=f[q[head]]+a[i];
if(i+r>n) ans=max(f[i],ans); // reach the destination
}
printf("%d",ans);
return 0;
}

这时候就有人要问了,二维的怎么做?

也是同理。

WUBF5n.png

这样子的转移($[l,r]$ 随 $j$ 平移) 都是可以的。

只是你需要根据题目要求判断一下什么时候出队,什么时候入队,什么时候决策。

「冥界の土地も有限よ、余計な霊魂は全て斬る!」

最近公共祖先(Lowest Common Ancestors)

定义1

我们假设有一颗有根树 $T$,对于 $\forall x,y \in T$。

一定存在至少一个节点 $z \in T$ ,满足 $z$ 是 $x$ 的祖先 且 $z$ 是 $y$ 的祖先。

特别的,一个节点 $x$ 的祖先也可以是 $x$ 自己。

那么所有的 $z$ 所组成的集合中 ,深度最大的一个 $z$ 则称为 $x,y$ 的最近公共祖先,一般记作 $\texttt{LCA}(x,y)$。

倍增Lca算法就基于这个定义。

定义2

是这样子的:

若存在一个无向无环图 $T$, 那么$x \to y$ 的最短路上的深度最小的点就是 $\texttt{LCA}(x,y)$

注意,这个“深度最小” 还是从树的角度来说的。

Tarjan算法就基于这个定义。

图例:

Wwh58K.png

Wwh4C6.png

如图所示,蓝点 $x,y$ 的最近公共祖先是黄色点 $\texttt{LCA}(x,y)$

向上标记法求 LCA

考虑怎么来求 $\texttt{LCA}$。

首先第一个想法是根据定义1,我们从 $x$ 向上搜索 $x$ 的祖先,同时从 $y$ 开始向上搜索 $y$ 的祖先,搜到一个标记一个。

然后找出深度最大的被同时标记的节点 $z$ ,$z$ 就是 $\texttt{LCA}(x,y)$

(当然同时搜两个不太现实,我们一般是先让 $x$ 搜到 $root$ 之后用 $y$ 来搜,找到的第一个被标记过得节点就是 $\texttt{LCA}(x,y)$)

但如果 $T$ 是一个链而 $x,y$ 分别在链的端点处,那么单次询问的复杂度就会被卡到 $\text{O}(n)$ 。

Ww4uMF.png

对于多次询问,\shq\cy

Tarjan求 LCA

这是候就有人要问了:“这个暴力能优化吗?”

看起来好像真的没什么办法。

但是 $\texttt{Tarjan}$ 老爷子带着他的并查集跳了出来:

我能优化!

这是一个基于并查集和定义2的离线算法。

大概思路是 $\texttt{dfs}$ 遍历树 $T$,利用并查集。

当某个节点 $u$ 及其子树遍历完成后,处理所有和 $u$ 有关的查询。

以此达到优化“向上标记法” 的目的。

标记的流程:

  1. 假设我们当前访问到了节点 $u$ , 那么我们新建一个关于 $u$ 的集合 $S$ (利用并查集)

  2. 递归搜索 $u$ 的子树,如果说 某一颗子树 $v$ 被搜完了,我们标记 $vis[v]=true$

  3. 很明显这个子树递归的过程当中也会产生一个新的集合 $S^{‘}$,那么这时我们将 $S$ 和 $S^{‘}$ 合并并且以 $u$ 作为整个大集合的 $root$ 。

  4. 重复 2,3 ,直到 $u$ 的所有子树都被访问完(即 $vis$ 都被标记),这时将 $vis[u]$ 标记为 $true$

WwIWUs.gif

这时候已经遍历完成了 $u$ 以及 $u$ 的所有子树,我们就可以处理查询了。

考虑一个查询 $(u,v)$ 。

  • 如果说 $vis[v]=true$ ,也就是已经被标记过了。

    那么 $\texttt{LCA}(u,v)$ 就是 $\texttt{root}(v)$ (并查集的查询根)

    为什么呢?

    因为 $vis[v]=true$ 的话,根据上面的标记流程,我们可以知道,

    它带着它的子树此时一定被并到了它的父亲的集合里去,

    而它的父亲又有可能被合到它($v$)父亲的父亲的集合里。

    以此类推,搜到大集合的根的时候,这个根一定没被标记过,否则它也将会被并到它(根)的父亲(祖先)节点的集合里去。

    所以 $\texttt{LCA}(u,v)$ 就是 $\texttt{root}(v)$ 。(反证法)

  • 如果说 $vis[v]\not= true$。

    那么跳过这个询问,当 $v$ 和 $v$ 的子树遍历完的时候一定会回来更新 $(u,v)$ 的(上一种情况)。

因为每个点只会别标记一次,每个询问也只处理一次。

所以复杂度为 $\text{O}(n+q)$ ($q$ 是查询次数)。

是所有$\texttt{LCA}$ 的算法里面最快的。\qq

Code:


#include<bits/stdc++.h>
using namespace std;

#define pb push_back
const int si_n=5e5+10;
const int si_m=5e5+10;

struct Tree{
int ver,Next,head;
}e[si_m<<1];
int cnt=0;
void add(int u,int v){
e[++cnt].ver=v,e[cnt].Next=e[u].head;
e[u].head=cnt;
}

int pa[si_n];
int root(int x){
if(pa[x]!=x){
return pa[x]=root(pa[x]);
}
return pa[x];
}
vector<int>que[si_n],pos[si_n];
int lca[si_n];
bool vis[si_n];
int n,q,s;

void tarjan(int u){
vis[u]=true;
for(register int i=e[u].head;i;i=e[i].Next){
int v=e[i].ver;
if(vis[v]==true) continue;
tarjan(v),pa[v]=root(u);
}
for(register int i=0;i<(int)que[u].size();++i){
int v=que[u][i],po=pos[u][i];
if(vis[v]==true) lca[po]=root(v);
}
}

int main(){
scanf("%d%d%d",&n,&q,&s);
for(register int i=1;i<=n;++i){
pa[i]=i,vis[i]=false;
que[i].clear(),pos[i].clear();
}
for(register int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
for(register int i=1;i<=q;++i){
int u,v;
scanf("%d%d",&u,&v);
if(u==v) lca[i]=u;
else{
que[u].pb(v),que[v].pb(u);
pos[u].pb(i),pos[v].pb(i);
}
}
tarjan(s);
for(register int i=1;i<=q;++i){
printf("%d\n",lca[i]);
}
return 0;
}

倍增求 LCA

在树上问题当中有个神奇的算法:

树上倍增。

在 $\texttt{LCA}$ 当中,倍增也是一个极其神(bao)奇(li)的算法。

你想,我们要维护的无非是一个节点 $u$ 的所有祖先,然后扩展到整棵树的节点的祖先。

利用倍增的思想(和 $\texttt{ST}$ 有那么一丢丢的像)。

我们设 $f[u,k] , (u \in T,k \in [1,\log(n)])$ 表示 $u$ 的 $2^{k}$ 级祖先。

那么很容易想到 $f[u,k]=f[f[u,k-1],k-1]$。

特别的,$f[u,0]=father(u)$。

这个东西本质上来说就是 $\texttt{DP}$ ,所以我们直接将其预处理出来。

复杂度是 $\text{O}(n\times\log(n))$ 的。

有人就问了,如果是 $3,5,7 ……$ 级祖先怎么办????

哦,二进制拆分不就完了……

在尝试跳的时候从大的开始跳,然后一个一个向下试就可以了。

这个做法的思路就是不断让 $u,v$ 向上跳,然后直到 $u=v$ 或者 $f[u,0]=f[v,0]$ 即可。

很简单,所以直接上代码:


#include<bits/stdc++.h>
using namespace std;

const int si=5e5+8;
int n,m,root;
struct Tree{
int ver,head,Next;
}e[si<<1];
int cnt=0;
void add(int u,int v){
e[++cnt].ver=v;e[cnt].Next=e[u].head;
e[u].head=cnt;
}
int dep[si];
int f[si][20];

void dfs(int i,int fa){
dep[i]=dep[fa]+1;
f[i][0]=fa;
for(register int j=1;j<18;++j){
f[i][j]=f[f[i][j-1]][j-1];
}
for(register int j=e[i].head;j;j=e[j].Next){
int v=e[j].ver;
if(v==fa) continue;
dfs(v,i);
}
}

int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(register int i=19;i>=0;--i){
if(dep[f[u][i]]>=dep[v]) u=f[u][i];
}
if(u==v) return u;
for(register int i=19;i>=0;--i){
if(f[u][i]!=f[v][i]){
u=f[u][i],v=f[v][i];
}
}
return f[u][0];
}

int main(){
scanf("%d%d%d",&n,&m,&root);
for(register int i=1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs(root,0);
while(m--){
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",lca(u,v));
}
return 0;
}

例题:

description

描述
S城现有两座监狱,一共关押着N名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。
很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。
我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。
如果两名怨气值为c的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c的冲突事件。
每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到S城Z市长那里。
公务繁忙的Z市长只会去看列表中的第一个事件的影响力,如果影响很坏,他就会考虑撤换警察局长。
在详细考察了N名罪犯间的矛盾关系后,警察局长觉得压力巨大。
他准备将罪犯们在两座监狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。
假设只要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。
那么,应如何分配罪犯,才能使Z市长看到的那个冲突事件的影响力最小?这个最小值是多少?

格式
输入格式
输入文件的每行中两个数之间用一个空格隔开。

第一行为两个正整数N和M,分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的M行每行为三个正整数aj,bj,cj,表示aj号和bj号罪犯之间存在仇恨,其怨气值为cj。

数据保证1<=aj<=bj<=N,0<=cj<=1000000000,且每对罪犯组合只出现一次。

输出格式
输出文件共1行,为Z市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件,请输出0。

样例输入
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
样例输出
3512
提示
分配方法:市长看到的冲突事件影响力是3512(由2号和3号罪犯引发)。其他任何分法都不会比这个分法更优。
对于30%的数据有N≤15。
对于70%的数据有N≤2000,M≤50000。
对于100%的数据有N≤20000,M≤100000。

solution

题目里面说了 :

按影响力从大到小排成一个列表

所以不妨我们就按照它说的来做。

那么从大到小处理,如果能够通过“分配到两个不同的监狱”来避免这个冲突的发生,那么我们就分。

反之如果没有办法分到两个不同的监狱,我们就输出(因为从大到小之后第一个矛盾的情况一定是答案,你后面不管怎么决策都不会影响答案了)。

然后你会发现这里对于一个罪犯和其他罪犯之间的关系是可能有多条的。

所以我们就需要用到并查集来维护这些不同的信息。

考虑怎么样把两个罪犯分到不同监狱之后维护他们之间的位置(在哪个监狱)信息。

第一个想法是建立两个集合 $A,B$ 来表示 A和B 两个监狱。

但是这样做的话有可能一个人会被同时分到两个监狱里去,非常不好处理。

怎么办?既然这里是会出现“一个人在两个监狱里面”。

那么我们就把这个情况变得好处理一些。

对于任意的一个罪犯 $x$ ,我们考虑建立一个他的在另一个监狱的镜像 $x^{‘}$。

这个 $x^{‘}$ 有什么用呢?

如果说 $x ,y$不能够相连(关在一起),那么我们就把 $y$ 和 $x^{‘}$ 合并。

意味着 $x$ 和 $y$ 不在同一个监狱(因为 $x^{‘}$ 就代表$x$在另一个监狱的“镜像”,而镜像和本体是不在一起的 )

那么信息就得到了维护。

考虑什么时候矛盾。

很明显,假设新扫到的二元组 $(x,y)$ 已经因为前面的关系而关在一起了。

那么矛盾必定发生,输出即可。

代码:


#include<bits/stdc++.h>
using namespace std;

const int si_n=2e4+10;
const int si_m=1e5+10;

int pa[si_n*2];
#define mir(x) x+n // the mirror of element 'x'

struct node{
int u,v,w;
bool operator < (const node &b)const{
return w>b.w;
}
}e[si_m];

int root(int x){
if(pa[x]!=x){
return pa[x]=root(pa[x]);
}
return pa[x];
}

void Union(int x,int y){
int rx=root(x),ry=root(y);
if(rx==ry) return;
pa[rx]=ry;
}

bool query(int x,int y){
if(root(x)==root(y)) return true;
return false;
}

int n,m;

int main(){
cin>>n>>m;
for(register int i=1;i<=m;++i){
cin>>e[i].u>>e[i].v>>e[i].w;
}
for(register int i=1;i<=n*2;++i){
pa[i]=i;
}
sort(e+1,e+1+m);
for(register int i=1;i<=m;++i){
int x=e[i].u,y=e[i].v,w=e[i].w;
if(query(x,y)==true){
return printf("%d\n",w),0;
}
else{
Union(x,mir(y));
Union(y,mir(x));
}
}
return printf("0"),0;
}

前言

我爱\cy Tarjan! Tarjan万岁!

(高中部的生活太美好,赛扩你high铁鸭子大~ \cy

一些基础

流图和搜索树

因为 $\text{Tarjan}$ 的 $\text{SCC}$ 算法是基于 $\text{dfs}$ 的。

所以需要一些关于“搜索树”的概念。

我们给定一张有向图 $G=(V,E)$。

如果存在一个 $r \in V$ ,使得从 $r$ 出发能够到达 $V$ 中其它的所有点。

那么我们称 $G$ 是一张“流图”,记作 $(G,r)$。

那么对于流图 $(G,r)$ ,我们对它进行 $\text{dfs}$,每个节点都只访问一次。

我们可以得到一颗搜索树 $T$ ,它就是这个流图 $(G,r)$ 的搜索树。

那么在 $(G,r)$ 的所有有向边 $(x,y) ,x \to y$ 中会出现这样子的四种情况:

  1. 树边:搜索树 $T$ 中的边。
  2. 正向边(前向边): 在搜索树中 $x$ 是 $y$ 的祖先节点。
  3. 反向边(后向边): 在搜索树中 $y$ 是 $x$ 的祖先节点。
  4. 交叉边(横叉边): 在搜索树过程中不同子树之间的边(也就是 $dfn[y]<dfn[x]$ ($dfn$ 是什么等会会说))。

WCYNrj.png

这是一个流图 $(G,r)$ 和它的搜索树 $T$。

另外,在执行 $\text{dfs}$ 的过程当中,我们按照 访问 的次序以此给每一个节点 $u$ 打上一个标记 $dfn[u]$ ($dfn[u] \in N_+ , ,, dfn[u] \in [1,n]$)。

这个标记 $dfn$ 被称作“时间戳”。

强连通分量(Strongly Connected Component)

定义:

在有向图 $G$ 中,如果任意两个顶点都是连通的,那么这个图就是强连通图。

非强连通图的极大强连通子图,被称为强连通分量。

下图中的子图 $ {1,2,3,5}$ 就是一个极大强连通子图,子图 ${4}$ 也是一个极大强连通子图。

对于“极大”的理解,就是在一个局部子图中不能再大。

WCUWZj.png

另外有一个理解:

每一个点都只能在一个 SCC 当中。

如果你一个点连接着两个不同的强连通分量(他们实际上应该是强连通子图)。

像下图那样,那么这两个强连通子图和这个点一定会构成一个新的更大的 SCC。

WCd6bQ.png

Tarjan的线性SCC算法

基础思想

你会发现,如果在 $G$ 当中出现了一个 “环”,那么这个“环”一定是一个强连通子图。

如果想要求强联通分量,那么我们就要尽可能地扩大这个强连通子图。

思考一下,如果要构成一个环,那么反向边是一定有用的,交叉边有时也有用(能在图 $G$ 中找到回到在搜索树中是祖先的节点的路的时候)。

所以 $\text{Tarjan}$的基本思路就是找到尽量多的环。

那么就需要找到反向边和交叉边,这时 $\text{Tarjan}$就引入了一个叫“追溯值 $low[u]$”的东西。

$low[u]$ 的定义:

$low[u]$ 是所有满足一下两个条件节点 $v$ 的最小时间戳的值。

  1. 这个点在搜索时建立的栈中(目前阶段被访问过了)
  2. 存在一条从 $u$ 的子树中出发的有向边,终点是这个节点 $v$

也就是以 $u$ 为起点,$u$ 或 $u$ 的子树能够追溯到的最早的栈中节点的 $dfn$。

说白了就是要尽量快地找到更多“环”。

至于这个栈是干什么的?

它在搜索时,边搜边记录所有当前阶段已经被访问过的节点。

用栈是为了符合 $\text{dfs}$ 的特点。

流程

  1. 当节点 $u$ 第一次被访问时,入栈,标记在栈里面。并且初始化 $low[u]=dfn[u]$

  2. 从 $u$ 出发,扫描所有出边 $(u,v)$

  3. 如果 $v$ 没有被访问过,那么 $(u,v)$ 是树边,递归去搜 $v$,回溯之后令 $low[u]=\min(low[u],low[v])$

  4. 反之,如果 $v$ 已经被访问过而且在栈之中,令 $low[u]=\min(low[u],dfn[v])$

(为什么是 $dfn[v]$ 请看 Tarjan 的论文,反正只能是这样子(有时不会出错但是不严谨))

然后如果 $low[u]=dfn[u]$ ,那么就找到了一个 $\text{SCC}$ ,记录,然后把栈中节点一直弹栈并加入 $\text{SCC}$ ,直到 $u$ 出栈 (这里就可以看出来为什么要用栈)

$low[u]=dfn[u]$ ,也就是以 $u$ 为根的搜索子树的所有栈中节点能够到达的最早节点是 $u$ 本身。

为什么这个时候就一定是一个强连通分量了呢?

假设这个SCC里面有一个节点 $v$,但是它不属于 $u$ 为根的搜索子树的所有栈中节点所构成的集合 $S$。

那么也就是说在 $u \to v$ 的路径上面,一定有能够离开子树的一条反向边(去到比 $u$ 更早访问的节点),或者交叉边(从这个子树跳到另一个子树)。

这个边的终点的 $dfn$ 就必须比 $dfn[u]$ 小,和上面的条件:

“能够到达的最早节点是 $u$。”

矛盾了,那么此时无法构成SCC,所以这样的 $v$ 不存在。

那么很容易得知此时($low[u]=dfn[u]$ )已经构成了一个SCC。

Code:

(缩点 & SCC)


#include<bits/stdc++.h>
using namespace std;

const int si_n=1e5+10;
const int si_m=1e6+10;
#define pb push_back

struct Edge{
int ver,Next,head;
}e[si_m];
int cnt_e=0;
void add(int u,int v){
e[++cnt_e].ver=v,e[cnt_e].Next=e[u].head;
e[u].head=cnt_e;
}

stack<int>s;
bool ins[si_n]; // in the stack or not
int c[si_n]; //c[x] = the num of SCC which is x iside
vector<int>scc[si_n]; // scc[i] -> all node in i-th scc (information of i-th scc)
int dfn[si_n],low[si_n];
int n,m,cnt_t=0,tot=0; // tot = how many scc in the graph.

void tarjan(int u){
dfn[u]=low[u]=++cnt_t;
s.push(u),ins[u]=true;
for(register int i=e[u].head;i;i=e[i].Next){
int v=e[i].ver;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
++tot;
int x;
do{
x=s.top(),s.pop(),ins[x]=false;
c[x]=tot,scc[tot].pb(x);
}while(u!=x);
}
}

Edge edag[si_m];//新图
int cnt_d=0;
void add_n(int u,int v){
edag[++cnt_d].ver=v,edag[cnt_d].Next=edag[u].head;
edag[u].head=cnt_d;
}
void contract(){
for(register int u=1;u<=n;++u){
for(register int i=e[u].head;i;i=e[i].Next){
int v=e[i].ver;
if(c[u]==c[v]) continue;
add_n(c[u],c[v]);
}
}
}//缩点

int main(){
cin>>n>>m;
for(register int i=1,u,v;i<=m;++i){
cin>>u>>v;
add(u,v);
}
for(register int i=1;i<=n;++i){
if(!dfn[i]) tarjan(i);
}
//......
}

注意在使用的时候可以视情况去掉 vector<int>scc 一类的东西来节省空间。

缩点就是直接把每一个 SCC 缩成一个新点(这时可以缩出一个DAG,建新图)

例题:

以上为模板题。

我还记得四个月前的某个下午。

我发现了一首熟悉但是不知道名字的歌(幼女幻奏)。

然后弹幕里给了名字,我就去搜了一搜。

在某音乐软件的评论区,我发现了一句话:

RRQZfU.png

那么理所应当的,我又去搜了少女幻葬。

一开始感觉好怪,然后听到副歌有种泪目的感觉?

然后就收藏了。

RRQVYT.png

(从这里开始,我的歌单迈上了被车万统治的道路)

很快就发现专辑写着:

東方妖々夢 ~ Perfect Cherry Blossom

RRQmpF.png

这之后我就懵懵懂懂的搜到一个叫“东方狗下载站”的东西。

RRQkT0.png

下了妖妖梦,那就是我和幻想乡的第一次相遇。

RRQEkV.png

还记得第一次用的是梦A机体(当时觉得自动诱导应该会很好用)。

还用了全开档进EX和PH看了看(当时的我,甚至不会低速,更别提扭自机狙)。

RRQu6J.png

吓死人。不过有一次居然一路炸到了橙那里,想起来,那时还真的挺快乐的?

后来就慢慢的开始接触圈子了。

记得洛谷的冬日绘版上有“东方天空璋”的图案,于是我就去老地方下载。

RRQnl4.png

(甚至还有个苗爷)
RRQKX9.png

开始还吐槽tkz操作恶心((((

说这么多,其实只是回忆啦,毕竟我才入坑半年不到(虽然传教很成功)

妖妖梦是我永远忘不了的初心之作,现在通关也算是圆了个小梦想(

那么就是这些。

某一天在晚自习的时候无聊做的思维题。

结果真就做出来了。

Description:

Sherry现在碰到了一个棘手的问题,有N个整数需要排序。
Sherry手头能用的工具就是若干个双端队列。
她需要依次处理这N个数,对于每个数,Sherry能做以下两件事:
1.新建一个双端队列,并将当前数作为这个队列中的唯一的数;
2.将当前数放入已有的队列的头之前或者尾之后。
对所有的数处理完成之后,Sherry将这些队列排序后就可以得到一个非降的序列。

Input
第一行包含一个整数N,表示整数的个数。接下来的N行每行包含一个整数Di,其中Di表示所需处理的整数。
Output
其中只包含一行,为Sherry最少需要的双端队列数。
Sample Input
6
3 6 0 9 6 3
Sample Output
2
Hint
100%的数据中N≤200000。
Source
Bejing Day1

solution

考虑这道题从何入手,正常想法都是正着取按照要求模拟一下。

但是这道题有些恶心,如果一个双端队列中存在一个相邻的二元组 $(u,v)$。

且在原序列当中 $(u,v)$ 不相邻。那么就有可能出现一个元素 $o$。

满足 $pos[o] \in (pos[u],pos[v])$ 且 $o \in (u,v)$。

($pos$ 表示元素在原序列的位置)

那么很明显就是无解了。

因为我们要 按顺序 对原序列进行操作。

最要命的是,这道题很容易出现这种情况,随便构造一个数据就行了。

做数学题的时候有个思想叫 “正难则反” 。

所以我们不妨考虑直接把这个序列变成不下降的,然后再倒推回去(显然这个不下降的序列是唯一的(有相同元素也无妨))。

那么问题可以转化为:

把一个不下降的序列划分成连续的 $k$ 的子段,使得每一个子段都是可以由原序列经过合法操作得来的。
并求 $k$ 的最小值。

因为题目的要求是按顺序,所以我们离散化一下,排序的时候记录一下这个元素在原序列的位置 $pos$ 。

现在考虑一下,怎么样的一个(离散后序列中的)子段才是合法的?

不难得出:对于一个子段,它想要合法,那么它不可能有形如 $pos={1,7,2}$
这样子的排列。

因为你不可能把 $a[1],a[2]$ 插入之后再在它们之间插入一个 $a[7]$ 啊($a[1],a[2]$ 又不能出队)。

说白了就是 $pos$ 要有单调性,但我们这里是双端队列,两边都能入队(扩展)。

那么分析一下,就有一个性质:

对于一个子段里的 $pos$ 最小(大)的数,一定满足它两边分别单调。

或者整段单调,甚至可以是就只有他一个元素。

也就是这样子的:

2Wfief.png

现在随便来一组数据模拟一下:

n=8,a={3,9,4,8,8,9,7,2};

离散之后:

a={2,3,4,7,8,8,9,9}
pos={8,1,3,7,4,5,2,6}

很明显其中一种最优划分是

a : |2 3 4 7|,|8 8 9|,|9|。

pos:|8 1 3 7|,|4 5 2|,|6|。

画一个图:

2Wh7VK.png

拆出来就是这样的三段函数:

2WhO8H.png

满足性质。

(实际上就是一个单谷性质)

那么我们离散之后统计一下 $pos$ 的单调性然后随便贪一贪,分一下就可以了。

「妖怪が鍛えたこの楼観剣に 斬れぬものなど、あんまり無い!」

树上差分

树上差分分两种,点差分和边差分。

不管是哪一种,都是基于最基础的差分的。

只不过我们的操作对象从序列变成了树链。

点差分

假设说给你一棵树 $T$。

且 $\forall u \in T$ 都有一个权值 $val[u]$

现在有 $q$ 次操作,每一次操作 $\operatorname{change}(u,v,d)$ 需要你修改 $u \to v$ 的路径上的所有点的权值。

即令 $\forall val[u]+d,(u\in \delta(u,v))$ 。

怎么做?

正常想法是 $\texttt{dfs}$ 暴力修改。

显而易见,这做法受不住树链很长的多次询问 dk

还有一种做法是先树剖然后套一个线段树。

但这里完全不在讨论范围内啊。

所以点差分就出现在了我们的眼前。

我们将一条树链拆成 $A:(u,lca(u,v)),B:(v,lca(u,v))$ 这两部分。

WsdjyR.png

那么设 $c[u]$ 表示 $[u]$ 这个节点的增量(差分数组)。

我们有:

Wswrc9.png

我们对于 $A,B$ 的端点分别差分一下。

所以 $c[u]=d,c[v]=d,c[lca]=-2\times d$。

但是这个 $\texttt{LCA}$ 本身就在树链 $\delta(u,v)$ 上。

所以它自己也要加 $d$ ,我们就给他加回去。

那么 $c[u]=d,c[v]=d,c[lca]=-d$。

WsB0y9.png

但是你想想,我们差分之后肯定要还原,还原的时候肯定要 $\texttt{dfs}$ ,从子树收集信息。

所以父节点的值是会被子树影响的。

所以我们还需要给 $father(lca(u,v))-d$。

这才是真正的点差分。

WsrSjH.png

void dfs(int u,int fa){
for(register int i=e[u].head;i;i=e[i].Next){
int v=e[i].ver;
if(v==fa) continue;
dfs(v,u),c[u]+=c[v];//收集子树信息
}
a[u]+=c[u];//还原
return;
} //在所有修改结束之后还原序列。

注意,差分的所有修改一定在查询之前,要不然你需要还原,修改多次。

还不如树剖+线段树。

边差分

点差分明白了,边差分也就十分类似。

之前做 P3627 [APIO2009]抢掠计划的时候。

用了一个思想叫“点权化边权”。

在这里我们反过来,“边权化点权”。

考虑任意的一条树边 $(u,v)$ ,一定满足它连接的是父亲和儿子(废话)。

那么这个边的“指向”就有唯一性。

所以我们把每一条树边的权值压到它指向的“儿子节点”。

特别的,因为树根没有父亲,所以它的权值为 $0$

这是候就有人想,既然边权化点权了,那我们能不能直接跑点差分?

不行。

Ws635t.png

($u$ 打错成 $x$了)

你仔细看看,lca的权值可是 $(lca,root)$ 的权值哦。

我哪里需要更新这条边?

所以相当于是在跑一个去掉 $\texttt{LCA}$ 的点差分。

于是我们就不需要考虑 $\texttt{LCA}$ 的权值和它对 $father({\texttt{LCA}})$ 的影响。

直接 $c[u]+d,c[v]+d,c[lca]-2\times d$ 即可。

然后也是利用子树上传信息还原序列。

树形DP

正常的线性DP都是在一个序列上进行决策和转移的。

那如果转到树上呢?

当然可以使用拓扑排序进行DP,不过这里我们讨论利用 $\texttt{dfs}$ 实现的树形DP。

我们一般从叶子节点上推到根节点,也就是在递归之后利用子树信息更新父节点。

不过调用 $\texttt{dfs}$ 的时候还是写 dfs(root)

所以说 $f$ 的第一维一般是当前访问的节点(方便决策和讨论转移)。

那么这里以最经典的“没有上司的舞会”为例讨论一下树形DP。

description

Ws7Eex.png

solution

题中极度明确的说到了:从属关系构成一棵树。

而且父亲节点是否参加会影响儿子节点是否参加。

那么我们就从这两个“树形”限制入手。

先设 $f[u]$ 表示节点 $u$ 的最大权值。

诶,不对啊,这状态有问题吧,节点 $u$ 的最大权值是什么,怎么来的?

很明显状态并没有设计完整,我们只考虑了“从属关系”这一条件,也就是考虑当前节点的位置,便于判断父亲节点。

所以利用第二个条件再加一维。

设 $f[u][0/1]$ 表示 $u$ 参加或者不参加舞会的最大快乐值。

嗯?还是不对,你这状态有个鬼用啊,参加不就是 $r[u]$,不参加不就是 $0$ 吗?

你怎么用这个节点的决策更新它的父亲(儿子)的状态?

你怎么转移?

所以这个状态设计的还不够完善,为了想办法“决策”,

我们设 $f[u][0/1]$ 表示以 $u$ 为根的子树, $u$ 参加或者不参加舞会取得的最大权值。

那么根据状态设计,我们分 $f[u][0]$ 和 $f[u][1]$ 两种情况来讨论。

如果 $u$ 不参加舞会,那么它的儿子们都可以参加舞会。

但是我们注意到 $r_i$ 可能是负数,所以要在儿子参加和不参加里面取个最大值然后再求和。

$f[u][0]=\sum^{v=1}_{v\le \text{sonsize(u)}} \max(f[v][1],f[v][0])$

然后如果 $u$ 参加了舞会,那么它的儿子节点就都不会参加,但是它自己要参加。

所以 $f[u][1]=\sum^{v=1}_{v\le \text{sonsize(u)}}f[v][0]+r_u$

然后我们DP完了之后就在 $f[root][0]$ 和 $f[root][1]$ 之间取个最大值即可。

Code:


#include<bits/stdc++.h>
using namespace std;

const int si=6e3+10;
struct Tree{
int ver,head,Next;
}e[si*2];
int root=0,cnt=0;
void add(int u,int v){
e[++cnt].ver=v,e[cnt].Next=e[u].head;
e[u].head=cnt;
}

int r[si];
int f[si][2];
bool nrt[si];

void dp(int u,int fa){
f[u][0]=0;
f[u][1]=r[u];//注意这里不要放到里面,会多加
for(register int i=e[u].head;i;i=e[i].Next){
int v=e[i].ver;
if(v==fa) continue;
dp(v,u);
f[u][0]+=max(f[v][1],f[v][0]);
f[u][1]+=f[v][0];
}
}

int n;
int main(){
scanf("%d",&n);
for(register int i=1;i<=n;++i){
scanf("%d",&r[i]);
}
for(register int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
nrt[v]=true;
}
for(register int i=1;i<=n;++i){
if(!nrt[i]){
root=i;break;
}
}
dp(root,0);
int res=max(f[root][0],f[root][1]);
printf("%d\n",res);
}

这道题告诉我们,

树形DP的常见“状态”可以是子树的权值(信息),

可以是以一个节点为根进行决策的权值。

树的直径

  • 定义:

    给定一颗树 $T={V,E}$,树上的每一条边都会有一个权值。

    如果说有一条路径 $\delta(u,v)$ 满足 $\text{dis}(u,v)$ ($u\to v$ 的距离)是所有路径当中最大的。

    那么 $\delta(u,v)$ 就是树的最长链。

    $\text{dis}(u,v)$ 就是树的直径。

  • 求法

(为了方便我们一般假设它是以 $1$ 为根的有根树)

众所周知树的链可能会长成下面这两种样子(蓝色链)

WcpU9s.png

不难发现,对于一个非叶子节点,经过它的链可以向它的子树延伸。

所以我们设 $d[u]$ 表示从 $u$ 出发,走向 $u$ 的所有子树,所能到达最远节点和 $u$ 距离。

设 $u$ 一共有 $k$ 个儿子节点。

显然,$d[u]=\max{d[son_{u,i}]\ + w(u,son_{u,i})}(i \in [1,k])$

这里用树形DP的思想,使用 $\texttt{dfs}$ 从子树向上收集信息即可。

设 $f[u]$ 表示经过 $u$ 的最长链的长度。

那么直径 $D$ 就是 $\max(f[i]),(i\in[1,|V|])$。

考虑怎么求 $f[u]$。

因为 $f[u]$ 可能有很多子树,所以我们考虑从所有子树的信息那里转移过来。

画个图感性理解:

WcCIte.png

因为经过 $u$ 的最长链(可以理解为以它为根)肯定是由两部分(两个子树的信息)合成的

那么根据 $f$ 的定义很容易有:

$f[u]=\max{ d[son_{u,a}] + d[son_{u,b}] + w(son_{u,a})+w(son_{u,b})}$

且 $a,b \in [1,size(son(u))]$

但是这样子的话我们就必须两两枚举 $a,b$。

复杂度稍微有点大,咋办?

想想我们更新 $d[u]$ 的过程,在取 $\max$ 的时候它就会保留一部分信息了。

这部分信息就是 $\max {d[v]+w(u,v)},(v\in son(u),v,has ,been , visited)$ (这个 $v$ 不一定循环到了所有的儿子)

所以我们可以直接用 $u$ 的下一个循环到的儿子 $x$ 的信息来更新 $f[u]$

所以 $f[u]=\max{d[u]+d[x]+w(u,x)}$。

那么就能够在 $\text{O}(n)$ 的复杂度下求解。

Code:


void dp(int u,int fa){
for(register int i=e[u].head;i;i=e[i].Next){
int v=e[i].ver;
if(v==fa) continue;
dp(v,u),f[u]=max(f[u],d[u]+d[v]+e[i].w);
d[u]=max(d[u],d[v]+e[i].w);
}
}
//也可以不用 f 直接写 res

树的重心

  • 定义:

    树若以某点为根,使得该树最大子树的结点数最小,那么这个点则为该树的重心。

    一棵树可能有多个重心。

  • 性质:

    1、树上所有的点到树的重心的距离之和是最短的,如果有多个重心,那么总距离相等。

    2、插入或删除一个点,树的重心的位置最多移动一个单位。

    3、若添加一条边连接2棵树,那么新树的重心一定在原来两棵树的重心的路径上。

这里还是从定义先入手。

设 $f[u]$ 表示以 $u$ 为根时最大子树的大小。

怎么求?

不难发现状态里有“最大子树”四个字。

所以我们先 $\texttt{dfs}$ 一遍,求出以每一个节点 $u$ 为根的子树大小 $siz[u]$

那么考虑怎么转移。

你想,假设我们以一个节点 $u$ 为根,那么这棵树一定可以分成两部分。

一部分是 $u$ 本身的子树(和它自己)。

另一部分就是整棵树抠掉第一部分。

如图:

WgVKSS.png

所以我们要分别用 $u$ 的子树们的信息和上面那一部分的信息来更新 $f[u]$。

那么首先 $f[u]=max{size[v]},(v\in Son(u))$。

然后 $f[u]=max{n-size[u]}$。

最后在 $f[u]$ 里面找最小值即可。

Code:


void dfs(int u,int fa){
siz[u]=1;
for(register int i=e[u].head;i;i=e[i].Next){
int v=e[i].ver;
if(v==fa) continue;
dfs(v,u);
siz[u]+=siz[v];
}
}
void dp(int u,int fa){
for(register int i=e[u].head;i;i=e[i].Next){
int v=e[i].ver;
if(v==fa) continue;
dp(v,u);
f[u]=max(f[u],siz[v]);
}
f[u]=max(f[u],n-siz[u]);
}

如果你要把这两个合到一起,再用一个 ans 替代 f[u] 也是可以的。

换根DP

none

同步发表:link

这里会记载我直升之前的一些心态一类的东西。

——20.3.1


直升前

day 1 | date 3.10

失眠了。

烦,真的很烦。

也不知道为什么。

今天看什么事情都特别烦躁。

明明都起来了生活老师都还要在哪儿乱叫。

吃个饭有人把牛奶洒了一点在我衣服上。

做作业的时候有个傻逼一直在前面乱叫。

机房里面有人颓废就算了,还TM一直大叫。

我打个电话,有个sb非要在旁边背书。搞得好像他多勤奋一样,还不是差一堆课文没背。

CP editor 缩进坏了,一直在调。然后代码也没写,烦。

东方在机房打不开,烦。

明明说让我们先做rczk,结果我其他作业没写先写数学。然后还剩一个小时你发套卷子给我做???

烦。

不想做二次函数,都是简单题所以真的不想算了。

以前都是随随便便算的。

效率低下。

算烦了,不想算了。

啥也不想做。

学烦了。

感觉也没什么人理解我。

找朋友聊几句,结果另一个人一直说说说,死活不给我一个话茬。

语文课代表的工作还没分好。

你给我那么多工作干嘛?

我作业能写完么?

然后听说我的膝盖出事了。

篮球赛没法。

qndb。

我想放弃了。

复兴杯还有20天。

啥也不会做。

我人是废的。

上个课也不想上了。

想好好睡个觉啊。

晚上打了个电话给老爸。

有点帮助吧。

睡觉去了。

day 2 | date 3.11

再次失眠。

14年来头一次连着两天失眠。

昨晚老爸问我要不要请一天假。

我想,但是不敢。

现在这个复习进度,是一天都丢不得啊。

昨晚的卷子考的极差。

历史新低。

上课被点三次。

但是我明明在思考第三种方法还说我走神?

是不是故意针对我啊?

中午机房来了几个蓝背心,这本来就是违反校规的。

中午机房只有js班才可以进来。

你还打游戏,喊那么大声干嘛?举报了!

傻逼玩意儿,你在机房叫个啥?

傻逼东西,你下课了不走在哪儿干啥???

我要关机房啊,你是有病是不是?

爬爬爬爬爬爬爬!

我想请个假回去休息一天。

压力真的扛不住了。

人快崩溃了。

想找个安静的地方休息一下。

我真的受不了了。

感觉也没有谁能理解我了。

想哭。

抑郁。

求你了。

人真的快死了。


day3 | date 3.11

今天睡着了。

好受多了。

下午的时候王老叫我去办公室聊了一下。

觉得王老说的挺对。

其实直不直升没什么问题。

也许我是适合继续留下来的……

嗯……不过说了挺多的吧。

反正说了很多,简单来说就是对那种位置的未来的不明确感的恐慌吧。

不过已经好受多了。


day 4 | date 3.15

事情有点多啊。

语文作业一堆人不交。

王老发了一张初联的卷子。

我人傻了。

我又不是数学竞赛生。

王老说是给高手做的。

但是我是傻逼啊!

我好多题做不起wwww。

物理课,胡老说下次我们数理必须压过18班??

胡老您不是18班班主任么??

虽然数学确实可以吊打他们。

因为王老 is 数学老师(

但是物理???

嗯……我们1尽力吧。

然后又听到了一个消息:直升提前了(然后fx杯也只有20天了……)。

我真题卷子还没刷几套……

现在数学B27常年出事儿……

物理大题会算错。

所以压力山大啊……

不过今天终于找回了以前那种和同学一起吐槽出题人的学习状态……

只不过上一套卷子挺难得……

大家都不是考的很好……

当我知道下铺那个巨的估分和我差不多的时候。

心情就完全好起来了。

晚上……

有人和我说球赛就是明天……

我这个伤势……

有点悬啊。

躺在床上……

发现每次学校的正式球赛我都伤了腿(

/dk

老天爷啊……

对待我公平点好吗??


day 5 | date 3.16

今天球赛……

早上领读的时候一帮人说背不到(

然后只能不收书……

搞得原定计划差点没做完……

我谢谢你啊。。

因为下午球赛占了机房的时间。

所以王老把上午的两节数学换成机房时间了(

王老万岁!

然后在机房发现我U盘不见了。

从挂件上掉下来了……

不过幸好……

我刚刚才备份了的(

然后在机房就只好用云剪贴板存东西了(

回去在桌上看到了球衣。

一个是红的,一个是白的。

您真就当这是在办红白喜事勒1???

谢谢您的关心……

然后我们球衣是76ers……

真就垫底呗?

我恨不得把这个球衣偷偷换成AI的那件了(

……

好,输了。

有点惨。

在王老的鼓励下。

有了许多新替补。

ssr的抢断很牛逼。

要让他上。

先写到这儿吧。


day6 | date:3.21

博客终于换好theme了。

原来是之前没有 hexo clean 所以 package.json 出事了。

也没啥可说的。

只是人际关系出了点问题。


day 7 | date 3.23

周二。

球赛。

和27班打。

他们说要 30:0 我们。

那稍微认真点吧?

不想被人看不起。

赢了。

尽管只赢4分。

但是真的出了一口气。

轮换上来的ssr贴防实在恐怖。

要考虑他的主力位置了。

然后其他人发挥也挺好。

wqx不仅没有乌龙还进了一个。

我进了一个 2+1

扬眉吐气。

鬼知道当时我有多高兴。

上半场领先4分之后开始用垃圾话搞他们心态。

紧逼战术也用起来了。

对面心态似乎炸了。

下半场没进球。

记得裁判宣布结束的时候。

在灿烂的夕阳之下。

我吼叫着。

兴奋地挥起胜利的拳头。

全班都沸腾了。

大喊着我球衣背后的 $AKIOI$

……


day 8 | date 3.25

这是我写的一些东西:

gEzf2V.jpg

day 9 | date 3.26

复兴杯前夕。

晚上自习去问了一堆问题。

出去打球的时候居然进了一个闭眼三分……

也许是肌肉记忆吧……

转转保佑。


day 10 | date 3.27 | fxb

上午7:00起床,(终于可以多睡半个小时了)

然后上午初三烤化学的时候。

我们在讲数学……

明明下一场是物理诶……

结果到了物理……

出题人傻逼。

拿绵阳南山的18自主招生卷。

就改了一点点。

我考之前刷过……

但是没对完答案……

死的惨……

据说大家都在抱怨(甚至是初三竞赛班回来故意减名额的巨佬们都是)

下午数学乱考(只有11道题)。

目标就是做出最后三道52分的大题。

二次函数和一道CRT秒了。

然后这道几何卡了我一会。

($G,F,A,D$四点共线)

先证了 $\Delta ACD $ 和 $\Delta BCE$ 全等

然后发现连一下$GC$可以四点共圆证明 $\angle EGC=60$°

再在 $\Delta CFD$ 里用余弦定理可以知道$FD=2\sqrt{7}$

然后用正弦定理求出 $\sin \angle EDF$

再用和差角公式求出 $\sin \angle EFG$

在$\Delta EGF$里用正弦定理可以知道 $EG=\frac{6}{7} \sqrt{7}$

做完了。

挺有成就感的。

毕竟还是卡了有点久。

这次不但没有搞垮我心态。

反而给直升增加了信心。

加油qwq


day Extra-1 | Unknown

这里记录一些心态吧……

主要是有点久没有管过这个文章了。

清明节的时候去看了下膝盖……

老妈用自己的人力资源帮我联系到了一个医生……

终于不用排队了……

然后最近数学稍微有一点崩掉……

在找状态……

周四的时候要给大家讲一些东西……

然后现在是改错绝对不偷懒了……

像EX 费马最值也有在自己消化理解……

感觉自己真的是个完美主义者……

所有东西都想做到完美……

而且收集癖也管不住……

总是觉得要把能力和知识总结了……

有实打实的资料在才会放心……

现在就不跟着别人进度快质量还高的走……

走我自己的路就好了……


day 11 | date 4.8 | Very special (周四)

三件事情两个人。

event 1 :学长

下去打球的时候遇见了每个周四都可以遇到的一位学长……

我们叫他 “cw库里,球场制霸” 。

主要是他能投三分能扣篮……

还穿着curry的球衣……

所以就这么叫他了。

现在才知道他是初一军训的时候作讲座的那位从新加坡国立大学回来报效母校的NB人物。

篮球打得好……

而且whk及其NB。

这才是我向往的生活啊……

event 2 speech OF ME

给大家讲了半节心理课……

以前初一的时候心理老师就说我是全年级讲的最好的……

现在换了一个老师……

还是这么说……

他说我很有政治家演讲的风范,有鼓动人心程度的能力。

简单来说就讲了几个方面:

1.Numbers & your Unknown Property
2.Different Levels & your own way
3.Know Yourself
4.Plan & Threeminute-hot
5.Extreme perfectionism

然后这里是我的稿子(freestyle之后凭着记忆抄下来的):

gEzW80.jpg

gEzRCq.jpg

很激动。

event 3 Fever

讲完课之后晕倒了……

结果是发烧了……

说是要周日才能回去……

我不干……

查完之后决定明天如果不烧了就回去……

(顺便感叹了一下China这种社会主义制度的优缺点……)

直升的关键时期怎么可以缺席啊……

回来就写下了这一篇……

记得在医务室有一个和我以前一样伤了踝关节的初三老兄……

和他畅谈了很久,都是关于直升啊,政策啊,压力啊等等……

走的时候他那句加油莫名振奋我的斗志……

只记得是个平行班的老兄……

有缘在和他相见吧。


day 12 | date 4.17

又赢球了。

但是最近whk状态很不好啊……

似乎是没有人能鼓励我的缘故吧……

感觉有的时候想说的很多,但又说不出来。

最近要和初二一起考半期,据说是加权带到直升里看。

那我终于有点希望了……

day 13 | date 4.20

想的越多,得到的越少。

想的越少,得到的越多。


半期 | day 14~15 | date 4.22 / 23

  • day 14 上午

第一堂是英语。

在8班和lhw一起考试。

旁边似乎是两个英高的,而且认识lhw。

英语除了听力太快了一切都还好……

然后考地理。

有一些稍微不确定的……

而且做完检查的时候发现自己吧地理特征,自然特征,气候特征搞混了……

幸好是检查出来了。

中午去另一个考场抓了13B 的一个rich guy (每个月零花钱一千多)

然后嫖了他一个饭团和一个sandwich。

  • day 14 下午

物理完全崩盘。

最后一题条件没给全。

本来说原题是用一个力使A浸没。

但是他没有说。

也就是 1.0 0.8 0.64

理论上来说都可以……

但是px和sy班没学到浮力……

所以他们只可能算出 0.64 ……

然后那个英高的说自己118,而且她平常都是70多……

快傻了。

但是我不能崩溃。

大概快速地整理了一下心态。

预估了一下我的情况。

  科目      英   地    物   生   |  数   语(这边是还没考的)

预估分 130+ 20 110+- 20 140+ 117 +
预估平均分 120 19 116+ 18.5 145+ 115 +
预计delta +10 +1 -6 +1.5 -5 +2

预计高于总平均: 10+1-6-5+1.5+2=3.5pts
总人数:56
预计rk:28 +
预计直升rk-line:32 +

也就是我如果后面不崩是不会掉下 28 的。

所以整理了心态去考生物了。

后来考完问了LLT 发现这题是错题。

而且很多神仙也是和我一样最后一题出事了。

也就是说,上面的$\Delta$ 可能更大。

我就有机会了。

所以晚上复习的时候心态就好多了。

即使发了一堆语文单子。

然后我们就一直做啊做啊做啊……

突然华子发了一张B卷……

于是我就滚到B班写卷子了。

题居然很简单。(也许是我现在心态比较好的缘故)

也可能是我带了多颜色的笔所以找条件比较舒服。

这是那张单子:

gEzhvT.jpg

(背面是yl批斗模型(鸡爪))

  • day 14 晚上。

寝室里一直在喊:

豆浆~ 哦亲爱的假期,我们终于分手了 / heituotuo好多哟~

后来才发现是在迫害那几篇作文的作者(pnx,ywh,lty,ssr)

于是加入进去一起迫害。

  • day 15 上午。

在食堂和518的一帮人讨论一些奇怪的东西。

比如一个火车过来,你要扳轨道还是不扳……

你选择 *味的面包 还是面包味的 * (Golden eggs 梗)

到教室先复习语文(同桌ys还吐槽问什么要考数学了还在复习语文……)

坤哥还被whisper 扔出教室了233

可怜我坤坤。

之后胡老突然进来,说物理最后一题要给我们分。

起飞!幸好我当时心态没崩。

王老复习了一些代数就去考数学了。

拿到卷子直接 A1->A20(2)->B21->B23->B26->B27(2)->B28(2)->A20(3)->B24,25->rest 的顺序无脑开卷。

做了一个多小时,把会做的做完了。

先检查了计算然后去想没做出来的。

先是想起华子说的 “初二的相等的边一定可以是旋转”

然后把B28卡住的第二问做了(我先用第二问的结论做的第三问)

之后一阵乱做,全做出来了(B25的加权费马最值最后一分钟构造出来 $2\sqrt{2}$)。

和别人对了一下答案。

似乎是AK了?

AK??!!!!?!?!?!?!

我操。

起飞啊。

这波是要翻盘的节奏。

看来考完物理的那波分析救了老子。

另外华子考前押的考前全中了(

冷静一下,下午好好考语文。

考完了。

选择全对。

回去王老说,这周作业就是好好吃,好好睡,好好玩


  • day 15 晚上

可以好好回去tui了。

点了份翘脚牛肉(楼下新开的店,支持一下)。

回家tui了 [DELETED] h 的绀珠传。

被123那张 转来转去的 [刈安色的迷梦] 卡疯了。

收率 01/49 ……

还有一次明明过了五面,但是残机莫名其妙没了……

我心态越来越好了,谢谢神主。

(不过这之后心态确实是越来越好了(

gSq49x.png

(图是借的别的dalao的,我那个是无欠所以没rep,哭唧唧(也忘记截图了))


day 16 | date 4.24

回去考了套数学,还有一套物理。

数学本来该是142的,结果wl说我那个5没写清楚给我扣了4pts……

物理这套卷子难的一批……

大家都烂,我连100都没上……

不过心态没炸,也许是绀珠传让我心态变得“无所谓”了吧。

之后考完了买个绀珠传光盘支持下2un.


day 17 | date 4.25

最后一场球。

和25班打,身高不够……

输了挺正常,不过我至少是在享受。

唯一愧疚的就是忘记换ywh上了……

whk随便吊打25班就够了。

写个名单纪念一下这只球队吧。

J 2019 C 19
| number | member name |
| :———– | :———– |
| 36 | HYL(captain) |
| 0 | YS |
| 3 | ZZM |
| 66 | WQX |
| 35 | YWH |
| 13 | CZX |
| 46 | SSR |
| 45 | DCY |
| 22 | XYH |
| 44 | ZTH |
| 14 | ZPC |
| 23 | LSB |
| 26 | XLT |
| 23 | CMY |
| 18 | MHZ |
| 88 | XZQ |


day 18 | date 4.26

居然可以去机房。然后整理了一下半期的日记(上面的都是现在写的)。

昨晚作业有道 2020 黄冈的中考题。

据说是大学内容。

答案都是错的。

我算出来第 1,3,4段的长度,但是第二段的摆线LLT说要用微积分??!!

我当时直接当弧算了……

王老讲的时候补充了一下摆线……

我还是不会QAQ (不过本来也没要求掌握)

这是那道题:

gSjJGn.png

知乎喷那套卷子的链接:https://www.zhihu.com/question/408523403

然后英语出来了,134.5

似乎每次大考都挺好……

请叫我大考杀手(吊打LYQ七次是不是可以找Nancy拿奶茶了(

突然想起来Nancy听写的那种方式……

一个句子:

“那些明星们感到了担忧,在一个以那种北极熊命名的人行道上,因为一个披头士的粉丝认出了他们当中的一个导演,而他给了那个有才的导演旁边的一位歌手一条丝绸做的围巾,在上一个周五。”

考 点 大 杂 绘

有意思。

最近要写的东西太多了……

完美主义又犯了。

这周五一放假之后就不写了。


day 19 | date 4.27 | 最終試験まであと16日

昨晚lty说我有机会进前十……

草。

草。

然后数学是真的AK了/cy

总分 558.5


day 20 | date 4.28 | 最終試験まであと15日

草。

rk7,LLT被我碾压了。

我当场疯掉你知道吗。

这他妈估计年排30多……

跟t老师说可以加个zs倒计时,然后她让我加……

最开始还把天数搞错了,结果意外知道了zs时间是5.13


day 21 | date 4.30 | 最終試験まであと13日

今个是个好日子啊。

语文作文因为50分(年级似乎没有51+的了)

被叫上去念……

img

(图可能要等等了,作文被whisper拿走复印去了……)

念着念着也不知道为啥,就哭了。

之后登了一手bilibili(whisper让我们看《大鱼海棠》)

gExb1f.png

结果全篇和《北冥有鱼》其实关系并不是很大?

不过万岁!

(YS和我都觉得这玩意儿画质特别像主机游戏233)

到家打比赛+绀珠传

gEzd8P.png

这玩意儿真的是百转不厌,越转越上头(懂得都懂)

gEzwgf.png

doremi的非符随机弹真的烦……

gEz0v8.png

嘲讽脸233(

顺手补了之前几篇的图(

然后写完这个的时候已经是5.1了(

上号的时候发现之前联系过的学长和我说了些东西(不放完整的了)

gVSSqe.png

其实真的很有道理(

yzh txdy!

突然想起来123的这张和这张转起来都贼爽

gV98DU.png

gV9aCR.png

图依旧是 SOC_ 巨佬的

(因为上次Lunatic的无欠的save找不到了又懒得打233)

(打easy是为了缓解心态(


day 21 | date 5.3

昨天发高烧+肚子疼

人差点挂掉(

然后今天继续颓废!

不想打绀珠传于是转向辉针城了

你不觉得封面的灵梦很涩吗(似乎是全正作到目前为止最好看的reimu)?

(其实本作title BGM个人认为是th里面最强TB)

gmBvfP.png

因为习惯魔理沙机体所以一直在死磕魔理沙(

然后今天才发现咲夜A机体真的好用(

你看这不一下进六面了吗(

gmBjYt.png

gmBzSf.png

不过正邪的这几张反过来反过去的卡着实有意思(也许因为我是M?)

(也有可能是看了神主在Omake里给的建议之后轻松了许多)

之后针妙丸那张变大的卡整的我吐了……

符卡用完……残机爆完……

之后去thb看看全开档方法(似乎和beer关系很大??)然后练一下这张卡吧……

顺手去Twitter上喷人(

gmBXFI.png


day 22 |date 5.4

听说昨晚虹龙洞正式版出了 (喜

老爸说13号通贩出了给我买个实体CD(喜+

guKCdg.png

其实封面没必要放(

因为体验版都玩够了不是么(

guKPoQ.png

顺手赞美一下ZUN老贼的画风,都四十多了(

但是仍然这么懂我们(

你看苗爷这半透明的裙子(

据说是ZUN学会了描身材曲线(

guKSL8.png

大天狗出来之后……

thbwiki上出现了优秀的老兄:

“你打完虹龙洞有什么想法吗?”

“我想看饭纲丸龙和射命丸文OO。”

“不是说这个,是你打完虹龙洞对故事本身有什么思考,有没有什么二创好点子。”

“我现在就t m想看到饭纲丸龙和射命丸文OO。”

谁能比我更野蛮.JPEG

guK9eS.png

另外这位似乎是reimu的阴阳玉制作者(

所以假设灵梦搞到了无尽的阴阳玉

永夜抄4A面Boss(reimu)恐变为自机真实情况(

顺带一提,早苗的机体在虹龙洞里似乎前期中期都比金发小女孩舒服(

看好多人都是苗爷混关(除了Seiko是reimu 苗爷都……)

头一次和人一起VP而不是正常contest

晚上CF炸了,比赛延期24h……

然后和pxz一起VP了一场AT(arc104)

下面是多图预警。

gu6EVS.png
gu6Z5Q.png
gu6VUg.png
gu6n8s.png
gu6mCj.png
gu6u2n.png
gu6Kvq.png
gu6QK0.png
gu6lrV.png
gu61bT.png
gu68VU.png
gu6J54.png
gu6GaF.png
gu6tPJ.png
gu6NG9.png


直升

呼——

这日子终于是到了呢。

不过居然意外地放松?

甚至比每一次小型考试还放松?

day -2 | 5.11

我ritamalegeji

什么shabi出题人。

这题出的比直升还吓人。

计算量及其恐怖,A20~B28都不是给人做的。

所有人都在辱骂出题人(

(5.12 更正:我是傻逼,这卷子居然那么好算)

day -1 | 5.12

在 day -2 之前的那些就没什么好写的了,就是正常的成外人生活。

不顾令我惊讶的是又打了两场球(和18班还有20班)

值得纪念的是打完20班虽然因为黑哨……

不过之后还是把18班送进“季后赛”了 /cy

而且看了数据发现我场均盖帽2点几……

吓人,据说是盖帽王(

gcaMfU.jpg

考前的最后一个晚上,政治老师送给我们一人一条巧克力。

我拿到一个写着“逆袭开挂”的士力架。

希望这真的有用吧。

说到这个,我想起了之前买的一瓶

卷壬の水

图在这(数学考试的时候喝掉了)
gcazjJ.jpg

回去和NSA他们一起改了倒计时。

然后上床继续听歌。

day 1 | 5.13 for physics

下午考试,于是一整个上午窝在胡老办公室里面问题·。

下午就去考场。(不过为什么准考证是生物操作考试的啊)

溜进去发现自己在考场最后守门(

不过更离谱的是,监考员甲居然一个一个人的地发卷子……

无语(他自己居然还说了一句,“这样子发要发多久啊,七大七张”)……

拿到卷子就直接做。

偶尔有几道题卡了一下,比如A1的“吼猴”

A19的 $R_{ao}$ ,B5的计算。

然后B7那里 $\rho_w$ 不能写 $\rho$ 水,我改了好几次。

最后检查的时候发现 B3填错了,于是赶紧找旁边的chm借了橡皮。

应该还好。

回去就直接开始卷数学然后评讲。

晚上依照惯例去做了引体。

day 2 | 5.14 ,the day of Komeiji Koishi

514,恋恋日(

进考场,喝了一口“卷王水”

(监考甲终于是传卷子了)

看题,总的来说难度不大。

从A1开始,但到了A10卡了一下,就先跳过了。

A20第二问本来觉得不好做,但是第一问证完之后想到字母形相似,直接就会了。

B21~B24都比较简单,B25的“正角”四边形画不出图来……

于是先B26,B27发现只能算第一问。

B28算了两个问发现第三问不好搞就先回去检查了。

之后发现B27可以用一个均值不等式的玄学方法解释。

不过最后的双重根号忘记开出来了……

然后用5分钟暴力做出了A10

之后可解把A20做完,B5猜了一个结论写上去。

然后就交卷了。

还行吧。

据说好多人都发挥不好(是因为A17的更正把心态搞爆了吧)

到教室给大家放 《Tom & Jerry》 (第一集的弹幕笑死一堆人)

(当然是先复习了生物操作考试之后)

下午的时候遇见Nancy,就去她办公室划水去了。

发现翔哥在写投到国际部的简历和介绍。

翔哥牛B。

下午放、《The Shape Of Voice》

西宫可爱啊www

看到四十多分钟的样子就放学回家了。

两年的压力放下的感觉真好。

THE END


直升后的双休 (extra)

嗯,比较正常,就是打打东方写写DP。

周六下午溜到万象城去吃点都德

(个人觉得还好,但是比不上广州那边本地的一家店)

然后下楼就发现Nayuki和Hey Tea 开在一起(

就久违的去Nayuki买了杯奶茶然后要了两根德式腊肠犬。

真悠闲啊。

(不过我突然不习惯了,还是觉得一周一休的感觉好(太闲了也不好))

然后把之前没细玩的作完了一下(神灵庙,凭依华,天空璋)

神灵庙神曲居然这么多!(欲望煤气灶真正的管理员((

(每次都死在miko的终符www,我想见见大狸子有那么难吗?)

凭依华里看见Doremy了!机械羊真的笑死www

然后就是……

无尽的,前所未见的,gzz ex 之噩梦。

现在背板已经很熟练了

目前打法(能到的地方)大概这样:

Tb XX 表示第XX波弹幕
--------------------
Tb 01 这里开局先躲到左下角,然后慢慢按着BGM的节奏低速向右,之后收个点。

Tb 02 先直接打掉中间的,然后靠右一点打掉二号位。
再到最左边四号位打掉,再折回来打三号位,中间躲一躲就好。

PS: | 4 3 2 1 0|

Tb 03 这波黄弹先左后右,然后打掉2号位,再向左,打掉3或者4号位,中间上下躲一下就行。

Tb 04 这里打掉小怪要出激光针,不太好搞(瞎眼)所以收枪在2号位这条线左右躲就行,不要被逼到侧边去。

Tb 05 这里蓝叶子没下来之前多高速左右晃打掉几个,之后就躲。不过小心地球出来的时候背景的变换。

Tb 06 【取而代之的蝴蝶】 这里注意蝴蝶外圈的灰色是有判定的,所以小心扭扭就过了。

Tb 07 【子弹快车】 左右屏大幅度移动来给自己找空间躲高速彩虹弹。

Tb 08 【爬行的子弹】 请务必跟着头转,否则只能放B了。

Tb 09 这里在3,4号位之间多combo,防止弹幕密度过大。

Tb 10 这里激光不好躲,目前还不会。

Tb 11 这里旋转弹,在123号位之间击落,不然密度大了也要洗白

Tb 12 没什么难度,扭扭就过了。

rep扔在github里了,就是博客的source目录里的repy文件夹。

点击即可下载。

Tb12 miss

Tb 06 Get Spell card


PH:

直升裸分上了高中部。

现在在新初三十八qwq。

我爱高中部!

day1

w老让我们先上完上午的文化课再去高中部集训……

恶心

听说这一次前三天需要点外卖吃。

因为食堂没开伙……(其实是大家都放假了,就我们在这里苦逼的集训)

中午拿到笔记本电脑就去校门口吃了一家日料,味道居然出奇的好(就是炸天妇罗有一点油腻了)

母亲大人说等我回来要给我做一些神奇的食物,期待……

下午见到了老师,@lqs2015,今年NOI 的Au选手。

CF和另一个机房讲课的 @wucstdio 一样都是IM。

强。

讲的速度很快,习题都是下来做。

whk今天没写,晚自习在颓尤里的复仇写代码。

于10.1夜

P.S.国庆节&中秋节快乐!

day2

今天是DP。
kmz最讨厌的东西。
我和xzq反而无比快乐……

但是听的时候傻了……

草这方程怎么可以这么搞???!!!

树形DP??!!我没学过……

听着有点懵逼。

whk作业写得好少啊……

于10.2午

day3

今天上午是模拟赛……

T1一个傻逼哥德巴赫猜想

T2一个傻逼数论。

T3忘了……

T4一个暴搜但是写挂了……

还有我unsigned long long 写个屁的负号!

于是 rk5 –> rk10

下午讲了一些基本的算法(贪心,二分),还挺轻松的。

今天开始迫害lqs老师

在白板上写满了几个字:LQS2015 AK IOI;

lqs大佬看了一眼没理……果然是巨佬。

下午是恶心的杂(nan)题选讲。

听说颓仙jsc在听wucstdio讲课的时候颓废被抓了…

惋惜

然后群里出现了这样的东西:

cSKG4g.png

至于jsc被举报的时候的图……不放了。

于10.3夜

day4

今天开始学图论了……

令我不可思议的是我居然全听懂了。

老师因为我的反馈从基础部分开始讲,所以之后听着比较顺畅。

先讲了一下拓扑排序的原理,敲了一下代码……懂了。

正当我以为会好很多的时候……

老师突然开启了乱杀模式……

BellmanFord,SPFA,dij,Floyd等等最短路算法在松弛操作讲完之后全部拉了上来……

WDNMD。

下午是LCA和最小生成树。

大概能听懂。

只是写模板的时候xzq非要用Prim,我交了Kruskal之后静静的看着他疯狂改代码……

然后讲例题的时候pwk秒了一道紫题……

于是全机房膜拜。

晚自习电脑面前供奉了这一张图:

cSK0bV.png

于是写作业跟开挂一样快,效率高。

老师还是没理……

TQL……

day5

今天上午是模拟赛……

T1是一个扩欧,切了。

T2到最后都没想出来是啥……结果是求最小环……

T3想了整整两个小时……犯了Wkr大佬今年NOI的时候的错误……

结果最后T了……

然后san值狂掉rating掉了。

中午在机房颓CS。只是机房鼠标出问题……搞得我们只能用键盘打……

CF里瞬狙的技术这里也可以用啊……

下午继续杂题选讲。

第一题是给出一堆条件,要你看给出的序列是否都满足条件……

看到那个式子:$a+b\le k$ 我突然想到了一些神奇的操作。

于是转化成了跑最短路求负环……

所以就是一个差分约束系统而已……

基本是秒了……

但是我这么弱鸡,这种事情应该只是撞上了而已吧……

solution:https://www.luogu.com.cn/blog/ingmiller/poj1364-king

结果下一道题又是一个傻逼题。秒了……

晚上继续写我的作业……

然后找 nnwy 聊了一会……

WHK爬爬爬,我讨厌作业……

晚自习快下课的时候碰到了从初二跳级到高中的ybc大佬……

这个人只爱学习……xlc副校已经指望靠他拿物理世界赛金牌了……

他应该是这几年cw的IQ巅峰了。

于10.5夜

day 6

上午继续难题选讲

我*****

这一题:https://www.luogu.com.cn/problem/solution/P2831

状压DP+二次函数求解恶心人……调了一个上午的东西……

休息时间在自己笔记本上下了CS,用着自己CF里的瞬狙技巧干翻了一堆人……我感觉机房里打FPS可能只有CLJ能和我匹敌了……

所以我现在已经是FPS网瘾人性自走戒除机了?

下午做了一套初赛模拟……分数还行。

我只是不满意下午的树形DP变成了模拟卷……

今天晚上又肝了一会作业,觉得月考可能要挂。于是准备专心复习初赛了……

day 7

上午继续模拟赛……

南高的人先走了,他们的老师让我帮忙发一下data和solution……

T1 送分数论……

T2 是一个大模拟……但是考场上写的是IDA*

T3是一个并查集套二分图……本来会做的……但是写root操作的时候一不小心把father写错了……QAQ

T4好像是一个状压DP套推柿子……没来得及开。

但是有人AK了 (lwh julao)

走的时候让kmz和xzq一起帮我搬床铺……

又遇到ybc了,听说这次全国高中物理竞赛他拿了奖,%%%

回家了!好好颓了一下午的CF就开始做作业了……

END

前言

这个东西是老早就该补的坑了……

所以现在有时间了。

回来写一写。


最小生成树

定义:

简单来说,最小生成树是一张带权无向图里面由全部 $n$ 个顶点,和边集中的 $n-1$ 条边构成的原图的一颗生成树,且所有边权之和是所有生成树中最小的(可能有多个情况)。

而且它一定包含原图中最小的边。

推论:

设一张无向图 $G=(V,E)$ ,从 $E$ 中选出 $k<|V|-1$条边构成 $G$ 的一个生成森林,然后再从剩余的 $|E|-k$ 条边中选出 $|V|-1-k$ 条边加入森林中,让它成为 $G$ 的生成树,并且选出的$\sum w$最小。

那么,这个生成树一定包含 $|E|-k$ 条边里面连接生成森林的两个不连通节点的权值最小的边。

很拗口对吧?

不过请好好理解,因为这个推论就是接下来的 $\text{Kruskal}$ 的基础了。

Kruskal

这是一种求最小生成树的高效算法。

它维护图的最小生成森林。

开始的时候生成森林是空的,每一个节点就是一颗独立的树。

然后我们用上述推论维护森林就好了。

首先先搞一个并查集出来。对于每一个点初始化。

接下来按照边权升序排个序。

然后扫一遍每个边。

如果这一条边所连得两条边$(u,v)$已经联通了。那么继续。

but,如果没有联通,根据这一条:

这个生成树一定包含 $|E|-k$ 条边里面连接生成森林的两个不连通节点的权值最小的边。

所以满足了条件,那么我们就把这一条边加入到最小生成树里。

顺便合并一下 $(u,v)$ (相当于让它联通)

代码:

#include<bits/stdc++.h>
using namespace std;

const int si=2e6+2;

int n,m;
int ans;
int pa[si];

struct edge{
int x,y,val;
bool operator < (const edge &u)const{
return val<u.val;
}
}ed[si];

int root(int x){
if(pa[x]!=x) pa[x]=root(pa[x]);
return pa[x];
}

bool Union(int x,int y){
int rx=root(x),ry=root(y);
if(rx==ry){
return 0;
}
pa[rx]=ry;
return 1;
}

int main(){
cin>>n>>m;
for(register int i=1;i<=m;++i){
cin>>ed[i].x>>ed[i].y>>ed[i].val;
}
sort(ed+1,ed+m+1);
for(register int i=1;i<=n;++i){
pa[i]=i;
}
for(register int i=1;i<=m;++i){
if(Union(ed[i].x,ed[i].y)) ans+=ed[i].val;
}
cout<<ans<<endl;
return 0;
}


Prim

这个算法实际上不是很常用。

因为在没有堆优化的情况下,$\text{Prim}$ 的复杂度是 $\text{O} (n^2)$
的。

而且写了堆优化以后会比 $\text{Kruskal}$ 麻烦的多(某次十一集训的时候xzq就是想写 $\text{Prim}$ ,结果我用 $\text{Kruskal}$ A了几道题了他还没调好/xyx)

那么大概说一下思路。

现在已经知道 $\text{Kruskal}$ 是维护一整个生成森林。

其实 $\text{Prim}$ 就和它稍微有点不同而已,它只是维护了最小生成树的一部分。而且它最开始确定 $1$ 号节点属于最小生成树。

它每一次找到一条权值最小的,且满足它连接的其中一个点 $u$ 已经被选入最小生成树里,另一个点 $v$ 则未被选中的边。

具体实现是这样子的:

维护一个数组 $dis[\ ]$ ,如果 $u$ 没有被选入,那么 $dis[u]$ 就等于 $u$ 和已经被选中点之间的连边中权值最小的边的权值。

反之 $dis[u]$ 就等于 $u$ 被选中的时候选出来那条权值最小边的权值。

然后怎么判是否选中呢?

维护一个$vis[]$ 即可。然后从 $vis[]=\text{false}$的节点中 (也就是未被选中的节点) 选出一个 $dis[]$ 最小的标记它

然后扫描和这个被选点的所有直接连它的边,更新另外一个端点的 $dis$ 。

最后生成树的权值和就是 $\sum^{n}_{i=2} dis[i]$。

代码:



#include<bits/stdc++.h>
using namespace std;

const int si=5e3+10;
int n,m;
int a[si][si];
int dis[si];
bool vis[si];

int main(){
cin>>n>>m;
memset(a,0x3f,sizeof a);
for(register int i=1;i<=n;++i){
a[i][i]=0;
}
for(register int i=1,u,v,w;i<=m;++i){
cin>>u>>v>>w;
a[v][u]=a[u][v]=min(a[u][v],w);
}
//Prim
memset(dis,0x3f,sizeof dis);
memset(vis,false,sizeof vis);
dis[1]=0;
for(register int i=1,u;i<n;++i){
u=0;
for(register int j=1;j<=n;++j){
if(!vis[j]&&(u==0||dis[j]<dis[u])) u=j;
}
vis[u]=1;
for(register int v=1;v<=n;++v){
if(!vis[v]) dis[v]=min(dis[v],a[u][v]);
}
}
//answer
int ans=0;
for(register int i=2;i<=n;++i){
ans+=dis[i];
}
cout<<ans<<endl;
return 0;
}


Boruvka

该算法并不常用,以后有时间会填坑。


习题:


关于Kruskal 算法过程的一个shabi理解

昨天(21/5/17) 晚上yl一直在纠结一道题(CF891C)。

然后在一番讨论之后,我有了一个对于 $\text{Kruskal} $ 的新理解

就是对于原图,我们将它划分为 $n$ 个相互连通的子集(有多种方式)。

且每一个子集原图的一个生成森林。

然后对于任意两个生成森林之间,我们找出所有连通他们的边。

取出有最小权值的边。

然后对于取出这 $C^n_2$ 条边,我们从小到大取就行(当然这里是动态过程所以不一定一直是原来最初的划分情况)(直到构成生成树也就是选完所有情况)(算法里的那个for)。

(这里利用并查集判断这个边是不是可以选出来的边(也就是连通两个生成森林的边),从小到大的话就根据最开始的排序来就行)(算法里的for当中的if和最开始的sort

至于为什么用并查集判是否连通两个森林选出来的那个边一定是连接那两个生成森林的最小边呢?

因为排了序啊,所以我们取到的第一个连通这两个森林的边一定是连通他们的边当中最小的。

(有点混乱但是解释了一点神奇的东西)

对于最小生成树性质的证明:

By : ciwei

(这位dalao的证明真的很有用!)

原文:

https://zhuanlan.zhihu.com/p/340438116 https://zhuanlan.zhihu.com/p/340411111

gfqd4H.png

引理部分:

gfqaUe.png
gfqUED.png

Prim 的证明

By : ciwei

原文:https://zhuanlan.zhihu.com/p/340464163

gfLBoF.png
gfL0dU.png

kruskal 的证明

By:ciwei

原文:https://zhuanlan.zhihu.com/p/340628568

gfOVTU.png
gfOEwT.png
gfOekF.png

其他的一些东西:

ciwei:最小生成树相关定理和算法正确性证明

二分

二分答案是重点。

而二分答案的重点是Check的构建。

你会发现二分答案的题的决策都有这种“单调性”(最小值最大,最大值最小)

cSn3sP.png

当然也可是左边不可行,右边可行。

一般 Check 都是 $\text{O}(n)$ 去暴力判断 $mid$ 的可行性。然后会根据题目的不同,在 Check 里面加上一些 模拟/基础算法。

然后你在写的时候一定要注意写全不可行/可行的情况。也要注意题目本身的坑点(比如负数,一开始就不可行)。

对于整数域上的二分一般这么写:

void binas_Z(int &res){
int l=1,r=n;//for find no solution,r=n+1;
while(l<r){
int mid=(l+r)>>1;
if(valid_Z(mid)) r=mid;
else l=mid+1;
}
res=a[l]; //l==r
}

这种写法 $mid$ 永远不会取到 $r$

这种(代码里的)写法有个好处,就是你可以判无解。

如果说你把 $r$ 扩大到了 $n+1$ ,

最后二分完了指针指在这个“越界下标” 上那么就是无解。

有一种 mid=(l+r+1)>>1 的写法就不会取到 $l$ ( $r,l$ 取值也要变,这里不提了)

然后实数域的二分就比较简单了。

$eps$ 取 $10^{-(k+2)}$ 就行,$k$ 是保留小数的位数。

//k for how many pos after '.'
void binas_R(double &res){
double eps=1e-(k+2); //Here is just a 'fake' code
double l=0.0,r=(double)1e9+7;//r=inf;
while(l+eps<r){
double mid=(l+r)/2;
if(valid_R(mid)) r=mid,res=mid;
else l=mid;
}
}

小心r边界的大小!!!不要盲目用 $n$!!!!
看题!!!!


贪心

贪心就是遵循某种规则,不断选取当前最优策略的算法。


差分前缀和

前缀和: $\text{O}(1) $ 查询区间和,$\text{O}(n)$ 预处理区间和。

差分:$\text{O}(1) $ 预处理区间值,$\text{O}(n)$ 查询区间值。(原数组实质上是差分数组的前缀和)。


拓扑排序

在一个DAG里面可以处理出来一个序列。

每次去掉一个入度(出度)为0的点。

然后按去掉的顺序组成一个新的序列。

拓扑排序可以判断环(也就是判图是不是DAG),图是不是链。

在题目里面可以处理一些有“依赖性”的关系。

比如你要做1就要先做2这种。

或者是做一个匹配是否合法的问题(烦人的幻灯片)

(这题就是每个数字可能对应几个字母,然后让你判断是否能一一对应(这个题就是魔改过的所以每次是看出度为1的点弹出。))

这种题都要先转化为一个图。

就是要维护一些有向的关系信息。

判无解就是判环。

如果判环的话就看拓扑出来的序列长度是否等于点的个数就可。

(如果少了那么就是有环了)


01分数规划

有n个物品,每个物品有两个数值vi和wi,求选至少 x 个物品,使得选的物品的vi的和除以wi的和最大。

做法:

定义$C(d)$为是否存在一种选法,使得能选至少$x$个数使得$v_i$的和除以$w_i$的和$>=d$。

发现$C(d)$满足单调性,所以可以二分,于是本题就被转化成了求$C(d)$。

发现$v_i$的和除以$wi$的和$>=d$可以转化为$vi-wid$的和$>=0$。于是直接按$vi-wid$从大到小排序,选前$x$个看和是否$>=0$即可(Check)。


尺取法

懒得写……

直接代码理解吧。

//http://auoj.net/contest/166/problem/1365

#include<bits/stdc++.h>
using namespace std;

const long long si=1e6+1;
const long long inf=LONG_LONG_MAX;
long long n,t;
long long a[si];

void solve(long long &rt){
long long l=1,r=0;
long long optimal=inf;
long long tot=0;
while(l<=n&&r<=n){
++r;//向后移
tot+=a[r];//选取
while(tot>=t){
optimal=min(optimal,r-l+1);//更新
tot-=a[l];//减掉前一个
++l;//向后移
}
}
return (void)(rt=optimal);
}

int main(){
scanf("%lld%lld",&n,&t);
for(register long long i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
long long res=-1;
solve(res);
if(res!=inf){
printf("%lld\n",res);
}
else{
puts("Angry");
}
return 0;
}

n log n LIS:

本质是贪心。

设$f[i]$表示长度为 $i$ 的最长上升子序列的最小结尾是 $f[ i ]$ (就是考虑前 $i$个)

$\text{O}(n)$ 扫一遍 $a[]$

那么如果扫到的数可以更新,那么更新一下。

反之二分去找 $f$ 中 第一个比 $a[i]$ 小的数。

int nlogn_lis(){
int len=0;
f[0]=-1;
for(register int i=1;i<=n;++i){
if(a[i]>f[len]){
f[++len]=a[i];
}
else{
*lower_bound(f,f+len,a[i])=a[i];
}
}
return len;
}

01/完全背包

不管你怎么写。

反正01/完全背包都是枚举物品(种/个)数。

内层枚举它的体积/重量(让背包空间少了多少)。

V,C,W随便乱写。

只要转移的是对的就好。


关于bitset (STL) 的一个注意事项。

正常来说我们写stl都是:

const int si=114514;

bitset<si>f;
//in main()
f.reset();
f.any();

set<int>s;
//in main()
s.insert();
s.begin();

//……

也就是引用函数用的是 .

但是有种情况:

bitset<si>f[si];

如果要reset 那么要这么写。

f->reset();

其它stl(string,set,map)都是这样。

set<int>s[si];

//in main()
s->clear();

因为这里 fs 都不是一个单一的容器,他现在相当于一个数组。

要使用指针访问。(f->reset()

不过这种情况比较少见啦。


传递闭包。

一般用floyd求解。

就是给定若干个元素和若干的二元关系(且该关系具有传递性)。

然后判定尽可能多的关系的题。

所以设 $f[i][j]$ 表示 $[i,j]$ 的关系。

true表示一个关系false表示另外一种关系。

然后跑一遍floyd,转移的时候根据题目特点转移即可。


一些技巧与要注意的点:

scanf("%1d"&n);

scanf 的返回值

sscanf()

取模的时候如果里面可能有负数要

先膜再加再膜:((a+b)%mod+mod)%mod

如果没有负数就 (a+b)%mod

return printf(),0;

当你要让 a[cnt+1]b[cnt+1] 都赋值为一个数 $d$ 时
不要写 a[++cnt]=b[cnt]=d; (会UB)

a[++cnt]=d,b[cnt]=d;

一些常用字符串函数

  • in cctype

int isdigit(int ch) ;//是否为数字,即ch是否是0-9中的字符
int isxdigit(int ch) ;//是否为十六进制数字,即ch是否是0-9 a-z A-Z 中的字符
int isalpha(int ch) ;//是否为字母
int isalnum(int ch) ;//是否为字母或数字
int islower(int ch) ;//是否为小写字母
int isupper(int ch) ;//是否为大写字母
int tolower(int ch) ;//转换为小写字母
int toupper(int ch) ;//转换为大写字母

  • in stdlib

double atof(char *str) ; //将字符串str转换为double型数字
int atoi(char *str) ; //将字符串str转换为int 型数字
long atol(char *str) ; //将字符串str转换为long int 型数字

//将int型数字digit按radix进制转换成字符串destStr
char * itoa (int digit, char *destStr, int radix) ;
//同理将long型数字转换成字符串
char * ltoa (long digit, char *destStr, int radix) ;
//同理将unsignedlong型数字转换成字符串
char * ultoa (long digit, char *destStr,int radix) ;
  • in cstring
char * strcpy (char *s1, char *s2) ; //将字符串s2拷贝到数组s1中。
char * strncpy(char *s1,char *s2) ; //将字符串s2的最多n个字符拷贝到数组s1中
char * strcat (char *s1, char * s2) ; //将字符串s2连接在字符串s1尾部
char * strncat(char *s1, char *s2, size_tn) ; //将字符串s2中最多n个字符连接在s1之后

【注意:以上操作都要求目标字符数组有足够的存储空间】



//比較字符串s1,s2.假设s1等于小于或大于s2。分别返回0。负值,正值
int strcmp(char *s1, char *s2 ) ;
int stricmp(char *s1, char *s2) ;//不区分大写和小写地比較两字符串
int strncmp(char *s1, char *s2, size_t n) ;//比較两字符串的至多n个字符


//在字符串str中查找字符ch第一次出现的位置,假设找到了,就返回str中ch的指针,否则返回NULL
char *strchr(char*str, int ch) ;
//查找字符串str中字符ch的最后一次出现的位置(即:从后往前查找)
char*strrchr(char *str, int ch) ;
//查找字符串str1中第一次出现字符串str2的位置
char *strstr(char*str1, char *str2) ;
//查找字符串str2中随意字符在字符串str1中首次出现的位置。
char*strpbrk(char *str1, char *str2)


string类的构造函数:
string(const char *s); //用c字符串s初始化
string(int n,char c); //用n个字符c初始化
此外,string类还支持默认构造函数和复制构造函数,如string s1;string s2="hello";都是正确的写法。当构造的string太长而无法表达时会抛出length_error异常
string类的字符操作:
const char &operator[](int n)const;
const char &at(int n)const;
char &operator[](int n);
char &at(int n);
operator[]和at()均返回当前字符串中第n个字符的位置,但at函数提供范围检查,当越界时会抛出out_of_range异常,下标运算符[]不提供检查访问。
const char *data()const;//返回一个非null终止的c字符数组
const char *c_str()const;//返回一个以null终止的c字符串
int copy(char *s, int n, int pos = 0) const;//把当前串中以pos开始的n个字符拷贝到以s为起始位置的字符数组中,返回实际拷贝的数目
string的特性描述:
int capacity()const; //返回当前容量(即string中不必增加内存即可存放的元素个数)
int max_size()const; //返回string对象中可存放的最大字符串的长度
int size()const; //返回当前字符串的大小
int length()const; //返回当前字符串的长度
bool empty()const; //当前字符串是否为空
void resize(int len,char c);//把字符串当前大小置为len,并用字符c填充不足的部分
string类的输入输出操作:
string类重载运算符operator>>用于输入,同样重载运算符operator<<用于输出操作。
函数getline(istream &in,string &s);用于从输入流in中读取字符串到s中,以换行符'\n'分开。

string的赋值:
string &operator=(const string &s);//把字符串s赋给当前字符串
string &assign(const char *s);//用c类型字符串s赋值
string &assign(const char *s,int n);//用c字符串s开始的n个字符赋值
string &assign(const string &s);//把字符串s赋给当前字符串
string &assign(int n,char c);//用n个字符c赋值给当前字符串
string &assign(const string &s,int start,int n);//把字符串s中从start开始的n个字符赋给当前字符串
string &assign(const_iterator first,const_itertor last);//把first和last迭代器之间的部分赋给字符串

string的连接:
string &operator+=(const string &s);//把字符串s连接到当前字符串的结尾
string &append(const char *s); //把c类型字符串s连接到当前字符串结尾
string &append(const char *s,int n);//把c类型字符串s的前n个字符连接到当前字符串结尾
string &append(const string &s); //同operator+=()
string &append(const string &s,int pos,int n);//把字符串s中从pos开始的n个字符连接到当前字符串的结尾
string &append(int n,char c); //在当前字符串结尾添加n个字符c
string &append(const_iterator first,const_iterator last);//把迭代器first和last之间的部分连接到当前字符串的结尾

string的比较:
bool operator==(const string &s1,const string &s2)const;//比较两个字符串是否相等
运算符">","<",">=","<=","!="均被重载用于字符串的比较;
int compare(const string &s) const;//比较当前字符串和s的大小
int compare(int pos, int n,const string &s)const;//比较当前字符串从pos开始的n个字符组成的字符串与s的大小
int compare(int pos, int n,const string &s,int pos2,int n2)const;//比较当前字符串从pos开始的n个字符组成的字符串与s中pos2开始的n2个字符组成的字符串的大小
int compare(const char *s) const;
int compare(int pos, int n,const char *s) const;
int compare(int pos, int n,const char *s, int pos2) const;
compare函数在>时返回1,<时返回-1,==时返回0
string的子串:
string substr(int pos = 0,int n = npos) const;//返回pos开始的n个字符组成的字符串

string的交换:
void swap(string &s2); //交换当前字符串与s2的值

string类的查找函数:
int find(char c, int pos = 0) const;//从pos开始查找字符c在当前字符串的位置
int find(const char *s, int pos = 0) const;//从pos开始查找字符串s在当前串中的位置
int find(const char *s, int pos, int n) const;//从pos开始查找字符串s中前n个字符在当前串中的位置
int find(const string &s, int pos = 0) const;//从pos开始查找字符串s在当前串中的位置
//查找成功时返回所在位置,失败返回string::npos的值
int rfind(char c, int pos = npos) const;//从pos开始从后向前查找字符c在当前串中的位置
int rfind(const char *s, int pos = npos) const;
int rfind(const char *s, int pos, int n = npos) const;
int rfind(const string &s,int pos = npos) const;
//从pos开始从后向前查找字符串s中前n个字符组成的字符串在当前串中的位置,成功返回所在位置,失败时返回string::npos的值
int find_first_of(char c, int pos = 0) const;//从pos开始查找字符c第一次出现的位置
int find_first_of(const char *s, int pos = 0) const;
int find_first_of(const char *s, int pos, int n) const;
int find_first_of(const string &s,int pos = 0) const;
//从pos开始查找当前串中第一个在s的前n个字符组成的数组里的字符的位置。查找失败返回string::npos
int find_first_not_of(char c, int pos = 0) const;
int find_first_not_of(const char *s, int pos = 0) const;
int find_first_not_of(const char *s, int pos,int n) const;
int find_first_not_of(const string &s,int pos = 0) const;
//从当前串中查找第一个不在串s中的字符出现的位置,失败返回string::npos
int find_last_of(char c, int pos = npos) const;
int find_last_of(const char *s, int pos = npos) const;
int find_last_of(const char *s, int pos, int n = npos) const;
int find_last_of(const string &s,int pos = npos) const;
int find_last_not_of(char c, int pos = npos) const;
int find_last_not_of(const char *s, int pos = npos) const;
int find_last_not_of(const char *s, int pos, int n) const;
int find_last_not_of(const string &s,int pos = npos) const;
//find_last_of和find_last_not_of与find_first_of和find_first_not_of相似,只不过是从后向前查找

string类的替换函数:
string &replace(int p0, int n0,const char *s);//删除从p0开始的n0个字符,然后在p0处插入串s
string &replace(int p0, int n0,const char *s, int n);//删除p0开始的n0个字符,然后在p0处插入字符串s的前n个字符
string &replace(int p0, int n0,const string &s);//删除从p0开始的n0个字符,然后在p0处插入串s
string &replace(int p0, int n0,const string &s, int pos, int n);//删除p0开始的n0个字符,然后在p0处插入串s中从pos开始的n个字符
string &replace(int p0, int n0,int n, char c);//删除p0开始的n0个字符,然后在p0处插入n个字符c
string &replace(iterator first0, iterator last0,const char *s);//把[first0,last0)之间的部分替换为字符串s
string &replace(iterator first0, iterator last0,const char *s, int n);//把[first0,last0)之间的部分替换为s的前n个字符
string &replace(iterator first0, iterator last0,const string &s);//把[first0,last0)之间的部分替换为串s
string &replace(iterator first0, iterator last0,int n, char c);//把[first0,last0)之间的部分替换为n个字符c
string &replace(iterator first0, iterator last0,const_iterator first, const_iterator last);//把[first0,last0)之间的部分替换成[first,last)之间的字符串

string类的插入函数:
string &insert(int p0, const char *s);
string &insert(int p0, const char *s, int n);
string &insert(int p0,const string &s);
string &insert(int p0,const string &s, int pos, int n);
//前4个函数在p0位置插入字符串s中pos开始的前n个字符
string &insert(int p0, int n, char c);//此函数在p0处插入n个字符c
iterator insert(iterator it, char c);//在it处插入字符c,返回插入后迭代器的位置
void insert(iterator it, const_iterator first, const_iterator last);//在it处插入[first,last)之间的字符
void insert(iterator it, int n, char c);//在it处插入n个字符c

string类的删除函数
iterator erase(iterator first, iterator last);//删除[first,last)之间的所有字符,返回删除后迭代器的位置
iterator erase(iterator it);//删除it指向的字符,返回删除后迭代器的位置
string &erase(int pos = 0, int n = npos);//删除pos开始的n个字符,返回修改后的字符串

string类的迭代器处理:
string类提供了向前和向后遍历的迭代器iterator,迭代器提供了访问各个字符的语法,类似于指针操作,迭代器不检查范围。
string::iterator或string::const_iterator声明迭代器变量,const_iterator不允许改变迭代的内容。常用迭代器函数有:
const_iterator begin()const;
iterator begin(); //返回string的起始位置
const_iterator end()const;
iterator end(); //返回string的最后一个字符后面的位置
const_iterator rbegin()const;
iterator rbegin(); //返回string的最后一个字符的位置
const_iterator rend()const;
iterator rend(); //返回string第一个字符位置的前面
rbegin和rend用于从后向前的迭代访问,通过设置迭代器string::reverse_iterator,string::const_reverse_iterator实现

字符串流处理:
通过定义ostringstreamistringstream变量实现,<sstream>头文件中
例如:
string input("hello,this is a test");
istringstream is(input);
string s1,s2,s3,s4;
is>>s1>>s2>>s3>>s4;//s1="hello,this",s2="is",s3="a",s4="test"
ostringstream os;
os<<s1<<s2<<s3<<s4;
cout<<os.str();

***************************************************************************************************

c++中的string常用函数用法总结

标准c++中string类函数介绍

注意不是CString
之所以抛弃char*的字符串而选用C++标准程序库中的string类,是因为他和前者比较起来,不必 担心内存是否足够、字符串长度等等,而且作为一个类出现,他集成的操作函数足以完成我们大多数情况下(甚至是100%)的需要。我们可以用 = 进行赋值操作,== 进行比较,+ 做串联(是不是很简单?)。我们尽可以把它看成是C++的基本数据类型。
好了,进入正题………
首先,为了在我们的程序中使用string类型,我们必须包含头文件 <string>。
如下:
#include <string> //注意这里不是string.h string.h是C字符串头文件
#include <string>
using namespace std;
1.声明一个C++字符串
声明一个字符串变量很简单:
string Str;
这样我们就声明了一个字符串变量,但既然是一个类,就有构造函数和析构函数。上面的声明没有传入参数,所以就直接使用了string的默认的构造函数,这个函数所作的就是把Str初始化为一个空字符串。String类的构造函数和析构函数如下:
a) string s; //生成一个空字符串s
b) string s(str) //拷贝构造函数 生成str的复制品
c) string s(str,stridx) //将字符串str内“始于位置stridx”的部分当作字符串的初值
d) string s(str,stridx,strlen) //将字符串str内“始于stridx且长度顶多strlen”的部分作为字符串的初值
e) string s(cstr) //将C字符串作为s的初值
f) string s(chars,chars_len) //将C字符串前chars_len个字符作为字符串s的初值。
g) string s(num,c) //生成一个字符串,包含num个c字符
h) string s(beg,end) //以区间beg;end(不包含end)内的字符作为字符串s的初值
i) s.~string() //销毁所有字符,释放内存
都很简单,我就不解释了。
2.字符串操作函数
这里是C++字符串的重点,我先把各种操作函数罗列出来,不喜欢把所有函数都看完的人可以在这里找自己喜欢的函数,再到后面看他的详细解释。
a) =,assign() //赋以新值
b) swap() //交换两个字符串的内容
c) +=,append(),push_back() //在尾部添加字符
d) insert() //插入字符
e) erase() //删除字符
f) clear() //删除全部字符
g) replace() //替换字符
h) + //串联字符串
i) ==,!=,<,<=,>,>=,compare() //比较字符串
j) size(),length() //返回字符数量
k) max_size() //返回字符的可能最大个数
l) empty() //判断字符串是否为空
m) capacity() //返回重新分配之前的字符容量
n) reserve() //保留一定量内存以容纳一定数量的字符
o) [ ], at() //存取单一字符
p) >>,getline() //从stream读取某值
q) << //将谋值写入stream
r) copy() //将某值赋值为一个C_string
s) c_str() //将内容以C_string返回
t) data() //将内容以字符数组形式返回
u) substr() //返回某个子字符串
v)查找函数
w)begin() end() //提供类似STL的迭代器支持
x) rbegin() rend() //逆向迭代器
y) get_allocator() //返回配置器
下面详细介绍:
21 C++字符串和C字符串的转换
C ++提供的由C++字符串得到对应的C_string的方法是使用data()、c_str()和copy(),其中,data()以字符数组的形式返回字符串内容,但并不添加'/0'。c_str()返回一个以‘/0'结尾的字符数组,而copy()则把字符串的内容复制或写入既有的c_string或 字符数组内。C++字符串并不以'/0'结尾。我的建议是在程序中能使用C++字符串就使用,除非万不得已不选用c_string。由于只是简单介绍,详细介绍掠过,谁想进一步了解使用中的注意事项可以给我留言(到我的收件箱)。我详细解释。
22 大小和容量函数
一个C++字符串存在三种大小:a)现有的字符数,函数是size()和length(),他们等效。Empty()用来检查字符串是否为空。b)max_size() 这个大小是指当前C++字符串最多能包含的字符数,很可能和机器本身的限制或者字符串所在位置连续内存的大小有关系。我们一般情况下不用关心他,应该大小足够我们用的。但是不够用的话,会抛出length_error异常c)capacity()重新分配内存之前 string所能包含的最大字符数。这里另一个需要指出的是reserve()函数,这个函数为string重新分配内存。重新分配的大小由其参数决定, 默认参数为0,这时候会对string进行非强制性缩减。

还有必要再重复一下C++字符串和C字符串转换的问 题,许多人会遇到这样的问题,自己做的程序要调用别人的函数、类什么的(比如数据库连接函数Connect(char*,char*)),但别人的函数参 数用的是char*形式的,而我们知道,c_str()、data()返回的字符数组由该字符串拥有,所以是一种const char*,要想作为上面提及的函数的参数,还必须拷贝到一个char*,而我们的原则是能不使用C字符串就不使用。那么,这时候我们的处理方式是:如果 此函数对参数(也就是char*)的内容不修改的话,我们可以这样Connect((char*)UserID.c_str(), (char*)PassWD.c_str()),但是这时候是存在危险的,因为这样转换后的字符串其实是可以修改的(有兴趣地可以自己试一试),所以我强调除非函数调用的时候不对参数进行修改,否则必须拷贝到一个char*上去。当然,更稳妥的办法是无论什么情况都拷贝到一个char*上去。同时我们也祈祷现在仍然使用C字符串进行编程的高手们(说他们是高手一点儿也不为过,也许在我们还穿开裆裤的时候他们就开始编程了,哈哈…)写的函数都比较规范,那样我们就不必进行强制转换了。
23元素存取
我们可以使用下标操作符[]和函数at()对元素包含的字符进行访问。但是应该注意的是操作符[]并不检查索引是否有效(有效索引0~str.length()),如果索引失效,会引起未定义的行为。而at()会检查,如果使用 at()的时候索引无效,会抛出out_of_range异常。
有一个例外不得不说,const string a;的操作符[]对索引值是a.length()仍然有效,其返回值是'/0'。其他的各种情况,a.length()索引都是无效的。举例如下:
const string Cstr(“const string”);
string Str(“string”);
Str[3]; //ok
Str.at(3); //ok
Str[100]; //未定义的行为
Str.at(100); //throw out_of_range
Str[Str.length()] //未定义行为
Cstr[Cstr.length()] //返回 ‘/0'
Str.at(Str.length());//throw out_of_range
Cstr.at(Cstr.length()) throw out_of_range
我不赞成类似于下面的引用或指针赋值:
char& r=s[2];
char* p= &s[3];
因为一旦发生重新分配,r,p立即失效。避免的方法就是不使用。
24比较函数
C ++字符串支持常见的比较操作符(>,>=,<,<=,==,!=),甚至支持string与C-string的比较(如 str<”hello”)。在使用>,>=,<,<=这些操作符的时候是根据“当前字符特性”将字符按字典顺序进行逐一得 比较。字典排序靠前的字符小,比较的顺序是从前向后比较,遇到不相等的字符就按这个位置上的两个字符的比较结果确定两个字符串的大小。同时,string (“aaaa”) <string(aaaaa)。
另一个功能强大的比较函数是成员函数compare()。他支持多参数处理,支持用索引值和长度定位子串来进行比较。他返回一个整数来表示比较结果,返回值意义如下:0-相等 〉0-大于 <0-小于。举例如下:
string s(“abcd”);
s.compare(“abcd”); //返回0
s.compare(“dcba”); //返回一个小于0的值
s.compare(“ab”); //返回大于0的值
s.compare(s); //相等
s.compare(0,2,s,2,2); //用”ab”和”cd”进行比较 小于零
s.compare(1,2,”bcx”,2); //用”bc”和”bc”比较。
怎么样?功能够全的吧!什么?还不能满足你的胃口?好吧,那等着,后面有更个性化的比较算法。先给个提示,使用的是STL的比较算法。什么?对STL一窍不通?靠,你重修吧!
25 更改内容
这在字符串的操作中占了很大一部分。
首先讲赋值,第一个赋值方法当然是使用操作符=,新值可以是string(如:s=ns) 、c_string(如:s=”gaint”)甚至单一字符(如:s='j')。还可以使用成员函数assign(),这个成员函数可以使你更灵活的对字符串赋值。还是举例说明吧:
s.assign(str); //不说
s.assign(str,1,3);//如果str是”iamangel” 就是把”ama”赋给字符串
s.assign(str,2,string::npos);//把字符串str从索引值2开始到结尾赋给s
s.assign(“gaint”); //不说
s.assign(“nico”,5);//把'n' ‘I' ‘c' ‘o' ‘/0'赋给字符串
s.assign(5,'x');//把五个x赋给字符串
把字符串清空的方法有三个:s=””;s.clear();s.erase();(我越来越觉得举例比说话让别人容易懂!)。
string提供了很多函数用于插入(insert)、删除(erase)、替换(replace)、增加字符。
先说增加字符(这里说的增加是在尾巴上),函数有 +=、append()、push_back()。
举例如下:
s+=str;//加个字符串
s+=”my name is jiayp”;//加个C字符串
s+='a';//加个字符
s.append(str);
s.append(str,1,3);//不解释了 同前面的函数参数assign的解释
s.append(str,2,string::npos)//不解释了
s.append(“my name is jiayp”);
s.append(“nico”,5);
s.append(5,'x');
s.push_back(‘a');//这个函数只能增加单个字符对STL熟悉的理解起来很简单
也许你需要在string中间的某个位置插入字符串,这时候你可以用insert()函数,这个函数需要你指定一个安插位置的索引,被插入的字符串将放在这个索引的后面。
s.insert(0,”my name”);
s.insert(1,str);
这种形式的insert()函数不支持传入单个字符,这时的单个字符必须写成字符串形式(让人恶心)。既然你觉得恶心,那就不得不继续读下面一段话:为了插 入单个字符,insert()函数提供了两个对插入单个字符操作的重载函数:insert(size_type index,size_type num,chart c)和insert(iterator pos,size_type num,chart c)。其中size_type是无符号整数,iterator是char*,所以,你这么调用insert函数是不行的:insert(0,1, 'j');这时候第一个参数将转换成哪一个呢?所以你必须这么写:insert((string::size_type)0,1,'j')!第二种形式指 出了使用迭代器安插字符的形式,在后面会提及。顺便提一下,string有很多操作是使用STL的迭代器的,他也尽量做得和STL靠近。
删除函数erase()的形式也有好几种(真烦!),替换函数replace()也有好几个。
举例吧:
string s=”il8n”;
s.replace(1,2,”nternationalizatio”);//从索引1开始的2个替换成后面的C_string
s.erase(13);//从索引13开始往后全删除
s.erase(7,5);//从索引7开始往后删5个
26提取子串和字符串连接
题取子串的函数是:substr(),形式如下:
s.substr();//返回s的全部内容
s.substr(11);//从索引11往后的子串
s.substr(5,6);//从索引5开始6个字符
把两个字符串结合起来的函数是+。(谁不明白请致电120
27输入输出操作
1.>> 从输入流读取一个string
2.<< 把一个string写入输出流。
另一个函数就是getline(),他从输入流读取一行内容,直到遇到分行符或到了文件尾。
28搜索与查找
查找函数很多,功能也很强大,包括了:
find()
rfind()
find_first_of()
find_last_of()
find_first_not_of()
find_last_not_of()
这些函数返回符合搜索条件的字符区间内的第一个字符的索引,没找到目标就返回npos。所有的函数的参数说明如下:
第一个参数是被搜寻的对象。第二个参数(可有可无)指出string内的搜寻起点索引,第三个参数(可有可无)指出搜寻的字符个数。比较简单,不多说不理解的可以向我提出,我再仔细的解答。当然,更加强大的STL搜寻在后面会有提及。

最后再说说npos的含义,string::npos的类型是string::size_type,所以,一旦需要把一个索引与npos相比,这个索引值必须是string::size)type类型的,更多的情况下,我们可以直接把函数和npos进行比较(如:if(s.find(“jia”)== string::npos))。
string类的构造函数:
string(const char *s); //用c字符串s初始化
string(int n,char c); //用n个字符c初始化
此外,string类还支持默认构造函数和复制构造函数,如string s1;string s2="hello";都是正确的写法。当构造的string太长而无法表达时会抛出length_error异常
string类的字符操作:
const char &operator[](int n)const;
const char &at(int n)const;
char &operator[](int n);
char &at(int n);
operator[]和at()均返回当前字符串中第n个字符的位置,但at函数提供范围检查,当越界时会抛出out_of_range异常,下标运算符[]不提供检查访问。
const char *data()const;//返回一个非null终止的c字符数组
const char *c_str()const;//返回一个以null终止的c字符串
int copy(char *s, int n, int pos = 0) const;//把当前串中以pos开始的n个字符拷贝到以s为起始位置的字符数组中,返回实际拷贝的数目
string的特性描述:
int capacity()const; //返回当前容量(即string中不必增加内存即可存放的元素个数)
int max_size()const; //返回string对象中可存放的最大字符串的长度
int size()const; //返回当前字符串的大小
int length()const; //返回当前字符串的长度
bool empty()const; //当前字符串是否为空
void resize(int len,char c);//把字符串当前大小置为len,并用字符c填充不足的部分
string类的输入输出操作:
string类重载运算符operator>>用于输入,同样重载运算符operator<<用于输出操作。
函数getline(istream &in,string &s);用于从输入流in中读取字符串到s中,以换行符'\n'分开。
string的赋值:
string &operator=(const string &s);//把字符串s赋给当前字符串
string &assign(const char *s);//用c类型字符串s赋值
string &assign(const char *s,int n);//用c字符串s开始的n个字符赋值
string &assign(const string &s);//把字符串s赋给当前字符串
string &assign(int n,char c);//用n个字符c赋值给当前字符串
string &assign(const string &s,int start,int n);//把字符串s中从start开始的n个字符赋给当前字符串
string &assign(const_iterator first,const_itertor last);//把first和last迭代器之间的部分赋给字符串
string的连接:
string &operator+=(const string &s);//把字符串s连接到当前字符串的结尾
string &append(const char *s); //把c类型字符串s连接到当前字符串结尾
string &append(const char *s,int n);//把c类型字符串s的前n个字符连接到当前字符串结尾
string &append(const string &s); //同operator+=()
string &append(const string &s,int pos,int n);//把字符串s中从pos开始的n个字符连接到当前字符串的结尾
string &append(int n,char c); //在当前字符串结尾添加n个字符c
string &append(const_iterator first,const_iterator last);//把迭代器first和last之间的部分连接到当前字符串的结尾
string的比较:
bool operator==(const string &s1,const string &s2)const;//比较两个字符串是否相等
运算符">","<",">=","<=","!="均被重载用于字符串的比较;
int compare(const string &s) const;//比较当前字符串和s的大小
int compare(int pos, int n,const string &s)const;//比较当前字符串从pos开始的n个字符组成的字符串与s的大小
int compare(int pos, int n,const string &s,int pos2,int n2)const;//比较当前字符串从pos开始的n个字符组成的字符串与s中pos2开始的n2个字符组成的字符串的大小
int compare(const char *s) const;
int compare(int pos, int n,const char *s) const;
int compare(int pos, int n,const char *s, int pos2) const;
compare函数在>时返回1,<时返回-1,==时返回0
string的子串:
string substr(int pos = 0,int n = npos) const;//返回pos开始的n个字符组成的字符串
string的交换:
void swap(string &s2); //交换当前字符串与s2的值
string类的查找函数:
int find(char c, int pos = 0) const;//从pos开始查找字符c在当前字符串的位置
int find(const char *s, int pos = 0) const;//从pos开始查找字符串s在当前串中的位置
int find(const char *s, int pos, int n) const;//从pos开始查找字符串s中前n个字符在当前串中的位置
int find(const string &s, int pos = 0) const;//从pos开始查找字符串s在当前串中的位置
//查找成功时返回所在位置,失败返回string::npos的值
int rfind(char c, int pos = npos) const;//从pos开始从后向前查找字符c在当前串中的位置
int rfind(const char *s, int pos = npos) const;
int rfind(const char *s, int pos, int n = npos) const;
int rfind(const string &s,int pos = npos) const;
//从pos开始从后向前查找字符串s中前n个字符组成的字符串在当前串中的位置,成功返回所在位置,失败时返回string::npos的值
int find_first_of(char c, int pos = 0) const;//从pos开始查找字符c第一次出现的位置
int find_first_of(const char *s, int pos = 0) const;
int find_first_of(const char *s, int pos, int n) const;
int find_first_of(const string &s,int pos = 0) const;
//从pos开始查找当前串中第一个在s的前n个字符组成的数组里的字符的位置。查找失败返回string::npos
int find_first_not_of(char c, int pos = 0) const;
int find_first_not_of(const char *s, int pos = 0) const;
int find_first_not_of(const char *s, int pos,int n) const;
int find_first_not_of(const string &s,int pos = 0) const;
//从当前串中查找第一个不在串s中的字符出现的位置,失败返回string::npos
int find_last_of(char c, int pos = npos) const;
int find_last_of(const char *s, int pos = npos) const;
int find_last_of(const char *s, int pos, int n = npos) const;
int find_last_of(const string &s,int pos = npos) const;
int find_last_not_of(char c, int pos = npos) const;
int find_last_not_of(const char *s, int pos = npos) const;
int find_last_not_of(const char *s, int pos, int n) const;
int find_last_not_of(const string &s,int pos = npos) const;
//find_last_of和find_last_not_of与find_first_of和find_first_not_of相似,只不过是从后向前查找
string类的替换函数:
string &replace(int p0, int n0,const char *s);//删除从p0开始的n0个字符,然后在p0处插入串s
string &replace(int p0, int n0,const char *s, int n);//删除p0开始的n0个字符,然后在p0处插入字符串s的前n个字符
string &replace(int p0, int n0,const string &s);//删除从p0开始的n0个字符,然后在p0处插入串s
string &replace(int p0, int n0,const string &s, int pos, int n);//删除p0开始的n0个字符,然后在p0处插入串s中从pos开始的n个字符
string &replace(int p0, int n0,int n, char c);//删除p0开始的n0个字符,然后在p0处插入n个字符c
string &replace(iterator first0, iterator last0,const char *s);//把[first0,last0)之间的部分替换为字符串s
string &replace(iterator first0, iterator last0,const char *s, int n);//把[first0,last0)之间的部分替换为s的前n个字符
string &replace(iterator first0, iterator last0,const string &s);//把[first0,last0)之间的部分替换为串s
string &replace(iterator first0, iterator last0,int n, char c);//把[first0,last0)之间的部分替换为n个字符c
string &replace(iterator first0, iterator last0,const_iterator first, const_iterator last);//把[first0,last0)之间的部分替换成[first,last)之间的字符串
string类的插入函数:
string &insert(int p0, const char *s);
string &insert(int p0, const char *s, int n);
string &insert(int p0,const string &s);
string &insert(int p0,const string &s, int pos, int n);
//前4个函数在p0位置插入字符串s中pos开始的前n个字符
string &insert(int p0, int n, char c);//此函数在p0处插入n个字符c
iterator insert(iterator it, char c);//在it处插入字符c,返回插入后迭代器的位置
void insert(iterator it, const_iterator first, const_iterator last);//在it处插入[first,last)之间的字符
void insert(iterator it, int n, char c);//在it处插入n个字符c
string类的删除函数
iterator erase(iterator first, iterator last);//删除[first,last)之间的所有字符,返回删除后迭代器的位置
iterator erase(iterator it);//删除it指向的字符,返回删除后迭代器的位置
string &erase(int pos = 0, int n = npos);//删除pos开始的n个字符,返回修改后的字符串
string类的迭代器处理:
string类提供了向前和向后遍历的迭代器iterator,迭代器提供了访问各个字符的语法,类似于指针操作,迭代器不检查范围。
string::iterator或string::const_iterator声明迭代器变量,const_iterator不允许改变迭代的内容。常用迭代器函数有:
const_iterator begin()const;
iterator begin(); //返回string的起始位置
const_iterator end()const;
iterator end(); //返回string的最后一个字符后面的位置
const_iterator rbegin()const;
iterator rbegin(); //返回string的最后一个字符的位置
const_iterator rend()const;
iterator rend(); //返回string第一个字符位置的前面
rbegin和rend用于从后向前的迭代访问,通过设置迭代器string::reverse_iterator,string::const_reverse_iterator实现
字符串流处理:
通过定义ostringstreamistringstream变量实现,<sstream>头文件中
例如:
string input("hello,this is a test");
istringstream is(input);
string s1,s2,s3,s4;
is>>s1>>s2>>s3>>s4;//s1="hello,this",s2="is",s3="a",s4="test"
ostringstream os;
os<<s1<<s2<<s3<<s4;
cout<<os.str();

并查集:

杂七杂八

并查集是个很简单的基础数据结构,但是真的很有用。

                       --南外的lqs神仙于国庆节的成外

(现在还依稀记得lqs神仙讲图论和基础数据结构时候的那种……)

(晕圈的感觉)

发现自己已经不会写并查集了……

重新学习吧……

算法和两种优化

并查集是一个能够维护很多个不重叠集合的数据结构

支持两种操作 :

  1. Root 查询元素所处的集合。

  2. Union 合并两个集合。

考虑用树形结构储存集合。

对于每一个集合,根节点就是这个集合的“象征”。

我们对于每一个节点 $i$ ,有一个指针指向它的父亲节点 $\text{pa}[i]$ ,代表他是属于集合 $\text{pa}[i]$的。

如果这个节点是树根,那么同理,它的 $\text{pa}[]$ 就是自己本身。

不难发现,我们维护的这个结构实际上是由很多个储存集合的树构成的森林。

那么对于查询操作,我们只需要递归查询它的树根就可以了。

也就是这样的。

int root(int x){
if(pa[x]!=x){
return root(pa[x]);//不是树根,递归。
}
return pa[x];//已经是树根了
}

那么在最开始的时候,每一个元素都是独立的。

我们考虑这样初始化(也就是让每一个元素都是一个集合):

for(register int i=1;i<=n;++i){
pa[i]=i;
}

我最开始学的时候有过这样一个想法:
直接用 $\text{pa}[x]$ 储存 $x$ 在哪一个集合里面。

但是很快就被否决了……

因为这样子合并的时候会十分麻烦……

后来 lqs 说了一个路径压缩的优化。就是利用了这个的思想。

因为我们只关心的是每个集合的根节点。

所以为什么要去管树的结构呢?

我们又不是在写平衡树……

那么就有一种优化。

比如我们查询节点 $x$ (蓝色箭头表示我们查询之后递归的那个去向)

cSnuPH.png

可以看到,我们在这中间经过了两个另外的节点。

它们和 $x$ 都在同一条到 $\text{root}$ 的链上。

所以我们直接把它们的 $\text{pa}[]$ 全部指向 $\text{root}$ 。

like is: (这里的蓝色箭头表示我们把它们的 $\text{pa}[]$ 全部 指向了 $\text{root}$)

cSnKGd.png

所以在递归查询的时候顺便赋一个值就可以达到这种效果。

int root(int x){
if(pa[x]!=x){
pa[x]=root(pa[x]);//优化
}
return pa[x];
}

我们将这种优化称之为 “路径压缩” 。

考虑合并集合的操作。

对于两个集合 $set_x$ 和 $set_y$

我们根据这一条 :

如果这个节点是树根,那么,它的 $\text{pa}[]$ 就是自己本身。

我们不难想到,只要任意的让 $set_x$ 或者 $set_y$ 的 $\text{root}$ 的 $pa[]$ 指向另外一个集合的 $\text{root}$ 就好了.

void Union(int x,int y){
return (void)(pa[root(x)]=root(y));
}

不过这个仍然不是最优的……

考虑这一句话:

只要 任意的 让 $set_x$ 或者 $set_y$ 的 $\text{root}$ 的 $pa[]$ 指向另外一个集合的 $\text{root}$ 就好了.

任意?怎么任意?能不能有更优的做法?

有的,这是一种启发式合并

我们维护每一个集合的元素个数。

然后让元素少的集合的根变成元素大的集合的子节点。

这样子我们只会增加小的集合的查询代价(就是说你要多找一个点(那个大集合的根节点))

那么合并之后的查询代价增加就会小。效率就会更高。

当然我们维护的是一个森林。所以也可以维护他们的深度(优化的东西同理)。

void Union(int x,int y){
int rx=root(x);
int ry=root(y);
if(rx==ry){
return;
}
if(size_[rx]>size_[ry]){//size_维护每一个集合的元素个数/深度。
pa[ry]=rx;
size_[rx]+=size_[ry];
}
else{
pa[rx]=ry;
size_[ry]+=size_[rx];
}优化
}

这个优化就是“按秩合并”。

不过如果这样子做,开始的时候就要加上

for(register int i=1;i<=n;++i){
pa[i]=i;
size_[i]=i;//维护深度
//size_[i]=1; //维护个数
}

例题:

  • P1955 [NOI2015] 程序自动分析
Description
在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本:假设x1,x2,x3,…代表程序中出现的变量,给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:x1=x2,x2=x3,x3=x4,x1≠x4,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。
现在给出一些约束满足问题,请分别对它们进行判定。
Input
输入文件的第1行包含1个正整数t,表示需要判定的问题个数。注意这些问题之 间是相互独立的。
对于每个问题,包含若干行:
第1行包含1个正整数n,表示该问题中需要被满足的约束条件个数。
接下来n行,每行包括3个整数i,j,e,描述1个相等/不等的约束条件,相邻整数之间用单个空格隔开。若e=1,则该约束条件为xi=xj;若e=0,则该约束条件为xi≠xj。
Output
输出文件包括t行。
输出文件的第k行输出一个字符串“YES”或者“NO”(不包含引号,字母全部大写),“YES”表示输入中的第k个问题判定为可以被满足,“NO”表示不可被满足。
Sample Input
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
Sample Output
NO
YES
HINT

在第一个问题中,约束条件为:x1=x2,x1≠x2。这两个约束条件互相矛盾,因此不可被同时满足。

在第二个问题中,约束条件为:x1=x2,x2=x1。这两个约束条件是等价的,可以被同时满足。

1≤n≤1000000
1≤i,j≤1000000000

这道题是一道比较经典的题。

我们可以发现,这道题如果不满足,那么一定会出现:

$x_i=x_j , x_j\not=x_k,x_k=x_i$

这种“自相矛盾的”关系。

我们注意到,这里用的 $=$ 是有传递性

所以我们只需要把所有 $=$ 的情况扔到一个并查集里面维护。

然后拿不等于的式子去判断 $x_i \not= x_j$ 时, $x_i,x_j$ 在不在同一个集合里就好了。

从这里可以发现,并查集可以维护具有 传递性 的集合关系。

(注意本题数据范围,需要离散)

离散的部分大概是这样子的:

vector<int>v;
int main(){
for(register int i=1;i<=n;i++){
scanf("%d%d%d",&x[i],&y[i],&e[i]);
v.push_back(x[i]);
v.push_back(y[i]);
}
sort(v.begin(),v.end());//排序
v.erase(unique(v.begin(),v.end()),v.end());//去重
for(register int i=1;i<=n;i++){
x[i]=lower_bound(v.begin(),v.end(),x[i])-v.begin()+1;
y[i]=lower_bound(v.begin(),v.end(),y[i])-v.begin()+1;//取出来
//这里是把坐标映射成了它的序号。
}
}

带权并查集

有的时候题目里面会出现“带边权的元素”,要求你维护这些元素的同时还要维护它们的边权(也可以是由“信息”转化得来的“边权”)。

那么我们维护一个数组 $d[]$ ,$d[u]$ 表示 $u$ 节点到$pa[u]$ 之间的边权。

在路径压缩的时候,我们同时更新$d$ ,并且利用路径压缩来统计信息。

这里用一道例题讲解。

  • 银河英雄传说[NOI2002]

有一个划分为N列的星际战场,各列依次编号为1,2,…,N。

有N艘战舰,也依次编号为1,2,…,N,其中第i号战舰处于第i列。

有T条指令,每条指令格式为以下两种之一:

1、M i j,表示让第i号战舰所在列的全部战舰保持原有顺序,接在第j号战舰所在列的尾部。

2、C i j,表示询问第i号战舰与第j号战舰当前是否处于同一列中,如果在同一列中,它们之间间隔了多少艘战舰。

现在需要你编写一个程序,处理一系列的指令。

输入格式
第一行包含整数T,表示共有T条指令。

接下来T行,每行一个指令,指令有两种形式:M i j或C i j。

其中M和C为大写字母表示指令类型,i和j为整数,表示指令涉及的战舰编号。

输出格式
你的程序应当依次对输入的每一条指令进行分析和处理:

如果是M i j形式,则表示舰队排列发生了变化,你的程序要注意到这一点,但是不要输出任何信息;

如果是C i j形式,你的程序要输出一行,仅包含一个整数,表示在同一列上,第i号战舰与第j号战舰之间布置的战舰数目,如果第i号战舰与第j号战舰当前不在同一列上,则输出-1。

数据范围
N≤30000,T≤500000
输入样例:
4
M 2 3
C 1 2
M 2 4
C 4 2
输出样例:
-1
1

可以看得出来,这里我们很明显是需要维护“边权”的。

这里的 $d[u]$ 就是战舰 $u$ 到 $pa[u]$ 中间所隔的战舰数量。

那么让每条边边权为$1$,那么我们 $root$ 操作的时候维护一下边权和。

然后路径压缩的时候$d$就直接更新为 $u$ 到根的边权和就好了。

Code:

int root(int x){
if(x!=fa[x]){
int k=fa[x];
fa[x]=root(fa[x]);
dis[x]+=dis[k];
num[x]=num[fa[x]];
}
return fa[x];
}

void Union(int x,int y){
int r1=root(x),r2=root(y);
if(r1!=r2){
fa[r1]=r2;dis[r1]=dis[r2]+num[r2];
num[r2]+=num[r1];
num[r1]=num[r2];
}
}

扩展域并查集

扩展域并查集的思想很简单。

在一个题有多种关系需要维护(而且有不同的可能来传递关系)的时候。

(大部分时候它可以维护需要处理“矛盾”并且维护“不矛盾”的信息的问题)

我们将一个节点拆成几个“域”

比如这一道题:

  • P2024 [NOI2001] 食物链
动物王国中有三类动物 A,B,C,这三类动物的食物链构成了有趣的环形。A 吃 B,B 吃 C,C 吃 A。

现有 N 个动物,以 1 - N 编号。每个动物都是 A,B,C 中的一种,但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述:

第一种说法是 1 X Y,表示 X 和 Y 是同类。
第二种说法是2 X Y,表示 X 吃 Y 。
此人对 N 个动物,用上述两种说法,一句接一句地说出 K 句话,这 K 句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

当前的话与前面的某些真的话冲突,就是假话
当前的话中 X 或 Y 比 N 大,就是假话
当前的话表示 X 吃 X,就是假话
你的任务是根据给定的 N 和 K 句话,输出假话的总数。

明显的,这一道题需要传递的东西太多了。

那么考虑对于一个元素,它可能需要维护的有什么信息?

天敌,同类,食物。

扩展域的做法就是对于每一个点拆成三个“域”来维护

cSnmIe.png

比如天敌我们用 $x_{ene}$ ,同类是 $x_{sam}$ , 食物是 $x_{eat}$

然后有种做法就是用三倍的并查集维护。

$sam=x$, $ene=x+n$, $eat=x+2n$

当然是在输入的时候维护。

只需要三个变量即可。

(因为并查集维护的时候你拿这个集合的任意元素出来合并都可以达到维护的效果)

然后考虑统计假话个数。

也就是在出现假话的时候++ans

真话那么就合并。

(当然这里要注意很多细节,注意代码的注释即可。)

代码(终于自己写了一遍):

for(register int i=1;i<=n*3;++i){
pa[i]=i;
}
for(register int i=1,x,y,op;i<=k;++i){
cin>>op>>x>>y;
if(x>n || y>n){
ans++;continue;
}
if(op==1){
if(query(en(x),y)==true || query(en(y),x)==true) ans++; // false
// x eat y || y eat x
// then false;
else{
Union(x,y);// x,y same type
Union(en(x),en(y));// same enemy
Union(fo(x),fo(y));// same food
} // true
}
else{
if(x==y){
ans++;continue;
}
if(query(x,y)==true || query(en(x),y)==true) ans++;
// x,y same type || y eat x .
// then false;
else{
Union(fo(x),y);// x eat y
Union(en(y),x);// y ate by x
Union(fo(y),en(x));// y's food eat x
}// true
}
}
return printf("%d\n",ans),0;

所以它的本质就是拆成多个值域然后看情况维护(拆点)。


fin.