牛客月赛42题解【完结】

冰狱寒岚【简单】

https://ac.nowcoder.com/acm/contest/26561/A
就是打表即可，然后查询即可。

#include<bits/stdc++.h>
using namespace std;
int n,m,t;
vector<int>ve;
int main(void)
{ 
   
	for(int i=0;i<1024;i++) ve.push_back(i);
	for(int i=1024;i>0;i--) ve.push_back(-i);
	cin>>n;
	while(n--)
	{ 
   
		int x;  cin>>x;
		cout<<ve[x%2048]<<" ";
	}
	return 0;
}

光之屏障【简单】

https://ac.nowcoder.com/acm/contest/26561/B
打表，二分找答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
vector<LL>ve;
int main(void)
{ 
   
	int t; cin>>t;
	for(int i=0;i<=31;i++) ve.push_back(pow(2,i));
	while(t--)
	{ 
   
		LL a,b; cin>>a>>b;
		int l=lower_bound(ve.begin(),ve.end(),a)-ve.begin();
		int r=upper_bound(ve.begin(),ve.end(),b)-ve.begin();
		if(l>=r) puts("-1");
		else cout<<ve[l]<<endl;
	}
	return 0;
}

想复杂了，数据很小，其实直接模拟即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
vector<LL>ve;
int main(void)
{ 
   
	int t; cin>>t;
	while(t--)
	{ 
   
		LL a,b; cin>>a>>b;
		LL sum=1;
        while(sum<a) sum*=2;
		if(sum>=a&&sum<=b) cout<<sum<<endl;
		else cout<<-1<<endl;
	}
	return 0;
}

寒潭烟光【简单】

https://ac.nowcoder.com/acm/contest/26561/C
他这个是，前缀和数组的平均值，加一个x,总和加了(n+1)*x

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
int main(void)
{ 
   
	int t; cin>>t;
	while(t--)
	{ 
   
		LL n,f,x0; cin>>n>>f>>x0;
		LL sum=(n*(f+x0)+x0)/(n+1);
		cout<<sum<<endl;
	}
	return 0;
}

金蛇狂舞【bfs】

https://ac.nowcoder.com/acm/contest/26561/D
bfs即可，通过数据范围可以知道阶乘一般不会太大，因为太大显然是无意义的。

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=15;
LL f[N];
LL bfs(int x,int y)
{ 
   	
	unordered_map<LL,LL>mp; mp[x]=1;
	queue<pair<LL,LL>>q; q.push({ 
   x,0});
	while(q.size())
	{ 
   
		auto temp=q.front(); q.pop();
		int u=temp.first,step=temp.second;
		if(step>7) continue;
		if(u==y) return step;
		LL a[3]={ 
   0};
		a[1]=ceil(sqrt(u*1.0)),a[2]=floor(sqrt(u*1.0));
		if(u>15) a[0]=0;
		else a[0]=f[u];
		for(int i=0;i<3;i++)
		{ 
   
			if(!i&&u>=N) continue;
			if(!mp[a[i]]) 
			{ 
   
				q.push({ 
   a[i],step+1});
				mp[a[i]]++;
			}
		}
	}
	return -1;
}
int main(void)
{ 
   
	f[0]=1;
	for(int i=1;i<N;i++) f[i]=f[i-1]*i;
	LL t; cin>>t;
	while(t--)
	{ 
   
		LL x,y; cin>>x>>y;
		cout<<bfs(x,y)<<endl;
	}
	return 0;
}

暗灭侵蚀【模拟】

https://ac.nowcoder.com/acm/contest/26561/E

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
int main(void)
{ 
   
	LL t; cin>>t;
	while(t--)
	{ 
   
		LL a[3],n;
		priority_queue<LL>heap;
		for(int i=0;i<3;i++) cin>>a[i],heap.push(a[i]);
		cin>>n;
		int cnt=0;
		while(1)
		{ 
   
			for(int i=0;i<3;i++) a[i]=heap.top(),heap.pop();
			if(a[0]>=n) break;
			a[2]=a[0]*2-a[2];
			for(int i=0;i<3;i++) heap.push(a[i]);
			cnt++;
		}
		cout<<cnt<<endl;
	}
	return 0;
}

火凤燎原【思维】

https://ac.nowcoder.com/acm/contest/26561/F
就是，统计每个点的度，然后枚举每一个点计算其贡献。
根据题意可知，只有度大于等于3才是蒲公英。

#include<bits/stdc++.h> 
using namespace std;
typedef long long int LL;
const int N=1e5+10;
int d[N],t,n;
int main(void)
{ 
   
	cin>>t;
	while(t--)
	{ 
   
		cin>>n;
        for(int i=0;i<=n;i++) d[i]=0;
		for(int i=1;i<n;i++) 
		{ 
   
			int a,b; scanf("%d%d",&a,&b);
			d[a]++,d[b]++;
		}
		LL ans=0;
		for(int i=1;i<=n;i++)//枚举每一个点
			if(d[i]>=3) ans+=n-1-d[i];
		printf("%lld\n",ans);
	}
	return 0;
}

今天的文章牛客月赛42题解【完结】分享到此就结束了，感谢您的阅读。