首页 > 其他分享 >AtCoder Beginner Contest 246

AtCoder Beginner Contest 246

时间:2023-03-22 20:57:16浏览次数:51  
标签:AtCoder sy sx Beginner Contest int -- 246 1e6

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

F

G

标签:AtCoder,sy,sx,Beginner,Contest,int,--,246,1e6
From: https://www.cnblogs.com/LIang2003/p/17245383.html

相关文章

  • AtCoder Beginner Contest 141
    AtCoderBeginnerContest141D-PowerfulDiscountTickets贪心+堆#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=1e5+5;......
  • [AtCoder] B - Counting Grids
      Thekeyobservationisthatthereisalwaysatmost1cellthatviolatesbothconditions. Proof: ifxviolatesbothconditions,thatmeansallothe......
  • AtCoder Beginner Contest 294
    题解报告基本的一些理解和问题都在注释中A:Filter//水题#include<cstdio>#include<algorithm>#include<cstring>#include<iostream>usingnamespacestd;intm......
  • [??记录] AtCoder 练习
    3.19arc066_c(dp,观察)观察:只会在负号右边添加\((/)\)两个位置之间至多一个括号。括号不会嵌套多层。\(f[i][j]\)表示处理完\(i\)个数,有\(j\)个未匹配左括号......
  • macOS 13.3 Beta 4 (22E5246b)With OpenCore 0.9.1开发版 and winPE双引导分区原版镜像
    镜像特点完全由黑果魏叔官方制作,针对各种机型进行默认配置,让黑苹果安装不再困难。系统镜像设置为双引导分区,全面去除clover引导分区(如有需要,可以自行直接替换opencore分区文......
  • AtCoder Beginner Contest 294
    A-Filter(abc294a)题目大意给定一个数组,不改变原顺序,输出是偶数的数。解题思路模拟即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL......
  • AtCoder Beginner Contest 293
    A-SwapOddandEven#include<bits/stdc++.h>usingnamespacestd;int32_tmain(){ strings; cin>>s; for(inti=0;i+1<s.size();i+=2) swap(......
  • AtCoder Beginner Contest 293
    上周因为GDKOI咕咕咕了A-SwapOddandEven(abc293a)题目大意给定一个字符串,交换每两个相邻字母,输出结果。解题思路模拟即可。神奇的代码#include<bits/std......
  • AtCoder Beginner Contest 293(C,D ,E,F)
    AtCoderBeginnerContest293(C,D,E,F)CC这道题其实还蛮好写的,就是一个\(dfs\),然后我看错了题意,就记录一下这道题的大意是我们需要从\((1,1)\)走到\((n,m)\),我们只......
  • [AtCoder Beginner Contest 281][G. Farthest City]
    和CF1657E的做法十分相似题目链接:G-FarthestCity题目大意:问有多少个\(n(3\len\le500)\)个点的无向连通图满足,若设\(1\)到\(i\)的最短路距离为\(dis_i\),则......