CF1153

Posted on | Edited on | Views:

$Div.2$

CF1153B Serval and Toy Bricks

  • 贪心+构造.
  • 能放行 $\max$ 而不爆列 $\max$ 的位置都放行 $\max$ , 能放列 $\max$ 而不爆行 $\max$ 的位置都放列 $\max$ .
  • 这样每个位置显然不会被定为两个不同的值.对于其他有而未放的位置直接都放 $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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=128;
int n,m,H;
int a[MAXN],b[MAXN];
int c[MAXN][MAXN],h[MAXN][MAXN];
int main()
{
	n=read(),m=read(),H=read();
	for(int i=1;i<=m;++i)
		a[i]=read();
	for(int i=1;i<=n;++i)
		b[i]=read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			h[i][j]=read();
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			if(h[i][j])
			{
				if(a[j]<=b[i])
					c[i][j]=a[j];
				else
					c[i][j]=b[i];
			}
			printf("%d ",c[i][j]);
		}
		puts("");
	}
	return 0;
}

CF1153C Serval and Parenthesis Sequence

  • 贪心+构造.显然可以将左括号,右括号的权值分别赋为 $1,-1$.
  • 那么容易发现题中限制条件就是权值前缀和 $sum(n)=0,sum(i)>0,\forall i<n$.
  • 将所有未确定的位置赋为 $1$ ,可以算出 $sum(n)=k$ ,需要将 $\frac k 2$ 个位置改为 $-1$.
  • 从后往前贪心改,能改的位置就改.判一下不合法的情况, $k$ 为奇数,负数或不够改.
  • 改完后再从前往后 $check$ 一次就可以了.
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
#include<bits/stdc++.h>
#define GG return puts(":("),0;
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=3e5+10;
int n;
char buf[MAXN];
int a[MAXN];
int main()
{
	n=read();
	scanf("%s",buf+1);
	int k=0,tot=0;
	for(int i=1;i<=n;++i)
	{
		if(buf[i]==')')
			--k,a[i]=-1;
		else if(buf[i]=='(')
			++k,a[i]=1;
		else
			++k,a[i]=1,++tot;
	}
	if(k<0 || k%2==1 || k/2>tot)
		GG
	for(int i=n;i>=1 && k>0;--i)
	{
		if(buf[i]=='?')
			a[i]=-1,k-=2;
	}
	int sum=0;
	for(int i=1;i<n;++i)
	{
		sum+=a[i];
		if(sum<=0)
			GG
	}
	for(int i=1;i<=n;++i)
	{
		if(a[i]==1)
			putchar('(');
		else
			putchar(')');
	}
	puts("");
	return 0;
}

CF1153D Serval and Rooted Tree

  • 树形 $dp$ .(一定思维难度?)
  • 考虑一颗子树,若其中有 $p$ 个叶子节点,任意选择 $p$ 个互不相同的权值,经过最优排列后,这个根节点的权值的相对大小,即排名,一定是确定的,即与选择了哪些权值无关.
  • 那么记 $f_i$ 表示给子树 $i$ 中的叶子节点最优赋值后,节点 $i$ 上的权值是这些叶子节点权值中的第 $f_i$ 大.
  • 对于叶子节点 ,显然 $f_u=1$ .
  • 若操作符为 $\min$ ,可以证明感性理解, $f_u=\sum f_v$ .若操作符为 $\max$ ,可以证明感性理解, $f_u=\min f_v$ ,其中 $v$ 为 $u$ 的儿子.
  • 共有 $k$ 个叶子节点,最后答案即为 $k+1-f_1$ ,即全部可用的权值的第 $f_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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=3e5+10;
int head[MAXN],nx[MAXN],to[MAXN],ecnt=0;
inline void addedge(int u,int v)
{
	++ecnt;
	nx[ecnt]=head[u];
	to[ecnt]=v;
	head[u]=ecnt;
}
int n;
int opt[MAXN],f[MAXN],outdeg[MAXN],k=0;
void dfs(int u)
{
	if(!outdeg[u])
	{
		++k;
		f[u]=1;
		return;
	}
	if(opt[u]==1)
		f[u]=MAXN+1;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		dfs(v);
		if(!opt[u])
			f[u]+=f[v];
		else
			f[u]=min(f[u],f[v]);
	}
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		opt[i]=read();
	for(int i=2;i<=n;++i)
	{
		int fa=read();
		addedge(fa,i);
		++outdeg[fa];
	}
	dfs(1);
	cout<<k+1-f[1]<<endl;
	return 0;
}

CF1153F Serval and Bonus Problem

  • 概率/期望,计数, $dp$ .

  • 随便在线段上钦定 $2n$ 个点,分割成 $2n+1$ 段区间,所以每段区间的期望长度就是 $\frac l {2n+1}$ .于是只需要再乘上一段区间至少被 $k$ 条线段覆盖的概率就好了.

  • 设 $f(i,j)$ 表示考虑 $i$ 个端点,第 $i$ 个端点后面的区间恰好被 $j$ 条线段所覆盖的方案数.转移时枚举 $i$ 是作为左端点还是右端点, $O(n^2)$ 大力转移.

  • 最后将所有合法方案数目求和,除以 $f(2n,0)$ 得到概率.

    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
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    inline int read()
    {
    	int out=0,fh=1;
    	char jp=getchar();
    	while ((jp>'9'||jp<'0')&&jp!='-')
    		jp=getchar();
    	if (jp=='-')
    		fh=-1,jp=getchar();
    	while (jp>='0'&&jp<='9')
    		out=out*10+jp-'0',jp=getchar();
    	return out*fh;
    }
    const int P=998244353;
    inline int add(int a,int b)
    {
    	return (a + b) % P;
    }
    inline int mul(int a,int b)
    {
    	return 1LL * a * b % P;
    }
    int fpow(int a,int b)
    {
    	int res=1;
    	while(b)
    	{
    		if(b&1)
    			res=mul(res,a);
    		a=mul(a,a);
    		b>>=1;
    	}
    	return res;
    }
    int inv(int x)
    {
    	return fpow(x,P-2);
    }
    const int MAXN=2019<<1;
    int n,l,k;
    int fac[MAXN];
    int f[MAXN][MAXN];
    int main()
    {
    	n=read(),k=read();
    	l=read();
    	int perl=mul(l,inv(2*n+1));
    	fac[0]=1;
    	for(int i=1;i<=n;++i)
    		fac[i]=mul(fac[i-1],i);
    	f[0][0]=1;
    	for(int i=0;i<2*n;++i)
    	{
    		for(int j=n<i?n:i;j>=0;--j)
    		{
    			f[i+1][j+1]=add(f[i+1][j+1],f[i][j]);
    			if(j)
    				f[i+1][j-1]=add(f[i+1][j-1],mul(f[i][j],j));
    		}
    	}
    	int ans=0;
    	for(int i=1;i<2*n;++i)
    		for(int j=k;j<=n;++j)
    		{
    			int tmp=mul(f[i][j],f[2*n-i][j]);
    			tmp=mul(tmp,fac[j]);
    			ans=add(ans,tmp);
    		}
    	cout<<mul(ans,mul(perl,inv(f[2*n][0])));
    	return 0;
    }