A. Bingbong的化学世界 签到
题意：
给你苯环的结构，判断类型。
思路：
按照区别特判即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;
void Showball(){
vector<string> s(6);
for(int i=0;i<6;i++) cin>>s[i];
int cnt=0;
if(s[0][3]=='|') cnt++;
if(s[5][3]=='|') cnt++;
cout<<(!cnt?"o":(cnt==1?"m":"p"));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T=1;
if(cases) cin>>T;
while(T--)
Showball();
return 0;
}
B. Bingbong的数数世界 博弈
题意：
给定一个长度为 \(n\) 的排列，两个人进行删数游戏，A每轮必须删一个奇数，同时可以选择删除一个偶数。
每轮必须删一个偶数，同时可以选择删除一个奇数。A先手操作，无法操作的人失败。每个人采取最优策略，求获胜者。
思路：
因为长度为 \(n\) 的排列，所以奇数和偶数的数量是可以计算出的。那么最优策略自然就是每轮每个人都删除两个数。所以 \(n \% 4==0\) 时，先手比输。
代码：
void Showball(){
int n;
cin>>n;
if(n%4==0) cout<<"Bong\n";
else cout<<"Bing\n";
}
C. Bingbong的蛋仔世界
题意：
在一个 \(n*m\) 的地图上，有很多蛋仔，每个时刻每个蛋仔都可以向上、下、左、右四个方向移动一格。同时地图会向内缩小范围(最外圈消失，对应位置上的蛋仔会死亡)。蛋仔能够存活并且到达地图中心则为通关。求出有多少个蛋仔可以通关。
思路：
我们只需要求出每个蛋仔到达中心的最短距离即可。这个距离就是曼哈顿距离。\(d=|x_1-x_2|+|y_1-y_2|\)。
代码：
void Showball(){
int n,m,k;
cin>>n>>m>>k;
int minn=max(n/2,m/2);
int sx=n/2+1,sy=m/2+1;
int cnt=0;
while(k--){
int x,y;
cin>>x>>y;
int dis=abs(x-sx)+abs(y-sy);
if(dis<=minn) cnt++;
}
cout<<cnt<<endl;
}
D. Bingbong的奇偶世界 DP
题意：
给你一个长度为 \(n\) 的只包含字符 \(['0','9']\) 字符串 \(S\)。求出 \(S\) 中所有子序列中能够拼凑出一个不含前导0的偶数的子序列个数。
思路：
考虑 \(cnt\) 表示当前合法数字的个数。那么我们对当前的情况进行分类讨论：
1.当前位为偶数 那么之前所有的情况都可以拼接当前位构成新的合法情况，并且当前位本身也是一个合法情况。 维护cnt和ans
2.当前位为奇数 和偶数一样，但是不更新ans，只更新cnt
3.当前位为0 由于前导0的存在，所以0不能作为开头，因此维护cnt时需要-1。
代码：
void Showball(){
int n;
cin>>n;
string s;
cin>>s;
LL ans=0,cnt=0;
for(int i=0;i<n;i++){
if(s[i]=='0'){
ans=(ans+cnt+1)%mod;
cnt=(cnt*2)%mod;
}else if(s[i]&1){
cnt=(cnt*2+1)%mod;
}else{
ans=(ans+cnt+1)%mod;
cnt=(cnt*2+1)%mod;
}
}
cout<<ans<<endl;
}
E. Bingbong的字符串世界 子序列自动机
题意：
给你一个长度为 \(n\) 的字符串和一个整数 \(k\)， 定义好字符串：
1.字符串长度大于等于k。
2.字符串既包含ACCPET子序列，又不包含WA子序列。
求出 \(S\) 中有多少个子串时好字符串。
思路：
定义 \(nxt[N][27]\) 表示从第i个位置第一次出现j的下标
那么我们就可以求出任意子序列第一次出现的尾字母下标。
这样我们就可以维护ACCEPT和WA的子序列位置。
并且维护字符串长度大于等于k，更新答案即可。
代码：
int n,k;
string s;
//子序列自动机
int nxt[N][27];//表示从第i个位置第一次出现j的下标
void get_next(){
for(int i=n;i>=0;i--){
for(int j=0;j<26;j++){
if(i==n) nxt[i][j]=n;
else nxt[i][j]=nxt[i+1][j];
}
if(i!=n) nxt[i][s[i]-'A']=i;
}
}
int get_pos(int st,string s){
int first=1;
for(auto ch:s){
if(first) st=nxt[st][ch-'A'];
else st=nxt[st+1][ch-'A'];
first=0;
if(st==n) return st;
}
return st;
}
void Showball(){
cin>>n>>k>>s;
get_next();
string ac="ACCEPT",wa="WA";
LL ans=0;
for(int i=0;i<n;i++){
int r1=get_pos(i,ac),r2=get_pos(i,wa);
r1=max(r1,i+k-1);
ans=ans+max(r2-r1,0);
}
cout<<ans<<endl;
}
F. Bingbong的幻想世界 拆位+算贡献
题意：
思路：
看到异或，区间；想到拆位。因为异或运算每位之间互相不影响。通过拆位后，我们只用考虑 \(a_i\)的值只有0和1两种值。对于算贡献，题目是每次 \([l,r]\) 中选出 \(i,j\)然后进行计算，那么我们把顺序进行调换，转换成先找 \(i,j\) 再找有多少个区间包含 \(i,j\) ，乘法原理即可。
那么如果当前位为\(1\)，那么当前位之前的每个0都可以产生贡献，令下标为 \(k\)，则贡献则为 \((k+1)*(n-i)*(1<<bt)\)。那么提取公因式，只需要用两个变量来维护当前0下标之和，当前1下标之和即可。
代码：
void Showball(){
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
LL ans=0;
for(int bt=0;bt<=20;bt++){
LL v0=0,v1=0;
for(int i=0;i<n;i++){
if(a[i]>>bt&1){
ans=(ans+v0*(n-i)%mod*(1<<bt)%mod)%mod;
v1+=i+1;
}else{
ans=(ans+v1*(n-i)%mod*(1<<bt)%mod)%mod;
v0+=i+1;
}
}
}
cout<<2LL*ans%mod<<endl;
}
G. Bingbong的回文路径 LCA+哈希
题意：
给你一棵根节点为1的树。每个节点包含一个小写字母，接着给你 \(q\) 次询问，查询 \(u,v\) 之间最短路径形成的字符串是否是一个回文串。
思路：
提到最短路径，自然想到要求LCA，这里采用倍增求LCA。判断回文串，我们就可以采用维护正序，逆序的哈希值。直接比较哈希值是否相同即可。
题目唯一的难点就是合并哈希值，细节较多，这里详细展开一下。
降序哈希
\(h1[r]=a_1*p^{r-1}+a_2*p^{r-2}+a_3*p^{r-3}+...+a_{r-1}*p+a_{r}\)
\(h1[l-1]=a_1*p^{l-2}+a_2*p^{l-3}+a_3*p^{l-4}+...+a_{l-2}*p+a_{l-1}\)
\(h1[l,r]=h1[r]-h1[l-1]*p[r-l+1]\)
升序哈希
\(h2[r]=a_1+a_2*p+a_3*p^2+...+a_{r-1}*p^{r-2}+a_{r}*p^{r-1}\)
\(h2[l]=a_1+a_2*p+a_3*p^2+...+a_{l-1}*p^{l-2}+a_{l}*p^{l-1}\)
\(h2[l,r]=(h2[r]-h2[l-1])*p^{1-l}\)
然后拼接即可，注意还需要处理一下前半部分的幂次，逆元用快速幂即可。
代码：
vector<int> e[N];
LL depth[N],fa[N][25];
LL h1[N],h2[N],p[N];
string a;
void bfs(int root){
memset(depth,0x3f,sizeof depth);
depth[root]=1;
h1[root]=a[root]-'a'+1,h2[root]=a[root]-'a'+1;
queue<int> q;
q.push(root);
while(!q.empty()){
int u=q.front();
q.pop();
for(auto v:e[u]){
if(depth[v]>depth[u]+1){
depth[v]=depth[u]+1;
q.push(v);
fa[v][0]=u;
for(int i=1;i<=20;i++){
fa[v][i]=fa[fa[v][i-1]][i-1];
}
h1[v]=(h1[u]*P%mod+(a[v]-'a'+1))%mod;//降序哈希
h2[v]=(h2[u]+p[depth[v]-1]*(a[v]-'a'+1)%mod)%mod;//升序哈希
}
}
}
}
int lca(int a,int b){
if(depth[a]<depth[b]) swap(a,b);
for(int i=20;i>=0;i--){
if(depth[fa[a][i]]>=depth[b]){
a=fa[a][i];
}
}
if(a==b) return a;
for(int i=20;i>=0;i--){
if(fa[a][i]!=fa[b][i]){
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
LL qmi(LL a,LL b,LL mod){
LL res=1%mod;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
void Showball(){
int n;
cin>>n>>a;
a="?"+a;
for(int i=1;i<=n;i++){
int f;
cin>>f;
if(f){
e[f].pb(i);
e[i].pb(f);
}
}
p[0]=1;
for(int i=1;i<=n;i++) p[i]=(p[i-1]*P)%mod;
bfs(1);
depth[0]=0;
int m;
cin>>m;
while(m--){
LL u,v,p1,p2;
cin>>u>>v;
int f=lca(u,v);
//处理正序哈希
p1=(h2[u]-h2[fa[f][0]]+mod)%mod*qmi(p[depth[f]-1],mod-2,mod)%mod;
p2=(h1[v]-h1[f]*p[depth[v]-depth[f]]%mod+mod)%mod;
LL ans1=(p1*(p[depth[v]-depth[f]])%mod+p2)%mod;
//处理逆序哈希
p1=(h2[v]-h2[fa[f][0]]+mod)%mod*qmi(p[depth[f]-1],mod-2,mod)%mod;
p2=(h1[u]-h1[f]*p[depth[u]-depth[f]]%mod+mod)%mod;
LL ans2=(p1*(p[depth[u]-depth[f]])%mod+p2)%mod;
cout<<(ans1==ans2?"YES\n":"NO\n");
}
}