题解归档 - cf2237I2

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2237I2
• 本地来源：problems/cf2237I2/idea.md
• 题目链接：https://codeforces.com/contest/2237/problem/I2

思路

pattern:
stable sorting / hidden boundary quotient
claim:
For a fixed coloring, the traversal order equals sorting vertices by the number of color-1 vertices on the root path, with DFS preorder as the stable tie-breaker.
necessary:
A real adjacent level boundary y is visible only if some level-y vertex appears before a later level-(y-1) vertex in DFS order. Otherwise S_y is a DFS suffix and deleting that boundary does not change the sorted order.
sufficient:
The hard version cannot use the easy-version rule "final bad mask must be empty", because fixed-1 edges may force invisible real levels. It also cannot simply accept every bad boundary with a fixed-1 crossing; optional vertices in the same hidden suffix may duplicate another coloring.
brute/check:
brute.cpp enumerates all ? assignments and simulates the official deque process. Use it for n<=10 random stress before trusting a hard-version DP.
edge:

• star, labels ?1: both colorings output DFS order, but the optional first leaf at hidden level 1 is not a distinct traversal.
• tree 1 children 2,3; 2 child 4; labels ?11: choosing c2=1 gives levels 0,1,2,1 and output [1,2,3,4]. The hidden boundary 1 is below a visible boundary 2 and is necessary to separate vertex 4 from fixed-1 vertex 3.
• tree 1 children 2,3,4; 3 child 5; labels ?111: choosing c2=0 or c2=1 gives the same output [1,2,3,4,5], despite the same bad/fixed masks around boundary 1. A correct DP needs more than (height, bad mask, fixed-crossing mask).

current blocker:
The I1 state (h, bad mask) loses the DFS position of the suffix start for hidden boundaries. For I2, final projection must forget hidden suffix thresholds without losing the cases where those thresholds later support visible higher levels. Several candidate extensions (bad, forced), (bad, first_fixed), and (bad, first_fixed, any_fixed) passed n<=4 but failed exhaustive n=5.

useful reframing:
Every distinct output has a canonical visible rank assignment r: sort by the output order and start a new rank exactly at descents of DFS order. Thus all visible rank boundaries are good. For a fixed actual level assignment d, r is obtained by collapsing hidden adjacent level boundaries.

Feasibility of a canonical r can be viewed as inserting hidden offsets inside each visible rank block:

• color 0 edge: same visible rank and same hidden offset.

• color 1 edge:

  • either crosses to the next visible rank, so the parent must be at the top offset of its block and the child at offset 0 of the next block;
  • or stays in the same visible rank and increases hidden offset by 1.
• ? edge allows either 0 or 1 in the same sense.
• Inside one visible rank, hidden offsets must be nondecreasing in DFS order; otherwise stable sorting by actual levels would create another visible boundary.

This explains the earlier counterexamples:

• star 111...: any visible split would require the root to be simultaneously top of rank 0, but hidden fixed-1 leaves in rank 0 force a larger top offset; only all-collapsed output is feasible.
• labels ?11 on 1:[2,3], 2:[4]: the hidden boundary below visible boundary 2 is needed to place vertex 4 after fixed-1 vertex 3.

代码

来源：problems/cf2237I2/solution.cpp

/* Author: likely
 * Time: YYYY-MM-DD HH:MM:SS
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll s[maxn+5];
int main(){
    ll t,n,i,j,k,zc,pd,cur,dq,cnt,ans;
    cin>>t;
    while(t--){
        cin>>n;
        for(i=1;i<=n;i++) cin>>s[i];
    }
    return 0;
}