D - Power Products

Description

给出一个长度为 $n$ 的序列和一不小于 2 的整数 $k$ ，要求找出数字对 $(i,j)$ 的数量，满足 $i\lt j$ 并且存在一个整数 $x$ 使得 $a_i\ast a_j = x^k$ 。

Solution

对于每个数字进行质因数分解，分解成 $x=p_1^{k_1}+p_2^{k_2}+\dots+p_m^{k_m}$ ，我们用一个存储若干个二元组，表示这个数字有个这个质因子，显然存储的时候这个次数可以对题中所给的取模。如果存在两个数字满足集合相同，并且对于所有，，则说明这两个数字相乘能得到。用维护即可。

Code

#include<bits/stdc++.h>

#define int long long

#define pii pair<int,int>

using namespace std;

const int maxn=1e5+5;

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

const int N=1e5;

int n,k;
int a[maxn];

int prime[maxn];
bool flag[maxn];

map<vector<pii>,int> hsh;

void build_prime(){
	memset(flag,true,sizeof(flag));
	flag[1]=false;
	for (int i=2;i<=N;i++){
		 (flag[i]) prime[++prime[]]=i;
		 ( j=;j<=prime[];j++){
			 (i*prime[j] > N) ;
			flag[i*prime[j]]=;
			 (i%prime[j]==) ;
		}
	}
}

{
	vector<pii> ret; ret.();
	 ( i=;i<=prime[];i++)  (x%prime[i]==){
		 cnt=;
		 (x%prime[i]==) cnt++,x/=prime[i];
		 (cnt%k) ret.((prime[i],cnt%k));
	}   (x==) ;
	 ret;
}

{
	vector<pii> ret=vec;
	 ( i=;i<ret.();i++) ret[i].second=k-ret[i].second;
	 ret;
}

 ans=;

{
	n=(); k=();
	 ( i=;i<=n;i++) a[i]=();

	();

	 ( i=;i<=n;i++){
		vector<pii> now=(a[i]);
		vector<pii> com=(now);
		ans+=hsh[com]; hsh[now]++;
	}

	(,ans);
	 ;
}

E - Rock Is Push

Description

你在一个 $n\ast m$ 的迷宫左上角 $1,1$ 位置，你要到达右下角 $n,m$ 的位置。每次你只能向右或者向下移动。
迷宫的一些格子里有石头。当你移动到有石头的格子时，石头就会按你移动的方向被推到下一个格子。如果下一个格子里有石头，它就会被推得更远，以此类推。迷宫被不可穿透的墙壁所包围，因此任何将你或任何石头移出迷宫的行为都是非法的。
求出起点到终点路径数量，对 $10^9+7$ 取模。。

一些很有趣的动图（样例解释）：

Solution

定义 $R(i,j)$ 和 $D(i,j)$ ，表示走到 $i,j$ ，下一次分别要向右/向下走，上一次和下一次走的方向不一样，走到终点的方案数。
则 $R (n, m) = D (n, m)$ 。

考虑到以这种定义走到 $i,j$ 的时候，右下角能到达的石头位置都没有改变过；所以 $i,j$ 的状态可以独立考虑，和经过的路径无关。

假设 $i,j$ 右边或者下面有 $k$ 个石头，则

$R(i,j)=\sum_{t=1}^{m-k-j} D(i,j+t)\\ D(i,j)=\sum_{t=1}^{n-k-i} R(i+t,j)$

然后前缀和优化即可。

Code

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=2005;
const int tt=1e9+7;

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

int n,m;
char a[maxn][maxn];
int rock[maxn][maxn];
int sum_r[maxn][maxn],sum_d[maxn][maxn];
int d[maxn][maxn],r[maxn][maxn];

int sd[maxn][maxn],sr[maxn][maxn]; // DP prefix sum

signed main(){
	n=read(); m=read();
	for (int i=1;i<=n;i++) scanf("%s",a[i]);

	 ( i=;i<=n;i++)
		 ( j=;j<=m;j++)
			rock[i][j]=a[i][j]==;

	 (n== && m==){(,-rock[][]); ;}

	 ( i=;i<=n;i++)
		 ( j=m;j>=;j--)
			sum_r[i][j]=sum_r[i][j]+rock[i][j];
	 ( j=;j<=m;j++)
		 ( i=n;i>=;i--)
			sum_d[i][j]=sum_d[i][j]+rock[i][j];

	 ( i=n;i>=;i--){
		 ( j=m;j>=;j--){
			
			
			d[i][j] = (sr[i][j] - sr[i+ (n-sum_d[i][j]-i) ][j] + tt)%tt;
			r[i][j] = (sd[i][j] - sd[i][j+ (m-sum_r[i][j]-j) ] + tt)%tt;
			 (i==n && j==m) d[i][j]=r[i][j]=-rock[i][j]; 
			 (i==n){d[i][j]=;  (sum_r[i][j]) r[i][j]=;}  
			 (j==m){r[i][j]=;  (sum_d[i][j]) d[i][j]=;}

			sr[i][j]=(sr[i][j]+r[i][j])%tt;
			sd[i][j]=(sd[i][j]+d[i][j])%tt;
		}
	}

	(,(d[][]+r[][])%tt);
	 ;
}

F - Tree Factory

Description

给出一棵树，节点编号为 $[0,n-1]$ ，0 为树根，节点 $x$ 父亲的标号 $p(x)$ 小于 $x$ 。
你需要构造一条链，赋予链上每个点 $[0, n - 1]$ 的标号，并且在对这个链进行次操作后，其形态和给出的树完全相同。所谓的“操作”如下：选定一个点，满足不是树根并且其父亲不是树根，把的父亲设置为。其它所有点的父亲不变。输出一种链上点的标号方案，然后输出操作次数和一种操作方案。操作次数不能大于的。保证有解。

$2\le n\le 10^5$ 。

Solution

考虑反着做，把给定的树变成一条链。如果每次操作都能使树的深度增加 1，那么我们最多只需要做 $n-1$ 次，满足答案的限制。那么考虑如何让每次操作都使深度加 1。
首先贪心地想，肯定选取树中从根节点出发的最长的一条路径作为链的基础，其他操作在剩余的点上完成。如果这条路径上所有节点都没有大于一个儿子，则已经做完了；否则找出一个有至少两个儿子的点 $x$ ，假设其一个在路径上的点是 $u$ ，另一个不在路径上的点是 $v$ ，我们另 $u$ 的父亲变成 $v$ ，就实现了深度增加。

具体实现，对最深的分叉点，把这个节点的所有儿子一个个合并。

参考 wxhtxdy 的代码……

Code

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

const int maxn=1e5+5;

int n,fa[maxn],deep[maxn];
int tot=0,lnk[maxn],nxt[maxn],to[maxn],son[maxn];

int opt[maxn],ans[maxn];

int heavy_son[maxn];

void add_edge(int x,int y){
	tot++; to[tot]=y; son[x]++;
	nxt[tot]=lnk[x]; lnk[x]=tot;
}

int cnt=0;

void DFS(int x){
	ans[++ans[0]]=x;
	for (int i=1;i<=cnt;i++) opt[++opt[]]=x;
	cnt=;
	 ( i=lnk[x];i;i=nxt[i])  (to[i]!=heavy_son[x]) (to[i]);
	 (heavy_son[x]) (heavy_son[x]);
	cnt++;
}

{
	n=();

	fa[]=; deep[]=;
	 ( i=;i<n;i++) fa[i]=(),(fa[i],i),deep[i]=deep[fa[i]];

	 max_deep=,k=;
	 ( i=;i<n;i++)  (deep[i]>max_deep) max_deep=deep[i],k=i;
	 (k!=){
		 (fa[k]!=) heavy_son[fa[k]]=k;
		k=fa[k];
	}

	();

	 ( i=;i<=ans[];i++) (,ans[i]); ();

	(,opt[]);
	 ( i=;i<=opt[];i++) (,opt[i]);
	();
	 ;
}

10/28/2019

Codeforces Round #596 Div2 题解

D - Power Products

Description

Solution

Code

E - Rock Is Push

Description

Solution

Code

F - Tree Factory

Description

Solution

Code

Post a New Comment