前面的碎碎念：
有点可惜没有AK呀，D题思想江化陷入到BFS的思路里出不来了，还是太菜QAQ。
题解部分：
A-胖胖的牛牛
搜索题的关键其实也是定义状态，在这我们定义一个V数组，V[x][y][d]表示到达(x,y)处方向是d的最小转弯次数，之后我们进行BFS并不断更新这个V数组就行了。
时间复杂度：O(n^2)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,y,h,d;
}Q[100005];
int r=0,f=0,flag=0,dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int main()
{
int i,j,k,n,x,y,h,d,X,Y,H,ans=1e9,V[105][105][4];
char R[105][105];
scanf("%d",&n);
memset(V,0x3f,sizeof(V));
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf(" %c",&R[i][j]);
if(R[i][j]!='A')continue;
for(k=0;k<4;k++)Q[r].x=i,Q[r].y=j,Q[r].h=0,Q[r++].d=k,V[i][j][k]=0;
}
while(r!=f)
{
x=Q[f].x,y=Q[f].y,h=Q[f].h,d=Q[f++].d;
if(R[x][y]=='B')flag=1,ans=min(ans,h);
for(i=0;i<4;i++)
{
X=x+dx[i],Y=y+dy[i],H=h+(i==d?0:1);
if(X<0||X>=n||Y<0||Y>=n||R[X][Y]=='x'||H>=V[X][Y][i])continue;
Q[r].h=V[X][Y][i]=H,Q[r].x=X,Q[r].y=Y,Q[r++].d=i;
}
}
if(!flag)ans=-1;
printf("%d\n",ans);
return 0;
}B-牛牛的零食
我们求出[1,a-1]区间能被8整除但是不能被那些数整除的数字个数，再求出[1,b]区间能被8整除但是不能被那些数整除的数字个数，用后者减去前者即可得到最终答案。
至于求取的方法，使用容斥定理即可，比如：求[1,n]区间能被8整除，但是不能被3和5整除的数字个数，那就是n/8-n/lcm(8,3)-n/lcm(8,5)+n/lcm(8,3,5)，显然这个过程我们可以用DFS实现。
时间复杂度：O(2^n)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{
return b?gcd(b,a%b):a;
}
int i,a,b,n,x[20],ans;
void DFS(int t,int L,long long s,bool flag)
{
if(L==n)
{
if(flag)ans-=t/s;
else ans+=t/s;
return;
}
DFS(t,L+1,s,flag);
DFS(t,L+1,s*x[L]/gcd(s,x[L]),flag^1);
}
int main()
{
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&x[i]);
scanf("%d%d",&a,&b);
ans=0,DFS(a-1,0,8,0),ans=-ans,DFS(b,0,8,0);
printf("%d\n",ans);
return 0;
}C-牛牛的最美味和最不美味的零食
很显然，维护区间最大值和最小值使用线段树即可，关键是如何处理一操作造成的数字左移。我们可以反着思考，对于某次操作给出的下标，可能需要右移才是原数组的真实下标。举个例子，原始序列为1 2 3 4 5，我们一开始对下标为2的地方进行一操作，那么序列变成了1 3 4 5。再次询问下标2，对应的数字应该是3。那么在原始序列上，因为2一开始进行过一操作，此时询问的下标2应该+1变成3，而真实下标3在原始序列对应的数字正就是3。
那么如何求取这个真实下标呢。我们对每次一操作给出的下标id，设其真实下标为x。那么有x=id+sum(x)，其中sum(x)为前缀和，求出这个x后我们就在x处置1，然后更新前缀和。这个前缀和可以由树状数组实现，而找x的过程可以二分实现。或者也可以用线段树维护区间和，然后树上二分找这个x，相比于二分+树状数组可以省去一个log的时间复杂度。此处我使用前者的写法。
时间复杂度：O(nlog(n)+m
log(n)
log(n))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int n=0,w=0;
char c=0;
while(!isdigit(c))w|=c=='-',c=getchar();
while (isdigit(c))n=(n<<3)+(n<<1)+(c^48),c=getchar();
return w?-n:n;
}
int ans1,ans2,n,S[1000005]={0},Max[4000005],Min[4000005];
int lowbit(int x)
{
return x&(-x);
}
void update(int i,int x)
{
while(i<=n)S[i]+=x,i+=lowbit(i);
}
int getsum(int i)
{
int s=0;
while(i)s+=S[i],i-=lowbit(i);
return s;
}
void build(int L,int R,int x)
{
if(L==R)
{
Max[x]=Min[x]=read();
return;
}
int M=(L+R)>>1;
build(L,M,2*x),build(M+1,R,2*x+1);
Max[x]=max(Max[2*x],Max[2*x+1]);
Min[x]=min(Min[2*x],Min[2*x+1]);
}
void update2(int L,int R,int l,int r,int x)
{
if(l<=L&&R<=r)
{
Max[x]=-2e9,Min[x]=2e9;
return;
}
int M=(L+R)>>1;
if(M>=l)update2(L,M,l,r,2*x);
if(M<r)update2(M+1,R,l,r,2*x+1);
Max[x]=max(Max[2*x],Max[2*x+1]);
Min[x]=min(Min[2*x],Min[2*x+1]);
}
void search(int L,int R,int l,int r,int x)
{
if(l<=L&&R<=r)
{
ans1=min(ans1,Min[x]),ans2=max(ans2,Max[x]);
return;
}
int M=(L+R)>>1;
if(M>=l)search(L,M,l,r,2*x);
if(M<r)search(M+1,R,l,r,2*x+1);
}
int find(int id)
{
int l=1,r=n,mid,ans=n;
while(l<=r)
{
mid=(l+r)>>1;
if(mid-getsum(mid)<id)l=mid+1;
else ans=mid,r=mid-1;
}
return ans;
}
int main()
{
int i,m,op,l,r,x;
n=read(),m=read();
build(1,n,1);
while(m--)
{
op=read();
if(op==1)
{
x=read(),x=find(x);
update2(1,n,x,x,1),update(x,1);
}
else
{
l=read(),r=read(),l=find(l),r=find(r);
ans1=1e9,ans2=-1e9,search(1,n,l,r,1);
printf("%d %d\n",ans1,ans2);
}
}
return 0;
}D-瘦了的牛牛去旅游
此处我们设DP[i][j][k]为从i到j，经过k条边的最短路径，设原始地图由R数组保存，那么我们可以通过弗洛伊德算法的思想递推求出这个DP数组，转移方程如下：
for(l=2;l<=n;l++)
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)DP[i][j][l]=min(DP[i][j][l],DP[i][k][l-1]+R[k][j]);求出这个DP数组后，我们设ans[i][j]为i到j的最小路径密度，很显然这个ans数组可以由DP数组求出。预处理出ans数组之后，对于每次询问，根据ans数组的值输出相应的解即可。
时间复杂度：O(n^4)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
int R[55][55],DP[55][55][55];
double ans[55][55];
int main()
{
int i,j,k,l,n,m,q;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=0;k<=n;k++)ans[i][j]=R[i][j]=DP[i][j][k]=1e9;
while(m--)
{
scanf("%d%d%d",&i,&j,&k);
R[i][j]=min(R[i][j],k),DP[i][j][1]=R[i][j];
}
for(i=1;i<=n;i++)DP[i][i][0]=0;
for(l=2;l<=n;l++)
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)DP[i][j][l]=min(DP[i][j][l],DP[i][k][l-1]+R[k][j]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
if(DP[i][j][k]<1e9)ans[i][j]=min(ans[i][j],1.0*DP[i][j][k]/k);
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&i,&j);
if(ans[i][j]<1e9)printf("%.3lf\n",ans[i][j]);
else printf("OMG!\n");
}
return 0;
}E-只能吃土豆的牛牛
这题我是找规律解的，建议去看其他正规解法...
和1组合能生成的数字是1，有1个；和3组合能生成的数字是3/3+1，有2个；和9组合能生成的数字是9/1+9/3+9/1+3+9，有4个，此处可以看出规律1，2，4，...，2^(n-1)。根据等比数列求和公式我们可以知道1+2+4+...+2^(n-1)=2^n-1。那么我们找到2^n-1>=k最小的那个n，然后从n遍历到1贪心地去取数字就行了。
时间复杂度：O(Tlog(k))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
long long fastpow(long long a,int b)
{
long long s=1;
for(;b;b>>=1,a=a*a)if(b&1)s*=a;
return s;
}
int main()
{
int i,x,c=0,T;
long long one=1,ans;
scanf("%d",&T);
while(T--)
{
scanf("%d",&x),ans=0;
for(i=1;(one<<i)-1<x;i++);
while(i--)if(x>=(one<<i))x-=(one<<i),ans+=fastpow(3,i);
printf("Case #%d: %lld\n",++c,ans);
}
return 0;
}完结撒花，若有疏漏之处，还望大佬轻喷。
京公网安备 11010502036488号