B-Card Game
具体的题目就不在这里详细的展开了，可以点击上方链接打开详细的去看一下。
题目类型：
这题是一个博弈/匹配问题，还隐藏着规则陷阱，其实只要看懂题目含义，将逻辑整理出来，也没有那么难。（注意看本题目给的范围，O（n2）一定是会超时的）
知识点：
组合数，数学，思维
解题思路：
核心推理一下规则（即得分的关键）：
-
A 赢了： A 得分，A 的牌丢弃，B 的牌不动。
-
B 赢了： B 得分（A不得分），B 的牌丢弃，A 的牌不动。
这题的关键来了：任何比
min(B)大的牌都有潜力得 1 分
假设小红手里最小的牌是 。如果小苯手里有一张牌
：
小苯可以一直等到小红出
的时候，出
。此时
，小苯得 1 分，
被移除了。但是
还在小红手里！ 小苯下一张牌还可以继续欺负这张 minb。
所以，最高得分
= 小苯手中大于
的牌的数量。
构造最高分的排列方案
为了拿到最高分 ：
- 小苯必须把所有能赢的牌（
）放在不能赢的牌（
）前面。
- 因为一旦“必输牌”出现在牌顶，小红的牌就会迅速耗尽，游戏强制结束。
所以，想要拿到最高分，小苯的排列必须满足：
前 张牌必须是那
张“大牌”，后
张牌必须是那
张“小牌”。
计算方案数：
既然位置已经固定了：前 个位置放
张大牌，后
个位置放
张小牌。
张大牌内部可以任意排列，方案数为
。
张小牌内部可以任意排列，方案数为
。
- 总方案数 =
。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const int mod = 998244353;
void slove()
{
int n,mn=2e5+10;
cin >> n;
vector<int> a(n);
vector<int> b(n);
for (auto &i : a) cin >> i;
for (auto &i : b)
{
cin >> i;
mn=min(mn,i);//找B数组中的最小值
}
int cnt=0;
for(auto i:a)
{
if(i>mn) cnt++;//记录A中比mn（B中数组最小数）大的个位数
}
int sum=1;
for(int i=1;i<=cnt;i++)
{
sum=(sum*(i%mod))%mod;
}
for(int i=1;i<=n-cnt;i++)
{
sum=(sum*(i%mod))%mod;
}
cout<<sum<<endl;
}
signed main()
{
ios;
int T;
cin >> T;
while (T--)
{
slove();
}
return 0;
}
G-Digital Folding_2026
题意:
题目类型：
披着数学外衣的构造题，贪心，思维
知识点：
stoi 函数：将字符串转成 int 整数。
stol 函数：将字符串转成 long 整数。
stoll 函数：将字符串转成 long long 整数。
使用时需要注意的是 stoi、stol、stoll 函数是 C++11标准 加入的，用 g++ 编译器编译时需要加参数：-std=c++11 原文链接：https://blog.csdn.net/d704791892/article/details/129706412
解题思路：
直观感觉——什么样的数反转后大
假设我们要比谁反转后的数字大：
-
A 拿出的数是：
反转后是
-
B 拿出的数是：
本质：
反转后的高位要尽可能大。
- 原数字的个位，反转后变成了最高位。
- 原数字的十位，反转后变成了第二高位。
结论：
原数字的最后一位，决定了反转后数字的第一位（最高位）。
我们要尽可能让原数字的末尾几位都是 9。
核心冲突——受限于区间
你手里最大的数是 。如果你想让
的末尾变成 9，你通常需要把
变小一点。
比如
：
- 想让末尾有一位 9： 最接近
且末尾是 9 的数是
。
- 想让末尾有两位 9： 最接近
。
- 想让末尾有三位 9： 最接近
。
注意： 这些变小后的数，必须还要
才有意义。
如何快速构造出“小于 且末尾有
个 9”的数？
万能公式： 候选数 = (r / 10^k) * 10^k - 1
举个例子：，
（我们要末尾有两个 9）：
（把末尾两位砍掉）
（末尾补零，得到一个整百的数）
（大功告成！ 得到了末尾全是 9 且最接近
的数）
总结：
- 不会超时：
也就 15 位数，我们每组数据只检查 16 个候选数，循环 16 次。
，总共才执行
次计算。计算机跑这个只需 0.001 秒。
- 不会漏解： 因为要让反转大，末尾必须多 9。我们穷举了所有“末尾
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const int mod = 998244353;
int cmp(int n)
{
string s = to_string(n); // 将数字转为字符串 "120"
reverse(s.begin(), s.end()); // 翻转"021"
return stoll(s); // 将字符串转为long long 整数（会自动去除前导0） 变为"21"
}
void solve()
{
int l, r;
cin >> l >> r;
int mx = cmp(r); // 先把r当作最大值
int p0 = 10;
for (int k = 1; k <= 15; k++) // 因为r的范围小于10的15次方
{
int x = r / p0 * p0 - 1;
if (x >= l)
mx = max(mx, cmp(x)); // 要比较这个数字在l的范围内
if (p0 > r / 10) // 如果p0*10比r还要大，那么减1一定是负数，，没有意义，可以提前结束
break;
p0 *= 10;
}
cout << mx << endl;
}
signed main()
{
ios;
int T;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
H-Blackboard
题意：
给定一个算式 。现在可以将其中一些
+ 替换为 |（按位或）。已知 | 的优先级高于 +。要求求出：有多少种替换方式，使得最终计算结果仍然等于原加法算式的总和 ？
知识点：
动态规划, 位运算, 双指针/滑动窗口, 前缀和
解题思路：
这题对我来说是真的难，你要去理解位运算的一些知识点，我理解的还不是很透彻，等我理清楚在把这里补上（可以先看我下面的代码）
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const int mod = 998244353;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
// dp[i]: 前i个数的合法方案数
// sum[i]: dp的前缀和
vector<int> dp(n + 1);
vector<int> sum(n + 1);
// 初始状态为1（即不改动全为+算一次）
dp[0] = 1;
sum[0] = 1;
int L = 1, mask = 0;
for (int i = 1; i <= n; i++)
{
while ((mask & a[i]) != 0) //(mask & a[i]) != 0为判断条件，当条件成立（即有数字二进制上有位相同时）为1，否则为0
{
mask ^= a[L];
L++;
}
mask |= a[i]; // 根据题意与当前数字相与
// 转移：dp[i] = sum(dp[L-1]...dp[i-1])
// 这里的区间是 [L-1, i-1]
int l = L - 1;
int r = i - 1;
if (l == 0)
{
dp[i] = sum[r];
}
else
{
dp[i] = (sum[r] - sum[l - 1] + mod) % mod;
}
// 更新前缀和
sum[i] = (sum[i - 1] + dp[i]) % mod;
}
cout << dp[n] << endl;
}
signed main()
{
ios;
int T;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
京公网安备 11010502036488号