A
题解
找到所有连续1的区间, 每个连续1的区间的贡献为区间长度len / 3(向上取整)
找到连续1的区间同时记录区间左右边界,方便二分
题目给出L, R
ans = 通过二分找到,L ~ R之间的所有连续1区间贡献之和(用前缀和) + 两个端点是否在连续1区间内的贡献之和
代码
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
struct node
{
int x, l, r, sum;
}s[N];
char str[N];
int cnt;
int n, m;
int bound(int x, bool st)
{
int l = 0, r = cnt + 1;
s[0].l = 0, s[r].r = n + 1;
while (l < r)
{
int t;
if (!st)
{
int mid = l + r >> 1;
if (s[mid].l > x) r = mid;
else l = mid + 1;
}
else
{
int mid = l + r + 1 >> 1;
if (s[mid].r < x) l = mid;
else r = mid - 1;
}
}
return l;
}
int main()
{
scanf("%d%d%s", &n, &m, str + 1);
//找到连续1的个数并记录,同时记录连续1的左端点和右端点
//每个连续1的贡献为连续1的个数x/3向上取整
for (int i = 1, j = 1; i <= n; )
{
int res = 0;
while (str[j] == '1')
{
res ++;
j ++;
}
if (j > i) s[++ cnt] = {res / 2 + res % 2, i, j - 1}, i = j;
else i ++, j ++;
}
//前缀和
for (int i = 1; i <= cnt; i ++ ) s[i].sum = s[i - 1].sum + s[i].x;
while (m -- )
{
int L, R, ans = 0;
scanf("%d%d", &L, &R);
//二分找到L, R之间有多少个连续1区间,前缀和计算出中间的总贡献
int a = bound(L, 0), b = bound(R, 1);
ans = s[b].sum - s[a - 1].sum;
//判断两端的贡献
int p = ans, u = 0;
if (a >= 1 && s[a - 1].l <= L && s[a - 1].r >= L)
u += (s[a - 1].r - L + 1);
if (b <= cnt - 1 && s[b + 1].l <= R && s[b + 1].r >= R)
u += (R - s[b + 1].l + 1);
p += u / 2 + u % 2;
//如果两端无贡献且中间无连续1区间,则确实没贡献
if (p == ans && b < a) {printf("%d\n", (R - L + 1) / 3); continue;}
//如果两端有贡献或者中间有贡献,则区间长度 / 3 - 贡献值
ans = p;
printf("%d\n",(R - L + 1) / 3 - ans < 0 ? 0 : (R - L + 1) / 3 - ans);
}
return 0;
}
D
题意
找到l~r间符合二进制下1的个数==后缀0的个数的数
题解
用字典树写的
后面再更
屎山代码
#include <iostream>
#include <cstring>
using namespace std;
int a, b;
int id, ans, sum;//岔路口
int tr[2 * 40][3], idx;
int id_1[2 * 40], sz_1[2 * 40], dep[2 * 40];//id_1上一个1的位置, sz_1上面1的个数, dep该点的深度
void insert(int x)
{
int p = 0, cnt = 0, pre = 0;
for (int i = 31, j = 1; i >= 0; i --, j ++)
{
int t = x >> i & 1;
if (!tr[p][t]) tr[p][t] = ++ idx;
else id = tr[p][t], sum = sum * 2 + t;
p = tr[p][t];
dep[p] = j;
sz_1[p] = cnt;
id_1[p] = pre;
if (t) cnt ++, pre = p;
}
}
bool dfs(int i, int p, bool st, int sum)
{
if (!p) return false;
if (!st)
{
if (!i && 32 - dep[p] + 1 == sz_1[p] + 2)
{
ans = sum + (1 << (32 - dep[p]));
return true;
}
if (!i && 32 - dep[p] + 1 >= sz_1[p] + 4)
{
ans = sum + (1 << (32 - dep[p])) + (1 << (sz_1[p] + 2));
return true;
}
}
else
{
if (i && 32 - dep[p] + 1 + dep[p] - dep[id_1[p]] - 1 == sz_1[p])
{
ans = sum;
return true;
}
if (i && 32 - dep[p] + 1 >= sz_1[p] + 3)
{
ans = sum + (1 << (sz_1[p] + 1));
return true;
}
}
sum += (i << (32 - dep[p]));
if (tr[p][0]) p = tr[p][0], i = 0;
else p = tr[p][1], i = 1;
return dfs(i, p, st, sum);
}
bool judge(int a)
{
int cnt = 0;
int x = a;
while (x)
{
cnt ++;
x -= (x & -x);
}
if ((1 << cnt) == (a & -a)){printf("%d\n", a); return true;}
return false;
}
void sovle()
{
memset(tr, 0, sizeof tr);
memset(id_1, 0, sizeof id_1);
memset(sz_1, 0, sizeof sz_1);
id = ans = sum = idx = 0;
scanf("%d%d", &a, &b);
if (judge(a)) return; if (judge(b)) return;
if (a == b) {puts("-1"); return;}
insert(a); insert(b);
int i, j;
int t1 = tr[id][0], t2 = tr[id][1];
if (tr[t1][0]) t1 = tr[t1][0], i = 0;
else t1 = tr[t1][1], i = 1;
if (tr[t2][0]) t2 = tr[t2][0], j = 0;
else t2 = tr[t2][1], j = 1;
if (dfs(i, t1, 0, (sum * 2) << (32 - (id + 1)))) {printf("%d\n", ans); return;}
if (dfs(j, t2, 1, (sum * 2 + 1) << (32 - (id + 1)))) {printf("%d\n", ans); return;}
puts("-1");
}
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
sovle();
}
return 0;
}
L
题意
俩个字符串s, t
求s的最长子序列
且该序列与t的任意公共子序列长度<= 1
题解
这个序列几个性质:
1、序列中前面字符已经在t中出现了,那么后面的字符一定不能出现在t中
所以我们可以根据t预处理出字符a后面不能出现那些字符b(记为 : ban(a, b))
for (int i = m; i >= 1; i -- )
{
for (int j = 0; j < 26; j ++ )
if (t_is[j]) ban[t[i] - 'a'][j] = true;
t_is[t[i] - 'a'] = true;
}
2、没有出现在t中的字符,可以直接添加进序列中
定义dp状态与转移方程:
dp(i, j) : 前1~i子串中, 后缀为j(出现在t中的), 符合条件的最长序列长度
dp(i, j) :
1) 当s[i]不在t中, 直接添加就行(就当这些字符不存在)dp(i - 1, j) + 1;
2) 当s[i]可以放在j后面时, dp(i - 1, j) + 1;
3) 不放s[i], dp(i - 1, j);
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5e5 + 10;
char s[N], t[N];
bool t_is[N], ban[N][26];
int dp[N][26];
int main()
{
scanf("%s%s", s + 1, t + 1);
int n = strlen(s + 1), m = strlen(t + 1);
//预处理出哪些b不能放到哪些a后
for (int i = m; i >= 1; i -- )
{
for (int j = 0; j < 26; j ++ )
if (t_is[j]) ban[t[i] - 'a'][j] = true;
t_is[t[i] - 'a'] = true;
}
for (int i = 1; i <= n; i ++ )
{
//当s[i]不在t中, 直接添加就行(就当这些字符不存在)
if (!t_is[s[i] - 'a'])
for (int j = 0; j < 26; j ++ )
dp[i][j] = dp[i - 1][j] + 1;
else
{
//初始化
dp[i][s[i] - 'a'] = 1;
//不放s[i]
for (int j = 0; j < 26; j ++ )
dp[i][j] = dp[i - 1][j];
//当s[i]可以放在j后面时
for (int j = 0; j < 26; j ++ )
{
if (!ban[j][s[i] - 'a'])
dp[i][s[i] - 'a'] = max(dp[i][s[i] - 'a'], dp[i - 1][j] + 1);
}
}
}
int res = 0;
for (int i = 0; i < 26; i ++ ) res = max(res, dp[n][i]);
printf("%d\n", res);
return 0;
}
d用爆搜组合枚举代码贼短
赛时我给队友说思路,他码了160多行,都快码疯了
d用next_permutation能少写不少代码
我没用这个