widsnoy's blog

编辑距离问题

发表于 2020-09-27 更新于 2023-12-07 分类于题解

编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。例如将kitten一字转成sitting： sitten （k->s） sittin （e->i） sitting （->g）所以kitten和sitting的编辑距离是3。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。给出两个字符串a,b，求a和b的编辑距离。

设$f[i][j]$表示A串前$i$位到$B$串前$j$位的编辑距离。
$A[i]=B[j]$，$f[i][j]=f[i-1][j-1]$
$A[i]\neq B[j]$，$min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1$
分别对应删除$A$最后一个字符，$A$末尾加一个字符，修改$A$最后一个字符。

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

const int N = 1005;
char a[N], b[N];
int f[N][N];

int main() {
    scanf("%s %s", a + 1, b + 1);
	int n = strlen(a + 1), m = strlen(b + 1);
	for (int i = 1; i <= max(n, m); i++) f[i][0] = f[0][i] = i;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
            if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1];
			else f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
		}
	printf("%d\n", f[n][m]);
	return 0;
}

「SCOI2005」栅栏

发表于 2020-09-27 更新于 2023-12-07 分类于题解

这道题的正解竟然就是 dfs +剪枝...
可以把题目理解成用木板去塞木材，最多塞多少个。

先将不可能塞的不板和不可能被塞的木材排除。

二分答案最多能塞多少个木板，搜索每个木材塞到哪个板，显然用更小的木板来塞一定不会更差。

记录前 mid 个木板的和，总的木材的和。
搜索的时候随时减去不能再被塞的木材。

如果某个时候$sum[mid]+w\ge S$则 return
如果木板大小相同，就直接从上一次塞的位置继续，因为我们应该让这些木板只能按某种顺序塞来减少状态数。

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

const int N = 1005;
int n, m, mid, S, a[N], b[N], sum[N], lst[N];
bool flg;

void dfs(int x, int p, int w) {
	if (x == 0) return (void)(flg = 1);
	while (a[p] < b[1] && p <= n) w += a[p], p++;
	if (p > n || w + sum[mid] > S || flg) return;
	int t = p;
	if (x != mid && b[x] == b[x + 1]) t = lst[x + 1];
	for (int i = t; i <= n; i++) if (a[i] >= b[x]) {
		lst[x] = i;
		a[i] -= b[x];
		dfs(x - 1, p, w);
		a[i] += b[x];
		if (flg) return;
	}
}

int main() {
    scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
	sort(a + 1, a + n + 1);
	sort(b + 1, b + m + 1);
	while (b[m] > a[n]) m--;
	int tot = 0;
	for (int i = 1; i <= n; i++) if (a[i] >= b[1]) a[++tot] = a[i];
    n = tot;
    for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] + b[i];
	for (int i = 1; i <= n; i++) S += a[i];
	int l = 1, r = m, ans = 0;
	while (l <= r) {
		mid = (l + r) >> 1;
		flg = 0;
		dfs(mid, 1, 0);
		if (flg) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	printf("%d\n", ans);
	return 0;
}

```

凸多边形的划分

发表于 2020-09-27 更新于 2023-12-07 分类于题解

#include<cstdio>
using namespace std;

#define int --int128
const int N = 55;
int n, f[N * 2][N * 2], a[N * 2];

int read() {
    int w = 0, f = 1; char ch = getchar();
    while(ch > '9' || ch < '0') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        w = w * 10 + ch - 48;
        ch = getchar();
    }
    return w * f;
}
void write(int x) {
    if(x < 0) {
        x = -x;
        putchar('-');
    }
    if(x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
int min(int a, int b) {
	return a < b ? a : b;
}

signed main() {
    n = read();
    for(int i = 1; i <= n; i++) a[i] = read(), a[i + n] = a[i];
    for(int i = 1; i <= 2 * n; i++)
    	for(int j = 1; j <= 2 * n; j++) f[i][j] = 1e38;
    int ans = 1e35;
    for(int len = 2; len <= n; len++)
    	for(int i = 1; i + len - 1 <= 2 * n; i++) {
    		int j = i + len - 1;
    		if(len == 2) f[i][j] = 0;
    		else {
    			for(int k = i + 1; k < j; k++) f[i][j] = min(f[i][j], f[i][k] + f[k][j] + a[i] * a[j] * a[k]);
    		}
    	    if(len == n) ans = min(ans, f[i][j]); 
    	}
    write(ans);
    return 0;
}

LOJ 10082 Word Rings

发表于 2020-09-26 更新于 2023-12-07 分类于题解

这道题很妙啊...

首先这个建边方式，很自然就能想到按题意串与串连边。
但是这样的复杂度是不能接受的。

我们只需要将每个串前两个字符对应的节点和后两个对应的节点连边就可以了，不难发现这样也是等价的。

现在边建好了，很自然就能想到用 spfa 跑最长路。
这样的时间复杂度也是不能接受的...

我们并不能直接知道答案是多少，于是二分答案上去验证
如果一个环$\frac{a-1+a-2+a-3+...+a-n}{n}\geq mid$
$(a-1-mid)+(a-2-mid)+...+(a-n-mid)\geq 0$

于是我们可以枚举答案，给每条边一个新的边权，用 dfs 版的 spfa 跑最长路判断有没有正环。

枚举一定数量的起点来验证，大概率能跑对...
注意这里不需要每次都 memset 最短路的 dis 数组，因为如果正环上某个点$x$被前驱是$y$，$dis[x]$被重赋值后，看似$dis'[x]\geq dis[y]+w$不能被更新，但是$dis[x]$被重赋值说明已经可以作为新的起点，不需要从$y$迭代过来。

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

const int N = 50500;
const double eps = 1e-9;
int n, cnt, head[N];
double dis[N];
bool vis[N];
char s[1005];
struct E {int nxt, v; double w;} e[N << 2];
void add(int u, int v, double w) {e[++cnt] = {head[u], v, w}; head[u] = cnt;}

bool dfs(int x, const double mid) {
    vis[x] = 1;
	for (int i = head[x]; i; i = e[i].nxt) {
		int v = e[i].v;
		double w = e[i].w - mid;
		if (dis[v] < dis[x] + w) {
			dis[v] = dis[x] + w;
		    if (vis[v]) return 1;
			if (dfs(v, mid)) return 1;
		}
	}
	vis[x] = 0;
	return 0;
}
bool check(double mid) {
	memset(vis, 0, sizeof vis);
	memset(dis, 0, sizeof dis);
	for (int i = 0; i <= 5000; i++) {
        if (dfs(i, mid)) return 1;
	}
	return 0;
}

int main() {
    while (scanf("%d", &n) != EOF && n) {
		memset(head, 0, sizeof head);
		cnt = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%s", s + 1);
			int len = strlen(s + 1);
		    if (len < 2) continue;
            int pre = (s[1] - 'a') * 26, suf = (s[len - 1] - 'a') * 26;
			pre = pre + s[2] - 'a', suf = suf + s[len] - 'a';
			double bl = 1.0 * len;
			add(pre, suf, bl);
		}
		double l = 0.0, r = 1005.0;
		while (r - l > eps) {
			double mid = (r + l) / 2.0;
			if (check(mid)) l = mid;
			else r = mid;
		}
		if (l == 0.0) puts("No solution");
		else printf("%.2lf\n", l);
	}
	return 0;
}

LOJ 10010 糖果传递

发表于 2020-09-26 更新于 2023-12-07 分类于题解

设$x-i$表示第$i$个人向第$i-1$传递的糖果数，$i\in [1,n],x-i\in \mathjaxbb{z}$
特别的$x-1$表示$1$向$n$传递的糖果数。

设平均数为$q$
$a-i-x-i+x_{i+1}=q$ 则有$x-i-x_{i+1}=a-i-q$

$x-1-x-2=a-1-q$
$x-2-x-3=a-2-q$
$......$
$x_{n-1}-x_{n}=a_{n-1}-q$

实际上还有$x-n-x-1=a-n-q$，但是这个方程并没有什么意义。
我们把每个方程相加，可以得到： $x-1=x-n+\sum_{i=1}^{n-1}a-i-q$
$x-2=x-n+\sum_{i=2}^{n-1}a-i-q$
$......$ $x_{n-1}=x_{n}+a_{n-1}-q$

把$\sum a-i-q$看作常数
题目求 $\lvert x-n+t-1\rvert+\lvert x-n+t-2\rvert+...+\lvert x-n+t_{n-1}\rvert+\lvert x-n\rvert$
为了形式统一，可以把$\lvert x-n\rvert$变成$\lvert x-n\rvert-t-n,t-n=0$

这是一个经典的结论，当$x-n$取$t$中位数时最小。
具体证明是$\lvert x+t\rvert$看作坐标轴上两点距离。
因为有$\lvert x-a\rvert+\lvert x-b\rvert\geq \lvert a-b\rvert$调整$x$取值，发现在中位数的时候最优。

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

typedef long long ll;
const int N = 1e6 + 5;
ll n, sum[N], t[N], b[N], ans;

int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &sum[i]), sum[i] += sum[i - 1];
    ll qaq = sum[n] / n;
	for (int i = 1; i < n; i++) {
        t[i] = sum[n - 1] - sum[i - 1] - (n - i) * qaq;
		t[i] = -t[i];
		b[i] = t[i];
	}
	t[n] = 0;
	b[n] = 0;
	sort(t + 1, t + n + 1);
	ll xn = t[n / 2];
	for (int i = 1; i <= n; i++) ans = ans + abs(xn - b[i]);
	printf("%lld\n", ans);
	return 0;
}

LOJ10235 序列统计

发表于 2020-09-26 更新于 2023-12-07 分类于题解

题目要求单调不降很不好做。
我们把每个数都加上它的下标，就变成了单调上升序列，值域是$[l+1,r+n]$

在$[l+1,r+n]$里面选$n$个数和单调上升序列的方案数是一一对应的。
答案是$\sum_{i=1}^n\binom{r-l+i}{i}=\binom{r-l+n+1}{n}-1$

因为模数是小质数，用$lucas$定理做就可以了。

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

const int N = 1e6 + 5;
const int p = 1e6 + 3;
int n, l, r, a[p + 5];

int fpow(int a, int b) {
	int res = 1;
	for (; b; b >>= 1, a = a * 1ll * a % p) if (b & 1) res = res * 1ll * a % p;
	return res;
}
int C(int n, int m) {
	if (m > n) return 0;
	return a[n] * 1ll * fpow(a[n - m], p - 2) % p * 1ll * fpow(a[m], p - 2) % p;
}
int solve(int n, int m) {
	if (m == 0) return 1;
    return solve(n / p, m / p) * 1ll * C(n % p, m % p) % p;
}

int main() {
    int -;
	a[0] = 1;
	for (int i = 1; i <= p; i++) a[i] = a[i - 1] * 1ll * i % p;
	for (scanf("%d", &-); -; ---) {
        scanf("%d %d %d", &n, &l, &r);
		printf("%lld\n", (solve(r - l + 1 + n, n) * 1ll - 1ll + p) % p);
	}
	return 0;
}

```

LOJ10059 Censoring

发表于 2020-09-26 更新于 2023-12-07 分类于题解

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

const int N = 1e6 + 5;
int n, tr[N][26], fail[N], id[N], tot, stk[N], top, o[N];
char s[N], qaq[N];

void insert(const char *s) {
	int u = 0, n = strlen(s + 1);
	for (int i = 1; i <= n; i++) {
		int c = s[i] - 'a';
		if (!tr[u][c]) tr[u][c] = ++tot;
		u = tr[u][c];
	}
	id[u] = n;
}
void build() {
	queue<int> q;
	for (int i = 0; i < 26; i++) if (tr[0][i]) q.push(tr[0][i]);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = 0; i < 26; i++) {
			if (tr[u][i]) fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
			else tr[u][i] = tr[fail[u]][i];
		}
	}
}

int main() {
	scanf("%s", qaq + 1);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%s", s + 1), insert(s);
	build();
	int m = strlen(qaq + 1), u = 0;
	for (int i = 1; i <= m; i++) {
		int c = qaq[i] - 'a';
		u = tr[u][c];
		stk[++top] = u;
		o[top] = i;
		if (id[u]) {
			top -= id[u];
			u = stk[top];
		}
	}
	for (int i = 1; i <= top; i++) printf("%c", qaq[o[i]]);
	return 0;
}

拉格朗日插值

发表于 2020-09-23 更新于 2023-12-07 分类于模板

假设$x-i$互不相同，$F(k)=\sum\limits_{i=0}^{deg} y-i \ell-i(k)$

其中$\ell-i$是拉格朗日基本多项式，$\ell-i(k)=\prod\limits_{j=0,i\neq j}^{deg}\frac{k-x-j}{x-i-x-j}$

这个$\ell$有什么特点呢？
对于$\forall j\neq i$，$\ell-i(x-j)=0，而$-i(x-i)=1$。
代值进去即可验证。

所以$\forall x-i,F(x-i)=\sum\limits_{i=0}^{deg} y-i \ell-i(x-i)=y-i$，一共有$deg+1$个点，所以能确定一个多项式。
时间复杂度$\mathjaxcal{O}(n^2)$

重心拉格朗日插值

每一次都算$\ell$好像很慢。
令$\ell(x)=(x-x-1)(x-x-2)...(x-x-n)$
$w-i=\frac{1}{\prod\limits_{j=0,i\neq j}^{deg}(x-i-x-j)}$

则$\ell-i(x)=\frac{\ell(x)}{x-x-i}w-i$
$F(x)=\sum\limits_{i=0}^{deg}y-i\ell-i(x)$
$F(x)=\ell(x)\sum\limits_{i=0}^{deg}y-i\frac{w-i}{x-x-i}$

$w-i$称为$i$的重心，每次加入新点时可以$\mathjaxcal{O}(n)$算新重心，计算$F$也是$\mathjaxcal{O}(n)$的。

~~当然初始化重心是$\mathjaxcal{O}(n^2)$~~

阅读全文 »

LOJ 3265 Delegation

发表于 2020-09-23 更新于 2023-12-07 分类于题解

这题看起来挺像赛道修建。
但是是要求把所有路选完，所以贪心方法不太一样。

首先，二分以后并不是能选就选，这个看样例就知道。

$\text{mid}=2$时，如果能选就选最后是不合法的，因为有边最后不能放到长度不小于$2$的链里面。

考虑最后合并一个点的所有链，如果有多于一条链最后不能合并，那就是不合法的。
所有链都满足要求的前提下，可以选取一条尽量长的链给父节点，这样一定是不劣的，因为可以顺便把这条链合并了，也有可能这条链刚好时父节点合并完。

最后特别判断一下父节点。

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

const int N = 1e5 + 4;
int n, mid, head[N], cnt;
struct E {
	int nxt, v;
} e[N << 1];

void add(int u, int v) {
	e[++cnt] = {head[u], v}; head[u] = cnt;
	e[++cnt] = {head[v], u}; head[v] = cnt;
}

int dfs(int u, int fa) {
	multiset<int> s;
    for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (v == fa) continue;
		int d = dfs(v, u);
		if (d == -1) return -1;
		s.insert(d + 1);
	}
	int t = 0, pt = 0;
	while (!s.empty()) {
		auto it = s.begin();
		int x = *it;
		s.erase(it);
		auto itl = s.lower-bound(mid - x);
		if (itl == s.end()) {
			if (!t) t = x;
			else return -1;
		} else {
			if (*itl >= mid) pt = x;
			s.erase(itl);
		}
	}
	if (u != 1) return t ? t : pt;
	return t;
}

int main() {
    scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		add(u, v);
	}
	int l = 1, r = n - 1, ans = 0;
    while (l <= r) {
		mid = (l + r) >> 1;
		int x = dfs(1, 0);
		if (x == 0 || x >= mid) l = mid + 1, ans = mid;
		else r = mid - 1;
	}
	printf("%d\n", ans);
	return 0;
}

阅读全文 »

LOJ 2721「NOI2018」屠龙勇士

发表于 2020-09-21 更新于 2023-12-07 分类于题解

因为是按照$1-n$的顺序杀龙，所以每次用的剑是固定的，可以先预处理出来。
每次需要满足
1 .$atk*x\geq a-i$
2. $atk*x\equiv a-i\pmod {p-i}$

观察数据，可以发现要不$p-i$满足$a-i\leq p-i$，要不$p-i=1$

对于第二种只需要刚好打到不大于$0$就可以了。

第一种情况，第一个限制显然是可以忽略的，因为满足第二个限制一定就满足第一种限制。

我们只需要考虑解出$x$，把每个方程都化为$x\equiv r-i\pmod {m-i}$这种一般形式。

直接的想法就是变成$x\equiv a-i*inv(atk)\pmod{p-i}$
但是模$p-i$意义下，$atk$的逆元不一定存在。
同余方程同时约去$\gcd(a-i,p-i,atk)$
如果$\gcd(atk,p-i)$仍不等于 $1$，则无解。

因为约去$\gcd(a-i,p-i,atk)$ 后仍不互质，说明$\gcd(atk,p-i)\nmid a-i$，不满足翡蜀定理，则无解。

化完之后来解同余方程组就可以了。

细节没处理好，代码毒瘤。

阅读全文 »