#
最大流
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 (枚舉匯點(diǎn))
POJ 1087 A Plug for UNIX
POJ 1149 Pigs (構(gòu)圖題)
ZOJ 2760 How Many Shortest Path (邊不相交最短路的條數(shù))
POJ 2391 Ombrophobic Bovines (必須拆點(diǎn)，否則有BUG)
WHU 1124 Football Coach (構(gòu)圖題)
SGU 326 Perspective (構(gòu)圖題，類似于 WHU 1124)
UVa 563 Crimewave
UVa 820 Internet Bandwidth
POJ 3281 Dining (構(gòu)圖題)
POJ 3436 ACM Computer Factory
POJ 2289 Jamie's Contact Groups (二分)
SGU 438 The Glorious Karlutka River =) (按時(shí)間拆點(diǎn))
SGU 242 Student's Morning (輸出一組解)
SGU 185 Two shortest (Dijkstra 預(yù)處理，兩次增廣，必須用鄰接陣實(shí)現(xiàn)，否則 MLE)
HOJ 2816 Power Line
POJ 2699 The Maximum Number of Strong Kings (枚舉+構(gòu)圖)
ZOJ 2332 Gems
JOJ 2453 Candy (構(gòu)圖題)
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 (找關(guān)鍵割邊)
POJ 1815 Friendship (字典序最小的點(diǎn)割集)
POJ 3204 Ikki's Story I - Road Reconstruction (找關(guān)鍵割邊)
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 (最大權(quán)閉合子圖)
POJ 1966 Cable TV Network (無(wú)向圖點(diǎn)連通度)
HDU 1565 方格取數(shù)(1) (最大點(diǎn)權(quán)獨(dú)立集)
HDU 1569 方格取數(shù)(2) (最大點(diǎn)權(quán)獨(dú)立集)
POJ 2987 Firing (最大權(quán)閉合子圖)
SPOJ 839 Optimal Marks (將異或操作轉(zhuǎn)化為對(duì)每一位求最小割)
HOJ 2811 Earthquake Damage (最小點(diǎn)割集)
2008 Beijing Regional Contest Problem A Destroying the bus stations ( BFS 預(yù)處理 )(
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4322)
ZOJ 2676 Network Wars (參數(shù)搜索)
POJ 3155 Hard Life (參數(shù)搜索)
ZOJ 3241 Being a Hero
有上下界
ZOJ 2314 Reactor Cooling (無(wú)源匯可行流)
POJ 2396 Budget (有源匯可行流)
SGU 176 Flow Construction (有源匯最小流)
ZOJ 3229 Shoot the Bullet (有源匯最大流)
HDU 3157 Crazy Circuits (有源匯最小流)
最小費(fèi)用流
HOJ 2715 Matrix3
HOJ 2739 The Chinese Postman Problem
POJ 2175 Evacuation Plan (消一次負(fù)圈)
POJ 3422 Kaka's Matrix Travels (與 Matrix3 類似)
POJ 2516 Minimum Cost (按物品種類多次建圖)
POJ 2195 Going Home
BUAA 1032 Destroying a Painting
POJ 2400 Supervisor, Supervisee (輸出所有最小權(quán)匹配)
POJ 3680 Intervals
HOJ 2543 Stone IV
POJ 2135 Farm Tour
BASHU2445 餐巾問(wèn)題
---------------------------------------------onmylove原創(chuàng)
最大流題目：
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
zju1992：http://acm.zju.edu.cn/show_problem.php?pid=1992
求增廣邊：
Poj3204：http://acm.pku.edu.cn/JudgeOnline/problem?id=3204
類似：Hoj1082: http://acm.hust.edu.cn/thx/problem.php?cid=1017&pid=6
項(xiàng)目選擇問(wèn)題：
Poj3469：http://acm.pku.edu.cn/JudgeOnline/problem?id=3469
Zoj2930：http://acm.zju.edu.cn/show_problem.php?pid=2930
求項(xiàng)目選擇項(xiàng)目最多的方案。
建圖：
Poj1149：http://acm.pku.edu.cn/JudgeOnline/problem?id=1149
Poj3436：http://acm.pku.edu.cn/JudgeOnline/problem?id=3436
Poj3281：http://acm.pku.edu.cn/JudgeOnline/problem?id=3281
連通度：
點(diǎn)連通度Poj1966: http://acm.pku.edu.cn/JudgeOnline/problem?id=1966
Uva563, http://icpcres.ecs.baylor.edu/onlinejudge/
點(diǎn)不交的路徑條數(shù)問(wèn)題，需要拆點(diǎn)
最小割：
Poj2914：http://acm.pku.edu.cn/JudgeOnline/problem?id=2914
（stoer-Wagner）
基本題：
Poj3498：http://acm.pku.edu.cn/JudgeOnline/problem?id=3498
枚舉:做n次最大流。
Poj1087：http://acm.pku.edu.cn/JudgeOnline/problem?id=1087
可以用最大流做，也可以用二分圖匹配做。
Poj1273：http://acm.pku.edu.cn/JudgeOnline/problem?id=1273
Poj1274：http://acm.pku.edu.cn/JudgeOnline/problem?id=1274
Poj1325: http://acm.pku.edu.cn/JudgeOnline/problem?id=1325
poj1459：http://acm.pku.edu.cn/JudgeOnline/problem?id=1459
Poj1797：http://acm.pku.edu.cn/JudgeOnline/problem?id=1797
Poj1815：http://acm.pku.edu.cn/JudgeOnline/problem?id=1815
poj2112：http://acm.pku.edu.cn/JudgeOnline/problem?id=2112
poj2239：http://acm.pku.edu.cn/JudgeOnline/problem?id=2239
poj2289: http://acm.pku.edu.cn/JudgeOnline/problem?id=2289
Poj2391：http://acm.pku.edu.cn/JudgeOnline/problem?id=2391
Poj2987：http://acm.pku.edu.cn/JudgeOnline/problem?id=2987
Poj3308：http://acm.pku.edu.cn/JudgeOnline/problem?id=3308
提示：最大權(quán)閉包，轉(zhuǎn)化成最大流
Poj3155: http://acm.pku.edu.cn/JudgeOnline/problem?id=3155
難
SGU 176 http://acm.sgu.ru/problem.php?contest=0&problem=176
容量有上下界的網(wǎng)絡(luò)流問(wèn)題，有難度
Spoj660：http://www.spoj.pl/problems/QUEST4/
Spoj377：http://www.spoj.pl/problems/TAXI/
UVA
http://icpcres.ecs.baylor.edu/onlinejudge/
753,
820,
10122,
10330,
10511,
10735.
題意：求1->n的兩條不相交的最短路（兩條路徑可以共頂點(diǎn)但是不能共邊)
心得：看了AC的博客學(xué)的，呵呵，這題充分展示了一切皆是網(wǎng)絡(luò)流的核心思想。做法：首先找出以1為頂點(diǎn)的最短路徑樹，1到樹中任意一點(diǎn)的連線都是最短路徑，首先把這些邊加到網(wǎng)絡(luò)流的邊集中，容量為1。
然后再枚舉下邊，將不在最短路徑樹上但是在最短路上的邊也加到網(wǎng)絡(luò)流的邊集中，容量為1。跑一遍1到n的最大流，如果流量>=2則有解，再?gòu)脑c(diǎn)深搜路徑即可。
確切的來(lái)說(shuō)，只要在后來(lái)建的圖中隨便找一條路徑均是原點(diǎn)到該點(diǎn)的最短路（注意邊是單向的），又因?yàn)橄拗屏肆髁渴?，所以一條邊只能選取一次，這樣跑出來(lái)的流量就一定是不相交最短路的條數(shù)。
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;
}
很難得的一次寫對(duì)了SPFA...
參考了AC大神的代碼，遞歸刪除邊的時(shí)候?qū)⒘髁恐脼?1,不錯(cuò)的想法。另外我用p-edge的奇偶性判斷正反邊，但是一直沒(méi)弄明白p和edge都是地址而且地址相差并不是1的時(shí)候減出來(lái)卻是1。。。
摘要: 實(shí)在不行，改了方法。SET 0和SET 1用延遲標(biāo)記，翻轉(zhuǎn)不用任何標(biāo)記，直接更新到底。800+MS AC.
#include<cstdlib>#include<iostream>#include<algorithm>#include<cstdio>using namespace std;int const m...
閱讀全文
摘要: 這題有點(diǎn)像Hotel的包裝版，非常經(jīng)典，讓我進(jìn)一步熟悉了線段樹的區(qū)間操作（主要是延遲標(biāo)記的使用）。唯一的問(wèn)題出在自己寫的二分函數(shù)上，死活都是TLE，后來(lái)參考了小HH的二分才過(guò)掉，不知道自己哪寫掛了，郁悶。。。。PS:順便問(wèn)一下，高質(zhì)量的內(nèi)存管理難道真的是用線段樹實(shí)現(xiàn)的？
#include<iostream>#include<algorithm>#include<ve...
閱讀全文
題意：可以標(biāo)記區(qū)間上某些節(jié)點(diǎn)或者取消標(biāo)記，并查詢與x連續(xù)的未被標(biāo)記的結(jié)點(diǎn)數(shù)。
這題和Hotel類似，由于換成了單節(jié)點(diǎn)操作，不需要區(qū)間操作的延遲標(biāo)記，維護(hù)起來(lái)更方便。
#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;
}
很顯而易見的線段樹，只是有一點(diǎn)需要注意，題目中雖然給了h的范圍可以達(dá)到10^9，但是由于布告總共只有200000條，最壞情況下只需要200000個(gè)線段樹的葉子節(jié)點(diǎn)，所以可以直接無(wú)視h的范圍，線段樹總結(jié)點(diǎn)開200000*4即可。維護(hù)的時(shí)候，注意利用回溯，自底向上地更新。
#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;
}
摘要: 接連做了維修數(shù)列和這個(gè)題，看來(lái)線段樹能做的區(qū)間操作，用splay樹應(yīng)該也是可以的（都是打一個(gè)延遲標(biāo)記嘛）,做這題時(shí)發(fā)現(xiàn)有一點(diǎn)很重要，就是當(dāng)我們壓入延遲標(biāo)記的時(shí)候(不管是push_down還是C a,b,c時(shí)都需要)一定要保證這個(gè)結(jié)點(diǎn)代表區(qū)間的最新信息。
#include <iostream>using...
閱讀全文
前一天晚上12點(diǎn)就睡了，睡得不是很好，做了幾個(gè)夢(mèng)，醒來(lái)了幾次，其中夢(mèng)到cyl卡F
題，然后很水的B題最后才過(guò)。沒(méi)想到夢(mèng)也成真了，只不過(guò)題號(hào)有偏差。
鑒于集訓(xùn)的時(shí)候我們隊(duì)錯(cuò)誤較多，加上熱身賽的觀察，我們并不覺(jué)得自己速度上有太 大劣勢(shì)，于是決定采取謹(jǐn)慎的策略，每題提交前再看一遍代碼，檢查檢查。
還是老策略：我從前往后看，kb看中間，cyl看后面。看了A題，發(fā)現(xiàn)看不懂，再看了
一遍，還是不懂，這是kb跟我說(shuō)C題是3D凸包，求面數(shù)，大水題，果斷要過(guò)來(lái)，但是沒(méi)有馬
上開。繼續(xù)讀B題，感覺(jué)是一個(gè)貪心，跟kb說(shuō)了一個(gè)方法，kb也跟我說(shuō)了一個(gè)方法，突然發(fā)
現(xiàn)我們的方法截然相反，于是我丟給他想，果斷上去寫C題吧。后來(lái)證實(shí)我們的算法其實(shí)是
一樣的。寫C題的時(shí)候看了一下board，發(fā)現(xiàn)有人過(guò)F，問(wèn)了問(wèn)cyl，他說(shuō)他在規(guī)劃了，我說(shuō)
隨時(shí)推我下來(lái)。之后他利落的過(guò)掉了F題。然后我繼續(xù)寫C，cyl接手B，kb在想E。經(jīng)過(guò)他們
討論后證明了算法正確性，cyl上機(jī)，提交，結(jié)果錯(cuò)了，看程序，發(fā)現(xiàn)了他一個(gè)很弱智的錯(cuò)
誤，修改后就過(guò)了。我利用空閑斷斷續(xù)續(xù)的寫好了C，由于很容易錯(cuò)，于是打印出來(lái)檢查。
kb上去寫A，其間kb跟cyl說(shuō)了H的做法，cyl規(guī)劃好了構(gòu)圖方法，讓我過(guò)了C后幫他敲一個(gè)費(fèi)
用流的模板。在59分鐘我很利落的一次過(guò)了C題，也是全場(chǎng)第一個(gè)。之后很長(zhǎng)時(shí)間都沒(méi)有人
過(guò)，第二個(gè)應(yīng)該是石頭哥。之后kb的A題返回wrong answer，他跟cyl討論了一下，發(fā)現(xiàn)對(duì)
題目的理解有問(wèn)題，迅速修改。我和cyl也在kb改A的時(shí)候討論好了D題，一個(gè)裸的dancing
links，商量好構(gòu)圖后，決定讓我來(lái)寫，其實(shí)我沒(méi)有太大的信心，因?yàn)檫@個(gè)東西是在來(lái)哈爾濱的火車上學(xué)的，還從
來(lái)沒(méi)有寫過(guò)，同時(shí)還討論了已經(jīng)很多
油ü腅題，結(jié)果不會(huì)。很快kb的A過(guò)了。我?guī)蚦yl敲完了H的模板，他構(gòu)圖寫進(jìn)去也很順利
的通過(guò)了。就這樣前2個(gè)鐘我們過(guò)了5個(gè)題目，手頭上還有2個(gè)題目在做，形勢(shì)不錯(cuò)。
然后讓cyl暴力E打表找規(guī)律，畢竟很多隊(duì)過(guò)了，不會(huì)太麻煩，其間我一直在寫D，寫得
很糾結(jié)。事實(shí)上當(dāng)時(shí)我們的排名一直在往下掉，我敲D的時(shí)候手一直很僵，頭很暈，補(bǔ)了一
塊巧克力，好了一點(diǎn)。最終經(jīng)過(guò)努力，kb還是在209分鐘過(guò)掉了E題。我們終于緩了一口氣
。在cyl的幫助下，我的D也搞定了，測(cè)了幾組簡(jiǎn)單的數(shù)據(jù)沒(méi)有錯(cuò)，我問(wèn)他要不要提交，他
說(shuō)交，怕什么？說(shuō)實(shí)話我是沒(méi)有任何信心的，首先這個(gè)東西不熟，其次覺(jué)得自己寫得很亂
，畢竟200多行的代碼，錯(cuò)誤在所難免，最后就是這題只給了1秒的時(shí)限，感覺(jué)蠻緊的。結(jié)
果居然返回一個(gè)YES。我和cyl都叫了出來(lái)，頓時(shí)士氣大振。在我調(diào)試D題的時(shí)候，kb和cyl
討論了J，沒(méi)想到什么好方法，用四邊形不等式只能優(yōu)化到O(n^2)，肯定不行，但是沒(méi)有題
目，還是讓kb硬著頭皮上了。然后cyl弄I題，kb說(shuō)自己的肯定過(guò)不了，于是讓我再想J。我
列了一條式子，發(fā)現(xiàn)具有單調(diào)性，然后跟kb討論了一下，被他質(zhì)疑了，其實(shí)我還是很肯定
的，于是還是給他寫完吧，我繼續(xù)想。他提交毫無(wú)疑問(wèn)返回了超時(shí)，我也在書中翻出了類
似于我列出的那條式子的式子，還剩下30分鐘，時(shí)間還足夠，于是果斷搶過(guò)機(jī)器，利用kb
之前寫的預(yù)處理，直接把dp寫了上去，寫完后他們一起幫我查錯(cuò)，提交，答案錯(cuò)了，再檢查，發(fā)現(xiàn)打反了一個(gè)符號(hào)，修改，再提交，一個(gè)大大的綠色的YES。 我大喊了一聲：“哥立功了！”。真是內(nèi)牛滿面。然后我就果斷打醬油了，他們兩個(gè)在討
論那個(gè)積分題，后來(lái)才發(fā)現(xiàn)算錯(cuò)了一個(gè)東西，不夠時(shí)間改了。最終定格8題，5題一次過(guò)的
，2個(gè)wrong answer，一個(gè)TLE。其中那兩個(gè)wrong answer完全可以避免。
后來(lái)跟石頭哥他們討論才發(fā)現(xiàn)G題他們的方法跟kb想的一樣，kb覺(jué)得時(shí)間太緊于是沒(méi)有
做，實(shí)在太可惜了，最后10多分鐘寫一個(gè)SPFA也不是什么難事的。其實(shí)想想卡E和D的期間
上G也是一個(gè)不錯(cuò)的選擇。總結(jié)這次比賽，最大的敗筆就是E題，一個(gè)毫無(wú)疑問(wèn)的大水題，
我們被卡了很久很久，浪費(fèi)了很多時(shí)間，似乎我們的3個(gè)隊(duì)對(duì)于這類題目都很水，還得加強(qiáng)
鍛煉。或許如果比賽前期就丟J給我，我們對(duì)于時(shí)間的安排就會(huì)更為合理。至于我個(gè)人的發(fā)
揮，我比較滿意，兩個(gè)200多行的代碼都是1AC，J題也頂住壓力絕殺成功，事實(shí)上08年在北
京我也是最后30分鐘絕殺一道單調(diào)性dp的題目。
說(shuō)說(shuō)隊(duì)員間的配合。我們隊(duì)算是磨合得比較好的，其中D題的構(gòu)圖是我和cyl討論出來(lái)
的，B題的正確性是kb和cyl討論出來(lái)的，H題算法是kb提出，模板是我抄的，其他代碼由c
yl完成。J題kb提供了預(yù)處理。
最后bless 1，2，8隊(duì)在下一站天津賽區(qū)中再創(chuàng)佳績(jī)！
--
其實(shí)結(jié)果就一句話：“混水摸到魚了。”
農(nóng)歷八月十七，中秋節(jié)后，經(jīng)過(guò)漫漫四十多個(gè)小時(shí)的火車，我們終于到了這個(gè)傳說(shuō)中冰天
雪地的哈爾濱。下火車，天氣好，晴朗陽(yáng)光下伴著瑟瑟涼風(fēng)，有點(diǎn)凍……
星期天早上九點(diǎn)多，比賽正式開始。
開ball，我調(diào)機(jī)器，然后從前看，石頭哥D開始，訓(xùn)哥后面看題。
看完A后，我發(fā)現(xiàn)題目規(guī)模巨大，馬上淡定了，心想應(yīng)該不用什么復(fù)雜的博弈，但還是放了 下來(lái)。
這時(shí)，石頭哥看完C、D，說(shuō)D用在火車上新學(xué)會(huì)的dancing link可以搞搞，C是純模板題，
然后果斷讓位給石頭哥拍C模板。
我繼續(xù)看B，好像原來(lái)B更水，幾番思前想后，我還是直接搶斷石頭哥的C，自己敲B，因?yàn)?br>B真的好像很水……B的做法是兩次排序然后for一下，直接過(guò)了。
刷board，有人過(guò)F，chyx也跟風(fēng)很快過(guò)掉了F。
再刷board，發(fā)現(xiàn)A、E、H都可做。換人，石頭哥繼續(xù)敲模板。訓(xùn)哥接過(guò)他的菜數(shù)學(xué)題E，無(wú)
奈說(shuō)了好多次不會(huì)做……囧。不管了，于是我拉他過(guò)來(lái)小討論了下A，發(fā)現(xiàn)真的挺水，就敲
了，就過(guò)了……
剩下E、H。E是數(shù)學(xué)題，我想還是訓(xùn)哥繼續(xù)糾結(jié)一下吧。H是明顯的費(fèi)用流，我想好建圖后
，上模板，直接又過(guò)掉……看來(lái)今天我的手風(fēng)還是挺好的。
E嘛，訓(xùn)哥還在說(shuō)不會(huì)做……囧，好奇怪，我推了下居然好像就推出來(lái)了，又不管了，搶過(guò)
機(jī)器，試了下，發(fā)現(xiàn)樣例都錯(cuò)了，改了下，就過(guò)掉了……
此時(shí)5題，全是1AC，華麗了……
期間，石頭哥的C交了，然后錯(cuò)了。叫他加上判重點(diǎn)、共線、共面后，還是不過(guò)……無(wú)奈之
下，訓(xùn)哥作為解放出來(lái)的生產(chǎn)力，去敲I了，說(shuō)不想浪費(fèi)機(jī)時(shí)，先敲個(gè)輸入輸出。
石頭哥說(shuō)應(yīng)該C沒(méi)錯(cuò)的呀，但還是先放下了C，接過(guò)訓(xùn)哥給的G，說(shuō)好像半平面交能做……我
對(duì)著石頭哥C的程序和石頭模板，發(fā)現(xiàn)真的沒(méi)敲錯(cuò)，不過(guò)有個(gè)新加的判共線的地方很詭異，
問(wèn)之，石頭哥說(shuō)傻B了，一改，救過(guò)了C，搞了這么久的C終于過(guò)掉了……石頭哥狀態(tài)不佳啊
，囧。
6題在手，但比賽時(shí)間還有好多好多，此時(shí)成績(jī)并不足夠。
到了后期，訓(xùn)哥一直在糾結(jié)I，說(shuō)之前一直在研究這個(gè)數(shù)值積分，應(yīng)該沒(méi)問(wèn)題的啦，但還是
過(guò)不了……換模板，發(fā)現(xiàn)模板上的精度更水，就又繼續(xù)埋頭糾結(jié)了。
其實(shí)我一早就接過(guò)訓(xùn)哥的J，但想起上次百度之星寫過(guò)一個(gè)類似的當(dāng)時(shí)寫得我很糾結(jié)的單調(diào)
性DP，馬上就頹了……石頭哥說(shuō)可以四邊形不等式優(yōu)化一下，發(fā)現(xiàn)還是TLE，然后我就不得
不重溫上次的悲劇了，一邊手寫J的單調(diào)性DP，時(shí)不時(shí)一邊看看石頭哥的G。
話說(shuō)石頭哥和訓(xùn)哥討論后，拿出算法導(dǎo)論，發(fā)現(xiàn)G可以差分約束，然后猛男般地上去敲G…
…改了幾個(gè)小bug，加了一個(gè)優(yōu)化后，就神奇地過(guò)了G，無(wú)敵了……
訓(xùn)哥的I在最后不知道怎么根據(jù)函數(shù)的特點(diǎn)改變了積分的方法就過(guò)掉了，同樣離奇……
比賽結(jié)束，我的J，寫到最后調(diào)出樣例和幾個(gè)水?dāng)?shù)據(jù)之后一直交不過(guò)。我的錯(cuò)，小悲劇了…
…
總體，中大的三個(gè)隊(duì)成績(jī)都挺滿意。三隊(duì)Vermoth第四，我們四隊(duì)Vodka第五，都金了，六
隊(duì)波本也銀了，很好！
下一站，杭州，坐等送死。
--
又是鍛煉匯編能力的訓(xùn)練。發(fā)現(xiàn)自己在每次寫匯編程序之前都不知道基本的代碼模式...具體的實(shí)現(xiàn)倒不是很難，只是剛開始的時(shí)候由于不知道基本模式浪費(fèi)了一些時(shí)間。
1.步進(jìn)電機(jī)控制應(yīng)用程序設(shè)計(jì)
.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.溫度測(cè)量與控制應(yīng)用程序設(shè)計(jì)
.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