2020银川B - The Great Wall dp 1383A - String Transformation 1 并查集

101 阅读 0 评论 67 点赞

我是靠谱客的博主美满树叶，这篇文章主要介绍2020银川B - The Great Wall dp 1383A - String Transformation 1 并查集，现在分享给大家，希望可以做个参考。

2020银川B - The Great Wall dp

没想到n^2竟然没有超时，如果要纠结怎样找最大最小值的话就有点困难了，其实这个题就分成k个组然后每个组选出两个数，这两个数的差值就是这个组的价值，也就是要有一个数乘1，一个数乘-1然后求和，dp[i][j][0]表示前i个数放到了前j个组中，且第j个组没有选出乘1的数也没选出乘-1的数，dp[i][j][1]表示前i个数放到了前j个组中且第j个组选出了乘1的数，dp[i][j][2]表示前i个数放到了前j个组中且前第j个组选出了乘-1的数，dp[i][j][3]表示前i个数放到了前j个组中且第j个组两个数都选出来了；状态转移看了题解之后发现没那么难，但是自己没有想到，，，

2020-2021 ICPC银川站B题 The Great Wall 题解(dp) - TheBestQAQ - 博客园 (cnblogs.com)

复制代码

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define endl 'n'
#define pause system("pause")
using namespace std;
const int N=2e4+5;
const int mod=998244353;
const int inf=1e18;
int n,a[N],f[2][N][4];
signed main()
{
    //ios::sync_with_stdio(0);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++)
    for(int j=0;j<=3;j++)
    {
        if(j==0) f[0][i][0]=f[1][i][0]=0;
        else f[0][i][j]=f[1][i][j]=-inf;
    }
    int t=0;
    for(int i=1;i<=n;i++)
    {
        t^=1;
        for(int j=1;j<=i;j++)
        {
            f[t][j][0]=max({f[t][j][0],f[!t][j-1][3],f[!t][j][0]});
            f[t][j][1]=max({f[!t][j][0]+a[i],f[t][j][0]+a[i],f[!t][j][1]});
            f[t][j][2]=max({f[!t][j][0]-a[i],f[t][j][0]-a[i],f[!t][j][2]});
            f[t][j][3]=max({f[!t][j][1]-a[i],f[!t][j][2]+a[i],f[!t][j][3],f[!t][j-1][3]});
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<f[t][i][3]<<endl;
    }
    pause;
    return 0;
}

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
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define endl 'n'
#define pause system("pause")
using namespace std;
const int N=2e4+5;
const int mod=998244353;
const int inf=1e18;
int n,a[N],f[2][N][4];
signed main()
{
    //ios::sync_with_stdio(0);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++)
    for(int j=0;j<=3;j++)
    {
        if(j==0) f[0][i][0]=f[1][i][0]=0;
        else f[0][i][j]=f[1][i][j]=-inf;
    }
    int t=0;
    for(int i=1;i<=n;i++)
    {
        t^=1;
        for(int j=1;j<=i;j++)
        {
            f[t][j][0]=max({f[t][j][0],f[!t][j-1][3],f[!t][j][0]});
            f[t][j][1]=max({f[!t][j][0]+a[i],f[t][j][0]+a[i],f[!t][j][1]});
            f[t][j][2]=max({f[!t][j][0]-a[i],f[t][j][0]-a[i],f[!t][j][2]});
            f[t][j][3]=max({f[!t][j][1]-a[i],f[!t][j][2]+a[i],f[!t][j][3],f[!t][j-1][3]});
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<f[t][i][3]<<endl;
    }
    pause;
    return 0;
}

1383A - String Transformation 1 并查集

如果s1[i]>s2[i]答案是-1；如果s1[i]!=s2[i]答案加1，然后s1[i]在以后是可以变成s2[i]的，可以理解为连了一条边，慢慢的s1[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
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define endl 'n'
#define pause system("pause")
using namespace std;
const int N=2e5+5;
const int mod=998244353;
const int inf=1e18;
int t,n,s[33];
char s1[N],s2[N];
int findd(int x){return x==s[x]?x:s[x]=findd(s[x]);}
signed main()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        for(int i=1;i<=27;i++) s[i]=i;
        cin>>n;
        cin>>(s1+1)>>(s2+1);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            int u=s1[i]-'a'+1,v=s2[i]-'a'+1;
            if(u>v){ans=-1;break;}
            int x=findd(u),y=findd(v);
            if(x!=y)
            {
                ans++;
                s[x]=y;
            }
        }
        cout<<ans<<endl;
    }
    pause;
    return 0;
}