【组合计数】CF1151E

迈不过友情╰ 2024-03-22 23:59 58阅读 0赞

[Problem - 1151E - Codeforces][]

题意：

![9af8880daced4f3d9b418de0063025f6.png][]

![bb2fce709fb04f418882d44f60e62d55.png][]

思路：

我们要统计区间数量，有两个思考方向

一个是枚举右端点r，然后计算左端点l的贡献

还有一个就是，更换枚举对象

这道题是后者

因为答案是连通块数量

连通块数量=点数-边数

对于点和边我们去单独计算贡献

对于每个点，它包含在区间的条件是ai在\[l,r\]范围内，因此贡献为ai\*(N-ai+1)

对于每条边，它包含在区间的条件是ai和ai-1都在\[l,r\]范围内，贡献为min(a\[i\],a\[i-1\])\*(N-max(a\[i\],a\[i-1\])+1)

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mxv=1e5+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    int N;
    int a[mxn];
    
    void solve(){
        cin>>N;
        int ans1=0,ans2=0;
        for(int i=1;i<=N;i++){
            cin>>a[i];
            ans1+=a[i]*(N-a[i]+1);
        }
        for(int i=2;i<=N;i++){
            ans2+=min(a[i],a[i-1])*(N-max(a[i],a[i-1])+1);
        }
        cout<<ans1-ans2<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - 1151E - Codeforces]: https://codeforces.com/problemset/problem/1151/E
[9af8880daced4f3d9b418de0063025f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/cdfe1f2359a74f1f8de5cebef15f21d2.png
[bb2fce709fb04f418882d44f60e62d55.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/aa719fc1358c4b22a0b64a3fd65ffd45.png

发表评论取消回复

表情：

评论列表（有 0 条评论，58人围观）

还没有评论，来说两句吧...

相关阅读

相关【贪心】CF1822 E

[Problem - 1822E - Codeforces][] 题意： ![2e9c008736434bd3aade35f13ba3671b.png][] ![e793

女爷i/ 2024年03月23日 23:48/ 0 赞/ 72 阅读

相关【组合计数】CF1151E

[Problem - 1151E - Codeforces][] 题意： ![9af8880daced4f3d9b418de0063025f6.png][] ![bb2f

迈不过友情╰/ 2024年03月22日 23:59/ 0 赞/ 59 阅读

相关【并查集+组合计数】ABC226 E

[E - Just one (atcoder.jp)][E - Just one _atcoder.jp] 题意： ![06f50f3c719f4819a171a6d800

￡神魔★判官ぃ/ 2024年03月17日 19:11/ 0 赞/ 47 阅读

相关【组合数学+插板法】CF893E

[Problem - 893E - Codeforces][] 题意： ![9b8b18625f244323a91936f7d4464fcc.png][] 思路： ![

清疚/ 2024年03月16日 11:07/ 0 赞/ 47 阅读

相关【组合计数】CF1866 H

[Problem - H - Codeforces][] 题意 ![ae0ad641c2c842abbdd97f19e7c95ea2.png][] 思路不知道这种tr

末蓝、/ 2024年02月20日 09:05/ 0 赞/ 36 阅读

相关 CF891E Lust

CF891E Lust -------------------- 鸽子更博了 Orz Itst 神仙结论：最后的答案是一开始的\\(\\prod a\_i\\)减去

迈不过友情╰/ 2023年08月17日 17:29/ 0 赞/ 118 阅读

相关 CF1151B Dima and a Bad XOR

题目乍一看很难做啊！你怎么找出一个xor和大于0的来啊？好像没有固定算法啊！ -------------------- 那就不要用固定算法，用随机算法啊！（欺负那些脑子

素颜马尾好姑娘i/ 2021年12月22日 15:55/ 0 赞/ 216 阅读

相关 [CF1111E]Tree

题目大意：给一棵$n(n\\leqslant10^5)$个点的树，有$q(q\\leqslant10^5)$次询问，每次询问给出$k,m,r$表示把以下$k$个点分成不超过$m

素颜马尾好姑娘i/ 2021年12月22日 04:15/ 0 赞/ 211 阅读

相关 CF 166E Tetrahedron

E. Tetrahedron time limit per test 2 seconds memory limit per test 256 megabytes in

蔚落/ 2021年12月19日 14:35/ 0 赞/ 209 阅读

相关 cf 1009E

如何看待某cf2000分选手不会一道tag1900的题？难。考虑每段距离的贡献， a\[i\]出现在位置j上，当且仅当j-i休息，并且中间的都不是休息的。

曾经终败给现在/ 2021年10月25日 12:56/ 0 赞/ 265 阅读