久久久久国产精品人妻,一本久久a久久精品综合香蕉,日本免费久久久久久久网站

Mon, 16 Nov 2009 11:45:00 GMT

notonlysuccess

�q�个博客不用了，一些还好的资料�?x��)慢慢搬到新博�?br>谢谢朋友们��l�关�?br>

shǎ�?/a> 2009-11-16 19:45 发表评论

旉��一��时

Thu, 10 Sep 2009 07:13:00 GMT

Elevator
http://acm.hdu.edu.cn/showproblem.php?pid=2494

Elevator Simulation
http://acm.hdu.edu.cn/showproblem.php?pid=1386

Tetris
http://acm.hdu.edu.cn/showproblem.php?pid=3013

Gates of Logic
http://acm.hdu.edu.cn/showproblem.php?pid=1886

Teacher YYF
http://acm.pku.edu.cn/JudgeOnline/problem?id=3746

中国象棋II
http://acm.fzu.edu.cn/problem.php?pid=1694

Typesetting
http://acm.hdu.edu.cn/showproblem.php?pid=2718

Connect
http://acm.hdu.edu.cn/showproblem.php?pid=2727

Hex Tile Equations
http://acm.hdu.edu.cn/showproblem.php?pid=2702

HTML Wrapper
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4083

shǎ�?/a> 2009-09-10 15:13 发表评论

Asia Regional Contest

Wed, 19 Aug 2009 05:35:00 GMT

暂无

shǎ�?/a> 2009-08-19 13:35 发表评论

PKU——DP专辑

Wed, 29 Jul 2009 07:18:00 GMT

1037 A decorative fence
1042 Gone Fishing
1062 昂贵的聘�C?br>1074 Parallel Expectations
1093 Formatting Text
1112 Team Them Up!
1143 Number Game
1160 Post Office
1178 Camelot
1179 Polygon
1180 Batch Scheduling
1187 陨石的秘�?br>1189 钉子和小�?br>1191 ��盘分割
1192 最优连通子�?br>1208 The Blocks Problem
1239 Increasing Sequences
1240 Pre-Post-erous!
1293 Duty Free Shop
1322 Chocolate
1390 Blocks
1414 Life Line
1432 Decoding Morse Sequences
1475 Pushing Boxes
1485 Fast Food
1505 Copying Books
1513 Scheduling Lectures
1609 Tiling Up Blocks
1633 Gladiators
1635 Subway tree systems
1636 Prison rearrangement
1644 To Bet or Not To Bet
1649 Market Place
1655 Balancing Act
1661 Help Jimmy
1664 放苹�?br>1671 Rhyme Schemes
1682 Clans on the Three Gorges
1690 (Your)((Term)((Project)))
1692 Crossed Matchings
1695 Magazine Delivery
1699 Best Sequence
1704 Georgia and Bob
1707 Sum of powers
1712 Flying Stars
1714 The Cave
1717 Dominoes
1718 River Crossing
1722 SUBTRACT
1726 Tango Tango Insurrection
1732 Phone numbers
1733 Parity game
1737 Connected Graph
1740 A New Stone Game
1742 Coins
1745 Divisibility
1770 Special Experiment
1771 Elevator Stopping Plan
1776 Task Sequences
1821 Fence
1837 Balance
1848 Tree
1850 Code
1853 Cat
1874 Trade on Verweggistan
1889 Package Pricing
1920 Towers of Hanoi
1926 Pollution
1934 Trip
1936 All in All
1937 Balanced Food
1946 Cow Cycling
1947 Rebuilding Roads
1949 Chores
1952 BUY LOW, BUY LOWER
1958 Strange Towers of Hanoi
1959 Darts
1962 Corporative Network
1975 Median Weight Bead
1989 The Cow Lineup
2018 Best Cow Fences
2019 Cornfields
2029 Get Many Persimmon Trees
2033 Alphacode
2047 Concert Hall Scheduling
2063 Investment
2081 Recaman's Sequence
2082 Terrible Sets
2084 Game of Connections
2127 Greatest Common Increasing Subsequence
2138 Travel Games
2151 Check the difficulty of problems
2152 Fire
2161 Chandelier
2176 Folding
2178 Heroes Of Might And Magic
2181 Jumping Cows
2184 Cow Exhibition
2193 Lenny's Lucky Lotto Lists
2231 Moo Volume
2279 Mr. Young's Picture Permutations
2287 Tian Ji -- The Horse Racing
2292 Optimal Keypad
2329 Nearest number - 2
2336 Ferry Loading II
2346 Lucky tickets
2353 Ministry
2355 Railway tickets
2356 Find a multiple
2374 Fence Obstacle Course
2378 Tree Cutting
2384 Harder Sokoban Problem
2392 Space Elevator
暴力三层循环
2397 Spiderman
2414 Phylogenetic Trees Inherited
2424 Flo's Restaurant
2430 Lazy Cows
2915 Zuma
3017 Cut the Sequence
3028 Shoot-out
3124 The Bookcase
3176 Cow Bowling
3133 Manhattan Wiring
3345 Bribing FIPA
3375 Network Connection

shǎ�?/a> 2009-07-29 15:18 发表评论

状态DP~

Sun, 12 Jul 2009 08:40:00 GMT

http://acm.sgu.ru/problem.php?contest=0&problem=222
�q�是入门题，数据较大�Q�需要记忆化搜烦(ch��)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1321
上题的提高版�Q�不�q�数据超��，爆搜都能�q?br>
http://acm.sgu.ru/problem.php?contest=0&problem=223
先要预处理出一行中的全部可行状态~
然后DP的时候��y妙的�q�用位运��进行状态的判断和�{�U?br>状态dp中位�q�算的��y妙运用会(x��)大幅度提高程序的效率和帅气程�?br>
http://acm.pku.edu.cn/JudgeOnline/problem?id=1185
非常�l�典的状态DP�Q�由于攻击范围是两格�Q�所以要保持两个状态，有�h用三�q�制压羃�Q�我觉得太烦(ch��)�?不能使用飘逸的位运��）(j��)
但是[101][2^10][2^10]得状态太大，考虑�?^10中有很多情况是不可到辄��
计算下当m=10的时候最�?0个合法状态，所以我开了[101][60][60]的数�l�记忆化DP�q�了

http://acm.hdu.edu.cn/showproblem.php?pid=2640
teddy大牛的题目，和上题差不多�Q�不�q�不能重叠放�Q�所以处理比上题�?ch��)很�?br>同样2^8里有很多不可到达的情况，最多之�?3�U?br>所以我开[101][13][13]的数�l?5ms��p��了，哈哈
�q�就好像�?span style="color: red;">两次状态压�~?/span>
最�q�的DP题目感觉�?span style="color: red;">把很多不可到辄��状态压�~�掉效率�?x��)提高超多~也可能让�E�序从TLE MLE变成AC~

http://acm.pku.edu.cn/JudgeOnline/problem?id=2411
http://acm.hdu.edu.cn/showproblem.php?pid=1400
�q�道其实很简单，先预处理出当前状态s1��C��一状态的可能值s2�Q�hash[1<dp[0][(1<然后�l�过n*(1<
http://acm.sgu.ru/problem.php?contest=0&problem=223
两种砖块�Q�除了预处理的时候状态多点，�?�U�分支，其他的都和上一题一�?br>(��L��一个状态到另一个状态可能会(x��)有多�U�情况，hash的时候要�?+而不是true false)

http://acm.hdu.edu.cn/showproblem.php?pid=2280
要求用最��的1铺满所有的�I�格�Q�其�?是没用的(可以用两�?代替)�Q�化��之后使用的方块和上一题一��P��一��L(f��ng)��预处理后
dp求出最��的1

http://acm.pku.edu.cn/JudgeOnline/problem?id=1038
http://acm.hdu.edu.cn/showproblem.php?pid=2696
http://acm.hdu.edu.cn/showproblem.php?pid=2442
http://acm.hdu.edu.cn/showproblem.php?pid=1755
http://acm.hdu.edu.cn/showproblem.php?pid=1820
http://acm.hdu.edu.cn/showproblem.php?pid=1668
http://acm.hdu.edu.cn/showproblem.php?pid=2518
http://acm.hdu.edu.cn/showproblem.php?pid=1666
http://acm.hdu.edu.cn/showproblem.php?pid=1820
http://acm.hdu.edu.cn/showproblem.php?pid=2315

shǎ�?/a> 2009-07-12 16:40 发表评论

��奇的舞�y�~~Dancing_Links

Thu, 09 Jul 2009 17:17:00 GMT

整了一天的跌��链，资料可以在网上搜�?br>http://sqybi.com/works/dlxcn/
惊讶于它做深搜的时候可以达到如此强劲的剪枝
下午的时候不看网上的模板自己写了一个，自认为是比模板少了一个for循环�Q�但是写好后才发现没有模板的启发式搜索的效率�Q�就�q�样�zȝ��生的TLE了，��费了我好几个小时啊~~%>_<%~~
晚上只好写用模板的方法，写了一个后瞬间�q�了�Q�感觉难度也不过��?d��ng)�?br>但这个舞�y�链可是�Ҏ(gu��)��解答却很隄��出的主，构造舞�y�链�q�是关键
献上我的模板~~
最��单的舞蹈链，效率仅比hhanger差，可以�?40MS,不过后来我测��Z��一些数据的�l�构�Q�暴力优化到�?24MS�Q�哈哈哈(得意一�?~~~
http://acm.hust.edu.cn/thanks/problem.php?id=1017
(�_��覆盖问题)

void remove(int &c) {
    L[R[c]] = L[c];
    R[L[c]] = R[c];
    for(int i = D[c]; i != c ; i = D[i]) {
        for(int j = R[i]; j != i ; j = R[j]) {
            U[D[j]] = U[j];
            D[U[j]] = D[j];
            --S[Col[j]];
        }
    }
}
void resume(int &c) {
    for(int i = U[c];i != c;i = U[i]) {
        for(int j = L[i]; j != i ; j = L[j]) {
            ++S[Col[j]];
            U[D[j]] = j;
            D[U[j]] = j;
        }
    }
    L[R[c]] = c;
    R[L[c]] = c;
}
bool dfs() {
    if(R[0] == 0) {
        return true;
    }
    int i , j;
    int idx,minnum = 999999;
    for(i = R[0];i != 0 ; i = R[i]) {
        if(S[i] < minnum) {
            minnum = S[i];
            idx = i;
        }
    }
    remove(idx);
    for(i = D[idx]; i != idx; i = D[i]) {
        ans[deep++] = Row[i];
        for(j = R[i]; j != i ; j = R[j]) {
            remove(Col[j]);
        }
        if(dfs()) {
            return true;
        }
        deep --;
        for(j = L[i]; j != i ; j = L[j]) {
            resume(Col[j]);
        }
    }
    resume(idx);
    return false;
}

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3209
(�_��覆盖问题)
��大的这道省赛题其实��是完美覆盖的�{化~把每一格都分开来，要求��是选N个方块把囑֮��覆盖全部搜完然后最��的个数
思�\�Q�行方块�Q�列单位��格子，矩阵�?是方块所能覆盖的��格�?br>
http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1507
(重复覆盖问题) 重复覆盖的模杉K��
献上模板

void remove(int &c) {
    for(int i = D[c]; i != c ; i = D[i]) {
        L[R[i]] = L[i];
        R[L[i]] = R[i];
    }
}
void resume(int &c) {
    for(int i = U[c]; i != c ; i = U[i]) {
        L[R[i]] = i;
        R[L[i]] = i;
    }
}
int h() {
    bool hash[51];
    memset(hash,false,sizeof(hash));
    int ret = 0;
    for(int c = R[0]; c != 0 ; c = R[c]) {
        if(!hash[c]) {
            ret ++;
            hash[c] = true;
            for(int i = D[c] ; i != c ; i = D[i]) {
                for(int j = R[i] ; j != i ; j = R[j]) {
                    hash[Col[j]] = true;
                }
            }
        }
    }
    return ret;
}
bool dfs(int deep,int lim) {
    if(deep + h() > lim) {
        return false;
    }
    if(R[0] == 0) {
        return true;
    }
    int idx , i , j , minnum = 99999;
    for(i = R[0] ; i != 0 ; i = R[i]) {
        if(S[i] < minnum) {
            minnum = S[i];
            idx = i;
        }
    }
    for(i = D[idx]; i != idx; i = D[i]) {
        remove(i);
        for(j = R[i]; j != i ; j = R[j]) {
            remove(j);
        }
        if(dfs(deep+1,lim)) {
            return true;
        }
        for(j = L[i]; j != i ; j = L[j]) {
            resume(j);
        }
        resume(i);
    }
    return false;
}

http://acm.tju.edu.cn/acm/showp3219.html
http://acm.hdu.edu.cn/showproblem.php?pid=2295
(重复覆盖问题)
�q�题无法转化成完��覆盖，所以remove和resume的时候要变化一下，但是�q�样�q�是�?x��)超时我看了标程才算AC。唉。�?br>主要是里边的一个A*的h函数是在是太犀利了�Q�一下从TLE��C��46MS。。。。剪枝还是非帔R��要的
思�\�Q�行是雷达，列是城市(j��ng)�Q�矩阵中1是雷达覆盖城�?br>
http://acm.fzu.edu.cn/problem.php?pid=1686
(重复覆盖问题)
�q�道题也同上道一��h��Q?�?-1矩阵中选取最��的行，使得每一列最��有一�?" �q�个模型
所以和上一道徏表一样徏好之后套上模板就AC了~
思�\�Q�行是枚丑֜�每个位子��N��法，列式怪物个数(最好给怪物标记个id)�Q�矩阵中�?是在�q�个地方��N��法是否能辑ֈ�目标怪物

http://www.spoj.pl/problems/NQUEEN/
(重复覆盖问题)
N皇后问题�Q�打的时候没能想到怎么转化成精��覆盖，只是用了dancing links的思想�Q�傻�?c��)��׃��一个晚上完成了一个超�U�复杂的�c�_��型链�?重复覆盖)�Q�开始的时候启发式函数S没有更新�Q�导致没有发挥效用，�l�果本例30�?的数据都跑不出来�Q�还以�ؓ(f��)是想法出错了�Q�睡觉前在床上想刎ͼ�改了一下，效率呈指数��增长�Q?0�?的瞬间跑出来�Q�在state里排到第一�Q�哈�?br>
(�_��覆盖问题)
今天CH教我怎么��之转化成十字链表的�_��覆盖�Q�但是矩阉|��(n*n)*(6*n-2)比米字型链表n*n的大了好多倍，交了一下，跑了1s�Q�效率不如米字型�?br>其思�\是：(x��)行是格子数n*n,列是(�?�?正逆对角线)�Q�矩阵中�?是放在各自上所占得行，列，对角�U?br>不需要全部搜完，只要初始皇后+dfs的深度达到n(放了n个皇�?��return true

http://acm.hdu.edu.cn/showproblem.php?pid=2828
(�_��覆盖问题)
�q�题恶化N皇后一样可以�{化成多种覆盖。我是精��覆盖，列是n+m只要�_��前n个就够了
(重复覆盖问题)
�q�可以�{化成不精��，那么列就是n

当然�Q�此题出题�h的意图是二分匚w��。。�?br>
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=31
http://acm.pku.edu.cn/JudgeOnline/problem?id=1084
(重复覆盖问题)
�q�题要不和我说是dancing links 我还真看不出�?br>此题��烦(ch��)�Q�虽看出来但是徏表就�׃��我一个半��时�Q�还�q�我使用上行的头节点�Q�以前我只是用列的头节点�Q�努力了很久�Q�过了sample��AC了，�?ch��)就烦(ch��)在��?br>思�\�Q�行是火柴棒敎ͼ�列是完美时能构成的矩阉|��目，矩阵中的1是列矩阵是否包含行火�?br>
http://acm.pku.edu.cn/JudgeOnline/problem?id=3074
http://acm.pku.edu.cn/JudgeOnline/problem?id=3076
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3038
(�_��覆盖问题)
�l�典的数独，看了论文才明白怎么覆盖�Q?*9*9的行 (9+9+9)*9+9*9的列
思�\�Q�行�?1个小�?每个格子�?个可能数字，列是81个小�?9�?�?��块�?个数�?br>每列��切的有4�?
开始读入的时候吧��定的数字的头上�?删掉可以很大的提高效�?br>
http://acm.hdu.edu.cn/showproblem.php?pid=2518
��爽的dancing links
�q�题所有的方块可以旋�{�Q�这点超�?ch��)~
我差点就��代码了，枚�D所有状态，不过最后我�q�是修改成不��的办�?br>只有几组�{�案�Q�用dancing links暴力跑出所有组合后然后打表�Q�嘿嘿，我就是这么猥琐的�q�的
72*所有摆放数~
思�\�Q?0个格子加12个方块作为列�Q�所有摆攄��Ҏ(gu��)��C��

好了�Q�A光上�q�题目dancing links的学�?f��n)也告一�D�落�Q�这个舞�y�是在是优美�Q�以后出题一定要�׃��曲经典的舞蹈~~

2009.9.6
发现dancing links�q�能�?span style="color: red;">最大团
http://acm.hdu.edu.cn/showproblem.php?pid=1530
转化成补囑֐�再徏表。。。不�q�效率很低，跑了6000+MS�Q�全部搜完找一个最大的�Q�还没有更优的办法优化，��试�q�二分再写个h函数未果。。�?br>
10.15
http://acm.hdu.edu.cn/showproblem.php?pid=3156
和雷辄��|��不过放radar的点要求出来�Q�也是先二分枚�D半径�Q�然后利用两个点和半径确定一个圆心C(n,2)�Q�可以证明如果放其他地方一定没�q�个圆心�?br>

shǎ�?/a> 2009-07-10 01:17 发表评论

hdu1055 & PKU2054------DP+可以��L��取出节点的二叉堆

Mon, 29 Jun 2009 08:30:00 GMT

http://acm.pku.edu.cn/JudgeOnline/problem?id=2054
http://acm.hdu.edu.cn/showproblem.php?pid=1055
好点�l�典的一道题目，做了半天都做不出�?br>后来到网上看了解题报告才明白�Q�解题报告网上有�Q�我��׃��再出说明了）(j��)是n^2的算�?br>我在惻I��每次都遍历一遍找最大权值的点会(x��)不会(x��)太浪�Ҏ(gu��)��_(d��)��如果用堆取出权值最大的�Ҏ(gu��)��率就�?x��)有很大改进�Q�变成n*log(n)�?br>但是最大权值的父亲节点也要从堆中取出，�q�有炚w��?br>�l�合昨天ZOJ月赛比赛中自创的可以取出��L��节点的二叉堆�Q�记录位子来实现�Q�想��C��Ҏ(gu��)��Q�多方试验之后果然成功了
在PKU提交也只用了16MS...哈哈
贴出来晒�?

#include "stdio.h"
#include "string"
#define maxn 1001
//-----------------------Binary Heap------------------------------------
struct Heap {
    int val,cost,time,idx;
}hh[maxn];
int pos[maxn];
int len;
bool Prior(Heap a,Heap b) {
    return a.val * b.time > b.val * a.time;
}
void Push(Heap s) {
    int i;
    for(i = ++len ; i > 1 && Prior(s,hh[i/2]); i /= 2) {
        hh[i] = hh[i/2];
        pos[hh[i].idx] = i;
    }
    hh[i] = s;
    pos[hh[i].idx] = i;
}
Heap Pop(int idx) {
    if(idx == -1)    return hh[0];
    Heap ret = hh[idx];
    Heap last = hh[len--];
    int i,s;
    for(i = idx ; i * 2 <= len; i = s) {
        s = i * 2;
        if(s + 1 <= len && Prior(hh[s+1],hh[s])) {
            s ++;
        }
        if(Prior(hh[s],last)) {
            hh[i] = hh[s];
            pos[hh[i].idx] = i;
        } else {
            break;
        }
    }
    hh[i] = last;
    pos[hh[i].idx] = i;
    for(i = idx ; i > 1 && Prior(hh[i],hh[i/2]); i /= 2) {
        Heap buf = hh[i];
        hh[i] = hh[i/2];
        hh[i/2] = buf;
        pos[hh[i].idx] = i;
        pos[hh[i/2].idx] = i/2;
    }
    return ret;
}
//---------------------------------------------------------------
int father[maxn];
int main() {
    int n,r,i;
    hh[0].cost = hh[0].time = hh[0].val = 0;
    while(scanf("%d%d",&n,&r),n+r) {
        len = 0;
        Heap root;
        for(i =1 ; i <= n ; i ++) {
            Heap buf;
            scanf("%d",&buf.cost);
            buf.val = buf.cost;
            buf.time = 1;
            buf.idx = i;
            if(i == r) {
                root = buf;
            } else {
                Push(buf);
            }
        }
        for(i = 1 ; i < n ; i ++) {
            int a,b;
            scanf("%d%d",&a,&b);
            father[b] = a;
        }
        while(len) {
            Heap max = Pop(1);
            int f = father[max.idx];
            if(f == r) {
                root.cost += max.cost + max.val * root.time;
                root.time += max.time;
                root.val += max.val;
            } else {
                Heap fa = Pop(pos[f]);
                fa.cost += max.cost + max.val * fa.time;
                fa.time += max.time;
                fa.val += max.val;
                fa.idx = f;
                Push(fa);
            }
            pos[max.idx] = -1;
        }
        printf("%d\n",root.cost);
    }
    return 0;
}

下边是n^2的算法，跑了200+MS。。简�z�是��z�，但效率不�?br>

#include "stdio.h"
#include "string"
#define maxn 1001
struct H{
    int val;
    int cost;
    int time;
    void clear() {
        val = cost = time = 0;
    }
}hh[maxn];
int father[maxn];
int main() {
    int n,r,i;
    while(scanf("%d%d",&n,&r),n+r) {
        for(i =1 ; i <= n ; i ++) {
            scanf("%d",&hh[i].cost);
            hh[i].val = hh[i].cost;
            hh[i].time = 1;
        }
        for(i = 1; i < n ; i ++) {
            int a,b;
            scanf("%d%d",&a,&b);
            father[b] = a;
        }
        while(true) {
            int idx = 0;
            for(i = 1 ; i <= n ; i ++) {
                if(i != r && hh[i].time && (idx == 0 || hh[idx].val * hh[i].time < hh[i].val * hh[idx].time)) {
                    idx = i;
                }
            }
            if(idx == 0)    break;
            int f = father[idx];
            hh[f].cost += hh[idx].cost + hh[idx].val * hh[f].time;
            hh[f].val += hh[idx].val;
            hh[f].time += hh[idx].time;
            hh[idx].clear();
        }
        printf("%d\n",hh[r].cost);
    }
    return 0;
}

shǎ�?/a> 2009-06-29 16:30 发表评论

概率题��L��

Tue, 19 May 2009 05:48:00 GMT

以前��p��q�不��求期望的题�Q�题意很直白�Q�但是却一直少不到思�\做题
今天lcy老师推荐我看了zjut一位大牛的文章
http://bbs.zjut.com/viewthread.php?tid=1170233&extra=page%3D1
�l�于略知一二了�Q�找几道概率题做�?br>

http://acm.hdu.edu.cn/search.php?field=problem&key=2262
E(now) = �Q�E(NEXT1) + E(NEXT2) +...+E(NEXTn))/n + 1
每个盔R��点徏方程�Q�注意�v点可以走到得�Ҏ(gu��)��能徏方程�Q�不然会(x��)��D��无解
先floodfill扑ֈ��L(f��ng)��可以走到得点�Q�然后徏方程�Q�最后仍个高斯消元模板解把答案解出来

http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1423
同上一道一�怸��L(f��ng)��?br>
http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1317
�q�个需要构造，盔R��位子数的转换
惛_��盔R��n�Q�都向内飞的话n-2�Q�都惛_��飞n+2�Q�一个向左一个向右的话就保持n不变�Q�所以有下列方程
E[n] = E[n+2]/4 + E[n-2]/4 + E[n]/2 + 1

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2619
此题极度郁闷�Q��{�U�L��E�已�l�推出来了，却因为精度问题过不了
�W�四个sample我试了三个模板，出来的答案都不一栗��。。。�?br>用java可过
http://acm.hdu.edu.cn/showproblem.php?pid=3058
上体升��版，变成了多串匹配，建Tire囄��基础上进行�{�U?br>一样存在精度问题，用java可过

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2837
因�ؓ(f��)甉|��有上有下�Q�我索性就把楼的高度加�?nbsp; n = n * 2 - 2
那sample来说�Q?~10是向上的�Q?0~20是向下的�Q?0��是0�Q�向上的话又变成1开�?br>在第7和第13层会(x��)��到�?我从0层开始，所以每个量都要-1)
�q�样��可以得到�{�U�L��E?br>E[i] = E[(i+j)%n]/6 + 1

        for(i =0; i < n ; i ++) {
            if(i == m ||  i == n-m) {
                mat[i][i] = 1;
            } else {
                mat[i][i] = 6;
                mat[i][n] = 6;
                for(j = 1; j <= 6; j ++) {
                    mat[i][(i+j)%n] --;
                }
            }
        }

http://acm.hdu.edu.cn/showproblem.php?pid=1204
�q�题很早��开始想了，现在才会(x��)做，公式如下�Q?br>a = p * (1 - q);
b = q * (1 - p);
E[n] = E[n-1] *　a + E[n+1] * b + E[n] * (1 - a - b);
E[0] = 0;
E[N+M] = 1;

�q�两道AC的代码都��短�Q�应该是公式题。。没上边几道那么有意思。。�?br>http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2949
http://acm.pku.edu.cn/JudgeOnline/problem?id=3682

献上�W�一�ơ写的高斯消元模�?br>若返回时false则无�?br>

/**************************************************
*    mat里徏好方�E?增广矩阵    n*(n+1)
*    传入方程个数
*    �{�案保存在mat[i][i]�?br>**************************************************/
#include "stdio.h"
#include "string"
#define ab(a) (((a)>0)?(a):(-a))
#define maxn 100
#define eps 1e-10
double mat[maxn][maxn];
void swap(double &a,double &b) {double t = a;a = b;b = t;}
bool Gauss(int n) {
    int i,j,row,idx;
    double maxx,buf;
    for(row = 0; row < n ; row ++) {
        for(maxx = 0,i =row ; i < n ; i ++)
            if(ab(mat[i][row]) > maxx)
                maxx = ab(mat[i][row]),idx = i;
        if(maxx < eps)return false;
        if(idx != row)
            for(j =0 ; j <= n ; j ++)
                swap(mat[row][j],mat[idx][j]);
        for(i = row + 1; i < n ; i ++)
            for(buf=mat[i][row]/mat[row][row],j = row; j <= n ; j ++)
                mat[i][j] -= buf * mat[row][j];
    }
    for(i = n-1;i >= 0; i --) {
        for(j = i +1; j < n ; j ++)
            mat[i][n] -= mat[i][j]*mat[j][j];
        mat[i][i] = mat[i][n]/mat[i][i];
    }
    return true;
}

shǎ�?/a> 2009-05-19 13:48 发表评论

Sun, 17 May 2009 12:36:00 GMT

很好玩的��法
��?�~�点可以把一块点看成一个点�Q�大大加快算法。还有一些无法解决的问题也可以用�q�个来解�?br>前几天在林学院做题的时候胡搞搞出来了，哈哈
今天又A了一�?br>最�q�对囑֯��?w��i)越来越有感觉�?br>
http://acm.hdu.edu.cn/showproblem.php?pid=2767

#include "stdio.h"
#include "algorithm"
using namespace std;
#define maxn 20001
struct Node {
    int to;
    Node * next;
}list[maxn],opp[maxn];
struct SCC{
    int time;
    int newid;
    int idx;
}hh[maxn];
int time,newid;
bool flag;
bool hash[maxn];
bool hashid[maxn];
bool gashid[maxn];
//--------------------------------------------
void dfs(int idx) {
    Node * buf;
    buf = list[idx].next;
    while(buf) {
        if(!hash[buf->to]) {
            hash[buf->to] = true;
            dfs(buf->to);
        }
        buf = buf->next;
    }
    if(time == 7)
        time = 7;
    hh[idx].time = time ++;
    hh[idx].idx = idx;
}
void dfs2(int idx) {
    Node * buf;
    buf = opp[idx].next;
    while(buf) {
        if(!hash[buf->to]) {
            hash[buf->to] = true;
            dfs2(buf->to);
        }
        buf = buf->next;
    }
    hh[idx].newid = newid;
}
void dfs3(int idx) {
    Node * buf;
    buf = list[idx].next;
    while(buf) {
        if(hh[idx].newid != hh[buf->to].newid) {
            hashid[hh[idx].newid] = true;
            gashid[hh[buf->to].newid] = true;
        }
        if(!hash[buf->to]) {
            hash[buf->to] = true;
            dfs3(buf->to);
        }
        buf = buf->next;
    }
}
bool cmp(SCC a,SCC b) {
    return a.time > b.time;
}
//-----------------------------------------
int main() {
    int n,i,a,b,m,T;
    Node * buf;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        for(i = 1 ; i <= n ; i ++) {
            list[i].next = NULL;
            opp[i].next = NULL;
        }
        while(m --) {
            scanf("%d%d",&a,&b);
            buf = (Node *)malloc(sizeof(Node));        //正图
            buf->to = b;
            buf->next = list[a].next;
            list[a].next = buf;

            buf = (Node *)malloc(sizeof(Node));        //反图
            buf->to = a;
            buf->next = opp[b].next;
            opp[b].next = buf;
        }
        memset(hash,false,sizeof(bool)*(n+1));
        time = 0;
        for(i = 1 ; i <= n ; i ++) {                //先确定时间戳
            if(!hash[i]) {
                hash[i] = true;
                dfs(i);
            }
        }
        sort(hh+1,hh+1+n,cmp);                        //按时间戳排序
        memset(hash,false,sizeof(bool)*(n+1));
        newid = 0;
        for(i = 1 ; i <= n ; i ++) {                //把点分成几块
            if(!hash[hh[i].idx]) {
                hash[hh[i].idx] = true;
                hh[hh[i].idx].newid = ++newid;
                dfs2(hh[i].idx);
            }
        }
        if(newid == 1) {
            puts("0");
            continue;
        }
        memset(hash,false,sizeof(bool)*(n+1));
        memset(hashid,false,sizeof(bool)*(newid+1));
        memset(gashid,false,sizeof(bool)*(newid+1));
        for(i =1 ; i <= n ; i ++) {                    //扑և�块的出度入度
            if(!hash[i]) {
                hash[i] = true;
                dfs3(i);
            }
        }
        int cnt = 0;
        int cnt1 = 0;
        for(i = 1; i <= newid ; i ++) {
            if(!hashid[i])
                cnt ++;
            if(!gashid[i])
                cnt1 ++;
        }
        printf("%d\n",cnt>cnt1?cnt:cnt1);
    }
    return 0;
}

shǎ�?/a> 2009-05-17 20:36 发表评论

又学了一招，随机化法�Q�用于比赛时候是在没办法的时候的��氓剪枝

Fri, 15 May 2009 02:01:00 GMT

不同时刻提交不限不同的结果。。。。学�?f��n)了。哈�?br>比赛时候是在没有办法的时候又多了一�?br>付代�?br>

#include "stdio.h"
#include "algorithm"
#include "time.h"
using namespace std;
int n,hash[25];
int A[25][25];
int res,maxdeep;
void fun() {
    int sum = 0;
    int a[25],b[25],la =0,lb =0;
    for(int i =0 ; i < n ; i ++) {
        if(hash[i])    a[la++] = i;
        else    b[lb++] = i;
    }
    for(int i = 0; i < la; i ++) {
        for(int j =0 ; j < lb; j ++) {
            sum += A[a[i]][b[j]];
        }
    }
    if(sum > res)    res = sum;
}
void dfs(int deep,int start) {
    if(deep == maxdeep) {
        fun();
        return ;
    }
    for(int i =start; i < n ; i ++) {
        if(!hash[i]) {
            hash[i] ^= 1;
            dfs(deep+1,i+1);
            hash[i] ^= 1;
        }
    }
}
int main() {
    int i,j;
    while(scanf("%d",&n) == 1) {
        for(i =0 ; i < n ; i ++) {
            for(j =0 ; j < n ; j ++) {
                scanf("%d",&A[i][j]);
            }
        }
        res = 0;
        if(n <= 19) {
            maxdeep = n / 2;
            memset(hash,0,sizeof(hash));
            while(maxdeep) {
                dfs(0,0);
                maxdeep --;
            }
        } else {
            int cnt = 100000;
            srand(time(NULL));
            memset(hash,0,sizeof(hash));
            while(cnt --) {
                hash[rand()%n] ^= 1;
                fun();
            }
        }
        printf("%d.\n",res);
    }
    return 0;
}

shǎ�?/a> 2009-05-15 10:01 发表评论

�?w��i)�ŞDP

Mon, 11 May 2009 12:39:00 GMT

#include "stdio.h"

struct Tree{
    int father;
    int child;
    int brother;
    int TakeParty;
    int Not;
    int Max() {
        return TakeParty > Not ? TakeParty : Not;
    }
    void init() {
        father = child = brother = Not = 0;
    }
}tree[6001];

void dfs(int idx ) {
    int child;
    child = tree[idx].child;
    while(child) {
        dfs(child);
        tree[idx].TakeParty += tree[child].Not;
        tree[idx].Not += tree[child].Max();
        child = tree[child].brother;
    }
}

int main() {
    int n,i,a,b;
    while(scanf("%d",&n) == 1) {
        for(i =1 ; i <= n ; i ++) {
            scanf("%d",&tree[i].TakeParty);
            tree[i].init();
        }
        while(scanf("%d%d",&a,&b),a+b) {
            tree[a].father = b;
            tree[a].brother = tree[b].child;
            tree[b].child = a;
        }
        for(i = 1 ; i <= n ; i ++) {
            if(!tree[i].father) {
                dfs(i);
                printf("%d\n",tree[i].Max());
                break;
            }
        }
    }
    return 0;
}

shǎ�?/a> 2009-05-11 20:39 发表评论

�׃��一天时间写的一个很挫很挫的大数模板

Wed, 06 May 2009 10:37:00 GMT

摘要: �q�就 Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->#include "iostream"#include "stdio.h"#define Mod 10000using namespace&nbs... 阅读全文

shǎ�?/a> 2009-05-06 18:37 发表评论

��江省历�q�省赛题+解析

Sat, 02 May 2009 13:10:00 GMT

http://acm.zju.edu.cn/onlinejudge/searchProblem.do?contestId=1&titlefrom=0&authorfrom=0&sourcefrom=0&query=provinc
�?x��)对每一道做�q�的题做一个简单的分析�Q�如果有出错或者不理解可以于我交流

2104 Let the Balloon Rise Zhejiang Provincial Programming Contest 2004
数据很小�Q�遍历一下，扑ֈ��?+�Q�没有的话就��新�?br>2105 Number Sequence Zhejiang Provincial Programming Contest 2004
扑��@环节�Q�开hash[7][7]来找�Q�hash前一个和后一�?br>2106 Tick and Tick Zhejiang Provincial Programming Contest 2004
当年应该是金牌题吧，旉��是连�l�的�Q�不能一�U�一�U�分开来计��?br>我是�Ҏ(gu��)��题目联立三个不等式方�E�，然后解出交集
2107 Quoit Design Zhejiang Provincial Programming Contest 2004
最�q�点对，二分的思想�Q�据说数据结构书上就有。。�?br>2108 Elevator Zhejiang Provincial Programming Contest 2004
��单模拟题�Q�求��Z��升和下降的层�?br>2109 FatMouse' Trade Zhejiang Provincial Programming Contest 2004
按性�h(hu��n)比排序后贪心
2110 Tempter of the Bone Zhejiang Provincial Programming Contest 2004
深搜�Q�加个奇偶性剪�?br>2111 Starship Troopers Zhejiang Provincial Programming Contest 2004
��题�Q�不�?x��)。。。据说是�?w��i)�ŞDP
5.13补充�Q�当时看着是的做也不敢做的��题�Q�前几天学习(f��n)了熟�(zh��n)�树(w��i)形DP后练�?f��n)了几道题目再来做这题发��C��炚w��不难
�?w��i)��?背包+临街表徏囑֏�以轻松A掉此�?br>

2474 World Goes Round Zhejiang Provincial Programming Contest 2005
�q�题数据量好大，n=10�Q�记得在北师大比赛的时候做�q�一�?*3的八数码也是�q�样转动规则�Q�当时是预处理直接秒掉的
�q�道状态太大，变��n为神题了�Q�不�?br>
不是求最优解�Q�所以我猜测应该是构造出一�U�方法让它�{到目标状�?br>//我想是不是可以降�l�_(d��)��拼好最左边和最上边��可以降一�l�了。�?br>至于怎么构造没有想出来。。。�?br>��未做出
2475 Benny's Compiler Zhejiang Provincial Programming Contest 2005
判断有向图成环，用拓扑排序，错了N遍，我都怀疑是不是我的拓扑写错了。�?br>后来试了一下原来有恶心数据�Q�Ai == Bi的时候这��L(f��ng)��数据不要计算�Q�不然就自己成环了�?br>2476 Total Amount Zhejiang Provincial Programming Contest 2005
模拟一下，都不用大数加法，直接用long long��够了，输出的时候分�D�输�?br>2477 Magic Cube Zhejiang Provincial Programming Contest 2005
题目说不��过5步，可以用�P代加深搜索，其实题目意思很直白�Q�就是这道题目很难模拟�?br>把魔方的转模拟出来这题目也就做出来了。�?br>我把每一�U��{都计��出来写�q�表里，然后按照�q�个表�{��O(ji��n)K�?br>2478 Encoding Zhejiang Provincial Programming Contest 2005
遍历一遍比较当前字�W�和前一个字�W�就�?br>2479 Cover the Rectangular Ground Zhejiang Provincial Programming Contest 2005
从最左下角的点开始dfs�Q�每�ơ先判断能不能放上，然后扑և�当前最左下角的点再dfs
�q�样很暴力。。最坏的情况��不来，大概�?0!�ơ。。。我晕，一直TLE
后来我试了下数据�Q�倒是是我的程序真的效率很低，�q�是只有一些数据都跑不�?br>�l�过多次WA和TLE的测试发现只要有解得数据我都能跑出来�Q�无解的��q��接搜到死�?br>于是我定义如果深搜次数超�q?00000��q��接蟩出，无解
�l�果��AC了。。。。效率还很高�Q�由于内存原因拍在第�?br>唉，比赛的时候如果能�q�样AC的话��太RP了。。�?br>。。求正解。�?br>2480 Simplest Task in Windows Zhejiang Provincial Programming Contest 2005
数据量小�Q�直接水掉，从后往前比较for(i = n- 1; i >= 0 ; i --)�Q�找到符合的跛_��Q�最后输��Z��?br>2481 Unique Ascending Array Zhejiang Provincial Programming Contest 2005
排序后输�?br>

2736 Daffodil number Zhejiang Provincial Programming Contest 2006, Preliminary
水题
2737 Occurrence Zhejiang Provincial Programming Contest 2006, Preliminary
题目看清楚后暴力比较久可�?br>2738 The Kth BST Zhejiang Provincial Programming Contest 2006, Preliminary
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊�?br>推了一个下午啊。。。。。竟然WA。。。。。极度郁闗��。。。�?br>
吃饭回来�l�于AC了。。。。再郁闷�Q�原来是我对BST的理解有误，后来�U�哥�U�正了，��p��样陷入了误区N久。。。。不值得啊。。�?br>2739 Color Quantization Zhejiang Provincial Programming Contest 2006, Preliminary
��未做出
2740 Message System Zhejiang Provincial Programming Contest 2006, Preliminary
用�ƈ查集做，判断是树(w��i)�q�是��林�q�是�?br>

2741 Offside Zhejiang Provincial Programming Contest 2006, Preliminary
很脑�D�的模拟题，我却脑残的错了N�~�。。。。�?br>2742 Toy Bricks Zhejiang Provincial Programming Contest 2006
��未做出
2743 Bubble Shooter Zhejiang Provincial Programming Contest 2006
先foldfill一下，把连��h��的hash掉，然后从最上边每个点开始foldfill�Q�看�q�有几个留下
2744 Palindromes Zhejiang Provincial Programming Contest 2006
从回文串的性质上找规律�Q�每个点向左叛_�g长数回文串个�?br>2745 01-K Code Zhejiang Provincial Programming Contest 2006
恶心的推推题�Q�我的方法一定不是最��单的�Q�我开了四�l�数�l�还转移状�?br>分别存的是：(x��)
dp[0�?相差几位�Q�最高到达过�Q�最低到达过�Q�n]
�q�是很烂的方法，我想了很久才惛_��来，实在想不出更好的�?br>2746 Rank the Teams Zhejiang Provincial Programming Contest 2006
��未做出
2747 Paint the Wall Zhejiang Provincial Programming Contest 2006
��L��?hash卛_��Q�有�Ҏ(gu��)��力，正解是线�D�|��(w��i)
2748 Free Kick Zhejiang Provincial Programming Contest 2006
恶心的集合题�Q�开始没有看到straight "WALL"构造出一�U�最优解�Q�结果WA�?br>改了之后也一直WA�Q�错了无数次后修改了下求夹角的方法，本来有atan�Q�改成acos竟然AC了~~
思�\�Q?br>先求出没有wall时候的夹角�Q�然后减��d��门员的范��_(d��)��再根据剩下的角度来求��Z�h�?br>2749 Polarium Zhejiang Provincial Programming Contest 2006
很好玩的一道题目，有�h竟然能TLE 1000+�ơ，而且�q�箋了半�q�。。Orz一�?br>我跑的比较暴力，效率��Z��?br>思�\�Q?br>首先枚�D最后的�{�案�Q�即每行的黑白情�?br>然后�Ҏ(gu��)��q�个�{�案重新��d��一张地图，每个能走的点(除了边界�?都只能走且只��C��ơ，然后�q�行DFS
走到�l�点的时候判断下是否�W�合条�g��AC�?开始的时候我先判断走完点再判断最后一�Ҏ(gu��)��否是�l�点�Q�结果超时了)
2750 Idiomatic Phrases Game Zhejiang Provincial Programming Contest 2006
构造出最短�\�Q�每个串的最�?个和最�?个就是�v点和�l�点�Q?^16个点�Q?000条�\
我用��L��?�?bfs加速优�?0ms

2849 Attack of Panda Virus Zhejiang Provincial Programming Contest 2007
按level最��和type最��的优先队列BFS一�?br>2850 Beautiful Meadow Zhejiang Provincial Programming Contest 2007
水题
2851 Code Formatter Zhejiang Provincial Programming Contest 2007
注意出现在后边的'\t'
2852 Deck of Cards Zhejiang Provincial Programming Contest 2007
DP,三维(每组牌的价�?加滚动数�l�能��L��AC
2853 Evolution Zhejiang Provincial Programming Contest 2007
矩阵题，有点卡时�?br>我的�l�构体模�?00*200开不下�Q�于是我升��了我的模板，换了一个全局矩阵
题目意思理解对套个矩阵模板��p��q�了
2854 Fish and Her Bowl Zhejiang Provincial Programming Contest 2007
��未做出
2855 Google Map Zhejiang Provincial Programming Contest 2007
用所�l�公�?递归解决
2856 Happy Life Zhejiang Provincial Programming Contest 2007
无论什么状态都一定能构造出可行解的�Q�所以只要while(1)把和��于0的那行变换符��P��一直都满��条�g
2857 Image Transformation Zhejiang Provincial Programming Contest 2007
水题

2965 Accurately Say "CocaCola"! The 5th Zhejiang Provincial Collegiate Programming Contest
数据��，暴力下就好，数据大的话可以数学归�U�x��者暴力看下规�?a >
2966 Build The Electric System The 5th Zhejiang Provincial Collegiate Programming Contest
��d��的最��树(w��i)
2967 Colorful Rainbows The 5th Zhejiang Provincial Collegiate Programming Contest
正解说是半��^面交
我是用一个栈�Q�先按b从大到小排序�Q�如果然后遍历一下，能出现的��放�q�栈里，能把前面的覆盖掉��把栈里的线�D�|��?br>正半��_(d��)��负半轴做两次�Q�再处理一下小�l�节��好�?br>2968 Difference Game The 5th Zhejiang Provincial Collegiate Programming Contest
我先把A数组和B数组的数全部保存C数组里，然后排序
再遍历C数组,i = 0 to n*2
i左边的�ؓ(f��)B,双��的�ؓ(f��)A�Q�然后算出到达这个状态A到B的个数AB和BA
�Ҏ(gu��)��q�两个数��出最��的��p��Q�X = Min(AB,BA)�Q�Y = |AB - BA|�Q�Ci = X * Y* (Y - 1)�Q?br>如果比c��的话旧更新一下res
如果最后一�ơ都没更新到得话��是最后的�{�案一定是负的
所以A和B排序下根据c贪心得到�{�案
2969 Easy Task The 5th Zhejiang Provincial Collegiate Programming Contest
easy task
2970 Faster, Higher, Stronger The 5th Zhejiang Provincial Collegiate Programming Contest
sort
2971 Give Me the Number The 5th Zhejiang Provincial Collegiate Programming Contest
模拟�?a >
2972 Hurdles of 110m The 5th Zhejiang Provincial Collegiate Programming Contest
按剩下的能量DP
2973 Intelligent Pouring Robot The 5th Zhejiang Provincial Collegiate Programming Contest
��烦(ch��)的模拟题
��未做出
2974 Just Pour the Water The 5th Zhejiang Provincial Collegiate Programming Contest
暴力加��@环节能过�Q�正解是矩阵�Q?br>K == 0的时候常�怼�(x��)被忽略，处理一下就�?br> 2975 Kinds of Fuwas The 5th Zhejiang Provincial Collegiate Programming Contest
n^3的算法，枚�D��L��两行C(2,n)�Q�遍历列n�Q�找到相同的个数x�Q�res+=(x-1)*x/2;
2976 Light Bulbs The 5th Zhejiang Provincial Collegiate Programming Contest
枚�D�q�面上每一个点取最大�?br>

3202 Second-price Auction The 6th Zhejiang Provincial Collegiate Programming Contest
3203 Light Bulb The 6th Zhejiang Provincial Collegiate Programming Contest
3204 Connect them The 6th Zhejiang Provincial Collegiate Programming Contest
3205 Derivative The 6th Zhejiang Provincial Collegiate Programming Contest
3206 Disaster Area Reconstruction The 6th Zhejiang Provincial Collegiate Programming Contest
3207 80ers' Memory The 6th Zhejiang Provincial Collegiate Programming Contest
3208 Reforestation The 6th Zhejiang Provincial Collegiate Programming Contest
3209 Treasure Map The 6th Zhejiang Provincial Collegiate Programming Contest
3210 A Stack or A Queue? The 6th Zhejiang Provincial Collegiate Programming Contest
3211 Dream City The 6th Zhejiang Provincial Collegiate Programming Contest
3212 K-Nice The 6th Zhejiang Provincial Collegiate Programming Contest

shǎ�?/a> 2009-05-02 21:10 发表评论

二分囄��完美匚w��

Tue, 21 Apr 2009 06:32:00 GMT

今天学了KM��法�Q�用于二分图的完��匹配，以前��遇到过很多�ơ，但是一直都没有花时间去�?br>学的比较挫，写的是n^4的算�?br>实际上有m*m*n的算法的
下边几道是完��匹配的题目
http://info.zjfc.edu.cn/acm/problemDetail.aspx?pid=1222 赤裸裸的完美匚w��Q�图都徏好了
http://acm.hdu.edu.cn/showproblem.php?pid=1533 �q�个建图很容�?br>http://acm.hdu.edu.cn/showproblem.php?pid=2282 �q�个需要徏�?br>
下边是http://acm.hdu.edu.cn/showproblem.php?pid=1533 的AC代码

//////////////////////////////////////////////////////////////////////////
//二分囄��完美匚w��Q�Kuhn�Q�Munkras��法
#include<stdio.h>
#include<math.h>
#include<string>
#define MAXN 101
//////////////////////////////////////////////////////////////////////////
#define inf 0x7FFFFFFF
int edge[MAXN][MAXN];
int match[MAXN];
bool hash[MAXN][MAXN];
bool xhash[MAXN],yhash[MAXN];
char map[MAXN][MAXN];
int min(int a,int b){return a>b?b:a;}
int max(int a,int b){return a>b?a:b;}
void Scanf(int n,int m,int &l);
bool dfs(int p,int n)//扑֢��q��\�?/span>
{
    int i;
    for(i=0;i<n;i++)
    {
        if(!yhash[i] && hash[p][i])
        {
            yhash[i] = true;
            int t = match[i];
            if(t == -1 || dfs(t,n))
            {
                match[i] = p;
                return true;
            }
            if(t != -1)
                xhash[t] = true;
        }
    }
    return false;
}
void show(int id,int n)
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(id)
                printf("%d ",edge[i][j]);
            else
                printf("%d ",hash[i][j]);
        }
        puts("");
    }
    puts("");
}
void KM_Perfect_Match(int n)
{
    int i,j;
    int xl[MAXN],yl[MAXN];
    for(i=0;i<n;i++)
    {
        xl[i] = 0;
        yl[i] = 0;
        for(j=0;j<n;j++)
            xl[i] = max(xl[i],edge[i][j]);
    }
    bool perfect = false;
    while(!perfect)
    {
        for(i=0;i<n;i++)//现阶�D�已�l�匹配的�?/span>
        {
            for(j=0;j<n;j++)
            {
                if(xl[i] + yl[j] == edge[i][j])
                    hash[i][j] = true;
                else
                    hash[i][j] = false;
            }
        }

//        show(0,n);
        int cnt = 0;
        memset(match,-1,sizeof(match));
        for(i=0;i<n;i++)//当前的图是否能全部匹�?/span>
        {
            memset(xhash,false,sizeof(xhash));
            memset(yhash,false,sizeof(yhash));
            if(dfs(i,n))
                cnt ++;
            else
            {
                xhash[i] = true;
                break;
            }
        }
        if(cnt == n)//没有增广路径
            perfect = true;
        else
        {
            int ex = inf;
            for(i=0;i<n;i++)
            {
                for(j=0;xhash[i] && j<n;j++)
                {
                    if(!yhash[j])
                        ex = min(ex,xl[i] + yl[j] - edge[i][j]);//扑ֈ�一条没建的边的最��?/span>
                }
            }
            for(i=0;i<n;i++)//�Ҏ(gu��)��q�个�Ҏ(gu��)��q�行村ּ�
            {
                if(xhash[i])
                    xl[i] -= ex;
                if(yhash[i])
                    yl[i] += ex;
            }
        }
    }
}
int main()
{
    int n,m,l;
    while(scanf("%d%d",&n,&m))
    {
        if(n == 0 && m == 0)
            break;
        Scanf(n,m,l);
        KM_Perfect_Match(l);
        int mindis = 0;
        for(int i=0;i<l;i++)
            mindis += edge[match[i]][i];
        printf("%d\n",-mindis);
    }
    return 0;
}

//��d��建图
void Scanf(int n,int m,int &l)
{
    int i,j,l1,l2;
    struct Point{
        int x,y;
    }MAN[MAXN],HOUSE[MAXN];
    l1 = l2 = 0;
    for(i=0;i<n;i++)
    {
        scanf("%s",map[i]);
        for(j=0;j<m;j++)
        {
            if(map[i][j]=='m')
            {
                MAN[l1].x = i;
                MAN[l1].y = j;
                l1 ++;
            }
            else if(map[i][j]=='H')
            {
                HOUSE[l2].x = i;
                HOUSE[l2].y = j;
                l2 ++;
            }
        }
    }
    l = l1;
    for(i=0;i<l;i++)
        for(j=0;j<l;j++)
            edge[i][j] = -abs(MAN[i].x - HOUSE[j].x) - abs(MAN[i].y - HOUSE[j].y);
}

shǎ�?/a> 2009-04-21 14:32 发表评论

Mon, 20 Apr 2009 07:47:00 GMT

摘要: http://acm.hdu.edu.cn/showproblem.php?pid=2807昨天比赛�q�道题目要求矩阵的乘法然后进行比较。。算了一下复杂度是O(n^5)�l�对��时。。比赛的时候一直卡着�Q�赛后才知道有一�U�好的算�?-矩阵比较法就是二�l�的矩阵乘以一个一�l�的矩阵使之降�ؓ(f��)一�l�_(d��)��然后�q�行比较�q�样的话��只用n^2的算法进行矩�늛�乘了�Q�复杂度降成�?n^4)��利AC、。。�?#include<... 阅读全文

shǎ�?/a> 2009-04-20 15:47 发表评论

图论~~要大�q�一��Z��--Author McFn

Fri, 17 Apr 2009 03:10:00 GMT

打星��L(f��ng)��表示个�h认�ؓ(f��)比较�l�典�Q�或是算法，构图比较好的题目

1062* 昂贵的聘�C?nbsp;枚�D�{��限制+dijkstra
1087* A Plug for UNIX 2分匹�?br>1094 Sorting It All Out floyd �?nbsp;拓扑
1112* Team Them Up! 2分图染色+DP
1125 Stockbroker Grapevine FLOYD
1135 Domino Effect 最短�\
1149* PIGS �|�络��?br>1161* Walls floyd
1201 Intervals 差分�U�束
1236* Network of Schools ��?br>1251 Jungle Roads MST
1273 Drainage Ditches 最大流
1274 The Perfect Stall 2分匹�?br>1275* Cashier Employment 差分�U�束
1325 Machine Schedule 2分匹�?最��点覆盖)
1364 King 差分�U�束
1422 Air Raid 2分匹�?br>1459 Power Network �|�络��?br>1466 Girls and Boys 2分图(最大独立团)
1469 COURSES 2分匹�?br>1502 MPI Maelstrom floyd
1511* Invitation Cards 最短�\
1637* Sightseeing tour 混合图欧拉回�?/span>-�|�络��?br>1716 Integer Intervals 差分�U�束
1724* ROADS 最短�\-拆点
1780* Code �Ƨ拉回�\
1789 Truck History 最��生成树(w��i)
1797 Heavy Transportation 最��生成树(w��i)
1847 Tram 最短�\
1904* King's Quest ��?/span>
1949 Chores 最短�\
2060 Taxi Cab Scheme 2分匹�?br>2075 Tangled in Cables 最��生成树(w��i)
2112 Optimal Milking �|�络��?br>2125 Destroying The Graph 最��割
2135 Farm Tour 费用��?br>2139 Six Degrees of Cowvin Bacon floyd
2226 Muddy Fields 2分匹�?br>2230 Watchcow �Ƨ拉回�\
2239 Selecting Courses 2分匹�?br>2267* From Dusk till Dawn or: Vladimir the Vampire 最短�\
2289 Jamie's Contact Groups �|�络��?/span>
2337 Catenyms �Ƨ拉通�\
2349 Arctic Network 最��生成树(w��i)
2369 Genealogical tree 拓扑�?br>2387 Til the Cows Come Home 最短�\
2391* Ombrophobic Bovines 最大流
2394 Checking an Alibi 最短�\
2396* Budget �|�络��?br>2421* Constructing Roads 最��生成树(w��i)
2446 Chessboard 2分匹�?br>2455 Secret Milking Machine �|�络��?br>2457 Part Acquisition 最短�\
2472 106 miles to Chicago 最短�\
2485 Highways 最��生成树(w��i)
2516 Minimum Cost 费用��?br>2536 Gopher II 2分匹�?br>2553* The Bottom of a Graph ��?br>2570 Fiber Network floyd
2584 T-Shirt Gumbo �|�络��?br>2594* Treasure Exploration 2分匹�?br>2723 Get Luffy Out 2-sat
2724 Purifying Machine 2分匹�?br>2728 Desert King 最优比例生成树(w��i)
2749* Building roads 2-sat
2762 Going from u to v or from v to u? ��?br>2949* Word Rings 差分�U�束
2983 Is the Information Reliable? 差分�U�束
2987 Firing 最��割(求解正确�?/span>??)
3020 Antenna Placement 2分匹�?br>3041 Asteroids 2分匹�?br>3072* Robot 最短�\
3160 Father Christmas flymouse ��?br>3164 Command Network 最��树(w��i)形图
3169 Layout 差分�U�束
3177 Redundant Paths 双联通分�?br>3189 Steady Cow Assignment �|�络��?br>3204 Ikki's Story I - Road Reconstruction 最大流
3207 Ikki's Story IV - Panda's Trick 2分图
3216 Repairing Company 2分匹�?br>3228 Gold Transportation �|�络��?br>3255 Roadblocks 最短�\
3259 Wormholes 最短�\
3268 Silver Cow Party 最短�\
3275 Ranking the Cows floyd
3281 Dining 最大流
3308 Paratroopers 最��割
3310 Caterpillar
3311 Hie with the Pie floyd
3328 Cliff Climbing 最短�\
3343 Against Mammoths 2分匹�?br>3352 Road Construction �?br>3439 Server Relocation 最短�\
3463 Sightseeing 最短�\
3469 Dual Core CPU 最��割
3487 The Stable Marriage Problem �E�_��婚姻
3522 Slim Span 最��生成树(w��i)
3594 Escort of Dr. Who How 最短�\
3615 Cow Hurdles 最短�\
3623 Wedding 2-sat
3653 Here We Go(relians) Again 最短�\
3659* Cell Phone Network 最��支配集
3660 Cow Contest 拓扑
3662* Telephone Lines 最短�\
3678 Katu Puzzle 2-sat
3683* Priest John's Busiest Day 2-sat求解
3687 Labeling Balls 差分�U�束 �?nbsp;拓扑
3692 Kindergarten 2分匹�?br>3694 Network 无向囄��?br>
��把上面的作为图论学�?f��n)的题目�?/span>~

shǎ�?/a> 2009-04-17 11:10 发表评论

Thu, 16 Apr 2009 09:08:00 GMT

834064 2008-10-16 10:07:01 Accepted 1000 0MS 0K 105 B C shǎ�?/font>

��d��10�?6��P��A了第一道A+B,我的AC生��(d��ng)也正是开始了

今天�?�?6��P��正好半年�Q�提交了三道水题。。。在HDU的AC量达��C��900.。�?br>

shǎ�?/font>

A New Start~�Q?/td>

900

1888

47.67%

本来惛_��yifenfei大大一般，在纪忉|��辑ֈ�1000的AC�?br>可惜力不从心�Q�今日比赛甚多，到在其他OJ上刷题，hdoj上的水题又渐��，�?ch��)事�~��n�Q�无法完成半�q?000的目标~~只好�?00来代替一�?...XD

遥想半年前接触ACM�?天天跑机�?机房不开门就�|�吧,�q�曾�l�有一晚在�|�吧通过�?�W�二天集训队的学长们看到我半夜的提交的记录以为我带了�W�记�?N块电(sh��)板，后来知道我是在网吧通宵A(ch��)C的，更加惊讶�Q�天涯还曑և�了一�?a >shǎ�?OrOrOrOrz的题目。提到Acmer in HDU-ACM team are ambitious, especially shǎ�? he can spend time in Internet bar doing problems overnight.哈哈�Q�笑��L��了。。这题我特地写了很多优化刷到了第一31MS�Q�哈哈，别�h恐怕很难超��了�?╯_�?�?br>
�q�个学期开始后lcy教练?y��u)��常常提醒我要花一�D�|��间去��d��一门算法，从最开始的最��生成数�Q�最短�\�Q�到了树(w��i)状数�l�，字典�?w��i)，��L��化，�q�几个星期又有搞定图论的目标�Q�可以说没有lcy教练的督促我�q�步没有�q�么明显�Q�毕竟不学算法只��h��题的话是没有提高的。�?br>
接着��是�q�队�Q�放弃了一切时间AC�Q�寒假更是没有出�ȝ��q�，上个学期都是在自己做题，�q�个学期��都是在PK�Q�PK比做题好玩多了，能和高手切磋�Q�挑战一些��^时不敢做的题目，�q�气好的话，RP爆发下还能拿到前几的名次炫耀一番。�?br>大大��小�l�历�q�了很多场PK�Q�集训队内部的单人PK��有4场，�q�有几乎每日都有的校外比赛，真是赛事多发期。。上个星期细��一下至��做�?场比赛吧~~�q�个比赛密度虽然很高�Q�但是�h也越比越兴奋~~哈哈�?^ω^)�?br>
前几个星期和��州大学的AedkyCion向老师甌��出比赛，我从来都没出�q�，有点��紧张，没想到老师一下就�{�应了，定在5�?��L(f��ng)��老菜鸟杯�l�我们出�Q�暂�?题，每�h四题�Q�到现在我只��Z��两题半，�q�进度太慢都有点不好意思了。。。前几天又有��州师范大学要求我们出题�Q�老师把�Q务交�l�了我们�Q�亦�U�飞�Q�周天��(d��ng)�Q�纪哥和我，哈哈�Q�我分配��C��道模拟题和一道搜索题。。。这个的�?�?号前�q�有5道题目要出。。可有的好忙�?br>接下来还有期中考试�Q�宁波的全国邀(g��)误��。所以今天晚上我又选择通宵(¯�H?#175;�Q�口��_(d��)��争取把题目赶出来�Q�还有复�?f��n)下物理。。话说宁波邀(g��)误��?4~26��P��我们的英语和数学考试也在�q�几天，哈哈�Q�逃过一劫，。。�?br>
接下来这�D�忙��的时期渡过之后�Q?月又可以开始疯狂的AC了~~前些日子做了USACO�Q�超�U�好玩，有点像闯��x��式的。过了一些题后开��N��度更高的题目和算法给你学�?f��n)~~昨天刚刚创到�W�二养I��一共有六关�Q�到后边�q�很多wf的题都出来了�Q�超有挑战，我一定要全部��d��。�?br>遇到�q�个OJ后我曄��q�L��以后能写一个新模式的OJ�Q�其实就是借鉴USACO�Q�升�U�打怪模式，哈哈�Q�打�?A完题)得到�l�验��|��可以��M��技能书(��法)�Q�然后开放新题目�Q�一�U�一�U�来�Q�还有很多附属功能。。。当然这只是初步假想而已。。我现在除了AC什么都不会(x��)�Q�更何谈做个新OJ。。不�q�既焉��择了AC�Q�必定会(x��)攑ּ�其他很多东西�Q�所以我可以说是背水一战，攑ּ�其他一门心思AC�Q�一定要在这斚w��拿到一个非常好的成�l�才对得��h��的大学四�q�。。�?br>
队内6轮PK完后�l�于开始组队选队友了�Q�由于最后一轮RP爆发�Q�被我赚了很多分敎ͼ�排名一下上升到�W�二�Q�本是纪哥选我的变成了我选纪哥，哈哈�Q�还选了��丽姐，她可�?a >3.8�?/a>后全国闻名的人物哦~~一哥一“�?#8221;的组合，虽然我和��丽姐第一�ơ参加省赛，但是我信心十��I��跟着曄��拿过银牌的纪哥省赛一定是要冲金夺银的~~PK�l�束的那个晚上周天��(d��ng)�q�和我谈�q�~~说有��Z��(x��)希望暑假能组�?#183;~啊哈�Q�我真是兴奋��x��。。他可是我在队内最希望�l�队的大牛，�q�队后就一直钦佩他�Q�现在竟然有��Z��(x��)能在以后一起�ƈ肩作战，一起参加全国赛�Q�冲击金牌，参加wf~~哈啊哈~\(≧▽�?/~�Q��想中。。）(j��)

期待接下�ȝ��l�队PK�Q�省赛，暑假集训�Q�全国赛~~~当然�Q�还有world final �Q�！

AC之旅中的酸甜苦��G��׃��再细说了�Q��L��看到很多��AC多么多么苦，很多��“别�h只看到AC所得到的荣耀�Q�而看不到我们背后训练的艰�?#8221;
其实不是�q�样的，臛_��我不是这��P��AC�Ҏ(gu��)��而言不是一�U�负担，不是一�U�压力，而是一�U�娱乐，一�U�生�z�L��式，已经�?f��n)惯了实验室的生�z�，可以除了吃饭睡觉都在实验室，�q�一切都是快乐的~~^_^当然�Q�AC有成果的话会(x��)更加的快乐~~~O(∩_∩)O哈哈~

一直奔跑下��d��~~A Crazy Man

shǎ�?/a> 2009-04-16 17:08 发表评论

Wed, 15 Apr 2009 04:24:00 GMT

/*
ID:notonlysuccess
LANG:C++
TASK:checker
*/
#include<stdio.h>
int cnt;
int ans[3][13];
int jilu[13];
int n,maxn;
void dfs(int row,int ld,int rd,int deep)
{
    int i,buf,pos;
    if(deep == n)
    {
        if(cnt<3)
        {
            for(i=0;i<n;i++)
                ans[cnt][i] = jilu[i];
        }
        cnt ++;
        return ;
    }
    buf = row | ld | rd;
    for(i=0;i<n;i++)
    {
        pos = 1<<i;
        if((buf & pos) == pos)
            continue;
        jilu[deep] = i+1;
        dfs(row+pos,(ld+pos)<<1,(rd+pos)>>1,deep+1);
    }
}
int main()
{
    freopen("checker.in","r",stdin);
    freopen("checker.out","w",stdout);
    int i,j;
    scanf("%d",&n);
    cnt = 0;
    maxn = 1<<n;
    dfs(0,0,0,0);
    for(i=0;i<3 && i<cnt;i++)
    {
        for(j=0;j<n-1;j++)
            printf("%d ",ans[i][j]);
        printf("%d\n",ans[i][j]);
    }
    printf("%d\n",cnt);
    return 0;
}

哈哈�Q�hdoj上超大数据量的N皇后也过了。�?br>

#include<stdio.h>
int cnt;
int n,maxn;
void dfs(int row,int ld,int rd)
{
    int buf,pos;
    if(row == maxn)
    {
        cnt ++;
        return ;
    }
    buf = row | ld | rd;
    for(pos = 1;pos <= maxn;pos <<= 1)
    {
        if((buf & pos) == pos)
            continue;
        dfs(row+pos,(ld+pos)<<1,(rd+pos)>>1);
    }
}
int main()
{
    int i,pos;
    while(scanf("%d",&n),n)
    {
        cnt = 0;
        maxn = (1<<n) - 1;
        for(i=0;i<n/2;i++)
        {
            pos = 1<<i;
            dfs(pos,pos<<1,pos>>1);
        }
        cnt <<= 1;
        if(n&1)
        {
            pos = 1<<i;
            dfs(pos,pos<<1,pos>>1);
        }
        printf("%d\n",cnt);
    }
    return 0;
}

shǎ�?/a> 2009-04-15 12:24 发表评论

Sun, 12 Apr 2009 16:59:00 GMT

最后一轮PK�Q�抱�q�轻村ց�做的心态去比，�l�果��Z��意料�Q�哈�?br>�q�次的题目没有以前那么水�Q�每道都是要动点��脑�{�的

http://acm.tju.edu.cn/toj/showp3256.html
�q�是dfs�Q�我惊讶别�h暴力深搜竟然都能�q�。。。我�?br>要是我来处数据的话暴力深搜一定爆掉。�?br>我是用hash[ landscapes ][ (total length)%k ][ Lth ]来剪�?br>�q�样的话最多也��搜�?0*50*50个状态。。。很好的设计。。嘿嘿又往自己�怸�贴金�?br>
http://acm.tju.edu.cn/toj/showp3257.html
不太清楚是什么算法，不过我程序里用的数组名是DP。。。当时下手的时候想写成DP的，�l�果��׃��伦不�c�L��了XD
不管用什么数�l�名�Q�DP也好�Q�HH也好�Q?span style="COLOR: red">�?/span>反正记录下每个字母后边的和该字母相同的字母个�?br>�?/span>然后用一个minch变量��L��一遍字�W�串�Q�不断更新minch(看到�q�个变量名应该知道怎么更新的吧)同时记录下标minch的下标pos
�?/span>扫到后边相同字母数是0的时候就比较一下，看minch和这个字母谁��?br>{
如果(minch��?
的话��p��出minch同时下标跛_��C��前记录的pos;
如果(minch�?
的话��p��个字母，然后�l�箋�?
再minch更新为最�?br>}
不要忘记吧已�l�输出的字母hash掉哦

http://acm.tju.edu.cn/toj/showp3258.html
一看就是技巧题目。。看成是环，排序后找��C��个最大的删除区间掉。。然后看看剩下的所能得到的�l�对值最��?br>注意要分�c�讨论。。比赛的时候被sample骗掉。。以为就是中间对�U�的只考虑了一�U�情况，其实有四�U�。。。�?br>错了好多遍。。。�?br>
http://acm.tju.edu.cn/toj/showp3259.html
��单题�Q�晒法晒下然后再预处理一�?br>
http://acm.tju.edu.cn/toj/showp3260.html
图论�ѝ��。看到就晕了。。。向来没有做�q�图论的题，最��q��也就是二分图的最大匹�?br>完全匚w��都还没有学过。�?br>没办法。。抱着一�U�希望来个强剪枝试试。。。结果不出所料TLE了。。。�?br>
两个��时的时候就��Z��前四道暂时第一了，Luke King��Z��三道�Q�而我的罚时太多（因�ؓ(f��)心态比较放松，所有一有思�\写好了就提交�Q�W(xu��)A了修改一下又提交又WA�Q�其实很多罚时是不必要的�Q�。。囧了。所�?a >Luke King只要在比赛前出题��p��过我。A是比较简单的
果然�Q�在最后十分钟��Z��A��过我了�Q�我在最后十分钟提交了E�Q�结果是��时。�?br>
赛后得知Luke King�?9的。。。天�z�市(j��ng)赛第六。。高中生�ѝ��。Orz

shǎ�?/a> 2009-04-13 00:59 发表评论

Sun, 12 Apr 2009 16:24:00 GMT

http://acm.tju.edu.cn/toj/showp3251.html
水题。。。瞬间被人秒的。。drogon大大说算日期和星期的有个什么公式，学习(f��n)
http://acm.tju.edu.cn/toj/showp3252.html
深搜�Q�每�ơ搜到四个区域的��g��持一下，然后枚�D12�U�可能取最��?br>http://acm.tju.edu.cn/toj/showp3253.html
比赛的时候想了半个小时的矩阵构造。。。后来发�?^20一定有循环节。用未压�~�保存了状态然后hash
�l�果最后半个小时提交的时候电(sh��)脑蓝屏（三教的破�?sh��)脑�Q�，开��原后代码全无
启动�q�启动了10分钟。�?zh��n)�剧收场，人品不好啊。。�?br>http://acm.tju.edu.cn/toj/showp3254.html
模拟加贪心。简单题
http://acm.tju.edu.cn/toj/showp3255.html
比赛的时候时间都花在了C上边�Q�没旉��看。。�?br>

�q�场比赛只有两道水题�Q�所有我做了三道也都排在了前�?nbsp; %>_<% 要是�?sh��)脑不蓝屏。。�?

shǎ�?/a> 2009-04-13 00:24 发表评论