C++博客-c++&oi

USACO总结

zyn.cpp — Sat, 02 Jun 2012 12:23:00 GMT

写在xls里面了，可以参考nocow版的doc。
马鞍山的同学做的时候帮我看看我写的对不对啊。

广告：
我做的丑陋的USACO，大家做的同时帮我参看以下，如果你的方法比我好，或发现我的解法是错的，或者看不懂我的xls里面写的话，请及时告诉我，尤其是马鞍山的同仁们啊。
下载地址：http://dl.dbank.com/c0ecq94jha

zyn.cpp 2012-06-02 20:23 发表评论

SGU计划

zyn.cpp — Sat, 02 Jun 2012 09:35:00 GMT

先做AC人数》1000的
然后800.。。

zyn.cpp 2012-06-02 17:35 发表评论

迎接初中同学——整理OI知识点（building）

zyn.cpp — Thu, 31 May 2012 09:25:00 GMT

这次省赛被初中小朋友虐爆了。
然后中考快（到了）结束了。
迎接一下初中的小朋友。
整理一下个人认为MAS的OIer成长所需的练习。

目录
零。说明
一。学习内容
二。练习题
三。推荐书目
四。资料

零。说明
   -第一部分列举了所有我所知道的要学的知识（不仅仅是的NOIP所需的知识），不要被数量吓到，具体的人我可以具体推荐学习内容。
   -可以直接跳到第二部分做练习，然后对照第一部分，看看自己掌握了那些知识。
   -仅代表个人观点，请以老师的要求为准。
   -我也很弱，互相学习。

一。学习内容（不是很好区分难度，详见练习题）：
0.windos及linux基本的系统命令以及对拍方法。
1.基础知识（待扩展，但觉得只要做USACO就可以掌握）
2.搜索（我们全队都太弱了，一定要加强）
   -N重循环
   -BFS
      =双向
      =判重
         +HASH（尤其是字符串HASH）
         +分段HASH
         +各种数据结构判重（Tire数、平衡树等）
      =A*
   -DFS
      =各种剪枝
   -ID-DFS
   -ID-A*
   -DLX
   -近似算法及其他
      =模拟退火
      =遗传算法
      =随机调整
      =随机贪心
3.DP（主要是自己做题总结，感悟+数学能力）
4.字符串操作
   -c++的string
   -KMP
   -ExKMP
   -最小表示法
   -Tire树
   -AC自动机
   -后缀数组
   -后缀树（好像被淘汰了）
   -后缀自动机【这个可以忽略】
5.数据结构
   -链表
      =普通链表
      =跳跃表
      =Dancing links
   -队列
      =普通队列
      =循环队列
      =单调队列
   -栈
      =手工栈搜索
      =表达式处理
   -堆
      =哈夫曼树
      =可合并堆
         +左偏树
         +斜堆
         +二项堆
   -并查集
   -树状数组
   -线段树(重点推荐)
   -平衡树
      =红黑树（知道理论+会用set和map）
      =AVL
      =Treap
      =超快SBT(重点推荐)
      =万能Splay(重点推荐)
   -块状链表
   -树链剖分（我也不知道）
6.图论与树
   -图的联通性
      =floodfill
      =BFS分层
      =两次BFS求强连通分量
      =拓扑排序
      =关键路径
      =求环
      =欧拉回路
      =汉密尔顿回路
      =Tarjan算法
         +求强连通分量
         +求割点
         +求桥
   -最短路
      =floyd
      =dijstra
      =SPFA
      =dijstra+heap
      =Bellman-ford求差分约束系统
      =floyd*求最小环
      =K短路
      =限制条件最短路
      =分层图最短路
      =状态压缩最短路
   -生成树
      =prim
      =Kruskal
      =prim+heap
      =破环法求最小生成树
      =动态最小生成树
      =次小生成树
      =最大价值比生成树
      =特殊生成树
      =统计生成树的个数（组合数学）
   -树上问题
      -LCA和RMQ
      -节点到根的距离
      -树的直径
      -树的中心
      -任意点对间距离
   - 2-SAT问题
7.网络流（我总结在了第三本笔记本）
   -二分图
      =匈牙利算法
      =KM算法
      =覆盖集与独立集
      =最小路径覆盖
   -最大流
      =DINIC
      =SAP
      =HLLP
      =有上下界的最大流
   -最小割
      =求当前流的最小割
      =平面图最小割转最短路
      =闭合图
      =最小点权覆盖集与最大独立点权集
      =0/1分数规划
      =最大密度子图
   -费用流
      =最短路增广费用流
      =zkw-费用流最小费用可行流
   -构图技巧（请学习网络流24题，作者：郭家宝）
8.数论（我总结在了最终笔记本）
   -gcd
      =stein算法
      =欧几里得算法
      =拓展欧几里得算法
   -质数
      =MR测试
      =快速幂
      =sqrt（n）判定
      =反质数
      =算数基本定理及推论
   -同余
      =威尔逊定理
      =费马小定理
      =欧拉定理
      =中国剩余定理
   -进制相关
      =精制转换=高精循环小数
      =Self-number
   -其他
      =px+qy命题
      =求n！位数的方法及推广
      =P^xTm！的应用
9.组合数学（还未学习）
10.计算几何（还未学习）
11.博弈论（还未学习）
12.概率论（还未学习）
13.高等数学与线性代数（正在学习）

二。练习题
NOIP：
   -USACO-C1~C4（我AC了）
   -大部分NOIP真题
省选：
   -所有NOIP真题（我差一点）
   -部分NOI真题（基本没有做）
   -USACO-C5~C6（我AC了）
   -SGU能做多少做多少（我还没做）
更高更妙：（完全非我所及，但你们会超过我的）
   -USACO上的各种比赛
   - www.topcoder.com/tc
   - www.codeforces.com
   说明：http://hi.baidu.com/buaa_babt/blog/item/522fb239ef912cdc7d1e71b5.html

三。推荐书目（我买了好多书放在二中）

四。资料（还未整理）

zyn.cpp 2012-05-31 17:25 发表评论

发现KM算法好重要

zyn.cpp — Sat, 05 May 2012 12:43:00 GMT

费用流的时间给予流量，而KM只与边和点有关，时间复杂度不是一个级别的。。。。

同时发现我写的DINIC比匈牙利算法还快,为什么呢？匈牙利算法是递归的吧。。。

zyn.cpp 2012-05-05 20:43 发表评论

小发现

zyn.cpp — Fri, 04 May 2012 10:37:00 GMT

memcpy的速度是直接一个一个复制4～5倍
用法:
复制a[i..i+k]给b[j..j+k]
memcpy(b+j,a+i,sizeof(a[0])*(k+1));
显然a和b到类型要一样的。

zyn.cpp 2012-05-04 18:37 发表评论

简要的说一下

zyn.cpp — Tue, 01 May 2012 12:43:00 GMT

简要的说一下,就是最近用电脑多了，视力有些下降。
反思一下，其实搞OI不须要天天做题写程序的，于是就放弃了一天两题的计划。
觉得大部分时间应该放在学习、思考和整理上，一周上机不超过10h（推荐8h），分两到三次
其它的时间应该结合书和打印的资料学习，于是后面就不怎么更新了。

zyn.cpp 2012-05-01 20:43 发表评论

USACO5.3.2window

zyn.cpp — Fri, 27 Apr 2012 14:29:00 GMT

最方便的快捷的方法，当然是离散化。
C++里面有些东西还是不熟啊，比如那个switch
/*
USER: zyn19961
TASK: window
LANG: C++
*/
#include
#include
#include
#include
#include
//
    using namespace std;
#define MM(a,i) memset(a,i,sizeof(a))
#define FOR(i,l,r) for (int i=(l);i<=(r);i++)
#define PFOR(p,a,next) for(int p=a;p;p=next[p])
//
    typedef long long int64;
    const int INF=~0U>>2;
//
    int maxp=0, minp=0;//maxp最后面的， minp最前面的
    class Window{
        public:
        int x1,y1,x2,y2,pos;
        void init(int a, int b, int c, int d){
            if(a>c)swap(a,c);if(b>d)swap(b,d);
            x1=a,y1=b,x2=c,y2=d,pos=minp--;}
        double area(){return (x2-x1)*(y2-y1);}
        };
    Window window[256];
    bool map[300][300];
    int hx[50000],hy[50000];
    int fx[1000], fy[1000];
    double query(char ch){
        MM(hx,0),MM(hy,0),MM(fx,0),MM(fy,0);
        int fxn=0,fyn=0;
        //step 1, 找出在ch前面的窗口
        //step 2, 离散化
        FOR(i,0,255)
            if(window[i].pos!=-INF)// && i != ch){
                if(window[i].pos<=window[ch].pos)
                    hx[window[i].x1]=true,hx[window[i].x2]=true,
                    hy[window[i].y1]=true,hy[window[i].y2]=true;
        FOR(i,0,32767){
            if(hx[i])fx[fxn++]=i,hx[i]=fxn-1;//else hx[i]=-1;
            if(hy[i])fy[fyn++]=i,hy[i]=fyn-1;//else hy[i]=-1;
            }
        //step 3, fillflood
        MM(map,false);
        FOR(i,0,255)
            if(window[i].pos!=-INF&&i!=ch){
                if(window[i].pos                    int bx=hx[window[i].x1],
                        by=hy[window[i].y1];
                    for(int x=bx;fx[x]                        for(int y=by;fy[y]                            map[x][y]=true;
                }
            }
        //step 4, 计算面积百分比
        double area=window[ch].area();
        int bx=hx[window[ch].x1],
            by=hy[window[ch].y1];
        double white=0.0;
        for(int x=bx;fx[x]            for(int y=by;fy[y]                if(!map[x][y])
                    white+=(fx[x+1]-fx[x])*(fy[y+1]-fy[y]);
            }
        return white/area;
        }
    int main(){
        freopen("window.in","r",stdin);
        freopen("window.out","w",stdout);
        char op, ch;
        int x1,y1,x2,y2,cnt=0;
        while(scanf("%c",&op) != EOF){
            if (op!='s')
                scanf("(%c,%d,%d,%d,%d)\n",&ch,&x1,&y1,&x2,&y2);
            else
                scanf("(%c)\n",&ch);
            switch(op){
                case 'w': window[ch].init(x1,y1,x2,y2);break;
                case 't': window[ch].pos=minp--; break;
                case 'b': window[ch].pos=maxp++; break;
                case 'd': window[ch].pos=-INF;   break;
                case 's': printf("%.3f\n", query(ch)*100); break;
                default: break;
                }
            }
        return 0;
        }

zyn.cpp 2012-04-27 22:29 发表评论

二分搜索

zyn.cpp — Sat, 21 Apr 2012 10:57:00 GMT

就是把搜索分成两个部分，时间变成sqrt（org）。
=AHOI07.2.3
=素数环

zyn.cpp 2012-04-21 18:57 发表评论

USACO Charper6 AC

zyn.cpp — Sat, 21 Apr 2012 03:36:00 GMT

由于Charper5存在过于变态的搜索， Charper6比Charper5先完成了。
第一题，vans递推题（据说可以用状态压缩DP），我的解决方式是不能说的秘密，本地的同学有兴趣可以当面问我，反正是不易外传（就当我是看了题解然后解决的吧！）。
第二题rectbarn据说有两种解法，我会的当然是DP，于是就DP掉了。
第三题cowxor感觉属于DP，然后用树这种数据结构辅助解决。

结合 Charper6的标题《大赛实践》可以推测：比赛的主要内容就是DP+图论+数据结构。

完毕。

zyn.cpp 2012-04-21 11:36 发表评论

在MEL和WA之间徘徊，艰难地独立地AC了cowxor

zyn.cpp — Thu, 19 Apr 2012 16:22:00 GMT

先是累加（xor，一开始真写成+了，结果查了那么久。。。。）
然后作差，感觉类似单调DP，有一类单调DP使用平衡树的，但这个不需要用平衡树，只要用tire树。
考虑到0/1性和最坏情况下树的密集度，于是写了静态完全二叉树。。。。
于是MLE，然后降低maxa，RT，同时降低maxt，WA。
然后左右斟酌提交多次，MLE或WA。
最后卡常数，把树的前maxt-1层用bool，最后一层用int。。。。。AC了。。。。。

被改残的代码

USACO的空间限制到底是多少？？？？

zyn.cpp 2012-04-20 00:22 发表评论