瓷砖
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
const int N=110;
int n,m;
char a[N][N];
int step[N][N];
bool st[N][N];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int x,y;
int res;
void bfs(int x,int y)
{
queue<pii> q;
q.push({x,y});
st[x][y]=1;
while(q.size())
{
pii t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int u=t.x+dx[i],v=t.y+dy[i];
if(1<=u&&u<=n&&1<=v&&v<=m&&!st[u][v]&&a[u][v]=='.')
{
st[u][v]=1;
res++;
q.push({u,v});
}
}
}
}
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++) cin>>a[i]+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]=='@')
{
x=i,y=j;
break;
}
}
}
bfs(x,y);
cout<<res+1;
return 0;
}
chess
愤怒的牛
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10,INF=1e9;
int n,m;
int a[N];
bool check(int mid)
{
int last=-INF;
int res=0;
for(int i=1;i<=n;i++)
{
if(a[i]-last>=mid)
{
res++;
last=a[i];
}
}
return res>=m;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int l=0,r=1e9;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<r;
return 0;
}
循环比赛日程表
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n;
int a[N][N];
int main()
{
cin>>n;
a[1][1]=1;
int m=1<<n;
int p=1;
while(p<=m)
{
for(int i=1;i<=p;i++)
{
for(int j=1;j<=p;j++)
a[i][j+p]=a[i][j]+p;
}
for(int i=1;i<=p;i++)
{
for(int j=1;j<=p;j++)
{
a[i+p][j]=a[i][j+p];
a[i+p][j+p]=a[i][j];
}
}
p*=2;
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
砍伐树木
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,m;
int a[N];
bool check(int mid)
{
int res=0;
for(int i=1;i<=n;i++) res+=max(a[i]-mid,0ll);
return res>=m;
}
signed main()
{
cin>>n>>m;
int l=0,r=0;
for(int i=1;i<=n;i++) cin>>a[i],r=max(r,a[i]);
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<r;
return 0;
}
迷宫
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
const int N=1010;
int n,m;
int a[N][N];
int step[N][N];
bool st[N][N];
int dx[]={1,0,0,-1},dy[]={0,-1,1,0};
int x,y;
int res;
pii pre[N][N],res1[N];
int cnt;
void bfs(int x,int y)
{
queue<pii> q;
q.push({x,y});
st[x][y]=1;
step[x][y]=1;
while(q.size())
{
pii t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int u=t.x+dx[i],v=t.y+dy[i];
if(0<=u&&u<=4&&0<=v&&v<=4&&!st[u][v]&&a[u][v]==0)
{
st[u][v]=1;
pre[u][v]={t.x,t.y};
step[u][v]=step[t.x][t.y]+1;
q.push({u,v});
}
}
}
}
void dfs(int x,int y)
{
if(pre[x][y].x==-1) return;
dfs(pre[x][y].x,pre[x][y].y);
printf("(%d,%d)\n",x,y);
}
int main()
{
memset(pre,-1,sizeof pre);
for(int i=0;i<=4;i++)
{
for(int j=0;j<=4;j++)
{
cin>>a[i][j];
}
}
bfs(0,0);
printf("(0,0)\n");
dfs(4,4);
//cout<<step[4][4];
return 0;
}
猫和老鼠