526互联

AtCoder Beginner Contest 289(E,F)

发布时间 2023-05-30 21:55:56作者: righting

AtCoder Beginner Contest 289(E,F)

E(dijkstra)

E

这个题的大意就是有两个人，一个人在点\(1\)，一个人在点\(n\),现在两个人要同时走（题目给出了点和边，还有每一个点的颜色），但是他们的下一步要到的点需要是颜色不同的，问\(1\)点出发的和\(n\)点

出发的同时达到对方的起点的最短路径时哪个

一开始觉得好复杂呀，还有考虑颜色，会不会超时

其实不用担心这个，\(n\)和\(m\)都不是很大，\(n\)为\(2e3\)，我们可以定义状态为两个人的不同位置，假如此时是\(x,y\)，一人在点\(x\)，一人在点\(y\)，那我们任意组合这两个点可达的点，对于颜色不同的满足条件的可以考虑

然后后面的就是\(djkstra\)了

我很多时候都害怕超时而放弃某一个想法，希望下一次可以多试试，还有就是我自己的时间复杂度也不太会计算

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=2e3+10;
const int mod=998244353;
int t,n,m;
vector<int>g[maxn];
int col[maxn];
struct node
{
    int l,r,dis;
    friend bool operator < (const node x,const node y)
    {
        return x.dis>y.dis;
    }
};
void init()
{
    for (int i=1;i<=n;i++)
    {
        g[i].clear();
    }
}
int dijkstra()
{
    priority_queue<node>q;
    vector<vector<int>>dis(n+1,vector<int>(n+1,inf));
    vector<vector<bool>>vis(n+1,vector<bool>(n+1,false));
    dis[1][n]=0;
    q.push({1,n,dis[1][n]});
    while (!q.empty())
    {
        auto [l,r,d]=q.top();
        q.pop();
        if(l==n&&r==1)
        {
            return d;
        }
        if(vis[l][r]) continue;
        vis[l][r]=true;
        for (auto x:g[l])
        {
            for (auto y:g[r])
            {
                if(col[x]!=col[y])
                {
                    if(dis[x][y]>d+1)
                    {
                        dis[x][y]=d+1;
                        q.push({x,y,d+1});
                    }
                }
            }
        }
    }
    return -1;
}
void solve()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        cin>>col[i];
        g[i].clear();
    }
    for (int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans=dijkstra();
    cout<<ans<<"\n";
    return ;
}
signed main ()
{
    cin>>t;
    while (t--)
    {
        solve();
    }
    system ("pause");
    return 0;
}

F (计算几何)

F

给出我们两个点\(sx,sy\)和\(tx,ty\)，还有一个矩形\(a<=x<=b\),\(c<=y<=d\)，就是\(x\)的范围是从\(a\)到\(b\),\(y\)的范围是\(c\)到\(d\),我们可以在这一块矩形里面任意选择一个点，把\(sx,sy\)变成一个以我们选择的点作为对称中心变成该点的对称位置，问我们可以怎么选择把\(sx,sy\)变成\(tx,ty\),如果不可以，输出\(-1\)

首先，我们要知道点对称变换的公式

如\(sx,sy\)以\(x,y\)对称的位置是\(xx,yy\),公式如下

\[xx=2\times x-sx\\yy=2\times y-sy \]

扩展学习

这里面有一个规律

当我们只看一维的时

如果一开始把\(sx,sy\)对\(x,y\)进行对称操作，然后再对\(x+1,y\)进行操作时,\(sx\)变成了\(sx+2\)（可以自己画着试一试）

反过来，如果一开始把\(sx,sy\)对\(x+1,y\)进行对称操作，然后再对\(x,y\)进行操作时,\(sx\)变成了\(sx-2\)

而且，对于二维坐标，这个是独立而互不影响的，所以每一次我们都可以对坐标进行一个加二或者减二的操作

那么我们要求坐标和目标坐标的距离是偶数，也就是他们的奇偶性相同即可

这是对于存在\(x\)和\(x+1\)操作的

还有一种情况就是\(a\)和\(b\)是一样的，那么就不能进行\(x+1\)的操作了

那么就只有\(a\)刚好是中点或者\(sx\)（只需一次操作）和\(tx\)是一样的（这样的话就根本不需要操作了）才可能成功

所以，对于不能进行\(x+1\)的那一步操作的，我们先进行一次操作（如果有必要的话），如果还是不行，那么直接输出\(No\)

后面就是排除了前面的特殊情况，一定是可以到达的情况了，我们就只用考虑让\(sx\)等于\(tx\),\(sy\)等于\(ty\)就好了

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=2e3+10;
const int mod=998244353;
struct point
{
    int x,y;
}s,t;
int a,b,c,d;
vector<pair<int,int>>ans;
bool ok(int i,int j,int l,int r)
{
    //  bool ok0 = ((i ^ j) % 2 == 0 && (l != r || (i == j|| l + r == i + j)));
    //  return ok0;
     if(i==j) return true;
    if((i&1)!=(j&1)) return false;
    if(l==r)
    {
        if(i+j==l+r)
        {
            return true;
        }
        return false;
    }
    return true;
}
void update(int x,int y)
{
    s.x=2*x-s.x;
    s.y=2*y-s.y;
    ans.push_back({x,y});
    return ;
}
signed main ()
{
    cin>>s.x>>s.y>>t.x>>t.y;
    cin>>a>>b>>c>>d;
    if(!ok(s.x,t.x,a,b)||!ok(s.y,t.y,c,d))
    {
        cout<<"No\n";
        system ("pause");
        return 0;
    }
    if(a==b&&s.x!=t.x)//只变一次，x可能会变,y也可能会变
    {
        update(a,c);
    }
    if(c==d&&s.y!=t.y)
    {
        update(a,c);
    }
    //都变完一次的情况，最后再来考虑会导致不一样的情况
    if(s.x!=t.x&&a==b)
    {
        cout<<"No\n";
        system ("pause");
        return 0;
    }
    if(s.y!=t.y&&c==d)
    {
        cout<<"No\n";
        system ("pause");
        return 0;
    }
    while (s.x<t.x)
    {
        update(a,c);
        update(a+1,c);
    }
    while (s.x>t.x)
    {
        update(a+1,c);
        update(a,c);
    }
    while (s.y<t.y)
    {
        update(a,c);
        update(a,c+1);
    }
    while (s.y>t.y)
    {
        update(a,c+1);
        update(a,c);
    }
    cout<<"Yes\n";
    for (auto [x,y]:ans)
    {
        cout<<x<<" "<<y<<"\n";
    }
    system ("pause");
    return 0;
}