3月模拟赛1

3月模拟赛1
质量不错

T1

给定一棵树,Alan和Bob轮流操作,Alan先手。
Alan可以把一个白点染灰,Bob可以选择一个白点,把被选点和周围相邻的点都染黑。
Bob有K次作弊机会,可以在任意时刻使用,每次作弊可以断开一条树边。
当所有点都被染黑,Bob获胜,否则,Alan获胜。求最优策略下的输赢局面。
复杂度线性

请先思考后再展开

如果存在联通块大小=1,A获胜
如果存在联通块大小=奇,A在某个叶子节点的父亲放,B只能取那个叶子节点,可归纳到大小为1,A获胜
接下来只剩下偶数的情况
如果存在大小=2,B获胜
如果存在不是2的链,A在端点放,B在旁边放,剩下的大小=奇,A获胜
如果存在某个节点x的孩子全部是叶子节点且不止一个,A在x放,显然获胜
而如果有非叶子节点在严格子树内,考虑深度最大那个非叶子节点的孩子处放,B必须在其父亲放,然后因为没有其他孩子,这样就减少了3个节点,剩下的大小为奇数

综上所述,B获胜,当且仅当把树完美匹配为相邻的大小为2的联通块,并且至少有 (n/2-1) 次删边机会

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
80
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<ll,ll>
#define PB push_back
inline void chmax(ll &x,ll y) {x=x>y?x:y;}
inline void chmin(ll &x,ll y) {x=x<y?x:y;}
const int MAX_N=5e3+10;
vector<int> to[MAX_N];
bool ok=1,v[MAX_N];
void dfs(int x,int fa)
{
v[x]=1;
for(int t=0;t<(int)to[x].size();t++)
{
int y=to[x][t];if(y==fa) continue;
dfs(y,x);
}
if(v[x]==1)
{
if(v[fa]) v[fa]=0;
else ok=0;
}
}
void main()
{
int n,K;scanf("%d%d",&n,&K);
for(int i=1;i<=n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
to[x].PB(y);to[y].PB(x);
}
dfs(1,0);
if(ok and K>=(n/2)-1) puts("Bob");
else puts("Alan");
}
};
int main()
{
srand(time(0));
mine::main();
}

T2

给定n个三元组(ai,bi,ci)
求有多少合法的(a0,b0,c0)满足
$∀i:[a0>ai]+[b0>bi]+[c0>ci]≥2$
n,a,b,c≤5e5

请先思考后再展开

因为一开始看错题,想的是其他人要比我小,就懒得换了,翻转一下即可

考虑二维平面上(a,b)能选取的c的数量,首先左上角不能有节点,然后左下角和右上角贡献c+1的上界
注意到平面上能限制我的c的上界的,本质只是有n个节点,分别为x和y的两次,看上去有n方个不同的矩形
但仔细考虑,发现只有2n个权值完全不同的矩形,就是两维坐标分别排序,然后维护两个指针的移动
这个过程每次增加的面积,类似于一个矩形横坐标或纵坐标增加的过程
不过因为有左上角不能有节点的限制,这个是类似于一个左上的阶梯形状,可以预处理
那么每次的面积就是和阶梯的交,这个其实只有两段,可以二分得出,复杂度为 $O(nlogn)$

因为横纵坐标都很小,排序可以线性,二分可以转为两个指针,复杂度为 $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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<ll,ll>
#define PB push_back
inline void chmax(ll &x,ll y) {x=x>y?x:y;}
inline void chmin(ll &x,ll y) {x=x<y?x:y;}
const int MAX_N=5e5+10;
int a[MAX_N],b[MAX_N],c[MAX_N];
int bin[30],lg[MAX_N];
ll f1[MAX_N],f2[MAX_N];
pr g1[MAX_N],g2[MAX_N];
ll t1[MAX_N],t2[MAX_N];
void main()
{
bin[0]=1;for(int i=1;i<20;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<MAX_N;i++) lg[i]=lg[i>>1]+1;
int n,A,B,C;scanf("%d%d%d%d",&n,&A,&B,&C);
for(int i=1;i<=A;i++) f1[i]=B;
for(int i=1;i<=B;i++) f2[i]=A;
memset(t1,0x3f,sizeof t1);memset(t2,0x3f,sizeof t2);
for(int i=1;i<=n;i++)
{
a[i]=A-qread()+1,b[i]=B-qread()+1,c[i]=C-qread()+1;
chmin(f1[a[i]],b[i]-1);chmin(f2[b[i]],a[i]-1);
chmin(t1[a[i]],c[i]);chmin(t2[b[i]],c[i]);
}
for(int i=1;i<=A;i++) chmin(f1[i+1],f1[i]);
for(int i=1;i<=B;i++) chmin(f2[i+1],f2[i]);
for(int i=1;i<=A;i++) f1[i]+=f1[i-1];
for(int i=1;i<=B;i++) f2[i]+=f2[i-1];
g1[0]=MP(INF,0);g2[0]=MP(INF,0);int gg1=0,gg2=0;
for(int i=1;i<=A;i++) if(t1[i]<g1[gg1].FR) g1[++gg1]=MP(t1[i],i);
for(int i=1;i<=B;i++) if(t2[i]<g2[gg2].FR) g2[++gg2]=MP(t2[i],i);
g1[++gg1]=MP(1,A+1);g2[++gg2]=MP(1,B+1);
ll ans=(g1[1].SE-1)*(g2[1].SE-1)*C;int i=0,j=0;
while(1)
{
if(i==gg1-1 and j==gg2-1) break;
if(j==gg2-1 or g1[i+1].FR>g2[j+1].FR)
{
i++;
//贴着左边,g1[i].SE->g1[i+1].SE-1,<=g2[j+1].SE-1
int l=g1[i].SE,r=g1[i+1].SE-1,pos=g1[i+1].SE;
while(l<=r)
{
int mid=(l+r)>>1;
if(f1[mid]-f1[mid-1]<g2[j+1].SE-1) pos=mid,r=mid-1;
else l=mid+1;
}
ll area=f1[g1[i+1].SE-1]-f1[pos-1]+(pos-1-g1[i].SE+1)*(g2[j+1].SE-1);
ans+=area*(g1[i].FR-1);
}
else
{
j++;
//贴着上面,g2[j].SE->g2[j+1].SE-1,<=g1[i+1].SE-1
int l=g2[j].SE,r=g2[j+1].SE-1,pos=g2[j+1].SE;
while(l<=r)
{
int mid=(l+r)>>1;
if(f2[mid]-f2[mid-1]<g1[i+1].SE-1) pos=mid,r=mid-1;
else l=mid+1;
}
ll area=f2[g2[j+1].SE-1]-f2[pos-1]+(pos-1-g2[j].SE+1)*(g1[i+1].SE-1);
ans+=area*(g2[j].FR-1);
}
}
printf("%lld",ans);
}
};
int main()
{
srand(time(0));
mine::main();
}

T3

$pi在[1,K]中随机,记ai表示i出现的次数,求 a_1^F a_2^F a_3^F … a_L^F 的期望 mod \ 2003$
$n≤10^9,L \times F≤5e4,F≤1e3$

请先思考后再展开

%DZY
补充:
总期望=各个单项式期望的和,每个单项式的长度为FL
每个合法单项式的期望,就是本质不同位置的概率乘积,即 $\frac{1}{K^{种类t}}$
枚举种类数量t,变成一个计数问题,在大小为FL的矩阵里填n以内的数字,某个数字不能跨行出现,且种类为t

因为行独立,则 $dp(i)=划分为t个给定数字的方案数=第二类斯特林数卷自己L次[t] \times t!$
$ans=\sum dp(t) C_n^t t! \frac{1}{K^t}$
因为有阶乘,计算dp的时候算到MOD即可

时间复杂度为 $O(F^2+MOD^2logL)$

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<ll,ll>
#define PB push_back
inline void chmax(ll &x,ll y) {x=x>y?x:y;}
inline void chmin(ll &x,ll y) {x=x<y?x:y;}
const int MOD=2003;
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<=-MOD) x+=MOD;}
const int MAX_N=3e3;
int c[MAX_N];
void cheng(int a[],int b[],int len)
{
memset(c,0,sizeof c);
for(int i=0;i<len;i++) for(int j=0;j<len;j++) if(i+j<len) add(c[i+j],a[i]*b[j]%MOD);
memcpy(a,c,sizeof c);
}
int C[MAX_N][MAX_N],S2[MAX_N][MAX_N],inv[MAX_N],fac[MAX_N];
int getC(int n,int m)
{
if(n<m) return 0;
if(n>=MOD or m>=MOD) return getC(n%MOD,m%MOD)*getC(n/MOD,m/MOD)%MOD;
return C[n][m];
}
int dp[MAX_N],f[MAX_N];
void main()
{
fac[0]=1;for(int i=1;i<MAX_N;i++) fac[i]=fac[i-1]*i%MOD;
C[0][0]=1;S2[0][0]=1;
for(int i=1;i<MAX_N;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++)
{
C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
S2[i][j]=(S2[i-1][j-1]+S2[i-1][j]*j)%MOD;
}
}
inv[1]=1;for(int i=2;i<MOD;i++) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
int n,K,L,F;scanf("%d%d%d%d",&n,&K,&L,&F);K%=MOD;
if(K==0) {puts("0");return;}
for(int i=0;i<=F;i++) f[i]=S2[F][i];
int e=L;dp[0]=1;
while(e)
{
if(e&1) cheng(dp,f,MOD);
cheng(f,f,MOD);e>>=1;
}
int ans=0;
for(int t=1,tk=inv[K];t<=MOD-1;t++,tk=tk*inv[K]%MOD)
add(ans, dp[t]*getC(n,t)%MOD*fac[t]%MOD*tk%MOD );
printf("%d",ans);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/5627.html
转载请注明出处,谢谢!