2021-01-08 12:26 已编辑浙江省杭州学军中学 C++

关注

【题解】牛客练习赛75

广义肥波

方法1. 设
$\begin{aligned}F_n&=m^{f_n}\\&=m^{a\cdot f_{n-1}+b\cdot f_{n-2}}\\&=m^{a\cdot f_{n-1}}\cdot m^{b\cdot f_{n-2}}\\&=(m^{f_{n-1}})^a\cdot (m^{f_{n-2}})^b\\&=F_{n-1}^a\cdot F_{n-2}^b\end{aligned}$

快速幂处理即可。

//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. 根据费马小定理 $a^{p-1}\equiv 1\pmod p$ ，可以在模 $10^9+6$ 意义下直接计算出 $f_n$ ，并在模 $10^9+7$ 意义下直接计算出答案。此方法可以通过矩阵快速幂拓展到 $O(\log n+\log p)$ 的时间复杂度，但由于放在送分题位，故不作要求。

//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;
}

小 $\text D$ 和他的魔法石

对于 $k=\text 0$ 的情形，直接完全背包。
对于 $n=\text 2$ 的情形，交换后完全背包。
剩余情形，我们考虑完全背包的性质：如果物品 $\mathop A$ 的价值大于物品 $\mathop B$ ，且体积小于 $\mathop B$ ，那么 $\mathop A$ 可以替换 $\mathop B$ 。因此，我们只需要找出价值最大的物品和体积最小的物品进行交换，得到价值最大且体积最小的物品。

//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;
}

宝石街

我们设时间为 $\mathop t$ 时，到达的点为 $\mathop q$ 。则问题可以转化成：有容积为 $\mathop t$ 的背包，在点 $\mathop q$ 之前任意点 $\mathop i$ ，宝石可以转化为 $a_i$ 个价值为 $\text 1$ ，体积为 $\mathop q-i$ 的物品。显然，选择体积较小的物品可以获得最大的价值。因此，捡宝石时，从点q开始往前捡，直到不能再捡，作为起点。由于要枚举终点和起点，时间复杂度： $O(n^2)$ 。
优化方法 $\text 1.$ 找起点的过程可以采用二分查找。时间复杂度： $O(n\log n)$ 。
优化方法 $\text 2.$ 设终点的点为 $q,q+\text 1$ 时，起点分别为 $\mathop p,p'$ 。注意到 $p\le p'$ ，因此可以采用双指针优化。时间复杂度： $\mathop O(n)$ 。

//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;
}

减数游戏

由于 $\mathop k$ 是正数，又要结果尽量大，所以要使大的数尽量受到与 $\mathop k$ 相乘的影响。因此，我们采取尽量删去最小的两个数的做法。容易想到使用优先队列维护最小值，每次弹出最小的两个数 $\mathop a,b$ ，插入 $a\cdot b+k$ 。当 $a\cdot b+k$ 大于等于原序列中的最大值时，在此之后的每个 $a\cdot b+k$ ，都将成为序列的最大值，证明如下：
设序列中的数从小到大依次为 $[a,b,a',b',...,p](a\cdot b+k\ge p)$ 。进行一次操作后，序列变为 $[a',b',...,p,a\cdot b+k]$ 。显然， $a'\cdot b'+k\ge a\cdot b +k$ 。

由此，我们不再需要关心序列中数的相对大小，只要把新产生的数添加到有序序列的末尾，因此，可以边取模边操作，避免高精度运算。

//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;
}

炒鸡矿工

一.约定

令 $n=n+1,v_1=c,s_1=p$ ， $v_i$ 表示升到第 $\mathop i$ 级单次挖矿增加的重量， $w_i$ 表示升级到第 $\mathop i$ 级的代价， $s_i$ 表示第 $\mathop i$ 级单次挖矿的时间。预处理出 $v_i$ 的前缀和 $sv_i$ ，则 $sv_i$ 表示第i级单次挖矿的重量。

二.做法 $\mathop A$ $\big($ 时间复杂度： $O(tns_i)$ $\big)$

$f_{i,j,k}$ 表示总时间在第 $i(0\le i\le t)$ 分钟，等级为 $j(1\le j\le n)$ 级，单次挖矿剩余 $k(s_j>k\ge 0)$ 分钟时的最大金矿重量。以时间作为状态。下面拆分转移方程：
- 继承： $f_{i,j,k}=f_{i-1,j,(k+1)\bmod s_j}+sv_j\cdot[k=0]$ 。
- 升级： $f_{i,j,k}=\max\big\{f_{i,j,0},f_{i,j-1,0}-w_j|k=0,f_{i,j-1,k}\ge w_j\big\}$ 。

三.做法 $\mathop B$ $\big($ 时间复杂度： $O(tn)\big)$

优化掉第三维。 $f_{i,j}$ 表示总时间在第 $i(0\le i\le t)$ 分钟且单次挖矿剩余 $\text 0$ 分钟，等级为 $j(1\le j \le n)$ 级时的最大金矿重量。
下面来说明 $\max\big\{f_{t,j}(1\le j\le n)\big\}$ 一定为最优的答案。由于在一次挖矿结束时收矿，所以对于任意正整数 $\mathop k$ ，在同一时刻同一等级，单次挖矿剩余 $\mathop x$ 分钟时的最大金矿重量一定大于 $\mathop x+k$ 分钟。那么单次挖矿剩余 $\text 0$ 分钟一定是最优的。
“只能在一次挖矿开始前进行升级”，等价于可以在任何时间升级，但只能在下一次挖矿开始后体现升级效果。因此转移方程可以分解如下：
继承： $f_{i,j}=f_{i-1,j}(i\ge 1)$ 。
收矿： $f_{i,j}=f_{i-s_j,j}+sv_j(i\ge s_j)$ 。
升级： $f_{i,j}=f_{i,j-1}-w_j(f_{i,j-1}\ge w_j)$ 。

//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;
}

迷路の小 $\text L$

我们称沿着跑动的一条线段为一条边，称整个过程经过的所有边的有序集合为路径，称与墙相邻且自身为空地的点为有效点（简称“点”）并为有效点连有效边（简称“边”）。记点数为 $\mathop{tot}$ ，边数为 $num\big(O(tot)=O(num)=O(n+m+s)\big)$ 。显然接下来我们只需要考虑有效点。
结论 $\text{1. }$ 如果存在一条边，它的长度为 $\mathop l$ ，那么下一步必然存在长度大于等于 $\mathop l$ 的边（往回跑动）。
结论 $\text{2. }$ 由结论 $\text{1}$ ，答案路径上的最后一条边一定是所有边中最长的。反证：假如不是最长的，则路径前面存在一条更长的边 $\mathop B$ 。这条路径一定不优于在边 $\mathop B$ 来回跑动所构成的路径。
统称路径上所有最长的边为边 $\mathop A$ 。由此，我们只需要枚举最终到达的边 $\mathop A$ 上的点，路径由起点到边 $\mathop A$ 上的点（记此为 $\mathop a$ 部分），在边 $\mathop A$ 上来回跑动（记此为 $\mathop b$ 部分）两部分组成。
结论 $\text{3. }$ 在 $\mathop a$ 部分中，没有一条边会经过已经经过的点。因为绕一圈所用的步数用在 $\mathop b$ 部分显然更优。
结论 $\text{4. }$ 由结论 $\text{3}$ ， $\mathop a$ 部分最多由 $\mathop{tot}$ 条边组成。
由此，对于 $\mathop a$ 部分，我们只需要进行动态规划。设 $f_{i,j}$ 表示第 $\mathop i$ 步到达点 $\mathop j$ 的最长路径长度。 $f_{i,j}=\max\big\{f_{i-1,u}+dis_{u\to j}|u\to j\big\}$ 。对于b部分，处理出每个点 $\mathop i$ 所连出的最长边长度 $mx_i$ 。则答案为 $f_{tot,i}+(k-tot+1)\cdot mx_i$ 。
总时间复杂度： $O\big((n+m+s)^2+T(n+m+s)\big)$ 。常数巨大。

//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;
}