T26:Snakes
2026-01-02 17:08:35
发布于：香港
3阅读
0回复
0点赞
1）题目意思
有一条很长的格子带（编号从 1 开始到 1e9），要放 n 条蛇。开始时每条蛇长度为 1，占一个格子，且不同蛇不能占同一格。
之后有 q 次操作，每次对某条蛇执行：
+：区间[l,r]变成[l,r+1]（向右变长）-：区间[l,r]变成[l+1,r]（从左缩短）
任何时刻蛇不能撞到边界（格子编号不能 < 1），也不能和其它蛇重叠（同一格不能被两条蛇同时占用）。
游戏结束后，得分是所有蛇占用到的最大格子编号（也就是所有蛇的 r 的最大值）。你要让得分尽可能小，输出最小可能得分。
2）思路解析（核心等价 + 二分答案 + 状压DP选顺序）
关键等价：每条蛇在任意时刻的位置只和“+/- 的次数”有关
设第 s 条蛇初始放在位置 p[s]（初始 l=r=p）。
令：
plus[s][t]：前t秒内对蛇s执行过+的次数minus[s][t]：前t秒内对蛇s执行过-的次数
那么在第 t 秒后（含 t=0 初始）：
- 左端点
l = p[s] + minus[s][t] - 右端点
r = p[s] + plus[s][t]
（因为 + 只让右端点 +1，- 只让左端点 +1，且输入保证不会缩到空。）
所以整题变成：选一组互不相同的起点 p[s]，使得对所有时刻 t，任意两条蛇区间不重叠，并最小化最终最大的 r。
不重叠条件（假设放置顺序从左到右）
如果某时刻我们保证蛇 A 的起点在蛇 B 左边（p[A] < p[B]），要想永远不重叠，需要对所有时刻 t 都满足：
p[A] + plus[A][t] < p[B] + minus[B][t]
整理得：
p[B] - p[A] > plus[A][t] - minus[B][t]
因此只要让相邻两条蛇的起点间距满足一个“最大需求间距”即可：
gap(A,B) = 1 + max_t( plus[A][t] - minus[B][t] )
然后只要 p[B] >= p[A] + gap(A,B)，就能保证任意时刻 A 永远在 B 左边且不重叠。
二分答案 M（最终最大格子编号）
如果我们猜一个最终得分上限 M，就等价于对每条蛇都有：
p[s] + plus[s][q] <= M
也就是：
p[s] <= M - plusFinal[s]
在给定 M 时，问题变成：
- 给
n条蛇排一个从左到右的顺序 - 从最左开始放，最左蛇放在
p=1 - 后面每条蛇满足相邻间距
gap - 并且每条蛇的起点不超过它的上界
ub[s]=M-plusFinal[s]
问能否做到。能做到则 M 可行，否则不可行。可行性随 M 单调，所以可以二分。
如何判断某个 M 是否可行：状态压缩 DP 选顺序
n<=20，可以用状压 DP 来选排列顺序：
dp[mask][last]表示：已放置集合mask这些蛇，并且最后一条是last，在“尽量靠左放”的策略下，last的最小可能起点位置。- 初始：选某条蛇作为第一条，放在
p=1，要求1<=ub[first] - 转移：从
last接一条nxt，则pNext = dp[mask][last] + gap(last,nxt)- 要求
pNext <= ub[nxt] - 更新
dp[mask|1<<nxt][nxt] = min(原值, pNext)
如果能做到 mask=ALL（所有蛇都放完）则这个 M 可行。
3）代码
#include <bits/stdc++.h>
using namespace std;
const long long INF = (1LL<<60); // 定义一个很大的数表示不可达
static int plusCnt[20][200005]; // plusCnt[s][t]：蛇s在前t步“+”次数
static int minusCnt[20][200005]; // minusCnt[s][t]：蛇s在前t步“-”次数
static int plusFinal[20]; // plusFinal[s]：蛇s总“+”次数
static long long gapNeed[20][20]; // gapNeed[a][b]：a在左b在右需要的最小间距
static long long dp[1<<20][20]; // dp[mask][last]：放完mask且最后是last时last最小起点
int main(){ // 主函数入口
ios::sync_with_stdio(false); // 加速输入输出
cin.tie(nullptr); // 加速输入输出
int n,q; // n条蛇，q次操作
cin>>n>>q; // 读入n和q
for(int s=0;s<n;s++){ // 初始化第0步的累计次数为0
plusCnt[s][0]=0; // 初始没有“+”
minusCnt[s][0]=0; // 初始没有“-”
}
for(int t=1;t<=q;t++){ // 逐步读入每次操作并维护前缀累计
int id; // 蛇编号
char op; // 操作符
cin>>id>>op; // 读入“si +/ -”
id--; // 转成0-based
for(int s=0;s<n;s++){ // 把上一步的计数先复制下来
plusCnt[s][t]=plusCnt[s][t-1]; // plus前缀复制
minusCnt[s][t]=minusCnt[s][t-1]; // minus前缀复制
}
if(op=='+') plusCnt[id][t]++; // 若是+，对应蛇的plus次数+1
else minusCnt[id][t]++; // 若是-，对应蛇的minus次数+1
}
for(int s=0;s<n;s++){ // 统计每条蛇最终的plus次数
plusFinal[s]=plusCnt[s][q]; // 最终右端点偏移量
}
for(int a=0;a<n;a++){ // 预处理相邻间距需求gapNeed[a][b]
for(int b=0;b<n;b++){ // 枚举b
if(a==b){ // 同一条蛇不考虑
gapNeed[a][b]=INF; // 随便设成很大
continue; // 跳过
}
int best = INT_MIN; // best存max_t(plus[a][t]-minus[b][t])
for(int t=0;t<=q;t++){ // 枚举所有时刻t
int val = plusCnt[a][t] - minusCnt[b][t]; // 计算此时的差值
if(val>best) best=val; // 更新最大值
}
gapNeed[a][b] = (long long)best + 1; // gap = 1 + 最大差值，保证严格不重叠
if(gapNeed[a][b]<1) gapNeed[a][b]=1; // 间距至少为1（起点不同且不重叠）
}
}
auto feasible = [&](long long M)->bool{ // 判断给定M是否可行的lambda
static long long ub[20]; // ub[s]=M-plusFinal[s]，蛇s起点上界
for(int s=0;s<n;s++){ // 计算每条蛇的起点上界
ub[s]=M - (long long)plusFinal[s]; // p<=M-plusFinal
if(ub[s]<1) return false; // 如果连p=1都放不下，直接不可行
}
int ALL=(1<<n)-1; // ALL表示所有蛇都已放置
for(int mask=0;mask<=ALL;mask++){ // 初始化dp为INF
for(int last=0;last<n;last++){ // 初始化dp为INF
dp[mask][last]=INF; // 设为不可达
}
}
for(int s=0;s<n;s++){ // 枚举第一条蛇是谁
if(1<=ub[s]){ // 如果第一条蛇允许放在1
dp[1<<s][s]=1; // 放在p=1
}
}
for(int mask=0;mask<=ALL;mask++){ // 枚举已放置集合mask
for(int last=0;last<n;last++){ // 枚举最后一条蛇last
long long curPos=dp[mask][last]; // 取last的最小起点
if(curPos>=INF) continue; // 不可达跳过
for(int nxt=0;nxt<n;nxt++){ // 枚举下一条要接上的蛇nxt
if(mask&(1<<nxt)) continue; // 已经放过则跳过
long long nextPos = curPos + gapNeed[last][nxt]; // nxt的起点至少要满足相邻间距
if(nextPos>ub[nxt]) continue; // 超过上界则不可行
int nmask = mask | (1<<nxt); // 新集合
if(nextPos < dp[nmask][nxt]){ // 取更小的起点更好（更靠左）
dp[nmask][nxt]=nextPos; // 更新dp
}
}
}
}
for(int last=0;last<n;last++){ // 只要有一种放完全部蛇的状态即可行
if(dp[ALL][last]<INF) return true; // 若可达则返回true
}
return false; // 否则不可行
};
long long lo=1, hi=1000000000LL; // 二分答案范围（格子编号最大1e9）
while(lo<hi){ // 标准二分
long long mid=(lo+hi)/2; // 取中点
if(feasible(mid)) hi=mid; // 可行则尝试更小
else lo=mid+1; // 不可行则增大
}
cout<<lo<<endl; // 输出最小可行得分
return 0; // 程序结束
}
上述代码TLE三个
正确解法
这题的关键是：蛇的形状始终是一个区间，并且每次操作只会改变区间的左端或右端 1 格。
1）把每条蛇任意时刻的位置写成“起点 + 偏移”
设第 s 条蛇初始放在格子 p[s]（一开始区间是 [p,p]）。
统计到第 t 秒为止：
plusCnt[s][t]：对蛇s执行+的次数minusCnt[s][t]：对蛇s执行-的次数
那么第 t 秒后蛇 s 的区间一定是：
- 左端点
L = p[s] + minusCnt[s][t] - 右端点
R = p[s] + plusCnt[s][t]
所以整个过程只和 p[s]、以及这两个前缀次数有关。
2）两条蛇不相撞的充分必要条件：固定左右顺序 + 保证所有时刻区间不重叠
假设我们决定蛇 a 在蛇 b 的左边（也就是 p[a] < p[b]），为了任何时刻都不重叠，需要对所有 t：
p[a] + plusCnt[a][t] < p[b] + minusCnt[b][t]
把 p[b] 移到右边整理，得到：
p[b] - p[a] > plusCnt[a][t] - minusCnt[b][t]
因此只要让相邻两条蛇的起点间距满足：
gapNeed[a][b] = 1 + max_t( plusCnt[a][t] - minusCnt[b][t] )
就能保证：只要 a 在左 b 在右，就永远不会相撞。
代码里就是先枚举 a,b，再扫一遍 t=0..q 求这个最大值，得到 gapNeed[a][b]。
3）最终得分怎么计算
游戏结束时（t=q），蛇 s 的右端点是：
R_final = p[s] + plusFinal[s]
其中 plusFinal[s] = plusCnt[s][q]
最终得分是所有蛇 R_final 的最大值，也就是：
max_s( p[s] + plusFinal[s] )
你要让它最小。
4）为什么可以“从左到右贪心放位置”，只需要决定顺序
如果我们已经决定了蛇的从左到右顺序，例如 s1, s2, ..., sn，那么为了得分尽量小，显然应该：
-
第一条蛇放到最左
p[s1]=1 -
后面每条蛇都放到“刚好不撞”的最左位置
p[si] = p[s(i-1)] + gapNeed[s(i-1)][si]
因为把任何一条蛇往右挪，只会让最终最大右端点变大或不变，不可能更优。
所以问题变成：只需要选出一条从左到右的排列顺序。
5）状压 DP：一次性求“最小得分”（不二分）
n<=20，我们用 mask 表示已经放进队列的蛇集合。
DP 状态存两件信息：
pos：当前最后一条蛇的起点（按最靠左放算出来的）mx：当前为止所有蛇的最终右端点最大值（也就是当前方案的得分）
定义：
dp[mask][last]：放置了mask中的蛇，并且最右边那条是last时的最优(mx,pos)
比较规则：先 mx 小更优；mx 相同则 pos 小更优（更靠左对后续更有利）。
初始化（只有 1 条蛇）：
pos = 1mx = 1 + plusFinal[s]
转移：
- 从
(mask,last)接一条新蛇nxt到右边 nextPos = pos + gapNeed[last][nxt]nextMx = max(mx, nextPos + plusFinal[nxt])- 更新
dp[mask|1<<nxt][nxt]
答案：
- 在
mask=ALL（所有蛇都放完）时，取所有last中最小的mx
6）这版为什么不会 MLE / 为什么比二分快
- 不再二分
M，只做一次 DP（少了约 30 倍） - 用“按 popcount 分层滚动”，只存当前层和下一层，内存显著下降
mx、pos都用int存（答案不会超过 1e9），进一步省内存
以上就是这版代码的完整思路链条：
把碰撞约束变成相邻起点间距 gapNeed，再用状压 DP 选最优排列顺序，同时在 DP 中直接最小化最终得分 mx。
代码
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f; // 定义一个足够大的数当作无穷大
static int plusCnt[20][200005]; // plusCnt[s][t]：前t步蛇s的+次数
static int minusCnt[20][200005]; // minusCnt[s][t]：前t步蛇s的-次数
static int plusFinal[20]; // plusFinal[s]：蛇s总+次数
static int gapNeed[20][20]; // gapNeed[a][b]：a在左b在右的最小起点间距（int足够）
static int lst[21][1<<20]; // lst[k]存popcount=k的所有mask（总量1<<n）
static int cnt[21]; // cnt[k]为lst[k]的元素个数
static int posIdx[1<<20]; // posIdx[mask]=mask在其popcount层里的下标
static int dpMx[200000][20]; // dpMx[idx][last]：当前层状态的mx（得分）
static int dpPos[200000][20]; // dpPos[idx][last]：当前层状态的pos（最后蛇起点）
static int ndpMx[200000][20]; // 下一层的mx
static int ndpPos[200000][20]; // 下一层的pos
static inline bool better(int mx1,int pos1,int mx2,int pos2){ // 比较(a)是否优于(b)：先mx小，再pos小
if(mx1!=mx2)return mx1<mx2; // 得分更小更优
return pos1<pos2; // 得分相同则更靠左更优
}
int main(){ // 主函数入口
ios::sync_with_stdio(false); // 加速输入输出
cin.tie(nullptr); // 加速输入输出
int n,q; // n条蛇，q次事件
cin>>n>>q; // 读入n,q
for(int s=0;s<n;s++){ // 初始化第0步
plusCnt[s][0]=0; // 初始+次数为0
minusCnt[s][0]=0; // 初始-次数为0
}
for(int t=1;t<=q;t++){ // 逐秒读入事件并维护前缀
int id; // 蛇编号
char op; // 操作符
cin>>id>>op; // 读入
id--; // 转0-based
for(int s=0;s<n;s++){ // 把上一秒计数复制到这一秒
plusCnt[s][t]=plusCnt[s][t-1]; // 复制plus
minusCnt[s][t]=minusCnt[s][t-1]; // 复制minus
}
if(op=='+')plusCnt[id][t]++; // 若是+则对应蛇+次数+1
else minusCnt[id][t]++; // 若是-则对应蛇-次数+1
}
for(int s=0;s<n;s++){ // 统计每条蛇最终+次数
plusFinal[s]=plusCnt[s][q]; // 右端点最终偏移量
}
for(int a=0;a<n;a++){ // 预处理gapNeed
for(int b=0;b<n;b++){ // 枚举b
if(a==b){ // 同一条蛇不考虑
gapNeed[a][b]=INF; // 设为很大
continue; // 跳过
}
int best = INT_MIN; // best记录max_t(plus[a][t]-minus[b][t])
for(int t=0;t<=q;t++){ // 枚举所有时刻
int val = plusCnt[a][t] - minusCnt[b][t]; // 计算差值
if(val>best)best=val; // 取最大
}
long long g = (long long)best + 1; // gap = best + 1 才能严格不重叠
if(g<1)g=1; // gap至少为1
gapNeed[a][b]=(int)g; // 存成int
}
}
int ALL=(1<<n)-1; // ALL表示所有蛇都放完
for(int k=0;k<=n;k++)cnt[k]=0; // 初始化每层计数为0
for(int mask=0;mask<=ALL;mask++){ // 枚举所有mask并按popcount分组
int k=__builtin_popcount((unsigned)mask); // k为mask中1的个数
lst[k][cnt[k]++]=mask; // 存入对应层
}
for(int mask=0;mask<=ALL;mask++)posIdx[mask]=-1; // 初始化posIdx
for(int k=0;k<=n;k++){ // 为每层建立mask->下标映射
for(int i=0;i<cnt[k];i++){ // 枚举该层每个mask
posIdx[lst[k][i]]=i; // 记录mask在层内的位置
}
}
int sz1=cnt[1]; // 第1层大小（单元素集合共有n个）
for(int i=0;i<sz1;i++){ // 初始化第1层dp为不可达
for(int last=0;last<n;last++){ // 初始化每个last
dpMx[i][last]=INF; // mx设为INF
dpPos[i][last]=INF; // pos设为INF
}
}
for(int s=0;s<n;s++){ // 初始化：第一条蛇选谁
int mask=(1<<s); // 只包含s
int idx=posIdx[mask]; // 找到mask在第1层的下标
dpPos[idx][s]=1; // 第一条蛇放在起点1
dpMx[idx][s]=1+plusFinal[s]; // 得分为这条蛇最终右端点
}
for(int k=1;k<n;k++){ // 从k层转移到k+1层
int szCur=cnt[k]; // 当前层大小
int szNxt=cnt[k+1]; // 下一层大小
for(int i=0;i<szNxt;i++){ // 初始化下一层为不可达
for(int last=0;last<n;last++){ // 初始化下一层为不可达
ndpMx[i][last]=INF; // mx设为INF
ndpPos[i][last]=INF; // pos设为INF
}
}
for(int idx=0;idx<szCur;idx++){ // 枚举当前层的mask
int mask=lst[k][idx]; // 取出mask
for(int last=0;last<n;last++){ // 枚举最后一条蛇last
int curMx=dpMx[idx][last]; // 取当前mx
int curPos=dpPos[idx][last]; // 取当前pos
if(curMx>=INF)continue; // 不可达跳过
if(!(mask&(1<<last)))continue; // last必须在mask里
for(int nxt=0;nxt<n;nxt++){ // 枚举下一条蛇nxt
if(mask&(1<<nxt))continue; // 已在mask里则跳过
int nmask=mask|(1<<nxt); // 新mask
int nidx=posIdx[nmask]; // 新mask在下一层的下标
long long nextPosLL=(long long)curPos+gapNeed[last][nxt]; // 计算nxt起点
if(nextPosLL>1000000000LL)continue; // 起点超过1e9必然不合法，直接剪枝
int nextPos=(int)nextPosLL; // 转成int
long long nextMxLL=max((long long)curMx,(long long)nextPos+plusFinal[nxt]); // 更新得分
if(nextMxLL>1000000000LL)continue; // 得分超过1e9也没意义，剪枝
int nextMx=(int)nextMxLL; // 转成int
if(better(nextMx,nextPos,ndpMx[nidx][nxt],ndpPos[nidx][nxt])){ // 若候选更优
ndpMx[nidx][nxt]=nextMx; // 更新下一层mx
ndpPos[nidx][nxt]=nextPos; // 更新下一层pos
}
}
}
}
for(int i=0;i<szNxt;i++){ // 把下一层搬到当前层
for(int last=0;last<n;last++){ // 把下一层搬到当前层
dpMx[i][last]=ndpMx[i][last]; // 复制mx
dpPos[i][last]=ndpPos[i][last]; // 复制pos
}
}
}
int idxAll=posIdx[ALL]; // ALL在第n层中的位置（第n层只有一个mask）
int ansMx=INF; // 最终答案mx
int ansPos=INF; // 最终答案pos（用于比较）
for(int last=0;last<n;last++){ // 枚举最后一条蛇是谁
if(better(dpMx[idxAll][last],dpPos[idxAll][last],ansMx,ansPos)){ // 若更优
ansMx=dpMx[idxAll][last]; // 更新答案mx
ansPos=dpPos[idxAll][last]; // 更新答案pos
}
}
cout<<ansMx<<endl; // 输出最小得分
return 0; // 程序结束
}
这里空空如也
有帮助，赞一个