1. 甯哥敤鐨勬暟鎹鍘嬬緝綆楁硶鏈夊摢浜涳紵
鍦ㄦ暟瀛楀寲鏃朵唬錛屾暟鎹鐨勫瓨鍌ㄥ拰浼犺緭鏁堢巼鏄懼緱灝や負閲嶈併備負浜嗗噺灝忓瓨鍌ㄧ┖闂村拰甯﹀介渶奼傦紝鍚勭嶆暟鎹鍘嬬緝綆楁硶濡傞洦鍚庢槬絎嬭埇娑岀幇銆傝繖浜涚畻娉曚緷鎹涓嶅悓鐨勫師鐞嗗拰閫傜敤鍦烘櫙錛屽垎涓哄彲閫嗗拰闈炲彲閫嗕袱縐嶇被鍨嬶紝鏃ㄥ湪鍦ㄤ繚璇佹暟鎹瀹屾暣鎬х殑鍓嶆彁涓嬶紝灝藉彲鑳藉湴鍘嬬緝鏁版嵁浣撶Н銆傝╂垜浠娣卞叆鎺㈣ㄤ竴涓嬭繖浜涘父鐢ㄧ殑鏁版嵁鍘嬬緝綆楁硶銆
棣栧厛錛屽彲閫嗗帇緙╃畻娉曪紝濡侶uffman緙栫爜錛屼互鍏舵棤鎹熺壒鎬ц屽彈鍒伴潚鐫愩傚畠閫氳繃瀵規暟鎹鐨勯戠巼鍒嗘瀽錛屼負姣忎釜瀛楃﹀垎閰嶆渶鐭鐨勭紪鐮侊紝浠庤屽疄鐜伴珮鏁堢殑鍘嬬緝銆傝繖縐嶇紪鐮佹柟寮忕『淇濅簡瑙ｅ帇鍚庣殑鏁版嵁涓庡師濮嬫暟鎹涓鑷達紝閫傜敤浜庡規暟鎹鍑嗙『鎬ц佹眰鏋侀珮鐨勫満鏅銆
鎺ョ潃錛岄潪鍙閫嗗帇緙╃畻娉曞侸PEG錛屼互鐗虹壊涓瀹氱殑鏁版嵁綺劇『搴︽崲鍙栨洿楂樼殑鍘嬬緝姣斻傝繖綾葷畻娉曞湪鍥懼儚澶勭悊鍜岃嗛戝帇緙╀腑騫挎硾搴旂敤錛屽挨鍏舵槸鍦ㄥ硅嗚夎川閲忚佹眰鐩稿硅緝浣庣殑鎯呭喌涓嬶紝鑳芥樉钁楀噺灝忔暟鎹閲忋
鏁版嵁鍘嬬緝鐨勭瓥鐣ュ氱嶅氭牱錛屽寘鎷鍩轟簬鍐呭圭殑緙栫爜錛堝傚瓧絎︿覆涓棰戠箒瀛楃︾殑棰戠巼緙栫爜錛夈佽〃紺烘柟娉曪紙濡傞湇澶鏇肩紪鐮佸規椂搴忔暟鎹鐨勯珮鏁堝勭悊錛変互鍙婂規暟鎹嫻佽勫緥鎬х殑鍒╃敤錛堝傛父紼嬬紪鐮佸拰RLE錛岀敤浜庤繛緇閲嶅嶆暟鎹鐨勫帇緙╋級銆備緥濡傦紝"this is a example"閫氳繃棰戠巼緙栫爜鑳藉噺灝忓埌54姣旂壒錛屾瘮鍘熷136姣旂壒鑺傜渷綰2.5鍊嶇殑瀛樺偍絀洪棿銆
Delta鍜孌elta-of-Delta緙栫爜鍒欏湪澶勭悊鏂囦歡鍘嗗彶璁板綍鍜屽崟璋冨簭鍒楁椂琛ㄧ幇鍑鴻壊錛岄厤鍚圧LE絳夋妧鏈錛岃兘鏄捐憲闄嶄綆鏁版嵁澶у皬銆侱elta閫氳繃閫愪釜鍏冪礌鐨勫樊寮傛潵鍘嬬緝鏁版嵁錛岃屼簩闃跺樊鍒嗙紪鐮佸垯榪涗竴姝ュ垎鏋愬墠鍚庝袱涓鍏冪礌鐨勫樊寮傦紝涓よ呭湪鐗瑰畾鍦烘櫙涓嬮兘鑳芥彁渚涢珮鏁堝帇緙┿
Zig-zag緙栫爜鐗瑰埆閽堝硅礋鏁幫紝涓嶥elta緇撳悎鑳芥湁鏁堝勭悊灝忔暟錛屽疄鐜伴珮鏁堝瓨鍌ㄣ侴oogle寮婧愮殑Snappy浠ュ叾蹇閫熺殑鍘嬬緝閫熷害鍜屽悎鐞嗙殑鍘嬬緝鏁堟灉錛屽箍娉涘簲鐢ㄤ簬寮婧愰」鐩錛岃孡Z4鍒欎互鍏跺瓧鑺傜駭鐨勫揩閫熻В鍘嬫ц兘錛岀壒鍒閫傚悎瀹炴椂鏁版嵁浼犺緭銆
Simple8b綆楁硶綆鍗曢珮鏁堬紝涓撲負灝忔暣鏁拌捐★紝浣嗗帇緙╃巼鍙鑳借緝浣庛侺ZO鍒欎互蹇閫熷帇緙╄侀暱錛屼絾瑙ｅ帇閫熷害鐣ラ婁簬LZ4錛屾洿閫傚悎澶勭悊澶у潡鏁版嵁銆侱EFLATE綆楁硶鏄痾ip鏂囦歡鐨勯粯璁ゅ帇緙╂柟寮忥紝瀹冪粨鍚堜簡LZ77鍜孒uffman緙栫爜錛屾彁渚涗簡涓縐嶅鉤琛＄殑鍘嬬緝絳栫暐銆
榪戝勾鏉ワ紝Zstandard浠ュ叾楂樻晥鐨勫帇緙╁拰蹇閫熺殑瑙ｅ帇鑳藉姏宕闇插ご瑙掞紝涓烘湭鏉ユ暟鎹鍘嬬緝鎶鏈鐨勫彂灞曟弿緇樹簡騫塊様鍓嶆櫙銆傝孊it-packing鍒欓氳繃鍘婚櫎涓嶅繀瑕佺殑浣嶏紝榪涗竴姝ヨ妭鐪佸瓨鍌ㄧ┖闂達紝浣嗗彲鑳藉獎鍝嶆暟鎹鐨勮誨彇閫熷害銆
TDengine鏁版嵁搴撻噰鐢ㄤ簡涓闃舵靛帇緙╋紙鍖呮嫭Delta銆丼imple8b銆亃ig-zag鍜孡Z4錛夊拰浜岄樁孌甸氱敤鍘嬬緝絳栫暐錛屼互閫傚簲涓嶅悓鍦烘櫙鐨勯渶奼傘傞夋嫨鍘嬬緝綆楁硶鏃訛紝闇瑕佺患鍚堣冭檻鍘嬬緝鏁堢巼銆佽В鍘嬮熷害浠ュ強鏁版嵁鐨勫師濮嬬簿搴︼紝浠ユ壘鍒版渶閫傚悎鐨勮В鍐蟲柟妗堛
鍦ㄦ暟瀛楀寲涓栫晫涓錛屾暟鎹鍘嬬緝綆楁硶鏄鎻愬崌瀛樺偍鍜屼紶杈撴晥鐜囩殑鍏抽敭宸ュ叿銆傛瘡涓縐嶇畻娉曢兘鏈夊叾鐙鐗圭殑浼樺娍鍜岄傜敤鑼冨洿錛屼簡瑙ｅ苟鐏墊椿榪愮敤榪欎簺宸ュ叿錛岃兘甯鍔╂垜浠鏇村ソ鍦扮＄悊鏁版嵁錛岄檷浣庡瓨鍌ㄦ垚鏈錛屾彁楂樻暟鎹澶勭悊閫熷害銆
2. c++編程設計兩道題。 求在n×m的棋盤上放k顆皇後的放法（1≤k≤n，m）（皇後可以斜著吃棋）（
採用狀態壓縮的辦法，因為用搜索的辦法，直接用32位的整數int進行壓縮。
如果這個int的二進制位是1，就表示該位是在某個皇後的攻擊范圍，不能放只皇後，0表示可以放置。
因為一行最多擺放1個皇後，所以從行開始搜索。
以下是第一題的代碼：
#include<iostream>
#include<cstring>
#defineULLunsignedlonglong
#defineUINTunsignedint
usingnamespacestd;
intN,M,K,ans;
voiddfs(introw,intdeep,UINTcol,UINTdig,UINTadg){//所在行,已放皇後數量,(列、左對角線、右對角線)的狀態
if(deep==K){
ans++;
return;
}
if(row==N)return;
UINTt=1;
for(inti=0;i<M;i++){
if((t&col)||(t&dig)||(t&adg)){
t<<=1;
continue;
}
dfs(row+1,deep+1,(t|col),(t|dig)>>1,(t|adg)<<1);
t<<=1;
}
if((N-row-1)+deep>=K)//這行不擺放。優化：如果剩下行數都擺放了還不能滿足條件，就不用搜下去了
dfs(row+1,deep,col,dig>>1,adg<<1);
}
intmain(){
while(cin>>N>>M>>K){
if(N<M)swap(N,M);//保證列數少，方便狀態壓縮
ans=0;
dfs(0,0,0,0,0);
cout<<ans<<endl;
}
return0;
}
第二問其實就是第一問k=n的情況
#include<iostream>
#include<cstring>
#defineULLunsignedlonglong
#defineUINTunsignedint
usingnamespacestd;
intN,M,K,ans;
voiddfs(introw,intdeep,UINTcol,UINTdig,UINTadg){//所在行,已放皇後數量,(列、左對角線、右對角線)的狀態
if(deep==K){
ans++;
return;
}
if(row==N)return;
UINTt=1;
for(inti=0;i<M;i++){
if((t&col)||(t&dig)||(t&adg)){
t<<=1;
continue;
}
dfs(row+1,deep+1,(t|col),(t|dig)>>1,(t|adg)<<1);
t<<=1;
}
if((N-row-1)+deep>=K)
dfs(row+1,deep,col,dig>>1,adg<<1);
}
intmain(){
while(cin>>N>>M){
K=N;
if(N<M)swap(N,M);//保證列數少，方便狀態壓縮
ans=0;
dfs(0,0,0,0,0);
cout<<ans<<endl;
}
return0;
}