8/2 训练日志(dp+思维+字典树)

​

活动地址：CSDN21天学习挑战赛

E. Pashmak and Graph

题意：给定一张带权值的有向图，n个顶点m条边，找出一条长度最大权值递增的路径，输出长度。
思路：
1.若是以每个点都进行一次遍历，必定会超时；g[i]表示在到达i点时满足题意得长度最大是多少
2.还需将权值进行升序排列，前面权值小的肯定先经过
3.再开一数组，dp[i]表示第i条边结尾的最大长度
4.状态转移方程：dp[i]=g[e[i].u]+1

#include<bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
int n,m,g[N],dp[N];
struct node
{
    
    int u,v,w;
    bool operator <(const node & e)const
    {
    
        return w<e.w;
    }
}e[N];

int main()
{
    
    IOS;
    //g[i]表示在到达i点时满足题意得长度最大是多少
    //dp[i]表示第i条边结尾的最大长度
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    
        int u,v,w;cin>>u>>v>>w;
        e[i]=(node){
    u,v,w};
    }
    sort(e+1,e+m+1);
    int ans=0,k=1;
    e[m+1].w=-1;
    for(int i=1;i<=m;i++)
    {
    
        dp[i]=g[e[i].u]+1;
        if(e[i].w!=e[i+1].w)     //权值相等的连续段
        {
    
            for(int j=k;j<=i;j++)
                g[e[j].v]=max(dp[j],g[e[j].v]);
            k=i+1;
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}

C. awoo’s Favorite Problem

题意：将一个串通过两个变换规则变成连一个串
思路：
1.将b全部删除，看看字符串s和t是否相等
2.比较s中a和c的下标是否分别大于、小于t中a和c下标

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
int n;
vector<int>v1,v2;
string s,tt;
int main()
{
    
    int t;scanf("%d",&t);
    while(t--)
    {
    
        v1.clear();
        v2.clear();
        scanf("%d",&n);
        cin>>s>>tt;
        s=" "+s;
        tt=" "+tt;
        string s1,s2;
        for(int i=1;i<=n;i++)
        {
    
            if(s[i]!='b')  s1+=s[i],v1.push_back(i);
            if(tt[i]!='b') s2+=tt[i],v2.push_back(i);
        }
        int flag=1;
        if(s1!=s2)
        {
    
            cout<<"NO"<<endl;
            continue;
        }
        for(int i=0;i<v1.size();i++)
        {
    
            //cout<<v1[i]<<" "<<v2[i]<<endl;
            if(s1[i]=='a'&&v1[i]>v2[i])
            {
    
                flag=0;break;
            }
            if(s1[i]=='c'&&v1[i]<v2[i])
            {
    
                flag=0;break;
            }
        }
        if(flag)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

E. Add Modulo 10

刚开始看了tag里面有暴力，写了一个纯纯暴力的做法，真的脑淤血了。

int main()
{
    
    //IOS;
    int t;cin>>t;
    while(t--)
    {
    
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+n+1);
        while(a[n]%2)
        {
    
            a[n]+=a[n]%10;
        }
        int flag=1;
        for(int i=n-1;i>=1;i--)
        {
    
            int tmp=a[i];
            while(a[i]<a[n])
            {
    
                a[i]+=a[i]%10;
                if(a[i]==tmp)
                    break;
            }
            if(a[i]!=a[n])
            {
    
                flag=0;break;
            }
        }
        if(flag)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

找规律发现：除了0和5结尾的数，其他数都会陷入2，4，8，6这样的怪圈。每个周期都会增加20。
列出公式：A[i] + k1 * 20 == A[j] + k2 * 20
化简得到：(A[i] - A[j]) % 20 == 0
将0和5结尾的数字，看能否统一为同一个数字。

#include<bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
int n,a[N];

int main()
{
    
    //IOS;
    int t;cin>>t;
    while(t--)
    {
    
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int cnt=0,mx=-1;
        for(int i=1;i<=n;i++)
        {
    
            if(a[i]%10==5)  a[i]+=5,cnt++;
            else if(a[i]%10==0)  cnt++;
            else
            {
    
                while(a[i]%10!=2)
                    a[i]+=a[i]%10;
                mx=max(mx,a[i]);
            }
        }
        int flag=1;
        if(n==cnt)
        {
    
            for(int i=2;i<=n;i++)
                if(a[i]!=a[i-1])
            {
    
                flag=0;break;
            }
        }
        else if(cnt>0) flag=0;
        else
        {
    
            for(int i=1;i<=n;i++)
            {
    
                if((mx-a[i])%20!=0)
                {
    
                    flag=0;break;
                }
            }
        }
        if(flag)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

字典树

https://www.bilibili.com/video/BV1yA4y1Z74t?spm_id_from=333.337.search-card.all.click&vd_source=91973ada1213cf6ba2cbb43a2bebd2e8
模板：

char s[N];      
int ch[N][26];  //存储从结点p沿着j这条边走到的子节点
int cnt[N];     //存储一节点p结尾的单词插入次数
int idx;        //给结点编号
void ins(char *s)
{
    
    int p=0;
    for(int i=0;s[i];i++)
    {
    
        int j=s[i]-'a';
        if(!ch[i][j])   ch[i][j]=++idx;
        p=ch[p][j];
    }
    cnt[p]++;
}
int query(char *s)
{
    
    int p=0;
    for(int i=0;s[i];i++)
    {
    
        int j=s[i]-'a';
        if(!ch[i][j])   return 0;
        p=ch[i][j];
    }
    return cnt[p];
}

P2922 [USACO08DEC]Secret Message G

类型：属于01的字典树
思路：
1.数组cnt[i]表示以i结尾的字符串个数
2.数组sum[i]表示经过结点i的字符串个数
3.统计不同长度的前缀为res+sum[p]-cnt[p];
代码：

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
char s[N];
int ch[N][26];  //存储从结点p沿着j这条边走到的子节点
int cnt[N];     //存储一节点p结尾的单词插入次数
int idx;        //给结点编号
int n,m,k,sum[N];
int ss[N];
void ins(int s[])
{
    
    int p=0;
    for(int i=0;i<k;i++)
    {
    
        int j=s[i];
        if(ch[p][j]==-1)   ch[p][j]=++idx;
        p=ch[p][j];
        sum[p]++;
    }
    cnt[p]++;
}
int query(int s[])
{
    
    int p=0,res=0;
    for(int i=0;i<k;i++)
    {
    
        int j=s[i];
        if(ch[p][j]==-1)   return res;
        p=ch[p][j];
        res+=cnt[p];
    }
    return res+sum[p]-cnt[p];
}
int main()
{
    
    cin>>m>>n;
    memset(ch,-1,sizeof ch);
    for(int i=1;i<=m;i++)
    {
    
        cin>>k;
        for(int j=0;j<k;j++)
            cin>>ss[j];
        ins(ss);
    }
    for(int i=1;i<=n;i++)
    {
    
        cin>>k;
        for(int j=0;j<k;j++)
            cin>>ss[j];
        cout<<query(ss)<<endl;
    }
    return 0;
}

P2580 于是他错误的点名开始了

思路：本来想联系一下字典树得模板题，但这个题目只需要一个map容器就解决了。
若不存在改键，则map容器中Int类型得默认值为0

#include<bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
int n,m;
map<string,int>mp;

int main()
{
    
    //IOS;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    
        string s;cin>>s;
        mp[s]=1;
    }
    cin>>m;
    while(m--)
    {
    
        string s;cin>>s;
        if(mp[s]==1)
            cout<<"OK"<<endl,mp[s]+=1;
        else if(mp[s]>1)
            cout<<"REPEAT"<<endl;
        else
            cout<<"WRONG"<<endl;
    }
    return 0;
}