【题解】牛客练习赛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. 根据费马小定理
，可以在模
意义下直接计算出
，并在模
意义下直接计算出答案。此方法可以通过矩阵快速幂拓展到)
的时间复杂度，但由于放在送分题位，故不作要求。
//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;
} 宝石街
我们设时间为优化方法
优化方法
//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;
} 炒鸡矿工
一.约定
令 二.做法
时间复杂度：)
)
- 继承：
- 升级：
三.做法
时间复杂度：%5Cbig))
优化掉第三维。下面来说明
“只能在一次挖矿开始前进行升级”，等价于可以在任何时间升级，但只能在下一次挖矿开始后体现升级效果。因此转移方程可以分解如下：
继承：
收矿：
升级：
//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;
} 迷路の小
我们称沿着跑动的一条线段为一条边，称整个过程经过的所有边的有序集合为路径，称与墙相邻且自身为空地的点为有效点（简称“点”）并为有效点连有效边（简称“边”）。记点数为结论
结论
统称路径上所有最长的边为边
结论
结论
由此，对于
总时间复杂度：
//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;
} 做个总结， 最后，各位新年快乐！
投递华为等公司10个岗位