蓝桥杯国赛训练第一周

P1491 集合位置 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

主要在于 $A*$ 函数中估价函数,这里给出最好想也是我想出来的一种方法,也就是当黑白棋子各自都在对方的领域上,那么就可以考虑一种最小的消耗情况,也就是走一步顶两不,也就是黑白互换,那么此时所需要消耗的最小步数就是不符合棋子的最大值

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
char mp[10][10];
int dx[]={1,1,-1,-1,2,2,-2,-2},dy[]={2,-2,2,-2,1,-1,1,-1};
int opposite[8]={3,2,1,0,7,6,5,4};
int f(){
    int black=0,white=0;
    for(int i=1;i<=5;i++) if(mp[1][i]!='1') black++;
    for(int i=2;i<=5;i++) if(mp[2][i]!='1') black++;
    for(int i=4;i<=5;i++) if(mp[3][i]!='1') black++;
    if(mp[4][5]!='1') black++;
    if(mp[2][1]!='0') white++;
    for(int i=1;i<=2;i++) if(mp[3][i]!='0') white++;
    for(int i=1;i<=4;i++) if(mp[4][i]!='0') white++;
    for(int i=1;i<=5;i++) if(mp[5][i]!='0') white++;
    return max(black,white);
}
bool dfs(int now,int maxdep,int x,int y,int lst){
    int cnt=f();
    if(now+f()>maxdep) return false;
    if(!cnt) return true;
    for(int i=0;i<8;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx<1||xx>5||yy<1||yy>5||opposite[i]==lst) continue;
        mp[x][y]=mp[xx][yy],mp[xx][yy]='*';
        if(dfs(now+1,maxdep,xx,yy,i)) return true;
        mp[xx][yy]=mp[x][y],mp[x][y]='*';
    }
    return false;
}
void solve(){
    int x,y;
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++){
            cin>>mp[i][j];
            if(mp[i][j]=='*') x=i,y=j;
        }
    int dep=0;
    while(dep<=15&&!dfs(0,dep,x,y,-1)) ++dep;
    cout<<(dep<=15?dep:-1)<<'\n';
}
signed main(){
   std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)solve();
}

P1491 集合位置 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意明了,也就是求出非严格的次短路即可,那么我们首先跑一遍最短路并储存最短路径

考虑一条最短路径上的边,可以肯定的是若最短路径中的一条边消失,其它边对终点的贡献仍然是最小的,所以说我们只需要删除一个最短路径上的边然后继续跑最短路就可以了

正确性: 对于一个最短路径,图中其它路径必然不存在更优的路径,若删去最短路径的一条边之后,最短路径一定会改变,此时再次求一遍最短路径,那么这个路径一定不劣于其他路径,且一定不优于不去除边的最短路径,故为次短路径

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
vector<pair<int,int>>point(N);
vector<pair<int,double>>g[N];
vector<int>pre(N);
vector<double>dijkstra(int n,int aa,int bb){
    vector<double>dist(n+1,1e9);
    vector<bool>vis(n+1,false);
    priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>>que;
    que.push({0,1}),dist[1]=0;
    while(!que.empty()){
        auto now=que.top(); que.pop();
        int x=now.second;
        double y=now.first;
        if(vis[x]) continue; vis[x]=true;
        for(auto u:g[x]){
            int v=u.first;
            double w=u.second;
            if((x==aa&&v==bb)||(x==bb&&v==aa)) continue;
            if(dist[v]>y+w){
                dist[v]=y+w,que.push({dist[v],v});
                if(aa==-1) pre[v]=x;
            }
        }
    }
    return dist;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,m,a,b; cin>>n>>m;
    cin>>a>>b;
    point[1]={a,b};
    for(int i=2;i<=n-1;i++){
        cin>>a>>b;
        point[i]={a,b};
    }
    vector<vector<double>>dis(n+1,vector<double>(n+1));
    cin>>a>>b,point[n]={a,b};
    auto get_distance=[](pair<int,int> a,pair<int,int> b){
        int x=a.first,y=a.second,xx=b.first,yy=b.second;
        return (double)(sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy)));
    };   
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dis[i][j]=get_distance(point[i],point[j]);
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        double c=dis[a][b];
        g[a].push_back({b,c}),g[b].push_back({a,c});
    }
    vector<double>ans=dijkstra(n,-1,-1);
    // for(int i=1;i<=n;i++) cout<<ans[i]<<' '; cout<<'\n';
    double res=1e9;
    for(int i=n;i!=1;i=pre[i]){
        int aa=i,bb=pre[i];
        ans=dijkstra(n,aa,bb);
        // for(int i=1;i<=n;i++) cout<<ans[i]<<' '; cout<<'\n';
        res=min(res,ans[n]);
    }
    if(res==1e9) cout<<"-1"<<'\n';
    else printf("%.2lf\n",res);
    return 0;
}

P2149 [SDOI2009] Elaxia的路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

刚开始看没太懂题意,于是看了下题解,用到好多算法,感觉太过复杂,于是自己尝试着去解

了解题意后会发现,本题要求是求出两条路径中的公共边,这些公共边的边权相加即为答案,那么主要难点就在于如何去求所有的最短路径