8/13 最短路+DP+倍增lca+基础思维

Word 小白月赛D

题意：将一个单词s转化为单词t，每次只改变一个单词，且变化的单词必须在给定单词表内
思路：
1.单词s看作是起点，单词t看作是终点。
2.每次变化一个单词，说明两个字符串若只有一个单词差异则可以变化，需要连线。
2.此时便看出是最短路，但是由于n属于1~2000，我不死心的试了以下floyed算法，可惜超时了。。。
floyed的O(n^3)做法+打印路径：

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N=2e3+10;
const int inf=0x3f3f3f3f;
const int mod=1e7+7;
int n,m,f[2005][2005],p[2005][2005];
string str[N];
bool check(int i,int j)
{
    int res=0;
    string s1=str[i],s2=str[j];
    for(int g=0;g<m;g++)
        if(s1[g]!=s2[g])
            res++;
    return res==1;
}
void path(int i,int j)
{
    if(p[i][j]==0) return;
    int k=p[i][j];
    path(i,k);
    cout<<str[k]<<endl;
    path(k,j);
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>str[i];
    string s,t;cin>>s>>t;
    if(s==t)
    {
        cout<<0<<endl<<s<<endl<<t<<endl;
        return;
    }
    int d1=0,d2=0;
    for(int i=1;i<=n;i++)
    {
        if(str[i]==s) d1=i;
        if(str[i]==t) d2=i;
    }
    if(!d1) str[++n]=s,d1=n;
    if(!d2) str[++n]=t,d2=n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=inf;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        if(check(i,j))
            f[i][j]=f[j][i]=1;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
    {
        if(f[i][j]>f[i][k]+f[k][j])
        {
            f[i][j]=f[i][k]+f[k][j];
            p[i][j]=k;
        }
    }
    if(f[d1][d2]==inf)
    {
        cout<<-1<<endl;return;
    }
    cout<<f[d1][d2]-1<<endl;
    cout<<s<<endl;
    path(d1,d2);
    cout<<t<<endl;
}
signed main()
{
    solve();
    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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

Dijkstra的堆优化：

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=1e7+7;
int n,m,d1,d2,dis[2005],pre[2005],vis[2005];
string str[2005];
vector<int>e[N];
priority_queue<pair<int,int>>q;
bool check(int i,int j)
{
    int res=0;
    string s1=str[i],s2=str[j];
    for(int g=0;g<m;g++)
        if(s1[g]!=s2[g])
            res++;
    return res==1;
}
void path(int u)
{
    if(u==d1)
    {
        cout<<str[u]<<endl;return;
    }
    path(pre[u]);
    cout<<str[u]<<endl;
}
void dijkstra(int s)
{
    for(int i=0;i<=n;i++)
        dis[i]=inf;
    dis[s]=0;
    q.push({0,s});
    while(q.size())
    {
        auto t=q.top();q.pop();
        int u=t.second;
        if(vis[u])
            continue;
        vis[u]=1;
        for(int ed:e[u])
        {
            int v=ed;
            if(dis[v]>dis[u]+1)
            {
                dis[v]=dis[u]+1;
                pre[v]=u;
                q.push({-dis[v],v});
            }
        }
    }
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>str[i];
    string s,t;cin>>s>>t;
    if(s==t)
    {
        cout<<0<<endl<<s<<endl<<t<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(str[i]==s) d1=i;
        if(str[i]==t) d2=i;
    }
    if(!d1) str[++n]=s,d1=n;
    if(!d2) str[++n]=t,d2=n;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        if(check(i,j))
    {
        e[i].push_back(j);
        e[j].push_back(i);
    }
    dijkstra(d1);
    if(dis[d2]==inf)
    {
        cout<<-1<<endl;return;
    }
    cout<<dis[d2]-1<<endl;
    path(d2);
}
signed main()
{
    solve();
    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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

Slash 小白月赛E

看完讲解视频，才稍微有点懂了。
很多是无效状态，即使有数字表示，也无任何意义，关注点应放在有意义的状态是否能正确转移。
思路：
1.dp[i][j][k]表示以i行j列结尾的字符串表示s的前k位中，包含了多少字符串s的个数。
2.规定匹配字符串s时第0个字符为记录更新后长度
3.对于没有匹配成功的状态转移：f[i][j][0]=max({f[i][j][0],f[i-1][j][k],f[i][j-1][k]})

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=7e6+7;
int n,m,f[105][105][105];
char s[105],c[105][105];

void solve()
{
    cin>>n>>m;
    scanf("%s",s+1);
    int len=strlen(s+1);
    for(int i=1;i<=n;i++)
        scanf("%s",&c[i][1]);
    for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)for(int k=0;k<=n;k++)
        f[i][j][k]=-inf;
    //预处理
    f[0][1][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
    {
        for(int k=1;k<=len;k++)
        {
            //匹配
            if(c[i][j]==s[k])
                f[i][j][k]=max(f[i-1][j][k-1],f[i][j-1][k-1]);
        }
        //规定第0个字符为更新后长度
        f[i][j][0]=f[i][j][len]+1;
        //匹配未成功
        for(int k=0;k<=n;k++)
            f[i][j][0]=max({f[i][j][0],f[i-1][j][k],f[i][j-1][k]});
    }
    int ans=0;
    for(int i=0;i<=len;i++)
        ans=max(ans,f[n][m][i]);
    cout<<ans<<endl;
}
signed main()
{
    solve();

    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
42
43
44
45
46
47
48
49
50
51

G. Path Prefixes

思路：
1.倍增lca，这里不需要差分，直接记录自根节点开始到相应节点的总和sum
2.计算差值，开一个数组g[u][j]表示u点向上跳2^j到响应祖先，所需要减去的w2的和

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=7e6+7;
int n,w1[N],w2[N],sum1[N],sum2[N];
int dep[N];     //存u点的深度
int fa[N][20];  //存从u点向上跳2^i层的祖先节点
int g[N][20];
vector<int>e[N];
void dfs(int u,int pare)
{
    dep[u]=dep[pare]+1;
    sum1[u]=sum1[pare]+w1[u];
    sum2[u]=sum2[pare]+w2[u];
    fa[u][0]=pare;
    g[u][0]=w2[u];
    for(int i=1;i<=19;i++)
    {
        fa[u][i]=fa[fa[u][i-1]][i-1];
        g[u][i]=g[fa[u][i-1]][i-1]+g[u][i-1];
    }
    for(int v:e[u])
        if(v!=pare) dfs(v,u);
}

void solve()
{
   cin>>n;
   for(int i=0;i<=n;i++)
       sum1[i]=sum2[i]=w1[i]=w2[i]=dep[i]=0,e[i].clear();

   for(int i=2,p;i<=n;i++)
   {
       cin>>p>>w1[i]>>w2[i];
       e[i].push_back(p),
       e[p].push_back(i);
   }
   dfs(1,0);
   for(int i=2;i<=n;i++)
   {
       int ans=dep[i];
       int u=i;
       if(sum1[u]<sum2[u])
       {
           int t=sum2[u]-sum1[u];
           for(int j=19;j>=0;j--)
           {
               if(g[u][j]<=t)
               {
                   t-=g[u][j];
                   u=fa[u][j];
                   ans-=(1<<j);
               }
           }
           if(t>0) ans--;
       }
       cout<<ans-1<<" ";
   }
   cout<<endl;
}
signed main()
{
    int t;cin>>t;
    while(t--)
    {
        solve();
    }
    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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

A. Everyone Loves to Sleep

一个小小的坑点：当睡觉时间大于最晚的闹钟时，需要特判

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=7e6+7;
int n,H,M,a[N];

void solve()
{
    cin>>n>>H>>M;
    int k=H*60+M;
    for(int i=1;i<=n;i++)
    {
        int x,y;cin>>x>>y;
        a[i]=x*60+y;
    }
    sort(a+1,a+n+1);
    int g=lower_bound(a+1,a+n+1,k)-a;
    int ans=a[g]-k;
    if(g>n)
    {
        ans=a[1]+24*60-k;
    }
    cout<<ans/60<<" "<<ans%60<<endl;
}
signed main()
{
    int t;cin>>t;
    while(t--)
    {
        solve();
    }
    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

B. Remove Prefix

思路：删除前缀数字，可想到从后向前遍历，若一个数字出现了两次，则前面数字都该删除。

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=7e6+7;
int n,a[N];
map<int,int>mp;
void solve()
{
    mp.clear();
   cin>>n;
   for(int i=1;i<=n;i++)
        cin>>a[i];
   int i;
   for(i=n;i>=1;i--)
   {
       mp[a[i]]++;
        if(mp[a[i]]>1)
            break;
   }
   cout<<i<<endl;
}
signed main()
{
    int t;cin>>t;
    while(t--)
    {
        solve();
    }
    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

C. Minimum Varied Number

思路：数组记录，会使用reverse函数，无了。

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=7e6+7;
int n,a[N],g;
map<int,int>mp;
void solve()
{

    g=0;
    int s;cin>>s;
    int tmp=9;
    while(1)
    {
        if(s>tmp)
        {
            a[++g]=tmp;s-=tmp;tmp--;
        }
        else
        {
            a[++g]=s;break;
        }
    }
    reverse(a+1,a+g+1);
    for(int i=1;i<=g;i++)
        cout<<a[i];
    cout<<endl;
}
signed main()
{
    int t;cin>>t;
    while(t--)
    {
        solve();
    }
    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
42
43
44

A. Mark the Photographer

简单的贪心，按升序排号，比较i和n+i

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=7e6+7;
int n,x,a[N];

void solve()
{
    cin>>n>>x;
    for(int i=1;i<=n*2;i++)
        cin>>a[i];
    sort(a+1,a+2*n+1);
    for(int i=1;i<=n;i++)
        if(a[n+i]-a[i]<x)
    {
        cout<<"NO"<<endl;return;
    }
    cout<<"YES"<<endl;
}
signed main()
{
    int t;cin>>t;
    while(t--)
    {
        solve();
    }
    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