A题
我是for循环暴力作的，题解里最牛逼的做法是O(1)：
O(1) solution - one may derive it from the previous approach: since x+c = d1 => 2*x + r1 - c1 = d1 => x = (d1+c1-r1)/2
So, you find x, check that it is in [0..9], restore all other numbers as in the previous approach and check that all conditions are met.
B题
简单模拟，注意科学计数 12,345,678.9里面逗号的位置，应该是 ( length - current_pos ) % 3 ==0处打逗号;
C题
给定一个数n表示(A - 1) × (B - 2) × (C - 2) ，要求A*B*C的最大值和最小值。n<=
10^9;
很值得说的一个题，对n<= 10^9，两层for循环x*y*c作为n的3哥因子拆分，保证x<=y<=z,复杂度是 O(
1000*1000 );
注意一个情况就是枚举的x,y,z后来变成(A - 1) × (B - 2) × (C - 2)形式应该是有三种情况。
/*Jan 13, 2012 4:15:42 PM yimao C-Help Farmer GNU C++ Accepted 50ms 1400KB*/
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define MM(a,b) memset(a,b,sizeof(a));
typedef unsigned long long u64;
typedef long long lld;
#define maxn
lld mmax,mmin,n;
void up_max(lld &x,lld y){if(x==-1||x<y)x=y;}
void up_min(lld &x,lld y){if(x==-1||x>y)x=y;}
void work(lld a,lld b,lld c){
lld t= a*b*c-n;
up_max( mmax, t );
up_min( mmin, t );
}
int main()
{
lld x,y,z;
while(cin>>n){
mmax=-1, mmin= -1;
for(x=1;x<1001;++x){
if(n%x==0){
lld k= n/x;
for(y=x;y*y<=k;++y){
if( k%y==0 ){
lld z= k/y;
// n= x*y*z= (A-1)*(B-2)*(C-2);
work( x+1, y+2, z+2 );
work( y+1, x+2, z+2 );
work( z+1, x+2, y+2 );
}
}
}
}
cout<<mmin<<" "<<mmax<<endl;
}
}
D题
这个题完全不会。
在n*m棋盘上放棋子，要求棋子之间的平方距离不得为5。
下面有个别人写的题解：
提示说这个是骑士巡游的二分图。
我感觉可以这么想。把所有格子看做节点，所有的不能共存的点之间有一条边。
我们的目标就是删掉最少的节点，使这个图中没有连通边。
这明显就是骑士巡游二分图的特点，奇数步与偶数步是不相交的，所以很明显，答案是(m*n+1)>>1
对于小数据需要加特判
E题
n*m(1<=n,m<=9)的棋盘，要求放置T字型，每个T字型是占5个格子，如下4种：
/* ### ..# .#. #..
.#. ### .#. ###
.#. ..# ### #..
*/
问最多可以放多少个，并输出方案，并且不同的T之间用A，B，C...字母区别。
难题，太难不会，直接贴代码。
/*Jan26,2012 1:52:19 PM yimao E-Help Caretaker GNU C++ Accepted 220ms 1400KB*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
#define MM(a,b) memset(a,b,sizeof(a));
typedef unsigned long long u64;
typedef long long lld;
#define maxn 9
/* ### ..# .#. #..
.#. ### .#. ###
.#. ..# ### #..
*/
//choose a point(upper left),then make position of other points follow:
const int shape[4][4][2]= {
{ {0,1},{0,2},{1,1},{2,1} },
{ {1,0},{2,0},{1,-1},{1,-2} },
{ {1,0},{2,0},{2,-1},{2,1} },
{ {1,0},{2,0},{1,1},{1,2} },
};
int m,n; //n row, m column;
struct node{
char g[maxn][maxn];
int num,sx,sy;
node(){
sx=sy=0;
MM(g,0);
num=0;
}
void printNode(){
for(int i=0;i<n;++i){
for(int j=0;j<m;++j)
printf("%c",g[i][j]?g[i][j]:'.');
puts("");
}
}
};
stack<node>q;
int ans;
node ansNode;
void bfs(){
while(1){
The_end_where_I_begin:
if( q.empty() ) break;
node now= q.top();
q.pop();
if( now.num>ans ){
ans= now.num;
ansNode= now;
}
now.num++;
char ch= 'A'+now.num-1;
bool flag= 1;
int i,j,k,l;
for(i=0;i<n;++i){
int in=0;
for(j=0;j<m;++j){
if( !now.g[i][j] ){
flag= 1;
for(k=3;k>=0;--k){
flag= 1;
for(l=0;l<4;++l){
int tx= j+ shape[k][l][1];
int ty= i+ shape[k][l][0];
if( tx<0 || tx>=m || ty<0 ||ty>=n || now.g[ty][tx] ){
flag=0;
break;
}
}
if( flag ){
in++;
node tNode= now;
tNode.g[i][j]= ch;
for(l=0;l<4;++l){
int tx= j+ shape[k][l][1];
int ty= i+ shape[k][l][0];
tNode.g[ty][tx]= ch;
}
tNode.sx= j+1, tNode.sy= i;
q.push( tNode );
}
}
if( in>1 ) goto The_end_where_I_begin;
}
}
}
}
}
int main()
{
//freopen("E.txt","r",stdin);
ans= -1;
while(cin>>n>>m){
while(!q.empty()) q.pop();
q.push( node() );
bfs();
printf("%d\n", ans);
ansNode.printNode();
}
}