00:00/00:00

250 : TheNumberGame

题意 :

给你两个数,两个人轮流操作,每次你可以把当前数反转或者除以10,然后给你的数字在int范围内,然后问你在500步内你可以把数字变成和另一个数相同,则你获胜。。。

分析 :

这里有一个非常简单的结论,我们只需要判断数字b是否在a中出现就好啦,正反都要判断,为什么自己想。。。

代码 :

int a[18],b[18],c[18];
string TheNumberGame::determineOutcome(int A, int B) 
{
    int ans=0;
    int lena=0,lenb=0;
    while(A)
        a[++lena]=A%10,A/=10;
    while(B)
        b[++lenb]=B%10,B/=10;
    for(int i=1;i<=lenb;i++)
        c[i]=b[lenb-i+1];
    for(int i=1;i<=lena-lenb+1;i++)
    {
        int zz=1;
        for(int j=1;j<=lenb;j++)
            if(a[i+j-1]!=b[j]){zz=0;break;}
        if(zz==1){ans=1;break;}
    }
    for(int i=1;i<=lena-lenb+1;i++)
    {
        int zz=1;
        for(int j=1;j<=lenb;j++)
            if(a[i+j-1]!=c[j]){zz=0;break;}
        if(zz==1){ans=1;break;}
    }
    if(ans==1)
        return "Manao wins";
    else return "Manao loses";
}

500:PolygonTraversal

该题就是Div2 1000的升级版,数据范围由13变成18,一样写就好啦,一算极限数据大概1.6亿,因为是TC所以能过。。。

代码 :


LL dp[1<<18][19]; vector <int> show[19]; void init(int now, const vector<int> & vec) { for(int i=0;i<=now;i++) show[i].clear(); for(int i=0;i<(1<<now);i++) show[__builtin_popcount(i)].push_back(i); memset(dp,0,sizeof(dp)); int start=0; for(int i=0;i<vec.size();i++) start|=(1<<(vec[i]-1)); show[vec.size()].clear(); show[vec.size()].push_back(start); dp[start][vec[vec.size()-1]-1]=1; } long long PolygonTraversal::count(int N, vector <int> points) { init(N,points); for(int i=points.size();i<=N;i++) { int siz=show[i].size(); for(int j=0;j<siz;j++) { int now=show[i][j]; for(int k=0;k<N;k++) { if(now&(1<<k)==0||!dp[now][k]) continue; for(int l=0;l<N;l++) { if(now&(1<<l)) continue; int flag1 = 0, flag2 = 0; int lb = min(k, l) + 1, ub = max(k, l) - 1; for (int ri = 0; ri < N; ri++) if (now >> ri & 1) { if (lb <= ri && ri <= ub) flag1 = 1; else if (ri < lb - 1 || ri > ub + 1) flag2 = 1; } int flag = flag1 & flag2; if(flag==1) dp[now|(1<<l)][l]+=dp[now][k]; } } } } LL ans=0,zz=points[0]-1; for(int i=0;i<N;i++) { if(i==(zz+N-1)%N||i==(zz+N+1)%N||i==zz) continue; ans+=dp[(1<<N)-1][i]; } return ans; }

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注