2022浙江省赛G I M
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;
}