Contest 20140708 testA && testC

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

testA

输入文件: testA.in 输出文件testA.out 时限2000ms

问题描述：

如果一个数化为一个二进制数之后(没有前导0),0的个数>=1的个数。那么这个数就是方数。

Eg.(12) = (1100) 2个1和2个0 所以12是一个方数。

(6)=(110) 2个1和1个0所以6不是一个方数。

现在方老师想知道区间[L,R]里有多少个方数。

输入描述：

一共一行L和R。(1<=L<=R<=2*10^9)

输出描述：

一个数表示[L,R]里有多少个方数。

数据范围 N<=200 , W<=100000 , M<=19900

样例输入：

2 12

样例输出：

这道题正解是用组合数算。但是明显数位DP要简单得多。

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

using namespace std;

#define MAXN 1000000

#define PROB "testA"

int ans1[MAXN];

int work1()

{

        //freopen(PROB".in","r",stdin);

        //freopen(PROB".out","w",stdout);

        int ans=;

        int x,t0,t1;

        int i;

        for (i=;i<MAXN;i++)

        {

                x=i;

                t0=t1=;

                //cout<<i<<":";

                while (x)

                {

                        if (x&)

                        {

                //                cout<<"1";

                                t1++;

                        }else

                        {

                //                cout<<"0";

                                t0++;

                        }

                        x>>=;

                }

                //cout<<endl;

                if (t0>=t1)

                {

                        ans++;

                /*        x=i;

                        t0=t1=0;

                        cout<<i<<":";

                        while (x)

                        {

                                if (x&1)

                                {

                                        cout<<"1";

                                        t1++;

                                }else

                                {

                                        cout<<"0";

                                        t0++;

                                }

                                x>>=1;

                        }

                        cout<<endl;*/

                }

                //printf("%d %d\n",i,ans);

                ans1[i]=ans;

        }

}

bool num[];

int rec[];

int topn;

int dp[][];

bool vis[][];

int solve(int now,int mr,int ov)//mr=t0-t1

{

        if (ov&&vis[now][mr+])

        {

                return dp[now][mr+];

        }

        int ret=;

        if (now==-)

        {

                if (mr>=)

                {

        /*                for (int i=topn;i>=0;i--)

                        {

                                cout<<rec[i];

                        }

                        cout<<endl;*/

                }

                return mr>=;

        }

        if (ov)

        {

                rec[now]=;

                ret+=solve(now-,mr+,true);

                rec[now]=;

                ret+=solve(now-,mr-,true);

                vis[now][mr+]=;

                return dp[now][mr+]=ret;

        }else

        {

                if (num[now]==)

                {

                        rec[now]=;

                        ret+=solve(now-,mr+,true);

                        rec[now]=;

                        ret+=solve(now-,mr-,false);

                }else

                {

                        rec[now]=;

                        ret+=solve(now-,mr+,false);

                }

                return ret;

        }

}

int work2(int x)

{

        int i;

        if (x==)return ;

        topn=-;

        memset(dp,,sizeof(dp));

        memset(vis,,sizeof(vis));

        while (x)

        {

                num[++topn]=x&;

                x>>=;

        }

        int ans=;

        rec[topn]=;

        ans+=solve(topn-,-,);

        rec[topn]=;

        for (i=topn-;i>=;i--)

        {

                rec[i+]=;

                rec[i+]=;

                ans+=solve(i,-,);

        }

        return ans+;

}

int main()

{

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

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

        int i;        int l,r;

        scanf("%d%d",&l,&r);

        int ans;

        ans=work2(r)-work2(l-);

        cout<<ans<<endl;

}

testC

输入文件: testC.in 输出文件testC.out 时限1000ms

问题描述：

给定一个n*m的国际象棋棋盘(左上角那个格子是黑的)，方老师在第0时刻我们把所有的黑色格子全部重新涂成0号颜色,在第i个时刻方老师会把一些点(如果4个和他有恰好有一个公共顶点的格子都涂上的是i-1号颜色)重新涂成i号颜色(这种循环会无限进行下去，而且每次重新涂颜色是同时进行的)。最后问有多少个格子恰好被重新涂了x次。

输入描述：

一行三个数n,m,x。(1<=n,m<=5000,x<=10^9)

输出描述：

一个数表示有多少个格子被重新涂了x次

样例输入：

3 3

样例输出：

 这道题主要是要联系生活，如果没有发现国际象棋棋盘是那种白黑间隔着的。那这道题就真的不可做了。
另外，考虑要全面。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 1000

#define VAL1 100009

#define PROB "testC"

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

int n,m;

int main()

{

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

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

        int x;

        scanf("%d%d%d",&n,&m,&x);

        if (x=0)

        {

                printf("%d\n",m*n/2);

                return 0;

        }

        if (n==1||n==2||m==1||m==2)

        {

                printf("0\n");

                return 0;

        }

        n-=(x-1)*2;

        m-=(x-1)*2;

        printf("%d\n",max(0,(n+m-2)));

}