day18

今天的题好难啊！！！！80/300；

T1第一眼像个树形DP，推了大约30min无果，改写暴力还写挂了！！！！0/100

正解：贪心，每次选最小的花费，向上更新看是否合法；

#include<iostream>
#include<cstdio>
#include<vector>
#include<cctype>
#include<algorithm>
using namespace std;
struct node{
    int e,fa;
}a[1010];
int fa[1010],w[1010];
int n,ans,total;
bool v;
inline int cmp(node x,node y){return x.e<y.e;}
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
inline void check(int x,int i)
{
    if(i==0)return;
    if(w[i]>=x)
    {
        check(x,fa[i]);
    }
    else
    {
        v=0;
        return;
    }
}
inline void updata(int x,int i)
{
    if(i==0)return;
    w[i]-=x;
    updata(x,fa[i]);
}
int main()
{
    n=read(); 
    for(int i=1;i<=n;i++)
    {
        fa[i]=read();a[i].e=read();w[i]=read();
        a[i].fa=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        v=1;
        check(a[i].e,a[i].fa);
        if(v){total++;updata(a[i].e,a[i].fa);}
    }
    cout<<total<<endl;
    return 0;
}

View Code

T2发现答案只在右端点，写了一个O（n/2+n²/2）的算法，拿了60分（吸一口氧可拿80）60/100

 正解，把 l 和 r 丢到一个数组中排序，处理一个 sa 记录全部 l 的和，sp 记录现在在几个区间中，

遇到一个 l 端点 sa--,sp++;遇到一个 r 端点 先判断是否要更新答案，然后 sp--;复杂度极低；

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
    long long l,r;
}c[210000];
int n,l[110000],r[110000];
inline long long maxx(long long x,long long y){return x>y?x:y;}
inline int cmp(node x,node y)
{
    return x.l<y.l;
}
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
int main()
{
    n=read();long long sa=0,sp=0,ans1,ans=-1;
    for(int i=1;i<=n;i++)
    {
        l[i]=read();r[i]=read();
        sa+=l[i];
        c[i].l=l[i];c[i+n].r=1;
        c[i+n].l=r[i];
    }
    sort(c+1,c+1+2*n,cmp);
    for(int i=1;i<=2*n;i++)
    {
        if(c[i].r)
        {
            if(ans<sa+sp*c[i].l){
                ans1=c[i].l;ans=sa+sp*c[i].l;
            }
            sp--;
        }
        if(!c[i].r)
        {
            sa-=c[i].l;sp++;
        }
    }
    cout<<ans1<<" "<<ans<<endl;
    return 0;
}

View Code

T3写了一个暴力匹配结果炸了？？？20/100

把A串以*分割成几个子串，B串*2处理循环，在kmp搞一下，记录以某个字符为起点能匹配完A的某个子串的最近位置。

然后再扫一遍就行了。

#include<bits/stdc++.h>
using namespace std;
char a[200],b[210000],c[110][110];
int n,m,ans,next[101][101],first[51][200001],last[200001],v,gs[101];
int main()
{
    scanf("%s%s",a+1,b+1);
    n=strlen(a+1);m=strlen(b+1);
    for(int i=1;i<=n;i++)
    {
        while(a[i]=='*')
        i++;
        gs[0]++;
        while(a[i]!='*'&&i<=n)
        {
            c[gs[0]][++gs[gs[0]]]=a[i];
            i++;
        }
    }
    if(gs[0]==1&&n!=m)
    {
        cout<<'0'<<endl;
        return 0;
    }
    for(int i=1;i<m;i++)
        b[i+m]=b[i];
    for(int i=1;i<=gs[0];i++)
    {
        int k=0;
        for(int j=2;j<=gs[i];j++)
        {
            while(c[i][j]!=c[i][k+1]&&k)k=next[i][k];
            if(c[i][j]==c[i][k+1])k++;
            next[i][j]=k;
        }
    }
    for(int i=1;i<=gs[0];i++)
    {
        int k=0;
        for(int j=1;j<=2*m;j++)
        {
            while(k&&c[i][k+1]!=b[j])k=next[i][k];
            if(c[i][k+1]==b[j])k++;
            if(i==gs[0])last[j]=k;
            if(k==gs[i]){
                int l=j-k+1;
                while(l&&!first[i][l])
                {
                    first[i][l]=j;
                    l--;
                }
                k=next[i][k];
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        int r=i+m-1,l=i-1,g=1;
        if(a[1]!='*'&&i+gs[g]-1!=first[g][i])continue;
        while(l<=r&&g<=gs[0])
        {
            l++;
            l=first[g][l];
            if(!l)break;
            g++;
        }
        if(a[n]!='*')
        {
            if(g!=gs[0]+1||l>r)continue;
            ans+=(last[r]==gs[gs[0]]);
        }
        else if(g==gs[0]+1&&l<=r)ans++;
    }
    cout<<ans<<endl;
    return 0;
}

View Code

完。

updata：

之前的那个会被hack掉！

*a

aaaaaa

会输出0

在判无解的时候出锅了！

AC代码

#include<bits/stdc++.h>
using namespace std;
char a[200],b[210000],c[110][110];
int n,m,ans,nex[110][110],first[55][210000],last[210000],v,gs[110];
int main()
{
//    freopen("pattern.in","r",stdin);freopen("pattern.out","w",stdout);
    scanf("%s%s",a+1,b+1);
    n=strlen(a+1);m=strlen(b+1);
    for(int i=1;i<=n;i++)
    {
        while(a[i]=='*')
        i++;
        gs[0]++;
        while(a[i]!='*'&&i<=n)
        {
            c[gs[0]][++gs[gs[0]]]=a[i];
            i++;
        }
    }
    for(int i=1;i<m;i++)
        b[i+m]=b[i];
    for(int i=1;i<=gs[0];i++)
    {
        int k=0;
        for(int j=2;j<=gs[i];j++)
        {
            while(c[i][j]!=c[i][k+1]&&k)k=nex[i][k];
            if(c[i][j]==c[i][k+1])k++;
            nex[i][j]=k;
        }
    }
    for(int i=1;i<=gs[0];i++)
    {
        int k=0;
        for(int j=1;j<=2*m;j++)
        {
            while(k&&c[i][k+1]!=b[j])k=nex[i][k];
            if(c[i][k+1]==b[j])k++;
            if(i==gs[0])last[j]=k;
            if(k==gs[i]){
                int l=j-k+1;
                while(l&&!first[i][l])
                {
                    first[i][l]=j;
                    l--;
                }
                k=nex[i][k];
            }
        }
    }
    int fl=0;
    for(int i=1;i<=n;i++)
    if(a[i]=='*'){
        fl=1;break;}
    if(!fl&&n!=m)
    {
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i<=m;i++)
    {
        int r=i+m-1,l=i-1,g=1;
        if(a[1]!='*'&&i+gs[g]-1!=first[g][i])continue;
        while(l<=r&&g<=gs[0])
        {
            l++;
            l=first[g][l];
            if(!l)break;
            g++;
        }
        if(a[n]!='*')
        {
            if(g!=gs[0]+1||l>r)continue;
            ans+=(last[r]==gs[gs[0]]);
        }
        else if(g==gs[0]+1&&l<=r)ans++;
    }
    cout<<ans<<endl;
    return 0;
}

View Code

2019.8.19

原文链接:https://www.cnblogs.com/Frost-Delay/p/day18.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有