更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19555785

大意

求 $[l, r]$ 内有多少数，满足 $本身 \mod 数位和 = 0$ ，则记一次贡献。

思路

不难发现最大为 $10 ^ 9$，发挥人类智慧！

分块打表，以 $10 ^ 6$ 为块的大小，分出 $1000$ 个块。

于是你只需要计算 $f(x) = [1, x]$ 内合法的，答案为：

$$f(r) - f(l - 1)$$

完结。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19555727

大意

求一段区间 $[l, r]$ 里面的 $(i, j)$ 二元组，满足 $s[i] \oplus s[i + 1] \cdots \oplus s[j] = k$。

思路

首先，我们不难想到这个异或的性质可以扩展，然后，我们可以考虑用莫队求解此题。

对于询问分块，那我们只需要考虑加入一个点与删除一个点对 $ans$ 的贡献。

由于异或具有前缀和的性质，即为异或和，那么我们的 $s[i] \oplus s[i + 1] \cdots \oplus s[j] = s[j] \oplus s[i - 1] = k$，也就是说，我们的点 $s[j] = s[i - 1] \oplus k$，于是我们对于点 $i$ 来说，加入这个点就会对 $s[i - 1] \oplus k$ 的位置的值产生贡献，使得 $s[i - 1] \oplus s[j] = k$,那么这个题就和 P1494 [国家集训队] 小 Z 的袜子(https://www.cnblogs.com/To-Carpe-Diem/p/19434503) 一样了。

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
const int MAXV = (1 << 20) + 5;
int n, m, k, b;
long long sum = 0;
int s[MAXN], a[MAXN];
int cnt[MAXV];
long long ans[MAXN];

struct node{
	int l, r, id;
}q[MAXN];

bool cmp(node x, node y){
	if(x.l / b != y.l / b){
		return x.l < y.l;
	}
	return (x.l / b) % 2 == 1 ? x.r < y.r : x.r > y.r;
}

void add(int x){
	sum += cnt[x ^ k];
	cnt[x] ++;
}

void del(int x){
	cnt[x] --;
	sum -= cnt[x ^ k];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;

	b = sqrt(n);

	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		s[i] = s[i - 1] ^ a[i];
	}

	for(int i = 1;i <= m;i ++){
		int l, r; cin >> l >> r;
		q[i] = {l, r, i};
	}

	sort(q + 1, q + m + 1, cmp);

	int l = 1, r = 0;

	cnt[0] = 1;

	for(int i = 1;i <= m;i ++){
		while(l > q[i].l) add(s[-- l - 1]);
		while(l < q[i].l) del(s[l ++ - 1]);
		while(r < q[i].r) add(s[++ r]);
		while(r > q[i].r) del(s[r --]);
		ans[q[i].id] = sum;
	}

	for(int i = 1;i <= m;i ++){
		cout << ans[i] << '\n';
	}

	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19527165

大意

求最小值的石子合并，$n \le 40000$。

思路

利用 GarsiaWachs 算法。

在序列中找到第一个满足 $a_{i-1} \le a_{i+1}$ 的三元组 $(a_{i-1}, a_i, a_{i+1})$。

合并 $a_{i-1}$ 和 $a_i$，得分增加 $W = a_{i-1} + a_i$。

从当前位置向左寻找第一个大于 $W$ 的位置，将 $W$ 插入到其后面。

重复上述过程，直到只剩下一堆石子。

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define int long long
int n;
int ans = 0;
vector<int> a;

void merge(int k){
	int tmp = a[k - 1] + a[k];
	ans += tmp;
	a.erase(a.begin() + k - 1);
	a.erase(a.begin() + k - 1);
	int pos = -1;
	for(int i = k - 2;i >= 0;i --){
		if(a[i] >= tmp){
			pos = i;
			break;
		}
	}
	a.insert(a.begin() + pos + 1, tmp);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i ++){
		int val; cin >> val;
		a.push_back(val);
	}
	while(a.size() > 1){
		int k = a.size() - 1;
		for(int i = 1;i < (int)a.size() - 1;i ++){
			if(a[i - 1] <= a[i + 1]){
				k = i;
				break;
			}
		}
		merge(k);
	}
	cout << ans << '\n';
	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19527051

大意

石子合并，$n = 1000$，求最小值。

思路

首先 $\mathcal{O}(n ^ 3)$ 的复杂度肯定是不可以的。

我们考虑优化，不难发现，对于 $w(i, j)$ 满足：

$$w(i, j - 1) + w(i + 1, j) \le w(i, j) + w(i - 1,j - 1)$$

所以这个 $w$ 满足四边形不等式，故 $f$ 也满足。

然后我们定义这个 $G(k) = f(i, k) + f(k + 1, j)$，所以 $G(k)$ 为凹函数，则最小值在一个区间内取得，我们可以记录 $[i, j]$ 区间的决策点，这样你在算第 $[i, j]$ 的时候，区间 DP 的点 $k$ 就可以在 $s[i][j - 1]$ 和 $s[i + 1][j]$ 之间取得。

代码

#include<iostream>
using namespace std;

#define int long long
const int MAXN = 2005;
int n;
int a[MAXN];
int dp[MAXN][MAXN];
int sum[MAXN];
int s[MAXN][MAXN];

signed main(){

	cin >> n;

	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		a[i + n] = a[i];
		sum[i] = sum[i - 1] + a[i];
	}

	for(int i = n + 1;i <= (n << 1);i ++){
		sum[i] = sum[i - 1] + a[i];
	}

	for(int i = 1;i <= (n << 1);i ++){
		s[i][i] = i;
	}

	for(int len = 2;len <= n;len ++){
		for(int i = 1;i + len - 1 <= (n << 1);i ++){
			int j = i + len - 1;
			dp[i][j] = 1e9;
			int L = s[i][j - 1];
			int R = s[i + 1][j];
			for(int k = L;k <= R;k ++){
				int cnt = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
				if(cnt < dp[i][j]){
					dp[i][j] = cnt;
					s[i][j] = k;
				}
			}
		}
	}

	int ans = 1e9;

	for(int i = 1;i <= n;i ++){
		ans = min(ans, dp[i][i + n - 1]);
	}

	cout << ans << '\n';
	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19526744

大意

$n = 2000$ 的石子合并。

思路

首先，区间 DP 是 $\mathcal{O}(n ^ 3)$ 的，对于这个题显然是不合适的。

我们考虑优化。

令 $G(k) = f(i, k) + f(k + 1, j)$。

我们接下来证明这个 $G(k)$ 为凸函数，则 $G(k) \le \displaystyle\frac{G(k - 1) + G(k + 1)}{2}$

令 $\Delta G(k) = G(k + 1) - G(k)$

$\Delta G(k) = [f(i, k + 1) - f(i, k)] - [f(k + 1, j) - f(k + 2, j)]$

左边的 $f(i, k + 1) - f(i, k)$ 随着 $k$ 的增大递增。

右边的 $f(k + 1, k) - f(k + 2, j)$ 随着 $k$ 的增大递减。

递增 - 递减 = 递增。

故 $G(k)$ 单调递增，则 $G(k)$ 为凸函数，最大值在端点处取得。

所以最终的转移式为：

$$f(i, j) = \max(f(i+1, j), f(i, j-1)) + w(i, j)$$

代码

#include<iostream>
using namespace std;

#define int long long
const int MAXN = 4 * 1e3 + 5;
int n;
int a[MAXN];
int dp[MAXN][MAXN];
int sum[MAXN];

signed main(){
	
	cin >> n;
	
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		a[i + n] = a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	
	for(int i = n + 1;i <= (n << 1);i ++){
		sum[i] = sum[i - 1] + a[i];
	}
	
	for(int len = 2;len <= n;len ++){
		for(int i = 1;i + len - 1 <= (n << 1);i ++){
			int j = i + len - 1;
			dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) + (sum[j] - sum[i - 1]);
		}
	}
	
	int ans = -1;
	
	for(int i = 1;i <= n;i ++){
		ans = max(ans, dp[i][i + n - 1]);
	}
	
	cout << ans << '\n';
	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19526480

大意

最小的步数达到要求的地方。

思路

这个题目的目标状态也很简约，就是形如题目中的样子，这个我们转换思路就是拿着这个空格去和旁边的格子不断的交换，但是这样产生的状态是很多的，为了剪枝，我们采用 IDA*，这个题目的估价函数有个很显然的写法，就是记录错误位置的个数，因此，一定小于等于...吗？我们考虑这样的情况，如果现在只需要一步，将空格和一个棋子交换，这样的实际步数是 $1$，但是你的估价函数给的是 $2$，显然不行，特判一下即可。然后我们就正常的去迭代加深的搜索就好。

代码

#include<iostream>
using namespace std;

int T, ans = 1e9;
int a[6][6];
int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};


int f(int b[6][6]){
	int res = 0;
	for(int j = 1;j <= 5;j ++){
		if(b[1][j] != 1) res ++;
	}
	for(int j = 1;j <= 5;j ++){
		if(b[5][j] != 0) res ++;
	}
	if(b[2][1] != 0) res ++;
	for(int j = 2;j <= 5;j ++){
		if(b[2][j] != 1) res ++;
	}
	if(b[4][5] != 1) res ++;
	for(int j = 1;j <= 4;j ++){
		if(b[4][j] != 0) res ++;
	}
	for(int j = 1;j <= 2;j ++){
		if(b[3][j] != 0) res ++;
	}
	if(b[3][3] != 2) res ++;
	for(int j = 4;j <= 5;j ++){
		if(b[3][j] != 1) res ++;
	}
	if(res == 2) return 1;
	return res;
}

void dfs(int dp, int now, int cnt[6][6]){
	if(now >= ans) return;
	if(f(cnt) == 0){
		ans = now;
		return;
	}
	if(now + f(cnt) > dp) return;
	if(now > dp){
		return;
	}
	int sx = 0, sy = 0;
	for(int i = 1;i <= 5;i ++){
		if(sx) break;
		for(int j = 1;j <= 5;j ++){
			if(cnt[i][j] == 2){
				sx = i, sy = j;
				break;
			}
		}
	}
	for(int i = 0;i < 8;i ++){
		int nx = sx + dx[i];
		int ny = sy + dy[i];
		if(nx < 1 || ny < 1 || nx > 5 || ny > 5) continue;
		int sum[6][6];
		for(int p = 1;p <= 5;p ++){
			for(int q = 1;q <= 5;q ++){
				sum[p][q] = cnt[p][q];
			}
		}
		swap(sum[sx][sy], sum[nx][ny]);
		dfs(dp, now + 1, sum);
	}
}

int main(){

	cin >> T;

	while(T --){
		for(int i = 1;i <= 5;i ++){
			string s; cin >> s;
			for(int j = 0;j < 5;j ++){
				if(s[j] == '*') a[i][j + 1] = 2;
				else a[i][j + 1] = s[j] - '0';
			}
		}
		ans = 1e9;
		for(int dp = 1;dp <= 15;dp ++){
			dfs(dp, 0, a);
			if(ans <= 15) break;
		}
		if(ans <= 15){
			cout << ans << '\n';
		}
		else{
			cout << -1 << '\n';
		}
	}

	return 0;
}