首页 > 代码库 > 2016-11-12试题解题报告

2016-11-12试题解题报告

2016-11-12试题解题报告

By shenben

本解题报告解析均为100分解题思路。


T1
枚举+乘法原理(+容斥原理)
滚动枚举最短的S串在T串的头和尾,然后用乘法原理当前的x。
ans=∑x(注意S串是类似“aabb”这种情况)
T2
dp
第一问:
根据题目中的伪代码,一个点一定会与位于这个点之后并且不大于这个点的点连一条边,样例中3会与1和2连一条边,而1就不会与2连边,这样就构成了一个下降的序列。那么反过来,不连边的点就构成了上升序列,这就是一个点独立集,最大的点独立集就是最长上升子序列。所以第一问的答案就是最长上升子序列的长度。 
第二问:
问哪些点在最长上升子序列中必不可少。
因为最长上升子序列可能有多个,那么所有上升子序列中公共的点就是一定在最大点独立集中的点。

T3
。。
暂时不知道


T1代码
AI版

#include<cstdio>#include<cstring>#include<algorithm>#define ll long long#ifdef unix//ifdef千万别再写错了区别 ifndef(×) #define LL "%lld"#else#define LL "%I64d"#endifusing namespace std;const int N=3e5+10,M=210;const int inf=0x3f3f3f;char t[N],s[M];int n,m,cnt,near[N][30];int head[N],tail[N];void special_judge(){    int p=-1;ll ans=0;    for(int i=0;i<m;i++){        if(t[i]!=s[0]) continue;        ans+=(ll)(i-p)*(ll)(m-i);        p=i;    }    printf(LL,ans);}#define name "encrypt" int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    gets(t);gets(s);    m=strlen(t);n=strlen(s);    if(n==1){special_judge();return 0;}    //near[i][j]表示距离t[i]右边最近的a~z的下标     for(int i=1;i<=26;i++) near[m][i]=inf;    for(int i=m-1;i>=0;i--){        for(int j=1;j<=26;j++){            if(t[i]==j+a-1) near[i][j]=0;            else if(near[i+1][j]==inf) near[i][j]=inf;            else near[i][j]=near[i+1][j]+1;        }    }    for(int i=0;i<=m;i++){        for(int j=1;j<=26;j++){            if(!near[i][j]){//aabb这种情况的更新                 near[i][j]=near[i+1][j]+1;            }        }    }    for(int i=0;i<m;i++){        if(t[i]!=s[0]) continue;        int j=i,zj=1;        for(;j<inf&&zj<n;zj++)j+=near[j][s[zj]-a+1];        if(zj==n&&j<inf) head[++cnt]=i,tail[cnt]=j;    }    ll ans=0;head[0]=-1;//乘法原理     for(int i=1;i<=cnt;i++) ans+=(ll)(head[i]-head[i-1])*(ll)(m-tail[i]);    printf(LL,ans);    fclose(stdin);    fclose(stdout);    return 0;}

简短精炼的std

#include<cstdio>#include<cstring>#include<iostream>#define ll long long#ifdef unix#define LL "%lld"#else#define LL "%I64d"#endifusing namespace std;const int N=3e5+10;const int M=210;char t[N],s[M];int n,m,f[M];ll ans;#define name "encrypt"int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    gets(t+1);    gets(s+1);    n=strlen(t+1);    m=strlen(s+1);    for(int i=1;i<=m;i++) f[i]=n+1;    for(int i=n;i;i--){        f[m+1]=i;        for(int j=1;j<=m;j++){            if(t[i]==s[j]){                f[j]=min(f[j],f[j+1]);            }        }        ans+=n-f[1]+1;    }    printf(LL,ans);    fclose(stdin);    fclose(stdout);    return 0;}

T2代码

#include<cstdio>#include<algorithm>#define R registerusing namespace std;inline int read(){    R int x=0;bool f=1;    R char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=0;ch=getchar();}    while(ch>=0&&ch<=9){x=(x<<3)+(x<<1)+ch-0;ch=getchar();}    return f?x:-x;}const int N=1e5+10;int n,len,a[N],b[N],f[N],maxx[N],sum[N];bool vis[N];#define name "bubble"int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    n=read();    for(int i=1;i<=n;i++) a[i]=read();    b[len=1]=a[1];f[1]=1;    for(int i=2,pos;i<=n;i++){        if(a[i]>b[len]){            b[++len]=a[i];            f[i]=len;        }        else{            pos=lower_bound(b+1,b+len,a[i])-b;            b[pos]=a[i];            f[i]=pos;        }    }    printf("%d\n",len);    for(int i=n;i;i--){        if(f[i]==len||maxx[f[i]+1]>a[i]){            vis[i]=1;sum[f[i]]++;            maxx[f[i]]=max(maxx[f[i]],a[i]);        }    }    for(int i=1;i<=n;i++) if(vis[i]&&sum[f[i]]==1) printf("%d ",i);    fclose(stdin);    fclose(stdout);    return 0;}

T3代码]

暂无AC代码

/*20分存档#include<cstdio>#include<cstring>#include<stack>#include<vector>#include<iostream>#include<algorithm>#define R register#define debug(x,y) cout<<x<<"---"<<y<<endl#define ll long long#ifdef unix#define LL "%lld"#else#define LL "%I64d"#endifusing namespace std;inline ll read(){    R ll x=0;bool f=1;    R char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=0;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();}    return f?x:-x;}const ll N=2001;const ll QLEN=N*4-5;const ll inf=2e9;ll n,m,pd,sd,dfn[N],low[N],sum[N];bool mark[N],vis[N];ll b[N][N];stack<ll>s;struct node{    ll id,v;    node(){id=0;v=0;}    bool operator <(const node &a) const{        return v>a.v;    }}ind[N],outd[N];struct ss{    ll id,val;    ss(){id=0;val=0;}    ss(ll _id,ll _val){        id=_id;        val=_val;    }    bool operator <(const ss &a) const{        if(val==a.val) return id<a.id;        return val>a.val;    }}dis[N];void tarjan(ll v){    dfn[v]=low[v]=++pd;    mark[v]=1;    s.push(v);    for(ll w=1;w<=n;w++){        if(b[v][w]){            if(!dfn[w]){                tarjan(w);                low[v]=min(low[v],low[w]);            }            else if(mark[w]){                low[v]=min(low[v],dfn[w]);            }        }    }    ll u;    if(low[v]==dfn[v]){        sd++;        do{            u=s.top();s.pop();            sum[sd]++;            mark[u]=0;        }while(u!=v);    }}ll q[N<<2]={0};ll ans[N];ll sans[N];inline void spfa(ll S){    ll h=0,t=1;    for(ll i=1;i<=n;i++) dis[i].id=i;    for(ll i=1;i<=n;i++) dis[i].val=-inf;    dis[S].val=0;    vis[S]=1;    q[t]=S;    while(h<t){        if(++h>QLEN) h=1;        ll x=q[h];        vis[x]=0;        for(ll i=1;i<=n;i++){            if(b[x][i]){                ll v=i;                if(dis[v].val<dis[x].val+1){                    dis[v].val=dis[x].val+1;                    if(!vis[v]){                        vis[v]=1;                        if(++t>QLEN) t=1;                        q[t]=v;                    }                }            }        }    }    //printf("%d",dis[T]);}void Cl(){    sd=0;pd=0;    memset(dfn,0,sizeof dfn);    memset(low,0,sizeof low);    memset(sum,0,sizeof sum);    memset(vis,0,sizeof vis);    memset(mark,0,sizeof mark);    while(!s.empty()) s.pop();}#define name "rebuild"int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    Cl();    n=read();m=read();    for(ll i=1,x,y;i<=m;i++){        x=read();y=read();        outd[x].id=x;outd[x].v+=1;        b[x][y]=i;    }    for(ll i=1;i<=n;i++) if(!dfn[i]) tarjan(i);    sort(sum+1,sum+sd+1,greater<ll>());    if(sum[1]==n){        printf(LL"\n"LL"\n",n,m);        for(ll i=1;i<=m;i++) printf("%d ",i);        return 0;    }    sort(outd+1,outd+n+1);    spfa(outd[1].id);    sort(dis+1,dis+n+1);    printf(LL"\n",dis[1].val+1);    ll tv=dis[1].val;ans[++ans[0]]=dis[1].id;    for(ll i=2;i<=n;i++) if(dis[i].val==tv) ans[++ans[0]]=dis[i].id;    for(ll i=1,z=outd[1].id,pt,x,y;i<=ans[0];i++){        pt=ans[i];        if(b[z][pt]) sans[++sans[0]]=b[z][pt];        if(b[pt][z]) sans[++sans[0]]=b[pt][z];    }    sort(sans+1,sans+sans[0]+1);    ll cnt=unique(sans+1,sans+sans[0]+1)-(sans+1);    printf(LL"\n",cnt);    for(ll i=1;i<=cnt;i++){        printf(LL" ",sans[i]);    }    fclose(stdin);    fclose(stdout);    return 0;}*/

 

2016-11-12试题解题报告