Znzryb's Blog
0%

Posted on

题目大意

题目大意

有 2n2n 张卡片排成一排，卡片上分别写着数字 1,1,2,2,…,n,n1, 1, 2, 2, \dots, n, n，初始时全部背面朝上。

你将使用以下“贪心”策略来进行翻牌游戏，每回合精确地翻开两张卡片：

  1. 如果你之前已经翻开过（且未被消除）两张数字相同的卡片，则直接翻开并消除它们。

  2. 否则，翻开从左到右第一张从未被翻开过的卡片，设其数字为 xx。

  3. 接着，如果之前已经翻开过另一张数字为 xx 的卡片，则翻开并消除它。

  4. 否则，再次翻开从左到右第一张从未被翻开过的卡片。如果这两张卡片数字相同，则消除；如果不同，则重新翻回背面。

给定 nn 和 kk，要求构造一个 11 到 nn 各出现两次的排列，使得上述算法恰好需要 kk 个回合才能消除所有卡片。如果存在这样的排列，输出 YES 并输出该排列；否则输出 NO。

输入格式

第一行包含一个整数 tt（1≤t≤1031 \le t \le 10^3），表示测试数据组数。
接下来每组数据包含一行，包含两个整数 nn 和 kk（1≤n≤3×1051 \le n \le 3 \times 10^5，1≤k≤1061 \le k \le 10^6）。
保证所有测试数据中 nn 的总和不超过 3×1053 \times 10^5。

输出格式

如果不存在满足条件的卡片排列，输出一行 NO。
如果存在，输出一行 YES，并在下一行输出 2n2n 个整数 a1,a2,…,a2na_1, a_2, \dots, a_{2n}（1≤ai≤n1 \le a_i \le n），表示卡片上的数字排列。如果有多个合法的排列，输出任意一个即可。

样例输入

1
2
3
4
5
6
7
6
2 3
3 4
3 2
3 5
6 10
6 67

样例输出

1
2
3
4
5
6
7
8
9
10
YES
2 1 2 1
YES
1 3 2 2 1 3
NO
YES
1 2 3 1 2 3
YES
2 1 3 4 5 4 1 2 6 5 6 3
NO

样例解释

对于第一组样例，初始排列为 2 1 2 1，每回合的操作如下：

  • 第 11 回合：翻开第一张未翻过的卡片（数字 22），之前没有记录，接着翻开下一张未翻过的卡片（数字 11）。数字不同，翻回背面。此时记下前两张卡片的数字为 22 和 11。

  • 第 22 回合：翻开第一张未翻过的卡片（第三张，数字 22），由于之前已经翻开过数字为 22 的卡片（第一张），因此翻开第一张，两张卡片相同并消除。

  • 第 33 回合：翻开第一张未翻过的卡片（第四张，数字 11），由于之前已经翻开过数字为 11 的卡片（第二张），因此翻开第二张，两张卡片相同并消除。
    游戏结束，共花费 33 个回合。

对于第四组样例，初始排列为 1 2 3 1 2 3，每回合的操作如下：

  • 第 11 回合：翻开第一、第二张从未翻过的卡片，数字分别为 11 和 22。数字不同，翻回背面。

  • 第 22 回合：翻开第三、第四张从未翻过的卡片，数字分别为 33 和 11。数字不同，翻回背面。

  • 第 33 回合：此时发现之前翻开过（且未消除）的卡片中存在两张数字相同的卡片（第一张和第四张均为 11），触发规则第一条，直接翻开这两张卡片并消除。

  • 第 44 回合：没有两张已翻开且相同的卡片。翻开第五张卡片（数字 22），由于之前翻开过数字 22（第二张卡片），因此翻开第二张卡片并消除。

  • 第 55 回合：翻开第六张卡片（数字 33），由于之前翻开过数字 33（第三张卡片），因此翻开第三张卡片并消除。
    游戏结束，算法恰好在 k=5k=5 回合赢得游戏。

注意啊，这是一个翻牌游戏，就是一开始你是不知道这些数字，它的大小，你需要翻开来你才知道。

image

思路讲解

这个题实在是太简单了，我操，哎呀，真的是后悔为什么没看这题。

image

不难发现，在这种位置交换一下，就会增加一次这个轮数，那么你就把所有的这些位置，就是你就交换他要求的这个轮数啊，当然是比N多的这个轮数然后就就好了。也就是把我们所找到的这个位置交换我们代码当中的REM次就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
ll rem=K-N;
for (int cnt=1,i=2;cnt<=rem;++cnt,i+=2) {
    if (i>=N2) {
        cout<<"NO\n";
        return;
    }
    swap(ans_ls[i],ans_ls[i+1]);
}
cout<<"YES\n";
for (int i=1;i<=N2;++i) {
    cout<<ans_ls[i]<<" ";
}
cout<<"\n";

AC代码

https://codeforces.com/contest/2202/submission/364156796

Posted on Edited on

基本情况

更新一下，虽然说其实我用小号打的其实也无所谓的，但是这个 D 还是不多评价，太简单了。当然了，也没有简单到说5分钟就能做出来了，但是我确实应该用了多久啊？我可以看一眼。应该是用了不到半个小时，还不是特别急吼拉轰的情况下，就做出来了这个赛事，估计半小时以内，肯定是能搞定的。这个实在是，不多评价了这个 D 哎呀。。

image

https://codeforces.com/contest/2202

做出来4道题目啊，div2 做出来4道题目还是比较满意的。

应该是 C1 WA 了一发，其实也总结不出来什么，因为 C1 Wrong answer 的地方比较隐蔽。对拍也要拍100多组，得用数据生成器设置的比较好，输出比较长，也要拍100多组才能拍出错的地方，所以还是比较隐蔽的，总的来说也总结不出什么东西来。那么Wrong awnser on test three, 所以它并不是wrong answer on test two，而实测test two应该也是一个比较强的，不是很水，就是一个两个点，其实还是有一个，它是多策，还是比较强的。

下面来看一看，就是每道题目的解法，以及解题的过程和思路，我稍微总结一下。

A题的题目意思是有各种跑酷的移动方式，只有3种，不难发现这3种移动方式，如果你想要实现平动，那么平动必须是3的倍数，所以需要%3一下，看是不是3的倍数，然后注意排除一下负数情况。那么，至于你想问我怎么知道平动需要多少呢？实际上平动需要多少呢？就是向上动一定附带了平动吧，因为我们向上动都是加1+一或者是减1-1，他没有什么疑问啊，所以说这个把这个向上动的附带平动给减掉以后，它不能是一个负数然后剩下的这个值，我们去执行一下上面的一个这个检查

那么这个B题我们采用的是贪心做法，首先我们会发现，如果双端队列的两端都和SI相同，那么无论操作哪一端无所谓的，因为它们都是对称的，然后剩下就是对于问号的处理。

问号的处理是这样的，我们维护一个问号。我们希望处理这个问号以后，不要对后面的处理，造成这个困难或各种问题，我们知道后面一个不是问号的字符是什么，后面一个我们一旦知道不是问号的字符，然后我们就不要去动那个和后面一个不是问号的字符相同的端就行了。

这个C1，其实是贪心啊，C1 的题目意思是问你能用最少的A中的元素生成整个A数组，用题目当中的这种向后插入其+1的方式。

那么我们的思路其实并不复杂，我们就是一开始想的就是维护类似于 123456 这样子的连续递增块吗。

1
2
3
4
5
6
7
8
9
10
11
12
13
1
9
9 8 9 2 3 4 4 5 3

_______________[ Stress test, testcase 117 INPUT ]_______________
1
9
2 3 4 3 5 2 2 3 3

_______________[ Stress test, testcase 117 OUTPUT]_______________
3

[-] FAILURE: WRONG ANSWER

然后我们发现，题目中的最后一个样例比较强。你会发现234453，它也是一个联通的块，所以说这个，它并不是说一定要是单调不降或者是递增。于是，非常自然，我们可以维护一个该数组或该段落，它可以接受的所有的接在其后面的值。我们的这个代码当中使用了vector套，vector的这个 g vector去维护。

通过这个对拍，我们会发现能够跟在它后面的值会随它变化，比如234453，这个时候你想在3后面再加一个5是不可以的，但前面如果是是23445，然后再加一个5，没有问题，所以它会随着后面缩小以后，它这个我们所维护的，能够接受所有的接在其后面的值的这个序列，它也会发生变化。

这个具体的变化逻辑是使用lower bound实现的，具体就看代码吧。

C2前面我感觉难度还是有一点，所以没花太大力气，时间也比较多，比较随意。主要是喝水，看看视频，再看C2，这个C2总体上来说还是比较顺利的，C2就是在这个C1的基础上，要求你求出全部的它的子段的的这个和。

具体来讲呢，如果说你把这个C1看作一个 solve 函数，那么C2所需要求的值就是这样子的。这个其实就是我们的C，R的暴力程序，虽然其实没有用上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    ll ans=0;
    for (int l=1;l<=N;++l) {
        for (int r=l;r<=N;++r) {
            vector<ll> sub(A.begin()+l,A.begin()+r+1);
            sub.insert(sub.begin(),0);
            ans+=solve(sub,r-l+1);
        }
    }
    cout<<ans<<"\n";
}

实际上是这样子的，去求C2，你要采用贡献的方法，采用算贡献的方法。我们维护了一个A的值，首先，我们便利到癌的时候，我们就要计算包含这个I，以I为结尾的，所有的以这个I为结尾的子串子数组会贡献多少答案？

那么这个代码中的A，你可以理解为什么？所有以前的点在I之前的点，如果包含了I以后会增加多少？因为包含了I这个点以后，就是I能在多少个他前面的点当中进行贡献，就是如果说是和是包含了同段的一些值的话，那么实际上它是没法贡献的。所以说，一个正常的不是子负数开始值，实际上只会贡献一个答案。如果你是子数组的开始值，那么，就会贡献下标为I的答案。那么，如果说你是会去缩小这个区间长度的话，你缩小区间长度的话，你对A的，你对这个答案的贡献就是你的下标减去减去it的下标，减去那个it ID的下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 我想要在这里处理的时候，直接把这个块内部的答案给解决掉
for (int i=1;i<=N;++i) {
    if (g.empty()) {
        g.push_back({{A[i]+1,i}});
        // g_id.push_back({i});
        ans++;
        add++;
        continue;
    }
    if (is_find(A[i])/*binary_search(all(g.back()),A[i])*/ ) {
        if (A[i]==g.back().back().val) {
            g.back().push_back({A[i]+1,i});
            // g_id.back().push_back(i);
            add++;
            ans+=add;
        }else {
            auto it=lower_bound(all(g.back()),(Val_id){A[i]+1,0});
            add+=(i-it->id+1);
            ll new_size=it-g.back().begin()+1;
            g.back().resize(new_size);
            // g_id.back().push_back(i);
            ans+=add;
        }
        // g_id.back().push_back(i);
    }else {
        g.push_back({{A[i]+1,i}});
        // g_id.push_back({i});
        add+=i;
        ans+=add;
    }
}

心得感悟

Posted on Edited on

题目大意

https://codeforces.com/contest/2110/problem/E

题目描述
给定 nn 个不同的声音，每个声音由音量 viv_i 和音高 pip_i 两个属性组成。
你需要将这 nn 个声音排列成一个序列，每个声音恰好出现一次。
一个合法的序列需要同时满足以下两个条件：

  1. 任意两个相邻的声音，必须且仅有一个属性相同（即要么音量相同且音高不同，要么音高相同且音量不同）。

  2. 任意连续的三个声音，它们的音量不能完全相同，音高也不能完全相同（即不能出现连续三个声音音量一样，也不能出现连续三个声音音高一样）。

请判断是否存在这样的合法序列。如果存在，输出 YES 以及排列后各个声音的初始编号；如果不存在，输出 NO。

输入格式
第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试用例的数量。
每个测试用例的第一行包含一个整数 nn（1≤n≤2⋅1051 \le n \le 2 \cdot 10^5），表示声音的数量。
接下来的 nn 行，每行包含两个整数 viv_i 和 pip_i（1≤vi,pi≤1091 \le v_i, p_i \le 10^9），分别表示第 ii 个声音的音量和音高。保证同一个测试用例中不会出现音量和音高都完全相同的两个声音。
所有测试用例中 nn 的总和不超过 2⋅1052 \cdot 10^5。

输出格式
如果存在合法的序列，第一行输出 YES，第二行输出 nn 个整数，表示合法的声音排列顺序对应的原始编号（从 1 开始）。
如果不存在，输出 NO。YES 和 NO 忽略大小写。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
输入：
5
4
179 239
179 179
239 179
239 239
3
1 1
2 1
3 1
1
5 7
5
1 1
1 2
2 1
2 2
99 99
7
1 1
1 3
2 1
2 2
3 1
3 2
3 3

输出：
YES
4 3 2 1
NO
YES
1
NO
YES
3 4 6 7 2 1 5

样例解释
在第一个测试用例中，按照 4, 3, 2, 1 的顺序排列，声音序列为：(239,239)−(239,179)−(179,179)−(179,239)(239,239)-(239,179)-(179,179)-(179,239)。包含了所有的声音，并且任意两个相邻的声音都仅有一个属性（音量或音高）不同，满足所有条件。
在第二个测试用例中，3 个声音的音高全部是 1，这意味着无论如何排列，都会出现连续三个声音音高相同的情况，因此无法构造合法的序列。

思路讲解

Codeforces Round 1081 (Div. 2)-CF-1081-E. Swap to Rearrange（按值进行图论建模）（欧拉回路）

注意，欧拉路径存在的充要条件（在无向连通图上），就是奇数度数节点数量等于0 或者 2。说白了，就是相比于回路，我们允许你的这个起点和终点搞点怪，只进不出或者只出不进，但是我们不允许你的其他点违反这一法则。

这两道题目应该是比较类似的。

在算法竞赛中，采用排除法还是一个比较好的办法。这道题目其实还是一样的，其他方法不太适合解决这种问题，那么只能够求助于图论建模了。

我们想问怎么样建这张图，实际上这个题目是rearrangement问题，它只有一个可以连边的东西，对吧，那就是V和P之间去连，V和P之间按值连接。这也是使用排除法，因为其他东西你都不知道，它怎么排，你怎么去连，对吧。

image

然后我们还是一样的套路，就是一开始是一张无向图，然后通过遍历进行定向。然后我们怎么样进行这个呢？这个遍历需要遵循怎样的规则呢？我个人认为呢，这个遍历所需要遵循的规则就是，首先它不能够去访问父节点（会造成连续的两个声音音量和音高重合），然后每条边仅遍历一次。

DFS写的话，这个递归它不符合这个线性特征，所以说的话不太适合。我们决定采用类似于CF 1081e的做法，但有一个问题，CF 1081e可以确保所有点的入度和出度。如果这张图是一张无像图，认为所有点的度数都是偶数，可以保证这一点，因为不保证这一点的图就是错的，输出no就可以了。但这道题不一定，如果作无像图，每个点的度数不一定是偶数，只是偶数时才有解，它可以不是偶数这也是可以的。

不过我们上面也说了，通过对欧拉路径的学习，我们知道：

奇数度数节点数量等于 0 或者 2。

注意还有判断图是否联通，这个也是非常重要的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
if (odd_cnt!=0 && odd_cnt!=2) {
    cout<<"NO\n";
    return;
}

vector<ll> ans_ls;
auto dfs=[&](auto && self,ll u) -> void {
    while (!g[u].empty()) {
        auto it=g[u].begin();
        auto [to,id]=*it;
        g[u].erase(it);
        g[to].erase({u,id});
        self(self,to);
        ans_ls.push_back(id);
    }
};
dfs(dfs,max(start_node,g.begin()->first));
// 判断图是否联通，如果不联通，也是错的。
if (SZ(ans_ls)!=N) {
    cout<<"NO\n";
    return;
}
reverse(all(ans_ls));
cout<<"YES\n";
for (auto u:ans_ls) {
    cout<<u<<" ";
}
cout<<"\n";

为什么 Euler 路径红色这样子写有问题呢？其实也很容易理解，因为我们要把 ans_ls 反过来的呀！所以说，肯定需要先遍历完后续的点，才能塞入这条边啊！其实简单来说，就是要和正常的反过来！

image

还有我们要注意起点选择，就是DFS的起点是非常重要的。在欧拉路径当中，欧拉回路我们当然是无所谓，但是欧拉路径的这个起始位置是要注意的。

我们采用的策略是有奇数点就选奇数点，没有奇数点就选随便选一个点。

image

AC代码

AC
https://codeforces.com/contest/2110/submission/364850915

https://codeforces.com/contest/2110/submission/321091518

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

为什么 Euler 路径红色这样子写有问题呢？其实也很容易理解，因为我们要把 ans_ls 反过来的呀！所以说，肯定需要先遍历完后续的点，才能塞入这条边啊！其实简单来说，就是要和正常的反过来！

image

还有我们要注意起点选择，就是DFS的起点是非常重要的。在欧拉路径当中，欧拉回路我们当然是无所谓，但是欧拉路径的这个起始位置是要注意的。

我们采用的策略是有奇数点就选奇数点，没有奇数点就选随便选一个点。

image

Posted on Edited on

题目大意

题目名称：E. Swap to Rearrange

题目大意

给定两个长度为 nn 的数组 aa 和 bb。你可以对任意下标 ii (1≤i≤n1 \le i \le n) 执行至多一次操作：交换 aia_i 和 bib_i。

你的目标是通过选择若干个下标进行交换，使得操作结束后，数组 aa 变成数组 bb 的一个重排（即最终数组 aa 和最终数组 bb 包含完全相同的元素集合，只是顺序可能不同）。

如果可以达成目标，请输出操作次数以及被选择进行交换的下标；如果无法达成，请输出 -1。如果存在多种方案，输出任意一种即可。

输入格式

每个测试点包含多组数据。
第一行包含一个整数 tt (1≤t≤1041 \le t \le 10^4)，表示测试用例的数量。
对于每个测试用例：

  • 第一行包含一个整数 nn (1≤n≤1061 \le n \le 10^6)。

  • 第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n (1≤ai≤n1 \le a_i \le n)。

  • 第三行包含 nn 个整数 b1,b2,…,bnb_1, b_2, \dots, b_n (1≤bi≤n1 \le b_i \le n)。
    保证所有测试用例中 nn 的总和不超过 10610^6。

输出格式

对于每个测试用例：

  • 如果无解，输出 -1。

  • 否则，第一行输出操作次数 ss (0≤s≤n0 \le s \le n)。

  • 第二行输出 ss 个整数，表示被交换的下标（下标从 1 开始）。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
4
4
1 1 3 3
2 2 4 4
3
1 2 1
3 3 1
3
1 2 3
2 3 1
4
1 2 2 4
3 1 4 3

样例输出

1
2
3
4
5
6
7
2
2 4
-1
0

2
3 4

样例解释

  • 第一个测试用例：
    初始时 a=[1,1,3,3]a=[1, 1, 3, 3]，b=[2,2,4,4]b=[2, 2, 4, 4]。
    选择下标 2 和 4 进行交换：
    • 交换 a2a_2 和 b2b_2：aa 变为 [1,2,3,3][1, \mathbf{2}, 3, 3]，bb 变为 [2,1,4,4][2, \mathbf{1}, 4, 4]。
    • 交换 a4a_4 和 b4b_4：aa 变为 [1,2,3,4][1, 2, 3, \mathbf{4}]，bb 变为 [2,1,4,3][2, 1, 4, \mathbf{3}]。
      最终 a=[1,2,3,4]a=[1, 2, 3, 4]，b=[2,1,4,3]b=[2, 1, 4, 3]。此时 aa 和 bb 都包含元素 {1,2,3,4}\{1, 2, 3, 4\}，满足条件。

image

  • 第二个测试用例：
    无论如何操作，都无法使 aa 成为 bb 的重排，故输出 -1。

  • 第三个测试用例：
    不需要任何操作，a=[1,2,3]a=[1, 2, 3]，b=[2,3,1]b=[2, 3, 1]。两者包含的元素集合均为 {1,2,3}\{1, 2, 3\}，已经是重排关系。输出 0。

思路讲解

我感觉AI唬我呢，左看右看，东看西看，完全没看出这道题目为什么需要用图论。因为说白了，这根本不是一个一一对应的问题，对吧？这和图论有什么关系？无非其实就是要让数量相等呀，这个图论实在难以说有什么联系。所以说，我感觉这个AI其实有点乱写，opus4.6，其实也不过如此吧。

仔细的看了一下，应该这道题就是用图论建模做。我们下面用一张图来说明一下图论建模，它这个图是怎么建的。那为什么这道题目用图文建模呢？我认为这道题目首先不适合使用DP解决，因为你不知道以什么为状态。所以说，用DP解决是不可以，因为状态所需空间太大了，然后，其实我们也没什么工具的，要么就贪心啊，你也很难贪，是吧？所以其实也就图论建模了。

首先呢，我们只关注值，所以说我们所见的图呢，是按值连接的。

image

Codeforces Round 1026 (Div. 2)-CF-1026-E. Melody

就是看了洛谷的题解，体检上的这个人来说，这道题目和CF 1026的E比较相似。我稍微看了一下CF 1026的题面，应该是解法比较相似，都是建图，按值进行图论建模。

剩下的就是找欧拉回路了，哎，怎么就突然扯到欧拉回路了呢？首先我们肯定要找一个回路嘛，如果一个连通分量中每个点的入度和出度一致，那么就说明该连通分量可以变成，或者说，该连通分量就是由一系列环构成的。当然了，由一系列环构成可能不能辅助我们实现，实际上它就是一个回路。我们可以使用欧拉回路的方法，把图中的每条边都消耗掉，欧拉回路是每条边恰好被遍历过一次，就是每条边都被恰好遍历一次组成的闭合路径，就是欧拉回路。这个和我们所说的由一系列环构成是一样的，其实是一个意思。存在欧拉回路的这个条件也很简单，就是每个顶点的度数都是偶数，那么一定存在一条欧拉回路（在联通无向图中）。

不过，由于这里我们不需要求欧拉回路，我们只是想要把这个图给建成一个环形的这个嵌套组合，那么实际上是非常简单的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 开始图论建模
vector<vector<To_id>> g(N+2);
vector<char> vis_edge(N+2);
for (int i=1;i<=N;++i) {
    g[A[i]].push_back({B[i],i,0});
    g[B[i]].push_back({A[i],i,1});
}
for (int i=1;i<=N;++i) {
    if (SZ(g[i])%2!=0) {
        cout<<-1<<"\n";
        return;
    }
}
vector<ll> ans_ls;
// 我们这里不需要求欧拉回路，我们只是想要把这个图给建成一个环形的这个嵌套组合，那么实际上是非常简单的
for (int st_node=1;st_node<=N;++st_node) {
    if (g[st_node].empty()) continue;
    ll u=st_node;
    while (!g[u].empty()) {
        auto [to,id,inv]=g[u].back();
        g[u].pop_back();
        if (vis_edge[id]) {
            continue;
        }
        vis_edge[id]=true;
        if (inv) {
            ans_ls.push_back(id);
        }
        u=to;
    }
}
sort(all(ans_ls));
cout<<SZ(ans_ls)<<"\n";
for (auto u:ans_ls) {
    cout<<u<<" ";
}
cout<<"\n";

AC代码

AC
https://codeforces.com/contest/2192/submission/363992212

Posted on Edited on

基本情况

打的还是挺不错的。一共做出来四道题，做出来四道题。这个 D 题是最后 A 的，D 题是最后 A 的。哎，D 题这个叫什么，稍微有点唐了，这漏了这两行有点唐了。还有这个 C 啊，读错题目了。这个 C 读错题目了，绷不住了，我自己给自己上难度啊，以为这个弹夹可以不打完就就换，这个弹夹可以不打完就换，自己给自己上难度。以后遇到这个题目啊，就是如果我们发现这道题目，就是我们还是要确定一下，就是一些限制条件，我们还是要想办法确定一下。

然后这个 d 的这个情况也是比较唐的，就这个 d 漏的这两行比较唐吧。是这样子，我感觉呢，以后这种如果说有多个，然后需要取 max 的话，最好啊 最好就是多整几行，多整几个变量，整个 add1 add2，这样子就你你不会忘记去给它进行这么一个赋值。然后你 add 1，你写出来，你不用，编译器还会报警，IDE 还会报警，对吧？你 add 1没用，你就知道你要把它取个 max 对吧？

https://codeforces.com/contest/2192

1
2
3
4
5
6
7
8
9
10
11
12
if (a.id!=b.id) {
    add=a.dep*b.suma;
    add_mx=max(add,add_mx);
}else {
    a=*prev(prev(mx_diff_st.end()));
    add=a.dep*b.suma;
    add_mx=max(add,add_mx);
    a=*mx_diff_st.rbegin();
    b=*prev(prev(mx_a_st.end()));
    add=a.dep*b.suma;
    add_mx=max(add,add_mx);
}

image

心得感悟

下面是和队友对 D 题的这个探讨。

ZnZrYb: 02-22 00:36:59
首先是树上 dp

ZnZrYb: 02-22 00:37:38
auto dfs2=[&](auto && self,ll u,ll p,ll dep) -> void {
dep_ls[u]=dep;
set<Dep_sub> mx_diff_st;
set<A_sub> mx_a_st;
ll id=0;
ll add_mx=0;
for (auto to:g[u]) {
if (to==p) continue;
self(self,to,u,dep+1);
dp[u]+=dp[to];
dp[u]+=sum_a[to];
sum_a[u]+=sum_a[to];
add_mx=max(add_mx,ans_ls[to]-dp[to]);
mx_dep[u]=max(mx_dep[to],mx_dep[u]);
++id;
mx_diff_st.insert({id,mx_dep[to]-dep});
mx_a_st.insert({id,sum_a[to]});
}
if (id>=2) {
Dep_sub a=mx_diff_st.rbegin();
A_sub b=mx_a_st.rbegin();
ll add=0;
if (a.id!=b.id) {
add=a.dep*b.suma;
add_mx=max(add,add_mx);
}else {
a=prev(prev(mx_diff_st.end()));
add=a.depb.suma;
add_mx=max(add,add_mx);
a=*mx_diff_st.rbegin();
b=prev(prev(mx_a_st.end()));
add=a.depb.suma;
add_mx=max(add,add_mx);
}
}
ans_ls[u]=dp[u]+add_mx;
sum_a[u]+=A[u];
mx_dep[u]=max(dep,mx_dep[u]);
};

ZnZrYb: 02-22 00:37:54
答案在这个 ans

鵗曦: 02-22 00:39:12
我是先枚举移动各个节点，显然移动该节点最好办法就是移动到子树外的最深节点，移完之后贡献变化是高度差乘以子树的系数和

ZnZrYb: 02-22 00:39:19
具体来说就是这个增量可以从，就是子节点里面来，就是可以从子节点里面来。然后这个增量也可以就是我们自己来操作。自己来操作的话，是使用的 Max D I F F S T 和 Max A S T。其实就是把最大的 sum A 嫁接到最大的深度指数上。但如果说最大的深度指数和最大的 sum A 是同一个的话，需要稍微进行一下其他处理。

鵗曦: 02-22 00:39:29
然后每个节点的答案就是子树的最大值。

鵗曦: 02-22 00:40:10
我是这么想的，但是写不对。

鵗曦: 02-22 00:40:48
你觉得对不对

鵗曦: 02-22 00:40:51
[图片]

鵗曦: 02-22 00:41:14
diffst和ast是啥玩意

ZnZrYb: 02-22 00:42:13
diff_st 存的是子树深度差值。 AST 就是存的是子树权值和

ZnZrYb: 02-22 00:43:01
我觉得这个思路挺对的

鵗曦: 02-22 00:43:53
按我这么写，需要用的信息可以O（n）维护出来。唯一的难点就是要查子树外的最深节点

鵗曦: 02-22 00:44:02
然后咱想的是上个树剖

ZnZrYb: 02-22 00:44:15
啊

鵗曦: 02-22 00:44:24
因为一个子树在dfn上是连续的。

鵗曦: 02-22 00:44:37
所以可以查前面一整段和后面一整段，取其中的深度最大值。

鵗曦: 02-22 00:44:44
但是写的不对

鵗曦: 02-22 00:44:51
[图片]

ZnZrYb: 02-22 00:44:55
懂了

ZnZrYb: 02-22 00:45:50
那就上个 st 表都能解决

ZnZrYb: 02-22 00:46:03
感觉挺对的

鵗曦: 02-22 00:46:13
过不去样例

鵗曦: 02-22 00:46:16
写炸了

ZnZrYb: 02-22 00:46:21
[笑哭]

鵗曦: 02-22 00:46:57
dfn序列用st表预处理是吧

鵗曦: 02-22 00:47:14
咱的树剖板子默认写了线段树

ZnZrYb: 02-22 00:47:22
哦，我知道你可能是哪里的问题了

鵗曦: 02-22 00:47:41
哪里

ZnZrYb: 02-22 00:48:34
不过我不确定，就是你限定了树的范围了吧，就是他求的是 i 的子树

ZnZrYb: 02-22 00:48:38
的答案

鵗曦: 02-22 00:49:16
不是输出每个节点对应的答案吗

鵗曦: 02-22 00:49:26
每个节点的操作是可以任意选择它指数里面的一个节点进行嫁接

鵗曦: 02-22 00:49:34
子树

鵗曦: 02-22 00:49:57
所以每个节点的答案就是处理出来的子树里的最大值。

ZnZrYb: 02-22 00:51:36
感觉好像你没有理解错啊，你也是查询的子树里深度最大值是吧

鵗曦: 02-22 00:52:09
我已经枚举计算过了，假如要移动某某个节点，能产生的最大权重

鵗曦: 02-22 00:52:35
所以输出答案的时候，对于一个节点的答案，只需要找这个节点所在的子数里面计算出的各个最大权重中的最大

鵗曦: 02-22 00:52:47
当然也是O（n）就能弄出来的。

ZnZrYb: 02-22 00:53:41
子树里面的这个点，是连到子树里面，还是连到子树外面

ZnZrYb: 02-22 00:54:22
如果计算 i 的答案，子树 i 里面的点必须只能连接到子树 i 的里面的其他点

鵗曦: 02-22 00:54:34
6

鵗曦: 02-22 00:54:37
这里理解错了

鵗曦: 02-22 00:55:15
那我这样反着做错完了。