A.Bingbong的化学世界
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
🌙“上帝把银河揉碎，让一片化作星光一片化作月亮
剩余的全部掉进我的梦里，化作了你”
Bingbong正在学习“苯环”。
已知苯环二元取代物分为：o-甲乙苯，m-甲乙苯和p-甲乙苯
分子结构图如图所示:
...|... ....... ...|... ..._... ..._... ..._... ../.\.. ../.\/. ../.\.. ..|.|.. ..|.|.. ..|.|.. ..\_/\. ..\_/\. ..\_/.. ....... ....... ...|... m-甲乙苯 o-甲乙苯 p-甲乙苯
为了能更好的了解苯环,Bingbong现在需要精确的判断给定的分子结构图为哪种类型的苯环二元取代物，请您帮帮他。
输入描述:
共6行7列，输入保证为题面描述中的二元取代物的其中一种。(输入的符号均已在样例中给出)。
输出描述:
一个字符,'m,o,p'中的其中一种,表示给定的分子结构式属于哪种苯环二元取代物。 示例1
输入
...|... ..._... ../.\.. ..|.|.. ..\_/.. ...|...
输出
p
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<list>
#include<deque>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f,mod=1e9+7,M=N*2;
typedef long long LL;
typedef pair<int,int>PII;
void solve(){
char s[7][8];
for(int i=1;i<=6;i++)
for(int j=1;j<=7;j++){
cin>>s[i][j];
}
if(s[6][4]!='|'){
if(s[1][4]=='|') cout<<"m";
else cout<<"o";
}else cout<<"p";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int _=1;
//cin>>_;
while(_--) solve();
return 0;
}B.Bingbong的数数世界
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
⭐星星是银河递给月亮的情书，你是世间赠于我的恩赐。
Bing和Bong在玩消数游戏，游戏规则如下：
初始时给定一个数字n，然后会有编号为1，2，3...n的卡牌共n张位于桌面上。
Bing每轮必须选择一个奇数消除，然后可以同时消除一个偶数(此步可以选择做或者不做）。
Bong每轮必须选择一个偶数消除，然后可以同时消除一个奇数(此步可以选择做或者不做）。
Bing先手操作，谁无法操作时即输掉了游戏，若两人都采取最优策略，请您来告诉他们最终的胜者。
输入描述:
第一行一个整数T(1≤T≤2×10^5),表示数据组数。 接下来T行，每行一个整数n(1≤n≤10^9),含义如题面所示。
输出描述:
输出共T行，每行一个字符串。Bing或者Bong,表示谁赢得了游戏的胜利。
示例1
输入
3 1 2 4
输出
Bing Bing Bong
说明
当n=1时，数字有1。 第一轮Bing可以选择消除数字1，然后选择不消除偶数。第二轮Bong无法操作，Bing赢得游戏。 当n=2时，数字有1,2。 第一轮Bing可以选择消除数字1，然后消除偶数2。第二轮Bong无法操作，Bing赢得游戏。 当n=4时，数字有1,2,3,4。 第一轮Bing可以选择消除数字1，然后消除偶数2。第二轮Bong选择数字4，消除奇数3。第三轮Bing无法操作，Bong赢得游戏。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<list>
#include<deque>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f,mod=1e9+7,M=N*2;
typedef long long LL;
typedef pair<int,int>PII;
int n;
void solve(){
cin>>n;
if(n%4) cout<<"Bing"<<"\n";
else cout<<"Bong"<<"\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int _;
cin>>_;
while(_--) solve();
return 0;
}C.Bingbong的蛋仔世界
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
🌙你站在桥上看风景，看风景的人在楼上看你。
明月装饰了你的窗子，你装饰了别人的梦。
蛋仔派对深受Bingbong喜爱，但是他玩游戏一向很菜，特别是在生存战中总落入下风，以下是某生存关的规则：
在万米高空有一个平行于地面且大小为n∗m的地图砖块，以俯视角度观看时，从上往下依次为第1~n行，从左往右依次为第1~m列，这个地图的特性是每个单位时间过后最外圈的砖块都会掉落，站在上面的蛋仔会因为踩空而摔落无尽的深渊,导致游戏失败。
形式上来说，若当前还未掉落砖块的总行数row≥3时，则当前的第1行和第row行的砖块会在下一个单位时间掉落，row减少2,否则row保持不变，列同理，可参考样例理解。
在0时刻总共有k只蛋仔位于此地图上，第i只蛋仔的坐标为(xi,yi)，他们会以每个单位时间一格的速度向四个方向移动或者选择不移动，具体描述为如果当前在(x,y),那么下一个位置可以是(x−1,y),(x+1,y),(x,y−1),(x,y+1)或者(x,y),游戏胜利的标志为蛋仔移动到地图的中央，坐标为(n/2+1,m/2+1),保证n,m均为奇数。好奇的Bingbong想要知道这关共有多少个蛋仔通过此关，请您帮他计算一下。
注意：
1.一个位置允许多个蛋仔同时存在。
2.砖块掉落后对于地图中央参数的n,m均为初始值，保持不变。
输入描述:
第一行包含3个整数n(1≤n＜500),m(1≤m＜500),k(1≤k≤n∗m),表示地图的行列大小和蛋仔数量。 接下来k行，每行2个整数x,y,第i行的数表示第i只蛋仔位于地图上的坐标。
输出描述:
一个整数，表示最终通过的蛋仔数量。
示例1
输入
3 3 3 2 2 1 1 2 1
输出
2
说明
初始时刻蛋仔所处位置如下：
第一只蛋仔由于已经位于地图中央砖块，所以通过此关。
第二只无论向下还是向右移动都会因为最外圈红色部分的砖块掉落而摔入无尽的深渊，所以此只蛋仔游戏失败。
第三只蛋仔可以选择向右跳一步，通过此关。
示例2
输入
1 5 3 1 1 1 5 1 2
输出
3
说明
初始时刻蛋仔所处位置如下：
第一秒过后333只蛋仔位置和砖块掉落状态如图所示：
第二秒过后333只蛋仔位置和砖块掉落状态如图所示：
所以最终333只蛋仔全部通关。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<list>
#include<deque>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f,mod=1e9+7,M=N*2;
typedef long long LL;
typedef pair<int,int>PII;
int n,m,k;
void solve(){
cin>>n>>m>>k;
int dx=n/2+1,dy=m/2+1;
int ans=0;
while(k--){
int x,y;
cin>>x>>y;
int xx=abs(x-dx),yy=abs(y-dy);
if(xx+yy<=max(n/2,m/2)) ans++;
}
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int _=1;
//cin>>_;
while(_--) solve();
return 0;
}D.Bingbong的奇偶世界
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
🌙若逢新雪初霁，满月当空，下面平铺着皓影，上面流转着亮银，而你带笑地向我步来。
月色与雪色之间，你是第三种绝色。
Bingbong有一个长度为n 的数字字符串S，该字符串仅包含[0,9]的数字。
Bingbong想要从中挑选出若干个字符，然后按照其相对顺序重新拼接而成一个数字，使其是一个无前导0的偶数。
例如：当n=3,S=100。 其包含的偶数数字有0,0,10,10,100, 。而00是不符合条件的，因为其含有前导0。
由于字符串实在是太长了，他一个人数不过来，请您帮他计算一下该字符串中含有的偶数方案总数， 结果对10^9+7取模。
输入描述:
第一行一个整数n(1≤n≤2×10^5)n,表示字符串S的长度。
第二行一个长度为n的字符串S,保证输入只含[0,9]的数字。
输出描述:
一个整数，表示最后含有的偶数方案总数。
示例1
输入
3 100
输出
5
示例2
输入
5 12345
输出
10
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<list>
#include<deque>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f,mod=1e9+7,M=N*2;
typedef long long LL;
typedef pair<int,int>PII;
int n;
string s;
void solve(){
cin>>n>>s;
int res=0,cnt=1,w=0;
for(int i=0;i<s.size();i++){
if((s[i]-'0')%2==0){
res=(res+cnt)%mod;
res=((res-w)%mod+mod)%mod;
}
if(s[i]=='0') w=(w*2+1)%mod;
else w=w*2%mod;
cnt=cnt*2%mod;
}
cout<<res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int _=1;
//cin>>_;
while(_--) solve();
return 0;
}E.Bingbong的字符串世界
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
⭐“星星会暗，月亮会有一天找不到踪迹
即使没有遇见在银河，和你相遇本身就很浪漫了。”
ACCEPT 或者是 WA 这是一个值得深思的问题！
Bingbong认为一个字符串TTT是“好字符串”需要满足以下条件：
1.字符串的长度∣T∣≥k。
2.字符串T既包含ACCEPT子序列且不包含WA子序列。
现在给定一个长度为n的字符串S,Bingbong想知道字符串S中包含多少个子串是“好字符串”。
一个一个数Bingbong认为很浪费时间,于是他请作为编程高手的您来解决这个问题。
子序列定义：在数学中，某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。
例如：S=“ABCDE" ,其中子序列可为ACE,ABCDE等。
子串定义：字符串中任意个连续的字符组成的子序列称为该串的子串(子串可以为空)。
例如：S=“ABCDE" ,其中子串可为ABC,ABCDE或者为空,但不能是AC,因为其两个字符在原串中不连续。
输入描述:
第一行2个整数n(6≤n≤2×10^5),k(6≤k≤n)。表示字符串的长度和好字符串长度的限制。 第二行一个长度为n的字符串,保证输入仅有大写字母构成。
输出描述:
一个整数,表示给定字符串中有少个子串是“好字符串”。
示例1
输入
9 6 WACCEPTTA
输出
3
说明
好字符串为：ACCEPT,ACCEPTT ACCEPTTA。 而像WACCEPT不是好字符串,因为其还有WA的子序列。
示例2
输入
6 6 ACCEPT
输出
1
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<list>
#include<deque>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f,mod=1e9+7,M=N*2;
typedef long long LL;
typedef pair<int,int>PII;
int f[N][26];
int n,k;
string s,ac="ACCEPT",wa="WA";
void init(){
for(int i=0;i<26;i++) f[n][i]=-1;
for(int i=n-1;i>=0;i--){
for(int j=0;j<26;j++)
f[i][j]=f[i+1][j];
f[i][s[i]-'A']=i;
}
}
int v_find(int l,string str,int len){
bool first=true;
for(int i=0;i<len;i++){
if(first) l=f[l][str[i]-'A'];
else l=f[l+1][str[i]-'A'];
first=false;
if(l==-1) return l;
}
return l;
}
void solve(){
cin>>n>>k>>s;
init();
LL ans=0;
for(int i=0;i<n;i++){
int l1=v_find(i,ac,6),l2=v_find(i,wa,2);
if(l1==-1) continue;
if(l2==-1) l2=n;
l1=max(l1,i+k-1);
ans+=max(l2-l1,(LL)0);
}
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int _=1;
//cin>>_;
while(_--) solve();
return 0;
}F.Bingbong的幻想世界
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
世界之大，遇见你
如同星辰相撞，闪耀璀璨
🌙我什么时候能与月色相比，穿过重重山河相拥你
Bingbong有一个长度为n数组a。
对于一个区间[l,r]的权值w定义为:
:位运算中的按位异或
现在需要求出数组a中所有非空子区间的权值之和，结果对10^9+7取模。
输入描述:
第一行一个整数n(1≤n≤2×10^5)，代表数组长度。 第二个n个整数，a1,a2,...,an(0≤ai≤10^6)。
输出描述:
一个整数，表示最后的答案。
示例1
输入
6 1 1 4 5 1 4
输出
422
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<list>
#include<deque>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f,mod=1e9+7,M=N*2;
typedef long long LL;
typedef pair<int,int>PII;
int n,a[N];
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans=0;
for(int i=0;i<=20;i++){
int w[2]={0,0};
for(int j=1;j<=n;j++){
int t=(a[j]>>i)&1;
int res=(LL)(n-j+1)*w[(1^t)]*(1<<i)%mod;
ans=(ans+res)%mod;
w[t]=(w[t]+j)%mod;
}
}
cout<<ans*2%mod;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int _=1;
//cin>>_;
while(_--) solve();
return 0;
}G.Bingbong的回文路径
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
⭐“我画了你身边每一个人，但却没有画你。我觉得你亮得耀眼，使我的目光无法停留。”
Bingbong 有一棵有根树，根节点为 1，总共有 n 个节点。树中的节点通过 n−1 条无向边相连，每条边的权重为 1。
树中的每个节点包含一个小写字母。Bingbong 将选择从节点 u 开始，并在选择最短路径的情况下到达节点 v。他想知道他所走路径形成的字符串是否是一个回文串。由于他会进行多次行走，您需要回答多个查询。
输入描述:
第一行包含一个整数n(1≤n≤10^5)，表示节点的数量。 第二行包含n个小写字母，其中第i个字母表示第i个节点上的小写字母。 第三行包含n个整数，其中第i个数字ai(1≤ai≤i−1)表示第i个节点的父节点，对于根节点ai=0。 第四行包含一个整数q(1≤q≤10^5)，表示查询的数量。
接下来是q行，每行包含两个整数u和v，表示一个查询的起点和终点。
输出描述:
输出q行，每行包含一个字符串。如果查询的起点到终点的路径连接形成一个回文串，则输出"YES"，否则输出"NO"。
示例1
输入
5 bbaaa 0 1 1 2 2 3 2 3 4 3 5 3
输出
NO YES YES
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<list>
#include<deque>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f,mod=1e9+7,M=N*2,P=13331;
typedef long long LL;
typedef pair<int,int>PII;
void solve(){
int n;
cin>>n;
vector<char>a(n+1);
vector<int>e[n+1];
vector<vector<int>>f(n+1,vector<int>(32,0));
vector<int>p(n+1);
vector<int>s(n+1);
vector<int>g(n+1);
vector<int>d(n+1,1e9);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
int fa;
cin>>fa;
e[fa].push_back(i);
e[i].push_back(fa);
}
p[0]=1;
for(int i=1;i<=n;i++){
p[i]=p[i-1]*P%mod;
}
auto bfs=[&](int root){
queue<int>q;
q.push(root);
d[root]=0;
s[root]=a[root];
g[root]=a[root];
while(!q.empty()){
auto t=q.front();
q.pop();
for(int i=0;i<e[t].size();i++){
int j=e[t][i];
if(d[j]<=d[t]+1) continue;
d[j]=d[t]+1;
q.push(j);
f[j][0]=t;
for(int k=1;k<=31;k++){
f[j][k]=f[f[j][k-1]][k-1];
}
s[j]=(s[t]+p[d[j]]*(a[j]-0)%mod)%mod;
g[j]=(g[t]*P%mod+a[j]-0)%mod;
}
}
};
bfs(1);
d[0]=-1;
auto LCA=[&](int u,int v)->int{
if(d[u]<d[v]) swap(u,v);
for(int i=31;i>=0;i--){
if(d[f[u][i]]>=d[v]){
u=f[u][i];
}
}
if(u==v) return u;
for(int i=31;i>=0;i--){
if(f[u][i]!=f[v][i]){
u=f[u][i];
v=f[v][i];
}
}
u=f[u][0];
v=f[u][0];
return u;
};
auto ksm=[&](int a,int b)->int{
int ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
};
auto cal=[&](int u,int v,int fa)->int{
int p1=(s[u]-s[fa]+mod)%mod;
p1=p1*ksm(p[d[fa]],mod-2)%mod;
p1=(p1+a[fa])%mod;
p1=(p1*p[d[v]%mod-d[fa]]+mod)%mod;
int p2=(g[v]-g[fa]*p[d[v]-d[fa]]%mod+mod)%mod;
return (p1+p2)%mod;
};
int q;
cin>>q;
while(q--){
int u,v;
cin>>u>>v;
int fa=LCA(u,v);
int ans1=cal(u,v,fa);
int ans2=cal(v,u,fa);
if(ans1==ans2) cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int _=1;
//cin>>_;
while(_--) solve();
return 0;
}
