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
样例输出：
6
这道题正解是用组合数算。但是明显数位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=0; int x,t0,t1; int i; for (i=1;i<MAXN;i++) { x=i; t0=t1=0; //cout<<i<<":"; while (x) { if (x&1) { // cout<<"1"; t1++; }else { // cout<<"0"; t0++; } x>>=1; } //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 ",i,ans); ans1[i]=ans; } } bool num[70]; int rec[70]; int topn; int dp[100][100]; bool vis[100][100]; int solve(int now,int mr,int ov)//mr=t0-t1 { if (ov&&vis[now][mr+50]) { return dp[now][mr+50]; } int ret=0; if (now==-1) { if (mr>=0) { /* for (int i=topn;i>=0;i--) { cout<<rec[i]; } cout<<endl;*/ } return mr>=0; } if (ov) { rec[now]=0; ret+=solve(now-1,mr+1,true); rec[now]=1; ret+=solve(now-1,mr-1,true); vis[now][mr+50]=1; return dp[now][mr+50]=ret; }else { if (num[now]==1) { rec[now]=0; ret+=solve(now-1,mr+1,true); rec[now]=1; ret+=solve(now-1,mr-1,false); }else { rec[now]=0; ret+=solve(now-1,mr+1,false); } return ret; } } int work2(int x) { int i; if (x==0)return 1; topn=-1; memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); while (x) { num[++topn]=x&1; x>>=1; } int ans=0; rec[topn]=1; ans+=solve(topn-1,-1,0); rec[topn]=0; for (i=topn-2;i>=0;i--) { rec[i+1]=1; rec[i+2]=0; ans+=solve(i,-1,1); } return ans+1; } 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-1); 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
1
样例输出：
4
这道题主要是要联系生活，如果没有发现国际象棋棋盘是那种白黑间隔着的。那这道题就真的不可做了。
另外，考虑要全面。
#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
",m*n/2);
return 0;
}
if (n==1||n==2||m==1||m==2)
{
printf("0
");
return 0;
}
n-=(x-1)*2;
m-=(x-1)*2;
printf("%d
",max(0,(n+m-2)));
}