2026年8月14日 day3题解
2026-08-14 20:38:26
发布于：广东
13阅读
0回复
0点赞
https://www.acgo.cn/problemset/info/137221?teamCode=2042058713337094144
T137221.新蚂蚁上岗
//全排列问题
#include<bits/stdc++.h>
using namespace std;
const int N=20+10;
#define ll long long
ll vis[N],val[N][N];
ll n;
ll ans=1e18;
void dfs(ll inx,ll cost){//第inx个选的位置
if(cost>ans)return ;//剪枝，提前结束掉没有必要的递推
if(inx>n){//当前选择位置超过n，停止并结束
ans=min(ans,cost);//求最小值
// for(int i=1;i<=n;i++)cout<<a[i]<<' ';cout<<endl;
return ;
}
//枚举当前位置的所有可能
for(int i=1;i<=n;i++){
if(vis[i])continue;//跳过前面选过的位置
// if(val[inx][i]==0)continue;//如果是 0，就表示这只蚂蚁不会做这项任务
vis[i]=1;//第inx个位置将i给选走
// a[inx]=i;//记录inx位置将i拿走
dfs(inx+1,cost+val[inx][i]);//下一个位置继续循环选择
vis[i]=0;//取消标记，将i放回，后面的可以进行选择
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>val[i][j];
if(val[i][j]==0)val[i][j]=1e18;
}
dfs(1,0);
cout<<ans<<endl;
}
https://www.acgo.cn/problemset/info/120022?teamCode=2042058713337094144
T120022.奶酪迷宫
#include<bits/stdc++.h>
using namespace std;
const int N=300+10;
#define ll long long
ll a[N][N],n,k,dp[N][N];//dp[i][j]存储坐标(i,j)的答案
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
ll dfs(ll x,ll y){
if(dp[x][y])return dp[x][y];//记忆化，直接返回计算过的结果
dp[x][y]=a[x][y];
for(int i=0;i<4;i++){
for(int len=1;len<=k;len++){
int nx=x+dx[i]*len;
int ny=y+dy[i]*len;
if(1>nx||1>ny||n<nx||n<ny)continue;
if(a[nx][ny]<=a[x][y])continue;//它只能移动到奶酪数量严格更多的格子
dp[x][y]=max(dp[x][y],dfs(nx,ny)+a[x][y]);
}
}
return dp[x][y];
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
cout<<dfs(1,1)<<endl;
}
https://www.acgo.cn/problemset/info/120237?teamCode=2042058713337094144
T120237.比尔吉沃特的潮汐
#include<bits/stdc++.h>
using namespace std;
const int N=500+10;
#define ll long long
int sx,sy,tx,ty;
int n,m;
int vis[N][N],a[N][N];
struct Node{
ll x,y;
};
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool check_1(ll x, ll y) {
return ( x >= 1 && y >= 1 && x <= n && y <= m );
}
bool check(ll limit){//海平面为limit的时候s是否能够到达tr
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
vis[i][j]=0;//清空初始vis标记
}
queue<Node>que;
que.push({sx,sy});
vis[sx][sy]=1;
while(que.size()){
auto cur=que.front();que.pop();
if(cur.x==tx&&cur.y==ty)return true;
for(int i=0;i<4;i++){
int x=cur.x+dx[i];
int y=cur.y+dy[i];
if(!check_1(x,y))continue;//跳过越界的点
if(vis[x][y])continue;//跳过访问过的点
if(a[x][y]<=limit)continue;
vis[x][y]=1;
que.push({x,y});
}
}
return false;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
cin>>sx>>sy>>tx>>ty;
ll l=0,r=1e6,ans;
while(l<=r){
ll mid=(l+r)/2;
// cout<<l<<' '<<r<<' '<<check(mid)<<endl;
if(check(mid)){
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
cout<<ans<<endl;
}
https://www.acgo.cn/problemset/info/120238?teamCode=2042058713337094144
T120238.皮尔特沃夫的信号
#include<bits/stdc++.h>
using namespace std;
const int N=1000+10;
#define ll long long
int sx,sy,tx,ty;
int n,m;
ll vis[N][N];
char a[N][N];
struct Node{
ll x,y;
};
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool check_1(ll x, ll y) {
return ( x >= 1 && y >= 1 && x <= n && y <= m );
}
int main(){
cin>>n>>m;
queue<Node>que;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='*'){
que.push({i,j});
vis[i][j]=1;
}
}
ll ans=0;
while(que.size()){
auto cur=que.front();que.pop();
ans=max(ans,vis[cur.x][cur.y]);
for(int i=0;i<4;i++){
int nx=cur.x+dx[i];
int ny=cur.y+dy[i];
if(!check_1(nx,ny))continue;
if(vis[nx][ny])continue;
if(a[nx][ny]=='#')continue;
vis[nx][ny]=vis[cur.x][cur.y]+1;
que.push({nx,ny});
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(a[i][j]=='.'&&!vis[i][j]){
cout<<-1<<endl;;
return 0;
}
}
cout<<ans-1<<endl;
}
这里空空如也
有帮助，赞一个