G - Easy Glide
题意
思路
由于数据范围比较小（1e3）,把所有的移动的时间转化为图论上的边权就可以了,再用dijkstra解决,注意如果用的是邻接表存的话要建双向边
代码
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define u1 (u<<1)
#define u2 (u<<1|1)
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
const int N=4e6+10,INF=4e18;
int n,m;
int e[N],ne[N],h[N],idx,v1,v2;
double w[N];
PII q[N];
double dist[N];
bool st[N];
void add(int a,int b,double c)
{
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
double getdist(PII a,PII b)
{
return sqrt((a.fi-b.fi)*(a.fi-b.fi)+(a.se-b.se)*(a.se-b.se));
}
void addv(PII a,PII b,int i,int j)
{
double dis=getdist(a,b);
if(!j)add(j,i,dis/v1);
else
{
if(v2*3>=dis)add(j,i,dis/v2);
else add(j,i,3+(dis-v2*3)/v1);
}
}
void dijkstra()
{
priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>>que;
_rep(i,0,n+1)dist[i]=INF;
que.push({0,0});
dist[0]=0;
while(que.size())
{
auto t=que.top();
que.pop();
int u=t.se;
if(st[u])continue;
st[u]=true;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
double k=w[i];
// cout<<dist[]
if(dist[j]>dist[u]+k)
{
dist[j]=dist[u]+k;
que.push({dist[j],j});
}
}
}
return ;
}
void solve()
{
memset(h,-1,sizeof(h));
// cin>>n;
sf(n);
_rep(i,1,n)sff(q[i].fi,q[i].se);
// cin>>q[i].fi>>q[i].se;
sff(q[0].fi,q[0].se);
sff(q[n+1].fi,q[n+1].se);
// cin>>q[0].fi>>q[0].se>>q[n+1].fi>>q[n+1].se;
// cin>>v1>>v2;
sff(v1,v2);
_rep(i,0,n+1)
_rep(j,0,i-1)
{
addv(q[i],q[j],i,j);
addv(q[j],q[i],j,i);
}
dijkstra();
printf("%.10Lf",dist[n+1]);
// cout<<dist[n+1]<<endl;
return ;
}
signed main()
{
// IOS;
int T=1;
// cin>>T;
while(T--)
solve();
return 0;
}I - Barbecue
题意
思路
如果此时查询的子字符串是回文,则Budada直接赢,否则这两个人一定会一直取取到最后一个,判断奇偶即可
可以发现abab...这种形式,删一次的话Putata直接输了,这里可以分类讨论一下
如果是偶数的ababab..这种形式的话Putata删一次就输了所以Putata就输了
假如是偶数但是不是ababab..这种形式的话,删到剩最后一个Putata还是输了
奇数没有特判所以删到最后一个Budada就输了
综上所述：如果此时查询的子字符串是回文,则Budada直接赢,否则偶数Budada赢,奇数Putata赢
代码
#include<bits/stdc++.h>
using namespace std;
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld%lld",&x,&y)
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pf(x) printf("%lld",x)
#define pii pair<int,int>
#define f first
#define s second
#define int long long
typedef unsigned long long ull;
const int N =1e6+10;
const int P = 133331;
ull h[N][3],p[N];
string a,b;
int m,n;
void hx()
{
p[0]=1;
for(int i=1;i<=m;i++)
{
p[i]=p[i-1]*P;
h[i][1] = h[i-1][1]*P+a[i];
h[i][2] = h[i-1][2]*P+b[i];
}
}
ull get(int l,int r)
{
return h[r][1]-h[l-1][1]*p[r-l+1];
}
ull fget(int l,int r)
{
return h[r][2]-h[l-1][2]*p[r-l+1];
}
//
//
//
void solve()
{
cin>>m>>n;
cin>>b;
a=b;
reverse(b.begin(),b.end());
a=" "+a;
b=" "+b;
hx();
while(n--)
{
int l,r;
cin>>l>>r;
int ll=m-r+1,rr=m-l+1;
if(get(l,r)==fget(ll,rr)) cout<<"Budada"<<endl;
else
{
if((r-l)%2)cout<<"Budada"<<endl;
else cout<<"Putata"<<endl;
}
}
}
signed main()
{
IOS;
int _=1;
while(_--)
solve();
return 0;
}M - BpbBppbpBB
题意
在1000x1000的图中找'8' 'b''p'形状的数量(大小必须相同)
思路
把所有第一次遇到'.'的位置BFS一遍,然后暴力判断这个'.'所在的连通块是否是满足条件的洞如下:
满足的话就把这个连通块左上角(也就是BFS初始进来的点)坐标加入到待选的数组里
由于一个'8'或者'b''p'尺寸为10*17,那么洞的数量最多1000/10*1000/17=5800个,可以两重循环判断洞与洞的关系
最后加入两个洞所在坐标的哈密顿距离=7就说明这两个洞对应一个8,剩余不满足这个条件的洞对应'b''p'即可
代码
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define u1 (u<<1)
#define u2 (u<<1|1)
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
const int N=1e3+10,INF=4e18;
int n,m,cnt;
char g[N][N];
int now[N][N];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
bool bfs(int a,int b,int cnt)
{
queue<PII>q;
now[a][b]=cnt;
q.push({a,b});
int res=1;
while(q.size())
{
auto t=q.front();
q.pop();
int xx=t.fi,yy=t.se;
_rep(i,0,3)
{
int x=xx+dx[i],y=yy+dy[i];
if(x<1||x>n||y<1||y>m||g[x][y]=='#'||now[x][y])continue;
now[x][y]=cnt;
res++;
q.push({x,y});
}
}
if(a+3<=n&&b+2<=m&&b-1>=1&&res==12)
{
vector<PII>v;
v.pb({a,b});
v.pb({a,b+1});
v.pb({a+1,b-1});
v.pb({a+1,b});
v.pb({a+1,b+1});
v.pb({a+1,b+2});
v.pb({a+2,b-1});
v.pb({a+2,b});
v.pb({a+2,b+1});
v.pb({a+2,b+2});
v.pb({a+3,b});
v.pb({a+3,b+1});
for(auto i:v)if(now[i.fi][i.se]!=cnt)return false;
}
else return false;
return true;
}
int getdist(PII a,PII b)
{
return abs(a.fi-b.fi)+abs(a.se-b.se);
}
void solve()
{
vector<PII>v;
cin>>n>>m;
_rep(i,1,n)
_rep(j,1,m)
cin>>g[i][j];
_rep(i,1,n)
_rep(j,1,m)
if(g[i][j]=='.'&&!now[i][j])
if(bfs(i,j,++cnt))v.pb({i,j});
int ba=0;
_rep(i,0,(int)v.size()-1)
_rep(j,0,i-1)
if(getdist(v[i],v[j])==7)ba++;
cout<<ba<<" "<<(int)v.size()-ba*2;
return;
}
signed main()
{
IOS;
int T=1;
// cin>>T;
while(T--)
solve();
return 0;
}
