#
摘要: 發現對匯編還是非常的生疏，可能平時程序寫少了吧，尤其是對那些寄存器可以間接尋址記的不牢，BIOS調用什么基本是現學現賣。原來這個BIOS調用比DOS調用還要底層，連輸出字符串的功能都沒有，輸入字符串要要用鍵盤中斷，顯示漢字要用字模，所謂字模就是一個點陣，用整數表示，用位運算去判斷是否在此處輸出點，很傻×的方法。為了能...
閱讀全文
##Update 2010-4-16
這里稍微證明一下:
給定方程
x = c1 (mod b1) ……………………(1)
x = c2(mod b2) ………………………(2)
(b1,b2)可以不為1
于是通過取mod 定義，我們得到
x = k1 * b1 + c1………………(3)
(3) 帶入(2)
k1 * b1 + c1 = c2 (mod b2)…………(4)
化簡
k1 * b1 = c2 - c1 (mod b2)…………(5)
于是可以解得到
令G = gcd(b1,b2),C = c2 - c1 (mod b2)
那么由(5)得到
k1 * b1 = W * b2 + C
---->>>>>
k1 * b1 / G = W * b2 / G + C / G
令C' = C/G
k1 * b1 / G = W * b2 / G + C '
k1 * b1 / G = C' (mod b2 / G)
--->
k1 = K (mod b2/G)………………(6)
那么有
k1 = k' * b2/G + K………………(7)
(7)帶入(3)
x = k' * b2 * b1/G + K * b1 + c1………………(8)
x = K*b1 + c1 (mod b1 * b2/G)
通過合并方程的方法成功AC下面此題
題目地址
#include<iostream>
#include<cmath>
using namespace std;
//x = c1 ( mod b1)
//x = c2 ( mod b2)
//若可以可并，則返回合并結果，否則返回-1
可以處理gcd(b1,b2)!=1的情況
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int ext_gcd(int a,int b,int& x,int& y){
int t,ret;
if (!b){
x=1,y=0;
return a;
}
ret=ext_gcd(b,a%b,x,y);
t=x,x=y,y=t-a/b*y;
return ret;
}
//求a對n的乘法逆元，若不存在返回-1
int Invmod(int a,int n){
int x,y;
if (ext_gcd(a,n,x,y)!=1)return -1;
return (x%n+n)%n;
}
int mergef(int b1,int c1,int b2,int c2,int &b,int &c)
{
int tb1=b1,tb2=b2;
c=((c2-c1)%b2+b2)%b2;
int G=gcd(b1,b2);
if(c%G)return 0;
c/=G;
b1/=G;
b2/=G;
c*=Invmod(b1,b2);
c%=b2;
c*=tb1;
c+=c1;
b=tb1*tb2/G;
c%=b;
return 1;
}
int main()
{
int b1,b2,c1,c2,b,c;
while(cin>>b1>>c1>>b2>>c2)
{
if(mergef(b1,c1,b2,c2,b,c))
cout<<"X = "<<c<<' '<<"(mod "<<b<<')'<<endl;
}
return 0;
}擴充了算法導論中中國剩余定理部分的內容，使得它可以處理更一般的情況了，這個模板具有通用性。
轉自：
http://hi.baidu.com/aekdycoin/blog/item/71d7a842b93f611b73f05da4.html順便提一下，除了整理模板之外，要開始網絡流部分的強化訓練了，強化構圖能力。
摘要: 所謂0->n-1路徑上一定要經過的割邊，就是0->n-1任意一條路徑上的割邊，因為割邊是必經之路。其實這題跟ZOJ 2588是同一個題，稍微變化就可以得到答案了，不過這題我當時的模板貌似寫挫了，對邊進行判重的時候進行了暴力，其實可以用set存一下，那么查找的復雜度可以降到log(n). 具體求割邊的方法可以看這個：http://www.cp...
閱讀全文
//數學建模
//2010年8月21日21:55:29
#include<iostream>
#include<algorithm>
#include<vector>
#include<sstream>
#include<string>
using namespace std;
int const maxn=10000;
char in[100000];
vector<string>mm[maxn];
int cnt=0;
bool isdigt(char a)
{
if(a>='0'&&a<='9')
return true;
else
return false;
}
void predo()
{
int len=strlen(in);
for(int i=0;i<len;i++)
{
if(!isdigt(in[i]))
in[i]=' ';
}
}
string ans;
void dfs(int k,string str)
{
if(k==cnt)
{
cout<<str<<endl;
return;
}
int n=mm[k].size();
for(int i=0;i<n;i++)
{
if(k!=0)
//cout<<"-"<<mm[k][i];
{
str+="-";
str+=mm[k][i];
}
else
//cout<<mm[k][i];
str+=mm[k][i];
dfs(k+1,str);
if(k!=0)
//cout<<"-"<<mm[k][i];
{
str=str.substr(0,str.length()-mm[k][i].length()-1);
}
else
//cout<<mm[k][i];
str=str.substr(0,str.length()-mm[k][i].length());
}
}
int main()
{
freopen("IN.txt","r",stdin);
freopen("OUT.txt","w",stdout);
cnt=0;
ans="";
while(cin.getline(in,100000))
{
predo();
//debug
//printf("%s\n",in);
//system("pause");
//
istringstream t(in);
string tem;
while(t>>tem)
{
mm[cnt].push_back(tem);
}
cnt++;
}
//debug
/**//*
printf("cnt = %d\n",cnt);
for(int i=0;i<cnt;i++)
{
for(int j=0;j<mm[i].size();j++)
{
cout<<mm[i][j]<<' ';
}
cout<<endl;
}
system("pause");
*/
dfs(0,ans);
return 0;
}
第一組
0567， 0042， 0025
1487
0303， 0302
0566
0436， 0438， 0437， 0435
0392， 0394， 0393， 0391
0386， 0388， 0387， 0385
3068， 0617， 0619， 0618， 0616
1279
2057， 0721， 0722， 0720
0070， 2361， 3721
0609， 0608
2633， 0399， 0401， 0400
3321， 2535， 2464
3329， 2534
3506， 0167， 0168
0237， 0239， 0238， 0236， 0540
0668
0180， 0181
2079， 2933， 1919， 1921， 1920
0465， 0467， 0466， 0464
3457
第二組
0537， 3580
0526， 0528， 0527， 0525
3045， 0605， 0607
0609， 0608
0087， 0088， 0086
0855， 0856， 0854， 0857
0631， 0632， 0630
3874， 1426， 1427
0211， 0539， 0541， 0540
0978， 0497， 0498
0668
1894， 1896， 1895
1104， 0576， 0578， 0577
3010， 0583， 0582
3676， 0427， 0061， 0060
1961， 2817， 0455， 0456
3262， 0622
1956， 0289， 0291
如果說《青花瓷》是江南古巷中的一位美人，那《蜀繡》便是巫山奇峽間的一卷流云。
一、詞
雖然不太關注郭敬明，不可否認的是，這首詞作得是不錯的。尤有幾句點睛之筆，讓我喜愛不已。
最喜愛的一句首推“羽毛扇遙指千軍陣 錦緞裁幾寸”。這一句可說已道盡整首《蜀繡》的精髓所在。和人聊天時曾說，如果這首歌只留一句詞，那留這句便可。“羽毛扇”三字道出蜀地，“錦緞”則是繡布，以“遙指千軍陣”呼應“裁幾寸”，似乎看到繡娘以柔荑素腕繡出萬馬奔騰，又似乎暗喻蜀繡絲線細密，用針如用兵。
而“繞指柔破錦千萬針 杜鵑啼血聲 芙蓉花蜀國盡繽紛 轉眼塵歸塵”兩句也甚得我心。
“繞指柔破錦千萬針 杜鵑啼血聲” 刺繡原是無聲的，但這句寫來，隱隱有“聽雪落”的感覺。一針針破錦似有聲，針針都是漏夜無眠子規啼血聲。整首詞說的是繡娘等征人的故事，而這句既有刺繡之勞，亦有等人之苦，可謂一語雙關。
“芙蓉花蜀國盡繽紛 轉眼塵歸塵” 有種道盡人間是滄桑的味道，配合李宇春柔和的嗓音唱出，尤其有一種淡淡愁緒，但又不是絕望，只是舉首凝望，淺吟輕唱。讓我想到以前和人戲作的一副對聯：“滄桑世間應無恙 聚散浮云不問情”。
絮叨得有些支離破碎。下來不得不提的是整首詞的韻腳。
整首詞主要以“ㄣ（en）”“ㄥ（eng）”為韻腳（紛、針、村、分、春等韻腳是en，燈、疼、聲、等、成等韻腳是eng），個人感覺這個韻腳特別適合李宇春這種中音且清糯的嗓音。咬在齒間，在口中鼻間繞個圈，再輕輕吐出，別有一種撓人心底的韻味。這種發音，唯有此等中音才能唱出最別致的滋味，若是高音，則高亢有余，以這種韻腳收尾，怕是發散了出去收不回來了；或是聲音再厚重點，怕是鼻音有余，余韻不足。唯有李宇春這等清糯淡雅的中音，才能把這種韻腳詮釋得恰到好處，有點小性感的滋味十足。
二、曲
這支曲很有高唐流云感，聽在耳間，似見云卷云舒流于巫山，又似霓裳羽衣翻轉旋舞，仿佛一副華美繡卷緩緩舒展于眼前。
作為一支中國風的曲，民樂元素是不可或缺的。
我耳拙，聽不出太多，只在樂間聽出了揚琴、二胡和笛子聲，也不知聽得對不對。（揚琴是在朋友的幫助下確認的，細辨了一番是琵琶還是揚琴 囧）
在開始時，似不經意地點綴一些清脆的揚琴聲，清越而靈動；隨著曲子展開，二胡這種很抒情樂器插入，曲中多出現在繡娘思征人處，柔腸千轉；到“君可見刺繡又一針 有人為你疼”始，笛聲也開始出現，華卷漸漸展開，流云變幻萬千。
用李宇春淡雅干凈的嗓音來詮釋這支有些華麗的曲子，有意料不到的好效果，一種繁花開盡顯霜華的舒暢感。歷盡一季繁華后的霜枝，別有一番肆意舒展的感動。她淡吟唱的華曲，簡繁結合得極致完美。中國畫講究的是寫意，中華一脈相隨的文化講究的也是寫意，隨意潑墨點綴的梅枝可以綻出最生動的花瓣，輕松流暢的干凈嗓音可以歌出最生動的畫卷。
三、唱
整支曲唱下來，如水銀瀉地。
那個小韻腳形成的小性感不再贅述，中國畫般的寫意流暢也不重復了。特別想說的是她對一些小細節的處理。
“君可見刺繡又一針 有人為你疼 君可見牡丹開一生 有人為你等
……
君可見刺繡又一針 有人為你疼 君可見夏雨秋風有人 為你等”
此二句，若是一般人處理，怕會有一種“啊啊啊，俺等嫩那么久，嫩咋滴還不回來”的感覺。但李宇春處理下來，卻是一種冷眼觀世間、心痛卻無奈的感覺，似手扶錦緞，觀古人之悲，娓娓向今人道來。用一個朋友的話說就是：她的歌聲里，有一種“悲天憫人”。
王國維說詩詞有有我之境，有無我之境。這首詞無疑是“有我”的，但這兩句李宇春隱隱唱出一絲“無我”的意味——皆非我所愿，世事本如是。
“濃情蜜意此話當真”一句，在詞來說，于我而言是整支詞中較弱的部分，但卻被她唱成了最有韻味的一句。“濃情蜜意”嚼在口中，聽來淡淡的，“此話”后卻是一頓，之后慢慢吟出比別句多幾份沉凝和不確定的“當真”，突然讓人心痛起來，讓人突然看到繡娘的悲哀——山盟尚在，良人何在？細密的悲傷悄悄漾起，替古人悲傷起來。
起首的“芙蓉城三月雨紛紛 四月繡花針 羽毛扇遙指千軍陣 錦緞裁幾寸”及曲中的“繞指柔破錦千萬針 杜鵑啼血聲 芙蓉花蜀國盡繽紛 轉眼塵歸塵”兩句，曲幾至無聲，所以幾乎可以說是清唱。李宇春的聲音本就很適合清唱，她的歌聲里有一種磁糯的黏性，有曲聲時易被蓋住，清唱時——尤其是抒情慢歌，這種黏性便破陣而出，可以把人深深地吸進去。
“江河向海奔，萬物為誰春”同樣是一種超脫大度的感覺，似乎小心翼翼地吐出的十個字，有一種為傷心人吟懷的體貼。
李宇春曾說過，“中國風”久已有之，其實《中華民謠》之類也是中國風的——那種風格，類似民謠戲曲。
查百科，對“中國風”有嚴格的定義。但也許我聽歌不多，一直覺得聽到的“中國風”不是江南般婉約，就是戰場上纏綿。
這一支，卻是中國畫般，舒展開來，如云蔚山間，沒有刻意的纏綿和故作的沉吟，不是落寞的冷月或壯志的戰士，她只是淡淡地、緩緩地，為你展開圖畫—— 一副歷經滄桑的繡品，繡的也許是盛唐牡丹，也許是敦煌飛天，也許是明月小橋，也或許是萬馬奔騰，各種圖畫變幻著撲面而來，聚成“蜀繡”兩字。
附《蜀繡》歌詞
作詞：郭敬明
芙蓉城/三月雨紛紛/四月繡花針
羽毛扇遙指千軍陣/錦緞裁幾寸
看鐵馬踏冰河/絲線縫韶華/紅塵千帳燈
山水一程/風雪再一程
紅燭枕/五月花葉深/六月杏花村
紅酥手/青絲萬千根/姻緣多一分
等殘陽照孤影/牡丹染銅樽/滿城牧笛聲
伊人倚門/望君踏歸程
君可見/刺繡每一針/有人為你疼
君可見/牡丹開一生/有人為你等
江河入海奔/萬物為誰春
明月照不盡離別人
君可見/刺繡又一針/有人為你疼
君可見/夏雨秋風/有人為你等
翠竹泣墨痕/錦書畫不成
情針意線/繡不盡鴛鴦枕
此生笑傲/風月瘦如刀/催人老
來世與君暮暮又朝朝/多逍遙
——摘自豆瓣
7月13號 FZU（周二，福大OJ)
7月15號 BUPT（周四）
7月20號 WHU（周二）
7月22號 UESTC（周四）
7月27號 BJTU（周二）
7月29號 NUDT（周四）
8月3號 HIT（周二，哈工大OJ）
8月5號 ECNU（周四，HDOJ）
8月7號 HDU（周六，聯合訓練 暨 HDOJ Monthly Contest，HDOJ）
8月10號 HNU（周二）
8月12號 TJU （周四）
8月17號 BUPT（周二）
8月19號 WHU（周四）
8月24號 UESTC（周二）
8月26號 BJTU（周四）
8月31號 NUDT（周二）
9月2號 BIT（周四，HDOJ）
9月7號 ZSTU（周二）
9月9號 HRBEU（周四）
100除以7的余數是2，意思就是說把100個東西七個七個分成一組的話最后還剩2個。余數有一個嚴格的定義：假如被除數是a，除數是b（假設它們均為正整數），那么我們總能夠找到一個小于b的自然數r和一個整數m，使得a=bm+r。這個r就是a除以b的余數，m被稱作商。我們經常用mod來表示取余，a除以b余r就寫成a mod b = r。
如果兩個數a和b之差能被m整除，那么我們就說a和b對模數m同余（關于m同余）。比如，100-60除以8正好除盡，我們就說100和60對于模數8同余。它的另一層含義就是說，100和60除以8的余數相同。a和b對m同余，我們記作a≡b(mod m)。比如，剛才的例子可以寫成100≡60(mod 8)。你會發現這種記號到處都在用，比如和數論相關的書中就經常把a mod 3 = 1寫作a≡1(mod 3)。
之所以把同余當作一種運算，是因為同余滿足運算的諸多性質。比如，同余滿足等價關系。具體地說，它滿足自反性（一個數永遠和自己同余）、對稱性（a和b同余，b和a也就同余）和傳遞性（a和b同余，b和c同余可以推出a和c同余）。這三個性質都是顯然的。
同余運算里還有稍微復雜一些的性質。比如，同余運算和整數加減法一樣滿足“等量加等量，其和不變”。小學我們就知道，等式兩邊可以同時加上一個相等的數。例如，a=b可以推出a+100=b+100。這樣的性質在同余運算中也有：對于同一個模數m，如果a和b同余，x和y同余，那么a+x和b+y也同余。在我看來，這個結論幾乎是顯然的。當然，我們也可以嚴格證明這個定理。這個定理對減法同樣有效。
性質：如果a≡b(mod m)，x≡y(mod m)，則a+x≡b+y(mod m)。 證明：條件告訴我們，可以找到p和q使得a-mp = b-mq，也存在r和s使得x-mr = y-ms。于是a-mp + x-mr = b-mq + y-ms，即a+x-m(p+r) = b+y-m(q+s)，這就告訴我們a+x和b+y除以m的余數相同。
容易想到，兩個同余式對應相乘，同余式兩邊仍然相等：
如果a≡b(mod m)，x≡y(mod m)，則ax≡by(mod m)。 證明：條件告訴我們，a-mp = b-mq，x-mr = y-ms。于是(a-mp)(x-mr) = (b-mq)(y-ms)，等式兩邊分別展開后必然是ax-m(...) = by-m(...)的形式，這就說明ax≡by(mod m)。
現在你知道為什么
有的題要叫你“輸出答案mod xxxxx的結果”了吧，那是為了避免高精度運算，因為這里的結論告訴我們在運算過程中邊算邊mod和算完后再mod的結果一樣。假如a是一個很大的數，令b=a mod m，那么(a * 100) mod m和(b * 100) mod m的結果是完全一樣的，這相當于是在a≡b (mod m)的兩邊同時乘以100。這些結論其實都很顯然，因為同余運算只關心余數（不關心“整的部分”），完全可以每一次運算后都只保留余數。因此，整個運算過程中參與運算的數都不超過m，避免了高精度的出現。
在證明
Fermat小定理時，我們用到了這樣一個定理：
如果ac≡bc(mod m)，且c和m互質，則a≡b(mod m) （就是說同余式兩邊可以同時除以一個和模數互質的數）。
證明：條件告訴我們，ac-mp = bc-mq，移項可得ac-bc = mp-mq，也就是說(a-b)c = m(p-q)。這表明，(a-b)c里需要含有因子m，但c和m互質，因此只有可能是a-b被m整除，也即a≡b(mod m
http://www.matrix67.com/blog/archives/236保存一下，以備今后學習:-)
記得當時做高斯消元那個題的時候，嘉龍的代碼死活過不了，后來發現是在航電long long 要用%I64d ,看來我沒吸取這個教訓啊，今天做昨天第七場的題目的時候，又犯了同樣的錯誤，浪費了一個下午，從Dij+heap到SPFA,能換的最短路算法都用了，就是過不了航電，還以為加了什么數據，原來是judge的問題，BS!
線段樹 經典的題目，以前曾經做過一遍，現在為了練手在做一次，剛學了splay樹，反倒是加深了對線段樹的理解，就是那個延遲標記（也就是懶操作）。雖然線段樹已經寫過多次，但是這題仍然不能1A,Query函數中有個地方應該是mid=(ST[i].l+ST[i].r)>>1寫成了(l+r)>>1,導致wa了幾次，今后要注意啊。
#include<iostream>
using namespace std;
int const maxn=100010;
int n,t,q;
struct node
{
int l,r;
int col;//用位來存儲顏色
int cover;//延遲標記
}ST[maxn*4];
void Build(int l,int r,int i)
{
ST[i].l=l;
ST[i].r=r;
ST[i].col=0;
ST[i].cover=0;
if(l==r)
return;
int mid=(l+r)>>1;
Build(l,mid,i*2);
Build(mid+1,r,i*2+1);
}
void push_down(int i)
{
ST[i*2].col=ST[i].col;
ST[i*2+1].col=ST[i].col;
ST[i].cover=0;
ST[i*2].cover=1;
ST[i*2+1].cover=1;
}
void insert(int l,int r,int col,int i)
{
if(ST[i].l==l&&ST[i].r==r)
{
ST[i].cover=1;
ST[i].col=(1<<(col-1));
return ;
}
if(ST[i].cover)//如果當前區間有效，下沿延遲標記
push_down(i);
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)
insert(l,r,col,i*2);
else if(l>mid)
insert(l,r,col,i*2+1);
else
{
insert(l,mid,col,i*2);
insert(mid+1,r,col,i*2+1);
}
ST[i].col=ST[i*2].col|ST[i*2+1].col;
}
int fun(int num)//檢查最后返回的整數中有多少顏色
{
int ans=0;
int i;
for(i=0;i<t;i++)
if(num&(1<<i))
ans++;
return ans;
}
int Que(int l,int r,int i)
{
if( (ST[i].l==l&&ST[i].r==r)||ST[i].cover==1)
return ST[i].col;
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)
return Que(l,r,i*2);
else if(l>mid)
return Que(l,r,i*2+1);
else
return Que(l,mid,i*2)|Que(mid+1,r,i*2+1);
}
int main()
{
while(scanf("%d%d%d",&n,&t,&q)!=EOF)
{
Build(1,n,1);
ST[1].cover=1;
ST[1].col=1;
char op[20];
int a,b,c;
for(int i=1;i<=q;i++)
{
scanf("%s",op);
if(op[0]=='C')
{
scanf("%d%d%d",&a,&b,&c);
if(a>b)
swap(a,b);
insert(a,b,c,1);
}
else
{
scanf("%d%d",&a,&b);
if(a>b)
swap(a,b);
printf("%d\n",fun(Que(a,b,1)));
}
}
}
return 0;
}