完全平方數
都知道完全平方數的性質
\(n=sqrt(n)*sqrt(n) 且 sqrt(n)為整數\)
驗證一下\(sqrt(n)\)是不是整數即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int a,ans=-1e6-10;
int main(){
cin>>n;
while(n--){
cin>>a;
int k=sqrt(a);
if(k*k!=a && a>ans) ans=a;
}cout<<ans<<endl;
}
傳送陣
考的知識點：dfs
簡化題意，分兩種情況
- 連通，代價0
- 不連通，找能使兩點連通的最小價值
針對第二種情況
用染色的思想，從起點和終點都搜一遍，能到的點分別存起來，然后列舉起點能到的點和終點能到的點，算出最小價值
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
const int maxn=60;
int mp[maxn][maxn];
bool book[maxn][maxn];
int r1,r2,c1,c2;
bool flag=0;//是否能直接到達
int ans=0;
struct node{
int x,y;
}st1[maxn*maxn],st2[maxn*maxn];//st1存起點能到的點，st2存終點能到達的點
int top1=0,top2=0;
int nt[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
void dfs(int x,int y,int k,bool b){
mp[x][y]=k;
book[x][y]=1;
if(b==0){
st1[++top1].x=x;
st1[top1].y=y;
}
if(b==1){
st2[++top2].x=x;
st2[top2].y=y;
}
//能到達
if(x==r2 && y==c2 && b==0){
flag=1;return ;
}
if(x==r1 && y==c2 && b==1){
flag=1;return ;
}
for(int i=0;i<4;++i){
int nx=x+nt[i][0],ny=y+nt[i][1];
if(nx<1 || ny<1 || ny>n || nx>n) continue ;
if(book[nx][ny]==1) continue;
dfs(nx,ny,k+1,b);
}
}
int cal(int r1,int c1,int r2,int c2){//計算值
return (r1-r2)*(r1-r2)+(c1-c2)*(c1-c2);
}
int main(){
cin>>n;
cin>>r1>>c1>>r2>>c2;
memset(book,0,sizeof(book));
for(int i=1;i<=n;++i){
string s;
cin>>s;
for(int j=0;j<s.length();++j)
if(s[j]=='1') book[i][j+1]=1;
}
//深搜
dfs(r1,c1,0,0);
dfs(r2,c2,0,1);
if(flag==1){//能直接到達
cout<<"0"<<endl;
return 0;
}
//列舉找最小價值
int ans=1e9;
for(int i=1;i<=top1;++i)
for(int j=1;j<=top2;++j){
int a=st1[i].x,b=st1[i].y,m=st2[j].x,n=st2[j].y;
int val=cal(a,b,m,n);
if(val<ans) ans=val;
}
cout<<ans<<endl;
return 0;
}
最后一題鴿一鴿
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/343032.html
標籤：其他
上一篇：2021 CCPC女生賽