A:Bingbong的化学世界
链接
题目描述
🌙“上帝把银河揉碎，让一片化作星光一片化作月亮
剩余的全部掉进我的梦里，化作了你”
BingbongBingbongBingbong正在学习“苯环”。
已知苯环二元取代物分为：o-甲乙苯，m-甲乙苯和p-甲乙苯
分子结构图如图所示:
1
2
3
4
5
6
7
| ...|... ....... ...|...
..._... ..._... ..._...
../.\.. ../.\/. ../.\..
..|.|.. ..|.|.. ..|.|..
..\_/\. ..\_/\. ..\_/..
....... ....... ...|...
m-甲乙苯 o-甲乙苯 p-甲乙苯
|
为了能更好的了解苯环,Bingbong现在需要精确的判断给定的分子结构图为哪种类型的苯环二元取代物，请您帮帮他。
输入描述:
1
| 共6行7列，输入保证为题面描述中的二元取代物的其中一种。。
|
输出描述:
1
| 一个字符,'m,o,p'中的其中一种,表示给定的分子结构式属于哪种苯环二元取代物。
|
示例1
输入
复制
1
2
3
4
5
6
| ...|...
..._...
../.\..
..|.|..
..\_/..
...|...
|
输出
复制
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include <iostream>
using namespace std;
char a[10][10];
int main()
{
for (int i = 1; i <= 6; i++) {
for (int j = 1; j <= 7;j ++) cin >> a[i][j];
}
if (a[6][4] == '|') cout << "p";
else if (a[1][4] == '|') cout << "m";
else cout << 'o';
}
|
B：Bingbong的数数世界
链接：https://ac.nowcoder.com/acm/contest/78807/B
来源：牛客网
题目描述
⭐星星是银河递给月亮的情书，你是世间赠于我的恩赐。
Bing和Bong在玩消数游戏，游戏规则如下：
初始时给定一个数字n，然后会有编号为1，2，3…n的卡牌共n张位于桌面上。
Bing每轮必须选择一个奇数消除，然后可以同时消除一个偶数(此步可以选择做或者不做）。
Bong每轮必须选择一个偶数消除，然后可以同时消除一个奇数(此步可以选择做或者不做）。
Bing先手操作，谁无法操作时即输掉了游戏，若两人都采取最优策略，请您来告诉他们最终的胜者。
输入描述:
1
2
3
| 第一行一个整数T(1≤T≤2×105),表示数据组数。
接下来T行，每行一个整数n(),含义如题面所示。
|
输出描述:
1
| 输出共T行，每行一个字符串。BingBingBing或者Bong,表示谁赢得了游戏的胜利。
|
示例1
输入
复制
输出
复制
说明
1
2
3
4
5
6
7
8
| 当n=1时，数字有1。
第一轮BingBingBing可以选择消除数字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赢得游戏。
|
思路
通过打表可知，但是具体的原因，数学推导并不清楚。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include <iostream>
using namespace std;
int main()
{
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
if (n % 4 == 0) cout << "Bong\n";
else cout << "Bing\n";
}
}
|
C：略
D：Bingbong的奇偶世界
链接
题目描述
🌙若逢新雪初霁，满月当空，下面平铺着皓影，上面流转着亮银，而你带笑地向我步来。
月色与雪色之间，你是第三种绝色。
Bingbong有一个长度为n的数字字符串S，该字符串仅包含[0,9的数字。
Bingbong想要从中挑选出若干个字符，然后按照其相对顺序重新拼接而成一个数字，使其是一个无前导000的偶数。
例如：当n=3,S=100。 其包含的偶数数字有0,0,10,10,100。而00是不符合条件的，因为其含有前导0。
由于字符串实在是太长了，他一个人数不过来，请您帮他计算一下该字符串中含有的偶数方案总数， 结果对109+7取模。
输入描述:
1
2
3
| 第一行一个整数n() ，表示字符串S的长度。
第二行一个长度为n的字符串S,保证输入只含[0,9]的数字。
|
输出描述:
示例1
输入
复制
输出
复制
示例2
输入
复制
输出
复制
思路
DP
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <iostream>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
int n,a1=1,a2=0,ans=0;
string s;
cin>>n>>s;
for(int i=0;i<n;i++){
if(s[i]=='0'){
(ans+=a2+1)%=mod;
a2=a2*2%mod;
}
else{
if((s[i]-'0')%2==0)
(ans+=a1+a2)%=mod;
(a2+=a1+a2)%=mod;
}
}
cout<<ans<<"\n";
return 0;
}
|
F：Bingbong的幻想世界
链接
题目描述
世界之大，遇见你
如同星辰相撞，闪耀璀璨
🌙我什么时候能与月色相比，穿过重重山河相拥你
Bingbong有一个长度为n数组a。
对于一个区间[l,r]的权值www定义为:
⊕:位运算中的按位异或
现在需要求出数组a中所有非空子区间的权值之和，结果对109+7取模。
输入描述:
1
2
3
| 第一行一个整数n(1≤n≤2×105)，代表数组长度。
第二个n个整数，a1,a2,...,an(0≤ai≤106)。
|
输出描述:
示例1
输入
复制
输出
复制
思路
代码一（暴力之最，O(n^4)）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <iostream>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL res;
int a[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
for (int k1 = i; k1 <= j; k1++) {
for (int k2 = i; k2 <= j; k2++) {
res += a[k1] ^ a[k2];
}
}
}
}
cout << res;
}
|
代码二（贡献法，基于贪心的思想,O(nlogn)）
思路
当a[i]二进制的第t位是1的时候，我们可以得出在[1,i−1]区间中在二进制的第t位上是0的数所贡献的区间个数为v0个,且影响a[i]的区间个数为之后的n−i+1个，所以贡献即为v0×(n−i+1)×(1<<t)，又因为一个区间需要两两异或运算，所以对于一对ai和aj需要计算两遍,故总贡献为v0×(n−i+1)×(1<<t)×2。
0同理计算即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
#define i64 long long
int main() {
int n;
cin >> n;
vector<i64>a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
i64 ans = 0;
for (int t = 0; t <= 20; t++) {
i64 v0 = 0;
i64 v1 = 0;
for (int i = 1; i <= n; i++) {
if ((a[i] >> t) & 1) {
ans = (ans + v0 * (n - i + 1) % mod * (1 << t) % mod * 2 % mod) % mod;
v1 = (v1 + i) % mod;
} else {
ans = (ans + v1 * (n - i + 1) % mod * (1 << t) % mod * 2 % mod) % mod;
v0 = (v0 + i) % mod;
}
}
}
cout << ans ;
return 0;
}
|