Atcoder Beginner Contest 134

Posted on | Edited on | Views:

$F$ 题不错.

A Dodecagon

签到题.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
}
int main()
{
	int x=read();
	cout<<3*x*x<<endl;
	return 0;
}

B Golden Apple

签到题.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
}
int main()
{
	int n=read(),D=read();
	cout<<(n+2*D)/(2*D+1)<<endl;
	return 0;
}

C Exception Handling

$ST$ 表或者线段树写一写就好了.或许有不用数据结构的高论?

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
#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=2e5+10;
int a[MAXN];
struct Segtree
{
	struct node
	{
		int mx;
	}Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
	void pushup(int o)
	{
		root.mx=max(lson.mx,rson.mx);
	}
	void bd(int o,int l,int r)
	{
		if(l==r)
		{
			root.mx=a[l];
			return;
		}
		int mid=(l+r)>>1;
		bd(o<<1,l,mid);
		bd(o<<1|1,mid+1,r);
		pushup(o);
	}
	int query(int o,int l,int r,int L,int R)
	{
		if(L>R || L>r || l>R)
			return -1;
		if(L<=l && r<=R)
			return root.mx;
		int res=0;
		int mid=(l+r)>>1;
		if(L<=mid)
			res=max(res,query(o<<1,l,mid,L,R));
		if(R>mid)
			res=max(res,query(o<<1|1,mid+1,r,L,R));
		return res;
	}
}T;
int main()
{
	int n=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	T.bd(1,1,n);
	for(int i=1;i<=n;++i)
		printf("%d\n",max(T.query(1,1,n,1,i-1),T.query(1,1,n,i+1,n)));
	return 0;
}

D Preparing Boxes

倒着确定每个数,显然每个数是唯一确定的.

暴力统计就好了,由调和级数知,时间复杂度 $O(n\log 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
#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=2e5+10;
int n,a[MAXN];
int t[MAXN],m=0;
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=n;i>=1;--i)
	{
		int x=a[i];
		for(int j=i*2;j<=n;j+=i)
			x^=t[j];
		t[i]=x;
		if(x)
			++m;
	}
	cout<<m<<endl;
	for(int i=1;i<=n;++i)
		if(t[i])
			printf("%d ",i);
	return 0;
}

E Sequence Decomposing

给一个序列,求最少分成几个单调上升子序列.

大概就是导弹拦截那道题.答案就是最长单调不降子序列的长度.

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
#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=1e5+10;
int n,A[MAXN],a[MAXN];
#define lowbit(x) x&(-x)
int bit[MAXN];
void add(int x,int c)
{
	for(;x<=n;x+=lowbit(x))
		bit[x]=max(bit[x],c);
}
int sum(int x)
{
	int s=0;
	for(;x;x-=lowbit(x))
		s=max(s,bit[x]);
	return s;
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		A[i]=a[i]=read();
	sort(A+1,A+1+n);
	int m=unique(A+1,A+1+n)-A-1;
	for(int i=1;i<=n;++i)
	{
		int x=lower_bound(A+1,A+1+m,a[i])-A;
		x=m+1-x;
		int y=sum(x)+1;
		add(x,y);
	}
	cout<<sum(n)<<endl;
	return 0;
}

F Permutation Oddness

$dp$ 计数,设 $f(i,j,k,l)$ 表示考虑前 $i$ 个位置, $1,2,\dots i $ 中有 $j$ 个数还没有填,位置 $1,2,\dots,i$ 中有 $k$ 个位置还没有放,已经确定的权值为 $l$ 时的方案数.

后两维可以写在一起,状态数 $O(n^4)$ ,转移 $O(1)$ ,时间复杂度 $O(n^4)$ .

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
#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=51;
const int P=1e9+7;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
void upd(int &x,int y)
{
	x=add(x,y);
}
int N,K;
int f[MAXN][MAXN][MAXN*MAXN];
int main()
{
	N=read(),K=read();
	f[0][0][0]=1;
	for(int i=1;i<=N;++i)
		for(int j=0;j<=i;++j)
			for(int k=2*j;k<=K;++k)
			{
				upd(f[i][j][k],mul(2*j+1,f[i-1][j][k-2*j]));
				upd(f[i][j][k],mul(j*j+2*j+1,f[i-1][j+1][k-2*j]));
				if(j)
					upd(f[i][j][k],f[i-1][j-1][k-2*j]);
			}
	cout<<f[N][0][K]<<endl;
	return 0;
}