C++博客-ACSeed

Wythoff’s Game (威佐夫博弈)

ACSeed — Wed, 08 Aug 2012 12:11:00 GMT

Wythoff’s Game (威佐夫博弈)

原文地址：

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

大致上是这样的：有两堆石子，不妨先认为一堆有10，另一堆有15个，双方轮流取走一些石子，合法的取法有如下两种：

1)在一堆石子中取走任意多颗；

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

约定取走最后一颗石子的人为赢家，求必败态(必胜策略)。

这个可以说是MR.Wythoff(Wythoff于1907年提出此游戏)一生全部的贡献吧，我在一篇日志里就说完有点残酷。这个问题好像被用作编程竞赛的题目，网上有很多把它Label为POJ1067，不过如果学编程的人不知道Beatty定理和Beatty序列，他们所做的只能是找规律而已。不熟悉的人可以先在这里玩几局~

简单分析一下，容易知道两堆石头地位是一样的，我们用余下的石子数(a,b)来表示状态，并画在平面直角坐标系上。

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

接下来就是找规律的过程了，忽略(0,0)，记第n组必败态为(a[n],b[n])

命题一：a[n+1]=前n组必败态中未出现过的最小正整数

[分析]：如果a[n+1]不是未出现的数中最小的，那么可以从a[n+1]的状态走到一个使a[n+1]更小的状态，和我们的寻找方法矛盾。

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

[分析]：归纳法：若前k个必败态分别为，下证：第k+1个必败态为

从该第k+1个必败态出发，一共可能走向三类状态，从左边堆拿走一些，从右边堆拿走一些，或者从两堆中拿走一些．下面证明这三类都是胜态．

情况一：由命题一，任意一个比a[k+1]小的数都在之前的必败态中出现过，一旦把左边堆拿少了，我们只要再拿成那个数相应的必败态即可。

情况二（从右边堆拿走不太多）：这使得两堆之间的差变小了，比如拿成了，则可再拿成；

情况二（从右边堆拿走很多）：使得右边一堆比左边一堆更少，这时类似于情况一，比如拿成了 (其中a[m] ；

情况三：比如拿成，则可再拿成．

综上所述，任何从出发走向的状态都可以走回核中．故原命题成立．

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

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

先证明两个性质：

性质一：核中的a[n],b[n]遍历所有正整数。

[分析]：由命题一，二可得a[n],b[n]是递增的，且由a[n]的定义显然。

性质二：A={a[n]:n=1,2,3,…},B={b[n]:n=1,2,3,…}，则集合A,B不交。

[分析]：由核是内固集，显然。

看到这里大家有没有想到Beatty序列呢，实际上a[n]和b[n]就是一个Beatty序列。

，有，解方程

得，到此，我们找到了该必败态的通项公式。

实际上这组Beatty序列还有一些别的性质，比如当一个数是Fibonacci数的时候，另一个数也是Fibonacci数；而且两者的比值也越来越接近黄金比，这些性质在得到通项公式之后不难证明。

总的来说，这个问题给我们了哪些启示呢？首先用定理所说的方法找核，然后给出核的规律（递推，或是通项）并且证明。最后附上一张对应的必败态图.

ACSeed 2012-08-08 20:11 发表评论

poj 2886 没啥，线段树基础应用，纪念一下队长教的打素数的方法

ACSeed — Wed, 08 Aug 2012 08:52:00 GMT

#include

using namespace std;

const int maxn = 500010;

struct NN

{

char s[20];

int num;

} ch[maxn];

int prim[maxn], plen;

bool vis[maxn];

long long cc[maxn];

void mklist()

{

plen = 0;

memset(prim, false, sizeof(prim));

for(int i = 2; i * i <= maxn; ++i)

{

if(!prim[i])

{

for(int j = i; j * i <= maxn; ++j)

{

if(!prim[i * j])

prim[i * j] = i;

}

long long split(int x)

{

long long ans = 1;

int cur = x;

if(x == 1) return 1;

int tmp = prim[cur];

while(prim[cur] != 0)

{

int cnt = 0;

while(cur % tmp == 0)

{

++cnt;

cur /= tmp;

}

ans *= cnt + 1;

tmp = prim[cur];

}

if(cur != 1)

ans *= 2;

return ans;

}

struct node

{

int l, r, mid;

int count;

node()

{

count = 0;

}

} seg[3 * maxn];

void build(int l, int r, int num)

{

seg[num].l = l;

seg[num].r = r;

seg[num].mid = (l + r) >> 1;

if(l + 1 == r)

{

seg[num].count = 1;

return ;

}

build(l, seg[num].mid, num << 1);

build(seg[num].mid, r, num << 1 | 1);

seg[num].count = seg[num << 1].count + seg[num << 1 | 1].count;

}

int search(int k, int num)

{

if(seg[num].l + 1 == seg[num].r)

{

seg[num].count--;

return seg[num].l;

}

seg[num].count--;

if(k <= seg[num << 1].count)

{

return search(k, num << 1);

}

else

{

return search(k - seg[num << 1].count, num << 1 | 1);

}

int n, k;

int main()

{

// freopen("in.txt", "r", stdin);

mklist();

while(scanf("%d%d", &n, &k) != EOF)

{

for(int i = 1; i <= n; ++i)

{

scanf("%s%d", ch[i].s, &ch[i].num);

}

int res = 1;

int mac = 1;

for(int i = n / 2 + 1; i <= n; ++i)

{

int tmp = split(i);

if(res < tmp)

{

res = tmp;

mac = i;

}

build(1, n + 1, 1);

int st = k;

int t = search(k, 1);

if(mac == 1)

{

printf("%s %d\n", ch[t].s, res);

continue;

}

int ans = t;

for(int i = 2; i <= mac; ++i)

{

if(ch[ans].num > 0)

{

st = (st + ch[ans].num - 1) % seg[1].count;

if(st == 0)

st = seg[1].count;

ans = search(st, 1);

}

else

{

st = (st + ch[ans].num) % seg[1].count;

if(st <= 0)

st += seg[1].count;

ans = search(st, 1);

}

printf("%s %d\n", ch[ans].s, res);

}

return 0;

}

ACSeed 2012-08-08 16:52 发表评论

uva 11029

ACSeed — Wed, 25 Apr 2012 13:52:00 GMT

太失败了！！
这题主要是log的性质，假设 log10(c) = x = a + b;
其中a是x的整数部分，b是x的小数部分，而 10^b = 10^(x - a) = 10^x / 10^a = c / 10^a;
可见a只影响c的小数点的位置，可以直接去掉，这样可以求出数的前三位，后三位就不用说了吧；

PS：真的好强大

ACSeed 2012-04-25 21:52 发表评论

uva 571

ACSeed — Wed, 25 Apr 2012 11:47:00 GMT

思路只有bfs，可是分类在数学里，所以极力寻求数学方法，分析在这里

http://www.cnblogs.com/devymex/archive/2010/08/04/1792288.html

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

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 发表评论

教程

ACSeed — Mon, 16 Apr 2012 13:37:00 GMT

http://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习题分类

ACSeed — Thu, 05 Apr 2012 12:51:00 GMT

一.动态规划

参考资料：

刘汝佳《算法艺术与信息学竞赛》《算法导论》

简单

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

中等，经典TSP问题

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

中等，状态压缩DP

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

中等

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

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

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

中等，《算法艺术与信息学竞赛》中的习题

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

中等，《算法艺术与信息学竞赛》中的习题

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

中等，《算法艺术与信息学竞赛》中的习题

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

中等，递推

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

中等，需要减少冗余计算

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

中等，四边形不等式的简单应用

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

较难，状态压缩DP，《算法艺术与信息学竞赛》中有解答

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

较难，《算法艺术与信息学竞赛》中有解答

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

较难，需要配合数据结构优化（我的题目^_^）

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

较难，写起来比较麻烦

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

难，状态压缩DP，题目很有意思

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

难

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

非常难

二.搜索

参考资料：

刘汝佳《算法艺术与信息学竞赛》

简单，深搜入门题

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

中等，广搜

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

中等，广搜

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

较难，广搜

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

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

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

难，可重复K最短路，A*。可参考解题报告:

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

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

难，深搜剪枝，《算法艺术与信息学竞赛》中有解答

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

难，《算法艺术与信息学竞赛》习题

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

难，深搜

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

较难，《算法艺术与信息学竞赛》中有解答

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

很难

三. 常用数据结构

参考资料：

刘汝佳《算法艺术与信息学竞赛》

《算法导论》

线段树资料：

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

树状数组资料

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

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

后缀数组资料

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=1151

简单，线段树应用矩形面积并，《算法艺术与信息学竞赛》中有解答

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

较难，线段树应用，可参考解题报告

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

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

难，二维树状数组。

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

中等，线段树应用。

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

难，堆的应用，《算法艺术与信息学竞赛》中有解答

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

中等，左偏树，二项式堆或其他可合并堆的应用。

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

二项式堆参见《算法导论》相关章节

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

中等，并查集

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

中等，字典树

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

较难，多串匹配树

参考： 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

较难，最长公共子串，经典问题，后缀数组

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

很难，后缀数组

可参考解题报告

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

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

很难，数据结构综合运用

四.图论基础

参考资料：

刘汝佳《算法艺术与信息学竞赛》《算法导论》《网络算法与复杂性理论》谢政

简单，欧拉路

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

中等，无向图割边

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

较难，无向图双连通分支

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

中等，最小度限制生成树，《算法艺术与信息学竞赛》中有解答

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

中等，最小比率生成树，《算法艺术与信息学竞赛》中有解答

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

简单，最短路问题

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

中等，差分约束系统，Bellman-Ford求解，《算法艺术与信息学竞赛》中有解答

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

简单，Bellman-Ford

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

中等，网络流

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

较难，网络流

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

中等，二部图最大匹配

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

较难，二部图最大匹配

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

中等，二部图最大权匹配

KM算法参考《网络算法与复杂性理论》

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

较难，二部图最大权匹配

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

中等，LCA（最近公共祖先）问题

参考Tarjan's LCA algorithm 《算法导论》第21章习题

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

较难，2-SAT问题

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

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

较难，2-SAT问题

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

较难，最小树形图

参考《网络算法与复杂性理论》中朱-刘算法

五.数论及组合计数基础

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

简单，素数判定，大数分解

较难，Burnside引理

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

中等，解模方程组

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

中等，经典问题，波利亚定理

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

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

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

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

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

简单，矩阵快速乘法

ACSeed 2012-04-05 20:51 发表评论

ACM 进阶之路（转

ACSeed — Thu, 15 Dec 2011 02:37:00 GMT

一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.
ACM主要是考算法的,主要时间是花在思考算法上，不是花在写程序与debug上。

下面给个计划你练练：

第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，
因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打
出来。

1.最短路(Floyd、Dijstra,BellmanFord)
2.最小生成树(先写个prim,kruscal要用并查集，不好写)
3.大数（高精度）加减乘除
4.二分查找. (代码可在五行以内)
5.叉乘、判线段相交、然后写个凸包.
6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)
7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.
8. 调用系统的qsort, 技巧很多，慢慢掌握.
9. 任意进制间的转换

第二阶段：练习复杂一点，但也较常用的算法。
如：
1. 二分图匹配（匈牙利），最小路径覆盖
2. 网络流，最小费用流。
3. 线段树.
4. 并查集。
5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp
6.博弈类算法。博弈树，二进制法等。
7.最大团，最大独立集。
8.判断点在多边形内。
9. 差分约束系统.
10. 双向广度搜索、A*算法，最小耗散优先.
===========================================================

ACMer必备知识（任重而道远......）

图论

   路径问题
        0/1边权最短路径
        BFS
        非负边权最短路径（Dijkstra）
            可以用Dijkstra解决问题的特征
        负边权最短路径
        Bellman-Ford
            Bellman-Ford的Yen-氏优化
            差分约束系统
        Floyd
            广义路径问题
            传递闭包
            极小极大距离 / 极大极小距离
        Euler Path / Tour
            圈套圈算法
            混合图的 Euler Path / Tour
        Hamilton Path / Tour
            特殊图的Hamilton Path / Tour 构造

    生成树问题
        最小生成树
        第k小生成树
        最优比率生成树
        0/1分数规划
        度限制生成树

    连通性问题
        强大的DFS算法
        无向图连通性
            割点
            割边
            二连通分支
            有向图连通性
            强连通分支
            2-SAT
            最小点基

    有向无环图
        拓扑排序
            有向无环图与动态规划的关系

    二分图匹配问题
        一般图问题与二分图问题的转换思路
        最大匹配
            有向图的最小路径覆盖
            0 / 1矩阵的最小覆盖
        完备匹配
        最优匹配
        稳定婚姻

    网络流问题
        网络流模型的简单特征和与线性规划的关系
        最大流最小割定理
        最大流问题
            有上下界的最大流问题
                循环流
        最小费用最大流 / 最大费用最大流

    弦图的性质和判定

组合数学

    解决组合数学问题时常用的思想
        逼近
        递推 / 动态规划
    概率问题
        Polya定理

计算几何 / 解析几何

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

    基本形
        点
        直线，线段
        多边形

    凸多边形 / 凸包
        凸包算法的引进，卷包裹法

    Graham扫描法
        水平序的引进，共线凸包的补丁

    完美凸包算法

    相关判定
        两直线相交
        两线段相交
        点在任意多边形内的判定
        点在凸多边形内的判定

    经典问题
        最小外接圆
            近似O(n)的最小外接圆算法
        点集直径
            旋转卡壳，对踵点
        多边形的三角剖分

数学 / 数论

   最大公约数
        Euclid算法
            扩展的Euclid算法
                同余方程 / 二元一次不定方程
                同余方程组

    线性方程组
        高斯消元法
            解mod 2域上的线性方程组
        整系数方程组的精确解法

    矩阵
        行列式的计算
            利用矩阵乘法快速计算递推关系

    分数
        分数树
        连分数逼近

    数论计算
        求N的约数个数
        求phi(N)
        求约数和
        快速数论变换
        ……

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

数据结构

    组织结构
        二叉堆
        左偏树
        二项树
        胜者树
        跳跃表
        样式图标
        斜堆
        reap

    统计结构
        树状数组
        虚二叉树
        线段树
            矩形面积并
            圆形面积并

    关系结构
        Hash表
        并查集
            路径压缩思想的应用

    STL中的数据结构
        vector
        deque
        set / map

动态规划 / 记忆化搜索

   动态规划和记忆化搜索在思考方式上的区别

    最长子序列系列问题
        最长不下降子序列
        最长公共子序列
        最长公共不下降子序列

    一类NP问题的动态规划解法

    树型动态规划

    背包问题

    动态规划的优化
        四边形不等式
        函数的凸凹性
        状态设计
        规划方向

线性规划

常用思想

    二分
    最小表示法

串

    KMP
    Trie结构
    后缀树/后缀数组
    LCA/RMQ
    有限状态自动机理论

排序
    选择/冒泡
    快速排序
    堆排序
    归并排序
    基数排序
    拓扑排序
    排序网络

ACSeed 2011-12-15 10:37 发表评论

poj 1896 Code Formatting

ACSeed — Fri, 25 Nov 2011 11:32:00 GMT

http://poj.org/problem?id=1896
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2463
格式化一段代码，格式题目里说的很清楚了。
zoj上的只不过多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 530

ACSeed — Fri, 11 Nov 2011 14:47:00 GMT

求一个组合数，保证结果在整形数内，给定n和k，求C(n,.k);
比较恶心，开始分解质因数，因为N!容易分解质因子，然后必须打出整形内的素数，
果断舍弃，想想不会超过整数，用公式算分子数不会太多，貌似不会超时，试试吧，成功了！！
C(n,n/2)最大了，n到几十就超int了，所以k不会很大，这里的k是指小的，如果k > n / 2 可以
C(n,k) = C(n,n-k),用n-k代替k,边乘边除，12MS AC!

ACSeed 2011-11-11 22:47 发表评论

神棍节3道水题

ACSeed — Fri, 11 Nov 2011 08:25:00 GMT

http://acm.hdu.edu.cn/diy/contest_show.php?cid=13622
第1题神棍数最后三位是471，前面是k-1;
第2题简单模运算
第3题先从n个中选出m个数码兽，然后这m个数码兽做错位排列即 ans = C(n,m) * D(m)；

ACSeed 2011-11-11 16:25 发表评论

C++博客-ACSeed

Wythoff’s Game (威佐夫博弈)

Wythoff’s Game (威佐夫博弈)

poj 2886 没啥，线段树基础应用，纪念一下队长教的打素数的方法

uva 11029

uva 571

教程

(转）ACM基本算法分类、推荐学习资料和配套poj习题 分类

ACM 进阶之路（转

poj 1896 Code Formatting

uva 530

神棍节3道水题

(转）ACM基本算法分类、推荐学习资料和配套poj习题分类