csp-s模拟65Simple，Walk， Travel题解

题面：https://www.cnblogs.com/Juve/articles/11639923.html

simple：

考试时只想到的暴力exgcd判断

考虑n，m互质的情况：

我们枚举y，对于方程$n*x+m*y \leq q$，$x\leq\frac{q-m*y}{n}$

其中y的范围是[0,n-1]，因为如果y大于n-1，那么可以使x的系数加一，会有重复

然后如果n，m不互质，那么设$n=n'*gcd(n,m),m=m'*gcd(n,m)$，所以$n'*gcd(n,m)*x+m'*gcd(n,m)*y \leq q$

其中把$gcd(n,m)*y$看成一个整体，那么枚举y的范围要保证$gcd(n,m)*y\in[0,n-1]$

然后就A了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define int long long
 6 using namespace std;
 7 const int MAXN=1e5+5;
 8 int t,n,m,q,ans;
 9 int gcd(int a,int b){
10     return b==0?a:gcd(b,a%b);
11 }
12 int max(int a,int b){return a>b?a:b;}
13 signed main(){
14     scanf("%lld",&t);
15     while(t--){
16         scanf("%lld%lld%lld",&n,&m,&q);
17         int g=gcd(n,m);
18         ans=0;
19         for(int i=0;i<(n/g);++i){
20             int x=q-i*m;
21             if(x<0) break;
22             ans+=x/n+1;
23         }
24         printf("%lld\n",q-(ans-1));
25     }
26     return 0;
27 }

View Code

walk：

枚举gcd，然后把边权是gcd倍数的边建出来，形成一个森林，求出森林的直径即是答案为gcd时的边的长度

注意一点，有些长度可能不会出现在最长链中，因为他是构成最长链的一部分，所以如果这个长度的答案<长度大于他的答案的话，就要将长度大于他的答案给他，从大到小枚举ans[i]=max(ans[i],ans[i+1]).

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=4e5+5;
const int MAXM=1e6+5;
int n,maxx=0,res[MAXN],len=0;
vector< pair<int,int> >e[MAXM];
int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],cnt=0;
void add(int u,int v){
	++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;
}
bool vis[MAXN];
int sta[MAXM],top=0;
int dfs(int x,int fa){
	vis[x]=1;
	int l=0,r=0;
	for(int i=pre[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa||vis[y]) continue;
		int p=dfs(y,x);
		if(p+1>l) r=l,l=p+1;
		else if(p+1>r) r=p+1;
	}
	len=max(len,l+r);
	return l;
}
int main(){
	scanf("%d",&n);
	for(int i=1,u,v,w;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		maxx=max(maxx,w);
		e[w].push_back(make_pair(u,v));
	}
	for(int i=1;i<=maxx;++i){
		cnt=0;
		for(int j=i;j<=maxx;j+=i){
			int N=e[j].size();
			for(int k=0;k<N;++k){
				int u=e[j][k].first,v=e[j][k].second;
				add(u,v),add(v,u);
				sta[++top]=u,sta[++top]=v;
			}
		}
		for(int j=1;j<=top;++j){
			if(!vis[sta[j]]){
				len=0;
				dfs(sta[j],0);
				res[len]=max(res[len],i);
			}
		}
		for(int j=1;j<=top;++j){
			pre[sta[j]]=vis[sta[j]]=0;
		}
		top=0;
	}
	for(int i=n-1;i>=1;--i) res[i]=max(res[i],res[i+1]);
	for(int i=1;i<=n;++i) printf("%d\n",res[i]);
	return 0;
}