10.19-10.20 test

2016 10.19-10.20 两天题目by mzx

Day1:

T1:loverfinding

题解：hash

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<string>

 #include<algorithm>

 #include<ctime>

 #include<cmath>

 #include<queue>

 using namespace std;

 #define FILE "loverfinding"

 #define pii pair<long long,long long>

 #define LL long long

 #define up(i,j,n) for(int i=j;i<=n;i++)

 #define down(i,n,j) for(int i=n;i>=j;i--)

 #define max(x,y) ((x)>(y)?(x):(y))

 #define min(x,y) ((x)<(y)?(x):(y))

 #define abs(x) ((x)<0?(-(x)):(x))

 template<typename T>inline bool chkmax(T &a,T b){return a<b?a=b,true : false;}

 template<typename T>inline bool chkmin(T &a,T b){return a>b?a=b,true : false;}

 int read(){

     int x=;char ch=getchar();bool flag=;

     while(ch<''||ch>''){if(ch=='-')flag=;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return flag?-x:x;

 }

 namespace OI{

     void print(int x){printf("%d\n",x);exit();}

     int n,x0,y0,xt,yt,cnt=,nx,ny,dx,dy;

     int hx[],hy[],step=,mod=;

     bool vis[];

     bool hash(int x,int y){

         int pos=abs((LL)(x+)*%mod*(y+)%mod*%mod*)%mod;

         while(vis[pos]&&!(hx[pos]==x&&hy[pos]==y)){

             pos+=step;

             if(pos>mod)pos-=mod;

         }

         if(!vis[pos]){

             vis[pos]=;hx[pos]=x;hy[pos]=y;return ;

         }

         return ;

     }

     void slove(){

         n=read(),nx=x0=read(),ny=y0=read(),xt=read(),yt=read();

         up(i,,n){

             if(nx==xt&&ny==yt)print(cnt);

             if(hash(nx,ny))cnt++;

             dx=read(),dy=read();

             nx+=dx,ny+=dy;

         }

         printf("SingleDogMZX\n");

     }

 }

 int main(){

     freopen(FILE".in","r",stdin);

     freopen(FILE".out","w",stdout);

     using namespace OI;

     slove();

     return ;

 }

T2:snackstore

题解：floyed

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define FILE "snackstore"

#define up(i,j,n) for(int i=j;i<=n;i++)

template<typename T>inline bool chkmax(T &a,T b){return a<b?a=b,true : false;}

template<typename T>inline bool chkmin(T &a,T b){return a>b?a=b,true : false;}

namespace IO{

    char buf[<<],*fs,*ft;

    inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;}

    inline int read(){

        int x=,ch=gc();

        while(ch<''||ch>'')ch=gc();

        while(ch>=''&&ch<='')x=(x<<)+(x<<)+ch-'',ch=gc();

        return x;

    }

}using namespace IO;

namespace OI{

    const int maxn=;

    const int inf=1000000001LL;

    int n,m,Q;

    struct node{

        int id,v;

        bool operator<(const node& b)const{return v<b.v;}

    }v[maxn];

    int A[maxn],pow[maxn];

    int f[maxn][maxn][maxn];

    void init(){

        n=read(),m=read(),Q=read();

        up(i,,n)v[i].v=read(),v[i].id=i;

        int x,y,vv;

        for(int c=;c<=n;c++)

            for(int i=;i<=n;i++)

                for(int j=;j<=n;j++)

                    f[c][i][j]=inf;

        for(int i=;i<=n;i++)f[][i][i]=;

        up(i,,m){

            x=read(),y=read(),vv=read();

            if(vv<f[][y][x])f[][x][y]=f[][y][x]=vv;

        }

        sort(v+,v+n+);

        for(int i=;i<=n;i++)A[i]=v[i].id;

        for(int i=;i<=n;i++)pow[i]=v[i].v;

        for(int c=;c<=n;c++){

            memcpy(f[c],f[c-],sizeof(f[c-]));

            for(int i=;i<=n;i++)

                for(int j=;j<=n;j++)

                    if(f[c][i][A[c]]+f[c][A[c]][j]<f[c][i][j])

                        f[c][i][j]=f[c][i][A[c]]+f[c][A[c]][j];

        }

        for(int c=;c<=n;c++)

            for(int i=;i<=n;i++)

                sort(f[c][i]+,f[c][i]+n+);

    }

    int left,right,mid,ans;

    inline int find(int c){

        left=,right=n;

        while(left<=right){

            mid=(left+right)>>;

            if(c>=pow[mid])ans=mid,left=mid+;

            else right=mid-;

        }

        return ans;

    }

    inline int Find(int *a,int d){

        left=,right=n;

        while(left<=right){

            mid=(left+right)>>;

            if(a[mid]>d)right=mid-;

            else left=mid+,ans=mid;

        }

        return ans;

    }

    void slove(){

        init();

        int s,c,d,pos;

        up(i,,Q){

            s=read(),c=read(),d=read();

            printf("%d\n",Find(f[find(c)][s],d)-);

        }

        return;

    }

}

int main(){

    freopen(FILE".in","r",stdin);

    freopen(FILE".out","w",stdout);

    using namespace OI;

    slove();

    return ;

}

T3：有点恶心，暂时搁置

Day2:

T1:three_squirrels

题解：拓扑排序

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<string>

#include<algorithm>

#include<ctime>

#include<cmath>

#include<queue>

using namespace std;

#define FILE "three_squirrels"

#define pii pair<long long,long long>

#define LL long long

#define up(i,j,n) for(int i=j;i<=n;i++)

#define down(i,n,j) for(int i=n;i>=j;i--)

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define abs(x) ((x)<0?(-(x)):(x))

template<typename T>inline bool chkmax(T &a,T b){return a<b?a=b,true : false;}

template<typename T>inline bool chkmin(T &a,T b){return a>b?a=b,true : false;}

int read(){

    int x=;char ch=getchar();bool flag=;

    while(ch<''||ch>''){if(ch=='-')flag=;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return flag?-x:x;

}

namespace OI{

    const int maxn=,mod=;

    int f[maxn];

    int n;

    struct node{

        int y,next;

    }e[];

    int len=,linkk[maxn];

    void insert(int x,int y){

        e[++len].y=y;

        e[len].next=linkk[x];

        linkk[x]=len;

    }

    int dfs(int x){

        if(f[x]!=-)return f[x];

        f[x]=;

        for(int i=linkk[x];i;i=e[i].next)f[x]=(f[x]+dfs(e[i].y))%mod;

        return f[x];

    }

    void slove(){

        memset(f,-,sizeof(f));

        f[]=;

        n=read();int k,x;

        up(i,,n){

            k=read();

            up(j,,k){

                x=read();

                insert(i,x);

            }

        }

        printf("%d\n",dfs(n));

    }

}

int main(){

    freopen(FILE".in","r",stdin);

    freopen(FILE".out","w",stdout);

    using namespace OI;

    slove();

    return ;

}

T2:savemzx

题解：树形动规

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<string>

#include<algorithm>

#include<ctime>

#include<cmath>

#include<queue>

using namespace std;

#define FILE "savemzx"

#define pii pair<long long,long long>

#define LL long long

#define up(i,j,n) for(int i=j;i<=n;i++)

#define down(i,n,j) for(int i=n;i>=j;i--)

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define abs(x) ((x)<0?(-(x)):(x))

template<typename T>inline bool chkmax(T &a,T b){return a<b?a=b,true : false;}

template<typename T>inline bool chkmin(T &a,T b){return a>b?a=b,true : false;}

int read(){

    int x=;char ch=getchar();bool flag=;

    while(ch<''||ch>''){if(ch=='-')flag=;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return flag?-x:x;

}

namespace OI{

    const int maxn=;

    const LL inf=10000000000000000LL;

    char s[maxn];

    int next[maxn],n;

    bool vis[maxn];

    inline LL squ(int x){return (LL)x*x;}

    struct node{

        int y,next;

        LL v;

    }e[maxn<<];

    int linkk[maxn],len=;

    void insert(int x,int y,LL v){

        e[++len].y=y;

        e[len].next=linkk[x];

        linkk[x]=len;

        e[len].v=v;

    }

    LL w[maxn],maxx[maxn],maxx2[maxn],child[maxn];

    int fa[maxn];

    LL ans=;

    void dfs(int x){

        for(int i=linkk[x];i;i=e[i].next){

            if(e[i].y==fa[x])continue;

            fa[e[i].y]=x;

            dfs(e[i].y);

            chkmax(ans,e[i].v);

            w[e[i].y]+=e[i].v;

            if(w[e[i].y]>maxx[x])maxx2[x]=maxx[x],maxx[x]=w[e[i].y];

            else if(w[e[i].y]>maxx2[x])maxx2[x]=w[e[i].y];

        }

        chkmax(ans,maxx[x]+maxx2[x]);

        w[x]=maxx[x];

    }

    void slove(){

        scanf("%s",s+);n=strlen(s+);

        int j=;next[]=;

        insert(,,);insert(,,);

        for(int i=;i<=n;i++){

            while(s[i]!=s[j+]&&j)j=next[j];

            if(s[i]==s[j+])j++;

            next[i]=j;

            insert(j,i,squ(j-i));

            insert(i,j,squ(i-j));

        }

        dfs();

        printf("%lld\n",ans);

        return;

    }

}

int main(){

    freopen(FILE".in","r",stdin);

    freopen(FILE".out","w",stdout);

    using namespace OI;

    slove();

    return ;

}

T3:chocolatebox

题解：请自行推导公式，数学题

总的来说，这套题，两个T3（实现了让人不想看的目标），T2都是图论题，也需要一些分析和转化，总体不错；

但这套题很恶心的地方是，卡常卡的太厉害（你能想象day1T1被卡的全T吗？），day1T2写完了正解后，交上去发现一直T，直到我抄了std的输入之后......

桑心过度；

祝初赛考出好成绩,啦啦啦......

巴特西

10.19-10.20 test

最新文章

热门文章