[数据结构与算法]Codeforces Round #774 (Div. 2)

比赛链接

C - Factorials and Powers of Two

题意 : 对于一个数$n$ , 判断$n$能否转换成$n=2^{k_1}+2^{k_2}+...+2^{k_x}+a!+b!+...c!$ , 也就是转换成$2$的次方加上一些数阶乘的和

题解 :

• 因为$15!=1,307,674,368,000$ , 所以考虑$n$的范围只可能是这$15$个数的组合 , 所以也就是使用状态压缩来做 , 比赛的时候用的是$01$背包 , 加上vector和map来保证只选一次
• 又因为任意一个数都可以转换成二进制 , 所以一个数二进制有多少个$1$那么使用的$2$的次方就有多少个 , 然后我们将$n$减去阶乘的组合 , 再看看这个数有多少个$1$ , 答案就是多少个$1$+组合成这个阶乘所需要数字的个数
• 还要考虑$1!=2^0$ , $2!=2^1$,所以阶乘从第三个开始

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#define int long long
#define maxn
using namespace std;
int T,jie[100],n,ans;
vector<int> v;
map<int,int> dp;
int get1(int num){
	int temp,cnt=0;
	while(num!=0){
		temp=num%2;
		num=num/2;
		if(temp==1) cnt++;
	}
	return cnt;
}
signed main(){
	jie[1]=1;
	for(int i=2;i<=15;i++) jie[i]=jie[i-1]*i;
	v.push_back(0);
	for(int i=3;i<=15;i++){
		int temp=v.size();
		for(int j=0;j<temp;j++){
			if(dp[v[j]+jie[i]]==0) dp[v[j]+jie[i]]=dp[v[j]]+1;
			else dp[v[j]+jie[i]]=min(dp[v[j]+jie[i]],dp[v[j]]+1);
			v.push_back(v[j]+jie[i]); 
		}
	}
	sort(v.begin(),v.end());
	scanf("%lld",&T);
	wxhile(T--){
		scanf("%lld",&n);
		ans=get1(n);
		for(int i=0;i<=v.size();i++){
			if(n-v[i]<0) break;
			ans=min(ans,get1(n-v[i])+dp[v[i]]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

D - Weight the Tree

题意 : 给定一个树 , 让我们对树的节点进行赋值 , 如果一个节点的值等于它所连接的所有节点的值的总和 , 那么这个节点是一个好节点 , 现在求让好节点的个数最大化的同时让所有的节点的值最小化

题解 :

• 最小化 , 所以不是好节点的值就为$1$ , 是好节点的值就为它所连接的节点的个数

• 能看出来这个是一个最小点覆盖问题 , 或者说成最大独立集

• 设$dp[i][0]$表示$i$节点不是好节点 , $dp[i][1]$是好节点 , $cnt$表示这个点的子树及自己好节点的个数 , $sum$就表示这个节点及其子节点的总和为多少

  $$\begin{gathered} dp[u][1].cnt+=dp[v][0].cnt \\ dp[u][1].sum+=dp[v][0].sum \\ dp[u][0].cnt+=temp.cnt \\ dp[u][0].sum+=temp.sum \end{gathered}$$

• 其中$temp$是从子节点的哪一个转移 , 要个数最大化值最小化

#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 300000
using namespace std;
int n,cnt[maxn],k,head[maxn],val[maxn];
struct node{
	int to,next;
}edge[maxn<<1];
void add(int u,int v){
	edge[++k]=(node) {v,head[u]}; head[u]=k; cnt[u]++;
	edge[++k]=(node) {u,head[v]}; head[v]=k; cnt[v]++;
}
struct Node{
	int cnt,sum;
	friend bool operator == (Node a,Node b){
		if(a.cnt==b.cnt && a.sum==b.sum) return true;
		return false;
	}
}dp[maxn][2];
Node getmax(Node a,Node b){
	if(a.cnt>b.cnt) return a;
	if(a.cnt==b.cnt && a.sum<b.sum) return a;
	return b;
}
void dfs(int u,int fa){
	dp[u][0]=(Node){0,1}; //不是好节点 
	dp[u][1]=(Node){1,cnt[u]}; //是好节点 
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v,u);
		dp[u][1].cnt+=dp[v][0].cnt;
		dp[u][1].sum+=dp[v][0].sum;
		Node temp=getmax(dp[v][0],dp[v][1]);
		dp[u][0].cnt+=temp.cnt;
		dp[u][0].sum+=temp.sum;
	}
}
void print(int u,int fa,bool flag){
	val[u]=flag?cnt[u]:1;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa) continue;
		print(v,u,flag?0:getmax(dp[v][0],dp[v][1])==dp[v][1]);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++) scanf("%d %d",&u,&v),add(u,v);
	if(n==2) printf("2 2\n1 1\n"),exit(0);
	dfs(1,1);
	Node temp=getmax(dp[1][0],dp[1][1]);
	print(1,1,temp==dp[1][1]);
	printf("%d %d\n",temp.cnt,temp.sum);
	for(int i=1;i<=n;i++) printf("%d ",val[i]);
	return 0;
}

E - Power Board

题意 : 求$i^j$不同的个数 , $i,j\in [1,10^6]$

题解 :

• 第一行全部都是$1$

• 从第二行开始 , 考虑怎么样才会重复 , 假设现在是$k$行 , 那么$k^m$行会因为第$k$行而重复 , 例如$2^4=4^2=8^1$ , 然后我们把这个$2$替换成一个符号$a^4=b^2=c...$

  for(int i=1;i<=n;i++)
  	for(int j=1;j*i<=n;j++)
  

  然后需要知道上面的这个循环的复杂度是比较小的 , 差不多$nlog$级别的

• 然后我们用类似于欧拉筛的方法来计算 , $a$的倍数全部都在$a$这个地方计算了 , 之后再到那个地方我们就不再进行计算了 , 代码中的预处理其实可以这样写 , 只是会超时超空间 , 可以先这样理解

  set<long long> st;
  for(int i=1;i<=20;i++){
  	for(int j=1;j<=m;j++) st.insert(i*j);
      s[i]=st.size();
  }
  

  也就是计算如果有$b$个$a$的倍数在$[1,n]$的范围内 , 答案是多少 , 又由于$2^{20}=1,048,576$ , 所以枚举$20$个就可以了

#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
int n,m,s[21],cnt;
bool book[20000001];
signed main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=20;i++){
		for(int j=1;j<=m;j++) cnt+=!book[i*j],book[i*j]=true;
		s[i]=cnt;
	}
	int ans=1;
	memset(book,0,sizeof book);
	for(int i=2;i<=n;i++){
		if(book[i]) continue;
		int c=0;
		for(int j=i;j<=n;j=j*i) book[j]=1,c++;
 		ans+=s[c];
	}
	printf("%lld\n",ans);
	return 0;
}