首页 > 其他 > 详细

2019-7-25 考试总结

时间：2019-07-25 17:17:26      阅读：76      评论：0      收藏：0      [点我收藏+]

A. 匹配

考试代码($WA18$)

技术分享图片 
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#define max(x,y) ((x)>(y)?(x):(y))
#define Maxn 100050
#define INF 0x7fffff
#define k1 10007
#define k2 109
#define mod1 1000000007
#define mod2 1000000009
#define Reg register
using namespace std;
int la,lb,t;
char B[Maxn];
long long lss1,lss2,has11[Maxn],has12[Maxn],has21[Maxn],has22[Maxn],pow1[Maxn],pow2[Maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        has11[0]=has12[0]=has21[0]=has22[0]=0;
        scanf("%d%d",&la,&lb);
        string S,K; cin>>S;
        for(Reg int i=1,x;i<=min(lb+1,la);++i)
        {
            x=S[i-1];
            has11[i]=(has11[i-1]*k1+x-‘a‘+1)%mod1;
            has12[i]=(has12[i-1]*k2+x-‘a‘+1)%mod2;
            B[i]=x;
        }
        cin>>K;
        for(Reg int i=0;i<3;++i)
        {
            if(K[i]>=‘a‘&&K[i]<=‘z‘)
            {
                B[++lb]=K[i];
                break;
            }
        }
        pow1[0]=pow2[0]=1;
        for(Reg int i=1;i<=lb;++i)
        {
            has21[i]=(has21[i-1]*k1+B[i]-‘a‘+1)%mod1;
            has22[i]=(has22[i-1]*k2+B[i]-‘a‘+1)%mod2;
            pow1[i]=pow1[i-1]*k1%mod1;
            pow2[i]=pow2[i-1]*k2%mod2;
        }
        int ans=0;
        for(Reg int i=lb;i>=1;--i)
        {
            lss1=(has21[lb]-has21[i]*pow1[lb-i]%mod1+mod1)%mod1;
            lss2=(has22[lb]-has22[i]*pow2[lb-i]%mod2+mod2)%mod2;
            if(lss1==has11[lb-i]&&lss2==has12[lb-i]) ans=max(ans,lb-i);
        }
        printf("%d\n",ans);
    }
    return 0;
}
View Code

$AC$代码

技术分享图片 
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#define max(x,y) ((x)>(y)?(x):(y))
#define Maxn 100050
#define INF 0x7fffff
#define k1 10007
#define k2 109
#define mod1 1000000007
#define mod2 1000000009
#define Reg register
using namespace std;
int la,lb,t;
char B[Maxn];
long long lss1,lss2,has11[Maxn],has12[Maxn],has21[Maxn],has22[Maxn],pow1[Maxn],pow2[Maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        has11[0]=has12[0]=has21[0]=has22[0]=0;
        scanf("%d%d",&la,&lb);
        string S,K; cin>>S;
        for(Reg int i=1,x;i<=min(lb+1,la);++i)
        {
            x=S[i-1];
            has11[i]=(has11[i-1]*k1+x-‘a‘+1)%mod1;
            has12[i]=(has12[i-1]*k2+x-‘a‘+1)%mod2;
            B[i]=x;
        }
        cin>>K;
        for(Reg int i=0;i<3;++i)
        {
            if(K[i]>=‘a‘&&K[i]<=‘z‘)
            {
                B[++lb]=K[i];
                break;
            }
        }
        pow1[0]=pow2[0]=1;
        for(Reg int i=1;i<=lb;++i)
        {
            has21[i]=(has21[i-1]*k1+B[i]-‘a‘+1)%mod1;
            has22[i]=(has22[i-1]*k2+B[i]-‘a‘+1)%mod2;
            pow1[i]=pow1[i-1]*k1%mod1;
            pow2[i]=pow2[i-1]*k2%mod2;
        }
        int ans=0;
        for(Reg int i=lb;i>=0;--i)
        {
            lss1=(has21[lb]-has21[i]*pow1[lb-i]%mod1+mod1)%mod1;
            lss2=(has22[lb]-has22[i]*pow2[lb-i]%mod2+mod2)%mod2;
            if(lss1==has11[lb-i]&&lss2==has12[lb-i]) ans=max(ans,lb-i);
        }
        printf("%d\n",ans);
    }
    return 0;
}
View Code

低错总结：

枚举不够。。从$l_b$枚举到了$1$，结果$WA18$，

然后考试后把$1$改成了$0$，然后过了。

 

B. 回家

考试代码($WA 20$)

技术分享图片 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#define min(x,y) ((x)<(y)?(x):(y))
#define Maxn 200050
#define Reg register
using namespace std;
int biao[Maxn];
int t,n,m,tot,top,ans,ok,fir[Maxn],fic[Maxn],vis[Maxn];
int root,indx,cnt,dfn[Maxn],low[Maxn],cur[Maxn],stack[Maxn],pos[Maxn],num[Maxn];
struct Tu {int st,ed,next;} lian[Maxn*2],liap[Maxn*2];
vector<vector<int> > dcc(Maxn/10);
void add(int x,int y)
{
    lian[++tot].st=x;
    lian[tot].ed=y;
    lian[tot].next=fir[x];
    fir[x]=tot;
    return;
}
void adp(int x,int y)
{
    liap[++top].st=x;
    liap[top].ed=y;
    liap[top].next=fic[x];
    fic[x]=top;
    return;
}
void tarjan(int x,int fat)
{
    dfn[x]=low[x]=++indx;
    if(x==root&&!fir[x]) {dcc[++cnt].push_back(x); return;}
    stack[++stack[0]]=x;
    int flag=0;
    for(Reg int i=fir[x];i;i=lian[i].next)
    {
        if(!dfn[lian[i].ed])
        {
            tarjan(lian[i].ed,x);
            low[x]=min(low[x],low[lian[i].ed]);
            if(low[lian[i].ed]>=dfn[x])
            {
                ++flag;
                if(flag>0||x!=root) cur[x]=1;
                ++cnt;
                while(stack[stack[0]]!=lian[i].ed)
                    dcc[cnt].push_back(stack[stack[0]--]);
                dcc[cnt].push_back(stack[stack[0]--]);
                dcc[cnt].push_back(x);
            }
        }
        else if(lian[i].ed!=fat)
            low[x]=min(low[x],dfn[lian[i].ed]);
    }
    return;
}
void dfs(int x)
{
    vis[x]=1;
    if(x==pos[n]) {ok=1; return;}
    if(ok) return;
    for(Reg int i=fic[x];i;i=liap[i].next)
    {
        if(!vis[liap[i].ed])
        {
            if(biao[liap[i].ed]) stack[++stack[0]]=biao[liap[i].ed];
            dfs(liap[i].ed);
            if(!ok) --stack[0];
            else return;
        }
    }
    return;
}
void init()
{
    tot=top=ans=ok=root=indx=cnt=stack[0]=0;
    for(Reg int x=1;x<=n;++x)
    {
        biao[x]=fir[x]=fic[x]=cur[x]=vis[x]=dfn[x]=low[x]=pos[x]=num[x]=0;
        if(x<Maxn) dcc[x].clear();
    }
    return;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init();
        for(Reg int i=1,x,y;i<=m;++i)
        {
            scanf("%d%d",&x,&y);
            add(x,y); add(y,x);
        }
        for(Reg int i=1;i<=n;++i)
            if(!dfn[i]) root=i,tarjan(i,i);
        int num=cnt;
        for(Reg int i=1;i<=n;++i) if(cur[i]) pos[i]=++num,biao[num]=i;
        for(Reg int i=1,l;i<=cnt;++i)
        {
            l=dcc[i].size();
            for(Reg int j=0,x;j<l;++j)
            {
                x=dcc[i][j];
                if(cur[x]) {adp(pos[x],i); adp(i,pos[x]);}
                else pos[x]=i;
            }
        }
        cnt=num; stack[0]=0;
        dfs(pos[1]);
        memset(vis,0,sizeof(vis)); ans=0;
        for(Reg int i=1;i<=stack[0];++i)
        {
            if(!vis[stack[i]]&&stack[i]!=n&&stack[i]!=1)
            {
                ++ans;
                vis[stack[i]]=1;
            }
        }
        printf("%d\n",ans);
        for(Reg int i=1;i<=n;++i) if(vis[i]) printf("%d ",i);
        printf("\n");
    }
    return 0;
}
View Code

$AC$代码

技术分享图片 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define min(x,y) ((x)<(y)?(x):(y))
#define Maxn 200050
#define Reg register
using namespace std;
int biao[Maxn*5];
int t,n,m,tot,top,ans,ok,fir[Maxn*5],fic[Maxn*5],vis[Maxn*5];
int root,indx,cnt,dfn[Maxn*5],low[Maxn*5],cur[Maxn],stack[Maxn*5],pos[Maxn*5];
struct Tu {int st,ed,next;} lian[Maxn*8],liap[Maxn*8];
vector<vector<int> > dcc(Maxn);
void add(int x,int y)
{
    lian[++tot].st=x;
    lian[tot].ed=y;
    lian[tot].next=fir[x];
    fir[x]=tot;
    return;
}
void adp(int x,int y)
{
    liap[++top].st=x;
    liap[top].ed=y;
    liap[top].next=fic[x];
    fic[x]=top;
    return;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++indx;
    stack[++stack[0]]=x;
    if(x==root&&!fir[x]) {dcc[++cnt].push_back(x); return;}
    int flag=0;
    for(Reg int i=fir[x];i;i=lian[i].next)
    {
        if(!dfn[lian[i].ed])
        {
            tarjan(lian[i].ed);
            low[x]=min(low[x],low[lian[i].ed]);
            if(low[lian[i].ed]>=dfn[x])
            {
                ++flag; if(flag>0||x!=root) cur[x]=1;
                ++cnt;
                while(stack[stack[0]]!=lian[i].ed)
                    dcc[cnt].push_back(stack[stack[0]--]);
                dcc[cnt].push_back(stack[stack[0]--]);
                dcc[cnt].push_back(x);
            }
        }
        else low[x]=min(low[x],dfn[lian[i].ed]);
    }
    return;
}
void dfs(int x)
{
    vis[x]=1;
    if(x==pos[n]) {ok=1; return;}
    if(ok) return;
    for(Reg int i=fic[x];i;i=liap[i].next)
    {
        if(!vis[liap[i].ed])
        {
            if(biao[liap[i].ed]) stack[++stack[0]]=biao[liap[i].ed];
            dfs(liap[i].ed);
            if(biao[liap[i].ed]&&!ok) --stack[0];
            if(ok) return;
        }
    }
    return;
}
void init()
{
    tot=top=ans=ok=root=indx=cnt=stack[0]=0;
    for(Reg int x=0;x<=n*2;++x)
        biao[x]=fir[x]=fic[x]=cur[x]=vis[x]=dfn[x]=low[x]=pos[x]=0;
    return;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init();
        for(Reg int i=1,x,y;i<=m;++i)
        {
            scanf("%d%d",&x,&y);
            add(x,y); add(y,x);
        }
        for(Reg int i=1;i<=n;++i)
            if(!dfn[i]) root=i,tarjan(i);
        int num=cnt;
        for(Reg int i=1;i<=n;++i) if(cur[i]) {pos[i]=++num; biao[num]=i;}
        for(Reg int i=1,l;i<=cnt;++i)
        {
            l=dcc[i].size();
            for(Reg int j=0,x;j<l;++j)
            {
                x=dcc[i][j];
                if(cur[x]) {adp(pos[x],i); adp(i,pos[x]);}
                else pos[x]=i;
            }
            dcc[i].clear();
        }
//        cout<<endl;
//        for(Reg int i=1;i<=n;++i) cout<<pos[i]<<‘ ‘;
//        cout<<endl;
        cnt=num; stack[0]=0; ok=0;
        dfs(pos[1]);
        memset(vis,0,sizeof(vis)); ans=0;
        for(Reg int i=1;i<=stack[0];++i)
        {
            if(!vis[stack[i]]&&stack[i]!=n&&stack[i]!=1)
            {
                ++ans;
                vis[stack[i]]=1;
            }
        }
        printf("%d\n",ans);
        for(Reg int i=1;i<=n;++i) if(vis[i]) printf("%d ",i);
        printf("\n");
    }
    return 0;
}
View Code

低错总结：

1、数组没开够。

2、板子不熟练，考试调$Tarjan$调了半小时，然后最后还没打对。

$Tarjan$找割点的板子

void tarjan(int x)
{
    dfn[x]=low[x]=++indx;
    stack[++stack[0]]=x;
    if(x==root&&!fir[x]) {dcc[++cnt].push_back(x); return;}
    int flag=0;
    for(Reg int i=fir[x];i;i=lian[i].next)
    {
        if(!dfn[lian[i].ed])
        {
            tarjan(lian[i].ed);
            low[x]=min(low[x],low[lian[i].ed]);
            if(low[lian[i].ed]>=dfn[x])
            {
                ++flag; if(flag>1||x!=root) cur[x]=1;
                ++cnt;
                while(stack[stack[0]]!=lian[i].ed)
                    dcc[cnt].push_back(stack[stack[0]--]);
                dcc[cnt].push_back(stack[stack[0]--]);
                dcc[cnt].push_back(x);
            }
        }
        else low[x]=min(low[x],dfn[lian[i].ed]);
    }
    return;
}

考试时码的：

void tarjan(int x,int fat)
{
    dfn[x]=low[x]=++indx;
    if(x==root&&!fir[x]) {dcc[++cnt].push_back(x); return;}
    stack[++stack[0]]=x;
    int flag=0;
    for(Reg int i=fir[x];i;i=lian[i].next)
    {
        if(!dfn[lian[i].ed])
        {
            tarjan(lian[i].ed,x);
            low[x]=min(low[x],low[lian[i].ed]);
            if(low[lian[i].ed]>=dfn[x])
            {
                ++flag;
                if(flag>0||x!=root) cur[x]=1;
                ++cnt;
                while(stack[stack[0]]!=lian[i].ed)
                    dcc[cnt].push_back(stack[stack[0]--]);
                dcc[cnt].push_back(stack[stack[0]--]);
                dcc[cnt].push_back(x);
            }
        }
        else if(lian[i].ed!=fat)
            low[x]=min(low[x],dfn[lian[i].ed]);
    }
    return;
}

3、

void dfs(int x)
{
    vis[x]=1;
    if(x==pos[n]) {ok=1; return;}
    if(ok) return;
    for(Reg int i=fic[x];i;i=liap[i].next)
    {
        if(!vis[liap[i].ed])
        {
            if(biao[liap[i].ed]) stack[++stack[0]]=biao[liap[i].ed];
            dfs(liap[i].ed);
            if(!ok) --stack[0];
            else return;
        }
    }
    return;
}

这个地方的弹栈弹过了，出现负数。。

改了一点：

if(biao[liap[i].ed]&&!ok) --stack[0];
if(ok) return;

然后过了。。

 

 

总结：

$T1$第一眼看是$KMP$，然后不会打。。。

打了一个$Hash$，然后$WA18$。

觉得自己之前打的是个假的$Hash$，

$T2$基本上是个$Tarjan$的板子，然后$WA20$，

这次$T1$和$T2$基本上都是送分题，然后就爆炸了。

板子不会，代码能力差，低错。。。。

然后最后$18+20+0=38$，

没什么水平。。。

最后忠告：

$AC$一道题需要$100+$行的代码，然而从$AC$到$WA$仅仅需要$1$个字符。

所以一定要打对拍。。

 

2019-7-25 考试总结

原文：https://www.cnblogs.com/Milk-Feng/p/11243805.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！