【题解】2024牛客寒假算法基础集训营3
A、智乃与瞩目狸猫、幸运水母、月宫龙虾
题意
给两个字符串，判断首字母忽略大小写后是否相同。
技巧
你可以使用std库函数std::tolower来将大写转换为小写。相应的，对于字符操作，也存在std::tolower、std::toupper。
在算法竞赛中，涉及到英文字母的字符操作一般使用位运算和空格字符来做。在某些需求中比使用库函数更加灵活，比较经典的例如将大小写英文字母转换为小大写，一般使用c^=' ';来实现。
在ASSIC编码中，英文字母所对应二进制的第6位表示大小写，该位为0时表示大写，为1时表示小写。，空格字符的ASSIC编码又恰好为
。
char c='a';
if(c&' ')//判断是否为小写
if(~c&' ')//判断是否为大写
c|=' ';//转换为小写，等价于std::tolower
c^=' ';//如果原本是大写，转换为小写，原本是小写转换为大写。
c=(c|' ')^' ';//转换为大写字母，等价于std::toupper
核心代码
int main(int argc, char const *argv[])
{
int T;
char s[55], t[55];
read(T);
while (T--)
{
read(s, t);
println((s[0] | ' ') == (t[0] | ' ') ? "Yes" : "No");
}
return 0;
}
B、智乃的数字手串
如果你看到数据范围被骗去写搜索或者DP，请立即下载国家反诈中心APP。
题意
两个人轮流在环上取数，要求只能取走相邻奇偶性相同数字的其中一个。取数后可以进行某些操作改变顺序，不能操作的人输掉游戏。
题解
是奇数先手必胜，偶数后手必胜。
这个操作其实并没有卵用，把题目改成允许取数后重新排序也是一样的结果。
考虑游戏最终的结果，无论是谁不能取数，最终剩下的数字一定按照[奇,偶,奇,偶,...,奇,偶]排列，即长度为偶数。所以无论数字的内容是什么，两人的决策是什么，都不影响起始回合到终局回合的奇偶性。
核心代码
int main(int argc, char const* argv[])
{
int T, n, a;
read(T);
while (T--)
{
read(n);
println(n & 1 ? "qcjj" : "zn");
while (n--)read(a);
}
return 0;
}
C、智乃的前缀、后缀、回文
题意
给两个字符串，分割成四个前后缀，要求互相的前缀和后缀两两相同且为回文。
题解
看着复杂，但其实是字符串入门级题目，只要能够熟练使用任意一种字符串匹配相关的算法就可以做。
算法一：manacher
马拉车算法(manacher)可以用于求一个字符串的所有回文中心，以及其延伸的长度。所以我们可以很方便的实现判断某字符串子串是否为回文的接口。
接下来同时枚举的前缀和
的后缀，因为是回文，所以所以直接倒着匹配即可。然后记录所有能够完整匹配且前后缀为回文的位置。再反过来枚举
的前缀和
的后缀，使用类前缀和（前缀/后缀极值）的方法合并答案即可。
核心代码
int main()
{
int ans = -1;
vec_t<char, 1> s(MAXN), t(MAXN);
vec_t<int, 1> suf(MAXN);
int n, m;
read(n, m, s.data(), t.data());
if (n > m)
{
swap(n, m);
swap(s, t);
}
chino::manacherWrapper manacher(s.data());
int last = -1;
int flag = 1;
for (int i = 0; i < n; ++i)
{
if (t[i] != s[n - i - 1])flag = 0;
if (flag && manacher.isPalindrome(n - i - 1, n - 1))last = i + 1;
suf[n - i - 1] = last;
}
for (int i = 0; i + 1 < n; ++i)
{
if (s[i] != t[m - i - 1])break;
if (manacher.isPalindrome(0, i) && suf[i + 1] != -1)
{
ans = max(ans, ((i + 1) + suf[i + 1]) << 1);
}
}
println(ans);
return 0;
}
算法二：z-function(exkmp)
z-function(exkmp)可以预处理出字符串所有的后缀与目标字符串前缀是否匹配。由于本题的字符串是一个前缀回文，所以相当于从回文中心切开，然后让这个后缀与前缀进行一个字符串匹配，而这个地方恰好就是z-function(exkmp)ex数组的定义。接下来的过程就同算法一了。
算法三：kmp
按照题意，由于求的是的前缀和
的后缀匹配，所以直接将
在前
在后拼接到一起，发现问题变为，找到新字符串的一个子串，使得该子串既是一个前缀，同时也是一个后缀，并且前后缀匹配，这实际上就是KMP的Next数组定义，所以可以直接求Next数组。然后同理，再将
在前
在后拼接到一起，求Next数组。最后双指针合并两Next数组即可求出答案。
算法四：hash
本质和算法二相同、不讲了
算法五：后缀数组
原理同算法二、四，不讲了。
D、E、F chino's bubble sort and maximum subarray sum
题意
先交换相邻元素次，然后求最大子段和。
题解
easy
方法比较多，由于数据范围较小，所以你可以枚举所有交换的可能性，然后扫一遍求最大子段和。
或者考虑，先求最大子段和，在过程中考虑因为反正只能交换0-1次，那就必然是跳过一个负数在两端多加上一个正数。所以也可以贪心。
hard
基于easy版本的贪心思路，我们继续考虑交换操作只能发生在所选的最大子段和头尾两侧，不会在最大子段和的中间产生。（）
相邻交换具有不交叉性质，该性质可以在“模拟费用流”类算法中有所体现。
具体来讲，当存存在如图所示的情况时，如果AD等价，BC等价。那么交换时一定不交叉。（可以按网络流理解，相当于增广路时被取消）。
在已知交换不产生交叉的前提下，我们可以将问题拆成左右两部分，变为两个新的问题：
从左往右进行冒泡排序，至多进行次交换，如果需要选中某个数字，就将其冒泡排序到最右侧，否则冒泡排序交换到左侧。（这个过程是一个典型的二维01背包）
接下来从右往左做一遍，同理。
已知不交叉，所以可以枚举断点，然后枚举交换次数合并两
数组。
核心代码
const int MAXN = 10005;
const int MAXK = 1005;
const long long INF = 1LL << 60;
using namespace std;
long long dp[2][MAXK][MAXK];
long long pre[MAXN][MAXK];
long long suf[MAXN][MAXK];
long long a[MAXN];
int main()
{
int n, K;
vec_t<long long, 1> a(MAXN);
//这种超大数组不建议开vector，vec_t_create常数较大
read(n, K);
vread(a.data() + 1, a.data() + 1 + n);
auto dpf = [&n, &K, &a](auto &dp,auto&pre)
{
int cur=0;
for (int j = 0; j <= K; ++j)
{
for (int k = 0; k <= K; ++k)
{
dp[0][j][k]=dp[1][j][k]=-INF;
}
}
dp[cur][0][0] = 0;
for (int i = 1; i <= n; ++i)
{
cur^=1;
for (int j = 0; j <= K; ++j)
{
for (int k = 0; k <= K; ++k)
{
dp[cur][j][k]=-INF;
}
for (int k = 0; k <= K; ++k)
{
if (j - k >= 0)
dp[cur][j][k] = max(dp[cur][j][k], dp[cur^1][j - k][k]);//不取，消耗k的代价
if (k > 0)
dp[cur][j][k] = max(dp[cur][j][k], dp[cur^1][j][k - 1] + a[i]);//取，k++
}
pre[i][j]=-INF;
for (int k = 0; k <= K; ++k)
{
pre[i][j]=max(pre[i][j],dp[cur][j][k]);
}
}
}
};
//正着求dp，倒过来求idp
dpf(dp,pre);
reverse(a.data() + 1, a.data() + 1 + n);
dpf(dp,suf);
reverse(a.data() + 1, a.data() + 1 + n);
for (int i = 1; i <= n / 2; ++i)
{
for (int j = 0; j <= K; ++j)
{
swap(suf[i][j], suf[n - i + 1][j]);
}
}
vec_t<long long, 1> pre_max(K + 1, 0);
long long pre_sum = 0, ans = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= K; ++j)
{
ans = max(ans, pre_sum + suf[i][j] + pre_max[K - j]);
}
pre_sum += a[i];
for (int j = 0; j <= K; ++j)
{
pre_max[j] = max(pre_max[j], -pre_sum + pre[i][j]);
if (j > 0)
{
pre_max[j] = max(pre_max[j], pre_max[j - 1]);
}
}
}
//最后一个参与向右排序的情况，或许并不需要这个处理，是一段冗余代码
//因为显然，若最后一个参与排序，它一定是参与向左排序，向右排序无意义（如果不要就不动，反之向左排序）
for (int j = 0; j <= K; ++j)
{
ans = max(ans, pre_sum + pre_max[K - j]);
}
if (ans == 0)
{
ans = -INF;
for (int i = 1; i <= n; ++i)
{
ans = max(ans, a[i]);
}
}
println(ans);
return 0;
}
very hard
考虑线段树求合并逆序对时的情况。我们认为0表示不选这个数，1表示选这个数。
考虑如下这种情况，假设从左往右进行冒泡排序，0代表不选这个数，1代表选择这个数。
000000010101｜0101011111111111
总逆序对k=左侧区间的贡献+右侧区间的贡献+左边的1数目*右边的0数目。
显然则有k<=左边的1数目*右边的0数目。
令a=左边的1数目，b=右边的0数目。
则当a>时，b必须<
。
逆序对有两种求法：
①求0前面的1
②求1后面的0
dp[n][k][p][2]表示前n个数，当前代价为k，当前增量为p，左侧还是右侧区间。
则当前半段dp时，每碰到一个1，我们让p++，每碰到0，我们计算当前代价。当p=时停止。
对于右侧区间倒过来假定其增量为p=x，每次遇到0的时候p--，同时因为我们已知左侧有
个1是定值，所以还要再计算左右区间合并的代价。每次遇到1就计算右区间代价即可。
核心代码
template<typename T>
void check_max(T &x, const T &val)
{
x = max(x, val);
}
int main()
{
int n, K;
read(n, K);
vread(a + 1, a + 1 + n);
auto dpf = [&n, &K](auto &dp, auto &pre)
{
int p = 1, cur = 0;
while (p * p < K)++p;
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= K; ++j)
{
for (int k = 0; k <= p; ++k)
{
dp[cur][j][k][0] = dp[cur][j][k][1] = dp[cur ^ 1][j][k][0] = dp[cur ^ 1][j][k][1] = -INF;
}
}
}
dp[cur][0][0][0] = 0;
//前面取p个1切换阶段
//000000000...1010|1010...111111111
for (int i = 1; i <= n; ++i)
{
cur ^= 1;
for (int j = 0; j <= K; ++j)
{
for (int k = 0; k <= p; ++k)
{
dp[cur][j][k][0] = dp[cur][j][k][1] = -INF;
}
for (int k = 0; k <= p; ++k)
{
if (j >= k)
check_max(dp[cur][j][k][0], dp[cur ^ 1][j - k][k][0]);//不取，消耗k的代价
if (k > 0)
check_max(dp[cur][j][k][0], dp[cur ^ 1][j][k - 1][0] + a[i]);//取，k++
}
//先0后1，后效性问题
for (int k = 0; k <= p; ++k)
{
check_max(dp[cur][j][k][1], dp[cur][j][p][0]);
}
//必须首先确定p是一个常数c的值，否则结合时仍然是sqrt*sqrt=K的复杂度，不解决问题。
for (int k = 0; k <= p; ++k)
{
if (j >= k)
check_max(dp[cur][j][k][1], dp[cur ^ 1][j - k][k][1] + a[i]);//取，消耗k的代价
if (j > p && k < p)
check_max(dp[cur][j][k][1], dp[cur ^ 1][j - p][k + 1][1]);//不取，已知前面确定取p个，所以k--的同时，消耗p的代价
}
//统计合法的状态，dp[i][j][k][0]和dp[i][j][0][1]均为合法。（0阶段任意增量，1阶段必须保证增量为0）
pre[i][j] = dp[cur][j][0][1];
for (int k = 0; k <= p; ++k)
{
check_max(pre[i][j], dp[cur][j][k][0]);
}
}
}
};
//正着求dp，倒过来求idp
dpf(dp, pre);
reverse(a + 1, a + 1 + n);
dpf(dp, suf);
reverse(a + 1, a + 1 + n);
for (int i = 1; i <= n / 2; ++i)
{
for (int j = 0; j <= K; ++j)
{
swap(suf[i][j], suf[n - i + 1][j]);
}
}
vec_t<long long, 1> pre_max(K + 1, 0);
long long pre_sum = 0, ans = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= K; ++j)
{
ans = max(ans, pre_sum + suf[i][j] + pre_max[K - j]);
}
pre_sum += a[i];
for (int j = 0; j <= K; ++j)
{
pre_max[j] = max(pre_max[j], -pre_sum + pre[i][j]);
if (j > 0)
{
pre_max[j] = max(pre_max[j], pre_max[j - 1]);
}
}
}
//最后一个参与向右排序的情况，或许并不需要这个处理，是一段冗余代码
//因为显然，若最后一个参与排序，它一定是参与向左排序，向右排序无意义（如果不要就不动，反之向左排序）
for (int j = 0; j <= K; ++j)
{
ans = max(ans, pre_sum + pre_max[K - j]);
}
if (ans == 0)
{
ans = -INF;
for (int i = 1; i <= n; ++i)
{
ans = max(ans, a[i]);
}
}
println(ans);
return 0;
}
G、H、智乃的比较函数
easy
因为只有两个条件，所以可以用逻辑直接分情况讨论。
核心代码
int main(int argc, char *argv[])
{
int T, n;
read(T);
auto a = vec_t_create<int, 3, 3>(-1);
while (T--)
{
read(n);
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
a[i][j] = -1;
}
}
bool f=true;
while (n--)
{
int x, y, z;
read(x, y, z);
if(z==1&&a[y - 1][x - 1]==1)
{
f=false;
}
if(z==1&&a[x - 1][y - 1]==0)
{
f=false;
}
if(z==0&&a[x - 1][y - 1]==1)
{
f=false;
}
if(x==y&&z==1)
{
f=false;
}
a[x - 1][y - 1] =z;
}
println(f ? "Yes" : "No");
}
return 0;
}
hard
hard其实有两种做法的，一种是摁做，还是通过逻辑判断。不过还是有一定技巧的，就是构造bitflag，使用二进制位来表示该种情况是否存在可能性，1表示还具有可能性，0表示不可能，则可以设计如下的枚举类
enum BITFLAG : int
{
invalid = 0, // 没有合法关系
less = 1 << 0, // 严格小于
equal = 1 << 1, // 严格等于
greate = 1 << 2, // 严格大于
leq = less | equal, // 小于等于
geq = equal | greate, // 大于等于
neq = less | greate, // 不等于
full = less | equal | greate // 所有关系均可
};
核心代码
int main(int argc, char *argv[])
{
enum BITFLAG : int
{
invalid = 0, // 没有合法关系
less = 1 << 0, // 严格小于
equal = 1 << 1, // 严格等于
greate = 1 << 2, // 严格大于
leq = less | equal, // 小于等于
geq = equal | greate, // 大于等于
neq = less | greate, // 不等于
full = less | equal | greate // 所有关系均可
};
auto a = vec_t_create<int, 3, 3>(BITFLAG::invalid);
// 是否包含某种关系
auto contain_flag = [](auto x, auto flag)
{
return (x & flag) == flag;
};
int T, n;
read(T);
while (T--)
{
read(n);
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
// 初始状态，显然只有当x=y的时候才知道ax=ay，不然所有关系都可以。
a[i][j] = i == j ? BITFLAG::equal : BITFLAG::full;
}
}
while (n--)
{
int x, y, z;
read(x, y, z);
// 如果ax<ay，那么就知道ay>ax，发过来如果知道ax>=ay，也知道ay<=ax。
a[x - 1][y - 1] &= z ? BITFLAG::less : BITFLAG::geq;
a[y - 1][x - 1] &= z ? BITFLAG::greate : BITFLAG::leq;
}
bool flag = true;
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
for (int k = 0; k < 3; ++k)
{
auto x = a[i][j] & a[j][k] & a[k][i]; // a=b=c
auto y = a[i][j] | a[j][k] | a[k][i]; // not (a=b=c)
if (!contain_flag(x, BITFLAG::equal) && !contain_flag(y, BITFLAG::neq))
{
flag = false;
}
}
}
}
println(flag ? "Yes" : "No");
}
return 0;
}
这样说实话是比较自找麻烦的，还有另一种方法。
暴力枚举所有情况，看是否有符合所有约束条件的，如果存在至少一种情况能够符合所有的约束条件，就是合法的，否则不合法。
核心代码
int main()
{
vec_t<int, 2> v;
for (auto i = 0; i < 3; ++i)
{
for (auto j = 0; j < 3; ++j)
{
for (auto k = 0; k < 3; ++k)
{
v.push_back({i, j, k});
}
}
}
int T;
read(T);
while (T--)
{
vec_t<int, 1> f(v.size(), 1);
int n;
read(n);
while (n--)
{
int x, y, z;
read(x, y, z);
for (auto i = 0; i < f.size(); ++i)
{
if ((v[i][x - 1] < v[i][y - 1]) != z)
{
f[i] = 0;
}
}
}
println(*max_element(f.begin(), f.end()) ? "Yes" : "No");
}
return 0;
}
I chino's infinite infinite strings without xyz
题意
初始数组模23的情况下不停地做前缀和，问前个数组两两之间的
之和是多少
因为相当于求s串的n-1次前缀和，然后与所有过程中产生串的lcp。
题解
如果你OEIS到一个错误的数列，或者你认为有循环节，或者大于529无解，请下载国家反诈中心APP。
虽然实际上在代码中并没有体现卢卡斯定理、卷积、组合数，但是实际上这道题考的就是这些知识点。
所以先考虑，对一个数组求前缀和，本质为求恒函数的自卷积。
卷积后出现相当于组合数C(n,0),C(n,1),C(n,2)...C(n,m)...C(n,n)
因为模数为23，为小模数，考虑卢卡斯定理 C(n,m)=C(n/p,m/p)*C(n%p,m%p)
因为这个题是求一个数组，所以变量m其实是要枚举的，姑且只关注n，即C(n)=C(n/p)*C(n%p)。这个式子形似一个23进制的进制转换算法。
即观察到对于a=在模23下，求若干次前缀和的a[1],a[23],a[23*23]...a[23^k]可以表示一个23进制数
所以答案为求n-1在23进制下，各个数位的数字分段出现的次数*段长(段长为23^(k-1)*22)+前导a的贡献+s0的贡献。
核心代码
int main()
{
using Mint = chino::ModInt<998244353>;
long long n;
int m;
vec_t<char, 1> s(MAXN);
read(n, m, s.data());
if (n == 1)
{
println(0);
return 0;
}
Mint prea = 0ll;
for (auto i = 0; i < m; ++i)
{
prea += s[i] == 'a';
if (s[i] != 'a')break;
}
if (prea.get() == m)
{
println(-1);
return 0;
}
auto log23 = [](long long n)
{
long long ans = 0;
while (n)
n /= 23, ++ans;
return ans;
};
auto C2 = [](Mint n)
{
return n * (n - 1) / 2;
};
auto ans = (prea + 1) * C2(n);
auto lim = log23(n - 1);
auto sum = vec_t_create<Mint, 100, 3>(0);
auto val = vec_t_create<Mint, 100>(0);
long long base = 1;
for (auto i = 0; i < lim; ++i)
{
val[i] = base * 22;
base *= 23;
}
base = 23;
for (auto i = 0; i < lim; ++i)
{
sum[i][0] = (n - 1) / base; //group[cnt]
sum[i][1] = (n - 1) % base; //group[cnt]++
sum[i][2] = base; //total group
base *= 23;
}
for (auto i = 0; i < lim; ++i)
{
ans = (ans + C2(sum[i][0]) * (sum[i][2] - sum[i][1]) * val[i]);
ans = (ans + C2(sum[i][0] + 1) * sum[i][1] * val[i]);
ans = (ans + sum[i][0] * val[i]);
}
println(ans.get());
return 0;
}
J、智乃的相亲活动
题意
给定无向二分图，每个点随机选择对面集合中的一个有边相连的点，问所选点去重后个数的期望。
题解
经典高考问题
期望公式：
注意期望的加法公式并不要求变量与
是独立的。
无论和
是否存在一些互斥或者由于其他关系产生影响，你都可以通过这个公式计算。
虽然有点反直觉，但请务必记住：和的期望等于期望的和。
所以只要单独计算每个人成为心动男/女嘉宾的期望，直接求和就可以了。
以男嘉宾为例，答案为：，其中
表示第
个男嘉宾，
表示第
个女嘉宾，
表示第
个男嘉宾与第
个女嘉宾存在好感关系，
表示与第
个女嘉宾存在好感关系的男嘉宾数目。
核心代码
int main()
{
int n, m, k;
using Mint = chino::ModInt<int(1e9 + 7)>;
read(n, m, k);
auto g = vec_t_create<int, MAXN, 0>(0);
auto G = vec_t_create<int, MAXN, 0>(0);
Mint ans1(0), ans2(0);
for (int i = 1; i <= k; ++i)
{
int u, v;
read(u, v);
g[u].push_back(v);
G[v].push_back(u);
}
auto calc = [](int n, const vec_t<int, 2> &g, const vec_t<int, 2> &ig) -> Mint
{
Mint ans = 0;
for (int i = 1; i <= n; ++i)
{
Mint p(1);
for (auto &j: g[i])
{
p = p*(Mint(1) - Mint((long long) ig[j].size()).inverse());
}
ans = ans + 1 - p;
}
return ans;
};
println("modint");
println(calc(n, g, G).get(), calc(m, G, g).get());
return 0;
}
K、智乃的“黑红树”
题意
构造一颗二叉树，深度为奇数的节点有个深度为偶数的节点有
个，且二叉树结点要么同时拥有孩子，要么为叶节点。
有两种方法，bfs或者直接构造，直接构造更困难。所以这里推荐用bfs法。
算法一：bfs
创建两个队列，队列中存放当前作为黑色和红色的叶子节点，不断循环直到无法再往下多构造一层时终止。如果此时恰好二叉树满足条件，则输出，否则无解。
核心代码
struct solver_
{
int total{};
vec_t<int, 1> lch, rch;
int _b, _r;
void init(int b, int r)
{
_b = b;
_r = r;
lch = vec_t<int, 1>(b + r + 1, -1);
rch = vec_t<int, 1>(b + r + 1, -1);
}
bool _build(queue<int>& q_out, queue<int>& q_in, int& cnt)
{
if (!q_out.empty() && cnt >= 2)
{
auto root = q_out.front();
q_out.pop();
lch[root] = ++total;
q_in.push(total);
rch[root] = ++total;
q_in.push(total);
cnt -= 2;
return true;
}
return false;
}
int build()
{
queue<int>qb, qr;
total = 1;
_b--;
qb.push(1);
while (_build(qr, qb, _b) || _build(qb, qr, _r));
return !(_b | _r);
}
};
算法二：直接构造
考虑这么一个更简单的判定性问题，使用个黑、
个红点构造的可行性。
问题可以转化成，个节点完全二叉树，深度为偶数的节点最多有多少个、最少有多少个。合法的
如此，我们可以设计一个校验器检查某个构造步骤的合法性。
struct checker_
{
int get_sequence_length(int n)
{
return ((n + 1) / 2 - 1) / 3 + 1;
}
int get_sequence_begin(int n)
{
return ((n + 1) / 6 + 1) * 2 - 1;
}
int get_sequence_end(int n)
{
return get_sequence_begin(n) + 2 * (get_sequence_length(n) - 1);
}
bool legal(int a, int b)
{
if (a < 0 || b < 0 || !((a + b) & 1) || (b & 1))
{
return false;
}
int n = a + b;
return get_sequence_begin(n) <= a && a <= get_sequence_end(n);
}
} checker;
接下来我们想一种方式固定构造，由于题目限制只和深度有关，所以可以考虑用左子树递归扩展，右子树构造的方式。（因为两个子树等价，所以相当于递归构建的是二叉树的最长链，把它直接放到左子树）。接下来右子树其实只有两种情况，要么放一层，要么放两层。其他情况都可以被这两种情况表示。
核心代码
int build(int a, int b)
{
int root = ++total;
if (a == 1 && b == 0)return root;
// b,a-1
if (checker.legal(b - 1, a - 1))
{
lch[root] = build(b - 1, a - 1);
rch[root] = build(1, 0);
} else
{
lch[root] = build(b - 1, a - 3);
rch[root] = build(1, 2);
}
return root;
}
完整代码
#include <bits/stdc++.h>
using namespace std;
///------------------ c++ -------------------
void read()
{
}
void read(int &x)
{
scanf("%d", &x);
}
void read(long long &x)
{
scanf("%lld", &x);
}
void read(char *x)
{
scanf("%s", x);
}
void print(const int &x)
{
printf("%d", x);
}
void print(const long long &x)
{
printf("%lld", x);
}
void print(const char *x)
{
printf("%s", x);
}
///------------------ c++11 -------------------
template<typename T, std::size_t N>
struct _vec : public _vec<std::vector<T>, N - 1>
{
};
template<typename T>
struct _vec<T, 0>
{
using type = T;
};
template<typename T, std::size_t N>
using vec_t = typename _vec<T, N>::type;
template<typename T>
vec_t<T, 0> vec_t_create(const T &data)
{
return data;
}
template<typename T, size_t arg0, size_t... args>
vec_t<T, sizeof...(args) + 1> vec_t_create(const T &data)
{
return vec_t<T, sizeof...(args) + 1>(arg0, vec_t_create<T, args...>(data));
}
template<typename T>
void vread(T *begin, T *end)
{
for (T *i = begin; i != end; ++i)
{
read(*i);
}
}
template<typename T>
void print(std::vector<T> &v)
{
for (auto i = 0; i < v.size(); ++i)
{
print(v[i]);
if (i + 1 != v.size())putchar(' ');
}
}
template<typename T>
void read(std::vector<T> &v)
{
for (auto &i: v)
{
read(i);
}
}
template<typename T, typename... Args>
void read(T &&arg0, Args &&...args)
{
read(arg0);
read(args...);
}
void println()
{
}
template<typename T, typename... Args>
void println(T &&arg0, Args &&...args)
{
print(arg0);
if (sizeof...(args))
{
printf(" ");
println(args...);
} else
{
printf("\n");
}
}
//-----------------------------------------
struct solver_
{
int a_, b_;
bool legal;
int total{};
vec_t<int,1> lch, rch;
void init(int a, int b)
{
a_ = a;
b_ = b;
legal = checker.legal(a, b);
if (legal)
{
lch = vec_t<int,1>(a + b + 1, -1);
rch = vec_t<int,1>(a + b + 1, -1);
}
}
int build(int a, int b)
{
int root = ++total;
if (a == 1 && b == 0)return root;
// b,a-1
if (checker.legal(b - 1, a - 1))
{
lch[root] = build(b - 1, a - 1);
rch[root] = build(1, 0);
} else
{
assert(checker.legal(b - 1, a - 3));
lch[root] = build(b - 1, a - 3);
rch[root] = build(1, 2);
}
return root;
}
void solve()
{
if (!legal)return;
total = 0;
build(a_, b_);
}
struct checker_
{
int get_sequence_length(int n)
{
return ((n + 1) / 2 - 1) / 3 + 1;
}
int get_sequence_begin(int n)
{
return ((n + 1) / 6 + 1) * 2 - 1;
}
int get_sequence_end(int n)
{
return get_sequence_begin(n) + 2 * (get_sequence_length(n) - 1);
}
bool legal(int a, int b)
{
if (a < 0 || b < 0 || !((a + b) & 1) || (b & 1))
{
return false;
}
int n = a + b;
return get_sequence_begin(n) <= a && a <= get_sequence_end(n);
}
} checker;
};
int main()
{
int T, a, b;
solver_ solver;
read(T);
while (T--)
{
read(a,b);
solver.init(a, b);
if (solver.legal)
{
println("Yes");
solver.solve();
for (int i = 1; i <= a + b; ++i)
{
println(solver.lch[i], solver.rch[i]);
}
} else
{
println("No");
}
}
return 0;
}
L、M智乃的36倍数
easy
暴力枚举，或者只需要统计
、
、
这三种情况即可
核心代码
int main() {
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&x);
a[x]++;
}
printf("%d\n",a[3]*a[6]+a[7]*a[2]+a[10]*a[8]);
return 0;
}
hard
实际上有两种思路，一种是利用模的性质，另一种不用。如果不知道模的性质，可以考虑36实际上就是4的倍数和9的倍数。通过小学数奥，我们知道4的倍数就是后两位可以被4整除，9的倍数就是所有数位的和可以被9整除所以可以开桶统计，然后枚举桶的情况合并即可。
另一种做法，根据模的性质，两个数字求和模36实际上就是每一部分分别模36求和后再模36，所以可以直接开桶统计每个数字模36后是几，然后36还有个特殊性质，即不论多少位的，只要
，剩下的数都为28。所以只需要知道它是不是10位数即可。
核心代码
int main(int argc, char const *argv[])
{
int n;
long long ans = 0;
read(n);
vec_t<long long, 1> a(n);
vread(a.data(), a.data() + n);
auto calc = [&]()
{
auto sum = vec_t_create<long long, 36>(0);
for (auto &i : a)
{
for (int j = 0; j < 36; ++j)
{
if ((j * (i < 10LL ? 10LL : 28LL) + i) % 36 == 0)
{
ans += sum[j];
}
}
sum[i % 36]++;
}
};
calc();
reverse(a.begin(), a.end());
calc();
println(ans);
return 0;
}
投递传音控股等公司10个岗位 >
查看5道真题和解析