1.A+B Problem
本题的主要内容是：有八个相同的七段码数位显示器，每个显示器有7个灯管，编号为i的灯管有p[i]的概率被点亮。设第一排显示的四位十进制数为 A，第二排显示的四位十进制数为 B。
其中：最终所有显示器均有灯管被点亮——说明每个显示器都会表示为一个数；
所有显示器显示的数字都是合法的——每个数表示的都是0-9；
A+B=C；
1.用二进制状态压缩表示每个数字对应的七段码的点亮模式：
如果灯管亮，则对应二进制中的1，不亮则对应0。
LL s[10] = {
0b1110111, // 0: 灯管1,2,3,5,6,7亮
0b0100100, // 1: 灯管3,6亮
0b1011101, // 2: 灯管1,3,4,5,7亮
0b1101101, // 3: 灯管1,3,4,6,7亮
0b0101110, // 4
0b1101011, // 5
0b1111011, // 6
0b0100101, // 7
0b1111111, // 8
0b1101111 // 9
};
2.求逆元
由于该题中所有情况都是独立的，只会涉及到类似p%的相乘问题，所以只需要计算100的逆元即可。
3.最后，求出每个数字的概率，以及A,B取不同值时的概率，得到结果。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL MOD = 998244353;
LL T, C;
LL p[10], res[10]; // p: 存储7个灯管的点亮概率，res: 存储0-9每个数字被正确显示的概率
LL s[10] = {0b1110111, 0b0100100, 0b1011101, 0b1101101,
0b0101110, 0b1101011, 0b1111011, 0b0100101,
0b1111111, 0b1101111}; // 从低位到高位分别对应灯管1-7
LL qmi(LL a, LL b, LL p) //快速幂函数，计算 a^b % p
{
LL res = 1;
while (b)
{
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int main()
{
scanf("%lld", &T);
LL ni = qmi(100, MOD - 2, MOD);//计算100在模MOD下的逆元(费马小定理）
while (T--)
{
scanf("%lld", &C);
// 读取7个灯管的点亮概率
for (int i = 0; i < 7; i++)
{
LL x;
scanf("%lld", &x);
// 将百分比转换为模意义下的概率：x/100 ≡ x * ni (mod MOD)
p[i] = x * ni % MOD;
}
// 计算每个数字（0-9）被正确显示的概率
for (int i = 0; i < 10; i++)
{
res[i] = 1;
for (int j = 0; j < 7; j++) // 遍历7个灯管
{
// 检查数字i的第j个灯管是否需要点亮,点亮则乘以p[j],否则乘以（1-p[j]）
if (s[i] >> j & 1)
res[i] = res[i] * p[j] % MOD;
else res[i] = res[i] * (1 - p[j] + MOD) % MOD;
}
}
// 计算最终答案
LL ans = 0;
for (int A = 0; A <= C; A++) //依次遍历可能的A
{
LL a1, b1, c1, d1; //暴力分解A的每一位（高位补0）
a1 = A % 10, b1 = (A / 10) % 10, c1 = (A / 100) % 10, d1 = (A / 1000) % 10;
// 计算A被正确显示的概率
LL p_A = res[a1] * res[b1] % MOD * res[c1] % MOD * res[d1] % MOD;
int B = C - A; //继续分解B
// 计算B被正确显示的概率
a1 = B % 10, b1 = (B / 10) % 10, c1 = (B / 100) % 10, d1 = (B / 1000) % 10;
LL p_B = res[a1] * res[b1] % MOD * res[c1] % MOD * res[d1] % MOD;
ans = (ans + p_A * p_B % MOD) % MOD;//结果加上此时AB同时发生的概率
}
printf("%lld\n", ans); //最终输出结果
}
return 0;
}
2.Card Game
本题主要内容：小苯正在和小红玩卡牌游戏。比较两人当前手牌中的最前一张，对应数字大的那一方得一分并将该张牌从自己手牌移除；另一方不得分，手牌也不变。随后进入下一轮。直到两人之中有人没有牌时，游戏结束。
因此小苯希望自己的得分尽可能多，也就是他的牌移除的尽可能多。
仔细思考，只要小苯的牌大于小红的牌中的最小值 添加公式 时，就可以通过合理的排序将其移除掉。
那么小苯大于小红的牌中的最小值 添加公式 的牌必须放在前面，小于的必须放在后面。
因此小苯排列自己的牌的顺序就是前面一部分‘大牌’的全排列乘以后一部分‘小牌’的全排列。
即 ( !) * (
!) 即为所求的结果。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=2e5+100;
const long long MOD=998244353;
int T,n;
int a[N],b[N];
long long f(int x) //返回x的阶乘 %MOD
{
if(x==0) return 1;
long long res=1;
for(int i=1;i<=x;i++)
res=res*i%MOD;
return res;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<n;i++) scanf("%d",&b[i]);
int mi=1e9;
for(int i=0;i<n;i++)
mi=min(mi,b[i]); //找到数组b中的最小值
int cnt=0;
for(int i=0;i<n;i++)
if(a[i]>mi)
cnt++; //统计a中有多少大于b中最小值的
long long ans=f(cnt)*f(n-cnt)%MOD; //计算最终结果，前后两部分的阶乘相乘
printf("%lld\n",ans);
}
return 0;
}
3.Array Covering
本题主要内容：进行将（ l , r ）开区间（一定注意是开区间）的内的所有数都变为区间端点值的较大者。求出数组总和的最大值。
由于是开区间，那么除了两个端点未必会变成最大值（除非两个端点就是这个数组的最大值），其余数一定会变成这个数组的最大值。
例如[1,2,4,3,2],通过选择（1,3）和（3,5）进行操作，就会将数组变为[1,4,4,4,2],最终结果就是：数组最大值*（n-2）+数组的两个端点。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=5e5+100;
int n;
long long a[N];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
long long ma=-1e9;
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
if(ma<a[i])
ma=a[i];//寻找最大值
}
printf("%lld\n",ma*(n-2)+a[0]+a[n-1]);//计算结果
}
return 0;
}
4.Sequence Coloring
本题主要内容：给定一个长度为 n 的数字序列，有白色也有黑色，选择其中至多 k 个白色元素染红。
每秒会执行以下内容：对于第 𝑖 个元素 添加公式 如果是红色，那么从 𝑖 到 𝑖 + 添加公式
间的白色都会染红。每个红色染红都是同时进行的。黑色不会被染红。
根据题意可以得到：对于所用最小染色时间t，那么 t+1 时间内也可以完成染色，而t-1时间内绝对不可以完成染色。因此时间 t 是单调的，可以采用二分法，二分时间来求取答案。特别地：只有当白色的个数小于所给的k时，是可以用 0 秒完成涂色的，其他情况均不可以。并且染色时间最长也不会超过n。因此二分区间为 1 到 n , 0为特解。
对于二分的检验函数check( int x ):可以通过从前到后依次遍历白色，在预处理中计算每个位置能到达的最远位置，通过维护手动染红的数量和红色传播的时间：从第一个白色数字开始跳到当前红色能到达的最远位置：i = ne[i] ,
如果 i >= n，结束;
如果当前点无法向右传播,就找下一个白色数字，手动染红，不断循环重复。
如果 t == x,就找下一个白色数字，手动染红，循环以上步骤。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e5 + 100;
int T, n, k;
int a[N], ne[N]; // a: 存储输入数组, ne: 存储每个位置能到达的最远位置
// 检查在给定的时间限制x秒内，是否能用不超过k个手动染红的点感染所有白色数字
bool check(int x)
{
int idx = 0;
// 跳过开头的黑色数字（值为0的位置）
while (idx <= n && a[idx] == 0) idx++;
int num = 1; // 手动染红的点的数量，初始为1（第一个白色数字）
int t = 0; // 当前红色数字已经传播的时间
// 开始模拟传播过程
while (idx <= n)
{
t++; // 经过一秒
idx = ne[idx]; // 跳到当前红色数字能到达的最远位置
// 如果已经覆盖到数组末尾，结束循环
if (idx >= n)
break;
// 当前位置无法再向右传播（可能是黑色数字或无法传播更远）
if (idx == ne[idx])
{
idx++; // 尝试下一个位置
// 跳过黑色数字
while (idx <= n && a[idx] == 0) idx++;
// 如果找到白色数字，手动染红它
if (idx <= n)
{
t = 0; // 新起点，传播时间重置为0
num++; // 手动染红点数加1
}
}
// 当前红色数字已经传播了x秒，需要新的起点
else if (t == x)
{
idx++; // 尝试下一个位置
// 跳过黑色数字
while (idx <= n && a[idx] == 0) idx++;
// 如果找到白色数字，染红它
if (idx <= n)
{
t = 0; // 新起点，传播时间重置为0
num++; // 染红点数加1
}
}
}
// 判断染红的点数是否不超过k
return num <= k;
}
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d %d", &n, &k);
int cnt = 0; // 统计白色数字的个数
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (a[i] != 0) cnt++;
// ne数组：当前位置能到达的最远位置
ne[i] = max(ne[i - 1], a[i] + i);
}
// 特殊情况：如果白色数字个数不超过k，可以直接全部手动染红，时间为0
if (cnt <= k)
{
printf("0\n");
continue; // 继续下一个测试用例
}
// 二分查找最小时间
int l = 1, r = n;
while (l < r)
{
int mid = (l + r) / 2;
if (check(mid))
r = mid;
else
l = mid + 1;
}
// 验证最终找到的时间是否可行，如果不可行则输出-1
if (!check(l)) l = -1;
printf("%d\n", l); // 输出答案
}
return 0;
}
5.Block Game
主要内容是: 将万能方块从方块序列的最左侧插入，同时最右侧的第 𝑛 个方块会被挤出这一行，成为新的万能方块。然后寻找从左往右数第一个方块上的数字加上最终的万能方块上的数字的总和的最大值。
本题可以先通过小规模的模拟找到规律：
当数组为1 ，2, 3时，k=4；此时结果res=1+4; 变为---> 数组4， 1 ，2, k=3,res=4+3;
---> 数组3， 4 ，1, k=2, res = 3 + 2; ---> 数组2， 3，4, k=1, res = 2 + 1;
可以得出其实本质就是将k插入数组后面：1, 2，3, 4，求两个相邻的数的加和并找出最大值（注意4和1也算相邻）
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 100;
int n, t, k;
int a[N];
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
// 初始化最大和为第一个元素加上万能方块的数字
int ma = k + a[0];
// 将万能方块放在数组末尾，形成长度为n+1的循环数组
a[n] = k;
// 遍历所有相邻元素对，找出最大的相邻元素和
for (int i = 0; i < n; i++)
ma = max(ma, a[i] + a[i + 1]); // 更新最大相邻元素和
// 输出最大的相邻元素和
printf("%d\n", ma);
}
return 0;
}
6.Permutation Counting
7.Digital Folding
本题主要内容：求 l 到 r 区间的数翻转之后的最大值
可以考虑到：在相同数位下，末位9越多，翻转后的值越大,而翻转之后数位多的一定大，所以因此可以尝试将 r 的某些低位变为 9 来获得更大的翻转值。
可以通过 ：r - r%（10的倍数）-1实现
例如：1000010 ----> 1000010-1000010 %10 - 1 == 1000009 通过翻转得到9000001，以此类推.............
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL t, l, r;
// 函数 f: 计算数字 n 翻转后去除前导0的值
LL f(LL n)
{
LL res = 0;
while (n > 0)
{
res = res * 10 + n % 10;
n /= 10;
}
return res;
}
// 函数 solve: 找出区间 [l, r] 中所有数字翻转后的最大值
LL solve()
{
LL ma = f(r); // 初始化为右边界 r 的翻转值
// 尝试将 r 的某些低位变为 9 来获得更大的翻转值
// t 是 10 的幂次，用于定位要修改的位
for (LL t = 1; t <= r; t *= 10)
{
// 计算将 r 在 t 位上的数字减1，低位全变为9的数
LL tmp = r - r % t - 1;
// 检查这个数是否在区间 [l, r] 内
if (tmp >= l)
ma = max(ma, f(tmp)); // 更新最大值
}
return ma; // 返回找到的最大翻转值
}
int main()
{
scanf("%lld", &t);
while (t--)
{
scanf("%lld %lld", &l, &r);
printf("%lld\n", solve());
}
return 0;
}
8.Blackboard
本题主要内容：将一部分符号‘+’变成符号‘|’ ，让该新式子与原式子的答案一样，有多少种不同的方法。
由于本题：我们认为 or 运算符的优先级大于加法运算 ‘+’，
因此表达式实际上被分割成若干连续段：每个段内全部进行按位或运算，段与段之间进行加法运算。
由于‘|’与‘+’的性质我们可以得出：
对于任意一个连续子段 [l,r]，记其按位或值为 O，和为 T。总有 O≤T，因为按位或不会进位，而加***进位。等号成立当且仅当该子段中所有数的二进制表示互不重叠，即任意两个数在同一二进制位上不会同时为 1（没有进位发生）。
因此，一段的或值等于其和，等价于该段内所有数的二进制位互不重叠。
因此本题可以采用DP的方法：
定义 dp[i] 表示考虑前 i 个数（即 添加公式 到 添加公式
的子序列，有多少种分割方式使得表达式的值等于这 i 个数的和）。
转移方式：我们枚举最后一段的起点 j+1（即最后一段为 [j+1,i]），那么前 j 个数的分割方式有 dp[j] 种，并且需要满足最后一段的或值等于该段的和（即二进制位互不重叠）。因此： 其中区间 [j+1,i] 满足二进制位互不重叠。
但此过程的复杂度是O（ ）的，会TLE。要考虑优化。
如果区间 [L,i] 满足二进制位互不重叠，那么它的任何子区间也一定满足条件。因此，对于固定的 i，存在一个最左位置 L，使得区间 [L,i] 满足条件，而任何更小的左端点都会导致冲突。那么所有合法的 j 正好是L - 1 ≤ j ≤ i - 1。
我们只需要如果我们能快速求出每个 i 对应的 L，就可以用前缀和 O(1) 转移。
本题一定要用pre[N]数组对a[i]=0这种情况进行预处理，否则会TLE。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL N = 2e5 + 100, MOD = 998244353;
LL T, n;
LL a[N], s[N], dp[N], pre[N]; // a: 输入数组, s: dp前缀和, dp: 动态规划数组, pre: 前一个非零位置索引
int main()
{
scanf("%lld", &T);
while (T--)
{
scanf("%lld", &n);
int last = 0; // 记录上一个非零元素的位置，初始化为0
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
pre[i] = last;
if (a[i] != 0)
last = i;
}
// 初始化dp[1]表示空序列的合法方案数为1
dp[1] = 1;
// 初始化前缀和数组
s[1] = dp[1];
for (int i = 1; i <= n; i++)
{
int j = i; // 从当前位置开始向前查找
LL sum = 0; // 记录当前累积的按位或值
// 条件：j > 0（未到开头）且 sum & a[j] == 0（当前数字与累积的二进制位没有重叠）
for (; j > 0 && (sum & a[j]) == 0; j = pre[j])
sum |= a[j]; // 将当前数字的二进制位合并到sum中
// 循环结束时，j是最后一个冲突位置，即[j+1, i]区间内所有数字二进制位互不重叠
dp[i+1] = (s[i] - s[j] + MOD) % MOD;
s[i+1] = (s[i] + dp[i+1]) % MOD;
}
printf("%lld\n", dp[n+1]);
}
return 0;
}
9.AND vs MEX
本题主要内容：从区间 [ l , r ] 中选择若干个（至少一个）不同的整数，将这些整数的 按位与 加入集合，求没有出现在集合中的最小非负整数的最大值是多少。
显而易见：AND运算的结果永远不会超过 r ，则答案的最大值为 r + 1.
定义highbit（）函数，找寻某个数的最高位 1 所在的位置。
对不同的 l 和 r 需要分情况讨论:
- l 等于0的时候， 集合中能取到所有的 [0,r ]的整数，因此答案为 r + 1
- l > 0时 并且 l 和 r 的最高位相同时，任意多个数字的 AND 结果在最高位仍为 1，不会出现等于 0 的情况， 因此答案为 0。
-
highbit( r ) ≥ highbit( l ) + 2 时，取
,构造二进制低 highbit( l )+1 位全 1 ,
显而易见： 都在区间里面，将其与M进行AND，可以得到
的所有整数，再单独选取区间内每个数字，得到 [l , r ] 的所有整数。
由此可知，区间覆盖 [0,R]，答案为 R+1。
4.highbit( r ) = highbit( l ) + 1时 ，取 ，与
的每个数字做 AND，
可得到 的所有整数。
L 的二进制表示中，从最高位开始连续 1 的位段可以构造出一个下限值 min，使得通过 AND 可以得到 [min , l] 的所有整数。
若这几部分覆盖了 [0, r ]，则答案为 r +1；否则存在间隙，答案为间隙的最小值。
#include <iostream>
#include <algorithm>
using namespace std;
int T;
int l, r;
// 求 x 的二进制最高位1的位置
int highbit(int x)
{
// 从高位向低位扫描
for (int j = 30; j >= 0; j--)
if (x >> j & 1) // 检查第j位是否为1
return j;
return -1; // x为0时返回-1
}
int main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d %d", &l, &r);
int h1 = highbit(l), h2 = highbit(r);
//如果 l=0 或 R的最高位比L的最高位至少高2位，此时可以构造出0到R的所有数字，答案为R+1
if(l == 0 || h2 >= h1 + 2)
{
printf("%d\n", r+1);
continue;
}
// 如果l和r的最高位相同（且l>0） 此时所有数字最高位都是1，AND结果不可能为0，答案为0
else if(h1 == h2)
{
printf("0\n");
continue;
}
// R的最高位恰好比L的最高位高1位
else if(h2 == h1 + 1)
{
// 通过AND运算可以得到的区间 [0, r - 2^{h2}] 的MEX候选值
int res = r - (1 << h2) + 1;
// 计算L自身能通过AND构造出的最小数字mi
// 即L的二进制中从最高位开始连续1的部分对应的值
int mi = 0;
for (int j = h1; j >= 0; j--)
{
if ((l >> j) & 1) // 如果L的第j位为1
mi += (1 << j); // 累加该位的值
else
break; // 遇到第一个0就停止
}
// 判断两个区间是否能覆盖 [0, R]
// 如果 mi <= res，说明两部分区间有重叠或连接，可以覆盖0到R
// 否则存在间隙，答案为间隙的最小值res
if (mi <= res)
printf("%d\n", r+1);
else
printf("%d\n", res);
}
}
return 0;
}
10.MST Problem
11.Constructive
本题主要内容：构造字典序最小的，长度为 n 的数组满足：所有数字均为正整数 , 所有数字互不相同 , 所有数字的和等于所有数字的乘积。
显而易见：当n = 1时，结果数组为 ：1
当 n = 2时，不存在该数组
当 n = 3时，结果数组为：1， 2 ，3
当 n 添加公式 4 时，作为乘积与和差距最小的结果：1 2 3 4 ，其和为10，乘积为24。已经差距过大，其他情况的差距只能越来越大。
因此 n 添加公式 4均无解。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=200;
int n;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
if( n == 1)
printf("YES\n1\n");
else if( n == 3) printf("YES\n1 2 3\n");
else printf("NO\n");
}
return 0;
}
12.Need Zero
本题主要内容: 找到目标 x ，使得x与n的个位乘积等于0 或者 10。
n的个位 t 只有0-9，这十种情况：t==0 x 直接取最小值 1 就可以。
t == 2 、4、6、8的时候 x 取 5
t == 5 的时候 x取 2
其他情况 x 直接取10即可。
代码如下:#include <iostream>
#include <algorithm>
using namespace std;
const int N=5e5+100;
int n;
long long a[N];
int main()
{
scanf("%d",&n);
int t=n%10;
if(t==0) printf("1\n");
else if(t==2 || t==4 || t==6 || t==8)
printf("5\n");
else if(t==5)
printf("2\n");
else printf("10\n");
return 0;
}
京公网安备 11010502036488号