#
摘要: 發(fā)現(xiàn)對匯編還是非常的生疏，可能平時程序?qū)懮倭税桑绕涫菍δ切┘拇嫫骺梢蚤g接尋址記的不牢，BIOS調(diào)用什么基本是現(xiàn)學(xué)現(xiàn)賣。原來這個BIOS調(diào)用比DOS調(diào)用還要底層，連輸出字符串的功能都沒有，輸入字符串要要用鍵盤中斷，顯示漢字要用字模，所謂字模就是一個點陣，用整數(shù)表示，用位運(yùn)算去判斷是否在此處輸出點，很傻×的方法。為了能...
閱讀全文
##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)
//若可以可并，則返回合并結(jié)果，否則返回-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;
}擴(kuò)充了算法導(dǎo)論中中國剩余定理部分的內(nèi)容，使得它可以處理更一般的情況了，這個模板具有通用性。
轉(zhuǎn)自：
http://hi.baidu.com/aekdycoin/blog/item/71d7a842b93f611b73f05da4.html順便提一下，除了整理模板之外，要開始網(wǎng)絡(luò)流部分的強(qiáng)化訓(xùn)練了，強(qiáng)化構(gòu)圖能力。
摘要: 所謂0->n-1路徑上一定要經(jīng)過的割邊，就是0->n-1任意一條路徑上的割邊，因為割邊是必經(jīng)之路。其實這題跟ZOJ 2588是同一個題，稍微變化就可以得到答案了，不過這題我當(dāng)時的模板貌似寫挫了，對邊進(jìn)行判重的時候進(jìn)行了暴力，其實可以用set存一下，那么查找的復(fù)雜度可以降到log(n). 具體求割邊的方法可以看這個：http://www.cp...
閱讀全文
//數(shù)學(xué)建模
//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
如果說《青花瓷》是江南古巷中的一位美人，那《蜀繡》便是巫山奇峽間的一卷流云。
一、詞
雖然不太關(guān)注郭敬明，不可否認(rèn)的是，這首詞作得是不錯的。尤有幾句點睛之筆，讓我喜愛不已。
最喜愛的一句首推“羽毛扇遙指千軍陣 錦緞裁幾寸”。這一句可說已道盡整首《蜀繡》的精髓所在。和人聊天時曾說，如果這首歌只留一句詞，那留這句便可。“羽毛扇”三字道出蜀地，“錦緞”則是繡布，以“遙指千軍陣”呼應(yīng)“裁幾寸”，似乎看到繡娘以柔荑素腕繡出萬馬奔騰，又似乎暗喻蜀繡絲線細(xì)密，用針如用兵。
而“繞指柔破錦千萬針 杜鵑啼血聲 芙蓉花蜀國盡繽紛 轉(zhuǎn)眼塵歸塵”兩句也甚得我心。
“繞指柔破錦千萬針 杜鵑啼血聲” 刺繡原是無聲的，但這句寫來，隱隱有“聽雪落”的感覺。一針針破錦似有聲，針針都是漏夜無眠子規(guī)啼血聲。整首詞說的是繡娘等征人的故事，而這句既有刺繡之勞，亦有等人之苦，可謂一語雙關(guān)。
“芙蓉花蜀國盡繽紛 轉(zhuǎn)眼塵歸塵” 有種道盡人間是滄桑的味道，配合李宇春柔和的嗓音唱出，尤其有一種淡淡愁緒，但又不是絕望，只是舉首凝望，淺吟輕唱。讓我想到以前和人戲作的一副對聯(lián)：“滄桑世間應(yīng)無恙 聚散浮云不問情”。
絮叨得有些支離破碎。下來不得不提的是整首詞的韻腳。
整首詞主要以“ㄣ（en）”“ㄥ（eng）”為韻腳（紛、針、村、分、春等韻腳是en，燈、疼、聲、等、成等韻腳是eng），個人感覺這個韻腳特別適合李宇春這種中音且清糯的嗓音。咬在齒間，在口中鼻間繞個圈，再輕輕吐出，別有一種撓人心底的韻味。這種發(fā)音，唯有此等中音才能唱出最別致的滋味，若是高音，則高亢有余，以這種韻腳收尾，怕是發(fā)散了出去收不回來了；或是聲音再厚重點，怕是鼻音有余，余韻不足。唯有李宇春這等清糯淡雅的中音，才能把這種韻腳詮釋得恰到好處，有點小性感的滋味十足。
二、曲
這支曲很有高唐流云感，聽在耳間，似見云卷云舒流于巫山，又似霓裳羽衣翻轉(zhuǎn)旋舞，仿佛一副華美繡卷緩緩舒展于眼前。
作為一支中國風(fēng)的曲，民樂元素是不可或缺的。
我耳拙，聽不出太多，只在樂間聽出了揚(yáng)琴、二胡和笛子聲，也不知聽得對不對。（揚(yáng)琴是在朋友的幫助下確認(rèn)的，細(xì)辨了一番是琵琶還是揚(yáng)琴 囧）
在開始時，似不經(jīng)意地點綴一些清脆的揚(yáng)琴聲，清越而靈動；隨著曲子展開，二胡這種很抒情樂器插入，曲中多出現(xiàn)在繡娘思征人處，柔腸千轉(zhuǎn)；到“君可見刺繡又一針 有人為你疼”始，笛聲也開始出現(xiàn)，華卷漸漸展開，流云變幻萬千。
用李宇春淡雅干凈的嗓音來詮釋這支有些華麗的曲子，有意料不到的好效果，一種繁花開盡顯霜華的舒暢感。歷盡一季繁華后的霜枝，別有一番肆意舒展的感動。她淡吟唱的華曲，簡繁結(jié)合得極致完美。中國畫講究的是寫意，中華一脈相隨的文化講究的也是寫意，隨意潑墨點綴的梅枝可以綻出最生動的花瓣，輕松流暢的干凈嗓音可以歌出最生動的畫卷。
三、唱
整支曲唱下來，如水銀瀉地。
那個小韻腳形成的小性感不再贅述，中國畫般的寫意流暢也不重復(fù)了。特別想說的是她對一些小細(xì)節(jié)的處理。
“君可見刺繡又一針 有人為你疼 君可見牡丹開一生 有人為你等
……
君可見刺繡又一針 有人為你疼 君可見夏雨秋風(fēng)有人 為你等”
此二句，若是一般人處理，怕會有一種“啊啊啊，俺等嫩那么久，嫩咋滴還不回來”的感覺。但李宇春處理下來，卻是一種冷眼觀世間、心痛卻無奈的感覺，似手扶錦緞，觀古人之悲，娓娓向今人道來。用一個朋友的話說就是：她的歌聲里，有一種“悲天憫人”。
王國維說詩詞有有我之境，有無我之境。這首詞無疑是“有我”的，但這兩句李宇春隱隱唱出一絲“無我”的意味——皆非我所愿，世事本如是。
“濃情蜜意此話當(dāng)真”一句，在詞來說，于我而言是整支詞中較弱的部分，但卻被她唱成了最有韻味的一句。“濃情蜜意”嚼在口中，聽來淡淡的，“此話”后卻是一頓，之后慢慢吟出比別句多幾份沉凝和不確定的“當(dāng)真”，突然讓人心痛起來，讓人突然看到繡娘的悲哀——山盟尚在，良人何在？細(xì)密的悲傷悄悄漾起，替古人悲傷起來。
起首的“芙蓉城三月雨紛紛 四月繡花針 羽毛扇遙指千軍陣 錦緞裁幾寸”及曲中的“繞指柔破錦千萬針 杜鵑啼血聲 芙蓉花蜀國盡繽紛 轉(zhuǎn)眼塵歸塵”兩句，曲幾至無聲，所以幾乎可以說是清唱。李宇春的聲音本就很適合清唱，她的歌聲里有一種磁糯的黏性，有曲聲時易被蓋住，清唱時——尤其是抒情慢歌，這種黏性便破陣而出，可以把人深深地吸進(jìn)去。
“江河向海奔，萬物為誰春”同樣是一種超脫大度的感覺，似乎小心翼翼地吐出的十個字，有一種為傷心人吟懷的體貼。
李宇春曾說過，“中國風(fēng)”久已有之，其實《中華民謠》之類也是中國風(fēng)的——那種風(fēng)格，類似民謠戲曲。
查百科，對“中國風(fēng)”有嚴(yán)格的定義。但也許我聽歌不多，一直覺得聽到的“中國風(fēng)”不是江南般婉約，就是戰(zhàn)場上纏綿。
這一支，卻是中國畫般，舒展開來，如云蔚山間，沒有刻意的纏綿和故作的沉吟，不是落寞的冷月或壯志的戰(zhàn)士，她只是淡淡地、緩緩地，為你展開圖畫—— 一副歷經(jīng)滄桑的繡品，繡的也許是盛唐牡丹，也許是敦煌飛天，也許是明月小橋，也或許是萬馬奔騰，各種圖畫變幻著撲面而來，聚成“蜀繡”兩字。
附《蜀繡》歌詞
作詞：郭敬明
芙蓉城/三月雨紛紛/四月繡花針
羽毛扇遙指千軍陣/錦緞裁幾寸
看鐵馬踏冰河/絲線縫韶華/紅塵千帳燈
山水一程/風(fēng)雪再一程
紅燭枕/五月花葉深/六月杏花村
紅酥手/青絲萬千根/姻緣多一分
等殘陽照孤影/牡丹染銅樽/滿城牧笛聲
伊人倚門/望君踏歸程
君可見/刺繡每一針/有人為你疼
君可見/牡丹開一生/有人為你等
江河入海奔/萬物為誰春
明月照不盡離別人
君可見/刺繡又一針/有人為你疼
君可見/夏雨秋風(fēng)/有人為你等
翠竹泣墨痕/錦書畫不成
情針意線/繡不盡鴛鴦?wù)?/p>
此生笑傲/風(fēng)月瘦如刀/催人老
來世與君暮暮又朝朝/多逍遙
——摘自豆瓣
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（周六，聯(lián)合訓(xùn)練 暨 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的余數(shù)是2，意思就是說把100個東西七個七個分成一組的話最后還剩2個。余數(shù)有一個嚴(yán)格的定義：假如被除數(shù)是a，除數(shù)是b（假設(shè)它們均為正整數(shù)），那么我們總能夠找到一個小于b的自然數(shù)r和一個整數(shù)m，使得a=bm+r。這個r就是a除以b的余數(shù)，m被稱作商。我們經(jīng)常用mod來表示取余，a除以b余r就寫成a mod b = r。
如果兩個數(shù)a和b之差能被m整除，那么我們就說a和b對模數(shù)m同余（關(guān)于m同余）。比如，100-60除以8正好除盡，我們就說100和60對于模數(shù)8同余。它的另一層含義就是說，100和60除以8的余數(shù)相同。a和b對m同余，我們記作a≡b(mod m)。比如，剛才的例子可以寫成100≡60(mod 8)。你會發(fā)現(xiàn)這種記號到處都在用，比如和數(shù)論相關(guān)的書中就經(jīng)常把a(bǔ) mod 3 = 1寫作a≡1(mod 3)。
之所以把同余當(dāng)作一種運(yùn)算，是因為同余滿足運(yùn)算的諸多性質(zhì)。比如，同余滿足等價關(guān)系。具體地說，它滿足自反性（一個數(shù)永遠(yuǎn)和自己同余）、對稱性（a和b同余，b和a也就同余）和傳遞性（a和b同余，b和c同余可以推出a和c同余）。這三個性質(zhì)都是顯然的。
同余運(yùn)算里還有稍微復(fù)雜一些的性質(zhì)。比如，同余運(yùn)算和整數(shù)加減法一樣滿足“等量加等量，其和不變”。小學(xué)我們就知道，等式兩邊可以同時加上一個相等的數(shù)。例如，a=b可以推出a+100=b+100。這樣的性質(zhì)在同余運(yùn)算中也有：對于同一個模數(shù)m，如果a和b同余，x和y同余，那么a+x和b+y也同余。在我看來，這個結(jié)論幾乎是顯然的。當(dāng)然，我們也可以嚴(yán)格證明這個定理。這個定理對減法同樣有效。
性質(zhì)：如果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的余數(shù)相同。
容易想到，兩個同余式對應(yīng)相乘，同余式兩邊仍然相等：
如果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)。
現(xiàn)在你知道為什么
有的題要叫你“輸出答案mod xxxxx的結(jié)果”了吧，那是為了避免高精度運(yùn)算，因為這里的結(jié)論告訴我們在運(yùn)算過程中邊算邊mod和算完后再mod的結(jié)果一樣。假如a是一個很大的數(shù)，令b=a mod m，那么(a * 100) mod m和(b * 100) mod m的結(jié)果是完全一樣的，這相當(dāng)于是在a≡b (mod m)的兩邊同時乘以100。這些結(jié)論其實都很顯然，因為同余運(yùn)算只關(guān)心余數(shù)（不關(guān)心“整的部分”），完全可以每一次運(yùn)算后都只保留余數(shù)。因此，整個運(yùn)算過程中參與運(yùn)算的數(shù)都不超過m，避免了高精度的出現(xiàn)。
在證明
Fermat小定理時，我們用到了這樣一個定理：
如果ac≡bc(mod m)，且c和m互質(zhì)，則a≡b(mod m) （就是說同余式兩邊可以同時除以一個和模數(shù)互質(zhì)的數(shù)）。
證明：條件告訴我們，ac-mp = bc-mq，移項可得ac-bc = mp-mq，也就是說(a-b)c = m(p-q)。這表明，(a-b)c里需要含有因子m，但c和m互質(zhì)，因此只有可能是a-b被m整除，也即a≡b(mod m
http://www.matrix67.com/blog/archives/236保存一下，以備今后學(xué)習(xí):-)
記得當(dāng)時做高斯消元那個題的時候，嘉龍的代碼死活過不了，后來發(fā)現(xiàn)是在航電long long 要用%I64d ,看來我沒吸取這個教訓(xùn)啊，今天做昨天第七場的題目的時候，又犯了同樣的錯誤，浪費(fèi)了一個下午，從Dij+heap到SPFA,能換的最短路算法都用了，就是過不了航電，還以為加了什么數(shù)據(jù)，原來是judge的問題，BS!
線段樹 經(jīng)典的題目，以前曾經(jīng)做過一遍，現(xiàn)在為了練手在做一次，剛學(xué)了splay樹，反倒是加深了對線段樹的理解，就是那個延遲標(biāo)記（也就是懶操作）。雖然線段樹已經(jīng)寫過多次，但是這題仍然不能1A,Query函數(shù)中有個地方應(yīng)該是mid=(ST[i].l+ST[i].r)>>1寫成了(l+r)>>1,導(dǎo)致wa了幾次，今后要注意啊。
#include<iostream>
using namespace std;
int const maxn=100010;
int n,t,q;
struct node
{
int l,r;
int col;//用位來存儲顏色
int cover;//延遲標(biāo)記
}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)//如果當(dāng)前區(qū)間有效，下沿延遲標(biāo)記
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)//檢查最后返回的整數(shù)中有多少顏色
{
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;
}