??xml version="1.0" encoding="utf-8" standalone="yes"?>国产精品99精品久久免费,色婷婷久久久SWAG精品,欧美综合天天夜夜久久http://www.shnenglu.com/Thundercrack/谨以此Blog记录自己的ACq度Q！ 20zh-cnFri, 04 Jul 2025 23:53:26 GMTFri, 04 Jul 2025 23:53:26 GMT60Wythoff’s Game (威佐夫博?http://www.shnenglu.com/Thundercrack/archive/2012/08/08/186683.htmlACSeedACSeedWed, 08 Aug 2012 12:11:00 GMThttp://www.shnenglu.com/Thundercrack/archive/2012/08/08/186683.htmlhttp://www.shnenglu.com/Thundercrack/comments/186683.htmlhttp://www.shnenglu.com/Thundercrack/archive/2012/08/08/186683.html#Feedback0http://www.shnenglu.com/Thundercrack/comments/commentRss/186683.htmlhttp://www.shnenglu.com/Thundercrack/services/trackbacks/186683.html

 Wythoff’s Game (威佐夫博?

原文地址Q?br />

http://yjq24.blogbus.com/logs/42826226.html

大致上是q样的：有两堆石子，不妨先认Z堆有10Q另一堆有15个，双方轮流取走一些石子，合法的取法有如下两种Q?/span>

1)在一堆石子中取走L多颗Q?/span>

2)在两堆石子中取走相同多的L颗；

U定取走最后一颗石子的Zؓ赢家Q求必|?必胜{略)?/span>

q个可以说是MR.Wythoff(Wythoff?907q提出此游戏)一生全部的贡献吧，我在一日志里p完有Ҏ(gu)酗这个问题好像被用作~程竞赛的题目，|上有很多把它Label为POJ1067Q不q如果学~程的h不知?a >Beatty定理和Beatty序列 Q他们所做的只能是找规律而已。不熟?zhn)的h可以先在q里 玩几局~

单分析一下，Ҏ(gu)知道两堆矛_C是一LQ我们用余下的石子数(a,b)来表C状态，q画在^面直角坐标系上?/span>

用之前的定理Q?/span> 有限个结点的无回路有向图有唯一的核  中所q的Ҏ(gu)L必|态。先标出(0,0)Q然后划L?0,k),(k,0), (k,k)的格点；然后找y=x上方未被划去的格点，标出(1,2)Q然后划?1,k),(k,2),(1+k,2+k)Q同时标出对U点(2,1)Q?划去(2,k),(1,k),(2+k,1+k)Q然后在未被划去的点中在y=x上方再找?3,5)。。。按照这LҎ(gu)做下去，如果只列出a& lt;=b的必败态的话，前面的一些是(0,0),(1,2),(3,5),(4,7),(6,10),…

接下来就是找规律的过E了Q忽?0,0)Q记Wnl必败态ؓ(a[n],b[n])

命题一Qa[n+1]=前nl必败态中未出现过的最正整数

[分析]Q如果a[n+1]不是未出现的C最的Q那么可以从a[n+1]的状态走C个a[n+1]更小的状态，和我们的LҎ(gu)矛盾?/span>

命题二：b[n]=a[n]+n

[分析]Q归UxQ若前k个必败态分别ؓ Q下证：Wk+1个必败态ؓ

从该Wk+1个必败态出发，一共可能走向三cȝ态，从左边堆拿走一些，从右边堆拿走一些，或者从两堆中拿C些．下面证明q三c都是胜态．

情况一Q由命题一QQ意一个比a[k+1]的数都在之前的必|态中出现q，一旦把左边堆拿了Q我们只要再拿成那个数相应的必|态即可?/span>

情况二（从右边堆拿走不太多）Q这使得两堆之间的差变小了，比如拿成?img src="http://latex.codecogs.com/gif.latex?%5Cleft%28%20%7Ba_%7Bk%20+%201%7D%20,a_%7Bk%20+%201%7D%20+%20m%7D%20%5Cright%29" alt="" /> Q则可再拿成 Q?/span>

情况二（从右边堆拿走很多Q：使得双一堆比左边一堆更，q时cM于情况一Q比如拿成了 (其中a[m] Q?/span>

情况三：比如拿成 Q则可再拿成 Q?/span>

lg所qͼM?img src="http://latex.codecogs.com/gif.latex?%5Cleft%28%20%7Ba_%7Bk%20+%201%7D%20,a_%7Bk%20+%201%7D%20+%20k%20+%201%7D%20%5Cright%29" alt="" /> 出发走向的状态都可以走回怸Q故原命题成立．

以上两个命题对于定(a[n],b[n])是完备的了，l定(0,0)然后按照q两个命题，可以写?1,2),(3,5),(4,7),…

q样我们得到了这个数列的递推式，以下我们把这两个命题当成?a[n],b[n])的定义?/span>

先证明两个性质Q?/span>

性质一Q核中的a[n],b[n]遍历所有正整数?/span>

[分析]Q由命题一Q二可得a[n],b[n]是递增的，且由a[n]的定义显然?/span>

性质二：A={a[n]:n=1,2,3,…},B={b[n]:n=1,2,3,…}Q则集合A,B不交?/span>

[分析]Q由核是内固集，昄?/span>

看到q里大家有没有想到Beatty序列呢，实际上a[n]和b[n]是一个Beatty序列?/span>

Q有 Q解方程

? Q到此，我们扑ֈ了该必|态的通项公式?/span>

实际上这lBeatty序列q有一些别的性质Q比如当一个数是Fibonacci数的时候，另一个数也是Fibonacci敎ͼ而且两者的比g来接q黄金比Q这些性质在得到通项公式之后不难证明?/span>

ȝ来说Q这个问题给我们了哪些启C呢Q首先用定理所说的Ҏ(gu)找核Q然后给出核的规律（递推Q或是通项Qƈ且证明。最后附上一张对应的必|态图.

wythoff



ACSeed 2012-08-08 20:11 发表评论
]]>poj 2886 没啥Q线D|基础应用Q纪念一下队长教的打素数的方?/title><link>http://www.shnenglu.com/Thundercrack/archive/2012/08/08/186665.html</link><dc:creator>ACSeed</dc:creator><author>ACSeed</author><pubDate>Wed, 08 Aug 2012 08:52:00 GMT</pubDate><guid>http://www.shnenglu.com/Thundercrack/archive/2012/08/08/186665.html</guid><wfw:comment>http://www.shnenglu.com/Thundercrack/comments/186665.html</wfw:comment><comments>http://www.shnenglu.com/Thundercrack/archive/2012/08/08/186665.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/Thundercrack/comments/commentRss/186665.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/Thundercrack/services/trackbacks/186665.html</trackback:ping><description><![CDATA[<div>#include<cstdio></div><div>#include<cstring></div><div>#include<algorithm></div><div>using namespace std;</div><div></div><div>const int maxn = 500010;</div><div>struct NN</div><div>{</div><div>    char s[20];</div><div>    int num;</div><div>} ch[maxn];</div><div></div><div>int prim[maxn], plen;</div><div>bool vis[maxn];</div><div>long long cc[maxn];</div><div></div><div>void mklist()</div><div>{</div><div>    plen = 0;</div><div>    memset(prim, false, sizeof(prim));</div><div>    for(int i = 2; i * i <= maxn; ++i)</div><div>    {</div><div>        if(!prim[i])</div><div>        {</div><div>            for(int j = i; j * i <= maxn; ++j)</div><div>            {</div><div>                if(!prim[i * j])</div><div>                    prim[i * j] = i;</div><div>            }</div><div>        }</div><div>    }</div><div>}</div><div></div><div>long long split(int x)</div><div>{</div><div>    long long ans = 1;</div><div>    int cur = x;</div><div>    if(x == 1) return 1;</div><div>    int tmp = prim[cur];</div><div>    while(prim[cur] != 0)</div><div>    {</div><div>        int cnt = 0;</div><div>        while(cur % tmp == 0)</div><div>        {</div><div>            ++cnt;</div><div>            cur /= tmp;</div><div>        }</div><div>        ans *= cnt + 1;</div><div>        tmp = prim[cur];</div><div>    }</div><div>    if(cur != 1)</div><div>        ans *= 2;</div><div>    return ans;</div><div>}</div><div></div><div>struct node</div><div>{</div><div>    int l, r, mid;</div><div>    int count;</div><div>    node()</div><div>    {</div><div>        count = 0;</div><div>    }</div><div>} seg[3 * maxn];</div><div></div><div>void build(int l, int r, int num)</div><div>{</div><div>    seg[num].l = l;</div><div>    seg[num].r = r;</div><div>    seg[num].mid = (l + r) >> 1;</div><div>    if(l + 1 == r)</div><div>    {</div><div>        seg[num].count = 1;</div><div>        return ;</div><div>    }</div><div>    build(l, seg[num].mid, num << 1);</div><div>    build(seg[num].mid, r, num << 1 | 1);</div><div>    seg[num].count = seg[num << 1].count + seg[num << 1 | 1].count;</div><div>}</div><div></div><div>int search(int k, int num)</div><div>{</div><div>    if(seg[num].l + 1 == seg[num].r)</div><div>    {</div><div>        seg[num].count--;</div><div>        return seg[num].l;</div><div>    }</div><div>    seg[num].count--;</div><div>    if(k <= seg[num << 1].count)</div><div>    {</div><div>        return search(k, num << 1);</div><div>    }</div><div>    else</div><div>    {</div><div>        return search(k - seg[num << 1].count, num << 1 | 1);</div><div>    }</div><div>}</div><div></div><div>int n, k;</div><div>int main()</div><div>{</div><div>   // freopen("in.txt", "r", stdin);</div><div>    mklist();</div><div>    while(scanf("%d%d", &n, &k) != EOF)</div><div>    {</div><div>        for(int i = 1; i <= n; ++i)</div><div>        {</div><div>            scanf("%s%d", ch[i].s, &ch[i].num);</div><div>        }</div><div>        int res = 1;</div><div>        int mac = 1;</div><div>        for(int i = n / 2 + 1; i <= n; ++i)</div><div>        {</div><div>            int tmp = split(i);</div><div>            if(res < tmp)</div><div>            {</div><div>                res = tmp;</div><div>                mac = i;</div><div>            }</div><div>        }</div><div>        build(1, n + 1, 1);</div><div>        int st = k;</div><div>        int t = search(k, 1);</div><div>        if(mac == 1)</div><div>        {</div><div>            printf("%s %d\n", ch[t].s, res);</div><div>            continue;</div><div>        }</div><div>        int ans = t;</div><div>        for(int i = 2; i <= mac; ++i)</div><div>        {</div><div>            if(ch[ans].num > 0)</div><div>            {</div><div>                st = (st + ch[ans].num - 1) % seg[1].count;</div><div>                if(st == 0)</div><div>                    st = seg[1].count;</div><div>                ans = search(st, 1);</div><div>            }</div><div>            else</div><div>            {</div><div>                st = (st + ch[ans].num) % seg[1].count;</div><div>                if(st <= 0)</div><div>                    st += seg[1].count;</div><div>                ans = search(st, 1);</div><div>            }</div><div>        }</div><div>        printf("%s %d\n", ch[ans].s, res);</div><div>    }</div><div>    return 0;</div><div>}</div><img src ="http://www.shnenglu.com/Thundercrack/aggbug/186665.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/Thundercrack/" target="_blank">ACSeed</a> 2012-08-08 16:52 <a href="http://www.shnenglu.com/Thundercrack/archive/2012/08/08/186665.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>uva 11029http://www.shnenglu.com/Thundercrack/archive/2012/04/25/172769.htmlACSeedACSeedWed, 25 Apr 2012 13:52:00 GMThttp://www.shnenglu.com/Thundercrack/archive/2012/04/25/172769.htmlhttp://www.shnenglu.com/Thundercrack/comments/172769.htmlhttp://www.shnenglu.com/Thundercrack/archive/2012/04/25/172769.html#Feedback0http://www.shnenglu.com/Thundercrack/comments/commentRss/172769.htmlhttp://www.shnenglu.com/Thundercrack/services/trackbacks/172769.htmlq题主要是log的性质Q假?log10(c) = x = a + b;
其中a是x的整数部分，b是x的小数部分，?10^b = 10^(x - a) = 10^x / 10^a = c / 10^a;
可见a只媄响c的小数点的位|，可以直接LQ这样可以求出数的前三位Q后三位׃用说了吧Q?br />
PSQ真的好强大

ACSeed 2012-04-25 21:52 发表评论
]]>uva 571http://www.shnenglu.com/Thundercrack/archive/2012/04/25/172759.htmlACSeedACSeedWed, 25 Apr 2012 11:47:00 GMThttp://www.shnenglu.com/Thundercrack/archive/2012/04/25/172759.htmlhttp://www.shnenglu.com/Thundercrack/comments/172759.htmlhttp://www.shnenglu.com/Thundercrack/archive/2012/04/25/172759.html#Feedback0http://www.shnenglu.com/Thundercrack/comments/commentRss/172759.htmlhttp://www.shnenglu.com/Thundercrack/services/trackbacks/172759.html思\只有bfsQ可是分cd数学里，所以极力寻求数学方法，分析在这?br />
http://www.cnblogs.com/devymex/archive/2010/08/04/1792288.html

下面单证明： 当n?到B-1变化Ӟr可以取到0到B-1之间的Q何?br />用反正法Q?br />na % B可以取到的值只?0 ~ B-1, 当n? ~ B-1Ӟ假设r不能取完0 ~ B-1, 则必有n取两个不同值时% B值相同，
设ؓn1,n2;则n1A % B = x,n2A % B = x, 两边分别相比Q得 n1 / n2 = 1, ?n1 = n2, 与假讄盾，证毕Q！

PS: a ?b 互质说明什么？ 说明gcd(a,b) = 1 && lcm(a,b) = a * b && for n <- 0 ~ b - 1   n * a % b 可以取到 0 ?b - 1;

ACSeed 2012-04-25 19:47 发表评论
]]>教程http://www.shnenglu.com/Thundercrack/archive/2012/04/16/171660.htmlACSeedACSeedMon, 16 Apr 2012 13:37:00 GMThttp://www.shnenglu.com/Thundercrack/archive/2012/04/16/171660.htmlhttp://www.shnenglu.com/Thundercrack/comments/171660.htmlhttp://www.shnenglu.com/Thundercrack/archive/2012/04/16/171660.html#Feedback0http://www.shnenglu.com/Thundercrack/comments/commentRss/171660.htmlhttp://www.shnenglu.com/Thundercrack/services/trackbacks/171660.htmlhttp://coolshell.cn/articles/3083.html 

http://blog.csdn.net/shinehoo/article/details/6755464 
http://blog.csdn.net/shinehoo/article/category/816995 
http://www.w3school.com.cn/ 
http://coolshell.cn/articles/4990.html 
http://woodpecker.org.cn/abyteofpython_cn/chinese/index.html

ACSeed 2012-04-16 21:37 发表评论
]]>(转）ACM基本法分类、推荐学习资料和配套poj习题 分类http://www.shnenglu.com/Thundercrack/archive/2012/04/05/170201.htmlACSeedACSeedThu, 05 Apr 2012 12:51:00 GMThttp://www.shnenglu.com/Thundercrack/archive/2012/04/05/170201.htmlhttp://www.shnenglu.com/Thundercrack/comments/170201.htmlhttp://www.shnenglu.com/Thundercrack/archive/2012/04/05/170201.html#Feedback0http://www.shnenglu.com/Thundercrack/comments/commentRss/170201.htmlhttp://www.shnenglu.com/Thundercrack/services/trackbacks/170201.html

一.动态规?/p>

参考资料：

刘汝佟뀊算法艺术与信息学竞赛》《算法导论?/p>

推荐题目Q?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1141

?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=2288

中等Q经典TSP问题

http://acm.pku.edu.cn/JudgeOnline/problem?id=2411

中等Q状态压~DP

http://acm.pku.edu.cn/JudgeOnline/problem?id=1112

中等

http://acm.pku.edu.cn/JudgeOnline/problem?id=1848

中等Q树形DP。可参考《算法艺术与信息学竞赛》动态规划一节的树状模型

http://acm.zju.edu.cn/show_problem.php?pid=1234

中等Q《算法艺术与信息学竞赛》中的习?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1947

中等Q《算法艺术与信息学竞赛》中的习?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1946

中等Q《算法艺术与信息学竞赛》中的习?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1737

中等Q递推

http://acm.pku.edu.cn/JudgeOnline/problem?id=1821

中等Q需要减冗余计?/p>

http://acm.zju.edu.cn/show_problem.php?pid=2561

中等Q四边Ş不等式的单应?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1038

较难Q状态压~DPQ《算法艺术与信息学竞赛》中有解{?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1390

较难Q《算法艺术与信息学竞赛》中有解{?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=3017

较难Q需要配合数据结构优化（我的题目^_^Q?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1682

较难Q写h比较ȝ

http://acm.pku.edu.cn/JudgeOnline/problem?id=2047

较难

http://acm.pku.edu.cn/JudgeOnline/problem?id=2152

难，树ŞDP

http://acm.pku.edu.cn/JudgeOnline/problem?id=3028

难，状态压~DPQ题目很有意?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=3124

?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=2915

非常?/p>

 

?搜烦

参考资料：

刘汝佟뀊算法艺术与信息学竞赛?/p>

推荐题目Q?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1011

单，深搜入门?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1324

中等Q广?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=2044

中等Q广?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=2286

较难Q广?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1945

难，IDA*QP代加深搜索，需要较好的启发函数

http://acm.pku.edu.cn/JudgeOnline/problem?id=2449

难，可重复K最短\QA*。可参考解题报?

http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144

http://acm.pku.edu.cn/JudgeOnline/problem?id=1190

难，深搜剪枝Q《算法艺术与信息学竞赛》中有解{?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1084

难，《算法艺术与信息学竞赛》习?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=2989

难，深搜

http://acm.pku.edu.cn/JudgeOnline/problem?id=1167

较难Q《算法艺术与信息学竞赛》中有解{?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1069

很难

? 常用数据l构

参考资料：

刘汝佟뀊算法艺术与信息学竞赛?/p>

《算法导论?/p>

U段树资料：

http://home.ustc.edu.cn/~zhuhcheng/ACM/segment_tree.pdf

树状数组资料

http://home.ustc.edu.cn/~zhuhcheng/ACM/tree.ppt

关于U段树和树状数组更多相关内容可在|上搜到

后缀数组资料

http://home.ustc.edu.cn/~zhuhcheng/ACM/suffix_array.pdf

http://home.ustc.edu.cn/~zhuhcheng/ACM/linear_suffix.pdf

推荐题目

http://acm.pku.edu.cn/JudgeOnline/problem?id=2482

较难Q线D|应用Q《算法艺术与信息学竞赛》中有解{?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1151

单，U段树应用矩形面UƈQ《算法艺术与信息学竞赛》中有解{?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=3225

较难Q线D|应用Q可参考解题报?/p>

http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1233

http://acm.pku.edu.cn/JudgeOnline/problem?id=2155

难，二维树状数组?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=2777

中等Q线D|应用?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=2274

难，堆的应用Q《算法艺术与信息学竞赛》中有解{?/p>

http://acm.zju.edu.cn/show_problem.php?pid=2334

中等Q左偏树Q二式堆或其他可合q堆的应用?/p>

左偏树参?http://www.nist.gov/dads/HTML/leftisttree.html

二项式堆参见《算法导论》相关章?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1182

中等Qƈ查集

http://acm.pku.edu.cn/JudgeOnline/problem?id=1816

中等Q字典树

http://acm.pku.edu.cn/JudgeOnline/problem?id=2778

较难Q多串匹配树

参考： http://home.ustc.edu.cn/~zhuhcheng/ACM/zzy2004.pdf

http://acm.pku.edu.cn/JudgeOnline/problem?id=1743

难，后缀数组

http://acm.pku.edu.cn/JudgeOnline/problem?id=2774

较难Q最长公共子Ԍl典问题Q后~数组

http://acm.pku.edu.cn/JudgeOnline/problem?id=2758

很难Q后~数组

可参考解题报?/p>

http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1178

http://acm.pku.edu.cn/JudgeOnline/problem?id=2448

很难Q数据结构综合运?/p>

?图论基础

参考资料：

刘汝佟뀊算法艺术与信息学竞赛》《算法导论》《网l算法与复杂性理论》谢?/p>

推荐题目:

http://acm.pku.edu.cn/JudgeOnline/problem?id=2337

单，Ƨ拉?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=3177

中等Q无向图割边

http://acm.pku.edu.cn/JudgeOnline/problem?id=2942

较难Q无向图双连通分?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1639

中等Q最度限制生成树，《算法艺术与信息学竞赛》中有解{?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=2728

中等Q最比率生成树Q《算法艺术与信息学竞赛》中有解{?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=3013

单，最短\问题

http://acm.pku.edu.cn/JudgeOnline/problem?id=1275

中等Q差分约束系l，Bellman-Ford求解Q《算法艺术与信息学竞赛》中有解{?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=1252

单，Bellman-Ford

http://acm.pku.edu.cn/JudgeOnline/problem?id=1459

中等Q网l流

http://acm.pku.edu.cn/JudgeOnline/problem?id=2391

较难Q网l流

http://acm.pku.edu.cn/JudgeOnline/problem?id=1325

中等Q二部图最大匹?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=2226

较难Q二部图最大匹?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=2195

中等Q二部图最大权匚w

KM法参考《网l算法与复杂性理论?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=2516

较难Q二部图最大权匚w

http://acm.pku.edu.cn/JudgeOnline/problem?id=1986

中等QLCAQ最q公q先）问题

参考Tarjan's LCA algorithm 《算法导论》第21章习?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=2723

较难Q?-SAT问题

参考：http://home.ustc.edu.cn/~zhuhcheng/ACM/2-SAT.PPT

http://acm.pku.edu.cn/JudgeOnline/problem?id=2749

较难Q?-SAT问题

http://acm.pku.edu.cn/JudgeOnline/problem?id=3164

较难Q最树形图

参考《网l算法与复杂性理论》中?刘算?/p>

?数论及组合计数基

http://acm.pku.edu.cn/JudgeOnline/problem?id=1811

单，素数判定Q大数分?/p>

参考算法导论相关章?/p>

http://acm.pku.edu.cn/JudgeOnline/problem?id=2888

较难QBurnside引理

http://acm.pku.edu.cn/JudgeOnline/problem?id=2891

中等Q解模方E组

http://acm.pku.edu.cn/JudgeOnline/problem?id=2154

中等Q经兔R题，波利亚定?/p>

http://cs.scu.edu.cn/soj/problem.action?id=2703

难，极好的题目，Burnside引理+模线性方E组

http://acm.pku.edu.cn/JudgeOnline/problem?id=2764

较难Q需要数学方法，该方法在《具体数学》第七章有讲

http://acm.pku.edu.cn/JudgeOnline/problem?id=1977

单，矩阵快速乘?/p>

ACSeed 2012-04-05 20:51 发表评论
]]>ACM q阶之\Q{http://www.shnenglu.com/Thundercrack/archive/2011/12/15/162151.htmlACSeedACSeedThu, 15 Dec 2011 02:37:00 GMThttp://www.shnenglu.com/Thundercrack/archive/2011/12/15/162151.htmlhttp://www.shnenglu.com/Thundercrack/comments/162151.htmlhttp://www.shnenglu.com/Thundercrack/archive/2011/12/15/162151.html#Feedback0http://www.shnenglu.com/Thundercrack/comments/commentRss/162151.htmlhttp://www.shnenglu.com/Thundercrack/services/trackbacks/162151.html

一般要做到50行以内的E序不用调试?00行以内的二分钟内调试成功.
ACM主要是考算法的,主要旉是花在思考算法上Q不是花在写E序与debug上?/font>

下面l个计划你练l：

W一阶段Q练l典常用法Q下面的每个法l我打上十到二十遍，同时自己_代码Q?/font>
因ؓ太常用，所以要l到写时不用惻I10-15分钟内打完，甚至x昄器都可以把程序打
出来?br style="line-height: normal; " />

1.最短\(Floyd、Dijstra,BellmanFord) 
2.最生成树(先写个prim,kruscal要用q查集，不好? 
3.大数Q高_ֺQ加减乘?nbsp;
4.二分查找. (代码可在五行以内) 
5.叉乘、判U段怺、然后写个凸? 
6.BFS、DFS,同时熟练hash?要熟Q要灉|,代码要简) 
7.数学上的有：辗{盔RQ两行内Q，U段交点、多角Ş面积公式. 
8. 调用pȝ的qsort, 技巧很多，慢慢掌握. 
9. Lq制间的转换

W二阶段Q练习复杂一点，但也较常用的法?/strong> 
如： 
1. 二分囑֌配（匈牙利）Q最\径覆?nbsp;
2. |络，最费用流?nbsp;
3. U段? 
4. q查集?nbsp;
5. 熟?zhn)动态规划的各个典型QLCS、最镉K增子串、三角剖分、记忆化dp 
6.博弈cȝ法。博弈树Q二q制法等?nbsp;
7.最大团Q最大独立集?nbsp;
8.判断点在多边形内?nbsp;
9. 差分U束pȝ. 
10. 双向q度搜烦、A*法Q最耗散优先.
===========================================================


ACMer必备知识QQ重而道q?.....Q?/p>

图论

   路径问题
        0/1Ҏ(gu)最短\?br style="line-height: normal; " />        BFS
        非负Ҏ(gu)最短\径（DijkstraQ?br style="line-height: normal; " />            可以用Dijkstra解决问题的特?br style="line-height: normal; " />        负边权最短\?br style="line-height: normal; " />        Bellman-Ford
            Bellman-Ford的Yen-氏优?br style="line-height: normal; " />            差分U束pȝ
        Floyd
            q义路径问题
            传递闭?br style="line-height: normal; " />            极小极大距离 / 极大极小距离
        Euler Path / Tour
            圈套圈算?br style="line-height: normal; " />            混合囄 Euler Path / Tour
        Hamilton Path / Tour
            Ҏ(gu)囄Hamilton Path / Tour 构?br style="line-height: normal; " />
    生成树问?br style="line-height: normal; " />        最生成树
        Wk生成树
        最优比率生成树
        0/1分数规划
        度限制生成树

    q通性问?br style="line-height: normal; " />        强大的DFS法
        无向图连通?br style="line-height: normal; " />            割点
            割边
            二连通分?br style="line-height: normal; " />            有向图连通?br style="line-height: normal; " />            通分?br style="line-height: normal; " />            2-SAT
            最点?br style="line-height: normal; " />
    有向无环?br style="line-height: normal; " />        拓扑排序
            有向无环图与动态规划的关系

    二分囑֌配问?br style="line-height: normal; " />        一般图问题与二分图问题的{换思\
        最大匹?br style="line-height: normal; " />            有向囄最\径覆?br style="line-height: normal; " />            0 / 1矩阵的最覆?br style="line-height: normal; " />        完备匚w
        最优匹?br style="line-height: normal; " />        E_婚姻

    |络问?br style="line-height: normal; " />        |络模型的单特征和与线性规划的关系
        最大流最割定理
        最大流问题
            有上下界的最大流问题
                循环?br style="line-height: normal; " />        最费用最大流 / 最大费用最大流

    弦图的性质和判?br style="line-height: normal; " />

l合数学

    解决l合数学问题时常用的思想
        D
        递推 / 动态规?br style="line-height: normal; " />    概率问题
        Polya定理


计算几何 / 解析几何

    计算几何的核心：叉积 / 面积
    解析几何的主力：复数

    基本?br style="line-height: normal; " />        ?br style="line-height: normal; " />        直线Q线D?br style="line-height: normal; " />        多边?br style="line-height: normal; " />
    凸多边Ş / 凸包
        凸包法的引q，卷包Ҏ(gu)

    Graham扫描?br style="line-height: normal; " />        水^序的引进Q共U凸包的补丁

    完美凸包法

    相关判定
        两直U相?br style="line-height: normal; " />        两线D늛?br style="line-height: normal; " />        点在L多边形内的判?br style="line-height: normal; " />        点在凸多边Ş内的判定

    l典问题
        最外接圆
            q似O(n)的最外接圆法
        炚w直径
            旋{卡壳Q对t늂
        多边形的三角剖分


数学 / 数论

   最大公U数
        Euclid法
            扩展的Euclid法
                同余方程 / 二元一ơ不定方E?br style="line-height: normal; " />                同余方程l?br style="line-height: normal; " />
    U性方E组
        高斯消元?br style="line-height: normal; " />            解mod 2域上的线性方E组
        整系数方E组的精解?br style="line-height: normal; " />
    矩阵
        行列式的计算
            利用矩阵乘法快速计递推关系

    分数
        分数?br style="line-height: normal; " />        q分数D

    数论计算
        求N的约C?br style="line-height: normal; " />        求phi(N)
        求约数和
        快速数论变?br style="line-height: normal; " />        ……

    素数问题
        概率判素法
        概率因子分解


数据l构

    l织l构
        二叉?br style="line-height: normal; " />        左偏?br style="line-height: normal; " />        二项?br style="line-height: normal; " />        胜者树
        跌?br style="line-height: normal; " />        样式图标
        斜堆
        reap

    l计l构
        树状数组
        虚二叉树
        U段?br style="line-height: normal; " />            矩Ş面积q?br style="line-height: normal; " />            圆Ş面积q?br style="line-height: normal; " />
    关系l构
        Hash?br style="line-height: normal; " />        q查?br style="line-height: normal; " />            路径压羃思想的应?br style="line-height: normal; " />
    STL中的数据l构
        vector
        deque
        set / map


动态规?/ 记忆化搜?/strong>

   动态规划和记忆化搜索在思考方式上的区?br style="line-height: normal; " />
    最长子序列pd问题
        最长不下降子序?br style="line-height: normal; " />        最长公共子序列
        最长公׃下降子序?br style="line-height: normal; " />
    一cNP问题的动态规划解?br style="line-height: normal; " />
    树型动态规?br style="line-height: normal; " />
    背包问题

    动态规划的优化
        四边形不{式
        函数的凸Ҏ(gu)?br style="line-height: normal; " />        状态设?br style="line-height: normal; " />        规划方向


U性规?/font>

常用思想

    二分
    最表C法

?/strong>

    KMP
    Triel构
    后缀?后缀数组
    LCA/RMQ
    有限状态自动机理论

排序
    选择/冒
    快速排?br style="line-height: normal; " />    堆排?br style="line-height: normal; " />    归ƈ排序
    基数排序
    拓扑排序
    排序|络



ACSeed 2011-12-15 10:37 发表评论
]]>poj 1896 Code Formattinghttp://www.shnenglu.com/Thundercrack/archive/2011/11/25/160978.htmlACSeedACSeedFri, 25 Nov 2011 11:32:00 GMThttp://www.shnenglu.com/Thundercrack/archive/2011/11/25/160978.htmlhttp://www.shnenglu.com/Thundercrack/comments/160978.htmlhttp://www.shnenglu.com/Thundercrack/archive/2011/11/25/160978.html#Feedback0http://www.shnenglu.com/Thundercrack/comments/commentRss/160978.htmlhttp://www.shnenglu.com/Thundercrack/services/trackbacks/160978.htmlhttp://poj.org/problem?id=1896
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2463
格式化一D代码，格式题目里说的很清楚了?br />zoj上的只不q多CASE而已

直接上code: 
1 #include<cstdio>
 2 #include<cstring>
 3 
 4 using namespace std;
 5 char s[20000000];
 6 int lev = 0;
 7 void printsp()
 8 {
 9     for(int i = 0; i < 4 * lev; ++i) putchar(' ');
10 }
11 int main()
12 {
13     //freopen("in.txt","r",stdin);
14     //freopen("out.txt","w",stdout);
15     char c;
16     int len = 0;
17     for(; scanf("%c",&c) != EOF;) {
18         if(c != ' ' && c != 10 && c != 13 && c != 9)
19             s[len++] = c;
20     }
21     //for(int i = 0; i < len; ++i) putchar(s[i]);
22     bool flag = false;
23     for(int i = 0; i < len; ++i) {
24         if(i == 0) {
25             flag = true;
26             printf("{\n");
27             lev++;
28         } else {
29             if(s[i] != '{' && s[i] != ';' && s[i] != '}') {
30                if(flag) printsp();flag = false;
31                 if(s[i] == ',') printf(", ");
32                 else putchar(s[i]);
33             }
34             if(s[i] == ';') {
35                 flag = true;
36                 printf(";\n");
37             } else if(s[i] == '{') {
38                 flag = true;
39                 printf(" {\n");
40                 ++lev;
41             } else if(s[i] == '}') {
42                 flag = false;
43                 lev--;
44                 printsp();
45                 printf("}");
46                /* ++i;
47                 while(s[i] != '{' && s[i] != ';' && i < len) {
48                     putchar(s[i]);
49                     ++i;
50                 }
51                 if(i < len && s[i] == ';')
52                     printf(";\n");
53                 else if(i < len && s[i] == '{') {
54                     flag = true;
55                     printf("\n{\n");*/
56                  //   ++lev;
57                // }
58                if(i + 1 < len && s[i+1] == '{') {
59                     flag = true;
60                     printf("\n{\n");
61                     ++i;++lev;
62                }
63             }
64         }
65     }
66     //printf("fuck!!!\n");
67     return 0;
68 }


ACSeed 2011-11-25 19:32 发表评论
]]>uva 530http://www.shnenglu.com/Thundercrack/archive/2011/11/11/159972.htmlACSeedACSeedFri, 11 Nov 2011 14:47:00 GMThttp://www.shnenglu.com/Thundercrack/archive/2011/11/11/159972.htmlhttp://www.shnenglu.com/Thundercrack/comments/159972.htmlhttp://www.shnenglu.com/Thundercrack/archive/2011/11/11/159972.html#Feedback0http://www.shnenglu.com/Thundercrack/comments/commentRss/159972.htmlhttp://www.shnenglu.com/Thundercrack/services/trackbacks/159972.html比较恶心Q开始分解质因数Q因为N!Ҏ(gu)分解质因子，然后必须打出整Ş内的素数Q?br />果断舍弃Q想想不会超q整敎ͼ用公式算分子C会太多，貌似不会时Q试试吧Q成功了Q！
C(n,n/2)最大了Qn到几十就int了，所以k不会很大Q这里的k是指的Q如果k > n / 2 可以
C(n,k) = C(n,n-k),用n-k代替k,边乘辚wQ?2MS AC!

ACSeed 2011-11-11 22:47 发表评论
]]>棍?道水?/title><link>http://www.shnenglu.com/Thundercrack/archive/2011/11/11/159963.html</link><dc:creator>ACSeed</dc:creator><author>ACSeed</author><pubDate>Fri, 11 Nov 2011 08:25:00 GMT</pubDate><guid>http://www.shnenglu.com/Thundercrack/archive/2011/11/11/159963.html</guid><wfw:comment>http://www.shnenglu.com/Thundercrack/comments/159963.html</wfw:comment><comments>http://www.shnenglu.com/Thundercrack/archive/2011/11/11/159963.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/Thundercrack/comments/commentRss/159963.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/Thundercrack/services/trackbacks/159963.html</trackback:ping><description><![CDATA[<div><a >http://acm.hdu.edu.cn/diy/contest_show.php?cid=13622<br /></a>W?题神数最后三位是471Q前面是k-1;<br />W?题简单模q算<br />W?题先从n个中选出m个数码兽Q然后这m个数码兽做错位排列即 ans = C(n,m) * D(m)Q?a ></a></div><div></div><img src ="http://www.shnenglu.com/Thundercrack/aggbug/159963.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/Thundercrack/" target="_blank">ACSeed</a> 2011-11-11 16:25 <a href="http://www.shnenglu.com/Thundercrack/archive/2011/11/11/159963.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item></channel></rss> <footer> <div class="friendship-link"> <p>лǵվܻԴȤ</p> <a href="http://www.shnenglu.com/" title="精品视频久久久久">精品视频久久久久</a> <div class="friend-links"> </div> </div> </footer> <a href="http://www.aimingshi.cn" target="_blank">Ʒ˾þþ</a>| <a href="http://www.laoji2004.cn" target="_blank">91Ըߺþþþ</a>| <a href="http://www.mingfeiyaye.cn" target="_blank">һaɫƬþ</a>| <a href="http://www.ljhn.com.cn" target="_blank">ŷպƷþ </a>| <a href="http://www.xnhtml.com.cn" target="_blank">þþһƷ99þþƷ66</a>| <a href="http://www.77ns.cn" target="_blank">ɫ͵͵88888ŷƷþþ</a>| <a href="http://www.akeyu.cn" target="_blank">Ʒ999þþþþĻ</a>| <a href="http://www.rcipbrdgydr.cn" target="_blank">߳þѹۿ</a>| <a href="http://www.maituogangwan.cn" target="_blank">þóСƵ</a>| <a href="http://www.idotime.cn" target="_blank">þ</a>| <a href="http://www.seekme.com.cn" target="_blank">þAVĻ</a>| <a href="http://www.kaifang001.cn" target="_blank">99þþƷѿһ </a>| <a href="http://www.bttzc.cn" target="_blank">91Ʒ91þþþþ</a>| <a href="http://www.ccgangjiegou.cn" target="_blank">ŷһƷþ</a>| <a href="http://www.bisibbs.cn" target="_blank">þþþþþþþþþƷ</a>| <a href="http://www.wangyanl3.com.cn" target="_blank">99þ뾫Ʒϵ</a>| <a href="http://www.zouzouqiaoqiao.cn" target="_blank">69Ʒþþþ99</a>| <a href="http://www.cizbuk.cn" target="_blank">Ļþҹ</a>| <a href="http://www.135gkr4.cn" target="_blank">þþžѸƵ</a>| <a href="http://www.wlvq.cn" target="_blank">һֻƴƬ99þ</a>| <a href="http://www.niguoyi.cn" target="_blank">AëƬþþþƷëƬ</a>| <a href="http://www.tdpqb.cn" target="_blank">þþܳ</a>| <a href="http://www.hgnulb.cn" target="_blank">ݺɫۺվþþþþþ</a>| <a href="http://www.worldedu.org.cn" target="_blank">þþþAVվ</a>| <a href="http://www.9394cn.cn" target="_blank">þþƷһ99</a>| <a href="http://www.adultr.cn" target="_blank">ŷһþþþþþô</a>| <a href="http://www.chaikuo.cn" target="_blank">ۺϾþĻ</a>| <a href="http://www.r7831.cn" target="_blank">ƷۺϾþþþþ97</a>| <a href="http://www.99j9.cn" target="_blank">ަvþþ</a>| <a href="http://www.zhinvest.cn" target="_blank">þɫۺ</a>| <a href="http://www.cjlxz.cn" target="_blank">þùֱ</a>| <a href="http://www.fa808.cn" target="_blank">͵͵þþþվ</a>| <a href="http://www.zghart.cn" target="_blank">þþþþþþ66ƷƬ</a>| <a href="http://www.qeckf.cn" target="_blank">ĻþþƷ</a>| <a href="http://www.bekin.com.cn" target="_blank">þþƷ</a>| <a href="http://www.227s.cn" target="_blank">޾Ʒtvþþþ</a>| <a href="http://www.zhaoyang-db.com.cn" target="_blank">ձƷһþþ</a>| <a href="http://www.geiduan.cn" target="_blank">þƵ</a>| <a href="http://www.cadcamcae.com.cn" target="_blank">޹þþۺ</a>| <a href="http://www.tf78.cn" target="_blank">þþþþþòҰ¸߳ </a>| <a href="http://www.dicy888.cn" target="_blank">޹徫Ʒ߾þ</a>| <script> (function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https') { bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else { bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })(); </script> </body>