AtCoder Beginner Contest 289(E,F)
E(dijkstra)
这个题的大意就是有两个人，一个人在点\(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 (计算几何)
给出我们两个点\(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;
}