10.12 模拟赛 by JTZ

, , , ,

狗队模拟赛！

被高一薄杀了/kk

T1

Description

image-20231013085603886

$n\le 10^5$ 1s。

Solution

感觉 T1 是最有石粒的一题。

显然可以 $O(n\log n)$ 模拟哪些东西最早撞到。

观察到碰撞顺序不影响答案，用单调栈维护一个速度不降的序列。最后看下里面还有几个就好了。

复杂度 $O(n)$ 。

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
61
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 100005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
struct yyy {
	double m,v;
}a[maxn];
int stac[maxn],tot,n;
void merge(int x,int y) {
	a[x].v=(a[x].v*a[x].m+a[y].v*a[y].m)/(a[x].m+a[y].m);
	a[x].m=a[x].m+a[y].m;
} 
void solve(void) {
	int i,x,y;
	read(n);
	for (i=1;i<=n;i++) read(x),read(y),a[i].m=x,a[i].v=y;//,gdb(x,y,a[i].m,a[i].v);
	tot=0;
	for (i=1;i<=n;i++) {
		if (tot&&a[stac[tot]].v>a[i].v) {
			merge(stac[tot],i);
			while (tot>1&&a[stac[tot-1]].v>a[stac[tot]].v) merge(stac[tot-1],stac[tot]),tot--;
		}
		else stac[++tot]=i;
	}
	printf("%d\n",tot);
	
}
signed main(void){
	int T;
	read(T);
	while (T--) solve();
	return 0;
}

T2

Description

https://www.luogu.com.cn/problem/CF1374F

Solution

发现如果直接模拟冒泡排序，顺序不顺序的都没什么关系，最后可以做成除了最后两个不一定有序以外，其余都有序。

部分分提示我们要利用好有两个数相同的情况。

考虑一种第一次排完序以后的情况，然后依次操作：

1
2
3
4
5
3 3 5 7 6
3 7 3 5 6 // 然后把 7 移到两个 3 中间
3 3 7 5 6
3 3 6 7 5
3 3 5 6 7

感觉正确性在于如果随便这样换逆序对是 $-2$ 的，但是遇到两个相同的就可以做到逆序对 $-1$。没怎么仔细证明。

具体的就把倒数第二个移到相同的后一个数的后面的后面。

注意特判最后 $a_n=a_{n-2}$ 的情况，这种也是可以的。

czh 写了随机化，正确率挺高的大概也在于只和奇偶有关，正确率差不多就 $\dfrac{1}{2}$ 左右。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n;
int a[maxn],id[maxn];
int ans[maxn*maxn],cnt;
void calc(int x) {
	if (x>n-2) return ;
	int tmp=a[x+2];
	ans[++cnt]=x;
	a[x+2]=a[x+1];a[x+1]=a[x];a[x]=tmp;
}
void solve(int L) {
	int i,j;
	for (i=L;i<=n-2;i++) {
		int id=i;
		for (j=i;j<=n;j++) if (a[id]>a[j]) id=j;
		while (id>i) {
			if (id==i+1) calc(i),calc(i),id--;
			else calc(id-2),id-=2;
		}
	}
}
signed main(void){
	int i,j,fl=0;
	read(n);
	for (i=1;i<=n;i++) read(a[i]);
	solve(1);
	if (a[n]>=a[n-1]) {
		for (printf("%d\n",cnt),i=1;i<=cnt;i++) printf("%d ",ans[i]);
		return 0;
	}
	int id=0;
	for (i=1;i<n;i++) if (a[i]==a[i+1]) id=i;
	if (id==0) return puts("-1"),0;
	int now=i;
	while (now>id+3) {
		if (now==id+4) calc(id+3),calc(id+3),now--;
		else calc(now-2),now-=2;
	} 
	calc(id+1);
	calc(id);
	solve(id);
	if (a[n]>=a[n-1]) {
		for (printf("%d\n",cnt),i=1;i<=cnt;i++) printf("%d ",ans[i]);
		return 0;
	}
	puts("-1");
	return 0;
}

T3

Description

https://www.luogu.com.cn/problem/CF1304F2

Solution

简单dp。单调队列优化一下就好了。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 20005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int f[55][maxn],ans;
int a[55][maxn],s[55][maxn],suf[maxn];
int n,m,L,q[maxn],head,tail,sf[maxn],pf[maxn];
signed main(void){
	int i,j,k;
	read(n);read(m);read(L);
	for (i=1;i<=n;i++) {
		for (j=1;j<=m;j++) read(a[i][j]),s[i][j]=s[i][j-1]+a[i][j];
	}
	for (j=1;j<=m-L+1;j++) f[1][j]=s[1][j+L-1]-s[1][j-1];
//	for (i=2;i<=n;i++) {
//		for (j=1;j<=m;j++) suf[j]=suf[j-1]+a[i][j];
//		for (j=1;j<=m-L+1;j++) {
//			int res=0;
//			for (k=1;k<=m-L+1;k++) {
//				if (k>=j-L+1&&k<=j+L-1) f[i][j]=max(f[i][j],f[i-1][k]+s[i][max(j,k)+L-1]-s[i][min(j,k)-1]);
//				else f[i][j]=max(f[i][j],f[i-1][k]+s[i][k+L-1]-s[i][k-1]+s[i][j+L-1]-s[i][j-1]);
//			}
//			if (i==n) ans=max(ans,f[i][j]);
////			gdb(i,j,f[i][j]);
//		}  
//	}这是暴力，干脆留在这里好了
	
	for (i=2;i<=n;i++) {
		for (j=1;j<=m;j++) suf[j]=suf[j-1]+a[i][j];
		for (j=1;j<=m-L+1;j++) sf[j]=max(sf[j-1],f[i-1][j]+suf[j+L-1]-suf[j-1]);
		for (j=m-L+1;j>=1;j--) pf[j]=max(pf[j+1],f[i-1][j]+suf[j+L-1]-suf[j-1]);
		q[head=tail=1]=0;
		for (j=1;j<=m-L+1;j++) {
			while (head<=tail&&q[head]<=j-L) head++;
			while (head<=tail&&f[i-1][q[tail]]-suf[q[tail]-1]<=f[i-1][j]-suf[j-1]) tail--;
			q[++tail]=j;
			f[i][j]=max(sf[j-L]+suf[j+L-1]-suf[j-1],f[i-1][q[head]]+suf[j+L-1]-suf[q[head]-1]); 
			f[i][j]=max(f[i][j],pf[j+L]+suf[j+L-1]-suf[j-1]);
		}  
		q[head=tail=1]=m-L+1;
		for (j=m-L+1;j>=1;j--) {
			while (head<=tail&&q[head]>=j+L) head++;
			while (head<=tail&&f[i-1][q[tail]]+suf[q[tail]+L-1]<=f[i-1][j]+suf[j+L-1]) tail--;
			q[++tail]=j;
			f[i][j]=max(f[i][j],f[i-1][q[head]]+suf[q[head]+L-1]-suf[j-1]);
		}
	}
	for (j=1;j<=m-L+1;j++) ans=max(ans,f[n][j]);
	printf("%lld",ans);
	return 0;
}

T4

Description

https://www.luogu.com.cn/problem/CF1773G

模拟赛中是对 $998244353$ 取模。

Solution

赛时我是计算方案数最后除以 $n!$ 的，赛后感觉这样太蠢了。可能也是没调出来的一个原因。

观察到 $m=17$，很自然的想到枚举子集转移。

令 $f_S$ 表示到剩下集合 $S$ 的选手的概率。

如果有转移到 $S$ 的子集，一定是 $S\cap s_i\not = S,S\cap s_i\not = \varnothing$。如果有这样的集合 $s_i$，之前一定不会被用过来到达状态 $S$（如果用过，那么应该转移到 $S$ 的子集），令 $c$ 为存在这样的 $s_i$ 的数量，所以可以放心转移：$f_{S\cap s_i}\gets \dfrac{f_{S}}{c}$。这样复杂度是 $O(n2^m)$ 的，平凡。

考虑怎么对于每个 $S$ 快速计算 $S\cap s_i=T$ 的数量。

定义 $g_{S,T}=\sum [S\cap s_i=T]$。根据 $s_i$ 是否包含 $S$ 中不存在的一个点 ${p}$，有转移：$g_{S,T}=g_{S\cup{p},T\cup{p}}+g_{S\cup{p},T}$。复杂度 $O(3^m)$。

总复杂度为 $O(nm+3^m)$。

在具体写法上，$T\subseteq S$，所以可以用一个三进制数来描述 $S,T$，而不是很蠢的开 $2^m$ 个 vector。

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
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=998244353;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m,M;
#define lowbit(x) ((x)&(-(x)))
int a[maxn],g[130000005],pw[18],inv[maxn],h[(1<<17)+5];
double f[(1<<17)+5],ans;
void add(int &x,int y) {x=(x+y)%mod;}
signed main(void){
	freopen("ex_match2.in","r",stdin);
	int i,j,k;char ch;
	read(n);read(m);M=(1<<m);
	for (inv[0]=1,i=1;i<=n;i++) inv[i]=power(i);
	for (pw[0]=1,i=1;i<=m;i++) pw[i]=pw[i-1]*3;
	for (i=0;i<M;i++) {
		for (j=0;j<m;j++) if ((i>>j)&1) h[i]+=pw[j];
	}
	for (i=1;i<=n;i++) {
		for (cin>>ch,j=0;j<m;j++) {
			if (ch=='1') a[i]|=(1<<j);
			ch=getchar();
		} 
		g[h[M-1]+h[a[i]]]++;
	}
	for (i=M-2;i>=0;i--) {
		int tmp=lowbit((M-1)^i);
		for (j=(i-1)&i;j>=0;j=i&(j-1)) {
			g[h[i]+h[j]]=g[h[i+tmp]+h[j]]+g[h[i+tmp]+h[j+tmp]];
			if (j==0) break;
		}
	} 
	f[M-1]=1;
	for (i=M-1;i>=0;i--) if (i&1) {
		int res=0;
		for (j=(i-1)&i;j;j=i&(j-1)) res+=g[h[i]+h[j]];
		if (res==0) ans+=f[i];
		else {
			for (j=(i-1)&i;j;j=i&(j-1)) if (j&1) f[j]+=f[i]*g[h[i]+h[j]]/res;		
		}
	}
	printf("%.14lf",ans);
	return 0;
}

这里贴的原题的代码。