CF1246

Posted on | Edited on | Views:

$Div.1$

A p-binary

考虑从小到大枚举答案 $k$ ,则需要满足
$$
n-k\cdot p=\sum_{i=1}^{k} 2^{b_i}
$$
其中每个 $b_i$ 表示选择了数字 $2^{b_i}+p$.

判断这个 $k$ 是否有解,只需要判断 $popcount(n-kp)\le k$ 是否成立.

若 $n-kp$ 二进制下的 $1$ 的个数比 $k$ 大,则这个 $k$ 无解.

否则,当 $n-kp$ 二进制下的 $1$ 的个数 $\le k$ 时,总可以把 $2^i$ 拆成 $2^{i-1}+2^{i-1}$ ,而凑够 $k$ 个数,即找到一组解.

当 $n\le kp$ 时,就可以退出了,若此时仍未找到解,则一定无解.

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
//%std
#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;
}
#define lowbit(x) x&(-x)
int popc(int x)
{
	int s=0;
	while(x)
		++s,x-=lowbit(x);
	return s;
}
int n,p;
int solve()
{
	for(int k=1;k<=31;++k)
		if(n-k*p>=k && popc(n-k*p)<=k)
			return k;
	return -1;
}
int main()
{
	n=read(),p=read();
	cout<<solve()<<endl;
	return 0;
}

B Power Products

把每个数质因数分解,得到
$$
x=\prod p_i^{b_i}
$$
这个指数 $b_i$ 可以对 $k$ 取模.

那么对于一个 $a_j$ 来说,找到的 $a_i$ 需要满足,对于每个质因子 $p_i$ ,两者的指数相加在模 $k$ 意义下为 $0$ .

用 $hash$ 去压缩每个数的每个质因子的次数.

在 CF 上写 hash 一定要写双进制模数啊.

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
//%std
#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,k;
typedef pair<int,int> pii;
#define mp make_pair
map<pii,int> cnt;
struct Hash
{
	int P,Base;
	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;
	}
	int pw[MAXN];
	void init(int p,int base)
	{
		P=p,Base=base;
		pw[0]=1;
		for(int i=1;i<=100000;++i)
			pw[i]=mul(pw[i-1],Base);
	}
	pii calc(int x) // (x,-x)
	{
		int a=0,b=0;
		for(int i=2;i*i<=x;++i)
			if(x%i==0)
			{
				int t=0;
				while(x%i==0)
					x/=i,++t;
				t%=k;
				a=add(a,mul(pw[i],t));
				t=(k-t)%k;
				b=add(b,mul(pw[i],t));
			}		
		if(x>1)
		{
			int t=1,i=x;
			a=add(a,mul(pw[i],t));
			t=(k-t)%k;
			b=add(b,mul(pw[i],t));
		}	
		return mp(a,b);
	}
}A,B;
int main()
{
	A.init(1e9+7,137);
	B.init(998244353,37);
	n=read(),k=read();
	ll ans=0;
	for(int i=1;i<=n;++i)
	{
		int x=read();
		pii upd,query;
		pii t=A.calc(x);
		upd.first=t.first,query.first=t.second;
		t=B.calc(x);
		upd.second=t.first,query.second=t.second;
		ans+=cnt[query];
		++cnt[upd];
	}
	cout<<ans<<endl;
	return 0;
}

C Rock Is Push

从那几张样例解释的 GIF 图中大概就能看出做法了.

每次进行 $dp$ 转移时考虑连续移动一段,直到改变移动方向.

设 $f(i,j,k=0/1)$ 表示从 $(1,1)$ 出发,走到 $(i,j)​$ ,且当前应该向 右/下 走的方案数.

由于每次移动之后都会切换方向,所以 一行/一列 只会被走一次,那么每次移动之间就不会互相影响了.

当 $k=0$ 时,往右边走,若 $(i,j+1)\sim (i,m)$ 这些位置共有 $x$ 个空位,那么往右最多可以走 $t$ 步.

当 $k=1$ 时,往下面走,若 $(i+1,j)\sim (n,j)$ 这些位置共有 $y$ 个空位,那么往下最多可以走 $t$ 步.

转移需要优化,如果直接上二维树状数组,时间复杂度是 $O(n^2\log^2 n)$ 的,不是很优.

可以利用前缀和的方式进行优化.

计算 $f(i,j,1)$ 时,考虑在 $f(i,j-1,1)$ 的基础上,减掉那些恰好只能到达 $j-1$ 这个位置的贡献,这可以用桶存起来.

如果合法,还需要加上 $f(i,j-1,0)$ 对 $f(i,j,1)$ 的贡献.

计算 $f(i,j,0)$ 同理.

时间复杂度 $O(n^2)$ .

特判 $n=m=1$ 的情况,否则因为根本上没有移动,导致 $f(1,1,0)$ 和 $f(1,1,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
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
//%std
#include<bits/stdc++.h>
#define endl '\n'
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=1e9+7;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
void inc(int &a,int b)
{
	a=add(a,b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
const int MAXN=2e3+10;
char buf[MAXN];
int n,m,Free[MAXN][MAXN];
int x[MAXN][MAXN],y[MAXN][MAXN],f[MAXN][MAXN][2];
void init()
{
	for(int i=1; i<=n; ++i)
	{
		scanf("%s",buf+1);
		for(int j=1; j<=m; ++j)
			Free[i][j]=(buf[j]=='.');
	}
	for(int i=1; i<=n; ++i)
	{
		int tmp=0;
		for(int j=m; j>=1; --j)
		{
			x[i][j]=tmp;
			tmp+=Free[i][j];
		}
	}
	for(int j=1; j<=m; ++j)
	{
		int tmp=0;
		for(int i=n; i>=1; --i)
		{
			y[i][j]=tmp;
			tmp+=Free[i][j];
		}
	}
}
int sum[2][MAXN][MAXN];
int solve()
{
	if(n==1 && m==1)
		return Free[n][m];
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=m; ++j)
		{
			if(i==1 && j==1)
				f[i][j][0]=f[i][j][1]=1;
			else
			{
				if(j==1)
					f[i][j][1]=0;
				else if(i==1)
					f[i][j][1]=(x[1][1]>=j-1);
				else
				{
					f[i][j][1]=f[i][j-1][1];
					inc(f[i][j][1],P-sum[1][i][j-1]);
					if(x[i][j-1]>=1)
						inc(f[i][j][1],f[i][j-1][0]);
				}
				if(i==1)
					f[i][j][0]=0;
				else if(j==1)
					f[i][j][0]=(y[1][1]>=i-1);
				else
				{
					f[i][j][0]=f[i-1][j][0];
					inc(f[i][j][0],P-sum[0][i-1][j]);
					if(y[i-1][j]>=1)
						inc(f[i][j][0],f[i-1][j][1]);
				}
			}
			if(y[i][j])
				inc(sum[0][i+y[i][j]][j],f[i][j][1]);
			if(x[i][j])
				inc(sum[1][i][j+x[i][j]],f[i][j][0]);
		}
	return add(f[n][m][0],f[n][m][1]);
}
int main()
{
	n=read(),m=read();
	init();
	cout<<solve()<<endl;
	return 0;
}

D Tree Factory

考虑倒着来实现这个过程,即从给出的树开始,不断操作,用最少的操作次数将它变成一条链.

若一个节点 $u$ 有 $v,w$ 两个儿子,则操作一次可以将子树 $v$ 接在子树 $w$ 下面.

不难发现,每次选择可操作的子树中,最大深度最大的那一颗,将它接在其他子树下面,会使最大深度 $+1​$ .

而当最大深度 $=n-1$ 时,就成了一条链了.

那么总操作次数一定是 $n-1-maxdep$ ,其中 $maxdep$ 表示初始时树中节点最大的深度.

对操作过程进行模拟即可.

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
//%std
#include<bits/stdc++.h>
#define endl '\n'
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;
vector<int> G[MAXN];
int n,dep[MAXN],fa[MAXN],mxson[MAXN];
vector<int> ans,op;
void dfs(int u)
{
	if(u)
	{
		int cnt=dep[ans.back()]-dep[fa[u]];
		while(cnt--)
			op.push_back(u);
	}
	ans.push_back(u);
	for(auto v:G[u])
		if(v^mxson[u])
			dfs(v);
	if(mxson[u])
		dfs(mxson[u]);
}
int main()
{
	n=read();
	for(int i=1;i<n;++i)
	{
		fa[i]=read();
		G[fa[i]].push_back(i);
		dep[i]=dep[fa[i]]+1;
	}
	int p=max_element(dep,dep+n)-dep;
	while(p)
	{
		mxson[fa[p]]=p;
		p=fa[p];
	}
	dfs(0);
	for(auto x:ans)
		printf("%d ",x);
	puts("");
	printf("%llu\n",op.size());
	for(auto x:op)
		printf("%d ",x);
	puts("");
	return 0;
}