7月7日
- 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
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
long long c[40][40];
void prework(){
memset(c,0,sizeof(c));
c[0][0] = 1 ;
c[1][0] = c[1][1] = 1 ;
for (int i=2;i<40;i++){
c[i][i] = c[i][0] = 1;
for (int j=1;j<i;j++)
c[i][j]=c[i-1][j]+c[i-1][j-1] ;
}
}
long long deal(long long x)
{ if (!x) return 0;
int a[33];
int cur = 0,rest = 0;
long long now = x;
do
{
rest = now & 1; now >>= 1; //!!
a[++cur] = rest;
}
while (now);
for (int i =1 ;i<=cur/2;i++)
{int t =a[i];a[i] = a[cur-i+1];a[cur-i+1] = t;}
long long ans = 0;
for (int i = cur - 2;i>0;i--)
{
for (int j = 0 ; j+1<=i-j;j++)
ans += c[i][i-j];
}
for (int i = 2;i<cur;i++)
{
if (a[i] == 0) continue;
else
{
int num1 = 0 ,num0 = 0;
for (int j = 1;j<i;j++)
if (a[j]) num1++;
else num0++;
num0++;
for (int k = 0; k <=cur-i && k+num1<=cur-k-num1;k++)
ans +=c[cur-i][cur-i-k];
}
}
int num1 = 0,num0 = 0;
for (int i = 1;i<=cur;i++)
if (a[i]) num1++;else num0++;
if (num0>=num1) ans++;
if (cur>1 && a[cur] && num0+1>=num1-1) ans++;
return ans;
}
int main()
{
long long l,r;
prework();
cin>>l>>r;
cout<<deal(r) - deal(l-1);
return 0;
}
3.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<cstdio>
using namespace std;
int max(int a,int b )
{
return a <b? b:a;
}
int main()
{
int n,m,x;
scanf("%d%d%d",&n,&m,&x);
n = n-2*(x-1);m = m - 2*(x-1);
if (m<=0 || n<=0 ) printf("%d",0);
else if (n==1 || m==1)
printf("%d",max(n,m)-max(n,m)/2);
else printf("%d",m+n-2);
return 0;
}
1.正解：简单组合数+特判0
做：想到组合数，但是由于纠结：若不考虑前导零，结果直接为2^n/2（易证），一直深入思考处理前导零，导致时间耗尽。
改：没有使用递推式。C[i][j] = c[i-1][j] + c[i-1][j-1]. (c[i][i] = c[i][0] = 1)
得：组合数深入理解 状态分类不重不漏 学会放弃
2.正解：未完待续
3.正解：直接根据题意列出，找规律。（简单题）
做：（1）没有注意“国际象棋”，不敏感。
改：特判ans==0 置于最前端。
得：一个字一个字审题 注意特殊情况 发现漏洞补上的位置要准确且检验