平面图基本题目

1 Comment

1。复习了下平面图的理论部分,平面图最重要的莫过于“欧拉5色原理”,即一个任意的平面图,都能使用不超过5色来使得相邻区域颜色不一致。

  • 欧拉定理:设有一个连通平面图G,共有v个节点e条边r块面,则v-e+r=2;
  • 推论1:给定G=<V,E,F>,若|V|>=3,则|E|<=3|V|-6,且|F|<=2|V|-4
  • 推论2:若|V|>=3,则存在v<V,使得d(v)<=5;

2。个人觉得没意思,记不住就翻书嘛,再说画出图来证明下就没问题了。还是来个与编程相关的。

procedurce Paint(G:Graph)
begin
  找出度最小的点v0
  Paint(G-v0)
  if 在图中无法找到对v0着色 then
          对v0的相邻店枚举双色对[见黑书],用UFS检测是否在同一分量中;
     若v1,v3在不同分量中,则提取v1的颜色使得其颜色与v3相同,然后把空闲的颜色给v0;
     否则,v2,v4在不同分量中,处理之
  end
end

先来个不是很相关的题目, Timus Online Judge.这道题目考的很简单,二分图处理问题[BFS可以作为二分图验证,第一,验证深度是否相差为奇数;第二,父节点和子节点不同色,注意gray的边界处理,很多书上没有处理这种边界,对于环路的时候程序是不稳定的,谨慎谨慎]

当然这种菜题不是我追求的,主要犯了个错!开始用前向星做的,然后由于是无向图,需要将一条边再次插入,结果vs[]变化了,想了下没好办法,就简单水过了事!

  • 1080. Map Colouring

Time Limit: 1.0 second
Memory Limit: 16 MB

Recent submissions

Problem: Map Colouring

ID

  Author

    Problem

  Language

  Judgement result

  Test #

 Execution time

 Memory used

2521921 

   

orlando22   

  1080

  C++

  Accepted

 

  0.031

  301 KB
 
#include <iostream>
#include <queue>
#include <fstream>
//1080 Map Colouring, Timus Online judge
using namespace std;
const int N=99;
enum{red=0,blue=1,white=-1,gray=-2};
int n;
typedef struct Node{
    int i;
    Node* next;
}Node, *Pnode;
Pnode list[N+1];
Node buffer[N*N];
int bufid=0;
//declaration
void insert(int i, int j){
    //for i->j
    Pnode newnode=&buffer[bufid++];
    newnode->i=j;newnode->next=NULL;
    Pnode cur=list[i];
    for(;cur&&cur->next; cur=cur->next);
    if(!cur) list[i]=newnode;
    else cur->next=newnode;
}
//for color and parent
int color[N], p[N];
#define fbase
int main()
{
    #ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif
    //implementation
    cin>>n; int tmp;
    for(int i=0; i<n; i++){
        while((cin>>tmp)&&tmp)
            insert(i, tmp-1),insert(tmp-1, i);
    }
    memset((void*)color, 0xff, sizeof(int)*n);
    p[0]=-1;
    queue<int> q;
    q.push(0);
    while(q.size()>0){
        int c=q.front(); q.pop();
        for(Pnode child=list[c]; child; child=child->next){
            if(color[child->i]==white){
                color[child->i]=gray;p[child->i]=c;
                q.push(child->i);
            }
            else if(p[c]!=-1&&color[child->i]!=gray&&color[child->i]!=color[p[c]]){
                cout<<-1<<endl;return 0;
            }
        }
        if(p[c]==-1) color[c]=red;
        else if(color[p[c]]==red) color[c]=blue;
        else if(color[p[c]]==blue) color[c]=red;
    }
    for(int i=0; i<n; i++) cout<<color[i];
    cout<<endl;
    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase
 
  • VII Olimpiada Informatyczna 1999/2000
Task: NAR
Author: Marcin Kubica
Skiers[stage I]
公正的评价这道题目不难,折腾料半天,但还好每次代码都没写多长!现在对这种一次写出来,连错都查不出的题,真的一点办法都没有!只能说好好细心研究吧!
分析如下:
1.题目是要求最大路,lrj说很容易让人想到最大流,俄!确实是的,但orlando有两个不同的想法!
2.DFS的贪心,lrj提示的方法,不过如何做却需要好好思考下:
由于每条路径不相交,因此需要做个的判断[开始想成边了,说老是不对呢];但这里会存在一个问题,那我什么时候才晓得,这个点是有效点[对路径有贡献的点]呢?当然是通过这个点的路径,有且只有一条,能使得最终路径增加一条,或者把所有边都用完料,还不行就自认倒霉吧!这里我又有个思路错了,开始写了句来将此点重置,好让其他点能再次访问,但出现料死循环.仔细分析下,确实如此,这样的话,一条无效路径就会不停的进入,然后再测试,再进入,再测试!
我们可以这样认为,假设此点不能使其增加一条有效路径,说明下面的路径,从此点到终点的路径已经被完全堵死,那么这个点也就没有再访问的必要了!
3.其实更简单的思路是什么当然是BFS,用一个队列来记录其可达深度,对于有交叉的中间点,直接合并,同时计数,这样到最后的接点之后,有效路径就是最大化的了.我们可以这样看,开始的时候,其最大路径为1的出度,然后向下一层,找到一个交叉点,合并一条路径,到达最后就是合法的最大路径.
4.最后才是最大流解题,一是本菜对最大流不熟悉,二是题目才菜,不用杀牛刀了.我一定能把最大流掌握的很熟练,动规也是!
好,代码如下:
GNU: 29ms,已通过官方测试文件nar0-nar8
#include <iostream>
#include <fstream>
//POI 1999/2000 Skiers
using namespace std;
const int MAX=5000;//2<=n<=5000
int n, vs[MAX+1], lenofE, maxofski, es[MAX*MAX];
char v[MAX+1];
//declaration
void dfs(int i);
//implementation
void dfs(int i){
    if(i==n-1){
        maxofski++;return;
    }
    //for each child
    for(int k=vs[i]; k<vs[i+1]; k++){
        //edge is available
        if(!v[es[k]]||es[k]==n-1){
            v[es[k]]=1;
            int pre=maxofski;
            dfs(es[k]);
            if(i==0) continue;
            else if(pre+1==maxofski) break;
            //else v[es[k]]=0;自己想想为什么?
        }
    }
}
#define fbase
int main()
{
    #ifdef fbase
    ifstream in("nar8.in");//
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif
    //implementation
    int lenc;lenofE=0;
    cin>>n;
    memset((void*)v, 0, n);
    for(int i=0; i<n-1; i++){
        cin>>lenc; vs[i]=lenofE;
        for(int j=0; j<lenc; j++){
            cin>>es[lenofE];es[lenofE]–;
            lenofE++;
        }
    }
    vs[n-1]=lenofE;
    maxofski=0;
    dfs(0);
    cout<<maxofski<<endl;
    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase
  • 似乎今天的三道题目除了第一道之外,其它都太简单了!所以,明天的开始是这么一道.貌似比较难.
Horizontally Visible Segments-Central Europe 2001
Time Limit: 5000MS  Memory Limit: 65536K
图论要加油了,明天还有三道动规!休息了!
 
分析:
  • 理论分析:这道题目实际上是求线段的相邻公共覆盖,黑书的分析有道理!但由于篇幅没有证明,这里简单说下,第一,要证明"三元组"实际上是一个平面图基础上的"三元组"验证.投映为图关系,实际上就是要证明两个含相邻边的“平面三角形”不可能有对边,这个很容易反证。第二,就是在生成的平面图里面计算三元组个数了,由于相邻的定义,是k对应于k-1,k+1,那么这个映射应该是很简单的。
  • 编程分析

1。难在线段树的生成上,要花点功夫,lrj有个很巧妙的思路!端点是很难分析的,如何做呢?简单的说就是将原来的端点展开为线段,然后再统一处理,如下图所示,lrj书上写的东西,我没看懂,估摸着应该是这个意思吧!

2。然后这点我还在思索中,如何才能让生成的平面图更高效呢?两种等价的选择,前向星和邻接表,问题在于我需要删边,当然我可以做一个标志位,但这个不好,因为扫描规模并没有随有效边的减少而变少,所以最好是将其删掉,如果用前向星,那么每次删边必然要处理整个边数组的移动,非常不好;所以邻接表应该更好,如果用Jon的统一内存分配的话,我甚至可以不管内存的回收。个人比较倾向这种做法,但pku上有牛人说空间占的太大,所以我有点犹豫!

研究了以下lrj的思路[貌似有点混乱,主要我太菜了,精神领会到了],确实没看懂!核心应该是用静态线段树来处理,自己随便想了个招!

对于此题,Top区间宽度为8000-0=8000,那么树深度Log8000+1[含端点]=13+1,一共结点有:2^14-1=16383[取17000].剩下的没什么好说的,用静态线段树的逻辑处理即可。说到专门的线段树,还有两道相关的题目:MatrixA Simple Problem with Integers,一起切了吧!

Advertisements

基本图论最后一题

Leave a comment

  • 牛题:超级翻转,遗憾的是没找到judge online的地方。
  • 出处:IOI2003国家集训队原创题目,连接地址[直接贴题]

题目5(0072):超级翻转
推荐者:许智磊

有一个N*N的网格,每一“格”上有一个可以翻转的方块,方块的两面分别涂成黑、白两种颜色。另外,有一个沿着网格线活动的东西——不妨称之为“动子”。初始时,每个方块随机地被翻成黑或白色,“动子”停在网格线的某个顶点上。例如图一就是一个4*4的网格的一种可能的开局情况。

“动子”在网格线上运动时,从一个顶点A到相邻的另一个顶点B之后,以网格线AB为边的两个或一个网格上的方块就会翻转——白变黑,黑变白。例如图一的“动子”向右移动一步之后变成图二,向下移动一步之后变成图三。

 
问题是:给定一个初始状态和一个目标状态,求“动子”的一种运动轨迹,可以把初始状态翻转成目标状态,最后“动子”停在哪里是无所谓的。

知识点:模线型方程组,UFS[DFS连通块],欧拉路

只看这三个知识点,就晓得要好好研究下了! 

1。理论证明:

  • 一个格子的初末状态不同,那么其四周的边必然被经过了2k+1次,否则为2k次。[充要]
  • 对于任何一个“动子”中间位置V[V!=Start,End],或者初末一致[S=T],其四周的相邻边必然被经过了2k次;若是初末不同[S!=T]状态,则被经过了2k+1次。[充要,可以反证]

2。求解:[黑书上说的很清楚]

  • Xi[i=1,2n+1]偶数则为0,奇数则为1。
  • 利用格子顶点分别建立模线形方程组,求出其解,无解则不存在通路。
  • 合并连通块,如下图所示。多个连通块则要进行添边合并,这个比较简单,加2即可。

  • 求出一条从S到T的欧拉路。

说起清楚,编码却并不轻松。

3。编码准备工作

  • 棋盘类问题,首先是要解决坐标映射问题,这道题目里面存在三个对象:格子以及顶点。研究了下,做了一个简单的映射函数,关系如下图所示:

  • 随后的问题就是模线型方程组的建立,这块不是很熟悉,转化下![暂时放下,感觉应该有现成的方法]
  • 合并连通块,这个可以用UFS来实现,不用多想2N(N+1)
  • 从S到T的欧拉路,这个让我有点犯难,怎么做呢?最好不建立显式的图结构,用传统的图结构还要转化,根据图的特点,我们可以把Edge[x]作为其默认的边,向四个方向查找即可。
  • 好了,这点补在最后,问题还在于是否能解出有解的方程就一定能有连通路呢?实际上是一定存在的,为什么呢?想想我们怎么设定模方程的,对于途中的点V,所有相邻边经过为偶数[0],这个条件等价于对于途中的任意结点其出度等于入度,这正是欧拉路的充要条件,因此只要模方程组有解,欧拉路是存在且不一定唯一的。[这点我对IOI2003大牛们的分析深有同感,所以这道题目是可行解易求,思路清晰,但最优解不容易。这相当于要回溯所有的欧拉路,然后再比较其步长。]

4。编码的最后方案

  • 棋盘转化方案上面已经有了,就不多说了
  • 解多元一次模线型方程组的方法,网上有很多论文都看不成,那只有用最笨的办法,CSP作搜索了,但由于是2^(2n(n+1)),n=4时,规模是2^40!唉!数学不好就只能这样做了!
  • 剩下的没啥说的,连通查找和欧拉路!

图论基本题目

Leave a comment

  • 我已经下决心了,以后再也不用DFS来找连通分量!还要开个多大的标志位,还是UFS好!

Primitivus – VI Olimpiada Informatyczna 1998/1999

一道很简单但很复杂的题目:基因编码 POI的一道基本图论题目,分析如下

1。将(l,r)映射为有向边,然后用UFS来合并连通分量,统计每一个连通分量里面的|in-out|

2。假设我们能找到一条欧拉回路或者道路,那么OK可以说明其最短路径。但这道题妙就妙在,不需要求出具体的欧拉回路是什么,只需要路长,如何分析呢?我们把原来条件中的路径按某种排列展开,如果是一条欧拉路[回路或道路],那么就没问题了,否则就要添上一些边,让它能组成一条欧拉路。

用欧拉回路的充要条件:一个连通分支,加所有点入度和出度差为0。

分情况讨论:若只有一个连通分支,且出入度绝对值之差和为N,那么我们应该要加N/2+1或者N/2,来构成欧拉回路,不过欧拉道路就可以了,因此N/2;

若有多个连通分支,对于当前计算的连通分支A,假设其存在欧拉回路[出入度为0],那么需要加对于整个图而言需要加一条边,但是考虑到一条边一定会搭到某一个连通分支上,因此这个增量可以视为下一个连通分量的增加值,因此当前不增;[POI牛人链接,牛人就是这里搞错了,估计写的太快了吧!]

而若当前分支A,出入度之差不为0,那么要增加N/2条边,其中一条边要搭到下一个分支上,那么算下一个分支的时候,我们是否要减去这条边呢,其实不用了;假设N/2形成的是欧拉回路,那么这条边搭到下一个分支上,我们可以知道下一个分支增值其实是不变的,因为我们取得是下取整!而假设是欧拉道路呢,则需要增加一条边,并且在下一个分支里面减去一条边,因为下一个分支N/2至少会形成一个欧拉道路,因此平均的效应就是当前的分支增加N/2即可.

代码实现:没找到judge online的地方,POI的测试用例都过了的!本来想用eager evalation来做Union的,想了下,好像没必要,所以就写料个函数完事!

GNU:293ms

#include <iostream>
#include <fstream>
//POI 1999, Primitivus , 1 <= l <= 1000, 1 <= r <= 1000, (l,r) and l!=r
using namespace std;
const int MAX=1001;
int A[MAX];//1…1000, in and out degree counting
int C[MAX];//connective components
int vn;
//UFS implementation
class UFS{
private:
    int T[MAX],t1;
public:
    UFS(){
        memset((void*)T, 0xff, sizeof(int)*MAX);
    }
    void adjust(int tsize){
        this->t1=tsize;
    }
    int find(int i){
        if(i<1||i>=MAX) return -1;
        int v=i,p;
        while(T[v]>0) v=T[v];
        p=v,v=i;
        while(v!=p){
            int tmp=T[v];
            T[v]=p;
            v=tmp;
        }
        return p;
    }
    void Union(int i, int j){
        if(i<1||i>=MAX||j<1||j>=MAX) return;
        int r1=find(i), r2=find(j), tmp;
        if(r1==r2) return;//sign!用紫色标记出来这个问题,Union的时候,千万要注意是否属于同一!!!!!!死循环!!!!!!!
        if(T[r1]<T[r2]){//r1 has more elements
            tmp=T[r2]; T[r2]=r1;
            T[r1]+=tmp;
        }
        else{
            tmp=T[r1]; T[r1]=r2;
            T[r2]+=tmp;
        }
    }
    int TorNot(int i, int j){
        if(i<1||i>=MAX||j<1||j>=MAX) return -1;
        return (find(i)==find(j));
    }
    //lazy evalation
    void TGroup(int& size){
        int i=0;
        C[i++]=0;
        for(int j=1; j<=t1; j++)
            if(T[j]<0) C[i++]=j;
        size=i;//1…i-1
    }

};
UFS u;

#define fbase
int main()
{
    #ifdef fbase
    ifstream in("PIE0.IN");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif

    //implementation
    long n, total;
    int maxv=-1, start, end, tsize=0;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>start, cin>>end;
        A[start]++, A[end]–;
        u.Union(start, end);
        if(start>maxv) maxv=start;
        if(end>maxv) maxv=end;
    }
    u.adjust(maxv);
    for(int i=1; i<=maxv; i++)
        if(A[i]<0) A[i]*=-1;
    for(int i=1; i<=maxv; i++){
        int tmp=u.find(i);
        if(tmp!=i) A[tmp]+=A[i];
    }

    total=n;
    u.TGroup(tsize);//看来看去,只有这里比较有价值,但好像似乎,估摸着。。。不太规范!
    if(tsize==1){
        if(A[C[1]]==0);//OK
        else total+=(A[C[1]]>>1);//OK
    }
    else{//tsize>0
        for(int i=1; i<=tsize; i++){
            if(A[C[i]]==0);//add one edge
            else total+=(A[C[i]]>>1);
        }
    }
    cout<<total<<endl;

    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase

  • 星期三很失败的一天,我不说什么了!基本什么都没过!明天压力大了!好好休息!省下力气来做题吧!
  • 图论确实比较难,不过好在理论基础还打得比较好,适应一下就好了!

1。Euler路的Euler Circuit算法,加前向星构图,Timus Online Judge上的online judge有问题,这道题目明显是多解[欧拉游程在多数情况下不可能是单一解的],自己写了两个用例确实如此! [先放下,觉得思路有点卡,等把下面的题目过了,再回来研究用例!那个管理员多好的,还答应给我发数据过来,平易的牛人压!]

2。用STL的list来做了个链表插入,本来没什么说的,只是怕自己忘了,iterator失效的问题,随便提下!

GNU:

0.015  Memory :  

221 KB

#include <iostream>
#include <list>
#include <fstream>
//Timus Online Judge, 1129. Door painting
//forward star for graph
//Vertexs N<=100, Max Edges are C(n,2)=5000
using namespace std;
const int MAXV=100,MAXE=50000;
typedef struct Edge{
 int s,e,link;
 bool v,add;
}Edge;
Edge es[MAXE];
typedef struct Vertex{
 int sv,d;
}Vertex;
Vertex vs[MAXV+1];//for last one
typedef list<int>::iterator INIITER;
char visited[MAXV]={0}, buffer[MAXE]={0}, status[MAXE]={0}, vertexs[MAXV]={0};
enum {white=0,gray=1,black=2};
//for all vertexs in the graph
int n,lenofE,bufid=0,staid=0;

//declaration
bool dfs(int i);
void solution(int iodds);
int insert(int s, int e, bool append);
//euler circuit algorithm
void euler(int i, list<int>& circuit);
void dfs_loop(int i, const int& start, int cur, list<int>& circuit, char* path, char* check, bool& stop);

//implementation
void dfs(int i, bool& connected){
 if(visited[i]!=white) return;
 //not visited
 //dummy implementation
 visited[i]=gray;
 for(int k=vs[i].sv; k<vs[i+1].sv; k++)
  if(visited[k]==white) dfs(k, connected);
 visited[i]=black;
 if(visited[0]==black){
  connected=true;
  for(int j=0; j<n; j++)
   connected=connected&&(visited[j]!=white);
 }
}
void solution(int iodds){//change into even edges for each odd vertexs
 int len=(iodds>>1)+1;
 for(int i=0,start=0; i<len&&start<n; i++){
  while(!(vs[start].d&0x1)) start++;
  int s=start;start++;
  while(!(vs[start].d&0x1)) start++;
  int e=start;start++;
  int e1=insert(s, e, true);
  int e2=insert(e, s, true);
        es[e1].link=e2,es[e2].link=e1;
 }//Add Edges done!
 for(int i=0; i<n; i++){
        for(int k=vs[i].sv; k<vs[i+1].sv; k++){
            int e=es[k].e;//i->e
            for(int p=vs[e].sv; p<vs[e+1].sv; p++)
                if(es[p].e==i&&!es[p].add) es[p].link=k,es[k].link=p;//前向星的无向图改进,把对等的边关联起来!
        }
  vertexs[i]=vs[i+1].sv-vs[i].sv;//copy vertex[i]
 }
 lenofE=vs[n].sv;
 list<int> path;
 euler(0, path);path.push_back(0);
 INIITER pre=path.begin(), s=path.begin();s++;
 for(; s!=path.end(); pre++,s++){
  int s1=*pre, e1=*s;
  for(int v=vs[s1].sv; v<vs[s1+1].sv; v++){
   if(es[v].e==e1&&!es[v].add)
                es[v].v=false, es[es[v].link].v=true;//for G color
  }
    }
 for(int i=0; i<n; i++){
  for(int v=vs[i].sv; v<vs[i+1].sv; v++){
   if(!es[v].add){
    if(es[v].v) cout<<"G";
    else cout<<"Y";
    if(v+1!=vs[i+1].sv) cout<<" ";
   }
  }
  cout<<endl;
 }
}
//euler path
void euler(int i, list<int>& circuit){//欧拉游程的套圈算法
 memset((void*)visited, 0, n);
 char *path=buffer+bufid;bufid+=lenofE;
 char *check=status+staid;staid+=n;
 memset((void*)check, 0, n),memset((void*)path, 0, lenofE);
 bool stop=false;
 visited[i]=1;
 dfs_loop(i, i, 0, circuit, path, check, stop);
 //once we have more than two path for single node?
 list<int> sub;
 //circuit status
 for(INIITER j=circuit.begin(); j!=circuit.end(); j++) visited[*j]=1;
 INIITER end=circuit.end();
 for(INIITER j=circuit.begin(); j!=end; j++){
  if(visited[*j]==1&&vertexs[*j]!=0){
   sub.clear();
   euler(*j, sub);
   if(sub.size()>1){
    circuit.insert(j, sub.begin(), sub.end());
    j=circuit.begin(),end=circuit.end();
   }
  }
 }
 //recovery
 bufid-=lenofE,staid-=n;
}

void dfs_loop(int i, const int& start, int cur, list<int>& circuit, char* path, char* check, bool& stop){
 if(stop) return;
 if(i==start&&check[i]){//find dfs loop
  for(int j=0; j<cur; j++) circuit.push_back((int)path[j]);
  stop=true;//just find one loop, avoid two circuit together
  return;
 }
 check[i]=1,path[cur]=i;
 for(int k=vs[i].sv; k<vs[i+1].sv; k++){
  int end=es[k].e;
  if((!check[end]||es[k].e==start)&&!es[k].v&&!stop){//target non-visited, and target edge exists
   es[k].v=true;
   int j=es[k].link; es[j].v=true;
   vertexs[i]–;vertexs[end]–;
   dfs_loop(es[k].e, start, cur+1, circuit, path, check, stop);
   if(!stop){
    es[k].v=false;es[j].v=false;
    vertexs[i]++;vertexs[end]++;
   }
  }
 }
}

int insert(int s, int e, bool append){//insert s->e into es
 int end=vs[s+1].sv;
 for(int i=vs[n].sv-1; i>=end; i–) es[i+1]=es[i];
 es[end].s=s,es[end].e=e,es[end].add=true,es[end].v=false;
 //modify starting position
 for(int i=s+1; i<=n; i++) vs[i].sv++;
 return end;
}

#define fbase
int main()
{
#ifdef fbase
 ifstream in("input.txt");
 if(!in) return EXIT_FAILURE;
 cin.rdbuf(in.rdbuf());
#endif

 //implementation
 cin>>n;
 int iofE=0,iodds=0;
 for(int i=0; i<n; i++){
  vs[i].sv=iofE;
  cin>>vs[i].d;
  if(vs[i].d&0x1) iodds++;
  for(int j=0; j<vs[i].d; j++, iofE++){
   es[iofE].s=i,es[iofE].v=false, es[iofE].add=false;
   cin>>es[iofE].e;es[iofE].e–;//why? here is error, char type is different from int
  }
 }
 //last item, dummy implementation
 vs[n].sv=iofE,vs[n].d=-1;
 if(iodds&0x1){
  cout<<"Impossible"<<endl;return 0;
 }
 bool connected=false;
 dfs(0, connected);
 if(!connected){
  cout<<"Impossible"<<endl;return 0;
 }
 //OK, valid items for graph
 solution(iodds);
#ifdef fbase
 in.close();
#endif
 return 0;
}
#undef fbase

  • 欲哭无泪,我连优化都不想做了,这道题目让我尝到了什么叫简单到你不用脑壳想,但就是搞不出来!

图论第一题就简直让我放弃了,终于找到原因了!http://acm.pku.edu.cn/JudgeOnline/problem?id=1257 Cross-stitch.

知识点:连通量的DFS;以及图映射。注意哈:唯一难的地方在我们可以求出一个顶点的真值,然后再求和,一点都不麻烦;唉!邻接表居然都能写错!我的天呀!当然能加速,可以用UFS来做通量的合并,这样不做DFS,会快一点,唉!轻视ACM的任何一道题,都要自食其果的!

我一直自信:邻接表,肯定不会错的!结果就是邻接表出的错!这道题目也创纪录了,之慢!LLV吐了,上次那道叫Bugs的程序是由于本来题目就比较难,这种菜题也花这么多时间,我只能说太失败了,只有用后来的行动来洗刷耻辱料!

Source Code

Problem: 1257

User: orlando22

Memory: 6036K

Time: 1844MS//我心都凉了!

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    
    using namespace std;
    const int MAX=40600;//(1+200)*(1+200)
    typedef struct Lnode{
        int i;//256 char type, estimate
        Lnode *next;
    }Lnode, *Pnode;
    Pnode llist[MAX];
    int lt[MAX];
    char visited[MAX];
    int n,m,total,threads;
    enum {white=0, gray=1, black=2};
    
    //declaration
    void insert(int i, int j, int r);
    int dfs(int i);
    
    //implementation
    void insert(int i, int j, int r){
        //for i->j, and j->i, i<j
        Pnode cur=llist[i];
        for(;cur&&cur->next&&cur->i!=j;cur=cur->next);//next is not null
        if(!cur||(!cur->next&&cur->i!=j)){//cur=NULL, last item
            Pnode n1=new Lnode;
            n1->i=j,n1->next=NULL;
            if(!cur) llist[i]=n1;
            else cur->next=n1;
            //insert for j
            Pnode n2=new Lnode;
            n2->i=i,n2->next=NULL;
            Pnode n=llist[j];
            for(;n&&n->next;n=n->next);//n may NULL
            if(!n) llist[j]=n2;
            else n->next=n2;
        }
        //else cur!=NULL&&cur->i==j;
        if(r==1) lt[i]++,lt[j]++;
        else lt[i]--,lt[j]--;
    }
    int dfs(int i){
        int tmp=lt[i];visited[i]=gray;
        //list node traverse
        for(Pnode cur=llist[i]; cur; cur=cur->next){
            if(visited[(int)cur->i]==white&&llist[(int)cur->i]!=NULL)
                tmp+=dfs((int)cur->i);
        }
        visited[i]=black;
        return tmp;
    }
    
    int main()
    {
        //implementation
        cin>>n,cin>>m;
        total=(n+1)*(m+1);
        memset((void*)lt, 0, sizeof(int)*MAX);
        memset((void*)visited, 0, MAX);
        memset((void*)llist, 0, sizeof(Pnode)*MAX);
        char c;
        for(int k=1; k>=0; k--){
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    cin>>c;
                    if(c=='.') continue;
                    //left_top:(i*m+j)+i,right_top:(i*m+j)+i+1,left_bottom:i*(m+1)+j+m+1,right_bottom:i*(m+1)+j+m+2
                    else{
                        if(c=='\\')
                            insert((i*m+j)+i, i*(m+1)+j+m+2, k);
                        if(c=='/')
                            insert((i*m+j)+i+1, i*(m+1)+j+m+1, k);
                        if(c=='X'){
                            insert((i*m+j)+i, i*(m+1)+j+m+2, k);
                            insert((i*m+j)+i+1, i*(m+1)+j+m+1, k);
                        }
                    }
                }
            }
        }
        //llist done, set value
        for(int i=0; i<total; i++)
            if(lt[i]<0) lt[i]*=-1;
        //DFS to find the linked block
        threads=0;
        for(int i=0; i<total; i++){
            if(visited[i]==white&&llist[i]!=NULL){
                int pre=dfs(i);
                if(pre==0) threads+=1;
                else threads+=(pre>>1);
            }
        }
        cout<<threads<<endl;
    
        return 0;
    }
  • E路的练习:1129. Door painting http://acm.timus.ru/problem.aspx?space=1&num=1129
改造欧拉回路题目!加油,A了它!
  • 先看个基本问题,如何求A[0…n-1]的逆序数,可以说是最简单的一种分治法了!但要结合归并的方式,却不见的能写得漂亮而不失风格!

不解释思路了,直接贴代码了[当然,这个算法不是最好的,分段归并n^1/2+就地重排,应该是更好的!但本菜认为,如果不是大数据量,有点杀鸡用牛刀!]

当然这是段常识性代码,还是能很快且正确的写出才算是基本功到家了!我刚才有个错误的思路,在就地重排的过程中,我想找到第一个orig[i]>=orig[j]的地方,然后把所有的右侧数据用swap_segment转移到左边,有什么问题orig[i]>orig[j],并不代表大于所有的右侧数据,好料!再简单的题也有它的价值,行加油了!

#include <iostream>
#include <fstream>

using namespace std;
const int MAX=30;
int orig[MAX], backup[MAX];
int n;

//declaration
int revert(int l, int r);
//implementation
int revert(int l, int r){
    if(l>=r) return 0;
    if(l+1==r){
        if(orig[l]>orig[r]){
            orig[l]^=orig[r],orig[r]^=orig[l],orig[l]^=orig[r];
            return 1;
        }
    }
    int c=0,mid=l+((r-l)>>1);
    c+=revert(l, mid)+revert(mid+1, r);
    //merge logic,这种代码才是我应该追求的
    for(int i=l,j=mid+1,k=l;i<=mid||j<=r;k++){
        if(i<=mid&&(j>r||orig[i]<=orig[j])){//merge sorting
            backup[k]=orig[i++]; c+=j-mid-1;//previous revert counting number for orig[i]
        }
        else{
            assert(i>mid||(j<=r&&orig[i]>orig[j]));
            backup[k]=orig[j++];
        }
    }
    memcpy((void*)(orig+l), (void*)(backup+l), sizeof(int)*(r-l+1));
    return c;
}

#define fbase
int main()
{
    #ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif

    //implementation
    cin>>n;
    for(int i=0;i<n;i++) cin>>orig[i];
    cout<<local(0, n-1)<<endl;

    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase

  • 今天的目标是把图论的4道基本题目[图的H路,E路问题]做完,然后解决3道动规的编码问题[至少2道,双向规划和多维动规],加油了!注意编码风格和思维严谨!
  • 提醒自己周末用socket和IO完成端口做一个小的网络测试咚咚,研究下IO完成端口到底性能有多好!
  • 可以用WPF框架重新写个俄罗斯方块的游戏,但注意运用和设计博弈论中的启发性算法!如果还是写那种没有价值的咚咚,那就不用动手浪费时间了!

找题地址

Leave a comment

转的一个地址,爆强!以后基本不用再用GG满世界找了!

(1)信息学初学者之家:http://oibh.ioiforum.org/
(2)大榕树编程世界:http://www.fjsdfz.org/~drs/program/default.asp
(3)中国教育曙光网:http://www.chinaschool.org/aosai/
(4)福建信息学奥林匹克:http://www.cfcs.com.cn/fjas/index.htm
(5)第20届全国青少年信息学奥林匹克竞赛:http://www.noi2003.org/
(6)第15届国际青少年信息学奥林匹克竞赛:http://www.ioi2003.org/
(7)全美计算机奥林匹克竞赛:http://ace.delos.com/usacogate
(8)美国信息学奥林匹克竞赛官方网站:http://www.usaco.org/
(9)俄罗斯 Ural 州立大学:http://acm.timus.ru/
(10)西班牙 Valladolid 大学:http://acm.uva.es/problemset
(11)ACM-ICPC:http://icpc.baylor.edu/icpc/
(12)北京大学:http://acm.pku.edu.cn/JudgeOnline/index.acm
(13)浙江大学:http://acm.zju.edu.cn/
(14)IOI:http://olympiads.win.tue.nl/ioi/
(15)2003年江苏省信息学奥林匹克竞赛夏令营[url=http://jsoi.czyz.com.cnhttp://oibh.ioiforum.org/download/uva.htm]http://jsoi.czyz.com.cnhttp://oibh.ioiforum.org/download/uva.htm[/url] 这是关于vallod上一些题的题解和测试数据。 http://www.dcc.ufmg.br/~reuber/solutions/index.html 这里只有一部分的题解。(vallod) http://www.csie.nctu.edu.tw/~huangyl/index1.htm 同上。 http://www.comp.nus.edu.sg/~stevenha/programming/acmoj.html 同上。 http://oibh.ioiforum.org/index.htm 这是一个关与NOI的网站。
还有就是两个测试中心: acm.uva.es(vallod) acm.timus.ru(俄国的)
http://acm.shu.edu.cn 关于编程竞赛的网址
http://202.109.195.141/chenyan/noi/noi.htm 信息资源,很全面的资源网站 http://algorithm.lzu.edu.cn/CLR/CLR.htm 《算法导论》OCR计划
http://202.113.96.10/ini/ 信息学奥林匹克,天津主办
http://www.ioiforum.org/cn/ 关于信息学奥林匹克的BBS
http://geworm.top263.net/olympic.htm 信息学园地,都是关于题目的解
http://www.ssxdzx.net/cdnoi/ 成都市中小学信息学奥林匹克网站,有很多连接 http://www.chinaschool.org/aosai/index.asp 中国教育曙光网 http://oibh.ioiforum.org/ 信息学初学者之家 http://www22.brinkster.com/zxj99/ 信息学奥林匹克竞赛园地,好像是一个老师的个人主页 http://www.noi2002.org/ NOI2002的网页 http://210.14.241.135/~dezx/oldindex/computer/fqlsst.htm NOI试题下载 http://61.187.64.123/~tuanwei/Information/index.asp 信息奥赛沙龙 http://www.ioi2000.org.cn/ioicomonline/online.htm IOI2000的试题下载 http://sfbc.xiaoxiaotong.org/country/Olympic/index_info_review.asp 国际奥赛 http://www.cq8z.com.cn/Informatic/noi/jsjj.htm 重庆八中信息学之窗
http://boc.94bb.com/ispace/ 一个个人网页
http://218.4.51.98/teacher/ljz/aosaizhilu.htm NOI试题下载
http://noi.myrice.com/test001.htm IOI试题下载,很全面 http://stqz.stedu.net/jyky/xueke/DJZ/Olympic/Olympicindex.htm 广东省的 http://www.zsqz.com/xxjy/aolpk/sc1.htm 中国信息学奥林匹克网络服务,非常好的网站!! http://noi.stinfo.net/tk/tk.htm 广东省的题库 http://www.louhau.edu.mo/www/teach/ioi/noi/noi95/indexc.htm NOI95 http://www.zsqz.com/xxjy/aolpk/indexc.htm 中国信息学奥林匹克,权威! http://www.lzgz.net.cn/jiaoshi/jishuanji/dingqiang/ 信息学初学者园地 http://ez.sm.fj.cninfo.net/bjgrzy/9808/olympic.htm 奥赛资源
http://noi.stedu.net/index0.asp 汕头信息学竞赛
http://www.karrels.org/Ed/ACM/ ACM的例程和测试数据
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
黄岩中学解题报告:http://www.zjhyzx.net/Soft/ShowClass.asp?ClassID=58
福建信息学奥林匹克:http://www.cfcs.com.cn/fjas/
EXACT STRING MATCHING ALGORITHMS:http://www-igm.univ-mlv.fr/~lecroq/string/
Game Theory Text :http://www.math.ucla.edu/~tom/Game_Theory/Contents.html
icpc meets fau:http://www2.informatik.uni-erlangen.de/ICPC/rankings/sorted.xml?language=de
IOI‘2003 中国国家集训队训练:http://oibh.kuye.cn/ioi2003/
信息学初学者之家:http://oibh.kuye.cn/
大榕树(荐!):http://www.mydrs.org/program/
Jnu ACMer BBS 解题报告:http://202.116.24.88/acm/acmbbs/list.asp?boardid=18
USACO译题http://wzioi.wzms.com/usaco/
ShanTou University :: Online Contest Judgehttp://acm.stu.edu.cn/index.html
OI爱好者:http://www.oifans.cn/bbs/index.php
极光炫影http://kennyblog.yculblog.com/
杭电题站 huicpc11http://acm.hziee.edu.cn/listproblem.php?vol=1
online judge
Tongji Online Judge Solutions http://purety.jp/akisame/oi/TJU/
浙江大学ACM在线答题
湖南大学ACM站
北京大学ACM在线答题
吉林大学的 Online Judge – http://acm.jlu.edu.cn
四川大学的 Online Judge – http://cs.scu.edu.cn/acm //自从袁牛,姜牛,彭牛走了后,似乎就档了样!!!
汕头大学的 Online Judge – http://acm.stu.edu.cn/
中科大的 Online Judge –    http://acm.ustc.edu.cn/index.php

哈工大的 Online Judge –    http://acm.hit.edu.cn/acm.php
西班牙的 Universidad de Valladolid -http://acm.uva.es/
俄罗斯乌拉尔大学 –   http://acm.timus.ru/

以下转自Myheimu‘s Blog
==========================================================

OI论坛
    http://jsoi.czyz.com.cn/ JSOI
    http://www.kogle.net/noi Kogle.Net 信息学奥林匹克论坛
    http://bbs.mydrs.org/index.asp 大榕树学生论坛
    http://www.hysbz.com/zybbs/index.asp 衡阳市八中信息学奥赛论坛&zju译题站
    http://www.qthome.org/ 趣题之家
    http://woi.wzms.com/ 温州中学信息学奥赛基地
    http://purec.binghua.com/ 哈工大·纯C论坛
    http://www.fzoi.com/ FZOI信息学论坛
    http://www.dyac6.com/fairfox/dvbbs/index.asp fairfox问题征解论坛

杂项

http://www.fengsha.com/index.asp 水木风沙网论坛
http://www.hfyz.net/teacherhomepage/xinxi/xinxihome1.htm 合肥一中信息技术园
http://www.ntzx.net.cn/dj/NOIWEB/NOI.HTM   南通中学信息学奥林匹克
http://218.4.152.202/xwuyan/ 信息技术在线 — 首页
http://www.chinaschool.org/aosai/index.asp 中国教育曙光网–奥赛
http://algorithm.myrice.com/ 算法与数据结构
http://www.jzsx.com/noi/11-3.asp 中山纪念中学信息学竞赛教程
http://www.kogle.net/ Kogle.Net 信息学奥林匹克总站
http://noi.stinfo.net/index0.asp 汕头信息学竞赛
http://www.bashu.com.cn/olympic/info.htm   巴蜀中学信息教育网
http://202.109.195.141/chenyan/noi/noi.htm 信息学资源
http://cs.sicnu.edu.cn/datastructure/ 数据结构—学习网站
http://oibh.ioiforum.org/ oibh.ioiforum.org
http://www.stm.gov.cn/activity/computer/ 晋江市青少年计算机奥林匹克竞赛
http://www.ggzx.net/oi/ www.ggzx.net、oi信息学奥赛网
http://www.nist.gov/dads/   Dictionary of Algorithms and Data Structures
http://www.xiaoxiaotong.org/ 全国青少年科技创新活动服务平台xiaoxiaotong
http://portal.acm.org/portal.cfm   The ACM Portal
http://www.student.org.cn/noi/index.htm   信息学奥赛[学生科技网]
http://www.itisonline.org/   信息学奥赛试题集—http–www.oipc.net
http://3.141592653589793238462643383279502884197169399375105820974944592.com/      Pi to 1,000,000 places

高级编程
    
    http://www.vcok.com/ 唯C世界
    http://www.china-askpro.com/   问专家-编程
    http://www.cstudyhome.com/ C 语言之家
    http://www.csdn.net/ CSDN.NET – 中国最大的开发者网络
    http://www.vbaspnew.com/ VB新势力
    http://202.107.76.62/index.asp c语言论坛
    http://www.delphifans.com/ Delphi园地
    http://www.delphidevelopers.com/ Delphi开发者
    http://delphi.ktop.com.tw/enews.asp   Delphi K.Top討論區
    http://wlbookwl.myrice.com/index1.htm 编程先锋 VB-VB.NET,VC,C++,Delphi, 电子书籍
    http://www.programfan.com/ 编程爱好者网站
    http://bc-cn.net/ 编程中国-中国最大的编程网站
    http://dos.e-stone.cn/ 中国DOS联盟
    http://tew.nease.net/ 漠寒楼-原创免费绿色软件+编程探讨
    http://www.ruanshuo.net/ 软硕网=中国软件工程硕士
官方性
    http://www.ccf.org.cn/index.jsp 中国计算机学会
    http://www.noi.cn/index.jsp 信息学奥林匹克www.noi.cn
    http://ite.nje.cn/school/index.asp 南京信息教研网
    http://www.xiaoxiaotong.org/ 全国青少年科技创新活动服务平台
    http://61.187.64.232/index.htm NOI2004官方网站
    http://www.noi2005.org/ NOI2005
网络题库
    http://acm.tongji.edu.cn/people/ps/problem.php   TjU Problems.Programming Steps
    http://acm.pku.edu.cn/JudgeOnline/   Pku Online Judge
    http://stu.yizhong.xm.fj.cn/dv777/list.asp?boardid=49 URAL题目翻译-厦门一中学生论坛
    http://icpc.baylor.edu/icpc/ ACM-ICPC International Collegiate Programming Contest
    http://acm.timus.ru/   URAL Online Judge
    http://ace.delos.com/usacogate2 USACO Training Program Gateway
    http://www.ssxdzx.net/noi/usaco/ USACO Translate译题
    http://woi.wzms.com/usaco/default.asp#1 USACO译题woi.wzms.com
    http://acm.sgu.ru/ SGU   Saratov State University
    http://online-judge.uva.es/problemset/ UVA PROBLEM SET ARCHIVE
    http://www.hysbz.com/zybbs/list.asp?boardid=34 USACO讨论-衡阳市第八中学信息学奥赛论坛&zju译题站
    http://acm.zju.edu.cn/ ZJU Online Judge
    http://www.hysbz.com/zybbs/list.asp?boardid=44   UVA讨论区–衡阳市第八中学信息学奥赛论坛
    http://www.hysbz.com/zybbs/list.asp?boardid=7   ZJU译题-衡阳市第八中学信息学奥赛论坛
    http://acm.hit.edu.cn/acm.php 哈工大的Online Judge

http://tech.china.com/zh_cn/netschool/softwares/system/index.html

Oxygen(5093670)   (2007-04-18 16:45:42)
http://acm.pku.edu.cn/course/
相关课程链接

Oxygen(5093670)   (2007-04-18 16:43:49)
http://162.105.81.202/course/problemSolving/
北大的ACM课程资料。。。
里面有北大的一些题的解题报告。。。

图论基本理论以及数论素数测试理论

Leave a comment

  • 数论的素数测试理论:这个暂不总结,等把代码写了再总结。
  • PS:研究下gprof的行计数:

1。http://sourceware.org/binutils/docs-2.16/gprof/Annotated-Source.html#Annotated-Source,但加有条件编译的行居然返回乱码!

2。gprof实现,秒了一眼,貌似[本菜的第一感觉而已,少拍少拍mount()]比较简单,

  • 图论的基本知识部分[看得晕头转向,我更喜欢搜索的风格]

1。图连通性:

  • 点连通性->点割集,割点,G的k(G)为点数最少割集的点数[G的点连通度]
  • 边连通性->边割集,桥,G的k'(G)为边数最少的边割集的边数[G的边连通度]
  • 图的连通性->连通分量,强连通图[对于任意两点,双向路径可达]

两个莫名其妙的定理[不晓得怎么证明]

Menger定理:G是k-连通图的充要条件是G中任何两点之间有k条独立路[无公共点的路]

度序列的k连通定理:设图的度序列为d(v1)<=d(v2)…<=d(vn),若存在k(0<=k<=n),使得d(vn)<=j+k-1,则G是k-连通的

2。图着色问题:

  • 点着色问题:[通常我们只研究这个,菜鸟嘛,见BOP上面非常非常简单的描述,转化为图着色问题,OK,很典型的CSP问题,N-Queen的框架]

其模糊的上下界分析:1<=X(G)<=n,X(G)>=[n/q],X(G)<=Max(d)+1…….

  • 边着色问题:对于简单图X‘(G)=Max(d),这类图为K2n,称为第一类图,即二分图;另一类X'(G)=Max(d)+1,这类图为K2n+1,称为第二类图。
  • 色多项式:用k种颜色给图G上色,那么方案数为一个Pk(G)多项式。性质见黑书。这里只说一个P(G)=P(G1)-P(G2),将u,v连通边合并后,直到零图。显然对于零图的色多项式为k^n.好了,这个是我唯一看懂的地方,觉得很精妙,90分的思路,顶点合并。

3。独立集,团,完美图

  • 以前看过,独立集和团互补,我们用单射函数可以从一个G图得到其补图,那么G的独立集就是其生成补图的团。
  • 一M的多结论,不写了,我觉得没多大必要的,用CSP搜索即可,没多大意思[浅见,个人浅见]

4。可行连通性问题

  • 著名的Hamilton路以及回路问题基于顶点的周游,太出名了,出名的地球人都知道[提一下,可以用状态标记的动规来生成其代价最小回路,参见高级动规。PS:不晓得高在什么地方,因为凹凸性以及用栈扫描的部分看得我到现在都二懂二懂,这个还好!公式很平易近人]
  • 出名的Emuler路以及回路问题:基于边的周游
  • TSP问题
  • 中国邮递员问题:若找不到Emuler回路,那么怎样才能在每条边至少走一次后,回到出发点,并且使得回路上权和最小。

图论的开始加动规的Review

Leave a comment

  • 今天开始进入图论和数论部分,以及动规的大量练题阶段.
  • 先把原来做错的题目过了,然后再整理图论的理论部分,
  • 动规今天准备再过至少两道与四边形加速原理相关的题目,最好能把双向规划部分整理下!
  • 好,先把原来做错的水题整理在下面:再次提醒自己不能只求难度,不求基础;再简单的题目也要精心考虑,

假如这是一个大型系统里面的构件,那一点很小的不成熟就会造成大的灾难,最好的办法就是:

1.对称的考虑问题,使用状态位来控制循环,那就要考虑到状态的恢复和设置一定是对称的;

2.用统一变量控制输出,那这个全局变量在设置的时候是否是期望的方式,要基于代码结构思考!

3.对于程序逻辑相关的东西,最好写在纸上,用脑子想的东西,很容易造成纰漏,因为

每个时刻个人可能只想到一个方面,或许点子够好,但谁也不能保证其完整性,可能只是一个测试用例的解决方案。

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

Source Code

Problem: 1226

User: orlando22

Memory: 292K

Time: 0MS

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    #include <string>
    
    
    using namespace std;
    const int MAX=102;
    string str[MAX];
    char t[MAX];
    
    int main()
    {
        //implementation
        int n,m,len,i,j,k;bool all;
        cin>>n;
        while(n--){
            cin>>m;
            len=MAX+2;//minmal of string
            string strMin;
            for(i=0; i<m; i++){
                cin>>t,str[i]=t;
                if(str[i].size()<len) strMin=str[i],len=str[i].size();
            }
            //compare each string with strMin
            int iMinslen=len;len=0;//全局变量的处理,细节才是真正的功力体现
            for(k=iMinslen;k>0;k--){
                all=false;//all supposed=true,我在设置这个状态控制的时候,
               //原来是在这个循环之外,想想为什么可能是错的!
            for(j=0;j<=iMinslen-k;j++){//k is len of template string
                string b=strMin.substr(j,k);//how to implement?
                strncpy(t, b.c_str(), k),t[k]='';//赫赫,这里最好用
              //逗号表达式,表示在非多线程操作下的“原子”操作~_~
                for(char *s=t,*e=t+k-1;s<=e;s++,e--){
                    char tmp=*s;*s=*e;*e=tmp;
                }
                string rb=t;
                all=true;
                for(i=0;i<m;i++){
                    if(str[i].find(b)==string::npos
			&&str[i].find(rb)==string::npos){
                        all=false;break;
			//for both which can't find substring
                    }
                }
                if(all){len=k; break;}
            }
            if(all) break;
        }
        cout<<len<<endl;
    }

    return 0;
}
  • 参数搜索的一道题目:著名的Copying Books,<实用算法>上叫做石子分配
P173页,这道问题很多人都写了解题报告.
本菜看来,如果想做这道题目,大家最好去看看书上的表述!
算法的核心在于精妙的解决问题,复杂的不可简单,同时简单也不可复杂!
我怎么看这道题目,我可以用参数搜索的方法找到上限参数P,然后在用其来进行分配!
注意:分配参数不一定可以将书可以绝对的分配到k这个数目,
容易想到,但写代码冲动的人容易忽视
[比如原来的我,其实现在代码也容易冲动,不过我会努力写出有风格的代码].
两个关键点:1.参数搜索;2.参数确定后的处理,以及再插入!
很多人在问为什么代码是错的,可以用下面的测试用例试下,pku的讨论中有!
3
5 3
1 1 1 1 10
8 3
1 1 1 1 1 1 1 10
9 3
12 12 12 12 12 12 12 12 1000
实现: http://acm.pku.edu.cn/JudgeOnline/problem?id=1505 Copying Books
Source Code
Problem: 1505User: orlando22
Memory: 284KTime: 79MS
Language: C++Result: Accepted
  • Source Code
    #include <iostream>
    
    //PKU:1505
    typedef long long int64;
    
    using namespace std;
    const int MAX=500;
    int n,k,tot;//index of array
    char s[MAX];
    int64 book[MAX];
    
    //pku1505: each parameter is less than 10000000
    //declaration
    bool check(int64 param);
    
    //implementation
    bool check(int64 param){
        int64 tmp=0;
        int tot=1;
        for(int i=n-1; i>-1; i--){
            if(book[i]>param) return false;
            if(tmp+book[i]<=param)
                tmp+=book[i];
            else//tmp+book[i]>param
                tmp=book[i],tot++;
        }
        if(tot<=k)return true;
        return false;
    }
    
    int main()
    {
        //implementation, upper boundary
        int m,upper,low,mid;
        cin>>m;
        while(m--){
            cin>>n,cin>>k;
            low=LONG_MIN,upper=0;
            for(int i=0; i<n; i++){
                cin>>book[i];
                if(book[i]>low) low=book[i];
                upper+=book[i];
            }
            low-=1;
            while(upper-low>1){
                mid=low+((upper-low)>>1);
                if(check(mid)) upper=mid;
                else low=mid;
            }
            //backtrack for minmal of max amount
            int64 tmp=0;int tot=1;
            memset((void*)s, 0, MAX);
            for(int i=n-1; i>-1; i--){
                if(tmp+book[i]<=upper) tmp+=book[i];
                else{
                    s[i]=1;//for current ending
                    tmp=book[i],tot++;
                }
            }
            if(tot!=k){//insert from the frontier, for different groups
                int left=k-tot;
                for(int i=0; i<n&&left; i++){
                    if(s[i]==0&&i!=k-1) s[i]=1,left--;
                }
            }
            for(int i=0; i<n; i++){
                cout<<book[i];
                if(s[i]==1)cout<<" /";
                if(i!=n) cout<<" ";
            }
            cout<<endl;
        }
        return 0;
    }
  • 动规的证明和代码,我贴在下面了,注意证明的思路一定要完备[对自己说的]
Supposed that M[i][k] is the minmal of maximum pages for P[0...i] of previous k scribers.
 
// k-1=<j<i,at least one book for kth scriber, then left [0...k-2] books.
描述:M[i][k]是对于k个抄书员,0...i本书,所存在的最优的最大分配数.
对于P[0...j]书,分配个k-1个抄书员,所存在的最小的最大分配数M[j][k-1],则证明如下
设K2=M[j,k-1],K1为其他非M[j,k-1]情况的最大分配,则K2<=K1.
对于第k个人的分配而言,[K1,w(j+1,i)] vs [K2,w(j,i)]
1.若w(j,i)<=K2,则M[j,k]=M[j+1,k-1](K1,K2仍然最大)
2.若w(j,i)>K2,则Max{[K2,w(j+1,i)]}=w(j+1,i);
若w(j,i)<=K1,则Max{[K1,w(j+1,i)]}=K1,而由K1>=w(j+1,i),知道M[i,k]=w(j+1,i);
若w(j,i)>K1,则Max{[K1,w(j+1,i)]}=w(j+1,i),知道M[i,k]=w(j+1,i).
这里的动规要非常小心!这里求出的只是一个关于[i,k]的最大量而已.
对于某一个针对[i,k]的最大量=Max{M[j][k-1],w(j+1,i)}.
则最大量的最小值为:M[i,k]=Min{Max{M[j][k-1],w(j+1,i)}}.
Orlando's Notes:可以直接画出线段图比较.
 

可是有个难点,题目需要将所有的[i,k]相关决策点记录下来,注意是与[i,k]相关的决策点!
这从决策空间来看,一条与[i,k]决策相关的最优解路径是无法在递归之前预判的,
因此只有用空间换时间d[i,k]来记录相关的决策点.
[这个题目明显是稀疏状态(k-2<=j<i)的,因此用自底而上的策略比较浪费运行时间].
实现代码:[运行时间,327ms,运行时间太高,可以消去递归,但估计重复的无效循环会导致无效决策产生!]
//buffer for p[0...m]
const int MAXEL=30;
int p[MAXEL];
//solution1 : DP table
int M[MAXEL][MAXEL], w[MAXEL][MAXEL], d[MAXEL][MAXEL];
int sc[MAXEL];
void DP(int m, int k);
int MemDP(int i, int k);
//M[i][k]=Min{Max{M[j][k-1],w[j+1][i]}}, k-2<=j<i;
int MemDP(int i, int k){
    if(M[i][k]!=-1) return M[i][k];
    //k>=1
    if(k==1){//k==0 is meanless
        M[i][1]=w[0][i];
        return w[0][i];
    }
    M[i][k]=INT_MAX;
    int j,tmp;
    for(j=i-1; j>=k-2; j--){
        tmp=MemDP(j, k-1);//each strategy for w(j+1,i)
        if(w[j+1][i]>tmp){
            tmp=w[j+1][i];
        }
        if(tmp<M[i][k]){//M[j][k-1],w[j][i]
            M[i][k]=tmp;d[i][k]=j;
        }
    }
    return M[i][k];
}
void DP(int m, int k){
    //calculate w[0...m-1][0...m-1]
    int i,j;
    for(i=0; i<m; i++){//w[i][0...m-1]
        w[i][i]=p[i];
        for(j=i+1; j<m; j++)
            w[i][j]=w[i][j-1]+p[j];//w[i][i]=0;
    }
    MemDP(m-1, k);
    memset(sc, 0, sizeof(int)*MAXEL);
    for(i=k,j=d[m-1][k];i;sc[j]=1,i--,j=d[j][i]);
    for(i=0; i<m; i++){
        cout<<p[i]<<" ";
        if(sc[i]) cout<<"/ ";
    }
    cout<<endl;
}

这道题目的意义不在于它多难,而在于有两个很重要的关键点:1.在处理动态规划边界的时候,s[i][j]如何处理?本菜就是在这里犯了一个错!
2.还有一点,当你用s[i][j+1],s[i][j-1](为什么不是s[i-1][j]?想想凸性怎么分析的)来处理边界的时候,那么
s[i][j+1],s[i][j-1]已经先求出来了,OK!如何规划求值过程!因此在写这类带四边形的问题时,注意以上两点,应该是很快搞定的![15分钟
:其中5-6分钟分析动规方程,我会花3-4分钟理清边界情况,哪些能用那些不能用;然后是1分钟的思考时间,如何规划求值顺序,从优化的角度
上讲,用自底向上,还是记忆化搜索;最后一半的时间中分3-4分钟编码,最后1-2分钟我观察常量定义和方程的边界处理,1-2分钟梳理代码,变量优化]
3.单独说一点,本菜要认真反思的是,为什么我在两道以上的题目里,出现了常量定义的错误,一道是将d[x][y]变量顺序写反,一道是
写常量的时候张冠李戴,一次是偶然,两次就是必然,请认真反省自己!
代码如下:

Source Code

Problem: 1160User: orlando22
Memory: 1100KTime: 110MS
Language: C++Result: Accepted
  • Source Code
    #include <iostream>
    
    using namespace std;
    typedef unsigned long long int64;
    //pku 1160
    //the number of villages V, 1 <= V <= 300, int
    //the number of post offices P, 1 <= P <= 30, int
    //each position X it holds that 1 <= X <= 10000, long
    const int MAXV=300, MAXP=30;
    long v[MAXV+1];
    int64 d[MAXP+1][MAXV+1],w[MAXV+1][MAXV+1];
    int s[MAXP+1][MAXV+1];
    //1,2...nv, start with village 1...then end with nv...
    //DP equation: d[i,j]=Min{d[i-1,k]+w(k+1,j)}.(i-1<=k<=j-1, 1<=i<=p)
    //boundary checking: m[1,j]=w[1,j],s[1,j]=mid; m[j,j]=0, s[j,j]=j-1.(1<=j<=n)
    //sum[i][j],sum of distance of all [i,j-1]->j(i<j), all [i+1,j]->i(i>j).
    //sum[i][j+1]=sum[i][j]+dis(j,j+1)*abs(i-j+1);(i<j+1)
    //sum[i][j+1]=sum[i][j]+dis(j+1,i);(i>j+1)
    //sum[i][j+1]=0;(i==j+1)
    
    int main()
    {
        //implementation
        int nv, np, ans;
        cin>>nv, cin>>np;//, cin>>ans;
        v[0]=0;
        for(int i=1; i<nv+1; i++) cin>>v[i];
        //clr
        memset((void*)&w[0][0], 0xff, sizeof(int64)*(MAXV+1)*(MAXV+1));
        memset((void*)&s[0][0], 0xff, sizeof(int)*(MAXP+1)*(MAXV+1));
        memset((void*)&d[0][0], 0xff, sizeof(int64)*(MAXP+1)*(MAXV+1));
        //pre-calculation for all w[i][j]
        for(int i=1; i<nv+1; i++) w[i][i]=0;
        for(int i=1; i<nv+1; i++){
            for(int j=i+1; j<nv+1; j++){//[i,j]
                int mid=i+((j-i)>>1);
                int64 sum=0;
                for(int k=i; k<j+1; k++) sum+=abs(v[k]-v[mid]);
                if((j-i)&0x1){//even number
                    int64 tmp=sum+((mid-i+1)-(j-mid))*(v[mid+1]-v[mid]);
                    if(tmp<sum) mid+=1,sum=tmp;
                }
                w[i][j]=sum;
                if(i==1) d[1][j]=sum, s[1][j]=mid-2;//boundary checking
            }
        }
        for(int i=1; i<np+1; i++)
            d[i][i]=0,s[i][i]=i-1;//i>=1,i<=np
        for(int i=2; i<np+1; i++){//i==1 done
            for(int j=nv; j>i; j--){//i=j?
                //d[i,j]=Min{d[i-1,k]+w[k+1,j]} k>=i-1,k<=j-1
                int l=i-1;
                if(s[i-1][j]!=-1&&l<s[i-1][j]) l=s[i-1][j];
                int r=j-1;
                if(s[i][j+1]!=-1&&r>s[i][j+1]) r=s[i][j+1];
                d[i][j]=d[i-1][l]+w[l+1][j],s[i][j]=l;
                for(int k=l+1; k<r+1; k++){
                    int tmp=d[i-1][k]+w[k+1][j];
                    if(tmp<d[i][j]) d[i][j]=tmp,s[i][j]=k;
                }
            }
        }
        cout<<d[np][nv]<<endl;
        return 0;
    }
    

以N皇后问题作为搜索的结语[加回顾]

Leave a comment

  • N皇后问题是很经典的一个问题[CSP中大家已经失去兴趣的一个问题],本菜感概下,所以把相关自己写过的程序都总结下,加深下理解这类问题的解法.

1.朴素的回溯法:朴素的定义是单纯的BT+单层FC解法;这里引用了<算法艺术>的实现,我用used1,used2,used3分别作为行,主对角线,副对角线的可行值!->映射为0->2*(n-1),主对角线为n-1+(y-x),而副对角线为y+x.思路很简单,代码如下:

int used1[MAX], used2[MAX], used3[MAX];
//MACRO,又来宏,引用jon的实现
#define setT(bit, i) (bit[(i)>>5]|=(1<<((i)&0x1f)))
#define resetT(bit, i) (bit[(i)>>5]&=~(1<<((i)&0x1f)))
#define testT(bit, i) (bit[(i)>>5]&(1<<((i)&0x1f)))

void itersearch(int n){//Note:纯的迭代框架
    for(int i=0; i>-1;){
        for(;queen[i]<n;queen[i]++){//y-x+n, and y+x
            //test(used1, queen[i])
            if(!testT(used1, queen[i])&&!testT(used2, queen[i]-i+(n-1))&&!testT(used3, queen[i]+i)){
                //set
                setT(used1, queen[i]),setT(used2, queen[i]-i+(n-1)),setT(used3, queen[i]+i);
                if(i==n-1){
                    total++;
                    //reset,我这里开始写的时候忘记了,FT,卡了1分钟,忽然醒悟
                    resetT(used1, queen[i]),resetT(used2, queen[i]-i+(n-1)),resetT(used3, queen[i]+i);
                }
                else{
                    i++;
                    queen[i]=-1;
                }
            }
        }
        //queen[i]==n
        i–;
        //reset
        resetT(used1, queen[i]),resetT(used2, queen[i]-i+(n-1)),resetT(used3, queen[i]+i);

        queen[i]++;
    }
}

void search (int dep, const int n){
    int i;
    if(dep==n) tot++;
    else{
        for(i=0; i<n; i++){
            if(!testT(used1, i)&&!testT(used2, i-dep+(n-1))&&!testT(used3, dep+i)){
                setT(used1, i),setT(used2, i-dep+(n-1)),setT(used3, dep+i);
                search(dep+1, n);
                resetT(used1, i),resetT(used2, i-dep+(n-1)),resetT(used3, dep+i);
            }
        }
    }//else
}

2.关于朴素算法的思考,你看我那么辛苦的用三个数组来禁位,确实很麻烦.好参考Matrix67的代码,改成c++如下,其实思路是一样的,代码我加了注释[我觉得这个代码可以称的上编程之美,造化巧妙].不敢隐大牛的地址如下:http://www.matrix67.com/blog/archives/266/comment-page-1,至于上面引用的dd大牛的Gray码解女友群问题,哈哈,没那个本事,人专注和专一点好!不过感兴趣的话,你可以写个程序来管理下,反正不难10行搞定!

void BQueen(int row, int ld, int rd, const int n, const int upper, int& sum){
    if(row==upper) sum++;
    else{
         int pos=(upper&(~(row|ld|rd)));//clr bits,所有的占用位求反,可得当前可用的位
         while(pos>0){//left bits yeah!
            int p=(pos&(-pos));//-a=~(a+1), the most right side bit,最右边的1,没啥说的,实在不懂看BOP
            pos=pos-p;
            BQueen(row+p,(ld+p)<<1,(rd+p)>>1, n, upper, sum);//<<1,>>1这个很有趣,把对角线映射到下一行上,一个左移,一个右移[左边第一位的对角线限制为0,因此若第一位置位那么实际上是无影响的,OK,没其他说的了!右边同理]
        }
    }
}

3.但朴素的算法能否修正呢,先用MRV来做一个,用下一位值域的非递减序列!这里随便写个,示意而已[如果在BQueen上修改的话,可以加上1位统计代码如下]。计算有多少个1,二分法计算每个unsigned int数

int forIntOne(unsigned int s){//当然可以优化,但这种代码最能表现原始企图,因此不改了,代码还是看得懂得好
        int v=(s&0x55555555)+((s>>1)&0x55555555);
        v=(s&0x33333333)+((s>>2)&0x33333333);
        v=(s&0x0f0f0f0f)+((s>>4)&0x0f0f0f0f);
        v=(s&0x00ff00ff)+((s>>8)&0x00ff00ff);
        v=(s&0x0000ffff)+((s>16)&0x0000ffff);
        return v;
    }

//MRV实现如下

void search (int dep, const int n){
    int i;
    if(dep==n) tot++;
    else{
        LNode cand[n];//Herusic Method
        int index=0;
        for(int i=0; i<n; i++){
            if(!used[i][0]&&!used[i-dep+n-1][1]&&!used[i+dep][2]){
                //valid for current selection
                used[i][0]=used[i-dep+n-1][1]=used[i+dep][2]=1;
                //counting next possibility
                int key=0;
                for(int i=0; i<n; i++) key+=(~(used[i][0]&used[i][1]&used[i][2]));//一个禁位计算
                int j=index;
                for(;j-1>=0&&key>cand[j-1].key; j–) cand[j]=cand[j-1];
                cand[j].key=key,cand[j].i=i;
                index++;
                used[i][0]=used[i-dep+n-1][1]=used[i+dep][2]=0;
            }
        }
        for(int i=0; i<index; i++){//don’t need to maintain status
            int curi=cand[i].i;
            if(!used[curi][0]&&!used[curi-dep+n-1][1]&&!used[curi+dep][2]){
                used[curi][0]=used[curi-dep+n-1][1]=used[curi+dep][2]=1;
                search(dep+1, n);
                used[curi][0]=used[curi-dep+n-1][1]=used[curi+dep][2]=0;
            }
        }
    }//else
}

但这种算法在运行时确差强人意,为什么?因为每次迭代都要排序,系统在这上面折腾的时间太多,但假如兴趣的话,在NQueen版本上的修改,通常不会让你失望的,当然N在适当大的时候[我们假设N->4,完全没必要排序,而较大的解,我可以用修正算法来做,所以算法嘛,要因地制宜]

3.当然我们可以用修正构造的方式来解Queen问题,下面的代码是CSDN上的,但他是修正一个解的代码,稍微动下脑筋,其实可以将修正代码和iterative的版本结合在一起对于一个到最后无解的近似解[或者说满足小于修正因子的解],单独运行修正程序,我想估计这就是lrj神牛说的吧!猜测,仅猜测!

//repair naive version
void repairApproach(int n);//size of n
bool repair(int* q, int n, int& maxconf);
int getConfNum(int* q, int n, int i);

//implementation
void repairApproach(int n){
    int* q=new int[n];
    int maxconf=n;//supposed max number
    srand((unsigned)0);
    while(maxconf!=0){//haven’t eliminate the maxconf
        for(int i=0; i<n; i++) q[i]=rand()%n;
        bool required=true;
        while(required=repair(q, n, maxconf));
    }
    delete[] q;
}

bool repair(int* q, int n, int& maxconf){
    maxconf=-1;
    bool required=false;
    for(int i=0; i<n; i++){
        int orgVal=q[i], minVal=q[i], minconf=n;
        for(int j=0; j<n; j++){//trial for each value
            q[i]=j;
            int confnum=getConfNum(q, n, i);
            if(confnum<minconf){
                minconf=confnum, minVal=j;
            }
        }
        q[i]=minVal;
        if(orgVal!=minVal) required=true;//not equal, change currently
        if(minconf>maxconf) maxconf=minconf;//maxconf is the max of all minmal num
    }
    return required;
}

//get number of columns that conflct with column i
int getConfNum(int *q, int n, int i ){
 int num = 0;
 for(int j=0; j<n; j++){
  if (j==i)continue;
  if (q[j]==q[i]) num++;
  else if (q[j]-q[i]==j-i) num++;
  else if (q[j]-q[i]==i-j) num++;
 }
 return num;
}

4.最后的最后,当然要说最强的方法啦,不过很难证明,参见《challenging.mathematical.problems.with.elementary.solutions》。主要方法如下:

一、当n mod 6 != 2 或 n mod 6 != 3时,有一个解为:

2,4,6,8,…,n,1,3,5,7,…,n-1       (n为偶数)

2,4,6,8,…,n-1,1,3,5,7,…,n       (n为奇数)

(上面序列第i个数为ai,表示在第i行ai列放一个皇后;… 省略的序列中,相邻两数以2递增。下同)

二、当n mod 6 == 2 或 n mod 6 == 3时,

(当n为偶数,k=n/2;当n为奇数,k=(n-1)/2)

k,k+2,k+4,…,n,2,4,…,k-2,k+3,k+5,…,n-1,1,3,5,…,k+1         (k为偶数,n为偶数)

k,k+2,k+4,…,n-1,2,4,…,k-2,k+3,k+5,…,n-2,1,3,5,…,k+1,n       (k为偶数,n为奇数)

k,k+2,k+4,…,n-1,1,3,5,…,k-2,k+3,…,n,2,4,…,k+1               (k为奇数,n为偶数)

k,k+2,k+4,…,n-2,1,3,5,…,k-2,k+3,…,n-1,2,4,…,k+1,n           (k为奇数,n为奇数)

引用袁牛的话“我没得那个智商,研究这个数学”,懒得管了,抄了段代码了事!对于不感兴趣的事,直接闪过!

void math(int n){
    int i;
    if (n%6!=2&&n%6!=3){
   for (i=2;i<=n;i+=2) printf("%d ",i);
   for (i=1;i<n-1;i+=2) printf("%d ",i);
   printf("%d\n",i);
  }
  else if ((n/2)&1){
   for (i=n/2;i<n;i+=2) printf("%d ",i);
   for (i=1;i<(n/2)-1;i+=2) printf("%d ",i);
   for (i=n/2+3;i<=n;i+=2) printf("%d ",i);
   for (i=2;i<n/2;i+=2) printf("%d ",i);
   printf("%d\n",i);
  }
  else{
   for (i=n/2;i<=n;i+=2) printf("%d ",i);
   for (i=2;i<(n/2)-1;i+=2) printf("%d ",i);
   for (i=n/2+3;i<n;i+=2) printf("%d ",i);
   for (i=1;i<n/2;i+=2) printf("%d ",i);
   printf("%d\n",i);
  }
}

可以看出CSP问题的套路还是相当清晰,而且理论思路也很清晰,了解到这个程度,可以了,以后有需要再认真研究吧!

  • 好,搜索的结语:开始我不明白lrj为什么说搜索是最难的,现在我明白了,搜索难是难在它的外延直接与人工智能接壤,而且对于确定的算法模型而言,非确定的人为因素很多,一个好的启发函数和好的框架,可以比一个一般或者坏的框架性能和思路都优越很多很多[典型的坏框架就是本菜的代码,俄!写的巨庞大无比,写到后面沾了点牛尾巴气,还算写得能看得过去了!当然思路的学习才是最大的提高]

那我学到了什么呢?

  • 简单的搜索框架:DFS,BFS[应该是熟练程度吧,例题:最优程序],以及双向广度搜索[例题:Color Hash];优点是什么,缺点是什么!
  • 重要的启发搜索问题:A*和IDA*框架[例题:编辑书稿,埃及分数],A*的空间要求太高,因此IDA*用迭代的方式来缓解空间危机。博大精深的启发函数
  • 博弈问题算法:Min-Max,Neg-Max框架,以及Alpah-Beta剪枝的框架问题[可以用动规解的,例题:三角形大战],这两种是基于DFS的搜索算法;而基于BFS的搜索算法呢,SSS*和AB-SSS*算法[AB-SSS*的框架实际上是一种DFS下的迭代框架,和IDA*差不多]
  • 两类问题:路径寻找问题[例题:外公的难题],以及限制满足问题[例题:N皇后问题]
  • 两种思想

1。剪枝思想:最优,极大极小的极端剪枝;基于数学模型的剪枝;基于动态规划的问题转化[状态压缩的模型搞的我之痛苦,不过现在看起来也不过是动规的一种变化而已,难在用数学优化!][例题:1M多,水题居多]

2。参数搜索思想:极大极小的一种变化而已。[例题:抄写书稿,可与动规相互转化]

先结一下,以后再有空再说搜索吧,下一个部分了,同时再回头复习下动规呀,分治这些东西了,练习下自己的白纸编程!

PS:看到dd大牛的一首诗歌,很有感概,大牛果真是大牛,情诗都写得气势不凡,小菜佩服!左手程序右手诗

Older Entries