K. 转向导航题意给定平面上nnn个整点航点P1,…,PnP_1, \dots, P_nP1,…,Pn汽车依次沿直线段P1→P2→⋯→PnP_1 \to P_2 \to \dots \to P_nP1→P2→⋯→Pn行驶。在每个中间航点PiP_iPi2≤i≤n−12 \le i \le n-12≤i≤n−1比较到达方向Pi−1Pi→\overrightarrow{P_{i-1}P_i}Pi−1Pi与离开方向PiPi1→\overrightarrow{P_iP_{i1}}PiPi1判断是左转LEFT、右转RIGHT还是直行STRAIGHT。保证不会掉头。题解设到达方向向量a⃗Pi−Pi−1\vec{a} P_i - P_{i-1}aPi−Pi−1离开方向向量b⃗Pi1−Pi\vec{b} P_{i1} - P_ibPi1−Pi则两者之间的转向关系恰好由二维叉积的符号给出a⃗×b⃗axby−aybx{0⇒LEFTb⃗ 由 a⃗ 逆时针旋转0∘∼180∘ 得到0⇒RIGHT顺时针0⇒STRAIGHT同向掉头已被输入排除\vec{a} \times \vec{b} a_xb_y - a_yb_x \begin{cases} 0 \Rightarrow \text{LEFT} \text{} \vec{b} \text{ 由 } \vec{a} \text{ 逆时针旋转} 0^\circ \sim 180^\circ \text{ 得到} \\ 0 \Rightarrow \text{RIGHT} \text{顺时针} \\ 0 \Rightarrow \text{STRAIGHT} \text{同向掉头已被输入排除} \end{cases}a×baxby−aybx⎩⎨⎧000⇒LEFTb由a逆时针旋转0∘∼180∘得到⇒RIGHT顺时针⇒STRAIGHT同向掉头已被输入排除直接对每个中间航点计算叉积并输出即可。时间复杂度O(∑n)O(\sum n)O(∑n)。L题目大意给定一个n×mn \times mn×m的网格地图每个格子有一个互不相同的整数高度hi,jh_{i,j}hi,j。两名玩家轮流移动一面旗帜先手先走。每次移动必须将旗帜从当前格子移动到正交相邻上下左右且高度严格更大的格子。如果当前格子没有可移动的相邻更高格子则当前玩家无法移动判负。有qqq次独立询问每次给出旗帜的起始位置问在双方都采取最优策略的情况下先手胜还是后手胜。分析首先注意到一个关键性质每次移动都严格增加高度。这意味着旗帜永远不会回到已经经过的格子游戏一定在有限步内结束。这是一个典型的无偏组合游戏Impartial Game可以考虑用 Sprague-Grundy 定理分析。为什么不能直接用 BFS如果尝试对每个询问的起点做 BFS/DFS 搜索游戏状态单次询问复杂度是O(nm)O(nm)O(nm)qqq次询问总复杂度O(q⋅nm)O(q \cdot nm)O(q⋅nm)当qqq很大时会超时。核心观察按高度从大到小处理由于每次只能移动到严格更高的格子一个格子的后继状态能一步到达的格子高度都比它大。因此如果我们按照高度从大到小的顺序处理每个格子那么处理到某个格子时它所有后继的 SG 值都已经计算完毕了。这提示我们可以离线预处理所有格子的 SG 值每次询问O(1)O(1)O(1)回答。SG 值的简化其实不必真的求出 SG 函数等等让我们再仔细看一下。题目只要求判断胜负先手胜还是后手胜而不需要具体的 SG 值。对于无偏组合游戏一个状态的 SG 值为000当且仅当它是必败态P-position非000则是必胜态N-position。更进一步由于每个格子可以移动到多个更高的相邻格子我们实际上只需要知道是否存在一个后继状态是必败态SG0如果存在当前状态是必胜态否则是必败态。这等价于当前格子的 SG 值等于其所有后继 SG 值的 mex最小非负整数不在集合中。但由于我们只关心是否为 0可以换个角度理解设当前格子能到达的后继状态的 SG 值集合为SSS。则若0∉S0 \notin S0∈/S则mex(S)\text{mex}(S)mex(S)至少为 0实际上 mex 就是 0 当且仅当 0 不在 S 中当前状态 SG 0先手胜。若0∈S0 \in S0∈S则 mex 可能非 0需要进一步判断。但实际上由于我们只关心胜负可以直接用经典结论状态为必败态当且仅当所有后继都是必胜态。这样预处理复杂度为O(nmlog(nm))O(nm \log(nm))O(nmlog(nm))主要是排序每次询问O(1)O(1)O(1)。代码#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN2e55;intdx[]{0,1,0,-1};intdy[]{1,0,-1,0};structNode{intx,y,w;};boolcmp(Node a,Node b){returna.wb.w;// 按高度降序排序}voidsolve(){intn,m;cinnm;vectorvectorinth(n2,vectorint(m2,0));vectorNodes(n*m1);intscnt1;// 读入地图for(inti1;in;i){for(intj1;jm;j){cinh[i][j];s[scnt].wh[i][j];s[scnt].xi;s[scnt].yj;scnt;}}// sg[x][y] 表示格子 (x,y) 的 SG 值-1 表示未计算vectorvectorintsg(n2,vectorint(m2,-1));// am[x][y] 存储格子 (x,y) 的已处理邻居的 SG 值// 由于按高度降序处理已处理的邻居一定比当前格子高vectorintam[n2][m2];sort(s.begin()1,s.end(),cmp);// 按高度从大到小处理每个格子for(intk1;kn*m;k){intxs[k].x,ys[k].y;mapint,intcnt;// 统计已收集的后继 SG 值for(inti0;iam[x][y].size();i){cnt[am[x][y][i]];}// 计算 mex得到当前格子的 SG 值for(inti0;i4;i){if(!cnt[i]){sg[x][y]i;break;}}// 将当前格子的 SG 值传播给未处理的低邻居for(inti0;i4;i){intxxxdx[i],yyydy[i];if(xx0||xxn||yy0||yym){continue;}// 若邻居未处理高度更低则将当前 SG 值加入其 amif(sg[xx][yy]-1){am[xx][yy].push_back(sg[x][y]);}}}intq;cinq;while(q--){intx,y;cinxy;// SG 非 0 则先手胜否则后手胜if(sg[x][y]){coutFirst\n;}else{coutSecond\n;}}}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int_1;cin_;while(_--)solve();return0;}总结这道题的关键在于发现高度顺序与游戏方向的一致性从而避免了对每个询问重复搜索。虽然代码中仍然计算了完整的 SG 值但由于值域极小效率非常高如果只关心胜负理论上还可以进一步简化但当前写法已经足够简洁高效。
