Znzryb's Blog
0%

Posted on Edited on

AC代码

这题题意很简单，把一段序列分为若干个子序列，要求这些子序列的和≠k，统计这种子序列的分法，mod 998244353

样例的计算过程如下

3 3
1 2 3

问分法种数，即2种

推出思路是这样的，不断枚举末尾

image

O（n^2）优化嘛就是用map维护之前的j
// 我们需要sumA[j]!=sumA[i]-k; 那为何不反过来想，把==的排除掉不就好了吗？

主要思路如上

AC

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=2e5+10,mod=998244353;
ll n,k,A[N],sumA[N],dp[N];      // dp[i]的意思是以i为结尾时，有多少种分法可行
map<ll,ll> occSum;              // occSum[i]  i表示对应sum值，occSum[i]表示该sum值累计方案数  occ即occurred简写
ll currSum;                     // i之前的现在的方案数总和
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i) {
        cin>>A[i];
        sumA[i]=sumA[i-1]+A[i];
    }
    dp[0]=1;
    occSum[0]=1;
    currSum+=dp[0];
    for(int i=1;i<=n;++i) {
        // 我们需要sumA[j]!=sumA[i]-k;那为何不反过来想，把==的排除掉不就好了吗？
         if(occSum.count(sumA[i]-k))
             dp[i]=(dp[i]%mod+currSum%mod-occSum[sumA[i]-k]%mod+mod)%mod;
        else
            dp[i]=currSum%mod;
        occSum[sumA[i]]=(occSum[sumA[i]]%mod+dp[i]%mod+mod)%mod;
        currSum=(currSum%mod+dp[i]%mod+mod)%mod;
        // for(int j=i-1;j>=0;--j) {
        //     if(sumA[i]-sumA[j]!=k)
        //         dp[i]=(dp[i]%mod+dp[j]%mod)%mod;
        // }
    }
    cout<<dp[n]<<endl;
}
// 哈哈，第一次提交忘记mod了   https://atcoder.jp/contests/abc370/submissions/59317169
// AC https://atcoder.jp/contests/abc370/submissions/59320083

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

如果发现WA的比较多，但是又觉得没啥问题，可能是没mod的问题

WA，原因就是C++的%是取余，而题目要求取模，故要在%的时候加一个mod。

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=2e5+10,mod=998244353;
ll n,k,A[N],sumA[N],dp[N];      // dp[i]的意思是以i为结尾时，有多少种分法可行
map<ll,ll> occSum;              // occSum[i]  i表示对应sum值，occSum[i]表示该sum值累计方案数  occ即occurred简写
ll currSum;                     // i之前的现在的方案数总和
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i) {
        cin>>A[i];
        sumA[i]=sumA[i-1]+A[i];
    }
    dp[0]=1;
    occSum[0]=1;
    currSum+=dp[0];
    for(int i=1;i<=n;++i) {
        // 我们需要sumA[j]!=sumA[i]-k;那为何不反过来想，把==的排除掉不就好了吗？
         if(occSum.count(sumA[i]-k))
             dp[i]=(dp[i]+currSum-occSum[sumA[i]-k])%mod;
        else
            dp[i]=currSum%mod;
        occSum[sumA[i]]=(occSum[sumA[i]]+dp[i])%mod;
        currSum=(currSum+dp[i])%mod;
        // for(int j=i-1;j>=0;--j) {
        //     if(sumA[i]-sumA[j]!=k)
        //         dp[i]=(dp[i]%mod+dp[j]%mod)%mod;
        // }
    }
    cout<<dp[n]<<endl;
}
// 哈哈，第一次提交忘记mod了   https://atcoder.jp/contests/abc370/submissions/59317169

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

Posted on Edited on

AC代码

AC

相比于上一次WA，修改了这些（这没啥好多说的，idx2为-会导致一系列问题）

1
2
if(idx2<0)
       idx2=0;

以及加了一个n+1（原来是n）（一般情况下不会被击穿因为如果超了我会减掉，但正巧空的默认值是0，即
xp[idx2].first）为0，正好我的判断条件是xp[idx2].first!=r，碰巧hack数据r也为0，就被击穿了，idx2没减，让我的程序WA了。

1
2
3
for(int i=1;i<=n+1;i++) {
        sumVil[i]=sumVil[i-1]+xp[i].second;
}

AC代码

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
55
56
#include <iostream>
#include <algorithm>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=2e5+10,MAXP=1e11+10;
pair<ll,ll> xp[N];
ll n,m,sumVil[N];
void debug() {
    for(int i=1;i<=n;i++) {
        cout<<sumVil[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<xp[i].first<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<xp[i].second<<" ";
    }
    cout<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>xp[i].first;
    }
    for(int i=1;i<=n;i++) {
        cin>>xp[i].second;
    }
    sort(&xp[1],&xp[n+1]);
    for(int i=1;i<=n+1;i++) {
        sumVil[i]=sumVil[i-1]+xp[i].second;
    }
    cin>>m;
    for(int _=1;_<=m;_++) {
        ll l,r;
        cin>>l>>r;
        ll idx1=lower_bound(&xp[0],&xp[n+1],make_pair(l,-MAXP))-&xp[0]-1;
        ll idx2=upper_bound(&xp[0],&xp[n+1],make_pair(r, MAXP))-&xp[0];
        if(idx1<0)
            idx1=0;
        if(xp[idx2].first!=r)
            idx2--;
        if(idx2<0)
            idx2=0;
        // cout<<idx1<<" "<<idx2<<": ";
        cout<<sumVil[idx2]-sumVil[idx1]<<endl;
    }
    // debug();
    return 0;
}
// 就WA了一个 https://atcoder.jp/contests/abc371/submissions/59255550

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

挺神奇的，就WA了一个点

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
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <algorithm>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=2e5+10,MAXP=1e11+10;
pair<ll,ll> xp[N];
ll n,m,sumVil[N];
// bool comp(pair<ll,ll> a, pair<ll,ll> b) {
//     if(a.first!=b.first)
//         return a.first<b.first;
//     return false;
// }
// struct cmp {
//     bool operator()(const pair<ll,ll> &a ,const pair<ll,ll> &b) const{
//         return a.first<b.first;
//     }
// };
void debug() {
    for(int i=1;i<=n;i++) {
        cout<<sumVil[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<xp[i].first<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<xp[i].second<<" ";
    }
    cout<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>xp[i].first;
    }
    for(int i=1;i<=n;i++) {
        cin>>xp[i].second;
    }
    sort(&xp[1],&xp[n+1]);
    for(int i=1;i<=n;i++) {
        sumVil[i]=sumVil[i-1]+xp[i].second;
    }
    cin>>m;
    for(int _=1;_<=m;_++) {
        ll l,r;
        cin>>l>>r;
        ll idx1=lower_bound(&xp[0],&xp[n+1],make_pair(l,-MAXP))-&xp[0]-1;
        ll idx2=upper_bound(&xp[0],&xp[n+1],make_pair(r, MAXP))-&xp[0];
        if(idx1<0)
            idx1=0;
        if(xp[idx2].first!=r)
            idx2--;
        //cout<<idx1<<" "<<idx2<<": ";
        cout<<sumVil[idx2]-sumVil[idx1]<<endl;
    }
    //debug();
    return 0;
}
// 就WA了一个 https://atcoder.jp/contests/abc371/submissions/59255550

Posted on Edited on

AC代码

这题面说起来也简单，就是P1=5 那我就用P5代替你———同理 所有的Pi都要进行这个操作

题意很简单，就是操作数很大，不可能模拟。

那我们的问题就变成了这个变化有什么规律吗？

image

一个非常详细的题解

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#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,p[N],k,ans[N],cnt,ring[N],d[N];
bool vis[N];
vector<ll> g[N];
void dfs(ll i,ll dis) {
    if(vis[i]) {
        return;
    }
    vis[i]=true;
    g[cnt].push_back(i);
    ring[i]=cnt,d[i]=dis;
    dfs(p[i],dis+1);
}
ll binpow(ll a,ll b,ll p) {
    if(b==0) return 1;
    ll res=binpow(a,b/2,p)%p;
    if(b%2)  // b%2!=0
        return res%p*res%p*a%p; // 毕竟res是
    else
        return res%p*res%p;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        cin>>p[i];
        if(p[i]==i)
            ans[i]=i;
    }
    for(int i=1;i<=n;i++) {
        if(ans[i]!=0)   // 这相当于一个自环，倒也不用走
            continue;
        if(vis[i])      // 走过了，不用处理
            continue;
        cnt++;
        dfs(i,0);
    }
    // 答案解决阶段
    for(int i=1;i<=n;i++) {
        if(ans[i]!=0)   // 答案都确定了也就无所谓了
            continue;
        ll ringSize=g[ring[i]].size();
        ll advStep=binpow(2,k,ringSize);
        ans[i]=g[ring[i]][(d[i]+advStep)%ringSize];
    }
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}
// AC https://atcoder.jp/contests/abc377/submissions/59254380

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

挺难想的，实现起来其实也比较难，还需要快速幂，但确实是一次提交AC，只能说我的图论代码实现水平还是比较高的

Posted on Edited on

题目大意

给定 nn 条线段 [Li,Ri][L_i, R_i]，线段端点都在 1∼m1\sim m 的范围内。需要统计满足题意的区间数量（等价于对每个左端点 ll，能延伸到的最大右端点受右侧最小的 RR 约束），并输出总数。

AC代码

主要思路是一个点所能到达的最大边界取决于它的minR，也即在它右边的最小右边界

可以看到minR的统计过程是这样的

1
2
3
4
5
6
7
8
9
10
11
for(int _=1;_<=n;_++) {
        ll l,r;
        cin>>l>>r;
        minR[l]=min(minR[l],r);     // 其实包括l之前所有的点，minR的值应该设为r（min（ r ，现有值））
                                        // 但如果直接这样设，时间复杂度会来到O（n^2）级别，显然无法通过全部数据
    }                                   // 那我们为什么不先设一个l，在最后来一个汇总，反正也不要求强制在线。
    ll currMin=m+1;
    for(int i=m;i>=1;--i) {             // 汇总
        currMin=min(currMin,minR[i]);
        minR[i]=currMin;
    }

可以证明在 【Li,Ri】，比Li还小的地方 l（包含Li）的【l，r】区间包含Ri，必然导致【l，r】包含【Li，Ri】

所以比Li更小的地方应该将Ri考虑在minR的取值中

比如说minR[1]==4 他的答案怎么统计那？

1
2
3
4
5
1 2 3

1 2

1

可以看到一共有三种区间（[1,3],[1,2],[1,1]）即区间长度之和即为答案（[1,4]）

然后还有一些离线化的优化方法，注释里写的很清楚

AC 

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,m,cnt,minR[N],ans;    // minR代表该点l对应的最小R

void debug() {
    for(int i=1;i<=m;++i) {
        cout<<minR[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {             // 初始化minR
        minR[i]=m+1;
    }
    for(int _=1;_<=n;_++) {
        ll l,r;
        cin>>l>>r;
        minR[l]=min(minR[l],r);     // 其实包括l之前所有的点，minR的值应该设为r（min（ r ，现有值））
                                        // 但如果直接这样设，时间复杂度会来到O（n^2）级别，显然无法通过全部数据
    }                                   // 那我们为什么不先设一个l，在最后来一个汇总，反正也不要求强制在线。
    ll currMin=m+1;
    for(int i=m;i>=1;--i) {             // 汇总
        currMin=min(currMin,minR[i]);
        minR[i]=currMin;
    }
    ans=0;
    for(int i=1;i<=m;++i) {
        ans+=minR[i]-i;           // 答案统计
    }
    cout<<ans<<endl;
    // debug();
}
// AC https://atcoder.jp/contests/abc377/submissions/59206219

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

一次提交过的，之前的代码样例都过不了就不放在这里了