The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

#

网络流题目集锦(转)

最大流
POJ 1273 Drainage Ditches
POJ 1274 The Perfect Stall (二分图匹配)
POJ 1698 Alice's Chance
POJ 1459 Power Network
POJ 2112 Optimal Milking (二分)
POJ 2455 Secret Milking Machine (二分)
POJ 3189 Steady Cow Assignment (枚举)
POJ 1637 Sightseeing tour (混合图欧拉回路)
POJ 3498 March of the Penguins (枚举汇点)
POJ 1087 A Plug for UNIX
POJ 1149 Pigs (构图题)
ZOJ 2760 How Many Shortest Path (边不相交最短路的条数)
POJ 2391 Ombrophobic Bovines (必须拆点,否则有BUG)
WHU 1124 Football Coach (构图题)
SGU 326 Perspective (构图题,类似于 WHU 1124)
UVa 563 Crimewave
UVa 820 Internet Bandwidth
POJ 3281 Dining (构图题)
POJ 3436 ACM Computer Factory
POJ 2289 Jamie's Contact Groups (二分)
SGU 438 The Glorious Karlutka River =) (按时间拆点)
SGU 242 Student's Morning (输出一组解)
SGU 185 Two shortest (Dijkstra 预处理,两次增广,必须用邻接阵实现,否则 MLE)
HOJ 2816 Power Line
POJ 2699 The Maximum Number of Strong Kings (枚举+构图)
ZOJ 2332 Gems
JOJ 2453 Candy (构图题)
SOJ3312 Stockholm Knights
SOJ3353 Total Flow
SOJ2414 Leapin' Lizards ­
最小割
SOJ3106 Dual Core CPU
SOJ3109 Space flight
SOJ3107 Select
SOJ3185 Black and white
SOJ3254 Rain and Fgj
SOJ3134 windy和水星 -- 水星交通
HOJ 2634 How to earn more
ZOJ 2071 Technology Trader (找割边)
HNU 10940 Coconuts
ZOJ 2532 Internship (找关键割边)
POJ 1815 Friendship (字典序最小的点割集)
POJ 3204 Ikki's Story I - Road Reconstruction (找关键割边)
POJ 3308 Paratroopers
POJ 3084 Panic Room
POJ 3469 Dual Core CPU
ZOJ 2587 Unique Attack (最小割的唯一性判定)
POJ 2125 Destroying The Graph (找割边)
ZOJ 2539 Energy Minimization
TJU 2944 Mussy Paper (最大权闭合子图)
POJ 1966 Cable TV Network (无向图点连通度)
HDU 1565 方格取数(1) (最大点权独立集)
HDU 1569 方格取数(2) (最大点权独立集)
POJ 2987 Firing (最大权闭合子图)
SPOJ 839 Optimal Marks (将异或操作转化为对每一位求最小割)
HOJ 2811 Earthquake Damage (最小点割集)
2008 Beijing Regional Contest Problem A Destroying the bus stations ( BFS 预处理 )(网络流题目集锦(转)http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4322)
ZOJ 2676 Network Wars (参数搜索)
POJ 3155 Hard Life (参数搜索)
ZOJ 3241 Being a Hero

有上下界
ZOJ 2314 Reactor Cooling (无源汇可行流)
POJ 2396 Budget (有源汇可行流)
SGU 176 Flow Construction (有源汇最小流)
ZOJ 3229 Shoot the Bullet (有源汇最大流)
HDU 3157 Crazy Circuits (有源汇最小流)

最小费用流
HOJ 2715 Matrix3
HOJ 2739 The Chinese Postman Problem
POJ 2175 Evacuation Plan (消一次负圈)
POJ 3422 Kaka's Matrix Travels (与 Matrix3 类似)
POJ 2516 Minimum Cost (按物品种类多次建图)
POJ 2195 Going Home
BUAA 1032 Destroying a Painting
POJ 2400 Supervisor, Supervisee (输出所有最小权匹配)
POJ 3680 Intervals
HOJ 2543 Stone IV
POJ 2135 Farm Tour
BASHU2445 餐巾问题
---------------------------------------------onmylove原创

最大流题目:

TC

Single Round Match 200 Round 1 – Division I, Level Three

Single Round Match 236 Round 1 – Division I, Level Three

 

Single Round Match 399 Round 1 – Division I, Level Three

Hoj1024: http://acm.hust.edu.cn/thx/problem.php?id=1024

 

 

2003 TCO Semifinal Round 4 – Division I, Level Three

2004 TCCC Championship Round – Division I, Level Three

2005 TCO Sponsor Track Round 3 – Division I, Level One

 

 

 

 

 

混合图的欧拉回路

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

zju1992http://acm.zju.edu.cn/show_problem.php?pid=1992 
  
  

求增广边:

Poj3204http://acm.pku.edu.cn/JudgeOnline/problem?id=3204

类似:Hoj1082: http://acm.hust.edu.cn/thx/problem.php?cid=1017&pid=6

 

 

 

 

项目选择问题:

Poj3469http://acm.pku.edu.cn/JudgeOnline/problem?id=3469

Zoj2930http://acm.zju.edu.cn/show_problem.php?pid=2930

求项目选择项目最多的方案。

 

 

建图:

Poj1149http://acm.pku.edu.cn/JudgeOnline/problem?id=1149

Poj3436http://acm.pku.edu.cn/JudgeOnline/problem?id=3436

Poj3281http://acm.pku.edu.cn/JudgeOnline/problem?id=3281

 

 

连通度:

点连通度Poj1966: http://acm.pku.edu.cn/JudgeOnline/problem?id=1966

Uva563, http://icpcres.ecs.baylor.edu/onlinejudge/ 
点不交的路径条数问题,需要拆点

 

 

 

最小割:

Poj2914http://acm.pku.edu.cn/JudgeOnline/problem?id=2914

stoer-Wagner

 

 

 

 

基本题:

Poj3498http://acm.pku.edu.cn/JudgeOnline/problem?id=3498

枚举:n次最大流。

 

Poj1087http://acm.pku.edu.cn/JudgeOnline/problem?id=1087

可以用最大流做,也可以用二分图匹配做。

 

 

 

Poj1273http://acm.pku.edu.cn/JudgeOnline/problem?id=1273

 

Poj1274http://acm.pku.edu.cn/JudgeOnline/problem?id=1274

 

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

 

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

  

Poj1797http://acm.pku.edu.cn/JudgeOnline/problem?id=1797

 

Poj1815http://acm.pku.edu.cn/JudgeOnline/problem?id=1815

 

 

poj2112http://acm.pku.edu.cn/JudgeOnline/problem?id=2112

 

poj2239http://acm.pku.edu.cn/JudgeOnline/problem?id=2239

 

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

 

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

 

Poj2987http://acm.pku.edu.cn/JudgeOnline/problem?id=2987

 

Poj3308http://acm.pku.edu.cn/JudgeOnline/problem?id=3308

提示:最大权闭包,转化成最大流

 

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

 

SGU 176 http://acm.sgu.ru/problem.php?contest=0&problem=176 
容量有上下界的网络流问题,有难度
  
Spoj660http://www.spoj.pl/problems/QUEST4/ 
Spoj377http://www.spoj.pl/problems/TAXI/ 
  
UVA  
http://icpcres.ecs.baylor.edu/onlinejudge/ 
753, 
820,  
10122,  
10330,  
10511,  
10735. 

posted @ 2010-11-06 13:18 abilitytao 阅读(792) | 评论 (0)编辑 收藏

SGU 185 Two shortest -一切皆是网络流

题意:求1->n的两条不相交的最短路(两条路径可以共顶点但是不能共边)

心得:看了AC的博客学的,呵呵,这题充分展示了一切皆是网络流的核心思想。
做法:首先找出以1为顶点的最短路径树,1到树中任意一点的连线都是最短路径,首先把这些边加到网络流的边集中,容量为1。
然后再枚举下边,将不在最短路径树上但是在最短路上的边也加到网络流的边集中,容量为1。跑一遍1到n的最大流,如果流量>=2则有解,再从原点深搜路径即可。

确切的来说,只要在后来建的图中随便找一条路径均是原点到该点的最短路(注意边是单向的),又因为限制了流量是1,所以一条边只能选取一次,这样跑出来的流量就一定是不相交最短路的条数。

int mat[maxn][maxn];
int n,m;

int dis[maxn];
int use[maxn];
void SPFA(int n,int s)
{
    fill(dis,dis
+n,INF);
    fill(use,use
+n,0);
    queue
<int>Q;
    dis[s]
=0;
    use[s]
=1;
    Q.push(s);
    
while(!Q.empty())
    
{
        
int x=Q.front();Q.pop();
        use[x]
=0;
        
for(int i=0;i<n;i++)
        
{
            
if(dis[x]+mat[x][i]<dis[i])
            
{

                dis[i]
=dis[x]+mat[x][i];
                
if(!use[i])
                
{
                    use[i]
=1;
                    Q.push(i);
                }

            }

        }

    }

}

int flag=0;
void dfs(int x)
{
    
if(flag==1)return;
    
if(x==n-1)
    
{
        flag
=1;
        printf(
"%d\n",x+1);
        
return;
    }

    
else printf("%d ",x+1);

    
for(node *p=adj[x];p;p=p->next)
    
{
        
if((p-edge)&1)continue;
        
if(p->flow==0{
            p
->flow=-1;
            dfs(p
->v);
            
if(flag==1)
                
return;
        }

    }


}



int main()
{
    scanf(
"%d %d",&n,&m);
    
int a,b,c;
    
for(int i=0;i<n;i++)
    
{
        
for(int j=0;j<n;j++)
        
{
            
if(i==j)mat[i][j]=0;
            
else mat[i][j]=INF;
        }

    }

    
for(int i=0;i<m;i++)
    
{
        scanf(
"%d%d%d",&a,&b,&c);
        a
--;b--;
        
if(c<mat[a][b])
            mat[a][b]
=mat[b][a]=c;
    }

    SPFA(n,
0);
    
for(int i=0;i<n;i++)
        
for(int j=0;j<n;j++)
        
{
            
if(i==j)continue;
            
if(dis[i]+mat[i][j]==dis[j])
                insert(i,j,
1);
        }

        
int ans=sap(n,0,n-1);
        
if(ans<2){
            printf(
"No solution\n");
            
return 0;
        }

        flag
=0;
        dfs(
0);
        flag
=0;
        dfs(
0);
        
return 0;
}
很难得的一次写对了SPFA...

参考了AC大神的代码,递归删除边的时候将流量置为-1,不错的想法。另外我用p-edge的奇偶性判断正反边,但是一直没弄明白p和edge都是地址而且地址相差并不是1的时候减出来却是1。。。

posted @ 2010-11-05 15:38 abilitytao 阅读(1927) | 评论 (0)编辑 收藏

HDOJ 3397 线段树大综合

     摘要: 实在不行,改了方法。SET 0和SET 1用延迟标记,翻转不用任何标记,直接更新到底。800+MS AC. #include<cstdlib>#include<iostream>#include<algorithm>#include<cstdio>using namespace std;int const m...  阅读全文

posted @ 2010-11-03 00:55 abilitytao 阅读(1162) | 评论 (0)编辑 收藏

HDOJ 2871 Memory Control 经典线段树懒操作

     摘要: 这题有点像Hotel的包装版,非常经典,让我进一步熟悉了线段树的区间操作(主要是延迟标记的使用)。唯一的问题出在自己写的二分函数上,死活都是TLE,后来参考了小HH的二分才过掉,不知道自己哪写挂了,郁闷。。。。PS:顺便问一下,高质量的内存管理难道真的是用线段树实现的? #include<iostream>#include<algorithm>#include<ve...  阅读全文

posted @ 2010-10-30 20:00 abilitytao 阅读(1629) | 评论 (0)编辑 收藏

HDOJ 1540 Tunnel Warfare 线段树

题意:可以标记区间上某些节点或者取消标记,并查询与x连续的未被标记的结点数。
这题和Hotel类似,由于换成了单节点操作,不需要区间操作的延迟标记,维护起来更方便。

#include<iostream>
#include
<algorithm>
using namespace std;
int const maxn=50010;
#define LL(i) (i<<1)
#define RR(i) ((i<<1)+1)

struct node
{

    
int l,r;
    
int lval,rval;
    
int len()
    
{
        
return r-l+1;
    }

}
ST[maxn*4];
int n,m;

void build(int l,int r,int i)
{
    ST[i].l
=l;
    ST[i].r
=r;
    
if(l==r)
    
{
        ST[i].lval
=1;
        ST[i].rval
=1;
        
return;
    }

    
int mid=(l+r)>>1;
    build(l,mid,LL(i));
    build(mid
+1,r,RR(i));
    ST[i].lval
=ST[i].len();
    ST[i].rval
=ST[i].len();
}



void update(int x,int op,int i)
{

    
if(ST[i].l==ST[i].r)
    
{
        
if(op==1)
            ST[i].lval
=ST[i].rval=0;
        
else if(op==0)
            ST[i].lval
=ST[i].rval=1;
        
return;
    }

    
int mid=(ST[i].l+ST[i].r)>>1;
    
if(x<=mid) update(x,op,LL(i));
    
else update(x,op,RR(i));

    ST[i].lval
=ST[LL(i)].lval;
    ST[i].rval
=ST[RR(i)].rval;

    
if(ST[LL(i)].lval==ST[LL(i)].len())
        ST[i].lval
+=ST[RR(i)].lval;
    
if(ST[RR(i)].rval==ST[RR(i)].len())
        ST[i].rval
+=ST[LL(i)].rval;
}



int Query(int x,int i)
{
    
if(ST[i].l==ST[i].r)
        
return ST[i].lval;
    
int mid=(ST[i].l+ST[i].r)>>1;
    
if(x<=mid)
    
{
        
if(x<=ST[i].lval)
            
return ST[i].lval;
        
if(x>=ST[LL(i)].r-ST[LL(i)].rval+1)
            
return ST[LL(i)].rval+ST[RR(i)].lval;
        
else return Query(x,LL(i));
    }

    
else
    
{
        
if(x>=ST[i].r-ST[i].rval+1)
            
return ST[i].rval;
        
if(x<=ST[RR(i)].l+ST[RR(i)].lval-1)
            
return ST[RR(i)].lval+ST[LL(i)].rval;
        
else return Query(x,RR(i));
    }

}



int d[maxn];
int pd=0;

int main()
{
    
while(scanf("%d%d",&n,&m)!=EOF)
    
{
        build(
1,n,1);
        
char op[100];
        
int x;
        pd
=0;
        
for(int i=0;i<m;i++)
        
{

            scanf(
"%s",op);
            
if(op[0]=='D')
            
{
                scanf(
"%d",&x);
                update(x,
1,1);
                d[pd
++]=x;
            }

            
else if(op[0]=='Q')
            
{

                scanf(
"%d",&x);
                printf(
"%d\n",Query(x,1));
            }

            
else
            
{
                update(d[
--pd],0,1);
            }

        }

    }

    
    
return 0;
}

posted @ 2010-10-30 10:34 abilitytao 阅读(1195) | 评论 (0)编辑 收藏

HDOJ 2795 Billboard 简单线段树

     很显而易见的线段树,只是有一点需要注意,题目中虽然给了h的范围可以达到10^9,但是由于布告总共只有200000条,最坏情况下只需要200000个线段树的叶子节点,所以可以直接无视h的范围,线段树总结点开200000*4即可。维护的时候,注意利用回溯,自底向上地更新。
    
#include<iostream>
using namespace std;
int const maxn=200010;

int h,w,n;
int num[maxn];
struct node
{
    
int size;
    
int l,r;
}
ST[maxn*6];

void creat(int l,int r,int i)
{
    ST[i].l
=l;
    ST[i].r
=r;
    
if(l==r)
    
{
        ST[i].size
=w;
        
return;
    }

    
int mid=(l+r)>>1;
    creat(l,mid,i
*2);
    creat(mid
+1,r,i*2+1);
    ST[i].size
=w;
}


int ans;
void Query(int i,int x)
{
    
if(ST[i].l==ST[i].r)
    
{
        ans
=ST[i].l;
        ST[i].size
-=x;
        
return ;
    }

    
if(ST[i*2].size>=x)
        Query(i
*2,x);

    
else if(ST[i*2+1].size>=x)
        Query(i
*2+1,x);
    ST[i].size
=max(ST[i*2].size,ST[i*2+1].size);
}


int main()
{

    
while(scanf("%d%d%d",&h,&w,&n)!=EOF)
    
{
        creat(
1,min(h,200000),1);
        
for(int i=0;i<n;i++)
        
{

            
int x;
            scanf(
"%d",&x);
            
if(ST[1].size<x)
                printf(
"-1\n");
            
else
            
{

                Query(
1,x);
                printf(
"%d\n",ans);
            }


        }



    }

    
return 0;


}

posted @ 2010-10-22 23:29 abilitytao 阅读(1321) | 评论 (0)编辑 收藏

POJ 3468 A Simple Problem with Integers Splay树区间操作

     摘要:     接连做了维修数列和这个题,看来线段树能做的区间操作,用splay树应该也是可以的(都是打一个延迟标记嘛),做这题时发现有一点很重要,就是当我们压入延迟标记的时候(不管是push_down还是C a,b,c时都需要)一定要保证这个结点代表区间的最新信息。    #include <iostream>using...  阅读全文

posted @ 2010-10-22 22:26 abilitytao 阅读(1977) | 评论 (0)编辑 收藏

SomeThing For The Test

就是实现一个简单的集合类IntSet

//"IntSet.h"
//Coded By abilitytao
//2010年9月27日
#include<vector>
#include
<algorithm>
#include
<iostream>
using namespace std;

class IntSet
{
public:
    vector
<int> data;
    IntSet()
    
{data.clear();}
    
~IntSet(){}
    
void insert(int x)
    
{
        
int i;
        
for(i=0;i<data.size();i++)
        
{
            
if(data[i]==x)
                
return;
        }

        data.push_back(x);
    }

    
bool IsEqual(IntSet s)
    
{
        sort(data.begin(),data.end());
        
if(data.size()!=s.data.size())
            
return false;
        
for(int i=0;i<data.size();i++)
        
{

            
if(data[i]!=s.data[i])
                
return false;
        }

        
return true;
    }

    IntSet union2(IntSet s1,IntSet s2)
    
{
        IntSet ans;
        
for(int i=0;i<s1.data.size();i++)
            
for(int j=0;j<s2.data.size();j++)
            
{

                
if(s1.data[i]==s2.data[j])
                    ans.insert(s1.data[i]);
            }

        
return ans;
    }

    IntSet incorporate2(IntSet s1,IntSet s2)
    
{
        IntSet ans;
        
for(int i=0;i<s1.data.size();i++)
        
{
            ans.insert(s1.data[i]);
        }

        
for(int j=0;j<s2.data.size();j++)
        
{
            ans.insert(s2.data[j]);
        }

        
return ans;
    }

    
void print()
    
{
        
for(int i=0;i<data.size();i++)
            printf(
"%d ",data[i]);
    }

}
;


//"IntSet.cpp"
//Coded By abilitytao
//2010年9月27日
#include"IntSet.h"
#include
<iostream>
using namespace std;


int main()
{

    IntSet s1,s2,s3,s4;
    
int x;
    
for(cin>>x;x!=0;cin>>x)
    
{
        s1.insert(x);
    }

    
for(cin>>x;x!=0;cin>>x)
    
{
        s2.insert(x);
    }

    
if(s1.IsEqual(s2))
        cout
<<"s1 is equal s2"<<endl;
    s3
=s3.union2(s1,s2);
    s4
=s4.incorporate2(s1,s2);
    cout
<<"\ns1:";
    s1.print();
    cout
<<"\ns2:";
    s2.print();
    cout
<<"\ns3:";
    s3.print();
    cout
<<"\ns4:";
    s4.print();
    
return 0;
}

posted @ 2010-09-27 17:09 abilitytao 阅读(224) | 评论 (0)编辑 收藏

果断转载 哈尔滨赛区总结 by Latsyrc @ SYSU_Vermouth and zhshzhen (MikeZheng)

      前一天晚上12点就睡了,睡得不是很好,做了几个梦,醒来了几次,其中梦到cyl卡F
题,然后很水的B题最后才过。没想到梦也成真了,只不过题号有偏差。

    鉴于集训的时候我们队错误较多,加上热身赛的观察,我们并不觉得自己速度上有太 大劣势,于是决定采取谨慎的策略,每题提交前再看一遍代码,检查检查。

    还是老策略:我从前往后看,kb看中间,cyl看后面。看了A题,发现看不懂,再看了
一遍,还是不懂,这是kb跟我说C题是3D凸包,求面数,大水题,果断要过来,但是没有马
上开。继续读B题,感觉是一个贪心,跟kb说了一个方法,kb也跟我说了一个方法,突然发
现我们的方法截然相反,于是我丢给他想,果断上去写C题吧。后来证实我们的算法其实是
一样的。写C题的时候看了一下board,发现有人过F,问了问cyl,他说他在规划了,我说
随时推我下来。之后他利落的过掉了F题。然后我继续写C,cyl接手B,kb在想E。经过他们
讨论后证明了算法正确性,cyl上机,提交,结果错了,看程序,发现了他一个很弱智的错
误,修改后就过了。我利用空闲断断续续的写好了C,由于很容易错,于是打印出来检查。
kb上去写A,其间kb跟cyl说了H的做法,cyl规划好了构图方法,让我过了C后帮他敲一个费
用流的模板。在59分钟我很利落的一次过了C题,也是全场第一个。之后很长时间都没有人
过,第二个应该是石头哥。之后kb的A题返回wrong answer,他跟cyl讨论了一下,发现对
题目的理解有问题,迅速修改。我和cyl也在kb改A的时候讨论好了D题,一个裸的dancing
 links,商量好构图后,决定让我来写,其实我没有太大的信心,因为这个东西是在来哈尔滨的火车上学的,还从
来没有写过,同时还讨论了已经很多 
油ü腅题,结果不会。很快kb的A过了。我帮cyl敲完了H的模板,他构图写进去也很顺利
的通过了。就这样前2个钟我们过了5个题目,手头上还有2个题目在做,形势不错。

    然后让cyl暴力E打表找规律,毕竟很多队过了,不会太麻烦,其间我一直在写D,写得
很纠结。事实上当时我们的排名一直在往下掉,我敲D的时候手一直很僵,头很晕,补了一
块巧克力,好了一点。最终经过努力,kb还是在209分钟过掉了E题。我们终于缓了一口气
。在cyl的帮助下,我的D也搞定了,测了几组简单的数据没有错,我问他要不要提交,他
说交,怕什么?说实话我是没有任何信心的,首先这个东西不熟,其次觉得自己写得很乱
,毕竟200多行的代码,错误在所难免,最后就是这题只给了1秒的时限,感觉蛮紧的。结
果居然返回一个YES。我和cyl都叫了出来,顿时士气大振。在我调试D题的时候,kb和cyl
讨论了J,没想到什么好方法,用四边形不等式只能优化到O(n^2),肯定不行,但是没有题
目,还是让kb硬着头皮上了。然后cyl弄I题,kb说自己的肯定过不了,于是让我再想J。我
列了一条式子,发现具有单调性,然后跟kb讨论了一下,被他质疑了,其实我还是很肯定
的,于是还是给他写完吧,我继续想。他提交毫无疑问返回了超时,我也在书中翻出了类
似于我列出的那条式子的式子,还剩下30分钟,时间还足够,于是果断抢过机器,利用kb
之前写的预处理,直接把dp写了上去,写完后他们一起帮我查错,提交,答案错了,再检查,发现打反了一个符号,修改,再提交,一个大大的绿色的YES。 我大喊了一声:“哥立功了!”。真是内牛满面。然后我就果断打酱油了,他们两个在讨
论那个积分题,后来才发现算错了一个东西,不够时间改了。最终定格8题,5题一次过的
,2个wrong answer,一个TLE。其中那两个wrong answer完全可以避免。

    后来跟石头哥他们讨论才发现G题他们的方法跟kb想的一样,kb觉得时间太紧于是没有
做,实在太可惜了,最后10多分钟写一个SPFA也不是什么难事的。其实想想卡E和D的期间
上G也是一个不错的选择。总结这次比赛,最大的败笔就是E题,一个毫无疑问的大水题,
我们被卡了很久很久,浪费了很多时间,似乎我们的3个队对于这类题目都很水,还得加强
锻炼。或许如果比赛前期就丢J给我,我们对于时间的安排就会更为合理。至于我个人的发
挥,我比较满意,两个200多行的代码都是1AC,J题也顶住压力绝杀成功,事实上08年在北
京我也是最后30分钟绝杀一道单调性dp的题目。

    说说队员间的配合。我们队算是磨合得比较好的,其中D题的构图是我和cyl讨论出来
的,B题的正确性是kb和cyl讨论出来的,H题算法是kb提出,模板是我抄的,其他代码由c
yl完成。J题kb提供了预处理。

    最后bless 1,2,8队在下一站天津赛区中再创佳绩!
--




其实结果就一句话:“混水摸到鱼了。”

农历八月十七,中秋节后,经过漫漫四十多个小时的火车,我们终于到了这个传说中冰天
雪地的哈尔滨。下火车,天气好,晴朗阳光下伴着瑟瑟凉风,有点冻……

星期天早上九点多,比赛正式开始。
开ball,我调机器,然后从前看,石头哥D开始,训哥后面看题。
看完A后,我发现题目规模巨大,马上淡定了,心想应该不用什么复杂的博弈,但还是放了 下来。
这时,石头哥看完C、D,说D用在火车上新学会的dancing link可以搞搞,C是纯模板题,
然后果断让位给石头哥拍C模板。
我继续看B,好像原来B更水,几番思前想后,我还是直接抢断石头哥的C,自己敲B,因为
B真的好像很水……B的做法是两次排序然后for一下,直接过了。
刷board,有人过F,chyx也跟风很快过掉了F。
再刷board,发现A、E、H都可做。换人,石头哥继续敲模板。训哥接过他的菜数学题E,无
奈说了好多次不会做……囧。不管了,于是我拉他过来小讨论了下A,发现真的挺水,就敲
了,就过了……
剩下E、H。E是数学题,我想还是训哥继续纠结一下吧。H是明显的费用流,我想好建图后
,上模板,直接又过掉……看来今天我的手风还是挺好的。
E嘛,训哥还在说不会做……囧,好奇怪,我推了下居然好像就推出来了,又不管了,抢过
机器,试了下,发现样例都错了,改了下,就过掉了……

此时5题,全是1AC,华丽了……
期间,石头哥的C交了,然后错了。叫他加上判重点、共线、共面后,还是不过……无奈之
下,训哥作为解放出来的生产力,去敲I了,说不想浪费机时,先敲个输入输出。
石头哥说应该C没错的呀,但还是先放下了C,接过训哥给的G,说好像半平面交能做……我
对着石头哥C的程序和石头模板,发现真的没敲错,不过有个新加的判共线的地方很诡异,
问之,石头哥说傻B了,一改,救过了C,搞了这么久的C终于过掉了……石头哥状态不佳啊
,囧。

6题在手,但比赛时间还有好多好多,此时成绩并不足够。
到了后期,训哥一直在纠结I,说之前一直在研究这个数值积分,应该没问题的啦,但还是
过不了……换模板,发现模板上的精度更水,就又继续埋头纠结了。
其实我一早就接过训哥的J,但想起上次百度之星写过一个类似的当时写得我很纠结的单调
性DP,马上就颓了……石头哥说可以四边形不等式优化一下,发现还是TLE,然后我就不得
不重温上次的悲剧了,一边手写J的单调性DP,时不时一边看看石头哥的G。
话说石头哥和训哥讨论后,拿出算法导论,发现G可以差分约束,然后猛男般地上去敲G…
…改了几个小bug,加了一个优化后,就神奇地过了G,无敌了……
训哥的I在最后不知道怎么根据函数的特点改变了积分的方法就过掉了,同样离奇……

比赛结束,我的J,写到最后调出样例和几个水数据之后一直交不过。我的错,小悲剧了…


总体,中大的三个队成绩都挺满意。三队Vermoth第四,我们四队Vodka第五,都金了,六
队波本也银了,很好!


下一站,杭州,坐等送死。
--

posted @ 2010-09-26 23:36 abilitytao 阅读(347) | 评论 (0)编辑 收藏

生产实习硬件实践

又是锻炼汇编能力的训练。发现自己在每次写汇编程序之前都不知道基本的代码模式...具体的实现倒不是很难,只是刚开始的时候由于不知道基本模式浪费了一些时间。
1.步进电机控制应用程序设计
.MODEL        SMALL
.STACK
.DATA
        PORT  DW        0E460H
     WELCOME  DB        
'welcome to my programme,please make choice',0DH,0AH,'$'
         OP1  DB        
'1.clockwise',0DH,0AH,'$'
         OP2  DB        
'2.counter-clockwise',0AH,0DH,'$'
         OP3  DB        
'3.exit',0AH,0DH,'$'
          OP  DB        
'input your choice:','$'
         TEM  DB        
'?'
.CODE
    SHOWMENU  PROC      NEAR
              PUSH      AX
              MOV       DX,OFFSET WELCOME
              MOV       AH,09H
              INT       21H
              MOV       DX,OFFSET OP1
              INT       21H
              MOV       DX,OFFSET OP2
              INT       21H
              MOV       DX,OFFSET OP3
              INT       21H
              MOV       DX,OFFSET OP
              INT       21H
              POP       AX
              RET
    SHOWMENU  ENDP

       DELAY  PROC      NEAR
              PUSH      DX
              PUSH      BX
              MOV       DX,0FFFH
         T2:
              MOV       BX,5FFFH
         T1:
              DEC       BX
              JNZ       T1
              DEC       DX
              JNZ       T2
              POP       BX
              POP       DX
              RET
       DELAY  ENDP

.startup
              MOV       AX,@DATA
              MOV       DS,AX
        ABC:
              CALL      SHOWMENU

              MOV       AH,01H      ;input one 
char
              INT       21H
              PUSH      AX
              MOV       AH,02H
              MOV       DL,0AH
              INT       21H
              MOV       DL,0DH
              INT       21H
              POP       AX

              CMP       AL,
'1'
              JZ        OPTION1
              CMP       AL,
'2'
              JZ        OPTION2
              CMP       AL,
'3'
              JZ        EXIT

    OPTION1:
              MOV       DX,PORT
              MOV       AL,33H
              MOV       CX,
100
      AGAIN:
              OUT       DX,AL
              CALL      DELAY
              ROL       AL,
1
              LOOP      AGAIN
              JMP       ABC
    OPTION2:
              MOV       DX,PORT
              MOV       AL,33H
              MOV       CX,
100
     AGAIN2:
              OUT       DX,AL
              CALL      DELAY
              ROR       AL,
1
              LOOP      AGAIN2
              JMP       ABC
       EXIT:
.EXIT         
0
              END


2.温度测量与控制应用程序设计
.model small
.stack
.data
ten db 0AH
port1 dw 0E460H
port2 dw 0E480H
heat db 0ffh
cool db 00h
wel    db 
'welcome to my programme',0dh,0ah,'$'
op1 db 
'1.heat the device',0ah,0dh,'$'
op0 db 
'0.exit to dos',0ah,0dh,'$'
warn db 
'----->>>>>>warnning:if the TEMP is over 70,it will be cut off',0ah,0dh,'$'
chioce db 
'choice:','$'

.code

show proc near
   push dx
   push ax
   mov ah,09h
    mov dx,offset wel
    
int 21h
    mov dx,offset op1
    
int 21h
    mov dx,offset op0
    
int 21h
    mov dx,offset warn
    
int 21h
    mov dx,offset chioce
    
int 21h
    pop ax
    pop dx
    ret
show endp
delay proc near
   push dx
   push bx
   mov dx,5fffh
T2:
   mov bx,5fffh
T1:
   dec bx
   jnz T1
   dec dx
   jnz T2
   pop bx
   pop dx
   ret
delay endp
change proc near;
interface ax
    push ax
    push dx
    div ten
    mov dh,00h
    mov dl,ah
    push dx
    mov ah,
0
    div ten
    mov dh,00H
    mov dl,ah
    push dx
    pop dx
    add dx,30h
    mov ah,02h
    
int 21h
    pop dx
    add dx,30h
    
int 21h
    mov dl,0ah
    
int 21h
    mov dl,0dh
    
int 21h

    pop dx
    pop ax
    ret
change endp


.startup
init:
  call show


   mov dx,port1
   mov al,cool
   
out dx,al

   mov ah,01h
   
int 21h


   push ax
   mov ah,02h
   mov Dl,0ah
   
int 21h
   mov Dl,0dh
   
int 21h
   pop ax


   cmp al,
'1'
   jnz exit

option1:
    mov dx,port2
    mov ax,
0
    
out dx,al
    call delay
    mov dx,port1
    mov al,heat
    
out dx,al
again:
       mov dx,port2
    mov ax,
0
    
out dx,al
    mov dx,port2
    
in al,dx
    call delay

    mov ah,
0
    call change
    cmp al,
70
    ja init
    mov ah,01h
    
int 16h
    jnz init


    jmp again





exit:
.exit 
0
end

posted @ 2010-09-09 00:43 abilitytao 阅读(225) | 评论 (0)编辑 收藏

仅列出标题
共42页: First 5 6 7 8 9 10 11 12 13 Last