不定期更新

一个宝藏

https://v.youku.com/v_show/id_XNTQ0MjA1NzUy.html

一个小 Trick

今天记一个小 Trick 吧。

.

例子

首先有一些喜闻乐见的例子

于是问题来了,

二项式

喜闻乐见的二项式定理

伸缩级数

喜闻乐见的裂项相消

求解

现在你已经知道该怎么做了吧!

接下来就是喜闻乐见的递归式

差分法

我发现 DLS 已经把这个研究得很透了。

对数列做差分。第 i 次差分的数列第 1 项是。显然. 于是有

计算 k 次差分的复杂度是的,总复杂度.

拉格朗日插值法咕咕

差比数列

不知为什么想要补一下这个。

一个等差数列,等比数列,则差比数列.

差别数列求和,使用裂项法,公式为

拉格朗日插值法

2019.6.29

对于一个 n 次多项式,可以由 n+1 个点唯一确定:.

现在我们想要求这个表达式在某个位置的值。

构造一个多项式

它被成为拉格朗日基本多项式。也称插值基函数。这个表达式有什么特点?

于是可以构造这样一个多项式

它显然经过了。于是代入一个点即可得到对应位置上的值。

化简后可以得到这个多项式的系数表示法。

取值连续

我们考虑一种特殊的情况,当时,我们得到

其中。于是得到的多项式为

预处理可以

DP 概述

先写一些 DP 概述的东西。对于一个动态规划问题,如果子问题的总数为,每个子问题需要用到个子问题的信息,那么我们称它为的问题。常见的 DP 模型如下(以下是代表取最优决策的含义。不局限)

对于一个的问题,其求解的复杂度下界通常是,其中是转移时计算代价的复杂度。

1D/1D

其中对应的决策集合,通常线性相关。是代价函数。

2D/0D

其中是求解问题时的全局常数

2D/1D

其实第 2 个方程是被第 1 个方程包含的,但相对而言第二种方程也算是很常见的

2D/2D

欧拉回路

欧拉回路指一个图中经过所有边的回路。分有向图欧拉回路和无向图欧拉回路两种。求欧拉回路可以直接采用 DFS 的方法。我们首先沿着路径不停地搜索,途中可能会掠过一些环,但我们不担心。因为我们是在回溯的时候记录路径,而回溯的时候会遍历这些没有走过的环。因此不会走漏。在搜索时可以更改前向星的头指针来剪枝。对于无向图的情况,需要记录每一条无向边(一条无向边在存的时候相当于两条有向边)是否访问过。

UOJ117

#include<algorithm>/*{{{*/
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)/*}}}*/
/******************heading******************/
const int M=1e6+5,N=1e6+5;
int t,n,m;
int a[M],la;

struct qxx{int nex,t,v;};
qxx e[M];
int h[N],le;
void add_path(int f,int t,int v){e[++le]=(qxx){h[f],t,v},h[f]=le;}

bool vis[N];
int d1[N],d2[N];
void dfs(int u){
    for(int i=h[u];i;i=h[u]){
        while(i&&vis[e[i].v])i=e[i].nex;
        h[u]=i;
        const int v=e[i].t,w=e[i].v;
        if(i)vis[w]=1,dfs(v),a[++la]=i%2?w:(t==2?w:-w);
    }
}

int main(){
    scanf("%d%d%d",&t,&n,&m);
    int u1,v1;
    FOR(i,1,m){
        scanf("%d%d",&u1,&v1);
        add_path(u1,v1,i);
        if(t==1)add_path(v1,u1,i);
        d1[u1]++,d2[v1]++;
    }
    FOR(i,1,n)if((d1[i]&1)^(d2[i]&1)||(t==2&&d1[i]!=d2[i]))return puts("NO"),0;
    dfs(u1);
    if(la<m)return puts("NO"),0;
    puts("YES");
    ROF(i,la,1)printf("%d ",a[i]);
    return 0;
}

欧拉回路有一些经典的应用

对于一个无向图,将其中的每一条边定向,要求每个结点的入度和出度的差不超过 1。

首先找到图中所有的奇点,将他们连向一个虚点 s。由于奇点的个数一定是偶数个,因此连完后整个图是欧拉图,跑一遍欧拉回路可以定向。然后再删掉 s 以及连接 s 的边,点的度最多变化 1。

平面上 n 个整点,要求将他们染成红色或者蓝色,且每行每列红蓝点个数差不超过 1。

当作之间连一条无向边,则染红色蓝色相当与给无向边定向,转化为上一题的模型。

生成长度为的首位相接的串使得所有长度为的 01 串都出现过。

这道题其实有两种转化模型的方式。对于一个串,你可以在后面加一个 0/1 然后删除首个字符得到下一个串,因此一个串连向两个串。问题转化为寻找哈密尔顿回路问题,貌似不太可做。

另一种转化方式是,把一个形如abcd的串拆成 (abc,bcd) 的边。这样建出来的图是可能有自环的,然后我们在这个有向图上跑欧拉回路就行了。

给一个无向图(不一定连通)加边使之成为一个欧拉图。

首先处理每一个连通块。对于有奇点的连通块们显然可以连一个大环搞掉两个奇点,剩下的奇点随便匹配就行。

然后就考虑剩下若干个没有奇点的连通块,那么我们也连一个大环就行了。

p1

在遇到一些和欧拉回路有关的问题的时候,有时是不需要建图的,直接搞度数 ;混合图求欧拉回路需要用网络流;欧拉回路只和每个点的奇偶性有关;出一道欧拉回路的好题非常难。

DFS 及其应用

手写栈模拟 DFS:相当于把状态丢到结构体里,手动开栈,跑一个 while 循环。搜索相当于圧栈。状态不仅仅包括函数参数,还有递归结构内的一些变量的值,比如循环变量 i 的值。同时还有递归、回溯的状态之分(总之先口糊一波,以后再补)

有一些图论构造题,可以在一棵 DFS 生成树上构造而忽略非树边。这常用在证明中,也有显示的构造。

一个无向图的 DFS 生成树,每一条非树边对应一个简单环。这个可以应用在仙人掌判定上。即把每个环的结点做标记,最后判断每条树边是否只覆盖一次。

连通分量的应用

强连通分量容易让人想到缩点 DP;边双连通分量缩点后构成一棵树,称作边双树;对于点双连通分量,一个点可能在多个点双中出现。

卡时

if(clock()>0.95*CLOCKS_PER_SEC)break;

计数题:TopCoder 500-700 1000 分的题

Latex 手动安装宏包:https://www.ctan.org/ 下载后把解压的文件夹丢/usr/share/texmf/tex/latex里,然后sudo texhash一下。如果是ins文件还得手动编译一下。

放缩思路的启发

很多题的正解需要将条件做一定的放缩,诸如“最优解一定会被这样考虑到”之类的思考。这样可以将条件转化变得更简单。

Linux 自定义命令

把可执行文件放到/usr/bin下即可

Linux 权限设置

chmod,一般是 755
chown,可以设置所有者

V2ray

bash <(curl -s -L https://git.io/v2ray.sh)

生成 UUID

cat /proc/sys/kernel/random/uuid

CF 读题(解)小助手

中 英 双 语

document.querySelectorAll('p').forEach(function(item){
    item.innerHTML=item.innerHTML
        .replace(/You are given/g,"给你")
        .replace(/at least/g,"至少")
        .replace(/overlap/g,"重叠")
        .replace(/can not/g,"不能")
        .replace(/cannot/g,"不能")
        .replace(/can't/g,"不能")
        .replace(/twice/g,"两次")
        .replace(/tournament/g,"锦标赛")
        .replace(/simplify/g,"简化")
        .replace(/consists of/g,"包含")
        .replace(/contains/g,"包含")
        .replace(/bidirectional/g,"双向")
        .replace(/easily/g,"容易地")
        .replace(/convex/g,"凸的")
        .replace(/functions/g,"函数")
        .replace(/function/g,"函数")
        .replace(/path/g,"路径")
        .replace(/tricky/g,"棘手的")
        .replace(/definition/g,"定义")
        .replace(/coincides with/g,"等价于")
        .replace(/centroid decmoposition/g,"点分治")
        .replace(/decreases/g,"递减")
        .replace(/increases/g,"递增")
        .replace(/increasing/g,"递增")
        .replace(/vertex/g,"结点")
        .replace(/vertices/g,"结点")
        .replace(/exists/g,"存在")
        .replace(/contradict/g,"否认")
        .replace(/gradient/g,"斜坡")
        .replace(/efficiently/g,"快速地")
        .replace(/algorithms/g,"算法")
        .replace(/algorithm/g,"算法")
        .replace(/given/g,"给定")
        .replace(/dichotomy/g,"二分法")
        .replace(/no larger than/g,"不大于")
        .replace(/optimum/g,"最优解")
        .replace(/already/g,"已经")
        .replace(/as we can see/g,"我们可以发现")
        .replace(/As we can see/g,"我们可以发现")
        .replace(/ we /g," 我们 ")
        .replace(/We /g,"我们 ")
        .replace(/subtrees/g,"子树")
        .replace(/subtree/g,"子树")
        .replace(/calculation/g,"计算")
        .replace(/global/g,"全局")
        .replace(/easy/g,"容易")
        .replace(/derivative/g,"导数")
        .replace(/degree/g,"度")
        .replace(/formula/g,"公式")
        .replace(/Indeed,/g,"具体地说,")
        .replace(/calculate/g,"计算")
        .replace(/Fix/g,"固定")
        .replace(/fix /g,"固定 ")
        .replace(/ a single /g," 一个 ")
        .replace(/ a /g," 一个 ")
        .replace(/A /g,"一个 ")
        .replace(/name/g,"名字")
        .replace(/substrings/g,"子串")
        .replace(/substring/g,"子串")
        .replace(/strings/g,"字符串")
        .replace(/string/g,"字符串")
        .replace(/Sometimes/g,"有时")
        .replace(/sometimes/g,"有时")
        .replace(/For example/g,"举个例子")
        .replace(/length/g,"长度")
        .replace(/sequence/g,"序列")
        .replace(/integer/g,"整数")
        .replace(/input/g,"读入")
        .replace(/Input/g,"读入")
        .replace(/lowercase/g,"小写")
        .replace(/the longest/g,"最长的")
        .replace(/longest/g,"最长的")
        .replace(/such that/g,"满足")
        .replace(/Print/g,"输出")
        .replace(/print/g,"输出")
        .replace(/except /g,"除了 ")
        .replace(/set up/g,"设立")
});

C++ 多维数组指针声名

int _f[MM][C][C],_g[MM][C][C];
int (*f)[C][C]=_f,(*g)[C][C]=_g;

m3u8

npm ci --registry https://registry.npmjs.org/ --https-proxy 127.0.0.1:1080

creat_ap

创建热点

create_ap wlo1 eno1 sshwy-manjaro 00000000

遇到ERROR: Failed to initialize lock

sudo rm /tmp/create_ap.all.lock