分两个阶段: $n_2>n_1$ 差大于i

$n_2<n_1$ 差小于i

会发现第二阶段每个数减得是一个等差数列

然后用二分模拟即可


//可以简单划分两个阶段
//第一个是n2>n1差大于x的时候
//第二个是n1>n2但差小于x的时候
//二分加速两个阶段
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int T;
ll n1, n2, nx;

inline ll chk(ll x) {
	return x * (x + 1) / 2;
}

//暴力删大的
inline void solve1(ll &A, ll &B, int tp) {
	ll del = A - B;
	ll L = 0, R = 1e9, mid = 0, ans = 0;
	while(L <= R) {
		mid = (L + R) >> 1;
		if(del <= chk(mid)) {
			R = mid - 1;
			ans = mid;
		} else {
			L = mid + 1;
		}
	}
	A -= chk(ans);
	nx = ans;//说明我们用了这么多轮了!
	if(A < 0) {
		if(tp == 1)printf("%lld %lld %lld\n", nx, A + ans, B);
		else printf("%lld %lld %lld\n", nx, B, A + ans);
		A = -1;
		B = -1;
	}
	// printf("%lld %lld %lld\n", A, B, nx);
	return ;
}

inline ll chk2(ll x) {
	return x * nx + x * (x + 1);
}

inline ll chk1(ll x) {
	return x * nx + x * x;
}

inline void solve2(ll A, ll B, int tp) {
	// printf("%lld %lld\n", A, B);
	ll L, R, mid, ans1 = 0, ans2 = 0;
	L = 0;
	R = 1e9;
	while(L <= R) {
		mid = (L + R) >> 1;
		if(A >= chk2(mid)) {
			// printf("%lld %lld %lld\n", A, chk2(mid), mid);
			L = mid + 1;
			ans1 = mid;
		} else {
			R = mid - 1;
		}
	}
	L = 0;
	R = 1e9;
	while(L <= R) {
		mid = (L + R) >> 1;
		// printf("%lld %lld %lld %lld\n", L, R, chk1(mid), B);
		if(B >= chk1(mid)) {
			L = mid + 1;
			ans2 = mid;
		} else R = mid - 1;
	}
	// printf("%lld %lld %lld %lld\n", ans1, ans2, chk1(ans1 + 1), B);
	ll ans = 0;
	ans1++;
	ans2++;
	//多一轮就死
	ans = min(ans1 * 2, ans2 * 2 - 1);
	ans1--;
	ans2--;
	if(ans1 < ans2) {//第一个
		// puts("qwq");
		A -= chk2(ans1);
		// printf("%lld %lld %lld\n", B, chk1(ans1 + 1), ans1);
		if(B - chk1(ans1 + 1) >= 0)B = B - chk1(ans1 + 1);//多杀一轮
		else B -= chk1(ans1);
		if(tp == 1)printf("%lld %lld %lld\n", nx + ans, A, B);
		else printf("%lld %lld %lld\n", nx + ans, B, A);
	} else {
		if(A - chk2(ans2 + 1) >= 0)A = A - chk2(ans2 + 1);
		else A -= chk2(ans2);
		B -= chk1(ans2);
		if(tp == 1)printf("%lld %lld %lld\n", nx + ans, A, B);
		else printf("%lld %lld %lld\n", nx + ans, B, A);
	}
	return ;
}

int main() {
	// freopen("test.out", "w", stdout);
	scanf("%d", &T);
	for(int i = 1; i <= T; ++i) {
		scanf("%lld%lld", &n1, &n2);
		if(n1 >= n2) {
			solve1(n1, n2, 1); //第一阶段
			// printf("%lld %llld??\n", n1, n2);
			if(n2 > 0) {
				if(n1 < n2)solve2(n1, n2, 1); //第二阶段
				else {
					if(n1 < nx) {
						printf("%lld\n", nx);
						continue;
					}
					// puts("????");
					// if(nx == 0)nx = 1;//0???
					nx++;
					n1 -= nx;
					solve2(n1, n2, 1); //强行小于然后第二阶段
				}
			}
		} else {
			solve1(n2, n1, 2); //第一阶段
			if(n2 > 0)
				solve2(n2, n1, 2);
		}
	}
	return 0;
}
/*

11
1 11
1 9
2 8
3 7
4 6
4 7
4 8
3 9
5 9
6 9
6 8



*/

$N=2$

解方程

$C_1=\frac{x-a_2}{a_1-a_2}$

$f_{B,C}=b_1C_1+b_2C_2=b_1(kx-p)+b_2(1-kx+p)$

显然当x变化的时候,我们的 $C_1,C_2$ 也是变化的

而x定了,这个值就定了

也就是说是一个直线

问题可以变成二维平面,纵轴 $f_{B,C}$ ,横轴为x

那会发现当n=2时,所有可行情况都在这直线上!

N=3

当我们只用其中的两个,显然会多出一个点,就是对应了 $(a_3,b_3)$ (当然这个点其实只是形象表示)

然后两两组合就是一些直线

那我们能表示的就是三角形-----凸包....

因为相当于在三个向量之间求加权平均,就是只能在那些

任何一个点都能用加权平均表示出来/se

严格的解不等式出来其实就是一样的

然后会发现n个点也是....凸包

我们要求的是一条竖线截凸包上凸壳

显然在某条线段上,于是我们直接暴力枚举即可

然后取最大值....


#include<bits/stdc++.h>
using namespace std;
#define db double
const int MAXN = 1005;
int m, n;
int a[MAXN], b[MAXN];
db A[MAXN], B[MAXN];
db chk(int x, int y, int z) {
	if(a[y] == a[z]) {
		if(x != a[y]) return -1.0;
		return max(B[y], B[z]);
	}
	db tc = (a[y] - x) * 1.0 / (a[y] - a[z]);
	db tc2 = 1.0 - tc;
	if(tc <= -1e-10) return -1.0;
	if(tc2 <= -1e-10) return -1.0;
	return tc * B[z] + tc2 * B[y];
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for(int i = 1; i <= n; ++i) scanf("%d", &b[i]);
	for(int i = 1; i <= n; ++i) A[i] = a[i] * 1.0, B[i] = b[i] * 1.0;
	for(int i = 1, x; i <= m; ++i) {
		scanf("%d", &x);
		db ans = 0.0;
		for(int i = 1; i <= n; ++i) {
			for(int j = 1; j <= n; ++j) {
				ans = max(ans, chk(x, i, j));
			}
		}
		printf("%.6lf\n", ans);
	} return 0;
}

显然是区间DP

考虑这个代价咋搞

左边有a个数比右边最小值大,右边右b个数比左边大,合并的代价为a+b

有个第一手做法,叫做空间换时间

预处理 $f_{l,r,n}$ 表示 $[l,r]$ 值域大于等于n有多少个

然后就能转移了,但是空间很吃紧

再随手优化下看看

区间最小值拿出来,我们至少有一边不用算答案...最小值在左边右边不用算,最小值在右边左边不用算

然后呢?随着右端点右移,这个最小值只能单调变大

左边所有数维护一个堆,然后不断删除即可

然鹅这个好像有log

搞掉他很简单,因为值域很小

my:

预处理 $f_{l,r}$ 表示l在[l,r]最后一个小于他的位置

剩下乱搞搞

zhq:(牛)

$f_{l,r}$ 表示前l个数小于等于r的数个数


//怎么维护那个奇怪的限制啊?
//先处理一边的f_{s1,s2}
//那么就是s2最小值大于s1哪些值?
//处理一个suf数组??
//suf_{i,j}表示从位置i到位置j对于i小于他最靠后的数
//pre_{i,j}表示从位置j到位置i对于i小于他最靠前的数
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 607;
const ll INF = 1e9;
int n;
int a[MAXN], suf[MAXN][MAXN], pre[MAXN][MAXN];
ll dp[MAXN][MAXN];

inline void init() {
	memset(dp, -1, sizeof(dp));
	for(int i = 1; i <= n; ++i) {
		for(int j = i + 1; j <= n; ++j) {
			if(a[j] < a[i])suf[i][j] = j;
			else suf[i][j] = suf[i][j - 1];
			// printf("%d %d %d\n", i, j, suf[i][j]);
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = i - 1; j >= 1; --j) {
			if(a[j] < a[i])pre[j][i] = j;
			else pre[j][i] = pre[j + 1][i];
			// printf("%d %d %d\n", i, j, pre[j][i]);
		}
	}
	return ;
}

ll c1[MAXN], c2[MAXN];

//f_l,r=min(f_l,k+f_k+1,r+c1+c2)
inline ll solve(int L, int R) {
	if(L == R) {
		return 0;
	}
	if(~dp[L][R])return dp[L][R];
	for(int i = L; i < R; ++i) {
		solve(L, i);
		solve(i + 1, R);
		//鬼畜
	}
	// printf("solve : %d %d ?\n", L, R);
	dp[L][R] = INF;
	for(int i = L; i <= R; ++i) {
		if(suf[i][R]) {
			// printf("suf : %d %d\n", i, suf[i][R]);
			c1[suf[i][R]]--; //端点在枚举到这个之前
			c1[i]++;//分进去!
		}
	}
	for(int i = L; i <= R; ++i)c1[i] += c1[i - 1];
	for(int i = L; i <= R; ++i) {
		if(pre[L][i]) {
			// printf("pre :%d %d\n", i, pre[L][i]);
			c2[pre[L][i]]++;
			c2[i]--;
		}
	}
	for(int i = L; i <= R; ++i)c2[i] += c2[i - 1];
	for(int i = L; i < R; ++i) {
		// printf("trs :%d %d %d %d\n", solve(L, i) + solve(i + 1, R), c1[i], c2[i], i);
		dp[L][R] = min(dp[L][R], solve(L, i) + solve(i + 1, R) + c1[i] + c2[i]);
	}
	for(int i = L; i <= R; ++i)c1[i] = c2[i] = 0;
	return dp[L][R];
}

int main() {
	// freopen("test.in", "r", stdin);
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);
	init();
	printf("%lld\n", solve(1, n)); //QAQ
	return 0;
}

我:

死命状压 $2^m*nm^3$

练死劲

code:


//80
//我讨厌卡常
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 407;
const int MAXS = 8194;
const int MAXM = 15;
const int MAXNI = 4001;
const int P = 1e9 + 7;
int n, L, R, m, tot;
int a[MAXN], pc[MAXN][MAXN];
int f[2][MAXS][MAXNI];//绰绰有余
int vis[MAXN], vvis[MAXN], que[MAXN];
inline void add(int &x, int y) {
	x += y;
	if(x >= P)x -= P;
	return ;
}

inline void init() {
	int inv = 0;
	for(int i = 1; i <= n; ++i) {
		if(a[i] == 0)continue;
		for(int j = 1; j <= i; ++j) {
			if(a[j] > a[i]) {
				inv++;
			}
		}
	}
	// printf("%d\n", inv);
	L -= inv;
	R -= inv;
	L = max(0, L);
	R = min(R, (n - 1) * m);//撑死了
	// printf("%d %d\n", L, R);
	//放在第i个空位的产生的其他逆序对贡献!??
	for(int i = 1; i <= m; ++i) {
		int p = vis[i];
		for(int j = 1; j <= tot; ++j) {
			int v = que[j];
			int inv = 0;
			for(int i = 1; i < p; ++i) {
				if(a[i] == 0)continue;
				if(a[i] > v) {
					inv++;
				}
			}
			for(int i = p + 1; i <= n; ++i) {
				if(a[i] == 0)continue;
				if(a[i] < v) {
					inv++;
				}
			}
			pc[i][j] = inv;//位置i放入j得到逆序对
			// printf("%d %d P :%d V: %d Suminv: %d\n", i, j, p, v, inv);
		}
	}
	return ;
}

inline void solve() {
	int mS = (1 << m) - 1;
	f[0][0][0] = 1;
	for(int i = 1; i <= tot; ++i) {//枚举每个值,从小到大填入
		for(int S = 0; S <= mS; ++S) {//枚举位置集合
			for(int k = 0; k <= R; ++k) {//枚举逆序对数....QAQ
				if(!f[0][S][k])continue;
				int cnt = 0;
				// printf("now is in :%d S jihe : %d k ni: %d fsh: %d \n", i, S, k, f[0][S][k]);
				for(int j = m - 1; j >= 0; --j) {
					if(!(S >> j & 1)) {
						if(cnt + pc[j + 1][i] + k > R)continue;
						add(f[1][S ^ (1 << j)][cnt + pc[j + 1][i] + k], f[0][S][k]);
					} else {
						cnt++;//如果这个已经有了,而且在他后面,就捏嘿嘿
					}
				}
			}
		}
		for(int S = 0; S <= mS; ++S) {//枚举位置集合
			for(int k = 0; k <= R; ++k) {//枚举逆序对数....QAQ
				f[0][S][k] = f[1][S][k];
				f[1][S][k] = 0;
			}
		}
	}
	int ans = 0;
	for(int i = L; i <= R; ++i)add(ans, f[0][mS][i]);
	printf("%d\n", ans);
	return;
}
int main() {
	scanf("%d%d%d", &n, &L, &R);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		if(a[i] == 0) {
			m++;
			vis[m] = i;
		}
		vvis[a[i]] = 1;
	}
	for(int i = 1; i <= n; ++i)
		if(!vvis[i]) {
			que[++tot] = i;
		}
	// printf("%d ?\n", m);
	// for(int i = 1; i <= m; ++i)printf("%d ", vis[i]);
	// puts("");
	// for(int i = 1; i <= tot; ++i)printf("%d ", que[i]);
	init();
	solve();
	return 0;
}

/*

10 10 20
0 0 0 3 0 5 0 0 1 8

5 0 4
1 0 3 0 0


*/

std:

爆搜前7个,先枚举前7个填什么值

然后后7个同样搜出来

然后我们要成为的是一个范围,所以知道后面排列的值

排序,双指针!?

但是我们可以更优秀去匹配

$f_{i}$ 表示有i个逆序对的方案数,前缀和一个

然后另一个搜到一种状态就直接皮配

然后我们外层枚举完了左边选的数值之后就是内层的搜索

相当于 $C_{7,14}*7!=P_{7,14}$

于是做完啦

口胡T1

i走到 $i+a_i$ 要0代价

i走到其他位置要 $|i-j|$ 代价

问1~n最小代价

i向i+1连边代价为1

i+1向i连边代价为1

然后i向 $i+a_i$ 连边代价为0

01最短路

这个很不错,像一个完全背包

一个斜着的边拆成很多横着的边和一条竖着的边

口胡T2

两棵树, $i>f_i$

然后询问 $p_1,p_2$ 表示第一棵树和第二棵树上的点到根的路径上所有点拿出来然后公共部分的点标号最大值

1e5

第一棵树可以直接建立线段树,树剖他

然后你会发现第二棵不能同时建立树剖啊....

所以说我们在第二棵树上dfs

然后点亮所有点

然后区间查询一下第一棵树

std:

还是要线段树!

还是要用dfn重标号

你会注意到一个性质:从 $p_2$ 向上跳,第一个子树dfn?范围包括了 $p_1$ 的就是答案

那么就会发现我们可以从 $a_1$ 到 $a_k$ 第一个满足条件的点就是答案

我们设每一个点有一个在第二个树上的dfn序范围,我们只要判断 $p_1$ 的dfn是否在这个范围

于是你会发现相当于从根到这个点染色,然后这个点上查 $p_2$ 的颜色

于是可以离线或者在线树上主席树

口胡T3

z_{i,j}=gcd(i,j)

然后我们有一个y数组

问是否存在一行是y数组

其中矩阵有大小限制

显然行数是 $LCM{y_1,y_k}$

显然列数.....

前面都是后面的一个数的倍数?

不妨我们设出第一个数出现的列数为 $k_1$

第二个数出现肯定是 $k_1+1$

然后我们有

k_1y_1+1 \equiv 0 (mod y_2)

然后继续

k_1y_1+1 \equiv 0 (mod y_2)

k_1y_1+2 \equiv 0 (mod y_3)

k_1y_1+3 \equiv 0 (mod y_4)

合并所有方程,解出一个最小的 $k_1$ ,为最小的列数

如果行数和列数都小于矩阵范围

则可以

夏晓光(loveJY)的博客

qbxtD6 && NOIP提高组考前刷题冲刺班（第六场）

$N=2$

N=3

qbxt D5 && NOIP提高组考前刷题冲刺班（第五场）

夏晓光(loveJY)的博客

qbxtD6 && NOIP提高组考前刷题冲刺班（第六场）

N=2N=2N=2

N=3

qbxt D5 && NOIP提高组考前刷题冲刺班（第五场）

$N=2$