掉掉掉-15/ll

靠不能让qlr再rank2了!!!

当大于33的时候为0,不知道为啥成为了2^32的一个倍数....

否则是暴力乘即可

如果仔细打表会发现,每个格子上能填的数是一段连续的区间

于是猜想计算区间的上下界

发现上界是这个格子到(n,m)组成的矩形格子数

对称下

下界是(1,1)到这个格子组成的矩形格子数

所以做完了....,差分维护区间加即可

考场现场发明O(n)高消....

首先设 $f_i$ 表示拿到排列i的最优消除代价

然后转移就是考虑这个排列用不用c

f_i=min(c+1/n!*(sum_f),g_i)

$g_i$ 表示我们不用c的代价,不难发现就是逆序对a和顺序对a+b的最小值

于是我们可以发现,这个是类似于高斯消元的升级版的东西

但是!我们是不是还能再进化一下呢?

也就是说能不能直接做呢,本质上我们要求 $c+1/n!*(sum_f)$ 是吧?

设x是 $c+1/n!*(sum_f)$

写式子:

$x=c+1/n!*(\sum_i{min(g_i,x)})$

变变变

\sum_i{(x=\frac{c*n!+sum_{gi}}{n!-n+i-1})}

于是会发现n是n!级别的,但是本质不同的 $g_i$ 其实相当少,因为只和逆序对数有关

于是 $f_i$ 表示逆序对为i的排列到1~n的最小代价

设 $w_i$ 表示逆序对为i的排列方案数

仿照上文我们有

$x=c+1/n!*(\sum_i{w_imin(g_i,x)})$

于是

\sum_i{x=\frac{n!*c+sum_{wgi}}{n!-ssum_w}}

然后我们就和之前一样:枚举前面的i然后计算x,看x的值是不是在 $g_{i},g_{i+1}$ 之间即可....

ex:

这个有凸性....

所以说你不断的向后枚举的时候,当第一个从大于号到小于号就对了.....

code:



//验证结论正确性的带暴力
//暴力写完了,结论萎了
//于是这是篇正解
//但是有没有分就不一定了
#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
const int MAXN = 20;
const int MAXM = 5000;
int T, a, b, c, d, n, k;
ll vlz, vlm;
int p[MAXN];
ll g[MAXM], sumw[MAXM], w[MAXM], sumgw[MAXM];

namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;

inline ll gcd(ll x, ll y) {
	return y == 0 ? x : gcd(y, x % y);
}

//不就是解你妈的方程吗
//不信了...
ll f[MAXN][MAXM];
inline void letsdp() {
	f[1][0] = 1;//1
	for(int i = 2; i <= 16; ++i) {
		int N = i * (i - 1) / 2;
		for(int k = 0; k <= N; ++k) {
			for(int l = 1; l <= i; ++l) {
				f[i][k] += f[i - 1][k - i + l];
			}
		}
	}
	return ;
}

inline void init1() {
	letsdp();
	return ;
}

inline ll getv(ll tmp) {
	ll j = n * (n - 1) / 2 - tmp;
	ll qaq = 0;
	qaq = min(j * a + b, tmp * a);
	return qaq;
}

struct rec {
	ll g, w;
	bool operator<(const rec &x)const {
		return g < x.g;
	}
} A[MAXM];

//把每个本质不同的拿出来!!!
inline void init2() {
	memset(sumgw, 0, sizeof(sumgw));
	memset(sumw, 0, sizeof(sumw));
	ll fac = 1;
	for(int i = 1; i <= n; ++i) {
		fac = fac * i;
	}
	int N = n * (n - 1) / 2;
	for(int i = 0; i <= N; ++i) {
		A[i + 1].g = getv(i);
		A[i + 1].w = f[n][i];
	}
	++N;
	sort(A + 1, A + N + 1);
	for(int i = 1; i <= N; ++i) {
		sumgw[i] = sumgw[i - 1] + A[i].g * A[i].w;
	}
	for(int i = N; i >= 1; --i) {
		sumw[i] = sumw[i + 1] + A[i].w;
	}
	A[N + 1].g = 1e18;
	for(int i = 1; i <= N; ++i) {
		vlz = fac * c + sumgw[i];
		vlm = fac - sumw[i + 1];
		if(A[i].g <= vlz / (db)vlm && A[i + 1].g >= vlz / (db)vlm) {
			ll gd = gcd(vlz, vlm);
			vlz /= gd;
			vlm /= gd;
			break;
		}
	}
	return ;
}

inline void solve1() {
	ll tmp = 0;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j < i; ++j) {
			if(p[j] > p[i]) {
				tmp++;
			}
		}
	}
	ll j = n * (n - 1) / 2 - tmp;
	ll qaq = 0;
	qaq = min(j * a + b, 1ll * tmp * a);
	if(qaq > vlz / (db)vlm) {
		printf("%lld/%lld\n", vlz, vlm);
	} else printf("%lld/1\n", qaq);
	return ;
}

int main() {
	// freopen("sj.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	T = read();
	init1();//计算??
	while(T-- > 0) {
		n = read();
		a = read();
		b = read();
		c = read();
		d = read();
		k = ceil(b / (double)a);
		init2();
		for(int orzhq = 1; orzhq <= d; ++orzhq) {
			for(int i = 1; i <= n; ++i) {
				p[i] = read();
			}
			solve1();
		}
	}
	return 0;
}
/*

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

10 1 2 1000 4
1 4 2 5 3 6 7 8 9 10
1 5 2 4 3 6 10 9 8 7
10 8 6 5 3 2 9 7 4 1
7 9 10 3 1 4 5 6 2 8

8 234 998 43 5
1 3 4 2 5 6 8 7
3 2 4 5 1 6 7 8
3 1 5 4 2 7 8 6
8 3 2 4 1 5 3 6
2 3 5 4 8 1 6 7

7 332 256 876 5
1 3 4 2 5 6 7
3 2 4 5 1 6 7
3 1 5 4 2 7 6
3 2 4 1 5 3 6
2 3 5 4 1 6 7

9 998 223 889 5
1 3 4 2 5 9 6 8 7
3 2 4 5 9 1 6 7 8
9 3 1 5 4 2 7 8 6
8 9 3 2 4 1 5 3 6
2 3 9 5 4 8 1 6 7

16 1 3 5 5

*/

降智QAQ

直接模拟是 $O(n^3k)$ ,跑不满所以可过100

于是!!!

考场上写了一个,但是存边没有清空!!!

啊啊啊,于是没了

边数达到了nk级别

没有拿到一点分数QAQ

剩下都是基础:

我们可以用bitset优化一下匹配的过程变成 $n^3*k/32$

唐爷爷手写了bitset实现了/64/se

实现方法:

会发现我们一个点x能成为答案,当且仅当在k棵树内他另外两端点都在x的两个不同子树

这个就可以作为剪枝,然后

std:

判断一个在链上的条件有: $dis(x,y)+dis(y,z)=dis(x,z)$

又因为我们这个显然当不在的时候左边大于右边

那么也就是说可以求和加起来的....

做完了.....用这个区判断点在链上时间复杂度 $O(n^2k)$


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 507;
int n, k, ccnt;
int home[MAXN][MAXN * 2], nxt[MAXN][MAXN * 2], to[MAXN][MAXN * 2];

namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;

inline void ct(int t, int x, int y) {
	ccnt++;
	nxt[t][ccnt] = home[t][x];
	home[t][x] = ccnt;
	to[t][ccnt] = y;
	return ;
}
int dis[MAXN][MAXN];

inline void dfs(int t, int u, int F, int dep, int rt) {
	dis[rt][u] += dep;
	for(int i = home[t][u]; i; i = nxt[t][i]) {
		int v = to[t][i];
		if(v == F)continue;
		dfs(t, v, u, dep + 1, rt);
	}
	return ;
}

inline void solve() {
	for(int t = 1; t <= k; ++t) {
		for(int i = 1; i <= n; ++i) {
			dfs(t, i, 0, 0, i);
		}
	}
	int cnt = 0;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			cnt = 0;
			for(int k = 1; k <= n; ++k) {
				if(dis[i][k] + dis[k][j] == dis[i][j]) {
					cnt++;
				}
			}
			printf("%d ", cnt);
		}
		puts("");
	}
	return ;
}

int main() {
	n = read();
	k = read();
	for(int t = 1; t <= k; ++t) {
		for(int i = 2, x, y; i <= n; ++i) {
			x = read();
			y = read();
			ct(t, x, y);
			ct(t, y, x);
		}
		ccnt = 0;
	}
	solve();//n^2k
	return 0;
}

夏晓光(loveJY)的博客

NOIP提高组考前刷题冲刺班（第一场）

于是!!!

MCOI-03