Tenka1 Programmer Contest 2019

Posted on | Views:

感觉这场打得好烂…

C Stones

  • 比较弱智.最后一定是连续一段黑之后连续一段白.枚举一下这个分界位置就好了.
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;
char s[MAXN];
int sum1[MAXN],sum2[MAXN];
int main()
{
	int n=read();
	scanf("%s",s+1);
	int ans;
	for(int i=1;i<=n;++i)
	{
		if(s[i]=='.')
			++sum1[i];//white
		else
			++sum2[i];
		sum1[i]+=sum1[i-1];
		sum2[i]+=sum2[i-1];
	}
	ans=sum2[n];
	for(int i=1;i<=n;++i)
		ans=min(ans,i-sum1[i]+n-i-(sum2[n]-sum2[i-1]));
	cout<<ans<<endl;
	return 0;
}

D Three Colors

  • 两个颜色一起 $dp$ 状态数目可能很大,考虑能不能每次只 $dp$ 一种颜色.
  • 用所有染色方案 $3^n$ 减去不合法的方案数就好了.
  • 记所有数的和为 $sum$ ,那么不合法的方案有 $R\geq sum/2,G\geq sum/2,B\geq sum/2$ 三种.
  • 记 $f(i,j)$ 表示前 $i$ 个数,红色数之和为 $j$ 的方案数.另外两种颜色计算方法一样,直接 $\times 3$ .
  • 注意若 $sum$ 为偶数,这里有两个颜色都恰好等于 $sum/2$ 的方案被减了两次,要加回来,这部分是 $g(n,sum/2)\cdot {3\choose 2}$ .
  • $f$ 转移时可以填三种颜色,而 $g$ 只能填两种.
  • 时间复杂度为 $O(n\cdot sum)$ ,实际肯定跑不满.空间可以滚动优化一下(其实 $f,g$ 用一个数组也就 $100\ MB$).
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
#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;
}
void upd(int &x,int y)
{
	x+=y;
	x=(x%P+P)%P;
}
const int MAXN=329;
int a[MAXN],sum[MAXN],n;
int ans=0;
int f[2][MAXN*MAXN],g[2][MAXN*MAXN];
int main()
{
	n=read();
	for(int i=1; i<=n; ++i)
		sum[i]=sum[i-1]+(a[i]=read());
	ans=fpow(3,n);
	int cur=0;
	g[cur][0]=f[cur][0]=1;
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<=sum[i];++j)
			f[cur^1][j]=g[cur^1][j]=0;
		for(int j=0;j<=sum[i-1];++j)
			if(f[cur][j])
			{
				upd(f[cur^1][j+a[i]],f[cur][j]);
				upd(f[cur^1][j],mul(2,f[cur][j]));
				upd(g[cur^1][j+a[i]],g[cur][j]);
				upd(g[cur^1][j],g[cur][j]);
			}
		cur^=1;
	}
	for(int i=(sum[n]+1)>>1;i<=sum[n];++i)
		upd(ans,-mul(3,f[cur][i]));
	if(!(sum[n]&1))
		upd(ans,mul(3,g[cur][sum[n]>>1]));
	cout<<ans<<endl;
	return 0;
}

E Polynomial Divisors

  • 比赛时一直 $WA$ 后面几个点.心态有些崩.后来改了些莫名其妙的地方就过了???
  • 结论:题述性质成立当且仅当这个多项式在模 $p$ 意义下能被 $x^p-x$ 整除.于是只需要验证 $[2,n]$ 以内的质数,再加上所有 $a_i$ 的 $gcd$ 的质因数就好了.
  • 证明:充分性显然.必要性:在模 $p$ 意义下, $0,1,\dots p-1$ 都是 $f$ 的根.
  • 那么这个多项式一定有因式 $x(x-1)(x-2)\dots (x-(p-1))$.
  • 这个因式的根与 $x^p-x$ 的根完全相同,而它们最高项系数也相同,在模 $p$ 意义下这两个式子是等价的.于是多项式 $f$ 就一定有因式 $x^p-x$ .
  • 这部分的证明好像在 $math$ 那个题里面有?

F Banned X

咕了.