Znzryb's Blog
0%

ABC- 371 - E- I Hate Sigma Problems

Posted on Edited on

AC代码

1
2
3
1 2 2

看我手算样例

image

主要思路写在注释当中，具体来说就是算贡献度

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
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,A[N],vis[N],dp[N],ans,fsum,give[N]; // give[i] 表示i位置对个数的贡献到几位置为止
ll valP[N];         // 值对应位置，比如说5这个值上次在4位置出现过，那么就   valP[5]=4，没出现过自然是0；
bool vis2[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>A[i];
    }
    for(int i=1;i<=n;i++)   // give 初始化
        give[i]=n+1;        // give[i] 表示i位置对个数的贡献到几位置为止
    for(int i=1;i<=n;i++) {
        ll ai=A[i];
        give[valP[ai]]=i;
        valP[ai]=i;
        if(vis[A[i]]==0)
            dp[i]=dp[i-1]+1,fsum+=dp[i],vis[A[i]]+=1;
        else
            dp[i]=dp[i-1],fsum+=dp[i],vis[A[i]]+=1;
    }
    ans+=fsum;
    // cout<<ans<<endl;
    for(int i=2;i<=n;i++) {
        fsum=fsum-(1+give[i-1]-i);      // 第一个1代表少了一个长度，自然要少一个（那一个即【i-1，i-1】）
                                        // 然后我们关注的是失去的i-1的贡献域
        ans+=fsum;
        // cout<<i<<":"<<fsum<<endl;
    }
    cout<<ans<<endl;
    // debug();
}
// AC https://atcoder.jp/contests/abc371/submissions/59306953

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

对拍暴力程序（不用多说，肯定超时）

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
38
39
40
41
42
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,A[N],dp[N],ans,fsum,diff[N],cnt=0;
bitset<N> vis;

void debug() {
    for(int i=1;i<=n;i++) {
        cout<<dp[i]<<" ";
    }
    cout<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>A[i];
    }
    for(int i=1;i<=n;i++) {
        cnt=0;vis.reset();
        for(int j=i;j<=n;j++) {
            if(!vis[A[j]])
                cnt++,ans+=cnt,vis[A[j]]=true;
            else
                ans+=cnt;
        }
    }
    cout<<ans<<endl;
}

贪心有偏差做法，偏差在这个部分

其实复杂的样例都通不过

1
2
3
4
5
}else {
            fsum-=1;
            ans+=fsum;
            cout<<i<<":"<<fsum<<endl;
        }

虽然从最后一位看上去 i 位置是没有贡献的（在个数上），但前面的某些位其实是有在个数上的贡献的

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,A[N],vis[N],dp[N],ans,fsum,diff[N];
bool vis2[N];

void debug() {
    for(int i=1;i<=n;i++) {
        cout<<dp[i]<<" ";
    }
    cout<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>A[i];
    }
    for(int i=1;i<=n;i++) {
        if(vis[A[i]]==0)
            dp[i]=dp[i-1]+1,fsum+=dp[i],vis[A[i]]+=1;
        else
            dp[i]=dp[i-1],fsum+=dp[i],vis[A[i]]+=1;
    }
    ans+=fsum;
    cout<<ans<<endl;
    for(int i=2;i<=n;i++) {
        vis[A[i-1]]-=1;
        if(vis[A[i-1]]<=0) {
            fsum=fsum-1-(n-i+1);
            cout<<i<<":"<<fsum<<endl;
            ans+=fsum;
        }else {
            fsum-=1;
            ans+=fsum;
            cout<<i<<":"<<fsum<<endl;
        }
    }
    cout<<ans<<endl;
    debug();
}