【超好懂的比赛题解】2021CCPC哈尔滨站个人题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了【超好懂的比赛题解】2021CCPC哈尔滨站个人题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

title : 2021CCPC哈尔滨站题解
date : 2022-10-4
tags : ACM,题解，练习记录
author : Linno

2021CCPC哈尔滨站题解

题目链接：https://codeforces.com/gym/103447

补题进度：7/12

B-Magical Subsequence

A的值很小，我们直接枚举两个数的和，然后遍历一遍看看能凑多少对，记录最长的答案即可。map应该会超时，建议用前缀和。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;

int n,a[N],sum[205][N];

signed main(){
	scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		for(int j=1;j<=100;++j) sum[j][i]=sum[j][i-1];
		++sum[a[i]][i];
	}
	for(int s=2;s<=200;++s){ //枚举和 
		int len=0,lst=0;
		for(int i=2;i<=n;++i){
			if(s-a[i]<0||s-a[i]>100) continue;
			if(sum[s-a[i]][i-1]-sum[s-a[i]][lst]){
				len+=2;
				lst=i;
			}
		}
		if(len>ans) ans=len;
	}
	printf("%d\n",ans);
	return 0;
}

C-Colorful Tree

滚回去重学DSU on Tree了。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;

int n,col[N],dp[N],fa[N];
vector<int>G[N];
multiset<int>st[N]; 

void dfs(int x){
	if(!G[x].size()){ //叶子结点，可以减少的次数为0 
		st[x].insert(col[x]);
		dp[x]=1; 
		return;
	}
	int mx=1;
	for(auto to:G[x]){
		if(to==fa[x]) continue;
		dfs(to); //算出儿子结点的答案 
		dp[x]+=dp[to]; //
		if(st[x].size()<st[to].size()) swap(st[to],st[x]);
		for(auto it:st[to]){  //小的集合向大的集合合并 
			st[x].insert(it);
			mx=max(mx,(int)st[x].count(it)); //记录出现最多的颜色次数 
		}
	}
	if(mx>1){  
		multiset<int>ss;
		for(auto it:st[x]){  //合并 
			if(!ss.count(it)&&st[x].count(it)==mx) ss.insert(it);
		}
		swap(st[x],ss);
	}
	//总和-儿子需要的颜色次数+这个结点染色可以减少maxn次染色
	dp[x]=dp[x]-G[x].size()+mx; 
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=2,x;i<=n;++i){ //建树 
		cin>>fa[x];
		G[fa[x]].emplace_back(i);
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		cin>>col[i]; 
		if(col[i]) ++ans; 
	}
	dfs(1);
	cout<<ans-dp[1]+1; //总数-可以减少的+第一个节点染色 
	return 0;
}

D-Math master

显然我们可以用 $O(2^k)$ 去枚举k位数p的约分结果a，那么通过等式 $\frac{p}{q}=\frac{a}{b}$ 能够求出b，只需要用 $O (k)$ 去检查b是否可行即可，可行的条件是a删去的数集刚好是b删去的数集，且其他数跟q一样。其他的特判大概就是当 $a == 0$ 以及 $a*q\%p!=0$ 。

#include<bits/stdc++.h>
#define int __int128
using namespace std;

int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){if(x>9) write(x/10ll);putchar(x%10+'0');}

int n,p,q,vis[10],tmp[10],lenq,lenp,ans1,ans2;
char sp[25],sq[25];

inline int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

bool check(int x){
	for(int i=lenq-1;i>=0;--i){
		if(sq[i]-'0'==x%10){
			x/=10;
			continue;
		}
		++tmp[sq[i]-'0'];
	}
	if(x) return 0;
	for(int i=0;i<=9;++i) if(tmp[i]!=vis[i]) return 0;
	return 1;
}

signed main(){
	n=read();
	for(int i=1;i<=n;++i){
		p=0;q=0;
		scanf("%s%s",sp,sq);
		lenp=strlen(sp),lenq=strlen(sq);
		for(int i=0;i<lenp;++i) p=p*10ll+(sp[i]-'0');
		for(int i=0;i<lenq;++i) q=q*10ll+(sq[i]-'0');
		ans1=p;ans2=q;
		for(int i=0;i<(1<<(lenp));++i){
			int a=0,b;
			for(int j=0;j<=9;++j) vis[j]=0,tmp[j]=0;
			for(int j=0;j<lenp;++j){
				if((i>>j)&1) a=a*10ll+(sp[j]-'0'); 
				else vis[sp[j]-'0']++;  //记录删去的数 
			}
			if(!a||a*q%p) continue;
			b=a*q/p;
			if(check(b)){
				ans1=min(ans1,a);
				ans2=min(ans2,b);
			}
		}
		write(ans1);putchar(' ');
		write(ans2);putchar('\n');
	}
	return 0;
}

E-Power and Modulo

显然当第一次 $A_i \neq 2^{i-1} \mod M$ 时，M就已经确定了，而这个时候2的幂次显然是不会大于 $2 e 9$ 的，这个时候再对前面和后面的数取模代入等式检查就可以了。（简而言之暴力）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;

int t,n,a[N];

void solve(){
	cin>>n;
	int no=0,ans=0;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1,st=1;i<=n;++i){
		if(ans){
			if(a[i]==st%ans){
				st=st*2ll%ans;
				continue;
			}else{
				no=1;
				break;
			}
		}else{
			if(a[i]==st){st=st*2ll;continue;}
			else{
				ans=(st-a[i]);
				if(ans<=0){
					no=1;
					break;
				}
				for(int j=1;j<i;++j) if(a[j]!=(1ll<<(j-1))%ans) no=1;
				if(no)	break;
				st=st*2ll%ans;
			}
		}
	}
	if(no||!ans) cout<<"-1\n";
	else cout<<ans<<"\n";
} 

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

G-Damaged Bicycle

首先我们可以预处理出k+1个关键点（包括1）开始的最短路。这个数据范围可以想到状压， $d p [s t] [x]$ 表示从第 $x$ 个关键点出发，经过的关键点集合为 $s t$ 时的最短期望到达时间，对于每一个 $< s t, x >$ ，策略都是固定的，所以可以记忆化搜索。从当前集合出发，我们很容易得到这个点不经过其他关键点时到达终点的期望时间（就是算一下拿到车和拿不到时去n号点要多久），而且对于从他出发到达任意一个关键点(仅当这个点的车坏掉)的时间是 $p [x] * (1.0 * d i s [x] [a [i]] / t$ ，最后一部分加上那个关键点的到终点的最小期望时间即可（即转移到 $d p [s t ∣ (1 << (p - 1))] [p]$ ）。

#include<bits/stdc++.h>
#define mk make_pair
#define pii pair<int,int>
#define S second
#define F first
#define inf 0x3f3f3f3f
#define int long long 
using namespace std;
const int N=1e5+7;

struct E{
	int v,w,nxt;
}e[N<<2];

int head[N],cnt=0;
inline void addedge(int u,int v,int w){
	e[++cnt]=(E){v,w,head[u]};head[u]=cnt;
}

int n,m,k,a[20];
double t,r,p[20],dp[1<<20][20];
int dis[20][N],vis[N];

void dij(int s,int id){
	for(int i=1;i<=n;++i) dis[id][i]=inf,vis[i]=0;
	dis[id][s]=0;
	priority_queue<pii>q;
	q.emplace(mk(0,s));
	while(q.size()){
		int fro=q.top().S;
		q.pop();
		if(vis[fro]) continue;
		vis[fro]=1;
		for(int i=head[fro];i;i=e[i].nxt){
			int to=e[i].v,w=e[i].w;
			if(dis[id][to]>dis[id][fro]+w){
				dis[id][to]=dis[id][fro]+w;
				q.emplace(mk(-dis[id][to],to));
			}
		}
	}
}

double dfs(int st,int x){ //得到从p[x]点出发且好的单车集合为st时的期望时间 
	if(dp[st][x]) return dp[st][x]; //记忆化 
	double res=1.0*p[x]*dis[x][n]/t+(1.0-p[x])*dis[x][n]/r;
	for(int i=1;i<=k;++i){  //该点单车坏掉，选一个未走过的点，从其期望最短时间转移 
		if(st&(1ll<<(i-1))) continue;
		res=min(res,1.0*(1-p[x])*dis[x][n]/r+p[x]*(1.0*dis[x][a[i]]/t+dfs(st|(1<<(i-1)),i)));
	}
	return dp[st][x]=res;
}

signed main(){
	scanf("%lf%lf",&t,&r);
	scanf("%lld%lld",&n,&m);
	for(int i=1,u,v,w;i<=m;++i){
		scanf("%lld%lld%lld",&u,&v,&w);
		addedge(u,v,w);
		addedge(v,u,w);
	}
	scanf("%lld",&k);
	for(int i=1;i<=k;++i){
		scanf("%lld%lf",&a[i],&p[i]);
		p[i]/=100.0;
	}
	a[0]=1;p[0]=1.0;
	for(int i=0;i<=k;++i) dij(a[i],i); //求k+1次最短路 
	if(dis[0][n]>=inf){ //-1的情况是不存在联通 
		printf("-1\n");
		return 0;
	}
	printf("%.10lf\n",dfs(0,0)); //开始状压dp 
	return 0;
}

I-Power and Zero

想象一下二进制下第i位的1可以看作是2个第i-1位的1，因此我们肯定是可以重新分配每一个二进制数1的个数使得 $c n t [i] <= c n t [i - 1]$ 的，最终我们可以得到一个阶梯型的序列，就能直观地算出答案是尽量取1。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;

int t,n,a[N],cnt[55];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=0;i<=40;++i) cnt[i]=0;
		for(int i=1;i<=n;++i){
			cin>>a[i];
			for(int j=0;j<=40;++j){
				if(a[i]&(1ll<<j)){
					++cnt[j];
				}
			}
		}
		while(1){
			int flag=1;
			for(int i=40;i>=1;--i){
				if(cnt[i]>cnt[i-1]){ 
					flag=0;
					int tmp=(cnt[i]*2+cnt[i-1])/3; //分成1:2需要的操作数 
					cnt[i-1]+=(cnt[i]-tmp)*2;
					cnt[i]=tmp;
				}
			}
			if(flag) break; 
		}
		cout<<cnt[0]<<"\n";
	}
	return 0;
}

J-Local Minimum

模拟签到题。会英文直接做就行。文章来源地址https://www.toymoban.com/news/detail-401002.html

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+7;

int n,m,mp[1005][1005],minx[1005],miny[1005],ans=0;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	memset(minx,0x3f,sizeof minx);
	memset(miny,0x3f,sizeof miny);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>mp[i][j];
			if(mp[i][j]<minx[i]) minx[i]=mp[i][j];
			if(mp[i][j]<miny[j]) miny[j]=mp[i][j];
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
		//	cout<<i<<" "<<j<<" "<<minx[i]<<" "<<miny[j]<<"!!\n";
			if(mp[i][j]==minx[i]&&mp[i][j]==miny[j]) ++ans;
		} 
	}
	cout<<ans<<"\n";
	return 0;
}