杭州网站建站平台,深圳网站专业建设公司,做网站工作描述,报考大专学历需要什么条件G - Easy Glide 题意
思路
由于数据范围比较小#xff08;1e3#xff09;,把所有的移动的时间转化为图论上的边权就可以了,再用dijkstra解决,注意如果用的是邻接表存的话要建双向边
代码
#include map
#include set
#include queue
#include 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 (u1)
#define u2 (u1|1)
#define pb push_back
#define pp pop_back()
#define int long long
#define laile coutlaileendl
#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 i0;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 pairint,intPII;
typedef pairdouble,doublePDD;
const int N4e610,INF4e18;
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 disgetdist(a,b);if(!j)add(j,i,dis/v1);else{if(v2*3dis)add(j,i,dis/v2);else add(j,i,3(dis-v2*3)/v1);}
}
void dijkstra()
{priority_queuepairdouble,int,vectorpairdouble,int,greaterpairdouble,intque;_rep(i,0,n1)dist[i]INF;que.push({0,0});dist[0]0;while(que.size()){auto tque.top();que.pop();int ut.se;if(st[u])continue;st[u]true;for(int ih[u];~i;ine[i]){int je[i];double kw[i];
// coutdist[]if(dist[j]dist[u]k){dist[j]dist[u]k;que.push({dist[j],j});}}}return ;
}
void solve()
{memset(h,-1,sizeof(h));
// cinn;sf(n);_rep(i,1,n)sff(q[i].fi,q[i].se);
// cinq[i].fiq[i].se;sff(q[0].fi,q[0].se);sff(q[n1].fi,q[n1].se);
// cinq[0].fiq[0].seq[n1].fiq[n1].se;
// cinv1v2;sff(v1,v2);_rep(i,0,n1)_rep(j,0,i-1){addv(q[i],q[j],i,j);addv(q[j],q[i],j,i);}dijkstra();printf(%.10Lf,dist[n1]);
// coutdist[n1]endl;return ;
}
signed main()
{
// IOS;int T1;
// cinT;while(T--)solve();return 0;
}
I - Barbecue
题意 思路
如果此时查询的子字符串是回文,则Budada直接赢,否则这两个人一定会一直取取到最后一个,判断奇偶即可
可以发现abab...这种形式,删一次的话Putata直接输了,这里可以分类讨论一下
如果是偶数的ababab..这种形式的话Putata删一次就输了所以Putata就输了
假如是偶数但是不是ababab..这种形式的话,删到剩最后一个Putata还是输了
奇数没有特判所以删到最后一个Budada就输了
综上所述如果此时查询的子字符串是回文,则Budada直接赢,否则偶数Budada赢,奇数Putata赢
代码
#includebits/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 pairint,int
#define f first
#define s second
#define int long long
typedef unsigned long long ull;
const int N 1e610;
const int P 133331;ull h[N][3],p[N];
string a,b;
int m,n;
void hx()
{p[0]1;for(int i1;im;i) {p[i]p[i-1]*P;h[i][1] h[i-1][1]*Pa[i];h[i][2] h[i-1][2]*Pb[i]; }
}ull get(int l,int r)
{return h[r][1]-h[l-1][1]*p[r-l1];
}
ull fget(int l,int r)
{return h[r][2]-h[l-1][2]*p[r-l1];
}
//
//
//void solve()
{cinmn;cinb;ab;reverse(b.begin(),b.end());a a;b b;hx();while(n--){int l,r;cinlr;int llm-r1,rrm-l1;if(get(l,r)fget(ll,rr)) coutBudadaendl;else {if((r-l)%2)coutBudadaendl;else coutPutataendl;}}}
signed main()
{IOS;int _1;while(_--)solve();return 0;
}
M - BpbBppbpBB
题意
在1000x1000的图中找8 bp形状的数量(大小必须相同)
思路
把所有第一次遇到.的位置BFS一遍,然后暴力判断这个.所在的连通块是否是满足条件的洞如下: 满足的话就把这个连通块左上角(也就是BFS初始进来的点)坐标加入到待选的数组里
由于一个8或者bp尺寸为10*17,那么洞的数量最多1000/10*1000/175800个,可以两重循环判断洞与洞的关系
最后加入两个洞所在坐标的哈密顿距离7就说明这两个洞对应一个8,剩余不满足这个条件的洞对应bp即可
代码
#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 (u1)
#define u2 (u1|1)
#define pb push_back
#define pp pop_back()
#define int long long
#define laile coutlaileendl
#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 i0;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 pairint,intPII;
typedef pairdouble,doublePDD;
const int N1e310,INF4e18;
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)
{queuePIIq;now[a][b]cnt;q.push({a,b});int res1;while(q.size()){auto tq.front();q.pop();int xxt.fi,yyt.se;_rep(i,0,3){int xxxdx[i],yyydy[i];if(x1||xn||y1||ym||g[x][y]#||now[x][y])continue;now[x][y]cnt;res;q.push({x,y});}}if(a3nb2mb-11res12){vectorPIIv;v.pb({a,b});v.pb({a,b1});v.pb({a1,b-1});v.pb({a1,b});v.pb({a1,b1});v.pb({a1,b2});v.pb({a2,b-1});v.pb({a2,b});v.pb({a2,b1});v.pb({a2,b2});v.pb({a3,b});v.pb({a3,b1});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()
{vectorPIIv;cinnm;_rep(i,1,n)_rep(j,1,m)cing[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 ba0;_rep(i,0,(int)v.size()-1)_rep(j,0,i-1)if(getdist(v[i],v[j])7)ba;coutba (int)v.size()-ba*2;return;
}
signed main()
{IOS;int T1;
// cinT;while(T--)solve();return 0;
}
