竞赛讨论区 > 【题解】牛客练习赛75
头像
Dragon_in_Bed
编辑于 2021-01-08 12:26
+ 关注

【题解】牛客练习赛75 精

广义肥波

方法1. 设

快速幂处理即可。 
//Coded by dst
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll p=1e9+7;
ll a,b,m,n,f[100005];
ll qpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)
			res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}
int main(){
	scanf("%lld%lld%lld%lld",&a,&b,&m,&n);
	f[1]=f[2]=m;
	for(int i=3;i<=n;i++)
		f[i]=qpow(f[i-1],a)*qpow(f[i-2],b)%p;
	printf("%lld\n",f[n]);
	return 0;
}
方法2. 根据费马小定理，可以在模意义下直接计算出f_n，并在模意义下直接计算出答案。此方法可以通过矩阵快速幂拓展到的时间复杂度，但由于放在送分题位，故不作要求。 
//Coded by dst
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int p=1e9+7;
int a,b,m,n,f[100005];
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1)
            res=(ll)res*a%p;
        a=(ll)a*a%p;
        b>>=1;
    }
    return res;
}
int main(){
    int i;
    cin>>a>>b>>m>>n;
    f[1]=1;
    f[2]=1;
    for(i=3;i<=n;i++)
        f[i]=((ll)f[i-1]*a+(ll)f[i-2]*b)%(p-1);
    cout<<qpow(m,f[n]);
    return 0;
}

小和他的魔法石

对于的情形，直接完全背包。
对于的情形，交换后完全背包。
剩余情形，我们考虑完全背包的性质：如果物品的价值大于物品， 且体积小于，那么可以替换。因此，我们只需要找出价值最大的物品和体积最小的物品进行交换，得到价值最大且体积最小的物品。
//Coded by dst
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int n,m,k,a[1005],b[1005],minA=1e9,maxB;
ll f[1005];
int main(){
	scanf("%d%d%d",&n,&m,&k);
	int i,j;
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<=n;i++)
		scanf("%d",&b[i]);
	if(k==0||n==2){
		if(k%2)
			swap(b[1],b[2]);
		for(i=1;i<=n;i++)
			for(j=a[i];j<=m;j++)
				f[j]=max(f[j-a[i]]+b[i],f[j]);
		printf("%lld\n",f[m]);
		return 0;
	}
	for(i=1;i<=n;i++){
		minA=min(minA,a[i]);
		maxB=max(maxB,b[i]);
	}
	printf("%lld\n",(ll)m/minA*maxB);
	return 0;
}

宝石街

我们设时间为时，到达的点为。则问题可以转化成：有容积为的背包，在点之前任意点，宝石可以转化为a_i个价值为，体积为的物品。显然，选择体积较小的物品可以获得最大的价值。因此，捡宝石时，从点q开始往前捡，直到不能再捡，作为起点。由于要枚举终点和起点，时间复杂度：。
优化方法 找起点的过程可以采用二分查找。时间复杂度：。
优化方法 设终点的点为时，起点分别为。注意到，因此可以采用双指针优化。时间复杂度：。
//Coded by dst
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int n,type;
ll t,ans,tmp,s[60000005],p,a1;
void get_s(){
	int i;
	ll x,y;
	s[1]=a1;
	for(i=2;i<=n;i++){
		x=a1^(a1<<13);
		y=x^(x>>17);
		s[i]=s[i-1]+(a1=(y^(y<<5))%p+1);
	}
}
int main(){
	int i,j;
	scanf("%d%lld%d",&n,&t,&type);
	if(type==1)
		for(i=1;i<=n;i++){
			scanf("%lld",&a1);
			s[i]=s[i-1]+a1;
		}
	else{
		scanf("%lld%lld",&a1,&p);
		get_s();
	}
	j=0;
	for(i=1;i<=n;i++){
		tmp+=s[i-1]-s[j];
		for(;tmp>t;j++)
			tmp-=(s[j+1]-s[j])*(i-j-1);
		ans=max(ans,s[i]-s[j]+(j?(t-tmp)/(i-j):0));
	}
	printf("%lld\n",ans);
	return 0;
}

减数游戏

由于是正数，又要结果尽量大，所以要使大的数尽量受到与相乘的影响。因此，我们采取尽量删去最小的两个数的做法。容易想到使用优先队列维护最小值，每次弹出最小的两个数，插入。当大于等于原序列中的最大值时，在此之后的每个，都将成为序列的最大值，证明如下：
设序列中的数从小到大依次为。进行一次操作后，序列变为。显然，。
由此，我们不再需要关心序列中数的相对大小，只要把新产生的数添加到有序序列的末尾，因此，可以边取模边操作，避免高精度运算。 
//Coded by dst
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
const ll p=1e9+7;
priority_queue<ll,vector<ll>,greater<ll> > pq;
queue<ll> q;
int n,k;
ll a[100005],s;
int main(){
	int i;
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	for(i=1;i<=n;i++)
		pq.push(a[i]);
	while(s<a[n]){
		s=pq.top();
		pq.pop();
		if(pq.empty())
			break;
		s=s*pq.top()+k;
		pq.pop();
		pq.push(s);
	}
	while(!pq.empty()){
		q.push(pq.top()%p);
		pq.pop();
	}
	if(!q.empty())
		while(1){
			s=q.front();
			q.pop();
			if(q.empty())
				break;
			s=(s*q.front()+k)%p;
			q.pop();
			q.push(s);
		}
	printf("%lld\n",s%p);
	return 0;
}

炒鸡矿工

一.约定

令，v_i表示升到第级单次挖矿增加的重量，w_i表示升级到第级的代价，s_i表示第级单次挖矿的时间。预处理出v_i的前缀和sv_i，则sv_i表示第i级单次挖矿的重量。

二.做法时间复杂度：O(tns_i)

表示总时间在第分钟，等级为级，单次挖矿剩余分钟时的最大金矿重量。以时间作为状态。下面拆分转移方程：
- 继承：。
- 升级：。

三.做法时间复杂度：

优化掉第三维。表示总时间在第分钟且单次挖矿剩余分钟，等级为级时的最大金矿重量。
下面来说明一定为最优的答案。由于在一次挖矿结束时收矿，所以对于任意正整数，在同一时刻同一等级，单次挖矿剩余分钟时的最大金矿重量一定大于分钟。那么单次挖矿剩余分钟一定是最优的。
“只能在一次挖矿开始前进行升级”，等价于可以在任何时间升级，但只能在下一次挖矿开始后体现升级效果。因此转移方程可以分解如下：
继承：。
收矿：。
升级：。
//Coded by dst
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
int n,m,t;
int w[7005],v[7005],s[7005];
ll f[7005][7005],sv[7005],g;
int main(){
	memset(f,-127/3,sizeof(f));
	int i,j;
	scanf("%d%d%d%d%d",&s[1],&v[1],&n,&m,&t);
	n++;
	for(i=2;i<=n;i++)
		scanf("%d",&w[i]);
	for(i=2;i<=n;i++)
		scanf("%d",&v[i]);
	for(i=2;i<=n;i++)
		scanf("%d",&s[i]);
	for(i=1;i<=n;i++)
		sv[i]=sv[i-1]+v[i];
	f[0][1]=m;
	for(i=0;i<=t;i++)
		for(j=1;j<=n;j++){
			if(i){
				f[i][j]=f[i-1][j];
				if(i>=s[j])
					f[i][j]=max(f[i][j],f[i-s[j]][j]+sv[j]);
			}
			if(f[i][j-1]>=w[j])
				f[i][j]=max(f[i][j],f[i][j-1]-w[j]);
		}
	for(j=1;j<=n;j++)
		g=max(g,f[t][j]);
	printf("%lld\n",g);
	return 0;
}

迷路の小

我们称沿着跑动的一条线段为一条边，称整个过程经过的所有边的有序集合为路径，称与墙相邻且自身为空地的点为有效点（简称“点”）并为有效点连有效边（简称“边”）。记点数为，边数为。显然接下来我们只需要考虑有效点。
结论如果存在一条边，它的长度为，那么下一步必然存在长度大于等于的边（往回跑动）。
结论由结论，答案路径上的最后一条边一定是所有边中最长的。反证：假如不是最长的，则路径前面存在一条更长的边。这条路径一定不优于在边来回跑动所构成的路径。
统称路径上所有最长的边为边。由此，我们只需要枚举最终到达的边上的点，路径由起点到边上的点（记此为部分），在边上来回跑动（记此为部分）两部分组成。
结论在部分中，没有一条边会经过已经经过的点。因为绕一圈所用的步数用在部分显然更优。
结论由结论，部分最多由条边组成。
由此，对于部分，我们只需要进行动态规划。设表示第步到达点的最长路径长度。。对于b部分，处理出每个点所连出的最长边长度mx_i。则答案为。
总时间复杂度：。常数巨大。
//Coded by dst
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
struct Edge{
	int to,nxt,dis;
}e[24005];
ll ans;
int n,m,k,T,p,q,num,tot,mx[8005],h[8005],f[8005][8005],d[1000005];
bool mp[1005][1005],col[1005][1005];
void add(int u,int v,int d){
	e[++num].to=v;
	e[num].nxt=h[u];
	e[num].dis=d;
	h[u]=num;
}
int st(int x,int y){
	return (x-1)*m+y;
}
int main(){
	int i,j,l,val,lst;
	memset(mp,1,sizeof(mp));
	scanf("%d%d%d%d%d%*d",&n,&m,&T,&p,&q);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++){
			scanf("%d",&val);
			mp[i][j]=val;
		}
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(i==p&&j==q||!mp[i][j]&&(mp[i][j+1]||mp[i][j-1]||mp[i-1][j]||mp[i+1][j])){
				d[st(i,j)]=++tot;
				col[i][j]=1;
			}
	for(i=1;i<=n;i++){
		lst=0;
		for(j=1;j<=m;j++){
			if(mp[i][j])
				lst=0;
			if(col[i][j]&&lst)
				add(d[st(i,j)],d[st(i,lst)],j-lst);
			if(col[i][j]&&mp[i][j-1])
				lst=j;
		}
	}
	for(i=1;i<=n;i++){
		lst=0;
		for(j=m;j;j--){
			if(mp[i][j])
				lst=0;
			if(col[i][j]&&lst)
				add(d[st(i,j)],d[st(i,lst)],lst-j);
			if(col[i][j]&&mp[i][j+1])
				lst=j;
		}
	}
	for(j=1;j<=m;j++){
		lst=0;
		for(i=1;i<=n;i++){
			if(mp[i][j])
				lst=0;
			if(col[i][j]&&lst)
				add(d[st(i,j)],d[st(lst,j)],i-lst);
			if(col[i][j]&&mp[i-1][j])
				lst=i;
		}
	}
	for(j=1;j<=m;j++){
		lst=0;
		for(i=n;i;i--){
			if(mp[i][j])
				lst=0;
			if(col[i][j]&&lst)
				add(d[st(i,j)],d[st(lst,j)],lst-i);
			if(col[i][j]&&mp[i+1][j])
				lst=i;
		}
	}
	for(i=1;i<=tot;i++)
		for(j=h[i];j;j=e[j].nxt)
			mx[i]=max(mx[i],e[j].dis);
	memset(f,-127/2,sizeof(f));
	f[0][d[st(p,q)]]=0;
	for(i=0;i<tot;i++)
		for(j=1;j<=tot;j++)
			for(l=h[j];l;l=e[l].nxt)
				f[i+1][e[l].to]=max(f[i+1][e[l].to],f[i][j]+e[l].dis);
	while(T--){
		scanf("%d",&k);++k;
		ans=0;
		for(i=1;i<=tot;i++){
			if(k<=tot)
				ans=max(ans,(ll)f[k][i]);
			else if(f[tot][i]>=0)
				ans=max(ans,f[tot][i]+(ll)mx[i]*(k-tot));
		}
		printf("%lld\n",ans+1);
	}
	return 0;
}
做个总结，题实在没想到的高精度能过，算是一个失误。题的一些数据的统计不合法，非常抱歉，不过好在只有一个人做出，对比赛结果没有影响。

最后，各位新年快乐！
2025最新求职资料大礼包领取
真题
历年笔试真题附答案
中国农业银行校招笔试真题-模拟卷1
饿了么24秋招工程方向&算法方向
搜狐畅游24届运营策划
全部 >
面经
面试常考问题整理
面试真题：经典海量数据处理题最详解析（下）
管理类双非硕的23秋招记录＆反思
Springboot全套注解解析《看不懂算我输》
全部 >
内推
员工内推码获取
帆软2025届校园招聘，欢迎来投
北京安卓开发工程师【急招】
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(7) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”