【清北学国庆刷题班】 Day7

T1 water

题目描述

有一个长为n的序列aia_i，小Y希望数字总共不超过k种。

为了达到这个目的，她可以把任意位置修改成任意数，这个操作可以进行任意多次。

请你帮她求出最少需要修改几个位置可以达成目的。

输入格式

第一行两个整数n,k。

接下来一个n个整数aia_i。

输出格式

一行一个整数表示答案。

样例输入

1
2
5 2
2 2 1 1 5

样例输出

1
1

样例解释

把5(第5个位置的数）改成1或2就行了。

数据范围

对于30%的数据，n≤20n\leq 20

对于另外30%的数据，n≤5000n\leq 5000

对于所有数据，满足q≤k≤n≤200000,1≤ai≤nq\le k \le n \le 200000,1\le a_i \le n

思路

这道目是真的水，这个题目统计一下每个数字的数量和数字的种类，然后按数量从小到大排序，删除数量最小的k−kmorek-k_{more}种就可以了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define re register
#define ll long long
using namespace std;
const int maxn=2000005;
ll n,k;
ll kind,ans;
ll a[maxn],cnt[maxn];
bool v[maxn];
int main()
{
	cin>>n>>k;
	memset(cnt,0x3f,sizeof(cnt));
	memset(v,0,sizeof(v));
	ll maxn=-9999;
	for(re int i=1;i<=n;i++)
	{
		cin>>a[i];
		maxn=max(maxn,a[i]);
		if(!v[a[i]])
		{
			kind++;
			cnt[a[i]]=1;
			v[a[i]]=true;
		}
		else
		{
			cnt[a[i]]++;
		}
	}
	ll rev=kind-k;
	sort(cnt+1,cnt+maxn+1); 
	for(int i=1;i<=rev;i++)
	ans+=cnt[i];
	cout<<ans<<endl;
	return 0; 
}

T2 circle

题目描述

如果你听过我今年的冬令营营员交流讲课，那么这将会是一道水题。

有一个1...n−11...n-1依次连成的环，有一个从1开始移动的指针，每次指针所在位置有p的概率消失并将这个位置对应的下标（在1...n−11...n-1中）插入序列B的末尾，然后指针移动一格（1移到2，n移到1这样，一个位置若已经消失则不会被移动到）。所有位置都消失时游戏结束。

最后B会是一个排列，你需要求出B的逆序对的期望，对998244353取模。

输入格式

一行三个整数n,x,y。概率p=xy。

输出格式

一行一个整数表示答案。

样例输入

1
4 1 2

样例输出

1
2

样例解释

因为一些原因，本题不提供样例解释。

数据范围

对于30%的数据,n≤10n\le 10

对于40%的数据,n≤15n\le 15

对于50%的数据,n≤20n\le 20

对于所有数据,1≤n≤108,0<x<y≤1091\le n \le 10^8,0<x<y\le 10^9

思路

那么只要做n=2n=2的情况，答案是∑tq2t+1p=qp1−q2\sum_{t}q^{2t+1}p=\frac {qp} {1-q^2}。
因此此题只需输出pqn(n−1)21−q2\frac {\frac {pqn(n-1)} {2}} {1-q^2}即可

代码(std)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> T gcd(T a, T b){return !b?a:gcd(b,a%b);}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int mo = 998244353;
int power(int a, int n) {
	int rs=1;
	while(n){
		if(n&1)rs=1ll*rs*a%mo;
		a=1ll*a*a%mo;n>>=1;
	}
	return rs;
}
int n,A,B,p,q;
int main() {
	read(n);read(A);read(B);
	p=1ll*A*power(B,mo-2)%mo;
	q=1+mo-p;
	int res=(1ll*n*(n-1)/2%mo*p%mo*q%mo*power(1-1ll*q*q%mo+mo,mo-2)%mo+mo)%mo;
	printf("%d\n",res);
	return 0;
}

T3 path

题目描述

有一个n个点m条边的DAG(有向无环图)，定义一条经过x条边的路径的权值为xkx^k。

对于 i=1...ni=1...n, 求出所有 1 到 i 的所有路径的权值之和, 对 998244353 取模。

输入格式

第一行三个整数n,m,k。

接下来m行，每行两个整数u,v，描述一条u到v的有向边。

输出格式

n行，每行一个整数表示答案。

样例输入

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

样例输出

1
2
3
4
5
0
1
1
9
51

数据范围

对于20%的数据，n≤2000,m≤5000n\le 2000,m\le 5000

对于另外10%的数据，k=1k=1

对于另外20%的数据，k≤30k\le 30。

对于所有数据，满足n≤100000,m≤200000,0≤k≤500n\le 100000,m\le 200000,0\le k\le 500

数据有梯度。

思路

这道题开始的时候我本来是想着从每条边出发开始遍历，然后没经过一个点记录深度，然后对于这个点的答案加上depkdep^k,然后就可以了

但是真实的代码并不是这样的，正解是：

先讲暴力。 dpu,idp_{u,i}表示1到u的所有路径边数的i次方的和。答案就是dpu,kdp_{u,k}
转移就对于每条边u→v,dpv,i+=∑jdpu,j(ij)u\rightarrow v,dp_{v,i}+=\sum_{j}dp_{u,j} \begin{pmatrix} i\\j \end{pmatrix}，
复杂度O(nk2)O(nk^2)
优化的话xk=∑i{ki}(xi)x^k=\sum_{i}\begin{Bmatrix} k\\i \end {Bmatrix} \begin{pmatrix} x\\i \end{pmatrix}。
也就是说dpu,idp_{u,i}表示1到u的所有路径边数的i次下降幂的和，最后用 stirling 数还原出答案。
第2类stirling数可以递推预处理，是经典问题。转移就对于每条边u→v+=dpu,i−1+dpu,iu\rightarrow v+=dp_{u,i-1}+dp_{u,i}，
复杂度O(mk)O(mk)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<cassert>
#define rep(i,a,b) for (int i=a; i<=b; i++)
#define per(i,a,b) for (int i=a; i>=b; i--)
typedef long long ll;
using namespace std;
typedef pair<int,int> Pii;
typedef vector<int> vec;
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
const int N = 202000, mo = 998244353;
const ll mod = (0x7fffffffffffffffLL / mo - mo)/503*mo;
ll dp[100005][502],s[505][505];
int n,m,K,q[N],deg[N];
int head[N],edgenum,nxt[N<<1],to[N<<1];
inline void add(int u, int v) {
	to[++edgenum]=v; nxt[edgenum]=head[u]; head[u]=edgenum; deg[v]++;
}
inline void topsort() {
	int f=1,r=1; rep(i,1,n) if (!deg[i]) q[r++]=i,dp[i][0]=1;
	while (f!=r) {
		int u=q[f++]; //printf("dot %d\n",u);
		for (int i=head[u]; i!=0; i=nxt[i]) {
			int v=to[i]; deg[v]--; if (!deg[v]) q[r++]=v;
			ll *p1=dp[u];
			ll *p2=dp[u];
			rep(k,0,K) {
				ll &tmp=dp[v][k];
				if (k==0) tmp+=(*p1);
				else {p1++; tmp+=(*p1)+(*p2)*k; p2++;}
			//	tmp+=dp[u][k]+(k==0?0:k*dp[u][k-1]);
				if (tmp>=mod) tmp%=mod;
			}
		}
	}
}
int main() {
	read(n); read(m); read(K);
	s[0][0]=1;
	rep(i,1,500) rep(j,1,i) s[i][j]=(s[i-1][j-1]+1LL*s[i-1][j]*j)%mo;
	rep(i,1,m) {int x,y; read(x); read(y); add(x,y);}
	topsort();
	rep(i,1,n) {
		ll ans=0; rep(j,0,K) ans+=s[K][j]*(dp[i][j]%mo)%mo;
		printf("%lld\n",ans%mo);
	}
	return 0;
}

T4 point

题目描述

你有n条直线，直线用Aix+Biy=CiA_ix+B_iy=C_i来表示。为了减少细节，保证这n条直线以及x轴、y轴两两都有恰好1个交点。

现在这n条直线两两的交点处产生了一个人，现在总共有n(n−1)/2个人。

你需要找到一个点P，使其距离所有人的曼哈顿距离和最小。若有多个满足条件的点，选择x坐标最小的，若仍有多个，选择y坐标最小的。

输入格式

第一行一个正整数n。

接下来n行，每行三个整数Ai,Bi,CiA_i,B_i,C_i。

输出格式

一行两个实数表示答案，请保留6位小数输出。

样例输入

1
2
3
4
3
1 1 1
2 -1 2
-1 2 2

样例输出

1
1.000000 1.000000

数据范围

对于20%的数据，n≤1000n\le 1000

对于40%的数据，n≤5000n\le 5000

对于所有数据，满足n≤40000,∣Ai∣,∣Bi∣,∣Ci∣≤10000n\le 40000,|A_i|,|B_i|,|C_i|\le 10000

思路

我当时考试的时候想的是算出来每个点的坐标，然后算出来曼哈顿距离，但是没把代码打出来

正解：

答案的x坐标即为所有人的中位数，y坐标也同理。
二分答案，就是要数有几个人在mid左侧。
在−∞-\infty处按直线高度排序，那么随着x变大，直线会产生交点，也就是说直线高度大小关系会改变。
发现这个交点个数就是逆序对个数，这个可以画图理解。
树状数组统计就好了O(nlog⁡nlog⁡V)O(n\log n \log V).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> T gcd(T a, T b){return !b?a:gcd(b,a%b);}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 1e5+11;
int n,v[N];
struct line{int a,b,c;}s[N];
bool cmp(const line&x,const line&y){
	if(1ll*x.a*y.b!=1ll*x.b*y.a)return 1.0*x.a/x.b<1.0*y.a/y.b;
	return 1.0*x.c/x.b<1.0*y.c/y.b;
}
pair<double,int>f[N];
int qry(int p){int r=0;while(p)r+=v[p],p-=p&-p;return r;}
void mdy(int p){while(p<=n)v[p]++,p+=p&-p;}
double solve(){
	sort(s+1,s+n+1,cmp);
	double l=-2e8,r=2e8;
	rep(t,1,85){
		double mid=(l+r)/2;
		rep(i,1,n)f[i]=mp((s[i].c-mid*s[i].a)/s[i].b,i);
		sort(f+1,f+n+1);
		rep(i,1,n)v[i]=0;ll res=0;
		rep(i,1,n)res+=i-1-qry(f[i].se),mdy(f[i].se);
		if(res*2<n*(n-1ll)/2)l=mid;else r=mid;
	}
	return l;
}
int main() {
	read(n);
	rep(i,1,n)read(s[i].a),read(s[i].b),read(s[i].c);
	printf("%.6lf ",solve());
	rep(i,1,n)swap(s[i].a,s[i].b);
	printf("%.6lf\n",solve());
	return 0;
}