首页 > 代码库 > XVI Open Cup named after E.V. Pankratiev. GP of SPB
XVI Open Cup named after E.V. Pankratiev. GP of SPB
A. Bubbles
枚举两个点,求出垂直平分线与$x$轴的交点,答案=交点数+1。
时间复杂度$O(n^2\log n)$。
#include<cstdio>#include<algorithm>#include<cmath>using namespace std;const double eps=1e-9;int sgn(double x){ if(x<-eps)return -1; if(x>eps)return 1; return 0;}struct P{ double x,y; P(){x=y=0;} P(double _x,double _y){x=_x,y=_y;} P operator+(P v){return P(x+v.x,y+v.y);} P operator-(P v){return P(x-v.x,y-v.y);} P operator*(double v){return P(x*v,y*v);} P operator/(double v){return P(x/v,y/v);} P rot90(){return P(-y,x);}}a[2000];double q[1111111];double cross(P a,P b){return a.x*b.y-a.y*b.x;}int line_intersection(P a,P b,P p,P q,P&o){ if(!sgn(a.x-b.x)&&!sgn(a.y-b.y))return 0; if(!sgn(p.x-q.x)&&!sgn(p.y-q.y))return 0; double U=cross(p-a,q-p), D=cross(b-a,q-p); if(sgn(D)==0)return 0; o=a+(b-a)*(U/D); return 1;}int main () { freopen ( "bubbles.in" , "r" , stdin ) ; freopen ( "bubbles.out" , "w" , stdout ) ; int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lf%lf",&a[i].x,&a[i].y); } P A(-100,0),B(100,0); int cnt=0; for(int i=1;i<=n;i++)for(int j=1;j<i;j++){ P t=(a[i]+a[j])/2.0; P v=a[i]-a[j]; v=v.rot90(); P tmp; if(line_intersection(t,t+v,A,B,tmp)){ q[++cnt]=tmp.x; } } sort(q+1,q+cnt+1); int ans=1; for(int i=1;i<=cnt;i++)if(i==1||sgn(q[i]-q[i-1]))ans++; printf("%d",ans); return 0;}
B. Drop7
留坑。
C. Eulerian Graphs
留坑。
D. At Least Half
枚举所有质数$p$,找出所有$p$的倍数,设$s[i]$表示前$i$个数里$p$的倍数$\times2$,枚举$i$,要找到最小的$j$满足$s[i]-i\geq s[j]-j$,维护$s[i]-i$的前缀最小值,然后二分查找即可。找到$j$之后贪心计算往左往右能扩展多少。
时间复杂度$O(n\log n\log\log n)$。
#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef pair<int,int>pi;const int Maxn=1000020;int a[Maxn];vector<int>V[Maxn/10];vector<int>pri;int n;bool isp[Maxn];void getp(){ for(int i=2;i<Maxn;i++){ if(!isp[i]){ pri.push_back(i); } for(int j=0;j<pri.size();j++){ if(i*pri[j]>=Maxn)break; isp[i*pri[j]]=1; if(i%pri[j]==0)break; } }}int ans,ansr;int g[Maxn],gmx[Maxn];void check(vector<int>&V){ //for(int i=0;i<V.size();i++)printf("%d ",V[i]);puts(""); for(int i=0;i<V.size();i++)g[i]=V[i]-2*(i+1); for(int i=0;i<V.size();i++)gmx[i]=V[i]-1-2*(i); for(int i=1;i<V.size();i++)gmx[i]=max(gmx[i],gmx[i-1]); for(int i=0;i<V.size();i++){ int j=lower_bound(gmx,gmx+V.size(),g[i])-gmx; int has=i-j+1,haslen=V[i]-V[j]+1; //printf("val=1%d val2=%d\n",V[i-1],j); int rr=i==V.size()-1?n:(V[i+1]-1); int ll=j==0?1:(V[j-1]+1); int tmpans=min(rr-ll+1,has*2); int csr=V[i]+min(tmpans-haslen,rr-V[i]); //printf("%d %d %d %d\n",ll,rr,has,tmpans); if(tmpans>ans){ ans=tmpans; ansr=csr; } }}void solve(vector<int>&V){ check(V);}int main(){freopen("halfgcd.in","r",stdin);freopen("halfgcd.out","w",stdout); getp(); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",a+i); for(int i=1;i<=n;i++){ int x=a[i]; for(int j=0;j<pri.size();j++){ if(1LL*pri[j]*pri[j]>x)break; if(x%pri[j])continue; V[j].push_back(i); while(x%pri[j]==0)x/=pri[j]; } if(x>1)V[lower_bound(pri.begin(),pri.end(),x)-pri.begin()].push_back(i); } ans=0,ansr=-1; for(int it=0;it<pri.size();it++){ if(!V[it].size())continue; solve(V[it]); } if(!ans){ puts("0 0"); } else printf("%d %d\n",ansr-ans+1,ansr); return 0;}
E. Next Partition in RLE Notation
只有最后几个数是有用的,分类讨论构造即可。
#include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , int > pii ;typedef pair < LL , LL > pll ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 100005 ;vector < pll > G ;int n ;void get ( LL N , LL K , LL val ) { LL tmp1 = ( N - K ) / ( val - 1 ) ; LL tmp2 = ( N - K ) % ( val - 1 ) ; LL tmp3 = K - tmp1 - ( tmp2 > 0 ) ; if ( tmp1 ) G.push_back ( pll ( tmp1 , val ) ) ; if ( tmp2 ) G.push_back ( pll ( 1 , tmp2 + 1 ) ) ; if ( tmp3 ) G.push_back ( pll ( tmp3 , 1 ) ) ;}void solve () { G.clear () ; for ( int i = 1 ; i <= n ; ++ i ) { LL x , y ; scanf ( "%lld%lld" , &x , &y ) ; G.push_back ( pll ( x , y ) ) ; } if ( n == 1 || n == 2 && G[0].second - G[1].second == 1 ) { printf ( "-1\n" ) ; return ; } pll a = G[n - 1] ; -- n ; G.pop_back () ; pll b = G[n - 1] ; if ( G[n - 1].second - a.second > 1 ) { G[n - 1].first -- ; if ( !G[n - 1].first ) { G.pop_back () ; -- n ; } //printf ( "%lld %lld %lld %lld\n" , a.first , a.second , b.first , b.second ) ; get ( a.first * a.second + b.second , a.first + 1 , b.second - 1 ) ; } else { G.pop_back () ; -- n ; pll c = G[n - 1] ; G[n - 1].first -- ; if ( !G[n - 1].first ) { G.pop_back () ; -- n ; } get ( a.first * a.second + b.first * b.second + c.second , a.first + b.first + 1 , c.second - 1 ) ; } printf ( "%d\n" , ( int ) G.size () ) ; for ( int i = 0 ; i < G.size () ; ++ i ) { printf ( "%lld %lld\n" , G[i].first , G[i].second ) ; }}int main () { freopen ( "next-partition-rle.in" , "r" , stdin ) ; freopen ( "next-partition-rle.out" , "w" , stdout ) ; while ( ~scanf ( "%d" , &n ) ) solve () ; return 0 ;}
F. Equation
留坑。
G. “Swap-Plus” Puzzle
显然存在一种最优操作序列,先做行交换,在做列交换,最后再交换格子。
枚举行交换、列交换的顺序,然后贪心交换即可。
#include<cstdio>#include<algorithm>#include<cmath>#include<string>#include<iostream>using namespace std;int i,j,a[9][9],b[9],c[9],d[9][9],m,e[100];int ans=~0U>>1,cnt;string q[100];int now;int cal(int*a,int n){ int t=0; int i,j; static int b[100]; for(i=1;i<=n;i++)b[i]=a[i]; for(i=1;i<=n;i++){ for(j=1;j<=n;j++)if(b[j]==i){ if(i!=j)t++; swap(b[j],b[i]); break; } } return t;}int cal2(int*a,int n){ int t=0; int i,j; static int b[100]; for(i=1;i<=n;i++)b[i]=i; for(i=1;i<=n;i++){ for(j=1;j<=n;j++)if(b[j]==a[i]){ if(i!=j)t++; swap(b[j],b[i]); break; } } return t;}void conb(int*a,char st){//[1,2,3,4]->a static int b[10]; int i,j; for(i=1;i<=4;i++)b[i]=i; for(i=1;i<=4;i++){ for(j=1;j<=4;j++)if(b[j]==a[i]){ if(i!=j){ string t=""; t.push_back(b[i]+st-1); t.push_back(‘-‘); t.push_back(b[j]+st-1); q[++cnt]=t; } swap(b[j],b[i]); break; } }}void cond(){//a->[1,2,3,4,...,16] static int a[9][9]; int i,j,x,y; for(i=1;i<=4;i++)for(j=1;j<=4;j++)a[i][j]=d[i][j]; for(i=1;i<=4;i++)for(j=1;j<=4;j++){ int now=(i-1)*4+j; if(a[i][j]==now)continue; bool flag=0; for(x=1;x<=4;x++){ for(y=1;y<=4;y++)if(a[x][y]==now){ flag=1; swap(a[x][y],a[i][j]); string t=""; t.push_back(i+‘a‘-1); t.push_back(j+‘0‘); t.push_back(‘-‘); t.push_back(x+‘a‘-1); t.push_back(y+‘0‘); q[++cnt]=t; break; } if(flag)break; } }}int main (){ freopen ( "puzzle-swap-plus.in" , "r" , stdin ) ; freopen ( "puzzle-swap-plus.out" , "w" , stdout ) ; for(i=1;i<=4;i++) for(j=1;j<=4;j++) scanf("%d",&a[i][j]); for(i=1;i<=4;i++)b[i]=i; do{ for(i=1;i<=4;i++)c[i]=i; do{ now=cal2(b,4)+cal2(c,4); for(i=1;i<=4;i++)for(j=1;j<=4;j++)d[b[i]][c[j]]=a[i][j]; m=0; for(i=1;i<=4;i++)for(j=1;j<=4;j++)e[++m]=d[i][j]; now+=cal(e,16); if(now<ans){ ans=now; cnt=0; conb(b,‘a‘); conb(c,‘1‘); cond(); } }while(next_permutation(c+1,c+4+1)); }while(next_permutation(b+1,b+4+1)); printf("%d\n",ans); for(i=1;i<=cnt;i++)cout<<q[i]<<endl; return 0;}
H. Wrong Sieve
考虑每一轮与上一轮位置的递推关系即可。
#include<bits/stdc++.h>using namespace std;const int Maxn=105;typedef long long LL;typedef pair<int,int>pi;LL solve(LL x){ for(LL i=1;x>=(i+1);i++){ if(x%(i+1)==0)return -1; x=x-x/(i+1); } return x;}int main(){freopen("sieve.in","r",stdin);freopen("sieve.out","w",stdout); int _;scanf("%d",&_); while(_--){ LL x;scanf("%lld",&x); LL ans=solve(x); printf("%lld\n",ans); } return 0;}
I. Space Cat
DP,$f[i][j]$表示在第$i$条线段,重心方向为$j$的最小代价,注意要特判图不联通的情况。
时间复杂度$O(n)$。
#include <bits/stdc++.h>using namespace std ;typedef pair < int , int > pii ;#define clr( a , x ) memset ( a , x , sizeof a )typedef long long ll;const ll inf=1LL<<60;const int N=100010;int n,i,a[N],b[N],c[N];ll f[N][2];inline void up(ll&x,ll y){if(x>y)x=y;}int main () { int T ; freopen ( "space-cat.in" , "r" , stdin ) ; freopen ( "space-cat.out" , "w" , stdout ) ; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); for(i=1;i<=n;i++)scanf("%d",&b[i]),c[i]=a[i]-b[i]; for(i=2;i<=n;i++)if(b[i]>=a[i-1]||b[i-1]>=a[i])return puts("-1"),0; for(i=1;i<=n;i++)f[i][0]=f[i][1]=inf; f[1][0]=0; for(i=1;i<=n;i++){ if(i>1){ if(a[i-1]<=a[i])up(f[i][1],f[i-1][1]); if(b[i-1]>=b[i])up(f[i][0],f[i-1][0]); } for(int j=0;j<4;j++){ up(f[i][0],f[i][1]+c[i]); up(f[i][1],f[i][0]+c[i]); } } if(f[n][0]>=inf)f[n][0]=-1; printf("%lld\n",f[n][0]); return 0 ;}
J. Tic-Tac-Toe Variation
第一步填中间,然后只有两种情况,分类讨论构造策略即可。
#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef pair<int,int>pi;const int Maxn=1000020;char Mp[4][4];bool getMp(){ bool ret=0; for(int i=0;i<3;i++){ scanf("%s",Mp[i]); for(int j=0;j<3;j++){ if(Mp[i][j]!=‘x‘)ret=1; } } return ret;}int idx[3][3]={ {0,1,2}, {7,-1,3}, {6,5,4}};int dx[8],dy[8];int curMp[3][3];int cg(char c){ if(c==‘.‘)return 0; if(c==‘x‘)return 1; return 2;}void tran(){ for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ curMp[i][j]=cg(Mp[i][j]); } }}void pt(){ for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ int c=curMp[i][j]; if(!c)putchar(‘.‘); if(c==1)putchar(‘x‘); if(c==2)putchar(‘o‘); } puts(""); } fflush(stdout);}int getst(){ for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(curMp[i][j]==2){ return idx[i][j]; } } }}int main(){//freopen("halfgcd.in","r",stdin);//freopen("halfgcd.out","w",stdout); for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(i==1&&j==1)continue; dx[idx[i][j]]=i; dy[idx[i][j]]=j; } } while(getMp()){ int st; memset(curMp,0,sizeof curMp); for(int it=0;;it++){ if(it==0){ curMp[1][1]=1; pt(); continue; } if(it==1){ getMp(); tran(); st=getst(); int nst=(st+2)%8; curMp[dx[nst]][dy[nst]]=1; pt(); continue; } if(it==2){ getMp(); tran(); if(curMp[dx[(st+6)%8]][dy[(st+6)%8]]!=2){ curMp[dx[(st+6)%8]][dy[(st+6)%8]]=1; pt(); break; } else{ curMp[dx[(st+3)%8]][dy[(st+3)%8]]=1; pt(); } } if(it==3){ getMp(); tran(); int nst=st&1?((st+1)%8):((st+4)%8); if(!curMp[dx[nst]][dy[nst]]){ curMp[dx[nst]][dy[nst]]=1; pt(); break; } else{ nst=(st+7)%8; curMp[dx[nst]][dy[nst]]=1; pt(); break; } } } } return 0;}
K. Captain Tarjan
对于每个询问,将路径上的边权都加1。
那么问题就变成了,给定一棵树,找到一个点,然后随意剖分,使得所有轻边的权值和最小,两遍DP即可。
时间复杂度$O(m\log n)$。
#include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , int > pii ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 100005 ;vector < pii > G[MAXN] ;LL dp[MAXN] , dp2[MAXN] , maxc[MAXN] ;LL Ldp[MAXN] , Rdp[MAXN] , Lmaxc[MAXN] , Rmaxc[MAXN] ;int c[MAXN] ;int siz[MAXN] ;int son[MAXN] ;int pre[MAXN] ;int top[MAXN] ;int dep[MAXN] ;int n , m ;LL ans ;void predfs ( int u , int f ) { siz[u] = 1 ; son[u] = 0 ; for ( int i = 0 ; i < G[u].size () ; ++ i ) { int v = G[u][i].first ; if ( v == f ) continue ; pre[v] = u ; dep[v] = dep[u] + 1 ; predfs ( v , u ) ; siz[u] += siz[v] ; if ( siz[v] > siz[son[u]] ) son[u] = v ; }}void rebuild ( int u , int top_element ) { top[u] = top_element ; if ( son[u] ) rebuild ( son[u] , top_element ) ; for ( int i = 0 ; i < G[u].size () ; ++ i ) { int v = G[u][i].first ; if ( v != pre[u] && v != son[u] ) rebuild ( v , v ) ; }}int get_lca ( int x , int y ) { while ( top[x] != top[y] ) { if ( dep[top[x]] > dep[top[y]] ) x = pre[top[x]] ; else y = pre[top[y]] ; } return dep[x] < dep[y] ? x : y ;}void dfs1 ( int u ) { for ( int i = 0 ; i < G[u].size () ; ++ i ) { int v = G[u][i].first ; if ( v == pre[u] ) continue ; dfs1 ( v ) ; G[u][i].second = c[v] ; c[u] += c[v] ; }}void dfs2 ( int u ) { dp[u] = maxc[u] = 0 ; for ( int i = 0 ; i < G[u].size () ; ++ i ) { int v = G[u][i].first ; if ( v == pre[u] ) continue ; dfs2 ( v ) ; dp[u] += dp[v] + G[u][i].second ; maxc[u] = max ( maxc[u] , G[u][i].second + 0LL ) ; } dp[u] -= maxc[u] ;}void dfs3 ( int u , int cost ) { int n = G[u].size () ; Ldp[0] = 0 ; Rdp[n - 1] = 0 ; Lmaxc[0] = 0 ; Rmaxc[n - 1] = 0 ; for ( int i = 1 ; i < n ; ++ i ) { int v = G[u][i - 1].first ; if ( v == pre[u] ) { Ldp[i] = Ldp[i - 1] ; Lmaxc[i] = Lmaxc[i - 1] ; } else { Ldp[i] = Ldp[i - 1] + dp[v] + G[u][i - 1].second ; Lmaxc[i] = max ( Lmaxc[i - 1] , G[u][i - 1].second + 0LL ) ; } } for ( int i = n - 2 ; i >= 0 ; -- i ) { int v = G[u][i + 1].first ; if ( v == pre[u] ) { Rdp[i] = Rdp[i + 1] ; Rmaxc[i] = Rmaxc[i + 1] ; } else { Rdp[i] = Rdp[i + 1] + dp[v] + G[u][i + 1].second ; Rmaxc[i] = max ( Rmaxc[i + 1] , G[u][i + 1].second + 0LL ) ; } } for ( int i = 0 ; i < n ; ++ i ) { int v = G[u][i].first ; if ( v == pre[u] ) continue ; dp2[v] = dp2[u] + Ldp[i] + Rdp[i] + cost - max ( max ( Lmaxc[i] , Rmaxc[i] ) , cost + 0LL ) ; ans = min ( ans , dp2[v] + dp[v] + maxc[v] + G[u][i].second - max ( maxc[v] , 0LL + G[u][i].second ) ) ; } for ( int i = 0 ; i < n ; ++ i ) { int v = G[u][i].first ; if ( v == pre[u] ) continue ; dfs3 ( v , G[u][i].second ) ; }}void solve () { for ( int i = 1 ; i <= n ; ++ i ) { G[i].clear () ; c[i] = 0 ; } for ( int i = 1 ; i < n ; ++ i ) { int u , v ; scanf ( "%d%d" , &u , &v ) ; G[u].push_back ( pii ( v , 0 ) ) ; G[v].push_back ( pii ( u , 0 ) ) ; } predfs ( 1 , 1 ) ; rebuild ( 1 , 1 ) ; for ( int i = 0 ; i < m ; ++ i ) { int u , v ; scanf ( "%d%d" , &u , &v ) ; c[u] ++ ; c[v] ++ ; int lca = get_lca ( u , v ) ; c[lca] -= 2 ; } dp2[1] = 0 ; dfs1 ( 1 ) ; dfs2 ( 1 ) ; ans = dp[1] ; dfs3 ( 1 , 0 ) ; printf ( "%lld\n" , ans ) ;}int main () { freopen ( "treepaths.in" , "r" , stdin ) ; freopen ( "treepaths.out" , "w" , stdout ) ; while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ; return 0 ;}
L. Gardening Lesson
求出两棵树的重心,枚举重心作为根,然后求出每棵子树的Hash值,在两棵树上一起dfs即可。
时间复杂度$O(n\log n)$。
#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef pair<int,int>pi;const int Maxn = 100005 , x = 123 , M = 998244353 , Left = 23 , Right = 371 ;const int Hleaf=Left*Right,Inf=1e9;vector < int > G1[Maxn] , G2[Maxn] ;int H1[Maxn] , H2[Maxn] ;int sz[Maxn],sonsz[Maxn],ans ;void dfs(int u , vector<int>*G,int p){ sz[u]= 1; sonsz[u]=0; for(int i=0;i<G[u].size ();++i){ int v =G[u][i]; if(v==p)continue ; dfs(v,G,u); sz[u]+=sz[v]; if(sz[v]>sonsz[u])sonsz[u]=sz[v]; }}vector<int>getroot(vector<int>*G,int n){ dfs(1,G,0); vector<int>ret; for(int i=1;i<=n;++i){ if(max(n-sz[i],sonsz[i])<=n/2){ ret.push_back(i); } } return ret;}bool cmp1(int a, int b){return H1[a]<H1[b];}bool cmp2(int a, int b){return H2[a]<H2[b];}void dfs2(int u,int p,vector<int>*G,int*H,int ty){ H[u]=Left; for(int i =0;i<G[u].size();++i){ int v=G[u][i];if(v==p)continue; dfs2(v,u,G,H,ty); } sort(G[u].begin(),G[u].end(),ty==1?cmp1:cmp2); for(int i=0;i<G[u].size();++i){ int v=G[u][i];if(v==p)continue; H[u]=((1LL*H[u]*x)^H[v])%M; } H[u]=1LL*H[u]*Right%M;}void check(int ua,int pa,int ub,int pb){ //printf("%d %d %d %d\n",ua,pa,ub,pb); set<pi>S; for(int i=0;i<G2[ub].size();i++){ int v=G2[ub][i]; if(v==pb)continue; S.insert(pi(H2[v],v)); } vector<int>rest; for(int i=0;i<G1[ua].size();i++){ int v=G1[ua][i]; if(v==pa)continue; set<pi>::iterator it=S.lower_bound(pi(H1[v],-1)); if(it==S.end()||(it->first!=H1[v]))rest.push_back(v); else S.erase(it); } if(rest.size()>1||S.size()>1)return; if(S.size()==1&&!rest.size()){ if(S.begin()->first!=Hleaf)return; for(int i=0;i<G2[ub].size();i++){ int v=G2[ub][i];if(v==pb)continue; if(H2[v]==Hleaf){ans=min(ans,v);} } return; } if(S.size()==1&&rest.size()==1){ for(int i=0;i<G2[ub].size();i++){ int v=G2[ub][i];if(v==pb)continue; if(H2[v]==S.begin()->first)check(rest[0],ua,v,ub); } }}void solve( int rt1 , int rt2){ dfs2(rt1,0,G1,H1,1); dfs2(rt2,0,G2,H2,2); check(rt1,0,rt2,0);}void pt(vector<int>&v){ for(int i=0;i<v.size();i++)printf("%d ",v[i]); puts("");}int main(){freopen("unexpected-leaf.in","r",stdin);freopen("unexpected-leaf.out","w",stdout); int n; while(scanf("%d",&n)!=EOF){ for(int i=1;i<=n+1;i++){ G1[i].clear(); G2[i].clear(); } for(int i=1;i<n;i++){ int u,v;scanf("%d%d",&u,&v); G1[u].push_back(v); G1[v].push_back(u); } for(int i=1;i<=n;i++){ int u,v;scanf("%d%d",&u,&v); G2[u].push_back(v); G2[v].push_back(u); } if(n==1){ printf("1\n"); continue; } if(n==2){ if(G2[1].size()==2)printf("2\n"); else printf("1\n"); continue; } vector<int>tmp1=getroot(G1,n); vector<int>tmp2=getroot(G2,n+1); //pt(tmp1); //pt(tmp2); ans=Inf; //solve(1,3); for(int i=0;i<tmp1.size();i++){ for(int j=0;j<tmp2.size();j++){ solve(tmp1[i],tmp2[j]); } } printf("%d\n",ans); } return 0;}
总结:
- L题发现树同构模板有误。
XVI Open Cup named after E.V. Pankratiev. GP of SPB