随机算法+套路思维
第一次遇到随机算法
也不能说没有像那个方向去想
因为我们有n个移动方案
然后组合一共有个所以,对于一个点大概室友的概率被抓到
然后我们就可以靠这个随机枚举个点,然后判断是否可以抓到
就好了。。。。。
#include<iostream> #include<algorithm> #include<vector> #include<ctime> using namespace std; const int max_n = 1e5+100; typedef pair<int,int> pii; pii G[max_n]; int n; bool check(int x0,int y0,int x1,int y1) { for (int i=1;i<=n;++i) { int x = x0+G[i].first; int y = y0+G[i].second; if (x<=0||x>n||y<=0||y>n)continue; if ((x==x1&&y==y1)||binary_search(G+1,G+1+n,pii(x1-x,y1-y))) return true; } return false; } int main() { ios::sync_with_stdio(0); cin>>n; int x0,y0,x1,y1; cin>>x0>>y0>>x1>>y1; for (int i=1;i<=n;++i)cin>>G[i].first>>G[i].second; sort(G+1,G+1+n); if (check(x0,y0,x1,y1)) { cout<<"Alice wins"<<endl; return 0; } srand(time(NULL)); int t = 30; while (t--) { int x = rand()%n+1; int y = rand()%n+1; if (x==x1&&y==y1) { ++t; continue; } if (!check(x1,y1,x,y)) { cout<<"tie "<<x<<" "<<y<<endl; return 0; } } cout<<"Bob wins"<<endl; }