2009-10-09 16:13
2009-01-09 00:45
blog访问量竟然过了两万。
不想再让无关紧要的人不着痕迹地看我写的乱七八糟的东西了。从现在开始，我的日志都会设置权限，仅限好友访问。所以，请要看我blog内容的朋友们申请一个baidu帐号并加我好友。当然不想看的人没必要这样做。
那么，如果你打开我的主页，第一篇日志是这篇，那么必然的是，你忘记登陆了。  |
2008-07-23 15:33
菜菜菜菜菜菜菜(631695609) 15:28:55
第33届ACM/ICPC亚洲区预选赛(杭州赛区)_网络选拔赛(10月18日)
第33届ACM/ICPC亚洲区预选赛(成都赛区)_网络选拔赛(10月19日)
菜菜菜菜菜菜菜(631695609) 15:29:29
哈尔滨赛区 9月20日 10月11日
北京赛区 9月27日 10月25日
杭州赛区 10月18日 11月22日
成都赛区 10月19日 11月29日
合肥赛区 9月28日 11月15日 |
2008-07-23 11:05
我是个懒人，就直接copy聊天记录了，呵呵
思路是：
用0表示没放，1表示放了。横放则左右两格都是1，竖放则上格是0，下格是1。
这种记录state的方法决定了：如果上下两行的state是确定的，那么放法唯一。
Fun（state，n）表示n这行的状态是state的时候有多少种放法。
那么我们要求的就是Fun（2^m-1,n）.
Fun（state，n）就等于sigma Fun（last，n-1），last取遍所有可以取到的状态。
限制last取值的因素有两个：
1、state中是0的位置，last中一定是1，否则出现没填满的情况。
2、把state和last取&，也就是last是0的位，state也变0，看有没有影响到state，让它出现单1不能横放。
结束条件是n==1,且state能横放。
还有一个要注意的问题就是结果要用64位整型保存。
#include <cstdio>
const int large = 1<<11;
int m,n;
__int64 result[12][12];
__int64 dp[large][12];
int power;
__int64 Fun( const int state, const int n )
{
if ( n == 1 )
{
int flag = 1;
for ( int i = 0; i < power; ++i )
{
if ( (state&(1<<i)) == 0 )continue;
if ( i+1 == m )
{
flag = 0;
break;
}
if ( (state&(1<<(i+1))) == 0 )
{
flag = 0;
break;
}
++i;
}
if ( flag ) return 1; //若能横放
return 0;
}
int last = ~state;//last是last状态1起码的状态
last &= ( (1<<m) -1 );//我一开始忘记了加这一句，last全都是负的，哈哈
__int64 s = 0;
if ( dp[state][n] != -1 ) return dp[state][n];
for ( int i = 0; i < power; ++i )
{
int flag = 1;
int tmp = state&i;
if ( (i&last) != last ) continue; //last限制因素1
for ( int j = 0; j < m; ++j )//last限制因素2
{
if ( (tmp&(1<<j)) == 0 ) continue;
if ( j+1 == m )
{
flag = 0;
break;
}
if ( (tmp&(1<<(j+1))) == 0 )
{
flag = 0;
break;
}
++j;
}
if ( flag ) s+= Fun( i, n-1 );
}
dp[state][n] = s;
return s;
}
int main()
{
while ( scanf( "%d%d", &m, &n ), !( m == 0 && n == 0 ) )
{
int s = 0;
if ( (m*n)%2 ) //面积
{
puts( "0" );
continue;
}
if ( m > n ) //使n大m小
{
int tmp = m;
m = n;
n = tmp;
}
if ( result[n][m] != 0 ) //算过就不要再算了
{
printf( "%I64d\n", result[n][m] );
continue;
}
power = 1<<m;
//初始化
for ( int i = 0; i < large; ++i )
{
for ( int j = 0; j <= n; ++j )
{
dp[i][j] = -1;
}
}
result[n][m] = Fun( power-1, n ); //最后一行放满
printf( "%I64d\n", result[n][m] );
}
return 0;
} |
2008-07-20 11:52
POJ 2411 Mondriaan's Dream 解题报告
（原文链接http://hi.baidu.com/newmyl/blog/item/b1d3c609fd6009206b60fbb1.html）
这题的DFS+DP解法：
当高度和宽度都为奇数时显然答案为0, 这个用面积的奇偶性就很容易得证记f[i][s1]为第i-1行全满且第i行状态为s1时的种数，便有如下递推关系:
f[i][s1] = sigma(f[i-1][s2]);
其中(s1, s2)整体作为一个放置方案， 这样f[h+1][0]即是答案了
对于每一个位置，我们有三种放置方法：
1. 竖直放置
2. 水平放置
3. 不放置
d为当前列号 ，初始化d, s1, s2都为0;对应以上三种放置方法，s1, s2的调整为:
1. d = d + 1, s1 << 1 | 1, s2 << 1;
2. d = d + 2, s1 << 2 | 3, s2 << 2 | 3;
3. d = d + 1, s1 << 1, s2 << 1 | 1;
先就第一种情况解释一下，另外的两种情况可以类推
S1<<1|1即为把s1的二进制表示后面加上一个1，对就于本题来说就是(d+1)列上放置，s2<<1即为把s2的二进制表示后面加上一个0，对于本题来说就是(d+1)列上不放置。
但为什么s1、s2会如此变化呢？s1对应于本行的状态，s2对应于上一行的状态，能竖直放置意味着上一行的(d+1)列是空着的，因此此时上一行的状态为s2<<1，同时竖置放置了之后，则本行(d+1)行放置了东西，状态于是变为s1<<1|1;
当d == w时保存状态
对于初始时的f值，可以假设第0行全满，第一行只有两种放法:
1. 水平放置 d = d + 2, s << 2 | 3;
2. 不放置 d = d + 1, s << 1;
另外，利用滚动数组，可以减少空间的开销
还有一个可以提高较率的地方，当输入的 w > h 时，对调，因为横向的运算是指数
级的， 而列向的是线性的.
附代码：
# include <stdio.h>
# include <string.h>
__int64 a[2][3000];
int t,n,m;
void dfs(int d,int mm) //d表示列数，mm表示状态
{
if(d==m)
{
a[0][mm]++;
return;
}
if(d+1<=m)
dfs(d+1,mm<<1);
if(d+2<=m)
dfs(d+2,mm<<2|3);
}
void DFS(int d,int mm,int nn)//mm对应于上一行状态，nn对应于下一行状态
{
if(d==m) //若全部的列都确定状态，就把此状态的放法数加到nn状态里
{
a[t][nn]+=a[(t+1)%2][mm];
return;
}
if(d+1<=m) //如上所说
{
DFS(d+1,mm<<1,nn<<1|1);
DFS(d+1,mm<<1|1,nn<<1);
}
if(d+2<=m)
DFS(d+2,mm<<2|3,nn<<2|3);
}
int main()
{
int i;
while(scanf("%d%d",&n,&m)&&n&&m)
{
if((n*m)%2) //根据面积
{
printf("0\n");
continue;
}
if(n>m)
n^=m,m^=n,n^=m; //交换
memset(a,0,sizeof(a));
dfs(0,0);//初始化第一行
for(i=2;i<=n;i++)
{
t=(i+1)%2; //滚动数组的第一个下标计算
DFS(0,0,0);
memset(a[(t+1)%2],0,sizeof(a[0]));//清空另一行
}
printf("%I64d\n",a[(n+1)%2][(1<<m)-1]); //输出最后一行全部放满的结果。
}
return 0;
}
别附打表代码：
# include <stdio.h>
__int64 a[11][11]={0,1,0,1,0,1,0,1,0,1,0,1,2,3,5,8,13,21,34,55,89,144,0,3,0,11,0,41,0,153,0,571,0,1,5,11,36,95,281,781,2245,6336,18061,51205,0,8,0,95,0,1183,0,14824,0,185921,0,1,13,41,281,1183,6728,31529,167089,817991,4213133,21001799,0,21,0,781,0,31529,0,1292697,0,53175517,0,1,34,153,2245,14824,167089,1292697,12988816,108435745,1031151241,8940739824,0,55,0,6336,0,817991,0,108435745,0,14479521761,0,1,89,571,18061,185921,4213133,53175517,1031151241,14479521761,258584046368,3852472573499,0,144,0,51205,0,21001799,0,8940739824,0,3852472573499,0};
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)&&n&&m)
printf("%I64d\n",a[n-1][m-1]);
return 0;
} |
2008-06-01 19:44
// Problem zju2451
// DP with Segment Tree
#include <stdio.h>
#define MAX 50000
int Len;
struct TNode {
int left , right;
int minstep;
TNode *LeftChild , *RightChild;
void Construct ( int , int );
void Insert ( int , int );
int GetRank ( int , int );
} STree [MAX * 2 + 2] , *Root = &STree [0];
int N , M;
void TNode :: Construct ( int l , int r )
{
left = l; right = r; minstep = 999999;
if ( l == r ) { LeftChild = NULL; RightChild = NULL; return; }
int mid = ( l + r ) >> 1;
LeftChild = &STree [Len ++];
RightChild = &STree [Len ++];
LeftChild->Construct ( l , mid );
RightChild->Construct( mid + 1 , r );
}
void TNode :: Insert ( int p , int x )
{
if ( x < minstep ) minstep = x;
if ( left == right ) return;
if ( p <= ( left + right ) >> 1 ) LeftChild->Insert( p , x );
else RightChild->Insert( p , x );
}
int TNode :: GetRank ( int l , int r )
{
if ( l == left && r == right ) return minstep;
int mid = ( left + right ) >> 1;
if ( r <= mid ) return LeftChild->GetRank( l , r );
if ( l > mid ) return RightChild->GetRank( l , r );
int ret1 , ret2;
ret1 = LeftChild->GetRank( l , mid );
ret2 = RightChild->GetRank( mid + 1 , r );
return ret1 < ret2 ? ret1 : ret2;
}
main ()
{
int i , a , b , p;
while ( scanf ( "%d %d" , &N , &M ) != EOF ) {
Len = 1; Root->Construct( 1 , N );
Root->Insert ( 1 , 0 );
for ( i = 0; i < M; i ++ ) {
scanf ( "%d%d" , &a , &b );
if ( a < b ) {
p = Root->GetRank ( a , b - 1 );
Root->Insert ( b , p + 1 );
}
}
printf ( "%d\n" , Root->GetRank( N , N ) );
}
}
// PKU 2104
// Segment Tree && Binnary Search
#include <stdio.h>
#define MAX 100000
int len;
struct TNode {
int left , right;
char depth;
TNode *LeftChild , *RightChild;
void construct ( int , int , int );
int GetRank ();
} Node [2 * MAX + 2];
int SortArray [18] [MAX + 2];
int Key , ls , rs;
void TNode :: construct ( int l , int r , int dep )
{
left = l; right = r; depth = dep;
if ( left == right ) {
scanf ( "%d" , &SortArray [dep] [l] );
return;
}
int mid = ( l + r ) >> 1;
LeftChild = &Node [len ++];
LeftChild->construct( l , mid , dep + 1 );
RightChild = &Node [len ++];
RightChild->construct( mid + 1 , right , dep + 1 );
int i = left , j = mid + 1 , k = left;
while ( i <= mid && j <= r ) {
if ( SortArray [dep + 1] [i] < SortArray [dep + 1] [j] )
SortArray [dep] [k ++] = SortArray [dep + 1] [i ++];
else
SortArray [dep] [k ++] = SortArray [dep + 1] [j ++];
}
while ( i <= mid ) SortArray [dep] [k ++] = SortArray [dep + 1] [i ++];
while ( j <= right ) SortArray [dep] [k ++] = SortArray [dep + 1] [j ++];
}
int TNode :: GetRank ()
{
if ( ls <= left && right <= rs ) {
if ( SortArray [depth] [left] >= Key ) return 0;
if ( SortArray [depth] [right] < Key ) return right - left + 1;
if ( SortArray [depth] [right] == Key ) return right - left;
int low = left , high = right , mid;
while ( low + 1 < high ) {
mid = ( low + high ) >> 1;
if ( SortArray [depth] [mid] < Key ) low = mid;
else high = mid;
}
return low - left + 1;
}
int ret = 0;
if ( ls <= LeftChild->right ) ret += LeftChild->GetRank();
if ( RightChild->left <= rs ) ret += RightChild->GetRank();
return ret;
}
main ()
{
int N , Q , i;
int low , high , mid , Index;
scanf ( "%d%d" , &N , &Q );
len = 1; Node [0].construct( 0 , N - 1 , 0 );
for ( i = 0; i < Q; i ++ ) {
scanf ( "%d%d%d" , &ls , &rs , &Index );
ls --; rs --;
low = 0; high = N;
while ( low + 1 < high ) {
mid = ( low + high ) >> 1;
Key = SortArray [0] [mid];
if ( Node [0].GetRank() >= Index ) high = mid;
else low = mid;
}
printf ( "%d\n" , SortArray [0] [low] );
}
}
|
2008-06-01 19:44
// problem zju 1610
// Segment Tree
#define NoColor -1
#define MulColor -2
#include <stdio.h>
#include <string.h>
int Len;
struct TNode {
int left , right;
int col;
TNode *LeftChild , *RightChild;
void Construct ( int , int );
void Insert ( int , int , int );
void Calculate ();
} Tree [16000] , *Root = &Tree [0];
int CalColor [8001] , Many [8001];
void TNode :: Construct ( int l , int r )
{
left = l; right = r;
if ( l + 1 == r ) { LeftChild = NULL; RightChild = NULL; return; }
int mid = ( l + r ) >> 1;
LeftChild = &Tree [Len ++];
RightChild = &Tree [Len ++];
LeftChild->Construct( l , mid );
RightChild->Construct( mid , r );
}
void TNode :: Insert ( int l , int r , int c )
{
if ( col == c ) return;
if ( l == left && r == right ) { col = c; return; }
int mid = ( left + right ) >> 1;
if ( col != MulColor ) { LeftChild -> col = col; RightChild -> col = col; }
col = MulColor;
if ( r <= mid ) { LeftChild -> Insert ( l , r , c ); return; }
if ( l >= mid ) { RightChild -> Insert ( l , r , c ); return; }
LeftChild -> Insert ( l , mid , c );
RightChild -> Insert ( mid , r , c );
}
void TNode :: Calculate ()
{
if ( col != MulColor && col != NoColor ) {
int i;
for ( i = left; i < right; i ++ ) CalColor [i] = col;
}
if ( col == MulColor ) { LeftChild -> Calculate (); RightChild -> Calculate (); }
}
main ()
{
int Total , a , b , c , i , t;
Len = 1; Tree [0].Construct( 0 , 8000 );
// printf ( "After Construct the Tree , Len = %d\n" , Len );
while ( scanf ( "%d" , &Total ) != EOF ) {
Tree [0].col = NoColor;
while ( Total ) {
scanf ( "%d %d %d" , &a , &b , &c );
Root -> Insert( a , b , c );
Total --;
}
memset ( CalColor , 0xff , sizeof ( CalColor ) );
memset ( Many , 0 , sizeof ( Many ));
Root -> Calculate ();
t = -1;
for ( i = 0; i <= 8000; i ++ ) {
if ( CalColor [i] == t ) continue;
t = CalColor [i];
if ( t != -1 ) Many [t] ++;
}
for ( i = 0; i <= 8000; i ++ ) if ( Many [i] )
printf ( "%d %d\n" , i , Many [i] );
printf ( "\n" );
}
}
|
2008-06-01 19:43
从简单说起，线段树其实可以理解成一种特殊的二叉树。但是这种二叉树较为平衡，和静态二叉树一样，都是提前已经建立好的树形结构。针对性强，所以效率要高。这里又想到了一句题外话：动态和静态的差别。动态结构较为灵活，但是速度较慢；静态结构节省内存，速度较快。
接着回到线段树上来，线段树是建立在线段的基础上，每个结点都代表了一条线段[a , b]。长度为1的线段成为元线段。非元线段都有两个子结点，左结点代表的线段为[a , (a + b ) / 2]，右结点代表的线段为[( a + b ) / 2 , b]。
图一就是一棵长度范围为[1 , 10]的线段树。
长度范围为[1 , L] 的一棵线段树的深度为log ( L - 1 ) + 1。这个显然，而且存储一棵线段树的空间复杂度为O（L）。
线段树支持最基本的操作为插入和删除一条线段。下面已插入为例，详细叙述，删除类似。
将一条线段[a , b] 插入到代表线段[l , r]的结点p中，如果p不是元线段，那么令mid＝（l＋r）/2。如果a<mid，那么将线段[a , b] 也插入到p的左儿子结点中，如果b>mid，那么将线段[a , b] 也插入到p的右儿子结点中。
插入（删除）操作的时间复杂度为O （ Log n ）。
上面的都是些基本的线段树结构，但只有这些并不能做什么，就好比一个程序有输入没输出，根本没有任何用处。
最简单的应用就是记录线段有否被覆盖，并随时查询当前被覆盖线段的总长度。那么此时可以在结点结构中加入一个变量int count；代表当前结点代表的子树中被覆盖的线段长度和。这样就要在插入（删除）当中维护这个count值，于是当前的覆盖总值就是根节点的count值了。
另外也可以将count换成bool cover；支持查找一个结点或线段是否被覆盖。
例题1（ZJU1610 Count The Colors 线段树基本应用题目）
给出在线段[0,8000]上的若干次涂色，问最后能看见哪些颜色，并统计能看到多少段。
解析
就这个题目而言，方法很多，而且数据范围不大，但我们由线段树的角度来解决这个问题。
建立一棵代表线段[0,8000]的线段树，涂色操作就是将[a , b]涂成颜色c。最后做统计。
结构如下：
struct TNode {
int left , right;
int col;
TNode *LeftChild , *RightChild;
};
col 有几种情况，如果col为－1，代表了尚未涂色，－2代表了是混和色，就是说这条线段并不是单一的颜色。其他情况，便是这条线段都是这个颜色的了。
全部程序见附录1。
线段树的第一种变化
基本的线段树代表的是线段，如果我们把线段离散成点来看，那么线段树可以变化成一种离散类型线段树。
这里可以有两种理解。一种离散关系可以是连续的线段的点，比方说在一条直线上放置的连续小球的着色问题；另一种则是完全将线段离散化分成若干小段，对每一段小段做为元线段来建立线段树，这种线段树可以支持实数划分类型的线段。
例题2（ZJU2451 Minimizing maximizer ）
Andy想要得到一组数中的最大值。会有一系列的操作Sorter(i[1], j[1]), ..., Sorter(i[k], j[k])。作用是将数组中的第i[k]个数字到第j[k]个数字排序。按照输入给出的顺序，你可以选择要不要执行这个操作。问题是最少需要多少步操作，可以求出这个最大值。题目保证可以求出。
多组数据。
第一行为两个数字N，M。表示N个数，M个操作。
接下来M行，每行描述一个操作i[k] , j [k]。
对于每组数据，输出最少需要多少次操作分离得到最大值。
每组数据一行。
解析
由于要将最大的数字分离到最后的一位，如果我们考虑将数组看成一条[1,n]的线段，而每项操作也看成是从[i[k],j[k]]的线段，那么就是要求按照输入的顺序，将线段[1,n]从左到右依次覆盖掉，问题变成求最小的覆盖线段总数。
考虑最基本的规划方法，用Opt [k] 表示覆盖掉 [1,k]的线段最少需要的步数，那么状态转移方程为：
Opt [k] = min { Opt [d] + 1 | j [p] = k && d >= i [p] && d <= j [p] && k > 1 }
Opt [1] = 0;
最后的答案就是Opt [n]了，但是考虑时间复杂度，是O（m^2）级别的，m最大为500000，超时无疑。但是这里我们看到了规划的决策集合是一条连续的线段，是要在这条线段上面取得最小值，那么线段树的结构就正好适合在这里应用了。
由于这里最小的单位是一个点，所以我们采取线段树的第一种变化，把元线段设置为单位点，即[k,k]。在规划的时候维护线段树即可。
线段树结点结构中，需要加入的元素是int minstep 代表最少需要用到的覆盖线段数目可以覆盖到当前结点所代表的线段中。
全部程序见附录2。
例题3（PKU2104K-th Number）
给出一个大小为n的数组A[]，给出m个问题（1 <= n <= 100 000, 1 <= m <= 5 000）。问题格式为Q（i，j，k），询问从A[i]到A[j]第k大的元素是什么。A[]中的数各不相同。
解析
由于仍旧是离散的整数问题，我们依旧采取第一种变化。看到题目，最基本的想法就是排序然后求第k个数了，但是时限上不能满足要求。
线段树的最强大方面就是将一组数（一条线段）放到一起处理。每层树需要的线段数目不会超过4，而深度为logn，所以最后操作的复杂度会是O(logn)。
但是仅仅应用线段树还是不够的，即使我们知道了需要处理的线段是那些，但是由于线段过多，也无法准确求出第k个元素究竟是什么。这里二分策略就派上了用场。我们用二分枚举第k个数字P，然后再在所要的线段中找到枚举的P所在的位置，同样是用二分的策略。所以复杂度是O(mlognlognlogn)。
我们在找P所在的位置的时候需要用到二分策略，也就是说，我们需要将线段所代表的结点排序，这里可以将每一层的所有数放到一起，统一成一个数组SortArray[depth][]。其实也可以理解成将归并排序的每个步骤记录下来。
全部程序见附录3。
线段树的第二种变化 （树状数组）
在结构上对线段树进行改变，可以得到线段树的另一种变化。
用O（n）的一维数组构造出线段树，无其他附加空间。比方说，一棵从[0,L]的线段树表示为TNode Tree[L];
这里应用二进制将树进行划分。将整数R的二进制表示中的最后一个1换成0，得到数L。Tree[R]代表的线段就是[L,R]。例如：6的二进制表示为（110）2将最后一个1换成0即为（100）2＝4，所以Tree[6]代表的线段就是[4,6]。
析出数R的最后一位1的方法是：LowBit（R）＝R^~R。
包含点L的一系列数为x1,x2,……，这里x1=R，x2=x1+LowBit (x1)，x3=x2+LowBit(x2)，……
这种线段树的优点在于：
1． 节省空间。完全线段长度的空间，无需左右指针，无需左右范围。
2． 线段树查找严格log(R)，因为二进制的每位查找一遍。
3． 状态转移快，操作简单。
4． 扩展到多维较为容易。
缺点：
1．随意表示线段[a,b]较为困难。
这种线段树适用于：
1． 查找线段[0,L]的信息。
2． 求线段[a,b]的和（应用部分和做差技术）。
|
2008-05-26 12:59
http://www.it.sytu.edu.cn/xxftw/onews.asp?id=208
虽然很扯。。。 |
2008-05-15 13:59
/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
/*
* main.c
* Copyright (C) wtthappy 2008 <wtthappy@hotmail.com>
*
* main.cpp is free software.
*
* You may redistribute it and/or modify it under the terms of the
* GNU General Public License, as published by the Free Software
* Foundation; either version 2 of the License, or (at your option)
* any later version.
*
* main.cpp is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with main.cpp. If not, write to:
* The Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor
* Boston, MA 02110-1301, USA.
*/
#include <iostream>
#include <cstdio>
int main()
{
int t;
int ttt = 0;
scanf( "%d", &t );
while ( t-- )
{
int m,n;
int tt = 0;
if( ttt++ != 0)
putchar( '\n');
while (scanf( "%d%d",&n, &m ) && !( n == 0 && m == 0 ))
{
int answer = 0;
for ( int i = 1; i < n; ++i )
{
for ( int j = i+1; j < n ; ++j )
{
if ( (i*i+j*j+m)%(i*j) == 0 )
{
++answer;
}
}
}
printf( "Case %d: %d\n", ++tt, answer );
}
}
return 0;
}
|
|
|
|
