【组合计数】CF1151E

迈不过友情╰ 2024-03-22 23:59 72阅读 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 条评论，72人围观）

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

相关阅读

相关【贪心+组合数学】CF697div3 E

[Problem - E - Codeforces][] 这道题一开始想的方向是对的，就是组合数学，但是感觉想不清楚，第一眼想的是把所有数从大到小排好序之后贪心地选，然后想用

痛定思痛。/ 2024年03月27日 14:46/ 0 赞/ 90 阅读

相关【贪心】CF1822 E

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

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

相关【枚举边+MST+组合计数】CF1857G

[Problem - 1857G - Codeforces][] 题意： ![4a0694b3491d4b64a4432fb12c43d801.png][] ![fbe

痛定思痛。/ 2024年03月23日 23:18/ 0 赞/ 85 阅读

相关【组合计数】CF1151E

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

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

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

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

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

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

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

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

相关【组合计数】CF1866 H

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

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

相关 CF1151B Dima and a Bad XOR

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

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

相关 CF 166E Tetrahedron

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

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

相关 cf 1009E

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

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