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();
}