Welcome to SwedenCpp

Latest blogs, videos, podcasts and releases in one stream

Monday, November 9, 2026

If this page is useful, please consider donating a coffee

Sunday, November 8, 2026

GSoC 2026 - Teach the Clang Static Analyzer to understand lifetime annotationsGoogle Summer of Code 2026 @ LLVM Compiler Infrastructure Commits on GitHub | Pullrequests Motivation Clang can warn about lifetime bugs. Behind -Wlifetime-safety [1] it reads the lifetime annotations a function carries and reports a warning when a pointer or a reference that outlives the object it refers to escapes the function,or when the dead object is accessed through it. The analysis runs on every translation unit of every build and examines one function at a time, so an unannotated call is treated optimistically as having no lifetime effects:the origin of the value is lost at the call and bugs that depend on it go unreported. This project extends the Clang Static Analyzer (later referred to as CSA) to cover those cases. It reads the same annotations and follows the value through the callsthe compiler cannot enter, and the three checkers that came out of it are in Clang today, reporting bugs the compiler does not. Patches These are the patches that closed the gap, taking the analyzer from missing this class of bugs to catching it. #205521 : implemented the UseAfterLifetimeEnd checker, which reports a value returned from a function while it still borrows from a local of that function. #205951 : implemented the LifetimeModeling checker and moved every state operation out of UseAfterLifetimeEnd into it. #207052 : implemented a BugReporterVisitor for UseAfterLifetimeEnd that adds the note showing where the value’s lifetime was bound to its source. #209278 : implemented DanglingPtrDeref , which reports a use of a pointer whose pointee has gone out of scope. #209862 : NFC, corrected the DanglingPtrDeref checker’s filename. #210801 : suppressed the report when a lifetimebound method is called during the destruction of an object. #211045 : added checkPostCall to DanglingPtrDeref so a dangling pointer passed as a call argument is reported. #211552 : matched dangling subobjects by their base region, so a pointer into a field, an array element or a base class subobject of a dead object is recognized. #211582 : NFC, rewrote the destructor frame walk with llvm::any_of . #211818 : added trackExpressionValue to DanglingPtrDeref so the report shows where the dangling value originated. #212158 : replaced the debug only getString() with getDescriptiveName() in the diagnostics and switched the path notes to trackStoredValue() . #212254 : NFC, added test cases to the lifetime test suite. #212883 : NFC, matched the parameter order of getEndPath and finalizeVisitor with VisitNode . #213092 : reverted a documentation change that broke the docs build. #213779 : discarded lifetime sources whose stack frame is not the frame being left, which removed most of the false positives found on LLVM. #215409 : implemented markAsReported , so DanglingPtrDeref reports only the first dereference of a given variable. #215651 : underlined only the parameter that the return value is actually bound to when a function has several parameters. #215905 : corrected the highlighted range so it matches the variable the note refers to. #216688 : documentation for UseAfterLifetimeEnd and DanglingPtrDeref . From an attribute to a report Nothing can be reported before the Clang Static Analyzer records where a value borrows from, so that recording came first. int * test_func ( int * p [[clang::lifetimebound]] ); Clang attaches [[clang::lifetimebound]] to the annotated ParmVarDecl , so the contract is in the AST before the analyzer starts. int * test_func ( int * p [[clang::lifetimebound]] ); int * variable_return () { int y = 5 ; int * p = test_func( & y); // checkPostCall records that the result borrows from 'y' // ... } In checkPostCall the call has been evaluated, so the return value has an SVal and the checker can pair it with the region of the argument it borrows from.That pair goes into the ProgramState , the object the analyzer carries from node to node, and a state belongs to one node. int * test_func ( int * p [[clang::lifetimebound]] ); int * variable_return () { int y = 5 ; int * p = test_func( & y); // checkPostCall records that the result borrows from 'y' return p; // checkEndFunction callback reports here: // warning: Returning value bound to 'y' that will go out of scope } The checkEndFunction callback asks the state what the returned value borrows from and whether those regions belong to the frame that is about to die. The two nodes below are consecutive in the ExplodedGraph and sit at the same program point. State 603 is the engine having evaluated the call. State 550 is onenode later, after LifetimeModeling ran, and it carries the borrow as Origin ... contains Loan y . -Wlifetime-safety is intra-procedural by default and path-insensitive: it analyzes one function at a time and merges the states at a join point (where branches meet), so a borrow taken on one branchis indistinguishable from one taken on the other. The analyzer performs an inter-procedural and path-sensitive analysis: it can enter a callee whose body isavailable (if the analyzer’s budget allows it) and explores each path separately, so what it records on one path never shows up on the other. One writer for the state With the borrow recorded, the next question was who is allowed to write it. LifetimeModeling owns everything that touches the program state and exposes nothing but queries. The reporting checkers( UseAfterLifetimeEnd and DanglingPtrDeref ) read it, decide whether what they see is a bug and build the report that explains the path to it. [[clang::lifetimebound]] end of a scope \ / v v +--------------------------------------------------+ | LifetimeModeling | | the only checker that writes state | | | | what borrows from what | what has died | +--------------------------------------------------+ | | | queries | queries v v +----------------------+ +--------------------------+ | UseAfterLifetimeEnd | | DanglingPtrDeref | | a returned value | | a pointer used after | | outlives its frame | | its object is gone | +----------------------+ +--------------------------+ Catching use after the scope ends The annotated case is now covered. The second kind of lifetime error needs no annotations at all: a pointer used after the object it points to has gone out ofscope. While the modelling was taking shape in June, Arseniy Zaostrovnykh and Tomasz Kaminski added CFGLifetimeEnds handling to the analyzer, which turns every end of a scopeinto a checkLifetimeEnd event and lets the CSA reason about lifetimes directly #201123 . I picked it up as soon as it landed and built DanglingPtrDeref on top ofit. LifetimeModeling listens to that event and adds the region to DeallocatedSourceSet . checkPreStmt(DeclStmt) clears a variable’s region from that setwhenever its declaration is executed, so a stale entry cannot make fresh storage look dead. DanglingPtrDeref subscribes to check::Location and asks on every load and store through a pointer whether the pointee is gone. void use_after_scope () { int * ptr = nullptr ; { int num = 5 ; ptr = & num; } * ptr = 6 ; // warning: Use of 'num' after its lifetime ended } num lives only inside the block, so by the last line its storage is gone while ptr still holds its address. checkLifetimeEnd fires at the closing braceand puts num into DeallocatedSourceSet . On the dereference checkLocation asks whether the pointee is still alive, finds the region in that set andreports. A pointer that is only passed on While evaluating the first version of the checker I found a case it did not cover: a dangling pointer handed to another function. check::Location does notfire there because the load at a call site is the load of the pointer variable itself and not an access through the pointer. DanglingPtrDeref now alsoimplements checkPostCall and inspects every argument, but only when the analyzer did not step into the callee’s body. If it did, checkLocation alreadycovers every dereference in there and reporting at the call site as well would produce the same bug twice. void escape ( int * ptr); void passing_dangling_ptr_to_opaque_func () { int * ptr = nullptr ; { int num = 5 ; ptr = & num; } escape(ptr); // warning: Use of 'num' after its lifetime ended } escape(ptr); | +-- check::Location fires once, for the load of 'ptr' | location it is given: the region of 'ptr' (alive) | 'num' is only the value that comes out of that load, never the location | so the event has nothing dead to look at | +-- checkPostCall sees the call after it was evaluated argument SVal: &num -> its lifetime has ended -> report Reporting at the call site is a deliberate choice. A dangling pointer cannot be used safely by anyone, so handing one to a function is already a bug even if the callee never dereferences it, and the caller should reset itto nullptr instead.The same holds for what a call can reach indirectly, an output parameter of type int ** or a std::pair : the dangling pointer should be cleared rather than passed on. Some of these reports can be argued tobe false positives. Flagging them anyway is a deliberate choice, because once a dangling pointer is handed on there is nothing safe left to do with it. A pointer into part of a dead object So far we only talked about primitive types, but there are aggregates and, in C++, inheritance as well. A pointer can point at a field, an array element or a base class subobject, while what the modeling checker recorded asdeallocated was the region of the whole object. struct MyBuffer { char buffer[ 8 ]; }; char member_subregion_dangling_deref () { const char * p = nullptr ; { MyBuffer tmp_buffer = {}; p = tmp_buffer.buffer; } return * p; // warning: Use of 'tmp_buffer.buffer[0]' after its lifetime ended } p points at the first element of the array inside tmp_buffer , not at tmp_buffer itself, while checkLifetimeEnd records the region of the whole variable that died. isDeallocated , the query the reporting checkersuse to ask whether a region is dead, now looks up the base region of the region it is asked about, which walks the element up through the field to tmp_buffer and finds it: p = tmp_buffer.buffer; p points at ElementRegion tmp_buffer.buffer[0] ---+ | | v | FieldRegion tmp_buffer.buffer | getBaseRegion() | | v | VarRegion tmp_buffer Before this change the checker only recognized pointers to whole variables, so a pointer into a field, an array element or a base class subobject went unreported. Also this change costs nothing in precision,because a subobject cannot outlive the object that contains it: if tmp_buffer is gone, every region inside it is gone with it. Testing the lifetime checkers Running the checkers on a real project does two things. It shows they hold up outside the cases I wrote tests for and it measures the property that decides whether a checker can stop being experimental: how rarely it reportssomething that is not a bug (false positive). A core checker is expected to have very few false positives and that number cannot come from a hand written suite. The LLVM monorepo is large, actively maintained and heavily reviewed, so itexercises shapes my tests never reach. Every report there has to be read on its own and the ones I went through fell into three classes, each a place where the model was too coarse. Closing them made both checkers moreprecise and moved them closer to the bar a core checker has to meet. A lifetimebound call during destruction A destructor is the one place where handing out a borrow of the dying object is normal: the caller is thedestructor itself and the borrow does not escape it. The fix walks the frames on the current stack and suppresses the report if any of them is a destructor, which is coarse on purpose: it asks whether a destructor is onthe stack, not whether the borrow belongs to the object being destroyed, so a function called from a destructor that returns a borrow of its own local goes unreported. struct S { call stack int x; int *get() [[clang::lifetimebound]] +----------------------+ { return &x; } | outer() | ~S() { get(); } +----------------------+ }; | passThrough() | the S dies here +----------------------+ S passThrough(S param) { return param; } | S::~S() | +----------------------+ void outer() { | S::get() | returns &x, a borrow auto f = passThrough(S()); -----------------> +----------------------+ of *this } a destructor frame is on the stack, so the borrow get() hands out is meant to die with the object -> no report A source owned by another frame This was the largest of the three classes. A returned value can only dangle if the frame that owns its lifetime source is the frame being left. When the source belongs to a caller thatstays alive, or to a frame the analyzer never entered, the storage outlives the value and there is nothing to report. const char *first(const char *buf [[clang::lifetimebound]]); void use(const char *p); call stack const char *helper(const char *buf) { +----------------------+ return first(buf); | caller() | owns 'buf' } +----------------------+ | helper() | void caller() { +----------------------+ char buf[64] = {}; returns a value bound use(helper(buf)); ----------------------------> to 'buf' } 'buf' belongs to caller(), which stays alive when helper() returns -> no report The same variable reported again and again checkLocation fires on every access through a pointer, so a dead variable used five times produced five warnings that all describe the same bug. markAsReported keeps the first and drops the rest. before after *p = 1; warning *p = 1; warning *p = 2; warning *p = 2; - use(p); warning use(p); - Results Two of the cases below come from how -Wlifetime-safety works: it analyzes one function at a time and treats a call asopaque, so the only thing it learns about a callee is what the callee’s declaration says. The third is a gap inside the analyzer itself: before the lifetime checkersit had no model of [[clang::lifetimebound]] and nothing that reported a stack object used after its scope ended. Every analyzer warning quoted in this section comes from the same command, so any of the examples can be reproduced by pasting it into a file and running: $ clang -cc1 -analyze \ -analyzer-checker=core,alpha.cplusplus.UseAfterLifetimeEnd,alpha.cplusplus.DanglingPtrDeref \ -analyzer-config cfg-lifetime=true -analyzer-output=text example.cpp Following a borrow through an unannotated call The compiler handles the direct case. With the local passed straight to the annotated parameter, -Wlifetime-safety says so: const char * findOption ( const char * config [[clang::lifetimebound]] , const char * key); const char * readTimeoutDirect () { char config[ 64 ] = "timeout=30" ; return findOption(config, "timeout" ); // warning: stack memory associated with local variable } // 'config' is returned [-Wlifetime-safety-return-stack-addr] Put one unannotated function between the local and the annotated call and the warning disappears, because the analysis cannot look inside optionValue and optionValue carries no contract of its own. A chain only has to lose one link for the diagnostic to go with it. // Defined in another translation unit. const char * findOption ( const char * config [[clang::lifetimebound]] , const char * key); const char * optionValue ( const char * config, const char * key) { return findOption(config, key); } const char * readTimeout () { char config[ 64 ] = "timeout=30" ; return optionValue(config, "timeout" ); // warning: Returning value bound to 'config[0]' } // that will go out of scope This is where inlining matters. When the body of a callee is available, the analyzer does not treat the call as a black box: it enters the body and keeps exploring the same path inside it, carrying the caller’s state in,so everything that happens in the callee is visible to the checkers on the way out. When the body is not available the call is evaluated conservatively and the analyzer knows only what the declaration says. Here optionValue is inlined, the annotated call inside it is reached and the contract on findOption stands in for the body that is not there. The report names config[0] because that is the region the array decays to atthe call. Reporting a use after the scope ends void use_after_scope () { int * ptr = nullptr ; { int num = 5 ; ptr = & num; } * ptr = 6 ; // warning: Use of 'num' after its lifetime ended } None of the analyzer’s existing checkers for this kind of error cover it, core.StackAddressEscape and cplusplus.InnerPointer included: with -analyzer-checker=core,cplusplus the analyzer produces no diagnostic at all. DanglingPtrDeref reports it, and the path in the report runs from theinitialization of num through the assignment to ptr to the closing brace where the storage dies. A borrow made in one function and used in another void submit ( const int * sample); const int * identity ( const int * value) { return value; } void collectSample ( int reading) { const int * sample = nullptr ; { int corrected = reading + 1 ; sample = identity( & corrected); } submit(sample); // warning: Use of 'corrected' after its lifetime ended } Neither function is annotated and sample is never dereferenced in collectSample . -Wlifetime-safety sees identity as an opaque call and has no origin tofollow, so it stays silent. The CSA inlines identity , follows the pointer back to corrected and reports the call that passes it on. Together the two checkers move lifetime checking past the point where the compiler has to stop. -Wlifetime-safety remains the right tool for the common case,because it is cheap enough to run on every build. What it cannot do is follow a value through a call it cannot see into, and a chain only has to lose one linkfor the warning to disappear. Every report the checkers produce carries the execution path from the borrow to the death of the storage, including the branchthat had to be taken, so the reader can judge it without rerunning the analysis. Both checkers ship in Clang today, both have been run over the LLVM monorepo,and LifetimeModeling is a base that the next lifetime checker can consume instead of rebuilding. Future work Support for LazyCompoundVal . std::string_view and std::span are among the types the annotations are written on. They are class types returned by value, which the analyzer represents as a LazyCompoundVal and none of the maps in the modeling checker cover that today, so the lifetime origin is lost: struct View { int * p; }; View makeView ( int & x [[clang::lifetimebound]] ); void caller_view () { int v = 42 ; View w = makeView(v); // FIXME: Currently none of the maps cover LazyCompoundVal. } Covering it brings the checkers to the code the annotations were introduced for. Interoperability with the MallocChecker . Both checkers reason about stack regions, so a lifetime source that lives on the heap is out of their reach. The plan is to extend them to heap sources through theinterface the MallocChecker already exposes for this in AllocationState.h , which is how cplusplus.InnerPointer works with it today, instead of modeling the heap in the lifetime checkers. The [[clang::lifetime_capture_by(X)]] annotation. The original proposal covered both annotations. During the summer I have prioritized [[clang::lifetimebound]] , because it is the annotation people currently use. Inthe LLVM monorepo alone libc++ applies _LIBCPP_LIFETIMEBOUND around 80 times across 22 headers, while lifetime_capture_by does not appear in the library at all, and outside LLVM the same asymmetry holds: Abseil ships ABSL_ATTRIBUTE_LIFETIME_BOUND [2] and uses it throughout its string and container implementations, while lifetime_capture_by is a much newer addition [3]. Supporting the capture annotation is the work I intend to doafter the summer. Special thanks I would like to say thank you to my mentors, in the order they appear on the LLVM GSoC page: Gábor Horváth, Balázs Benics and Dániel Domján, for mentoring this project, for the reviews and design discussions that shapedboth checkers and for answering my questions throughout the summer. The time they put into the project and into teaching me went well beyond what I expected. My questions were answered quickly and my patches were reviewedeven at weekends. This was the greatest summer of my life so far without a doubt. I am grateful for the opportunity and for my mentors for all their help and guidance. This project gave me a huge motivation to stay activein the LLVM community and continue working on the lifetime checkers and the Clang Static Analyzer. I would also like to say thank you to Donát Nagy for his code reviews on some of these patches and to Arseniy Zaostrovnykh and Tomasz Kaminski for the CFGLifetimeEnds support in the CFG. References [1] U. Saxena, D. Hrybenko, Y. Mandelbaum, J. Voung and K. Yasuda, “[RFC] Intra-procedural lifetime analysis in Clang”, LLVM Discussion Forums, May 2025. https://discourse.llvm.org/t/rfc-intra-procedural-lifetime-analysis-in-clang/86291 [2] Abseil, definition of ABSL_ATTRIBUTE_LIFETIME_BOUND in absl/base/attributes.h . https://github.com/abseil/abseil-cpp/blob/master/absl/base/attributes.h [3] G. Horvath and U. Saxena, “[RFC] Introduce [[clang::lifetime_capture_by(X)]] ”, LLVM Discussion Forums, November 2024. https://discourse.llvm.org/t/rfc-introduce-clang-lifetime-capture-by-x/81371📝The LLVM Project Blog

Saturday, November 7, 2026

四色滑道：从博物馆的益智玩具到一道OI题Palo Alto Junior Museum and Zoo的室内科学展区(Indoor science exhibits)墙上挂着一块大号的Montessori Slide Puzzle：下方是四条竖直滑槽，每条槽里叠着四颗彩色圆柱珠子；上方的卡片给出目标图案，玩家要通过滑动珠子把下面摆成卡片上的样子。 本文把它抽象成一道OI题，并给出题解和标准程序。 我只拍了两张照片，问了一句「能否根据这个益智玩具设计一道OI算法题？涉及编号时，从 0 开始。提供题解和C++标准程序」。 下面的题面、题解、标程、对拍程序，连同数据范围的取舍，都是Opus 5.5根据照片生成的，这篇文章也是它写的。 它自己从照片里读出了槽、木舌和滑道的结构，写暴力程序对拍，实测连通块大小来确定数据范围，还发现了「底层冻结」这个不变量。我大受震撼。 玩具 上图是摆好的状态，与卡片一致。 相邻两条槽之间是固定的木舌，木舌顶端可以搁一颗珠子；所有槽的顶上由一条只有一颗珠子高的横向滑道连通。 下图中，三颗珠子分别从槽 1、2、3 被推上滑道，停在三根木舌顶上。 木舌顶上的珠子会挡住滑道：此时槽之间无法互相传递珠子，只能把它们放回槽中。 这个「挡路」的性质让题目有了意思。 题目 下文编号均从 0 开始。 一块益智板上有 n 条竖槽，编号 0..n-1 ，每条槽最多叠放 h 颗珠子（从槽底往上紧密叠放）。 相邻的槽 j 与 j+1 之间有一个 台阶 j ，最多放一颗珠子。 所有槽和台阶的上方由一条横向滑道相连，从左到右依次为：槽 0、台阶 0、槽 1、台阶 1、……、台阶 n-2 、槽 n-1 。 每次操作可以拿起 某条槽最上面的珠子 或 某个台阶上的珠子 ，沿滑道左右移动，放到另一处 空台阶 或 未满的槽 中（落在槽的最上方）。 移动途中不能越过有珠子的台阶，但可以越过任何槽。 珠子有 R 、 G 、 B 、 Y 四种颜色，同色珠子没有区别。给定初始状态和目标状态，求最少操作次数；若无法达到，输出 -1 。 输入格式 ：第一行两个整数 n h 。接下来依次给出初始状态和目标状态，每个状态占 h+1 行： 第一行是长度为 n-1 的字符串，第 j 个字符表示台阶 j ； 接下来 h 行，每行长度为 n ， 从上到下 描述各槽，第 i 列对应槽 i 。 . 表示空位。保证同一列中 . 只出现在珠子上方。 数据范围 ： 2 ， 1 ，两个状态中的珠子数都恰好为 n*h 。时间限制 2 s，内存限制 256 MiB。 样例 0 就是上面第二张照片的局面，目标是卡片上的图案： 4 4 RGG R... BYRY YGBR YBGB ... RRGG BYRY YGBR YBGB 答案是 3：依次把台阶 0、1、2 上的珠子放入槽 1、2、3。 样例 1，两条槽都是满的，唯一能做的事是把某条槽顶的珠子放到台阶 0 上；此后台阶被占，两条槽不再连通，答案是 -1 ： 2 2 . RG BY . GR BY 样例 2，从一个打乱的局面摆回卡片，答案是 16： 4 4 ... GRGR YBYR YGBR YBGB ... RRGG BYRY YGBR YBGB 题解 建模 一个状态由每条槽自底向上的颜色序列和每个台阶的内容组成。 操作是可逆的：把珠子从 a 移到 b 之后， a 一定能再接收这颗珠子（槽刚少了一颗，或台阶刚被腾空），而 a 、 b 之间的台阶和移动前一样全空。 所以状态图是无向图，答案就是最短路，用 BFS 求解。 把滑道位置记为 0..2n-2 ：槽 i 在 2i ，台阶 j 在 2j+1 。 枚举后继时，对每个可取珠子的位置 a 向左、向右扫描：遇到空台阶就生成一个后继并继续，遇到有珠子的台阶就停止；遇到未满的槽就生成一个后继，无论满不满都继续。每个状态有 O(n^2) 个后继。 状态压缩 每条槽用 11 位：低 3 位存珠子个数，之后每颗珠子 2 位（ h 时至多 8 位）；每个台阶 3 位（0 表示空，1~4 表示颜色）。 n 时总共不超过 4*11 + 3*3 = 53 位，可以放进一个 unsigned long long 。 底层冻结 考察槽 i 自底向上第 k 颗珠子（从 0 开始）。它要移动，必须先成为槽顶，此时槽 i 恰有 k+1 颗珠子。 槽 i 之外有 (n-1)*h 个槽位和 n-1 个台阶，放着其余 n*h-k-1 颗珠子，空位数为 (n-1)(h+1) - (n*h-k-1) = n - h + k 这颗珠子要移走，槽外至少要有一个空位，即 k >= h-n+1 。因此： 每条槽最底下的 max(0, h-n+1) 层珠子永远不会移动。 若两个状态的冻结层不同，可以直接输出 -1 。 n = h = 4 时最底一行冻结， 4×4 就退化成了 4×3 ；实测两者的连通块大小都是 1587600 个状态。 不过这只是必要条件： 4×3 没有冻结层，随机生成的两个颜色组成相同的状态仍然大多不连通，所以还是要搜索。 双向 BFS 单向 BFS 已经足够：最大连通块约 160 万个状态。标程用双向 BFS，每次扩展当前队列较小的一侧，有解时几乎瞬间出答案。 正确性：设两侧已分别搜完距离 与 的全部状态，且没有公共状态。 若最短距离 D ，最短路上距起点 min(a, D) 的那个点必然同时出现在两侧，矛盾，所以 D >= a+b+1 。 扩展起点一侧的第 a+1 层时，一旦新状态 y 已在另一侧出现，就得到一条长 a+1+dist2(y) 的路径，它不可能短于 D ，所以恰好等于 D 。 因此 第一次相遇即可返回 。若某一侧队列搜空仍未相遇，说明它所在的连通块不含另一端，输出 -1 。 最坏情况是无解：两侧都要把各自的连通块搜完。标程用开放寻址哈希表，颜色均衡且无解的 4×3 、 4×4 数据实测最慢约 0.9 s、86 MB。 为什么珠子数恰好是 n*h 只要少放一颗珠子，空位就会变多，连通块急剧膨胀： n×h 珠子数 连通块大小 4×3 12 1587600 4×3 11 11550000 4×4 16 1587600 4×4 15 > 20000000 关于实物 由底层冻结，若实物每槽恰好只能放 4 颗，底行就永远无法改变：要么所有卡片的底行都相同，要么槽其实还能多放一颗。 照片中第一列装满 4 颗后上方仍有空隙，更像是后者（ h = 5 ，仍是 16 颗珠子）。 我按 h = 5 试过：空位从 3 个增加到 7 个，状态数约 10 10 ，随机两张卡片之间的最少步数通常在 21~29 之间。 双向 BFS 和以「必须移动的珠子数」为估价的 A* 都要数十秒、数 GB 内存。 所以题目把珠子数固定为 n*h 。若想贴合实物规模，可以改成构造题：只要求输出一个步数不超过某个上界的方案，用 Special Judge 判定。 标准程序 用暴力程序（字符串存状态、单向 BFS）对拍了 600 组随机数据，结果一致。 // 四色滑道 —— 标准程序：双向 BFS #include using namespace std ; typedef unsigned long long u64; int n, h; // 状态：每个槽 11 位（3 位个数 + 4×2 位颜色，自底向上），每个台阶 3 位（0 空，1..4 颜色） struct State { int cnt[ 4 ], col[ 4 ][ 4 ], shelf[ 3 ]; }; u64 encode ( const State & s ) { u64 c = 0 ; for ( int i = 0 ; i n; i ++ ) { u64 v = s.cnt[i]; for ( int k = 0 ; k s.cnt[i]; k ++ ) v |= (u64)s.col[i][k] ( 3 + 2 * k); c = c 11 | v; } for ( int j = 0 ; j + 1 n; j ++ ) c = c 3 | s.shelf[j]; return c; } State decode ( u64 c ) { State s; for ( int j = n - 2 ; j >= 0 ; j -- ) s.shelf[j] = c & 7 , c >>= 3 ; for ( int i = n - 1 ; i >= 0 ; i -- ) { u64 v = c & 2047 ; c >>= 11 ; s.cnt[i] = v & 7 ; for ( int k = 0 ; k s.cnt[i]; k ++ ) s.col[i][k] = v >> ( 3 + 2 * k) & 3 ; } return s; } // 滑道上的位置：槽 i 在 2i，台阶 j 在 2j+1 template class F > void forEachNext ( u64 code , F f ) { State s = decode (code); int m = 2 * n - 1 ; for ( int a = 0 ; a m; a ++ ) { int piece; // 取出的珠子颜色（台阶编码，即颜色+1） if (a % 2 == 0 ) { if ( ! s.cnt[a / 2 ]) continue ; piece = s.col[a / 2 ][ -- s.cnt[a / 2 ]] + 1 ; } else { if ( ! s.shelf[a / 2 ]) continue ; piece = s.shelf[a / 2 ], s.shelf[a / 2 ] = 0 ; } for ( int dir = - 1 ; dir 1 ; dir += 2 ) for ( int b = a + dir; b >= 0 && b m; b += dir) { if (b % 2 == 1 ) { // 台阶：空则可停，非空则挡路 if (s.shelf[b / 2 ]) break ; s.shelf[b / 2 ] = piece; f ( encode (s)); s.shelf[b / 2 ] = 0 ; } else if (s.cnt[b / 2 ] h) { // 槽：未满则可落入，满了也能越过 int i = b / 2 ; s.col[i][s.cnt[i] ++ ] = piece - 1 ; f ( encode (s)); s.cnt[i] -- ; } } if (a % 2 == 0 ) s.cnt[a / 2 ] ++ ; else s.shelf[a / 2 ] = piece; } } int colorId ( char ch ) { return string ( "RGBY" ). find (ch); } u64 readState () { State s; string line; cin >> line; for ( int j = 0 ; j + 1 n; j ++ ) s.shelf[j] = line[j] == '.' ? 0 : colorId (line[j]) + 1 ; vector string > g (h); for ( auto & r : g) cin >> r; for ( int i = 0 ; i n; i ++ ) { s.cnt[i] = 0 ; for ( int r = h - 1 ; r >= 0 && g[r][i] != '.' ; r -- ) s.col[i][s.cnt[i] ++ ] = colorId (g[r][i]); } return encode (s); } // 开放寻址哈希表：键为状态编码（编码不为 ~0），值为步数 struct HashMap { static constexpr u64 EMPTY = ~ 0 ULL ; vector u64 > key; vector unsigned char > val; size_t mask, used = 0 ; HashMap () : key ( 1 16 , EMPTY), val ( 1 16 ), mask (( 1 16 ) - 1 ) {} static size_t hsh ( u64 x ) { x ^= x >> 31 ; x *= 0x 9E3779B97F4A7C15 ULL ; return x ^ (x >> 29 ); } size_t slot ( u64 k ) const { size_t p = hsh (k) & mask; while (key[p] != EMPTY && key[p] != k) p = (p + 1 ) & mask; return p; } int get ( u64 k ) const { size_t p = slot (k); return key[p] == k ? val[p] : - 1 ; } void put ( u64 k , int v ) { if ((used + 1 ) * 2 > key. size ()) grow (); size_t p = slot (k); if (key[p] != k) key[p] = k, used ++ ; val[p] = v; } void grow () { vector u64 > ok; vector ov; ok. swap (key), ov. swap (val); key. assign (ok. size () * 2 , EMPTY), val. assign (ok. size () * 2 , 0 ); mask = key. size () - 1 , used = 0 ; for ( size_t i = 0 ; i ok. size (); i ++ ) if (ok[i] != EMPTY) put (ok[i], ov[i]); } }; int main () { cin >> n >> h; u64 st = readState (), ed = readState (); if (st == ed) { puts ( "0" ); return 0 ; } HashMap dist[ 2 ]; vector u64 > q[ 2 ]; dist[ 0 ]. put (st, 0 ), dist[ 1 ]. put (ed, 0 ); q[ 0 ] = {st}, q[ 1 ] = {ed}; while ( ! q[ 0 ]. empty () && ! q[ 1 ]. empty ()) { int t = q[ 0 ]. size () q[ 1 ]. size () ? 0 : 1 ; // 扩展较小的一侧 vector u64 > nq; int ans = - 1 ; for ( u64 x : q[t]) { int d = dist[t]. get (x); forEachNext (x, [ & ]( u64 y ) { if (ans >= 0 || dist[t]. get (y) >= 0 ) return ; int e = dist[ ! t]. get (y); if (e >= 0 ) { ans = d + 1 + e; return ; } // 第一次相遇即为最优 dist[t]. put (y, d + 1 ); nq. push_back (y); }); if (ans >= 0 ) { printf ( " %d\n " , ans); return 0 ; } } q[t]. swap (nq); } puts ( "-1" ); // 某一侧的连通块已搜完仍未相遇 }📝MaskRay

Friday, November 6, 2026

Better Transparency with VTK and WebGPUTransparency is a seemingly simple and powerful visualization technique to facilitate the understanding of complex geometric structures. However, to do so accurately, and at highly interactive frame rates, is challenging. That is why we're excited about VTK's new WebGPU deep framebuffer. It collects translucent rendering fragments in one geometry pass, then composites them in depth order, preserving relationships that VTK's default OpenGL transparency averages away. For nested scans and intersecting simulation surfaces, this gives us a clearer way to explore how the pieces fit together.📝Kitware Inc

Thursday, November 5, 2026

Wednesday, November 4, 2026

Kitware and UNC-Chapel Hill Release New Imaging Dataset Through ARPA-H AIR ProgramKitware and the University of North Carolina at Chapel Hill are releasing the first installment of the Multimodal Imaging Dataset for Cerebrovascular Disease through the Testbed for Autonomous Interventions and Robotics (TAIR) project. Developed as part of the Advanced Research Projects Agency for Health (ARPA-H) Autonomous Interventions and Robotics (AIR) program, this first-of-its-kind dataset combines video fluoroscopy recordings with corresponding CT/MR angiography data to support research in autonomous robotics and cerebrovascular disease.📝Kitware Inc

Tuesday, November 3, 2026