摘要: 2010 East Central Regional Contest声明：本博菜，只做水，未给出程序的题目待补充。
题目网址：http://acm.ashland.edu/
【Problem A】 Cut It Out!【Problem B】 Flip It 简单的模拟题。 把一个卡片矩阵通过四种操作翻成一叠...
阅读全文
摘要: 声明：本博菜，只做水。题目网址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3416比赛网址：http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=319【Problem C】 水题，直接按题目意思写即可。
Code highli...
阅读全文
摘要: 【练习一】http://acm.hdu.edu.cn/showproblem.php?pid=3622这题是2010天津网络赛试题。二分答案，将圆看做一个点，当两个圆a,b的距离小于给定距离d时，说明a,b互斥，连边<a , ~b> ，<~b , a> 。二分+ 2_SAT 。 这确实是个好思路。
Code highlighting pr...
阅读全文
摘要:
Southeastern European Regional Programming Co...
阅读全文
摘要:
其实早有Beyond The Void 大牛做了解题报告，非常犀利，Orz !网址：http://www.byvoid.com/blog/lpf24-solution/ 我从头做了一遍， 感觉受益匪浅。贴出自己代码，仅供参考。思路可参考Beyond牛。好不容易找到了两个可提交的网站：南开大学<可惜只有几个题>http://acm.nankai.edu.cn/p...
阅读全文
摘要: POJ 1950 Dessert 比较简单，但是要细心。 这道题关键注意运算一个给定的表达式。我的是用两个栈实现，一个数字栈，一个操作符栈。 其次，题目规模<=15，所以可以全体打表。也可以将结果个数打表，表达式搜索，当搜出结果超过20时，马上退出。
参考程序：
Co...
阅读全文
摘要: 题目描述： 一个规模为 W*H 的长方形 ， 其中 W*H＝40； 然后游戏依次随机生成10个块，这10个块为以下之一： 题目特别限制：不能使后面方块的某个格子在前面方块...
阅读全文
题目描述：
给出一个 h*w 的空棋盘，1<=h,w<=11，若用1*2或2*1的骨牌去完全覆盖这个棋盘，问有多少种方法？
题目分析：
规模很小，棋盘的每个格子有覆盖和未覆盖两种，正好对应二进制中的 1 和 0 。所以可以用一个二进制数表示一行棋盘的状态，这称之为状态压缩，然后对其进行相应的位运算，表示相应的操作。
首先，我们明确一下状态的在该题的意义： 若当前格被一个1*2的骨牌盖住，或者被一个2*1的骨牌下面格盖住，则为 1 ；否则为0 。
有了状态，我们就可以得出一些结论：
1.当前行的状态只与上一行有关；
2.若上行某个为0，则下行相应格必须为1；若上行某格为1，则下行相应格可为 0 或1；
这样我们就可以有上一行的状态，递推出下一行的状态了。我们可以先求出所有的用1*2骨牌填一列的状态集M。然后，用每一个状态A去与上行状态判断，若有矛盾，则证明当前行不能为A；否则，A状态的方法数可由上行得出。
用一个方程表示： F[ row , i ] = sum ( f[row - 1 , j ] ) , j表示上行状态，i表示与j无矛盾的状态。
参考程序：
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef __int64 i64;
const int maxn = 1<<12;
const int maxl = 150;
int status , als , n ,h ;
int all[maxl] ; //所有的1*2骨牌填一行的状态，二进制表示
i64 f[maxn] , s[maxn]; // 滚动数组
inline void put(int &bd ,int i) // 覆盖格子
{
if(!( bd & (1<<i) )) bd += 1<<i;
}
inline void clr(int &bd ,int i) //清空格子
{
if( bd & (1<<i) ) bd -= 1<<i;
}
void dfs(int i) //先搜索出用1*2骨牌去填一行，未填为0
{
if(i >= n - 1 )
{
all[als ++ ] = status;
return ;
}
dfs(i + 1);
put(status , i); put(status , i + 1 );
dfs(i + 2);
clr(status , i); clr(status , i + 1 );
}
i64 dp()
{
int i , j , row , son , t , c;
status = als = 0 ; dfs(0) ;
memset(f , 0 ,sizeof(f));
for(i = 0 ; i<als ; ++i) f[ all[i] ] = 1 ; //初始首行
for(row = 1 ; row < h; ++ row)
{
memset(s , 0 , sizeof(s));
for(i = 0 ; i< (1<<n) ; ++i)
if( f[i] != 0 )
{
c = i ^( (1<<n) - 1 ) ; // 对i的后n为取反
for( j = 0 ; j< als ; ++j) // 试探每个状态
if( !( all[j] & c ) ) // 表示无矛盾
{
t = c + all[j] ; // t 为新状态
s[ t ] += f[i]; // 方法数累加
}
}
for(i = 0 ; i< (1<<n) ; ++i)
f[i] = s[i] ;
}
return f[( 1<<n )- 1];
}
int main()
{
while(scanf("%d%d",&h , &n )!=EOF && ( h || n))
printf("%I64d\n",dp());
return 0;
}
摘要: 题目描述：在一个 8 * 8 的棋盘上，有四个棋子，每颗棋子可在上，下，左，右，四个方向进行四种操作,四种操作是一下的某一种： 1. 若相邻格有棋子，则可像跳棋一样，跳过去，到达对称的一格。 2.若相邻格为空，则可直接移过去。 问能否从一种状态在8步之内变成另一种状态？题目分析： &...
阅读全文
POJ 2186
题目描述：给定一个有向图，求满足下列条件的点V的个数：其他点均能沿着有向边到达V。
首先，将图的极大强联通分量缩成一个点，这是因为只要该联通分量某一点满足上述条件，则整个联通分量满足条件。
然后，明确的一点是，缩点后的图必无环，否则，可将环上所有点也缩成一个点，与极大强联通分量矛盾。
最后，只要找到缩点后的图中无出度的点的个数，设为cnt, 若 cnt > 1 , 则必无满足条件的点，因为一个出度为
零的点无法到达另一个出度为零的点；若cnt = 1 , 则该点所对应的强联通分量的点的个数即为答案。
参考程序：
#include<iostream>
using namespace std;
const int maxn = 10005;
const int maxe = 50005;
struct node
{
int v,next;
};
node e[maxe];
int es, E , N ;
int gh[maxn];
void ins(int vs, int vt )
{
e[es].v = vt , e[es].next=gh[vs] , gh[vs] = es ++ ;
}
int stack[maxn] , instack[maxn] ,low[maxn] ,dfn[maxn] , idx[maxn] , out[maxn] , ok[maxn] ;
int cnt ,top , pnt ;
void tarjan( int v)
{
int i,j,k , w , u;
dfn[v] = low[v] = ++ cnt ;
stack[++top] = v; instack[v] = 1;
for( i = gh[v] ; i!=-1 ; i = e[i].next)
{
w = e[i].v ;
if(!dfn[w])
{
tarjan(w);
low[v] = min(low[w], low[v]);
}
else
if(instack[w]) low[v] = min(low[v] , dfn[w]);
}
if( dfn[v] == low[v])
{
++ pnt ;
do { u = stack[top -- ] ; instack[u] = 0 ; idx[u] = pnt ; ok[pnt] ++ ;
} while( u!=v);
}
}
int can()
{
int i,j,k;
cnt = top = pnt = 0 ;
memset(dfn , 0 , sizeof(dfn));
memset(ok ,0 , sizeof(ok));
for( i = 1 ; i<=N ; ++i)
if( !dfn[i] ) tarjan(i);
if(pnt == 1) return N ;
memset(out, 0 , sizeof(out));
for( i = 1 ; i<=N ; ++i )
for( j = gh[i] ;j!=-1 ;j=e[j].next)
if( idx[ e[j].v ] != idx[i] ) out[ idx[i] ] ++ ;
int ret , num = 0 ;
for(i = 1 ;i<=pnt ; ++i)
if( !out[i] ) { num ++ ; ret = i ;}
if(num == 0) return N ;
if(num > 1) return 0 ;
return ok[ret];
}
int main()
{
int i,vs,vt;
scanf("%d%d",&N,&E);
es = 0 ;
memset(gh , -1, sizeof(gh));
for(i = 0 ; i<E ; ++i)
{
scanf("%d%d",&vs,&vt);
ins(vs,vt);
}
cout<<can()<<endl;
return 0;
}