目录

• 2018.10.12 正睿普及4
  • A 学打字
  • B 减肥计划(DP 背包)
  • C 卡常数(倍增)
  • D 造人(BFS)
  • 考试代码
    • B
    • D

2018.10.12 正睿普及4

时间：3.5h
期望得分：100+?+100+10
实际得分：100+45+100+10

比赛链接

A 学打字

题目链接

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=10005;

char s[N],t[N];

int main()
{
    scanf("%s%s",s+1,t+1);
    int n=strlen(s+1),m=strlen(t+1),ans=0;
    s[n+1]='!',t[n+1]='?';
    for(int i=1; i<=n; )
    {
        int ps=i,pt=1;
        while(s[ps]==t[pt]) ++ps,++pt;
        if(pt>m) i+=m,++ans;
        else ++i,++ans;
    }
    printf("%dn",ans);

    return 0;
}

B 减肥计划(DP 背包)

题目链接

当(sum ai)一定时，(sum bi)越大自然越优。所以令(f[i])表示(sum ai=i)时(sum bi)的最大值，转移就是个背包。
所以复杂度为(O(n^2*a_{max}))。期望得分(60)。
我们发现问题在于背包容量太大。
一个简单的性质是(max{frac{bi}{ai}}geqfrac{sum bi}{sum ai})。所以我们删去所选集合中(frac{bi}{ai})最小的那个一定不会更差。
所以在满足(sum aigeq m)时我们可以不断删元素，得到的答案一定不会更差。这样需要考虑的背包最大容量就是(m+a_{max})。
所以复杂度(O(n(m+a_{max})))。

傻了，考试的时候背包都没想到，一直在想分数规划，但是没法解啊。骗了个分。

//988ms 900kb
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e5+1e4+5;

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}
int Gcd(int x,int y)
{
    return y?Gcd(y,x%y):x;
}

int main()
{
    static int f[N];

    int n=read(),m=read(),mx=0,sum=0;
    memset(f,-0x3f,sizeof f);
    f[0]=0;
    for(int i=1,ai,bi; i<=n; ++i)
    {
        sum+=ai=read(),mx=std::max(mx,ai),bi=read();
        for(int j=std::min(m+mx,sum); j>=ai; --j)
            f[j]=std::max(f[j],f[j-ai]+bi);
    }
    if(sum<m) return puts("-1"),0;

    int A=0,B=1;
    for(int i=m+mx; i>=m; --i)
        if(1ll*A*i<1ll*B*f[i]) A=f[i],B=i;
    int g=Gcd(A,B);
    printf("%d/%dn",A/g,B/g);

    return 0;
}

C 卡常数(倍增)

题目链接

#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define BIT 29
typedef long long LL;
const int N=1e5+5,M=N;

int f[N][30];
char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}
int Calc(int x)
{
    static int bit[66];
    int cnt=0;
    for(int v=x; v; bit[++cnt]=v%10,v/=10);
    while(cnt<5) bit[++cnt]=0;
    std::sort(bit+1,bit+1+cnt);
    int mn=0,mx=0;
    for(int i=1; i<=5; ++i) mn=mn*10+bit[i];
    for(int i=5; i; --i) mx=mx*10+bit[i];
    return mx-mn;
}
void Init()
{
    f[0][0]=0;
    const int n=99999;
    for(int i=1; i<=n; ++i) f[i][0]=Calc(i);
    for(int i=1; i<=BIT; ++i)
        for(int x=1; x<=n; ++x) f[x][i]=f[f[x][i-1]][i-1];
}
void Solve(int x,int t)
{
    static char o[66];
    if(t<=100)
        while(t--) x=f[x][0];
    else
    {
        for(int i=BIT; ~i; --i)
            if(t>>i&1) x=f[x][i];
    }
    int cnt=0;
    for(int v=x; v; o[++cnt]=v%10+'0',v/=10);
    while(cnt<5) o[++cnt]='0';
    for(int i=5; i; putchar(o[i--])); putchar('n');
}

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);

    Init();
    for(int T=read(),c=read(); T--; Solve(read(),c));
    return 0;
}

D 造人(BFS)

题目链接

一条回文路径关于中点对称，所以我们枚举点作为路径中点BFS（一个点走的同时另一个点对称走），就可以知道，对于长为偶数的回文路径，一个点能否一次走到另一个点。
对于长为奇数的回文路径，我们从一条边开始BFS就行了。这部分复杂度(O(n^4))。
有了从一个点能一次到达哪些点，对于询问从起点BFS就可以了。复杂度也是(O(n^4))。

//288ms 8796kb
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
const int N=53,INF=0x3f3f3f3f,dx[]={-1,0},dy[]={0,-1,1};

bool mp[N][N],ok[N][N][N][N];
struct Node1{
    int xa,ya,xb,yb;
};
struct Node2{
    int x,y;
};

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}
inline char Get()
{
    register char c=gc();
    for(; c!='.'&&c!='#'&&c!='F'&&c!='R'; c=gc());
    return c;
}
void BFS(int x1,int y1,int x2,int y2)
{
    static bool vis[N][N];
    static std::queue<Node1> q;

    memset(vis,sizeof vis);
    vis[x1][y1]=1,vis[x2][y2]=1,q.push((Node1){x1,y1,x2,y2});
    while(!q.empty())
    {
        Node1 tmp=q.front(); q.pop();
        int xa=tmp.xa,ya=tmp.ya,xb=tmp.xb,yb=tmp.yb;
        ok[xa][ya][xb][yb]=1,ok[xb][yb][xa][ya]=1;
        for(int i=0,x,y,xx,yy; i<4; ++i)
        {
            x=xa+dx[i],xx=xb+dx[i^1];
            y=ya+dy[i],yy=yb+dy[i^1];
            if(vis[x][y]||vis[xx][yy]||!mp[x][y]||!mp[xx][yy]) continue;
            vis[x][y]=1,vis[xx][yy]=1;
            q.push((Node1){x,yy});
        }
    }
}
int BFS2(int n,int m,int sx,int sy,int ex,int ey)
{
    static int dis[N][N];
    static std::queue<Node2> q;

    while(!q.empty()) q.pop();
    memset(dis,0x3f,sizeof dis);
    dis[sx][sy]=0,q.push((Node2){sx,sy});
    while(!q.empty())//BFS
    {
        int x=q.front().x,y=q.front().y; q.pop();
        if(x==ex&&y==ey) return dis[ex][ey];
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                if(dis[i][j]==INF && ok[x][y][i][j])
                    dis[i][j]=dis[x][y]+1,q.push((Node2){i,j});
    }
    return dis[ex][ey]<INF?dis[ex][ey]:-1;
}

int main()
{
    for(int T=read(); T--; )
    {
        memset(ok,sizeof ok);
        memset(mp,sizeof mp);//边界得清空 
        int n=read(),sx=0,sy=0,ex=0,ey=0;
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                switch(Get())
                {
                    case '.': mp[i][j]=1; break;
                    case '#': mp[i][j]=0; break;
                    case 'F': mp[i][j]=1,ex=i,ey=j; break;
                    case 'R': mp[i][j]=1,sx=i,sy=j; break;
                }
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                if(mp[i][j])
                {
                    BFS(i,j,i,j);
                    if(mp[i][j+1]) BFS(i,j+1);
                    if(mp[i+1][j]) BFS(i,i+1,j);
                }
        printf("%dn",BFS2(n,m,sx,sy,ex,ey));
    }
    return 0;
}

考试代码

B

#include <cstdio>
#include <cctype>
#include <algorithm>
#define eps 1e-14
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e4+5;
//#define double long double

int n,A[N],B[N];
char IN[MAXIN],*TT=IN;
struct Frac
{
    LL x,y;
    Frac(LL x=0,LL y=0):x(x),y(y) {}

    LL Gcd(int x,int y) {return y?Gcd(y,x%y):x;}
    inline void Fix() {LL d=Gcd(std::abs(x),std::abs(y)); x/=d,y/=d;}
    friend Frac operator +(Frac a,Frac b)
    {
        Frac res=Frac{a.x*b.y+a.y*b.x,a.y*b.y};
        res.Fix(); return res;
    }
    friend Frac operator *(Frac a,Frac b)
    {
        Frac res=Frac{a.x*b.x,a.y*b.y};
        res.Fix(); return res;
    }
    friend bool operator !=(Frac a,Frac b)
    {
        a.Fix(),b.Fix(); return a.x!=b.x||a.y!=b.y;
    }
    friend bool operator ==(Frac a,b.Fix(); return a.x==b.x&&a.y==b.y;
    }
    friend bool operator <(Frac a,b.Fix();
        return a.x*b.y<=a.y*b.x;
    }
    inline void Print()
    {
        Fix(),printf("%lld/%lldn",y);
//      Fix(),printf("%I64d/%I64dn",y);
    }
};

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}
void Spec()
{
    Frac ans(0,1);
    for(int s=1,all=1<<n; s<all; ++s)
    {
        int sa=0,sb=0;
        for(int i=0; i<n; ++i) if(s>>i&1) sa+=A[i+1],sb+=B[i+1];
        if(sa>=m && ans<Frac(sb,sa)) ans=Frac(sb,sa);
    }
    ans.Print();
}
bool Check(double mid)
{
    int sum=0;
    for(int i=1; i<=n; ++i)
        if((double)B[i]-mid*A[i]>=0) sum+=A[i];
    return sum>=m;
}
void GetAns(double x)
{
    printf("GetAns:%.10lfn",x);
    int sa=0,sb=0;
    for(int i=1; i<=n; ++i)
        if((double)B[i]-x*A[i]>=0) sa+=A[i],sb+=B[i];
    Frac(sb,sa).Print();
}

int main()
{
    freopen("a.in",stdout);

    n=read(),m=read(); int suma=0,sumb=0;
    for(int i=1; i<=n; ++i)
        suma+=A[i]=read(),sumb+=B[i]=read();
    if(suma<m) return puts("-1"),0;
//  if(n<=20) return Spec(),0;

    double l=0,r=sumb,mid;
    for(int T=1; T<=100; ++T)
    {
        if(Check(mid=(l+r)*0.5)) l=mid;
        else r=mid;
    }
    GetAns(l);

    return 0;
}

D

#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=50;

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}

int main()
{
//  freopen(".in",stdout);

    char s[N];
    for(int T=read(); T--; )
    {
        int n=read(),tx=0,ty=0;
        for(int i=1; i<=n; ++i)
        {
            scanf("%s",s+1);
            for(int j=1; j<=m; ++j)
                if(s[j]=='F') tx=i,ty=j;
                else if(s[j]=='R') sx=i,sy=j;
        }
        int dx=std::abs(sx-tx),dy=std::abs(sy-ty),ans=0;
        if(std::abs(dx-dy)<=1) ans=1;
        else ans=1+(std::max(dx,dy)&1);
        printf("%dn",ans);
    }
    return 0;
}