C++博客-A Crazy Man

新博客

shǎ崽 — Mon, 16 Nov 2009 11:45:00 GMT

notonlysuccess

这个博客不用了，一些还好的资料会慢慢搬到新博客
谢谢朋友们继续关注

shǎ崽 2009-11-16 19:45 发表评论

时限一小时

shǎ崽 — 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ǎ崽 2009-09-10 15:13 发表评论

Asia Regional Contest

shǎ崽 — Wed, 19 Aug 2009 05:35:00 GMT

暂无

shǎ崽 2009-08-19 13:35 发表评论

PKU——DP专辑

shǎ崽 — Wed, 29 Jul 2009 07:18:00 GMT

1037 A decorative fence
1042 Gone Fishing
1062 昂贵的聘礼
1074 Parallel Expectations
1093 Formatting Text
1112 Team Them Up!
1143 Number Game
1160 Post Office
1178 Camelot
1179 Polygon
1180 Batch Scheduling
1187 陨石的秘密
1189 钉子和小球
1191 棋盘分割
1192 最优连通子集
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 放苹果
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ǎ崽 2009-07-29 15:18 发表评论

状态DP~

shǎ崽 — Sun, 12 Jul 2009 08:40:00 GMT

http://acm.sgu.ru/problem.php?contest=0&problem=222
这是入门题，数据较大，需要记忆化搜索

http://acm.pku.edu.cn/JudgeOnline/problem?id=1321
上题的提高版，不过数据超小，爆搜都能过

http://acm.sgu.ru/problem.php?contest=0&problem=223
先要预处理出一行中的全部可行状态~
然后DP的时候巧妙的运用位运算进行状态的判断和转移
状态dp中位运算的巧妙运用会大幅度提高程序的效率和帅气程度

http://acm.pku.edu.cn/JudgeOnline/problem?id=1185
非常经典的状态DP，由于攻击范围是两格，所以要保持两个状态，有人用三进制压缩，我觉得太烦了(不能使用飘逸的位运算）
但是[101][2^10][2^10]得状态太大，考虑到2^10中有很多情况是不可到达的
计算下当m=10的时候最多60个合法状态，所以我开了[101][60][60]的数组记忆化DP过了

http://acm.hdu.edu.cn/showproblem.php?pid=2640
teddy大牛的题目，和上题差不多，不过不能重叠放，所以处理比上题烦很多
同样2^8里有很多不可到达的情况，最多之有13种
所以我开[101][13][13]的数组15ms就过了，哈哈
这就好像是两次状态压缩
最近的DP题目感觉到把很多不可到达的状态压缩掉效率会提高超多~也可能让程序从TLE MLE变成AC~

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

http://acm.hdu.edu.cn/showproblem.php?pid=2280
要求用最少的1铺满所有的空格，其中3是没用的(可以用两个5代替)，化简之后使用的方块和上一题一样，一样的预处理后
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ǎ崽 2009-07-12 16:40 发表评论

神奇的舞蹈~~Dancing_Links

shǎ崽 — Thu, 09 Jul 2009 17:17:00 GMT

整了一天的跳舞链，资料可以在网上搜到
http://sqybi.com/works/dlxcn/
惊讶于它做深搜的时候可以达到如此强劲的剪枝
下午的时候不看网上的模板自己写了一个，自认为是比模板少了一个for循环，但是写好后才发现没有模板的启发式搜索的效率，就这样活生生的TLE了，浪费了我好几个小时啊~~%>_<%~~
晚上只好写用模板的方法，写了一个后瞬间过了，感觉难度也不过尔尔
但这个舞蹈链可是容易解答却很难看出的主，构造舞蹈链还是关键
献上我的模板~~
最简单的舞蹈链，效率仅比hhanger差，可以跑240MS,不过后来我测出了一些数据的结构，暴力优化到了124MS，哈哈哈(得意一下)~~~
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个方块把图完美覆盖全部搜完然后最小的个数
思路：行方块，列单位小格子，矩阵中1是方块所能覆盖的小格子

http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1507
(重复覆盖问题) 重复覆盖的模板题
献上模板

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
(重复覆盖问题)
这题无法转化成完美覆盖，所以remove和resume的时候要变化一下，但是这样还是会超时我看了标程才算AC。唉。。
主要是里边的一个A*的h函数是在是太犀利了，一下从TLE到了46MS。。。。剪枝还是非常重要的
思路：行是雷达，列是城市，矩阵中1是雷达覆盖城市

http://acm.fzu.edu.cn/problem.php?pid=1686
(重复覆盖问题)
这道题也同上道一样是："在0-1矩阵中选取最少的行，使得每一列最少有一个1" 这个模型
所以和上一道建表一样建好之后套上模板就AC了~
思路：行是枚举在每个位子放魔法，列式怪物个数(最好给怪物标记个id)，矩阵中的1是在这个地方放魔法是否能达到目标怪物

http://www.spoj.pl/problems/NQUEEN/
(重复覆盖问题)
N皇后问题，打的时候没能想到怎么转化成精确覆盖，只是用了dancing links的思想，傻傻的花了一个晚上完成了一个超级复杂的米字型链表(重复覆盖)，开始的时候启发式函数S没有更新，导致没有发挥效用，结果本例30个0的数据都跑不出来，还以为是想法出错了，睡觉前在床上想到，改了一下，效率呈指数级增长，50个0的瞬间跑出来，在state里排到第一，哈哈

(精确覆盖问题)
今天CH教我怎么将之转化成十字链表的精确覆盖，但是矩阵是(n*n)*(6*n-2)比米字型链表n*n的大了好多倍，交了一下，跑了1s，效率不如米字型的
其思路是：行是格子数n*n,列是(行+列+正逆对角线)，矩阵中的1是放在各自上所占得行，列，对角线
不需要全部搜完，只要初始皇后+dfs的深度达到n(放了n个皇后)就return true

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

当然，此题出题人的意图是二分匹配。。。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=31
http://acm.pku.edu.cn/JudgeOnline/problem?id=1084
(重复覆盖问题)
这题要不和我说是dancing links 我还真看不出来
此题建表超烦，虽看出来但是建表就花了我一个半小时，还迫我使用上行的头节点，以前我只是用列的头节点，努力了很久，过了sample就AC了，烦就烦在建表上
思路：行是火柴棒数，列是完美时能构成的矩阵数目，矩阵中的1是列矩阵是否包含行火柴

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
(精确覆盖问题)
经典的数独，看了论文才明白怎么覆盖，9*9*9的行 (9+9+9)*9+9*9的列
思路：行是81个小格*每个格子的9个可能数字，列是81个小格+9行9列9小块的9个数字
每列确切的有4个1
开始读入的时候吧确定的数字的头上的1删掉可以很大的提高效率

http://acm.hdu.edu.cn/showproblem.php?pid=2518
超爽的dancing links
这题所有的方块可以旋转，这点超烦~
我差点就人肉代码了，枚举所有状态，不过最后我还是修改成不人肉的办法
只有几组答案，用dancing links暴力跑出所有组合后然后打表，嘿嘿，我就是这么猥琐的过的
72*所有摆放数~
思路：60个格子加12个方块作为列，所有摆放的方案数作为行

好了，A光上述题目dancing links的学习也告一段落，这个舞蹈是在是优美，以后出题一定要谱一曲经典的舞蹈~~

2009.9.6
发现dancing links还能做最大团
http://acm.hdu.edu.cn/showproblem.php?pid=1530
转化成补图后再建表。。。不过效率很低，跑了6000+MS，全部搜完找一个最大的，还没有更优的办法优化，尝试过二分再写个h函数未果。。。

10.15
http://acm.hdu.edu.cn/showproblem.php?pid=3156
和雷达类似，不过放radar的点要求出来，也是先二分枚举半径，然后利用两个点和半径确定一个圆心C(n,2)，可以证明如果放其他地方一定没这个圆心优

shǎ崽 2009-07-10 01:17 发表评论

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

shǎ崽 — 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
好点经典的一道题目，做了半天都做不出来
后来到网上看了解题报告才明白（解题报告网上有，我就不再出说明了）是n^2的算法
我在想，每次都遍历一遍找最大权值的点会不会太浪费时间，如果用堆取出权值最大的点效率就会有很大改进，变成n*log(n)了
但是最大权值的父亲节点也要从堆中取出，这有点麻烦
结合昨天ZOJ月赛比赛中自创的可以取出任意节点的二叉堆，记录位子来实现，想到了方法，多方试验之后果然成功了
在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。。简洁是简洁，但效率不高

#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ǎ崽 2009-06-29 16:30 发表评论

概率题总汇

shǎ崽 — Tue, 19 May 2009 05:48:00 GMT

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

http://acm.hdu.edu.cn/search.php?field=problem&key=2262
E(now) = （E(NEXT1) + E(NEXT2) +...+E(NEXTn))/n + 1
每个相邻点建方程，注意起点可以走到得边才能建方程，不然会导致无解
先floodfill找到起点可以走到得点，然后建方程，最后仍个高斯消元模板解把答案解出来

http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1423
同上一道一摸一样的题

http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1317
这个需要构造，相隔位子数的转换
想在相邻n，都向内飞的话n-2，都想外飞n+2，一个向左一个向右的话就保持n不变，所以有下列方程
E[n] = E[n+2]/4 + E[n-2]/4 + E[n]/2 + 1

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2619
此题极度郁闷，转移方程已经推出来了，却因为精度问题过不了
第四个sample我试了三个模板，出来的答案都不一样。。。。。
用java可过
http://acm.hdu.edu.cn/showproblem.php?pid=3058
上体升级版，变成了多串匹配，建Tire图的基础上进行转移
一样存在精度问题，用java可过

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2837
因为电梯有上有下，我索性就把楼的高度加倍 n = n * 2 - 2
那sample来说，0~10是向上的，10~20是向下的，20就是0，向上的话又变成1开始
在第7和第13层会碰到鬼(我从0层开始，所以每个量都要-1)
这样就可以得到转移方程
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
这题很早就开始想了，现在才会做，公式如下：
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;

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

献上第一次写的高斯消元模板
若返回时false则无解

/**************************************************
*    mat里建好方程,增广矩阵    n*(n+1)
*    传入方程个数
*    答案保存在mat[i][i]中
**************************************************/
#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ǎ崽 2009-05-19 13:48 发表评论

强连通。。。。

shǎ崽 — Sun, 17 May 2009 12:36:00 GMT

很好玩的算法
强连通+缩点可以把一块点看成一个点，大大加快算法。还有一些无法解决的问题也可以用这个来解决
前几天在林学院做题的时候胡搞搞出来了，哈哈
今天又A了一道
最近对图对树越来越有感觉了

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ǎ崽 2009-05-17 20:36 发表评论

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

shǎ崽 — Fri, 15 May 2009 02:01:00 GMT

不同时刻提交不限不同的结果。。。。学习了。哈哈
比赛时候是在没有办法的时候又多了一招
付代码

#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ǎ崽 2009-05-15 10:01 发表评论

树形DP

shǎ崽 — 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ǎ崽 2009-05-11 20:39 发表评论

花了一天时间写的一个很挫很挫的大数模板

shǎ崽 — Wed, 06 May 2009 10:37:00 GMT

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

shǎ崽 2009-05-06 18:37 发表评论

浙江省历年省赛题+解析

shǎ崽 — 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
会对每一道做过的题做一个简单的分析，如果有出错或者不理解可以于我交流

2104 Let the Balloon Rise Zhejiang Provincial Programming Contest 2004
数据很小，遍历一下，找到就++，没有的话就算新的
2105 Number Sequence Zhejiang Provincial Programming Contest 2004
找循环节，开hash[7][7]来找，hash前一个和后一个
2106 Tick and Tick Zhejiang Provincial Programming Contest 2004
当年应该是金牌题吧，时间是连续的，不能一秒一秒分开来计算
我是根据题目联立三个不等式方程，然后解出交集
2107 Quoit Design Zhejiang Provincial Programming Contest 2004
最近点对，二分的思想，据说数据结构书上就有。。。
2108 Elevator Zhejiang Provincial Programming Contest 2004
简单模拟题，求出上升和下降的层数
2109 FatMouse' Trade Zhejiang Provincial Programming Contest 2004
按性价比排序后贪心
2110 Tempter of the Bone Zhejiang Provincial Programming Contest 2004
深搜，加个奇偶性剪枝
2111 Starship Troopers Zhejiang Provincial Programming Contest 2004
神题，不会。。。据说是树形DP
5.13补充：当时看着是的做也不敢做的神题，前几天学习了熟悉树形DP后练习了几道题目再来做这题发现一点都不难
树形+背包+临街表建图可以轻松A掉此题

2474 World Goes Round Zhejiang Provincial Programming Contest 2005
这题数据量好大，n=10，记得在北师大比赛的时候做过一个3*3的八数码也是这样转动规则，当时是预处理直接秒掉的
这道状态太大，变身为神题了，不会

不是求最优解，所以我猜测应该是构造出一种方法让它转到目标状态
//我想是不是可以降维，拼好最左边和最上边就可以降一维了。。
至于怎么构造没有想出来。。。。
尚未做出
2475 Benny's Compiler Zhejiang Provincial Programming Contest 2005
判断有向图成环，用拓扑排序，错了N遍，我都怀疑是不是我的拓扑写错了。。
后来试了一下原来有恶心数据，Ai == Bi的时候这样的数据不要计算，不然就自己成环了。
2476 Total Amount Zhejiang Provincial Programming Contest 2005
模拟一下，都不用大数加法，直接用long long就够了，输出的时候分段输出
2477 Magic Cube Zhejiang Provincial Programming Contest 2005
题目说不超过5步，可以用迭代加深搜索，其实题目意思很直白，就是这道题目很难模拟。
把魔方的转模拟出来这题目也就做出来了。。
我把每一种转都计算出来写进表里，然后按照这个表转就OK了
2478 Encoding Zhejiang Provincial Programming Contest 2005
遍历一遍比较当前字符和前一个字符就好
2479 Cover the Rectangular Ground Zhejiang Provincial Programming Contest 2005
从最左下角的点开始dfs，每次先判断能不能放上，然后找出当前最左下角的点再dfs
这样很暴力。。最坏的情况算不来，大概有20!次。。。我晕，一直TLE
后来我试了下数据，倒是是我的程序真的效率很低，还是只有一些数据都跑不出
经过多次WA和TLE的测试发现只要有解得数据我都能跑出来，无解的就直接搜到死了
于是我定义如果深搜次数超过100000就直接跳出，无解
结果就AC了。。。。效率还很高，由于内存原因拍在第二
唉，比赛的时候如果能这样AC的话就太RP了。。。
。。求正解。。
2480 Simplest Task in Windows Zhejiang Provincial Programming Contest 2005
数据量小，直接水掉，从后往前比较for(i = n- 1; i >= 0 ; i --)，找到符合的跳出，最后输出下标
2481 Unique Ascending Array Zhejiang Provincial Programming Contest 2005
排序后输出

2736 Daffodil number Zhejiang Provincial Programming Contest 2006, Preliminary
水题
2737 Occurrence Zhejiang Provincial Programming Contest 2006, Preliminary
题目看清楚后暴力比较久可以
2738 The Kth BST Zhejiang Provincial Programming Contest 2006, Preliminary
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
推了一个下午啊。。。。。竟然WA。。。。。极度郁闷。。。。。

吃饭回来终于AC了。。。。再郁闷，原来是我对BST的理解有误，后来纪哥纠正了，就这样陷入了误区N久。。。。不值得啊。。。
2739 Color Quantization Zhejiang Provincial Programming Contest 2006, Preliminary
尚未做出
2740 Message System Zhejiang Provincial Programming Contest 2006, Preliminary
用并查集做，判断是树还是森林还是图

2741 Offside Zhejiang Provincial Programming Contest 2006, Preliminary
很脑残的模拟题，我却脑残的错了N编。。。。。
2742 Toy Bricks Zhejiang Provincial Programming Contest 2006
尚未做出
2743 Bubble Shooter Zhejiang Provincial Programming Contest 2006
先foldfill一下，把连起来的hash掉，然后从最上边每个点开始foldfill，看还有几个留下
2744 Palindromes Zhejiang Provincial Programming Contest 2006
从回文串的性质上找规律，每个点向左右延长数回文串个数
2745 01-K Code Zhejiang Provincial Programming Contest 2006
恶心的推推题，我的方法一定不是最简单的，我开了四维数组还转移状态
分别存的是：
dp[0和1相差几位，最高到达过，最低到达过，n]
这是很烂的方法，我想了很久才想出来，实在想不出更好的了
2746 Rank the Teams Zhejiang Provincial Programming Contest 2006
尚未做出
2747 Paint the Wall Zhejiang Provincial Programming Contest 2006
离散化+hash即可，有点暴力，正解是线段树
2748 Free Kick Zhejiang Provincial Programming Contest 2006
恶心的集合题，开始没有看到straight "WALL"构造出一种最优解，结果WA了
改了之后也一直WA，错了无数次后修改了下求夹角的方法，本来有atan，改成acos竟然AC了~~
思路：
先求出没有wall时候的夹角，然后减去守门员的范围，再根据剩下的角度来求出人数
2749 Polarium Zhejiang Provincial Programming Contest 2006
很好玩的一道题目，有人竟然能TLE 1000+次，而且连续了半年。。Orz一下
我跑的比较暴力，效率挺低的
思路：
首先枚举最后的答案：即每行的黑白情况
然后根据这个答案重新画出一张地图，每个能走的点(除了边界点)都只能走且只走一次，然后进行DFS
走到终点的时候判断下是否符合条件就AC了(开始的时候我先判断走完点再判断最后一点是否是终点，结果超时了)
2750 Idiomatic Phrases Game Zhejiang Provincial Programming Contest 2006
构造出最短路，每个串的最先4个和最后4个就是起点和终点，2^16个点，1000条路
我用邻接表+堆+bfs加速优化10ms

2849 Attack of Panda Virus Zhejiang Provincial Programming Contest 2007
按level最小和type最小的优先队列BFS一下
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,三维(每组牌的价值)加滚动数组能轻松AC
2853 Evolution Zhejiang Provincial Programming Contest 2007
矩阵题，有点卡时间
我的结构体模板200*200开不下，于是我升级了我的模板，换了一个全局矩阵
题目意思理解对套个矩阵模板就能过了
2854 Fish and Her Bowl Zhejiang Provincial Programming Contest 2007
尚未做出
2855 Google Map Zhejiang Provincial Programming Contest 2007
用所给公式+递归解决
2856 Happy Life Zhejiang Provincial Programming Contest 2007
无论什么状态都一定能构造出可行解的，所以只要while(1)把和小于0的那行变换符号，一直都满足条件
2857 Image Transformation Zhejiang Provincial Programming Contest 2007
水题

2965 Accurately Say "CocaCola"! The 5th Zhejiang Provincial Collegiate Programming Contest
数据小，暴力下就好，数据大的话可以数学归纳或者暴力看下规律
2966 Build The Electric System The 5th Zhejiang Provincial Collegiate Programming Contest
傻傻的最小树
2967 Colorful Rainbows The 5th Zhejiang Provincial Collegiate Programming Contest
正解说是半平面交
我是用一个栈，先按b从大到小排序，如果然后遍历一下，能出现的就放进栈里，能把前面的覆盖掉就把栈里的线段拿出
正半轴，负半轴做两次，再处理一下小细节就好了
2968 Difference Game The 5th Zhejiang Provincial Collegiate Programming Contest
我先把A数组和B数组的数全部保存C数组里，然后排序
再遍历C数组,i = 0 to n*2
i左边的为B,右边的为A，然后算出到达这个状态A到B的个数AB和BA
根据这两个数算出最小的花费，X = Min(AB,BA)，Y = |AB - BA|，Ci = X * Y* (Y - 1)；
如果比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
模拟下
2972 Hurdles of 110m The 5th Zhejiang Provincial Collegiate Programming Contest
按剩下的能量DP
2973 Intelligent Pouring Robot The 5th Zhejiang Provincial Collegiate Programming Contest
超烦的模拟题
尚未做出
2974 Just Pour the Water The 5th Zhejiang Provincial Collegiate Programming Contest
暴力加循环节能过，正解是矩阵，
K == 0的时候常常会被忽略，处理一下就好
2975 Kinds of Fuwas The 5th Zhejiang Provincial Collegiate Programming Contest
n^3的算法，枚举任意两行C(2,n)，遍历列n，找到相同的个数x，res+=(x-1)*x/2;
2976 Light Bulbs The 5th Zhejiang Provincial Collegiate Programming Contest
枚举平面上每一个点取最大值

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ǎ崽 2009-05-02 21:10 发表评论

二分图的完美匹配

shǎ崽 — Tue, 21 Apr 2009 06:32:00 GMT

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

下边是http://acm.hdu.edu.cn/showproblem.php?pid=1533 的AC代码

//////////////////////////////////////////////////////////////////////////
//二分图的完美匹配，Kuhn－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)//找增广路径
{
    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++)//现阶段已经匹配的路
        {
            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++)//当前的图是否能全部匹配
        {
            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]);//找到一条没建的边的最小值
                }
            }
            for(i=0;i<n;i++)//根据这个边来进行松弛
            {
                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;
}

//读入建图
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ǎ崽 2009-04-21 14:32 发表评论

又学了一招，矩阵的比较

shǎ崽 — Mon, 20 Apr 2009 07:47:00 GMT

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

shǎ崽 2009-04-20 15:47 发表评论

图论~~要大干一场了--Author McFn

shǎ崽 — Fri, 17 Apr 2009 03:10:00 GMT

打星号的表示个人认为比较经典，或是算法，构图比较好的题目

1062* 昂贵的聘礼枚举等级限制+dijkstra
1087* A Plug for UNIX 2分匹配
1094 Sorting It All Out floyd 或拓扑
1112* Team Them Up! 2分图染色+DP
1125 Stockbroker Grapevine FLOYD
1135 Domino Effect 最短路
1149* PIGS 网络流
1161* Walls floyd
1201 Intervals 差分约束
1236* Network of Schools 强联通
1251 Jungle Roads MST
1273 Drainage Ditches 最大流
1274 The Perfect Stall 2分匹配
1275* Cashier Employment 差分约束
1325 Machine Schedule 2分匹配(最小点覆盖)
1364 King 差分约束
1422 Air Raid 2分匹配
1459 Power Network 网络流
1466 Girls and Boys 2分图(最大独立团)
1469 COURSES 2分匹配
1502 MPI Maelstrom floyd
1511* Invitation Cards 最短路
1637* Sightseeing tour 混合图欧拉回路-网络流
1716 Integer Intervals 差分约束
1724* ROADS 最短路-拆点
1780* Code 欧拉回路
1789 Truck History 最小生成树
1797 Heavy Transportation 最小生成树
1847 Tram 最短路
1904* King's Quest 强联通
1949 Chores 最短路
2060 Taxi Cab Scheme 2分匹配
2075 Tangled in Cables 最小生成树
2112 Optimal Milking 网络流
2125 Destroying The Graph 最小割
2135 Farm Tour 费用流
2139 Six Degrees of Cowvin Bacon floyd
2226 Muddy Fields 2分匹配
2230 Watchcow 欧拉回路
2239 Selecting Courses 2分匹配
2267* From Dusk till Dawn or: Vladimir the Vampire 最短路
2289 Jamie's Contact Groups 网络流
2337 Catenyms 欧拉通路
2349 Arctic Network 最小生成树
2369 Genealogical tree 拓扑序
2387 Til the Cows Come Home 最短路
2391* Ombrophobic Bovines 最大流
2394 Checking an Alibi 最短路
2396* Budget 网络流
2421* Constructing Roads 最小生成树
2446 Chessboard 2分匹配
2455 Secret Milking Machine 网络流
2457 Part Acquisition 最短路
2472 106 miles to Chicago 最短路
2485 Highways 最小生成树
2516 Minimum Cost 费用流
2536 Gopher II 2分匹配
2553* The Bottom of a Graph 强联通
2570 Fiber Network floyd
2584 T-Shirt Gumbo 网络流
2594* Treasure Exploration 2分匹配
2723 Get Luffy Out 2-sat
2724 Purifying Machine 2分匹配
2728 Desert King 最优比例生成树
2749* Building roads 2-sat
2762 Going from u to v or from v to u? 强联通
2949* Word Rings 差分约束
2983 Is the Information Reliable? 差分约束
2987 Firing 最小割(求解正确性??)
3020 Antenna Placement 2分匹配
3041 Asteroids 2分匹配
3072* Robot 最短路
3160 Father Christmas flymouse 强联通
3164 Command Network 最小树形图
3169 Layout 差分约束
3177 Redundant Paths 双联通分量
3189 Steady Cow Assignment 网络流
3204 Ikki's Story I - Road Reconstruction 最大流
3207 Ikki's Story IV - Panda's Trick 2分图
3216 Repairing Company 2分匹配
3228 Gold Transportation 网络流
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分匹配
3352 Road Construction 桥
3439 Server Relocation 最短路
3463 Sightseeing 最短路
3469 Dual Core CPU 最小割
3487 The Stable Marriage Problem 稳定婚姻
3522 Slim Span 最小生成树
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 差分约束或拓扑
3692 Kindergarten 2分匹配
3694 Network 无向图缩点

就把上面的作为图论学习的题目了~

shǎ崽 2009-04-17 11:10 发表评论

半年AC生涯，仅以此文纪念

shǎ崽 — Thu, 16 Apr 2009 09:08:00 GMT

834064 2008-10-16 10:07:01 Accepted 1000 0MS 0K 105 B C shǎ崽

去年10月16号，A了第一道A+B,我的AC生涯也正是开始了

今天是4月16号，正好半年，提交了三道水题。。。在HDU的AC量达到了900.。。

shǎ崽

A New Start~！

900

1888

47.67%

本来想向yifenfei大大一般，在纪念日达到1000的AC量
可惜力不从心，今日比赛甚多，到在其他OJ上刷题，hdoj上的水题又渐少，烦事缠身，无法完成半年1000的目标~~只好用900来代替一下....XD

遥想半年前接触ACM后,天天跑机房,机房不开门就网吧,还曾经有一晚在网吧通过宵,第二天集训队的学长们看到我半夜的提交的记录以为我带了笔记本+N块电板，后来知道我是在网吧通宵AC的，更加惊讶，天涯还曾出了一道shǎ崽 OrOrOrOrz的题目。提到Acmer in HDU-ACM team are ambitious, especially shǎ崽, he can spend time in Internet bar doing problems overnight.哈哈，笑死我了。。这题我特地写了很多优化刷到了第一31MS，哈哈，别人恐怕很难超越了╮(╯_╰)╭

这个学期开始后lcy教练就常常提醒我要花一段时间去攻克一门算法，从最开始的最小生成数，最短路，到了树状数组，字典树，离散化，这几个星期又有搞定图论的目标，可以说没有lcy教练的督促我进步没有这么明显，毕竟不学算法只刷水题的话是没有提高的。。

接着就是进队，放弃了一切时间AC，寒假更是没有出去玩过，上个学期都是在自己做题，这个学期就都是在PK，PK比做题好玩多了，能和高手切磋，挑战一些平时不敢做的题目，运气好的话，RP爆发下还能拿到前几的名次炫耀一番。。
大大小小经历过了很多场PK，集训队内部的单人PK就有4场，还有几乎每日都有的校外比赛，真是赛事多发期。。上个星期细算一下至少做了7场比赛吧~~这个比赛密度虽然很高，但是人也越比越兴奋~~哈哈↖(^ω^)↗

前几个星期和福州大学的AedkyCion向老师申请出比赛，我从来都没出过，有点小紧张，没想到老师一下就答应了，定在5月2号的老菜鸟杯给我们出，暂定8题，每人四题，到现在我只出了两题半，这进度太慢都有点不好意思了。。。前几天又有福州师范大学要求我们出题，老师把任务交给了我们，亦纷飞，周天涯，纪哥和我，哈哈，我分配到两道模拟题和一道搜索题。。。这个的话5月1号前还有5道题目要出。。可有的好忙了
接下来还有期中考试，宁波的全国邀请赛。所以今天晚上我又选择通宵(¯﹃¯）口水，争取把题目赶出来，还有复习下物理。。话说宁波邀请赛事24~26号，我们的英语和数学考试也在这几天，哈哈，逃过一劫，。。。

接下来这段忙碌的时期渡过之后，5月又可以开始疯狂的AC了~~前些日子做了USACO，超级好玩，有点像闯关模式的。过了一些题后开放难度更高的题目和算法给你学习~~昨天刚刚创到第二关，一共有六关，到后边连很多wf的题都出来了，超有挑战，我一定要全部攻克。。
遇到这个OJ后我曾经幻想以后能写一个新模式的OJ，其实就是借鉴USACO，升级打怪模式，哈哈，打怪(A完题)得到经验值，可以去买技能书(算法)，然后开放新题目，一级一级来，还有很多附属功能。。。当然这只是初步假想而已。。我现在除了AC什么都不会，更何谈做个新OJ。。不过既然选择了AC，必定会放弃其他很多东西，所以我可以说是背水一战，放弃其他一门心思AC，一定要在这方面拿到一个非常好的成绩才对得起我的大学四年。。。

队内6轮PK完后终于开始组队选队友了，由于最后一轮RP爆发，被我赚了很多分数，排名一下上升到第二，本是纪哥选我的变成了我选纪哥，哈哈，还选了小丽姐，她可是3.8杯后全国闻名的人物哦~~一哥一“姐”的组合，虽然我和小丽姐第一次参加省赛，但是我信心十足，跟着曾经拿过银牌的纪哥省赛一定是要冲金夺银的~~PK结束的那个晚上周天涯还和我谈过~~说有机会希望暑假能组队·~啊哈，我真是兴奋至极。。他可是我在队内最希望组队的大牛，进队后就一直钦佩他，现在竟然有机会能在以后一起并肩作战，一起参加全国赛，冲击金牌，参加wf~~哈啊哈~\(≧▽≦)/~（幻想中。。）

期待接下去的组队PK，省赛，暑假集训，全国赛~~~当然，还有world final ！！

AC之旅中的酸甜苦辣就不再细说了，总是看到很多人说AC多么多么苦，很多人说“别人只看到AC所得到的荣耀，而看不到我们背后训练的艰辛”
其实不是这样的，至少我不是这样，AC对我而言不是一种负担，不是一种压力，而是一种娱乐，一种生活方式，已经习惯了实验室的生活，可以除了吃饭睡觉都在实验室，这一切都是快乐的~~^_^当然，AC有成果的话会更加的快乐~~~O(∩_∩)O哈哈~

一直奔跑下去吧~~A Crazy Man

shǎ崽 2009-04-16 17:08 发表评论

飘逸的N皇后问题位运算代码，纪念USACO创过第一关~~matrix67大牛博客上学的

shǎ崽 — 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;
}

哈哈，hdoj上超大数据量的N皇后也过了。。

#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ǎ崽 2009-04-15 12:24 发表评论

第四轮PK。。。

shǎ崽 — Sun, 12 Apr 2009 16:59:00 GMT

最后一轮PK，抱这轻松做做的心态去比，结果出乎意料，哈哈
这次的题目没有以前那么水，每道都是要动点小脑筋的

http://acm.tju.edu.cn/toj/showp3256.html
这是dfs，我惊讶别人暴力深搜竟然都能过。。。我晕
要是我来处数据的话暴力深搜一定爆掉。。
我是用hash[ landscapes ][ (total length)%k ][ Lth ]来剪枝
这样的话最多也就搜索50*50*50个状态。。。很好的设计。。嘿嘿又往自己脸上贴金了

http://acm.tju.edu.cn/toj/showp3257.html
不太清楚是什么算法，不过我程序里用的数组名是DP。。。当时下手的时候想写成DP的，结果就不伦不类掉了XD
不管用什么数组名，DP也好，HH也好，①反正记录下每个字母后边的和该字母相同的字母个数
②然后用一个minch变量去扫一遍字符串，不断更新minch(看到这个变量名应该知道怎么更新的吧)同时记录下标minch的下标pos
③扫到后边相同字母数是0的时候就比较一下，看minch和这个字母谁小
{
如果(minch小)
的话就输出minch同时下标跳回到之前记录的pos;
如果(minch大)
的话就输出这个字母，然后继续扫;
再minch更新为最大
}
不要忘记吧已经输出的字母hash掉哦

http://acm.tju.edu.cn/toj/showp3258.html
一看就是技巧题目。。看成是环，排序后找到一个最大的删除区间掉。。然后看看剩下的所能得到的绝对值最小值
注意要分类讨论。。比赛的时候被sample骗掉。。以为就是中间对称的只考虑了一种情况，其实有四种。。。。
错了好多遍。。。。

http://acm.tju.edu.cn/toj/showp3259.html
简单题，晒法晒下然后再预处理一下

http://acm.tju.edu.cn/toj/showp3260.html
图论阿。。看到就晕了。。。向来没有做过图论的题，最深的也就是二分图的最大匹配
完全匹配都还没有学过。。
没办法。。抱着一线希望来个强剪枝试试。。。结果不出所料TLE了。。。。

两个小时的时候就出了前四道暂时第一了，Luke King出了三道，而我的罚时太多（因为心态比较放松，所有一有思路写好了就提交，WA了修改一下又提交又WA，其实很多罚时是不必要的）。。囧了。所以Luke King只要在比赛前出题就能超过我。A是比较简单的
果然，在最后十分钟出了A超过我了，我在最后十分钟提交了E，结果是超时。。

赛后得知Luke King是09的。。。天津市赛第六。。高中生阿。。Orz

shǎ崽 2009-04-13 00:59 发表评论

第三轮PK。。。。

shǎ崽 — Sun, 12 Apr 2009 16:24:00 GMT

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

这场比赛只有两道水题，所有我做了三道也都排在了前十 %>_<% 要是电脑不蓝屏。。。

shǎ崽 2009-04-13 00:24 发表评论