CSP-S2考前综合强化刷题（第七场）

唉,回去了...

显然取出现次数最多的

code:


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;

int a[MAXN], n, k, tot, ans;
int que[MAXN], buc[MAXN];

int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		buc[a[i]]++;
	}

	for(int i = 1; i <= n; ++i) {
		if(buc[i]) {
			que[++tot] = buc[i];
		}
	}
	sort(que + 1, que + tot + 1);
	for(int i = tot; i >= max(tot - k + 1, 1); --i) {
		ans += que[i];
	}
	printf("%d\n", n - ans);

	return 0;
}

考虑我们期望的线性型,那么我们一个逆序对只需要看后面的那个先消失然后第一个后消失

然后就是两个数的期望算一下!再考虑所有点对的就好了

枚举第一组t就是第一个数取走在什么时候,然后我们有

$\sum_{t}q^{2t+1}p$ 这个东西,对他等比数列求和

1+q^1+q^2+.....+q^{n-1}=\frac{1-q^n}{1-q}

证明乘以q

然后我们要级数求和, $q<1$ 会收敛, $q^n=0$

显然右边这个东西会变成 $1/1-q$

回到这个题公差为q^2,首项显然是pq

得到 $\frac{pq}{1-p^2}$

然后权值为1

所以 $n*(n-1)/2*\frac{pq}{1-p^2}$

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e8 + 7;
const int P = 998244353;
ll n, x, y, p, p2, i2;

inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

int main() {
	scanf("%lld%lld%lld", &n, &x, &y);
	p = x * ksm(y, P - 2) % P;
	p2 = ksm((P - p + 2) % P, P - 2) % P;
	i2 = ksm(2, P - 2) % P;
	printf("%lld\n", n * (n - 1) % P * i2 % P * (P - p + 1) % P * p2 % P);
	return 0;
}

Wustd:

$x^k$ =k个西格玛求和,然后k元组,而且这个k元组是有序的

就相当一个路径上无标号选取了k个边

那么我们就考虑把形态dp出来,怎么计算呢?

这些k元组中我们要选出几列

然后第二类斯特林数就是有k行(k个球),i列(每列是盒子)每个球放入相同盒子中,每一个盒子都非空

$S_{n,m}$ 怎么递推呢?

考虑第n个球,如果放入m个盒子,则从 $S_{n-1,m-1}$ 转移

否则会发现我们从 $S_{n-1,m}*m$ 转移,也就是说我们丢进任何一个集合内

然后再看看组合意义,那个sigema写成矩阵就是

k行,有m列,每一列要求非空

我们有k个球,m个盒子,要求每个盒子球都丢进去

这样我们就可以斯特林反演了

$x^k=\sum_{i=1^m}S_{m,i}C_{x,i} i!$

然后设 $f_{i,j}$ 把组合数递推一下就好了


//卡空间
//使用int空间一定开的下,ll一定开不下
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXK = 507;
const int P = 998244353;
const int MAXN = 1e5 + 7;
const int MAXM = 3e5 + 7;
int n, m, K;
int ccnt, home[MAXN], nxt[MAXM], to[MAXM], in[MAXN];
int que[MAXN];

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

int f[MAXN][MAXK];

inline void add(int &x, int y) {
	x += y;
	x = x >= P ? x - P : x;
}

inline void topsort() {
	int hd = 1;
	int tl = 0;
	for(int i = 1; i <= n; ++i) {
		if(in[i] == 0) {
			que[++tl] = i;
		}
	}
	f[1][0] = 1;
	while(hd <= tl) {
		int u = que[hd];
		++hd;
		for(int i = home[u]; i; i = nxt[i]) {
			int v = to[i];
			for(int j = 0; j <= K; ++j) {//哪有走0条边的啊
				add(f[v][j], f[u][j]);
				if(j > 0)add(f[v][j], f[u][j - 1]);
			}
			in[v]--;
			if(!in[v])que[++tl] = v;
		}
	}
	return ;
}

ll stl[MAXK][MAXK];
ll fac[MAXK];

inline void init() {
	fac[0] = 1;
	for(int i = 1; i <= K; ++i) {
		fac[i] = 1ll * fac[i - 1] * i % P;
	}
	stl[0][0] = stl[1][1] = 1;
	for(int i = 2; i <= K; ++i) {
		for(int j = 1; j <= i; ++j) {
			stl[i][j] = (stl[i - 1][j] * j % P + stl[i - 1][j - 1]) % P;
		}
	}
	return ;
}


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;

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test1.out", "w", stdout);
	n = read();
	m = read();
	K = read();
	for(int i = 1, x, y; i <= m; ++i) {
		x = read();
		y = read();
		ct(x, y);
	}
	topsort();
	init();
	for(int i = 1; i <= n; ++i) {
		ll ans = 0;
		for(int j = 1; j <= K; ++j) {
			ans = (ans + f[i][j] * fac[j] % P * stl[K][j] % P) % P;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

仔细观察,我们发现答案就是x轴和y轴的中位数

那么考虑我们怎么快速求出中位数,考虑二分

然后我们要判断有多少个交点在左边,有多少个交点在右边

显然可以冲一个分类讨论

当x是竖线的时候,你会发现两组直线交点在右侧当且仅当斜率小的直线而且与这个竖线交点靠上

所以说我们可以把这个按照交点排序,然后二维数点,看看能否达到一半,题目也告诉我们直线两两有交集

直接冲就好了

纵坐标上可以交换x,y来实现

贴一份暴力吧,正解不实现了懒懒懒

暴力在找中位数的时候可以nth_element/se

code:


#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
int n;
const int MAXN = 2e7 + 6e6 + 7;
struct rec {
	ll A, B, C;
	bool operator<(const rec &x) {//按照斜率排序,叉积判
		return A * x.B > B * x.A;//叉积判!!
	}
} e[MAXN];

const db eps = 1e-14;

struct  NODE {
	db x, y;
} q[MAXN];

inline bool cmp1(const NODE x, const NODE y) {
	return x.x - y.x < eps;
}


inline bool cmp2(const NODE x, const NODE y) {
	return x.y - y.y < eps;
}

inline NODE getnd(int i, int j) {
	NODE z;
	z.y = (e[j].C * e[i].A - e[i].C * e[j].A) / (db)(e[j].A * e[i].B - e[i].A * e[j].B);
	z.x = (e[j].B * e[i].C - e[i].B * e[j].C) / (db)(e[j].A * e[i].B - e[i].A * e[j].B);
	return z;
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%lld%lld%lld", &e[i].A, &e[i].B, &e[i].C);
		e[i].C = -e[i].C;
	}
	int tot = 0;
	for(int i = 1; i <= n; ++i) {
		for(int j = i + 1; j <= n; ++j) {
			q[++tot] = getnd(i, j);
		}
	}
	if(tot & 1) {
		nth_element(q + 1, q + tot / 2 + 1, q + tot + 1, cmp1);
		printf("%lf ", q[tot / 2 + 1].x);
	} else {
		nth_element(q + 1, q + tot / 2, q + tot + 1, cmp1);
		printf("%lf ", q[tot / 2].x);
	}
	if(tot & 1) {
		nth_element(q + 1, q + tot / 2, q + tot + 1, cmp2);
		printf("%lf\n", q[tot / 2 + 1].y);
	} else {
		nth_element(q + 1, q + tot / 2, q + tot + 1, cmp2);
		printf("%lf\n", q[tot / 2].y);
	}
	return 0;
}

夏晓光(loveJY)的博客

CSP-S2考前综合强化刷题（第七场）

CSP-S2考前综合强化讲课(Day 6)