Znzryb's Blog
0%

Codeforces Round 1082 (Div. 2)-CF-1082 赛后总结（这个D呀，是真简单啊，后悔没看啊，在C2上花太多时间）

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;
    }
}

心得感悟