D.Bingbong的奇偶世界
思路1：数学计数
1、对于每一个偶数，那么以它结尾的数都是偶数，这样的数有多少，其实就是前i-1的数的组合：
对于前i-1个数，我们每次可以选0~i-1数，然后求和：C(i-1, 0) + C(i-1, 1) + C(i-1, 2) + .... + C(i-1, i-2) + C(i-1, i-1) == 2^(i-1);
2、因为题目要求不含前导0，所以我们要把含有前导0的组合减掉，经过发现我们可以得知：
对于每一个0 和它后面的偶数x，含有前导零的个数为: 假设0 和 x之间有n个数，sum = C(n,0) + C(n,1) + ... + C(n, n-1) + C(n,n) == 2^n;
3、问题在于如何快速的求得每个0 和 后面偶数的 sum，暴力枚举肯定超时的
4、我们可以找一下规律，看看能否在过程中就求出每个偶数的sum
5、注意点：用快速幂求2^n
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
typedef long long LL;
int quick_pow(int a, int k)
{
int res = 1 % mod;
while(k)
{
if(k & 1) res = (LL)res * a % mod;
a = (LL)a * a % mod;
k = k >> 1;
}
return res % mod;
}
int main()
{
//如何快速去重
//cout << quick_pow(2, 10) << endl;
int n;
string s;
cin >> n >> s;
s = " " + s;
LL res = 0, sum = 0;
for(int i = 1; i <= n; i ++)
{
int num = s[i] - '0';
if(num % 2 == 0)
{
int t = quick_pow(2,i - 1);
//cout << t << endl;
res = (res + t - sum + mod) % mod;//+ mod 防止变成负数
}
sum = (LL)(sum * 2) % mod;
if(num == 0)
{
sum ++;
}
}
cout << res << endl;
return 0;
}
思路2：dp的思想
1、我们记录前i个数的中偶数的个数ans和前i个数可以组成的合法数的个数cnt
2、如果s[i] 是奇数，ans(i) = ans(i-1), cnt = cnt * 2 + 1 cnt的算法，前i-1个数可以组成cnt个合法的数，每个组合加上s[i]可以变成新的数相当于扩大了一倍，再加上s[i] 本身。
3、如果s[i] 是偶数，ans(i) = ans(i-1) + cnt + 1, cnt = cnt * 2 + 1 ans 的算法，前i-1个数中组成的偶数，末尾加上一个偶数还是偶数，所以会新增加cnt + 1（s[i]本身）个偶数
4、如果s[i] 是0，特殊情况，考虑前导0问题，ans(i) = ans(i-1) + cnt + 1, cnt = cnt * 2,s[i]自己不能作为一个合法的前导数所以没有加1
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
typedef long long LL;
int main()
{
//如何快速去重
int n;
string s;
cin >> n >> s;
s = " " + s;
LL ans = 0, cnt = 0;
for(int i = 1; i <= n; i ++)
{
if(s[i] == '0')
{
ans = (ans + cnt + 1) % mod;
cnt = cnt * 2 % mod;
}
else if((s[i] - '0') % 2 == 1)
{
cnt = (cnt * 2 + 1) % mod;
}
else
{
ans = (ans + cnt + 1) % mod;
cnt = (cnt * 2 + 1) % mod;
}
}
cout << ans << endl;
return 0;
}
E Bingbong的字符串世界
思路：根据题解说是序列自动机问题
1、我们用next[i][j] 维护前i个字符中字符j第一次出现的位置，因为我们要维护第一次出现的位置，所以我们要从后向前遍历，没出现的字符我们标记为0。
2、我们通过find_x(int l, string aim) 来查找从l开始，第一次找到aim序列的位置。
3、最后我们进行子串的统计：r1 表示ac第一次出现的位置，r2表示wa第一次出出现的位置
（1） 如果r1 等于0，表示ac没有出现过，不符合题意。
（2）因为字符串的长度要大于等于k，所以右端点你至少为l+k-1，所以t = max（r1, l+k+-1），当l+K-1 大于n时也是不符合题意的。
（3）当r2 位于 r1 的右边，说明wa在字符串的最后，只要我们不包含wa的最后一个字符就是合法的，合法的字符个数应该为r2 - t。
（4）当r2 ==0时，说明字符串里面没有wa，这种字符串都是符合题意的。
总结: 本题的要点就是如何构造出next[i][j] 和 find_x()函数
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
string s;
int n, k;
int nnext[N][27];
int find_x(int l, string aim)
{
int ff = 1;
for(int j = 0; j < (int)aim.size(); j ++)
{
if(ff) l = nnext[l][aim[j] - 'A'];
else l = nnext[l + 1][aim[j] - 'A'];
ff = 0;
if(l == 0) return l;
}
return l;
}
int main()
{
cin >> n >> k >> s;
s = " " + s;
for(int i = n; i >= 1; i --)
{
for(int j = 0; j <= 25; j ++)
{
nnext[i][j] = nnext[i+1][j];
}
nnext[i][s[i] - 'A'] = i;
}
string ac = "ACCEPT", wa = "WA";
LL res = 0;
for(int i = 1; i <= n; i ++)
{
int r1 = find_x(i, ac), r2 = find_x(i, wa);
if(r1 == 0) continue;
if(i + k - 1 > n) continue;
int t = max(r1, i + k - 1);
if(r2 >= t)
{
res += r2 - t;
}
else if(r2 == 0)
{
res += n - t +1;
}
}
cout << res << endl;
return 0;
}
F Bingbong的幻想世界
思路：位运算
1、首先我们考虑，每一个数a[i]，我们可以考虑它对二进制位上的贡献。
2、考虑二进制数枚举到t位，数组枚举到第i个：
（1）当a[i]二进制第t位是1的时候，我们可以得出在[1, i-1]区间中在二进制的第t位上是0的数所贡献的区间的个数为v0个，a[i]后面的区间为（n-i+1）个，所以贡献即为v0 * （n-i+1） * （1 << t）,又因为一个区间需要两两异或运算，所以对于一对a[i]和a[j]需要计算两遍,故总贡献v0 * （n-i+1） * （1 << t） * 2
（2）对于是1的时候同理
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
typedef long long LL;
int a[N];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
}
int v1 = 0, v0 = 0, res = 0;
for(int t = 0; t <= 20; t ++)
{
int v0 = 0, v1 = 0;
for(int i = 1; i <= n; i ++)
{
if((a[i] >> t) & 1)
{
res = res + (LL)v0 * (n - i + 1) % mod * (1 << t) % mod;
res %= mod;
v1 = (v1 + i) % mod;
}
else
{
res = res + (LL)v1 * (n - i + 1) % mod * (1 << t) % mod;
res %= mod;
v0 = (v0 + i) % mod;
}
}
}
res %= mod;
cout << res * 2 % mod <<endl;
return 0;
}
京公网安备 11010502036488号