Znzryb's Blog

2026天梯赛选拔赛-L1-7-简单计数（赛时-号搞错成加号了，绷不住了）

Posted on 2026-03-15 Edited on 2026-03-16

题目大意

给定 $n$ 个人从左到右站成一排。每个人的身份只有两种：诚实者或欺诈者。

诚实者一定说真话。
欺诈者可能说真话，也可能说假话。
第 $i$ 个人会报一个数 $a_i$ ，表示“自己左边有多少个欺诈者”。
额外保证：不存在两个相邻的欺诈者。

任务是统计：一共有多少种身份安排（每个人是诚实者或欺诈者）能够与所有人的发言同时不矛盾。结果对 998244353 取模输出。

输入为两行：

第一行是 $n$ 。
第二行是 $n$ 个整数 $a_i$ 。

输出为一行：满足条件的方案数（取模后）。

样例：

输入：
6
0 0 0 0 0 0

输出：
2

样例含义：6 个人都说自己左边有 0 个欺诈者。在“欺诈者不相邻”的前提下，能成立的身份安排共有 2 种。

思路讲解

// 0 shuo huang
for(int i=1;i<=N;++i){
    if(i==1){
        if(A[i]==0){
            dp[i][1]=1;
            dp[i][0]=1;
        }else{
            dp[i][0]=1;
        }
        continue;
    }
    // 说谎者只能从前面一个的诚实者转移过来
    // 因为不能连续两个都是说谎者
    dp[i][0]=dp[i-1][1];
    if(A[i]==A[i-1]){
      // 可以从诚实者转移过来的条件
        dp[i][1]+=dp[i-1][1];
        dp[i][1]%=mod;
    }
    if(A[i]==A[i-2]+1){
      // 可以从说谎者转移过来的条件
      // 之所以是这个，是因为如果前面一个是说谎者的话，那么再前面一个就是诚实者
        dp[i][1]+=dp[i-1][0];
        dp[i][1]%=mod;
    }
}

AC代码

http://10.199.227.101/contest/1005/problem/L1-7/submission-detail/2146

源代码

#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":["<<x<<"]\n";
#define SZ(x) ((ll)x.size())
#define all(x) x.begin(),x.end()

using namespace std;
using ll = long long;
using DB = double;
const DB pi = acos(-1.0);
const ll mod = 998244353;
const ll INF = (1ll<<61)-1;
ll lT;

void Solve(){
    ll N;
    cin>>N;
    vector<ll> A(N+2);
    for(int i=1;i<=N;++i){
        cin>>A[i];
    }
    vector<array<ll,2>> dp(N+2);
    // 0 shu huang
    for(int i=1;i<=N;++i){
        if(i==1){
            if(A[i]==0){
                dp[i][1]=1;
                dp[i][0]=1;
            }else{
                dp[i][0]=1;
            }
            continue;
        }
        dp[i][0]=dp[i-1][1];
        if(A[i]==A[i-1]){
            dp[i][1]+=dp[i-1][1];
            dp[i][1]%=mod;
        }
        if(A[i]==A[i-2]+1){
            dp[i][1]+=dp[i-1][0];
            dp[i][1]%=mod;
        }

    }
    ll ans=dp[N][0]+dp[N][1];
    ans%=mod;
    cout<<ans<<"\n";

    // mod
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    //	cin>>lT;
    //	while(lT--)
    Solve();
}
/*




 */

心路历程（WA，TLE，MLE……）

2026天梯赛选拔赛-赛后总结

Posted on 2026-03-15 Edited on 2026-03-16

基本情况

还是有继续进步的这个空间的。

心得感悟

l1-3（while 写成 if）

l1-5（map 效率不够高）

原来使用了这个 map，对于 2e6 的这个数据，1000ms 的时限，可能不是很够。

#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":["<<x<<"]";
#define SZ(x) ((ll)x.size())
#define all(x) x.begin(),x.end()

using namespace std;
using ll = long long;
using DB = double;
const DB pi = acos(-1.0);
//const ll mod = 998244353;
const ll INF = (1ll<<61)-1;
ll lT;

void Solve(){
    ll N,mod;
    cin>>N>>mod;
    vector<ll> A(N+2);
    for(int i=1;i<=N;++i){
        cin>>A[i];
    }
    // map<ll,ll> mp;
    ll ans=0;
    vector<ll> cnt(mod+2);
    for(int i=1;i<=N;++i){
        ll r=A[i]%mod;
        cnt[r]++;
        if (cnt[r]==2) {
            ++ans;
        }
    }
    // for(auto it=mp.begin();it!=mp.end();++it){
    //     if(it->second>=2){
    //         ++ans;
    //     }
    // }
    cout<<ans<<"\n";
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    //	cin>>lT;
    //	while(lT--)
    Solve();
}
/*
AC
http://10.199.227.101/contest/1005/problem/L1-5/submission-detail/2134



 */

l1-7（+，-搞错了）

2026天梯赛选拔赛-L1-7-简单计数（赛时-号搞错成加号了，绷不住了）

l1-9（二分范围设置错误）

http://10.199.227.101/contest/1005/problem/L1-9/submission-detail/2144

赛时 r 写了r=N。（确实是比较搞笑了，因为 n 可能比 diff 小，diff 是一个值，N 是数组大小）

Codeforces Round 1086 (Div. 2)——CF-2208-D2. Tree Orientation (Hard Version)

Posted on 2026-03-15 Edited on 2026-03-16

题目大意

题目描述
有一棵包含 $n$ 个节点的无向树，为了让它更有趣，你对它的 $n-1$ 条边任意指定了方向，将其变成了一棵有向树。
现在你忘记了这棵树的结构和边的方向，但你找到了一份记录，上面写着给边指定方向后，所有节点对之间的可达性。具体来说，给定 $n$ 个长度为 $n$ 的 01 字符串。如果第 $i$ 个字符串的第 $j$ 个字符为 1，则表示在有向树中，节点 $i$ 可以到达节点 $j$ （必然存在一条从 $i$ 到 $j$ 的有向路径）；如果为 0 则表示无法到达。特别地，一个节点总是可以到达它自己。

你的任务是根据这个可达性信息，判断是否存在合法的树结构与边的方向。如果存在，请构造并输出任意一个满足条件的解；如果不存在，请输出 No。本题为 Hard 版本，与 Easy 版本的唯一区别是 $n$ 的数据范围更大。

输入格式
第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例的数量。
每个测试用例的第一行包含一个整数 $n$ （ $2 \le n \le 8000$ ），表示节点的数量。
接下来 $n$ 行，每行包含一个长度为 $n$ 的 01 字符串，表示可达性矩阵。
保证所有测试用例中 $n^2$ 的总和不超过 $8000^2$ 。

输出格式
对于每个测试用例，如果存在解，输出 Yes，并在接下来的 $n-1$ 行中输出构造的有向边。每行包含两个整数 $x$ 和 $y$ ，表示存在一条从 $x$ 指向 $y$ 的有向边。如果有多个解，输出任意一个即可。
如果不存在解，输出 No。
（输出 Yes 和 No 时不区分大小写，例如 yEs、YES 都会被接受）。

样例输入

样例输出

Yes
2 3
2 4
3 1
No
No
Yes
2 3
4 1
4 2
No
No
Yes
2 1
3 1
3 5
4 3
No
No
Yes
1 2
1 3
4 2
Yes
2 3
3 1

样例解释
对于第一个测试用例，给定的矩阵表示：节点 $1$ 和 $4$ 只能到达它们自己，节点 $2$ 可以到达所有节点，节点 $3$ 只能到达节点 $1$ 和 $3$ 。输出构造的边为 $2 \to 3$ 、 $2 \to 4$ 、 $3 \to 1$ ，这三条边构成了一棵合法的有向树，并且恰好满足上述可达性限制。
对于第二个测试用例，可以证明不存在任何合法的一棵树能够满足给定的可达性要求，因此输出 No。

思路讲解

Codeforces Round 1086 (Div. 2)——CF-2208-D1. Tree Orientation (Easy Version)

这道题目的简单版本确实是比较 easy 的。

Codeforces Round 1085 (Div. 1 + Div. 2)——CF-2207-E1. N-MEX (Constructive Version)

我觉得和这道题目有一点像，都是要使用这个贪心方法，来解决一些问题。

具体而言，我们要解决的，就是这个两个循环。我们发现，现在的问题在于，全部的 a，都要把全部的 b 给遍历一遍。这个太耗时耗力了。说白了，这个其实是一个连通性问题，即根节点 i，能不能通过一个中间点 b，访问到这个 a？当然，我们可以把

for (int i=1;i<=N;++i) {
    vector<ll> nodes;
    for (int j=1;j<=N;++j) {
        if (j==i) continue;
        if (Reach[i][j]=='1') {
            nodes.push_back(j);
        }
    }
    for (auto a:nodes) {
        bool ok=true;
        for (auto b:nodes) {
            if (b==a) continue;
            if (Reach[b][a]=='1') {
                ok=false;
                break;
            }
        }
        if (ok) {
            edges.push_back({i,a});
        }
    }
}

我们可以使用离线思想和排序思想，找到一种顺序，使得先处理顺序靠前的，后处理顺序靠后的，不会造成问题。

我们可以按照 cnt_reach（即所有可到达点的数量） 降序排序。

为什么降序排列有效？ cnt_reach 最大的节点，其子树规模最大。在合法树中， $i$ 的各个孩子的子树是互不相交的。最大子树的根必定是直系孩子（不可能被更小的子树"遮挡"），所以先处理最大的是安全的。

for (int i=1;i<=N;++i) {
    vector<ll> nodes;
    dsu.init(N);
    for (int j=1;j<=N;++j) {
        if (j==i) continue;
        if (Reach[i][j]=='1') {
            nodes.push_back(j);
        }
    }
    ll guard=0;
    sort(all(nodes),[&](const ll &a,const ll &b) {
        return cnt_reach[a]>cnt_reach[b];
    });
    for (auto a:nodes) {
        // 想恶意卡我？没门
        if (guard>N) {
            cout<<"No\n";
            return;
        }
        if (!dsu.same(i,a)) {
            guard+=cnt_reach[a];
            edges.emplace_back(i,a);
            dsu.merge(i,a);
            for (auto b:node_reach[a]) {
                dsu.merge(i,b);
            }
        }
    }
}

AI对我们做法的总结

虽然我无法访问到当前的文件系统（worktree 似乎已被清理），但根据我们之前的深入讨论和我读过的代码，我可以完整总结我们的做法。

总结：D2. Tree Orientation (Hard Version) 的做法

核心思路

给定一个 $n \times n$ 的可达性矩阵 Reach，要求还原一棵 $n$ 个节点的有向树（ $n-1$ 条边）使得可达性与输入一致。
关键观察：如果 Reach[i][j] = '1'，说明 $i$ 能到达 $j$ 。在有向树中， $i$ 的直系孩子 $c$ 满足： $i$ 能到 $c$ ，且不存在中间节点 $b$ 使得 $i \to b \to \cdots \to c$ 。
D1 的 $O(N^3)$ 做法是暴力三重循环：对每个 $i$ ，枚举候选孩子 $a$ ，再枚举所有其他节点 $b$ 检查 Reach[b][a] 来判断 $a$ 是否被某个 $b$ “遮挡”。

D2 的 $O(N^2)$ 优化

第一步：预处理。 对每个节点 $i$ ，计算 cnt_reach[i]（ $i$ 能到达的节点数，不含自身）和 node_reach[i]（ $i$ 能到达的节点列表）。
第二步：贪心找直系孩子。 对每个节点 $i$ ：

将 $i$ 能到达的所有节点按 cnt_reach 降序排列。
初始化一个局部 DSU。
按排好的顺序遍历候选节点 $a$ ：

若 dsu.same(i, a) 为真，说明 $a$ 已经被某个先前确认的孩子的子树覆盖，跳过。
否则， $a$ 是 $i$ 的一个直系孩子。连边 $(i, a)$ ，然后把 node_reach[a] 中的所有节点 merge 进 $i$ 的 DSU 分量，同时把 $a$ 本身也 merge 进去。
为什么降序排列有效？ cnt_reach 最大的节点，其子树规模最大。在合法树中， $i$ 的各个孩子的子树是互不相交的。最大子树的根必定是直系孩子（不可能被更小的子树"遮挡"），所以先处理最大的是安全的。
复杂度分析： 对合法输入，每个节点 $i$ 的所有直系孩子的子树大小之和恰好等于 $|R(i)| - 1$ ，即 merge 操作的总量不超过 $O(N)$ 。遍历候选也是 $O(|R(i)|)$ 。因此所有节点加起来是 $O(N^2)$ 。
第三步：防御性 guard。 累加实际被选为孩子的节点的 cnt_reach 值（仅对真正的孩子累加，不是对所有候选节点）。如果这个累加和超过 $N$ ，说明输入矩阵不合法，直接输出 “No”。这个 guard 同时也防止恶意输入把复杂度卡到 $O(N^3)$ 。
第四步：验证。 构造完所有边后：

检查边数是否恰好 $N-1$ 。
用 DSU 检查是否连通（构成一棵树）。
从每个节点 BFS，重建可达性矩阵 $R$ ，与输入 Reach 逐位比较。不一致则输出 “No”。

关键修复点（相比 D1 代码的改动）

用 DSU 替代 $O(N^3)$ 枚举：这是核心优化。不再对每个候选 $a$ 暴力枚举所有 $b$ 判断 Reach[b][a]，而是利用排序 + DSU 在 $O(N^2)$ 内完成。
guard 位置修正：guard += cnt_reach[a] 必须放在 if (!dsu.same(i,a)) 内部，只对实际选中的孩子计数。放在外面会对链状合法输入误判为 “No”。
自身 merge：确认孩子 $a$ 后，除了 merge node_reach[a] 的所有节点，还需要 dsu.merge(i, a) 把 $a$ 本身也并入。

一句话总结

按子树大小降序贪心 + DSU 快速跳过已覆盖节点 + BFS 回代验证，将 D1 的 $O(N^3)$ 传递归约优化为 $O(N^2)$ 。

AC代码

AC
https://codeforces.com/contest/2208/submission/366894699

源代码

/**
 * Problem: D2. Tree Orientation (Hard Version)
 * Contest: Codeforces Round 1086 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2208/problem/D2
 * Created: 2026-03-16 13:00:28
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */


/**   并查集（DSU）
 *    2023-08-04: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=63239142 (base on jiangly)
 *    2025-11-08: https://frp-shy.com:32768/domjudge/team H题 增加dsu on next，标记区间l，r的功能
 *    为了适配这个dsu on next，对merge 函数合并方向进行了修改。
 *    2025-12-05：https://codeforces.com/contest/2171/submission/351963922
 *    增加了 countFa 功能
 *    2025-12-23：移除了宏定义，增加功能说明模块。
 *    功能说明：dsu on next，find(x)，就是在 x 之后第一个没有被标记的数字
 *    该 dsu 传入构造函数的这个大小，需要是 n 就是 n，如果你不希望 countFa 出错的话。
**/
struct DSU {
    vector<int> fa/*, siz*/;
    ll n;

    DSU() {}
    DSU(ll n):n(n){
        init(n);
    }

    void init(ll n) {
        n+=5;
        fa.resize(n);
        for(int i=0;i<SZ(fa);++i) {
            fa[i]=i;
        }
        // siz.assign(n, 1);
    }

    ll find(ll x) {
        while (x != fa[x]) {
            x = fa[x] = fa[fa[x]];
        }
        return x;
    }

    bool same(ll x,ll y) {
        return find(x) == find(y);
    }

    bool merge(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        // siz[y] += siz[x];
        fa[x] = y;
        return true;
    }

    // ll size(ll x) {
        // return siz[find(x)];
    // }

    // dsu on next 技巧，直接标记 [l,r] 这段区间
    // 标记就是指让[l,r]这段区间里的所有数字这个都不指向自己
    // 可以理解为指向 r+1
    void taglr(ll l,ll r) {
        l=max(0ll,l);
        r=min(SZ(fa)-2,r);
        l=find(l);
        while(l<=r) {
            merge(l,l+1);
            l+=1;
            l=find(l);
        }
    }
    // 如果想让 countFa 结果准确，传入的 n 必须不多不少
    ll countFa() {
        ll res=0;
        for(int i=1;i<=n;++i) {
            if (fa[i]==i) {
                ++res;
            }
        }
        return res;
    }
};

void Solve() {
    ll N;
    cin >> N;
    vector<vector<char>> Reach(N+2,vector<char>(N+2));
    vector<vector<int>> node_reach(N+2);
    vector<ll> cnt_reach(N+2);
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=N;++j) {
            cin>>Reach[i][j];
            if (j==i) continue;
            if (Reach[i][j]=='1') {
                cnt_reach[i]++;
                node_reach[i].push_back(j);
            }
        }
    }
    vector<pair<ll,ll>> edges;
    DSU dsu(N);
    for (int i=1;i<=N;++i) {
        vector<ll> nodes;
        dsu.init(N);
        for (int j=1;j<=N;++j) {
            if (j==i) continue;
            if (Reach[i][j]=='1') {
                nodes.push_back(j);
            }
        }
        ll guard=0;
        sort(all(nodes),[&](const ll &a,const ll &b) {
            return cnt_reach[a]>cnt_reach[b];
        });
        for (auto a:nodes) {
            // 像恶意卡我？没门
            if (guard>N) {
                cout<<"No\n";
                return;
            }
            if (!dsu.same(i,a)) {
                guard+=cnt_reach[a];
                edges.emplace_back(i,a);
                dsu.merge(i,a);
                for (auto b:node_reach[a]) {
                    dsu.merge(i,b);
                }
            }
        }
        // for (auto a:nodes) {
        //     bool ok=true;
        //     for (auto b:nodes) {
        //         if (b==a) continue;
        //         if (Reach[b][a]=='1') {
        //             ok=false;
        //             break;
        //         }
        //     }
        //     if (ok) {
        //         edges.push_back({i,a});
        //     }
        // }
    }
    do {
        DSU dsu_check(N);
        if (SZ(edges)!=N-1) {
            cout<<"No\n";
            return;
        }
        vector<vector<ll>> g(N+2);
        for (auto [u,v]:edges) {
            dsu_check.merge(u,v);
            g[u].push_back(v);
        }
        // 对化为无向图后，树的可达性作校验
        if (dsu_check.countFa()!=1) {
            cout<<"No\n";
            return;
        }
        // 直接模拟，校验我们所构造
        vector<vector<char>> R(N+2,vector<char>(N+2,'0'));
        for (int i=1;i<=N;++i) {
            queue<ll> q;
            q.push(i);
            R[i][i]='1';
            while (!q.empty()) {
                ll a=q.front();
                q.pop();
                for (auto v:g[a]) {
                    if (R[i][v]=='1') {
                        continue;
                    }
                    R[i][v]='1';
                    q.push(v);
                }
            }
        }
        for (int i=1;i<=N;++i) {
            for (int j=1;j<=N;++j) {
                if (Reach[i][j]!=R[i][j]) {
                    cout<<"No\n";
                    return;
                }
            }
        }
    }while (false);

    cout<<"Yes\n";
    for (auto [u,v]:edges) {
        cout<<u<<" "<<v<<"\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}


/*
AC
https://codeforces.com/contest/2208/submission/366894699

1
4
1000
1111
1010
0001

_______________[ Stress test, testcase 6170 INPUT ]_______________
1
4
1101
0100
1111
0001

_______________[ Stress test, testcase 6170 OUTPUT]_______________
No

*/

心路历程（WA，TLE，MLE……）

_______________[ Stress test, testcase 6170 INPUT ]_______________
1
4
1101
0100
1111
0001

_______________[ Stress test, testcase 6170 OUTPUT]_______________
No

Codeforces Round 1086 (Div. 2)——CF-2208-D1. Tree Orientation (Easy Version)

Posted on 2026-03-14 Edited on 2026-03-16

题目大意

题目描述
曾经有一棵包含 $n$ 个节点的无向树。为了让它更有趣，每条无向边都被随意赋予了一个方向，使其变成了一棵有向树。
现在树的结构和边的方向都遗失了，但给出了一份记录了这棵树连通性的矩阵。该连通性矩阵表现为 $n$ 个长度为 $n$ 的 01 字符串。如果第 $i$ 行的第 $j$ 个字符是 1，则代表在原图中存在一条从节点 $i$ 到节点 $j$ 的有向路径；如果是 0 则代表无法到达。（特别地，任何节点都始终可以到达它自身）。
你需要根据给出的连通性矩阵，判断是否存在符合条件的有向树结构。如果存在，请构造并输出任意一种满足条件的边连接方式；如果不存在，则指出无解。

输入格式
第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ )，表示测试用例的数量。
每个测试用例的第一行包含一个整数 $n$ ( $2 \le n \le 500$ )，表示树的节点数量。
接下来的 $n$ 行，每行包含一个长度为 $n$ 的仅由 0 和 1 组成的字符串。第 $i$ 个字符串的第 $j$ 个字符为 1 当且仅当节点 $i$ 可以到达节点 $j$ 。
保证所有测试用例中 $n^3$ 的总和不超过 $500^3$ 。

输出格式
对于每个测试用例，如果存在满足条件的有向树，输出 Yes（大小写均可），并在随后的 $n-1$ 行中输出你构造的有向边。每行输出两个整数 $x$ 和 $y$ ，表示存在一条从 $x$ 指向 $y$ 的有向边（即 $x \to y$ ）。如果有多种合法的树结构，输出其中任意一种即可。
如果不存在满足条件的解，输出 No。

样例输入

样例输出

Yes
2 3
2 4
3 1
No
No
Yes
2 3
4 1
4 2
No
No
Yes
2 1
3 1
3 5
4 3
No
No
Yes
1 2
1 3
4 2
Yes
2 3
3 1

样例说明
对于第一个测试用例，节点 $1$ 和 $4$ 只能到达它们自身；节点 $2$ 可以到达所有节点；节点 $3$ 可以到达节点 $1$ 和 $3$ 。构造的有向边为 $2 \to 3$ ， $2 \to 4$ ， $3 \to 1$ ，该结构刚好满足所有可达性限制。
对于第二个测试用例，可以证明不存在任何一种满足给出连通性的树结构。

说白了，就是给你点与点之间的联通情况，你要重建出一颗有向的树，能够满足题目的要求。

思路讲解

如果只是做一个 D1 的话，还是非常 easy 的。

只要一个点比如说 6，不出现在其他 2 可达的点中（比如说图上的 4,3,5,1）的可达性表上，那么 2,6 直接相连。（⚠️注意，之所以这么连，是因为如果不连这条边，可达性就无法满足了，我们采用这一策略是为了连最少的边，达到题目要求）

这个做法的正确性是这样的，如果不连我们的算法所选择的边，可达性就无法满足了。如果比我们的这个做法连的边更多，要么你一定会改变这个可达性规律，要么你会把一棵树，变成一个环。多也不行，少也不行，那我们的做法就是正确的了。

vector<pair<ll,ll>> edges;
for (int i=1;i<=N;++i) {
    vector<ll> nodes;
    for (int j=1;j<=N;++j) {
        if (j==i) continue;
        if (Reach[i][j]=='1') {
            nodes.push_back(j);
        }
    }
    for (auto a:nodes) {
        bool ok=true;
        for (auto b:nodes) {
            if (b==a) continue;
            // 检查是否出现在其他点的可达性表上
            if (Reach[b][a]=='1') {
                ok=false;
                break;
            }
        }
        if (ok) {
            edges.push_back({i,a});
        }
    }
}

当然，最后需要写一个校验程序，也非常 easy 啊，先写一个东西校验这个树结构是否正确，然后再直接跑一遍可达性判断，看看和题目给出的是否一致。

do {
    if (SZ(edges)!=N-1) {
        cout<<"No\n";
        return;
    }
    vector<vector<ll>> g(N+2);
    for (auto [u,v]:edges) {
        merge(u,v);
        g[u].push_back(v);
    }
    // 对化为无向图后，树的可达性作校验
    set<ll> st;
    for (int i=1;i<=N;++i) {
        ll fai=find(i);
        st.insert(fai);
    }
    if (SZ(st)!=1) {
        cout<<"No\n";
        return;
    }
    // 直接模拟，校验我们所构造
    vector<vector<char>> R(N+2,vector<char>(N+2,'0'));
    for (int i=1;i<=N;++i) {
        queue<ll> q;
        q.push(i);
        R[i][i]='1';
        while (!q.empty()) {
            ll a=q.front();
            q.pop();
            for (auto v:g[a]) {
                if (R[i][v]=='1') {
                    continue;
                }
                R[i][v]='1';
                q.push(v);
            }
        }
    }
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=N;++j) {
            if (Reach[i][j]!=R[i][j]) {
                cout<<"No\n";
                return;
            }
        }
    }
}while (false);

AC代码

AC
https://codeforces.com/contest/2208/submission/366753217

源代码

/**
 * Problem: D1. Tree Orientation (Easy Version)
 * Contest: Codeforces Round 1086 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2208/problem/D1
 * Created: 2026-03-15 10:58:12
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
ll fa[MAXN];
ll find(ll x) {
    if (x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void merge(ll x,ll y) {
    ll fax=find(x),fay=find(y);
    if (fax==fay) {
        return;
    }
    fa[fax]=fay;
}
void Solve() {
    ll N;
    cin >> N;
    for (int i=1;i<=N;++i) {
        fa[i]=i;
    }
    vector<vector<char>> Reach(N+2,vector<char>(N+2));
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=N;++j) {
            cin>>Reach[i][j];
        }
    }
    vector<pair<ll,ll>> edges;
    for (int i=1;i<=N;++i) {
        vector<ll> nodes;
        for (int j=1;j<=N;++j) {
            if (j==i) continue;
            if (Reach[i][j]=='1') {
                nodes.push_back(j);
            }
        }
        for (auto a:nodes) {
            bool ok=true;
            for (auto b:nodes) {
                if (b==a) continue;
                if (Reach[b][a]=='1') {
                    ok=false;
                    break;
                }
            }
            if (ok) {
                edges.push_back({i,a});
            }
        }
    }
    do {
        if (SZ(edges)!=N-1) {
            cout<<"No\n";
            return;
        }
        vector<vector<ll>> g(N+2);
        for (auto [u,v]:edges) {
            merge(u,v);
            g[u].push_back(v);
        }
        // 对化为无向图后，树的可达性作校验
        set<ll> st;
        for (int i=1;i<=N;++i) {
            ll fai=find(i);
            st.insert(fai);
        }
        if (SZ(st)!=1) {
            cout<<"No\n";
            return;
        }
        // 直接模拟，校验我们所构造
        vector<vector<char>> R(N+2,vector<char>(N+2,'0'));
        for (int i=1;i<=N;++i) {
            queue<ll> q;
            q.push(i);
            R[i][i]='1';
            while (!q.empty()) {
                ll a=q.front();
                q.pop();
                for (auto v:g[a]) {
                    if (R[i][v]=='1') {
                        continue;
                    }
                    R[i][v]='1';
                    q.push(v);
                }
            }
        }
        for (int i=1;i<=N;++i) {
            for (int j=1;j<=N;++j) {
                if (Reach[i][j]!=R[i][j]) {
                    cout<<"No\n";
                    return;
                }
            }
        }
    }while (false);

    cout<<"Yes\n";
    for (auto [u,v]:edges) {
        cout<<u<<" "<<v<<"\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2208/submission/366753217

*/

心路历程（WA，TLE，MLE……）

Codeforces Round 1086 (Div. 2)——CF-2208-赛后总结

Posted on 2026-03-14 Edited on 2026-03-15

基本情况

这个打的不算太好。

但是，说实话嘛，这个 C 确实没对上脑电波。 Codeforces Round 1086 (Div. 2)——CF-2208-C. Stamina and Tasks（赛时 AC）（确实，乘法衰减，概率 dp，都是用这个反向居多）所以说做的比较慢。

这个 A 唐完了，我以为要构造那个矩阵，就过只要判断 yes，no。还因为 > 写成了 ≥ WA 了一发。

心得感悟

还是要看清楚是不是需要构造。

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

基本情况

心得感悟

l1-3（while 写成 if）

l1-5（map 效率不够高）

l1-7（+，-搞错了）

l1-9（二分范围设置错误）

题目大意

思路讲解

虽然我无法访问到当前的文件系统（worktree 似乎已被清理），但根据我们之前的深入讨论和我读过的代码，我可以完整总结我们的做法。

总结：D2. Tree Orientation (Hard Version) 的做法

核心思路

D2 的 O(N2)O(N^2)O(N2) 优化

关键修复点（相比 D1 代码的改动）

一句话总结

AC代码

心路历程（WA，TLE，MLE……）

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

基本情况

心得感悟

D2 的 $O(N^2)$ 优化