2026 牛客寒假集训营-6
1. K-小L的游戏1
题目描述
小 L 的科研毫无进展，于是他开始和 fallleaves01 玩游戏。
的变量
上进行。小 L 和 fallleaves01 轮流对
小 L 的回合：将
；
。
，游戏立即结束，否则继续进行下一轮。现在小 L 想请问你，最后一次操作是谁进行的？
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数
代表数据组数，每组测试数据描述如下：
在一行上输入三个正整数
，表示小 L 的增量、fallleaves01 的增量、目标阈值。
输出描述
将所有测试数据的答案按顺序拼接，在一行内连续输出（中间不加空格或换行）。如果最后一次操作是小 L 进行的，输出
；如果最后一次操作是 fallleaves01 进行的，输出
。
解题思路
找到边界 res = (floor(z/(m+n)))*(m+n)，判断一下最后一次
AC 代码
void solve(){
cin>>m>>n>>z;
int k=z/(m+n);
int res=k*(m+n);
if(res<z&&res+m>=z){
cout<<0;
return ;
}
else{
cout<<1;
return ;
}
}
2. G-小L的散步
题目描述
个石块，第
个石块的长度为
，每两个相邻石块之间都有一个长度不计的缝隙。
步，每步跨过的长度为
。
，脚后跟位于
输入描述
第一行输入三个正整数
，表示石块的数量，走的步数和脚掌的长度。
第二行输入
个正整数
，表示每个石块的长度。
第三行输入
个正整数
，表示步子的大小。
输出描述
如果小L在散步的过程中有踩中石块的缝隙，输出
，否则输出
。
解题思路
把每一个缝隙都存起来，排序，把每一步的LR处理出来，对于每一个LR区间，二分找到最近的缝隙，检查一下有没有踩到即可
AC 代码
void solve(){
cin>>n>>m>>L;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]+=a[i-1];
}
for(int i=1;i<=m;i++){
cin>>b[i];
}
vector<array<int,2>>v;
v.push_back({0,L});
for(int i=1;i<=m;i++){
auto [l,r]=v.back();
v.push_back({l+b[i],r+b[i]});
}
for(auto [l,r]:v){
int idx=lower_bound(a+1,a+1+n,l+1)-a;
int val=a[idx];
if(val>l&&val<r){
cout<<"YES\n";
return ;
}
}
cout<<"NO\n";
return ;
}
3. H-小L的数组
题目描述
和
。小 L 拥有一个初始数值
。
，即
后与
，即
进行按位异或运算。
输入描述
第一行输入一个正整数
，表示数组长度。
接下来一行输入
个非负整数
，表示
数组。
接下来一行输入
个非负整数
，表示
数组。
输出描述
输出一个非负整数，表示
次操作后
的最大可能值。
解题思路
由于异或操作，最大值不超过4095，数据量很小，直接动态规划跑一遍就OK。
AC 代码
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
dp[0][0]=true;
for(int i=1;i<=n;i++){
for(int j=4096;j>=0;j--){
if(dp[i-1][j]){
dp[i][max(0ll,j-a[i])]=true;
dp[i][j^b[i]]=true;
}
}
}
for(int i=4096;i>=0;i--){
if(dp[n][i]){
cout<<i<<"\n";
return ;
}
}
}
4. A-小L的三角尺
题目描述
作为打磨掉的长度（即打磨后的直角边长变为
）。该操作必须满足
，即打磨长度不能超过原边长。
时，打磨后该直角边长度变为
的打磨额度，所有尺子的打磨长度之和必须满足
。请问在最优策略下，这
输入描述
第一行输入两个正整数
，分别表示直角三角尺的个数和总打磨额度。
此后
行，第
行输入两个正整数
，表示第
把直角三角尺的两条直角边长度。其中
为可打磨的直角边。
输出描述
输出一行一个实数，表示所有直角三角尺打磨后的斜边长度之和的最小值。
由于实数的计算存在误差，当误差的量级不超过
时，您的答案都将被接受。具体来说，设您的答案为
，标准答案为
，当且仅当
时，您的答案将被接受。
解题思路
把每一次打磨一个单位长度后产生的贡献作为关键字排序，每一次选择贡献最大的三角尺进行打磨
PS
想二分枚举打磨的长度，但是精度存在问题，浮点数的题慎用二分吧
AC 代码
void solve(){
cin>>n>>w;
priority_queue<array<ld,3>>q;
ld ans=0;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
ans+=cal(x[i],y[i]);
if(y[i]>0.5)q.push({cal(x[i],y[i])-cal(x[i],y[i]-1),x[i],y[i]-1.0});
}
while(w>0&&q.size()){
auto [gx,x,y]=q.top();q.pop();
ans-=gx;
w--;
if(y>0.5){
q.push({cal(x,y)-cal(x,y-1),x,y-1.0});
}
}
cout<<fixed<<setprecision(20)<<ans<<"\n";
}
5. D-小L的扩展
题目描述
个白色方格组成，其中有
个方格被染黑了，染黑的方格每个单位时间会向上下左右四个方向扩散一格。其中有
个方格上有蓝色的墨水，每个染上蓝色的墨水的方格会在某个特定的时间点变为白色，在蓝色墨水存在的时刻是不能被染黑的方格扩散到的。
到来时先变为白色。
，先让所有满足
的蓝色方格变为白色，然后黑色从所有已变黑的方格向上下左右四邻方格各扩散
格；若目标方格在该时刻已为白色，则在该时刻被染黑。
输入描述
第一行输入四个正整数
，表示纸张大小、黑方格个数、蓝方格个数。
此后
行，第
行输入两个正整数
，表示第
个黑方格的位置；
此后
行，第
行输入三个正整数
，表示第
个蓝方格的位置及其变为白色的时间。
保证
个被染色的方格两两不同，即不存在同一个方格既被染黑又被染蓝。
输出描述
输出一个整数，表示整张纸被完全染黑的时间。
解题思路
BFS解决，只是不能以层为单位，要以时间为顺序，把时间为第一排序的关键字，可以实现时间的顺序性染色，也不用考虑时间中间的过程，会产生跳跃性的效果。
AC 代码
void bfs(){
while(!q.empty()){
auto [dis,x,y]=q.top();q.pop();
if(dis!=res[x][y])continue;
for(int i=0;i<4;i++){
int sx=x+dx[i],sy=y+dy[i];
if(!safe(sx,sy))continue;
int t=max(dis+1,tim[sx][sy]);
if(t<res[sx][sy]){
res[sx][sy]=t;
q.push({t,sx,sy});
}
}
}
}
6. C-小L的线段树
题目描述
：
，则该节点为叶节点。
，令
。该节点的左子节点对应区间
，右子节点对应区间
。
。
，从根节点开始进行区间查询，过程如下：
被
完全包含：
若该节点未被毁坏：计
为完成对
。
【名词解释】
，且此时每个子节点都有明确的“左”或“右”属性。
输入描述
第一行输入一个正整数
，同时用于表示事件总数和线段树的根节点对应的区间长度。
此后
行，第
行先输入一个整数
，表示第
天发生的事件类型，随后在同一行：
若
，输入两个整数
，表示毁坏了
区间所代表的节点，保证仅对应线段树上的一个节点，同一个节点可能被毁坏多次；
若
，输入两个整数
，表示想要获取
区间的信息。
输出描述
对于每一个
的事件，新起一行输出一个整数，表示
的值。
解题思路
每一次都查询，时间上无法通过，根据线段树的性质，提前处理好每一个节点的查询值，没有破坏的节点为1，破坏的节点从左右子节点中更新，线段树模板的题
AC 代码
void update(int p,int l,int r,int L,int R){
if(l==L&&r==R){
tr[p].f=0;
tr[p].val=tr[p<<1].val+tr[p<<1|1].val;
return ;
}
int mid=(l+r)>>1;
if(R<=mid)update(p<<1,l,mid,L,R);
else if(L>mid)update(p<<1|1,mid+1,r,L,R);
else{
update(p<<1,l,mid,L,R);
update(p<<1|1,mid+1,r,L,R);
}
if(tr[p].f==1)tr[p].val=1;
else tr[p].val=tr[p<<1].val+tr[p<<1|1].val;
}
int query(int p,int l,int r,int L,int R){
if(L<=l&&r<=R){
return tr[p].val;
}
int res=0;
if(tr[p].f)res++;
int mid=(l+r)>>1;
if(R>mid)res+=query(p<<1|1,mid+1,r,L,R);
if(L<=mid)res+=query(p<<1,l,mid,L,R);
return res;
}
7. I-小L的构造2
题目描述
，使得该排列中任意相邻的三个元素中，都至少存在两个数不互质
。
，在集合
中存在两个不同的数
，满足
。
。
【名词解释】
这
是一个长度为
的排列，而
和
都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
和
的公约数有
，其中最大的约数是
，所以它们不是互质的；
的公约数仅有
输入描述
输入一个正整数
，表示排列的长度。
输出描述
如果不存在符合条件的排列，直接输出
。否则，在一行上输出
个整数，表示构造出的排列，整数之间用空格分隔。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
解题思路
题解是以12个数为一组，边界情况特殊讨论一下。但是我对于边界情况的理解不太好,并没有使用分组的做法。
把不存在可以分在一起的质数看作孤立数，把其他的数字按照最小质因子分组，然后不同的质因子边界使用2的倍数填充，之后把孤立数分散地插入分组有序的数组中，得到答案
AC 代码
void solve() {
int n;cin >> n;
if (n == 3 || n == 5) {cout << -1 << "\n";return;}
vector<int> s = {1}, v[N];
for (int i = 3; i <= n; i += 2) {
if (2 * spf[i] > n) s.push_back(i);
else v[spf[i]].push_back(i);
}
vector<int> b, used(n + 1, 0), evens;
for (int i = 3; i <= n / 2; i++) {
if (spf[i] == i && !v[i].empty()) {
b.push_back(2 * i);
used[2 * i] = 1;
for (int x : v[i]) b.push_back(x);
}
}
for (int i = 2; i <= n; i += 2)if (!used[i]) evens.push_back(i);
evens.insert(evens.end(), b.begin(), b.end());
b = evens;
if (3*s.size() > n + 2) {cout << -1 << "\n";return;}
vector<int> res;
int si = 0, m = b.size();
if (si < s.size()) res.push_back(s[si++]);
for (int i = 0; i < m; i++) {
res.push_back(b[i]);
if (si < s.size() && i % 2 == 1 && i < m - 1) {
res.push_back(s[si++]);
}
}
if (si < s.size()) res.push_back(s[si++]);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << (i == res.size() - 1 ? "\n" : " ");
}
}
8. J-小L的字符串
题目描述
输入描述
输出描述
PS
这个区域以后再探索吧
我不会NTT啊
AC 代码
9. L-小L的游戏2
题目描述
输入描述
输出描述
PS
这个区域以后再探索吧
我真会矩阵快速幂，但我想吃吃吃了
AC 代码
10. F-小L的极大团
题目描述
输入描述
输出描述
PS
这个区域以后再探索吧
我最讨厌推式子了，其实我是懒狗，我要去写点CF水题了，我不进步，沃兰多
AC 代码
京公网安备 11010502036488号