AtCoder Beginner Contest 246
D
题意
求一个\(x\geq n\) 使得\(x=a^3+a^2b+ab^2+b^3\)且\(n\leq10^{18}\)
思路
变形 \(x=(a+b)(a^2+b^2)\) ,那么a、b的范围在1e6
从大到小枚举每个a,那么每个符合情况的b的最小值一定单调不升
代码
int f(int x,int y)
{
return (x+y)*(x*x+y*y);
}
void solve()
{
// (a+b)(a^2+b^2)
//双指针
cin>>n;
m=1e6;
int r=1e6;
for(int i=0;i<=m;i++)
{
int k;
while(1)
{
k=f(i,r);
if(k>=n&&r>=0) ans=min(ans,k),r--;
else break;
}
}
cout<<ans<<endl;
}
E
思路
以为是简单的bfs,一直wa,明明都过了52个点了,后来看题解发现不对劲啊,一个点可能从两个方向走过来而且它们的步数是相等的。所以vis数组要开多一维
代码
bool vis[N][N][2];
void bfs()
{
queue<node> q;
memset(dis,-1,sizeof(dis));
q.push({sx,sy});
dis[sx][sy]=0;
while(q.size())
{
node tmp=q.front();
q.pop();
int x=tmp.x,y=tmp.y;
for(int i=0;i<4;i++)
{
int nx=x,ny=y;
while(1)
{
nx+=dx[i],ny+=dy[i];
if(!check(nx,ny)||s[nx][ny]=='#') break;
if(vis[nx][ny][i&1]) break;
vis[nx][ny][i&1]=1;
if(dis[nx][ny]==-1)
{
dis[nx][ny]=dis[x][y]+1;
q.push({nx,ny});
}
}
}
}
cout<<dis[tx][ty]<<"\n";
}
void solve()
{
cin>>n;
cin>>sx>>sy>>tx>>ty;
for(int i=0;i<n;i++) cin>>s[i];
sx--,sy--,tx--,ty--;
if((sx+sy)%2!=(tx+ty)%2) {cout<<"-1\n";return;}
bfs();
}