筆記整理一、輸入輸出1、使用cin不能輸入空格這個字符，string類也不能讀入空格，使用gets（）。會讀入換行符，但不會保存在變量中?？梢韵扔胏har口存下gets的內(nèi)容，然后賦值給string。這樣string會得到包括空格的所有內(nèi)容。2、輸入時有負數(shù)使用scanf,不要去從字符串中分離，會很麻煩3、輸入輸出數(shù)據(jù)量過大時，要使用scanf、printf,速度比cin、cout要快4、cstdio是將stdio.h的內(nèi)容用C++頭文件的形式表示出來。5、％4d右對齊不夠輸出空格,％04d右對齊不夠輸出0。要左對齊，則改為%-4do處理日期問題，把每個月的天數(shù)與閏年化為數(shù)組，非常清晰好處理。二、數(shù)學(xué)問題1、任意進制轉(zhuǎn)換2,素數(shù)問題1087：求約數(shù)的個數(shù)，一般方法會超時，使用sqrt,count+=2.1207：求質(zhì)因數(shù)，只要判斷在1?根號n的范圍內(nèi)就可以了，節(jié)省時間3、二分求塞1081：線性代數(shù)，矩陣二分乘法3D031442：二分快速求幕。JDO31443：矩陣求基（原理與二分求球一樣），模擬了矩陣的乘法，在％M時，注意任何計算結(jié)果都要重新%愀，否則會導(dǎo)致下一次運算結(jié)果上溢而出錯。4、高精度運算1076：大數(shù)階乘5,浮點數(shù)1072：浮點數(shù)表示不是精確表示，所以不能對浮點數(shù)進行==式或！=的比較，盡量轉(zhuǎn)化為整數(shù)的比較。注意組合算法（遞歸）1045：小心小數(shù)的運算6、數(shù)位拆解JDOJ1015：末尾k位數(shù)字是否相同，可以直接模pow（10,k）,不必一位位比較。7,數(shù)據(jù)范圍int2147483648?2147483647longlong的最大值：9223372036854775807longlong的最小值：-9223372036854775808三、Hash3DOJ1018：Hash解決問題，空間換時間。JDO31088：Hash解決了以前卡住的題目，NICE四、貪心算法JDO31435：貪心算法，選擇合適的貪心策略。注意題目細節(jié)，例如不大于這種說法，《=。五、字符串問題strlwr將大寫轉(zhuǎn)為小寫仕。1。碇「也可以），字符串的問題注意思維的全面考慮。注意單詞替換類題目，不要把一個單詞的子串也給替換了，所以要判斷查找到的前后是否為空格（末尾或者第一特殊判斷）。string類型的使用1078：用string類型解決字符串相關(guān)問題很方便。1103：二次方程處理，有時候就得一個個字符判斷來處理QC0JA1117：解方程式等相關(guān)問題時，可以采用未知數(shù)的倍數(shù)，來避開事先不知道未知數(shù)的值的情況JDOJ1809：字符轉(zhuǎn)數(shù)字時，用sprintf比較麻煩時，可以直接使用a-'。'這種方法六、STLsort使用#include〈algorithm〉，sort函數(shù)來排序，時間復(fù)雜度小，代碼簡潔。自寫cmp函數(shù)。sort不能對二維字符串數(shù)組排序，可以改為string數(shù)組。3DOJ1023：sort自寫排序規(guī)則，適用于降序、結(jié)構(gòu)體等多種情況，關(guān)于數(shù)組可以設(shè)大一點,例如字符串數(shù)組空間設(shè)為題目所給的數(shù)字會缺少\。的位置，導(dǎo)致錯誤。3DOJ1185：不要被題目的描述順序所影響，有時要跳出這個圈。該題先說要找出最大數(shù)，把最大數(shù)剔除再排序。但是完全可以先排序，最后一個數(shù)就是最大數(shù)，這樣方便很多。stack和queue全排列函數(shù)1120：STL庫中有全排列函數(shù)，#include<algorithm>,next_permutation提供升序，prev_permutation提供降序參數(shù)是char*類型。3、大根堆（小根堆）JDOJ1107：優(yōu)先隊列（堆）解決哈夫曼樹問題。priority_queue<int,vector<int>,greater<int>>Q;小根堆4、Vector5、MapJDO31450：注意全局變量，在多次使用的時候要初始化，要不然會出現(xiàn)runtimeerror。注意題目細節(jié)，竟然在Yes、N。上沒注意錯誤了好多次。map的使用會節(jié)省名字處理的時間和簡化代碼。七、BFS和DFS八、并查集JDO31446：利用并查集求各種相關(guān)關(guān)系類題，如數(shù)據(jù)信息復(fù)雜，需要使用結(jié)構(gòu)體時，可以采用vector（STL）來存儲。JDO31100：使用了dijkstra算法，寫了很久高精度的乘法、加法和小于重載，第一次WA,重新過一遍修改錯誤后AC。發(fā)現(xiàn)大神分析出此題的距離很特殊，是成倍增長，可以使用最小生成樹算法，代碼簡單。3DO31162：Dijkstra,只要刪除陣營2到陣營1的邊就可以。因為固定了從1（固定陣營1）出發(fā)，到2（固定陣營2）,所以始終要從陣營1到陣營2,而陣營2到陣營1的邊就不能走了，因為跨陣營的路最多只能走一條。九、動態(tài)規(guī)劃1209：動態(tài)規(guī)劃，注意總結(jié)，例如經(jīng)典背包問題1077：動態(tài)規(guī)劃十、其他3DOJ1173：二分查找時間復(fù)雜度較低JDOJ1348：利用歸并排序完成數(shù)組逆序?qū)y(tǒng)計，是按由大到小的順序3DO31113（完全二叉樹）：數(shù)據(jù)值過大，超過了隊列的內(nèi)存限制，并且超時。經(jīng)過自己的分析，使用了簡單的方法。H-一、Dev-C++快捷鍵：Ctrl+F9編譯程序；Ctrl+F10運行；F9編譯并運行；F8調(diào)試程序。JD0J1434：#include<iostream>#include<algorithm>usingnamespacestd;structTV{intstart,end;}；boolcmp(TVa,TVb){returna.end<b.end;)intmain(){intn;while(cin>>n){if(n==0)return0;inti,ans=0,currentime=0;TVbuf[100]；for(i=0;i<n;i++){cin>>buf[i].start>>buf[i].end;}sort(buf,buf+n,cmp);for(i=0;i<n;i++){if(currentime<=buf[i].start){currentime=buf[i].end;ans++;)}cout<<ans<<endl;}return0;)JDOJ1435：#include<iostream>#include<algorithm>#include<cstdio>usingnamespacestd;intmain(){intc;while(cin>>c){inti;for(i=0;i<c;i++){intn,v,w,j,pi[101]={0},ansn=0,count=0;cin>>n>>v>>w;for(j=0;j<n;j++){cin>>pi[j]；)sort(pi,pi+n);for(j=0；j<n;j++){if((ansn+pi[j])<=w*(j+1)){ansn+=pi[j];count++;)elsebreak;}if(count==0)printf(w00.00\n");elseprintf("%d%.21f\nM,count*v,(double)ansn/count/100);}return0;}JDOJ1019：#include<iostream>#include<cstdio>#include<stack>usingnamespacestd;stack<double>num;stack<char>op;voidcalc(){chare=op.top();op.popO;doublec,d;d=num.top();num.pop();c=num.top();num.pop();if(e=='+')num.push(c+d);elseif(e==?-1)num.push(c-d);elseif(e==**?)num.push(c*d);elseif(e==?/*)num.push(c/d);)intmain(){inta;while(scanf(H%dM,&a)!=EOF){charb=getchar();if(a==0&&b==*\n')return0;num.push(a);while(scanf("%c%d“，&b,&a)!=EOF){if(op.empty())op.push(b);else(while(!((b=='*'||b=='/")&&(op.top()=='+'||op.top()==,-1))){calc();if(op.empty())break;}op.push(b);)num.push(a);b=getchar();if(b=='\n')break;}while(!op.empty()){calc();)printf("%.21f\n",num.topO);num.pop();)return0;}JDOJ1078：#include<iostream>#include<string>usingnamespacestd;voidgetrx(stringpx,stringmx){if(px.empty()){return;)intpos=mx.find(px[0]);getrx(px,substr(l,pos),mx.substr(0,pos));getrx(px,substr(pos+l),mx?substr(pos+1));cout<<px[0];}intmain(){stringpx,mx;while(cin>>px>>mx){getrxCpx,mx);cout<<endl;)return0;}3DO31040:#include<iostream>#include<math.h>usingnamespacestd;boolIsPrime(intx){intbound=(int)sqrt(x)+1;for(inti=2;i<bound;i++){if(x%i==0)returnfalse;)returntrue;)intmain(){inti=2,prime[10001],len=0,k;while(len<10000){if(IsPrime(i))prime[len++]=i;“+；)while(cin>>k){cout<<prime[k-1]<<endl;)return0;}JDOJ1440:#include<iostream>#include<math.h>usingnamespacestd;boolIsPrime(intx){intbound=(int)sqrt(x)+1;for(inti=2;i<bound;i++){if(x%i==0)returnfalse;)returntrue;)intmain(){inti=2,j,prime[10001]jlen=0,n;while(i<37629){if(IsPrime(i))prime[len++]=i;i++；)while(cin>>n&&n!=0){intres=0;for(i=0;i<len;i++){if(prime[i]>n/2)break;for(j=0;j<len;j++){if(prime[i]+prime[j]>n)break;elseif(prime[i]+prime[j]==n)res++;))cout<<res<<endl;}return0;)DDO31087:#include<iostream>#include<math.h>usingnamespacestd;intCalyues(inta){inti,count=0,b=sqrt(a);for(i=1;i<sqrt(a);i++){ 〃此處需用sqrtif(a%i==0)count+=2;)if(b*b==a)count++;returncount;)intmain(){intn;while(cin>>n){inti^inputflOOO];for(i=0;i<n;i++){cin>>input[i]])for(i=0;i<n;i++){cout<<Calyues(input[i])<<endl;))return0;}DDOO1442：#include<iostream>usingnamespacestd;#defineM200907intmain(){intn;while(cin>>n){inti;for(i=0;i<n;i++){longlonginta,b,c,k,res;cin>>a>>b>>c>>k;k--；if(a+c==b*2){res=a%M+(k%M)*((b-a)%M);res%=M;}else{longlongintq=(b/a)%M;res=a%M;while(k!=0){if(k%2==1){res*=q;res%=M;)k/=2;q*=q；q%=M;))cout<<res<<endl;)return0;)JDOJ1443：#include<iostream>usingnamespacestd;#defineM9973structMatrix{intd[ll][ll];}；MatrixMultiply(Matrixa,Matrixb,intn){Matrixres;inti,j,k,m,x,y;for(i=0;i<n;i++){for(j=0；j<n;j++){res.d[i][j]=0;for(k=0,m=0;k<n,m<n;k++,m++){res.d[i][j]+=(a.d[i][k]*b.d[m][j])%M;)res.d[i][j]%=M;}}returnres;)MatrixCalcMatrix(Matrixa,intk,intn){Matrixres=a;k--；while(k!=0){if(k%2==1)res=Multiply(reSja,n);k/=2;a=Multiply(a,a,n);)returnres;)intmain(){intt;while(cin>>t){inti;for(i=0;i<t;i++){intn,k,j,a=0,m,res=0;Matrixinput;cin>>n>>k;for(j=0；j<n;j++){for(m=0;m<n;m++)

cin>>input.d[j][m]]}input=CalcMatrix(inputjk,n);for(j=0；j<n;j++){res+=input.d[j][j];)cout<<res%M<<endl;))return0;)JDOD1137：#include<iostream>#include<string>usingnamespacestd;structBigFloat(intInteger[101],Decimal[101];intlenl,len2;voidinit(){inti;for(i=0;i<101;i++)Integer[i]=0;for(i=0;i<101;i++)Decimal[i]=0;lenl=len2=0;)voidset(strings){init();inti,b=s.find('.'for(i=b-1;i>=0;i--)Integer[lenl++]=s[i]-*0*;for(i=b+1;i<s.length();i++)Decimal[len2++]=s[i]-*0*;)};intmain(){intn,i;cin>>n;for(i=0;i<n;i++){stringsi,s2;cin>>si>>s2;BigFloata,b,c;c.init();a.set(sl);b.set(s2);intj,carry=0;for(j=0;j<a.len2||j<b.len2;j++)c.Decimal[c.Ien2++]=a.Decimal[j]+b.Decimal[j];for(j=c.len2-1;j>=0;j--){c.Decimal[j]+=carry;carry=0;if(c.Decimal[j]>9){c.Decimal[j]-=10;carry=1;)}〃小數(shù)可能進位給整數(shù)在此也一起考慮了while(c.Decimal[c.len2-1]==0){c,len2--;if(c.len2==0){c.len2++;break;))for(j=0;j<a.lenl||j<b.lenl;j++){c.Integer[c.lenl++]=a.Integer[j]+b.Integer[j]+carry;carry=0;if(c.Integer[j]>9){c.Integer[j]-=10;carry=1;))if(carry==1){c.Integer[c.lenl++]=1;carry=0;)for(j=c.lenl-1;j>=0;j--)cout<<c.Integer[j];cout<<for(j=0;j<c.len2;j++)cout<<c.Decimal[j];cout<<endl;)return0;)JDOJ1080：#include<iostream>#include<string>#include<string.h>usingnamespacestd;intten[10000],out[10000],tlen,olen;voidgeten(intin[],intlen,intm){inti,j;memset(ten,0,sizeof(ten));tlen=l;for(i=0;i<len;i++){if(i!=len-l){for(j=0;j<tlen;j++){if(j==0){ten[j]=(ten[j]+in[i])*m;)else(ten[j]=ten[j]*m;)))else(ten[0]+=in[i];)for(j=0;j<tlen;j++){if(ten[j]>=10){ten[j+l]=ten[j]/10+ten[j+1];ten[j]=ten[j]%10;if(j==tlen-l){tlen++;))))return;)voidgetnout(intn){intj=0JtempJa;memset(out,0,sizeof(out));olen=0;while(ten[j]!=0){temp=0;for(i=j;i<tlen;i++){if((ten[i]+temp*10)%n==0){ten[i]=(ten[i]+temp*10)/n;temp=0;if(i==tlen-l){out[olen++]=0;}}else(a=ten[i];ten[i]=(ten[i]+temp*10)/n;temp=(a+temp*10)%n;if(i==tlen-l){out[olen++]=temp;)))while(ten[j]==0&&j<tlen){j++；})return;)intmain(){intm,n,i,a,xn[10000];stringx;charzf;while(cin>>m>>n){x.clear();cin>>x]memset(xn,0,sizeof(xn));for(i=0;i<x.length();i++){if(x[i]>='0'&&x[i]<='9'){a=x[i]-'0';xn[i]=a;)elseif(x[i]>='A'&&x[i]<='Z,){a=x[i]-,A';xn[i]=a+10;))if(x.length()==l&&xn[0]==0){cout<<0<<endl;continue;)geten(xn,x,length(),m);for(i=0;i<tlen/2;i++){a=ten[i];ten[i]=ten[tlen-l-i];ten[tlen-l-i]=a;}getnout(n);for(i=0;i<olen;i++){if(out[olen-l-i]>9){zf=out[olen-l-i]-10+'a';cout<<zf;)else(cout<<out[olen-l-i];))cout<<endl;)return0;)JDOJ1446：#include<iostream>#include<algorithm>#include<vector>#include<string>usingnamespacestd;structData{stringname;intparent,time,people;voidInit(){name=parent=-1;time=0;people=1;)};vector<Data>Tree;intHandleName(strings){for(inti=0;i<Tree.size();i++){if(Tree[i].name==s)returni;)Datat;t.Init();=s;Tree.push_back(t);returnTree.size()-1;)intFindRoot(intx){if(Tree[x].parent==-1)returnx;else{inttmp=FindRoot(Tree[x].parent);Tree[x].parent=tmp;returntmp;))boolCmp(Dataa.Datab){<;)intmain(){intn,k;while(cin>>n>>k){Tree.clear();inti;for(i=0;i<n;i++){stringsi,s2;inta,b,c;cin>>si>>s2>>c;a=HandleName(sl);b=HandleName(s2);Tree[a].time+=c;Tree[b].time+=c;a=FindRoot(a);b=FindRoot(b);if(a!=b){Tree[a].parent=b;Tree[b].people+=Tree[a].people;)}vector<Data>Gang;for(i=0;i<Tree.size();i++){if(Tree[i].parent==-1&&Tree[i].people>2){intalltime=tmp=i;for(j=0;j<Tree.size。；j++){if(FindRoot(j)==i){

alltime+=Tree[j].time;if(Tree[j].time>Tree[tmp].time)tmp=j;})if(alltime>k*2){Datat;=Treeftmp].name;t.people=Tree[i].people;Gang.push_back(t);)))cout<<Gang.size()<<endl;sort(Gang?begin(),Gang,end(),Cmp);for(i=0;i<Gang.size();i++){cout<<Gang[i].name<<""<<Gang[i].people<<endl;))return0;)DDOD1024：#include<iostream>#include〈algorithm)usingnamespacestd;#defineMAX101structEdge(inta,b,cost;booloperator<(constEdge&A)const{ 〃重載小于returncost<A.cost;))；intTree[MAX];EdgeE[5100];intFindRoot(intx){if(Tree[x]==-1)returnx;else(inttmp=FindRoot(Tree[x]);Tree[x]=tmp;returntmp;))intmain(){intn,m;while(cin>>n>>m){if(n==0)break;inti,res=0;for(i=1;i<=m;i++)Tree[i]=-1;for(i=0;i<n;i++)cin>>E[i].a>>E[i].b>>E[i].cost;sort(E,E+n);for(i=0;i<n;i++){inta,b;a=FindRoot(E[i].a);b=FindRoot(E[i].b);if(a!=b){Tree[a]=b;res+=E[i].cost;)}intcount=0;for(i=1;i<=叫i++){〃檢查最小生成樹是否存在if(Tree[i]==-1)count++;)if(count>1)cout<<M?"<<endl;elsecout<<res<<endl;)return0;)JDOJ1100:#include<iostream>#include<math.h>#include<vector>usingnamespacestd;#defineMAX500structBiglnteger{intnum[MAX];intlen;voidInit(){for(inti=0;i<MAX;i++)num[i]=0;len=1;)booloperator<(constBiginteger&A)const(if(len!=A.len)returnlen<A.len;else(inti;boolt=true;;for(i=len-1;i>=0;i--){if(num[i]>A.num[i]){t=false;break;)elseif(num[i]<A.num[i])break;)if(i==-1)〃等于的情況t=false;returnt;)}}；structE( 〃鄰接表?邊表節(jié)點intnext;Bigintegerweight;}；structData{Bigintegerdis;boolmark;}；vector<E>edge[501];Datainfo[101];voidMultiply(Biginteger&a,intk){inti;while(k>0){for(i=0;i<a.len;i++){a.num[i]*=2;}k--;for(i=0;i<a.len;i++){if(a.num[i]>9){a.num[i+1]++;a.num[i]-=10;if(i==a.len-1)a.len++;)}BigintegerPlus(BigIntegera,Bigintegerb){inti;Bigintegert;t.Init();t.len=0;for(i=0;i<a.len||i<b.len;i++)t.num[t.len++]=a.num[i]+b.num[i];for(i=0;i<t.len;i++){if(t.num[i]>9){t.num[i]-=10;t.num[i+1]++;if(i+1==t.len)t.len++;})returnt;)intmain(){intn,m;while(cin>>n>>m){inti,j;for(i=0;i<n;i++){edge[i].clear();info[i].dis.Init();info[i].dis.num[0]=-1;info[i].mark=false;)for(i=0;i<m;i++){inta,b;cin>>a>>b;Etmp;tmp,weight.Init();tmp.weight.num[0]=1;Multiply(tmp.weight,i)；tmp.next=b;edge[a].push_back(tmp);tmp.next=a;edge[b].push_back(tmp);)info[0].dis.num[0]=0;info[0].mark=true;intnewP=0;for(i=1;i<n;i++){for(j=0;j<edge[newP].size();j++){intt;Bigintegerw;t=edge[newP][j].next;vj=edge[newP][j].weight;if(info[t].mark==true)continue;if(info[t].dis.num[0]==-1||Plus(info[newP].dis,w)<info[t].dis){info[t].dis=Plus(info[newP].dis,w);))Bigintegermin;min.Init();min.len=300;for(j=0;j<n;j++){if(info[j].mark)continue;if(info[j].dis.num[0]==-1)continue;if(info[j].dis<min){min=info[j].dis;newP=j;})info[newP].mark=true;)for(i=1;i<n;i++){intres=0;if(info[i].dis.num[0]==-1)res=-1;else(for(j=0;j<5;j++)〃相當于MOD100000res+=pow(10,j)*info[i].dis.num[j];)cout<<res<<endl;))return0;}JD0J1162：#include<iostream>#include<vector>usingnamespacestd;structE{〃鄰接表一邊表節(jié)點intnext;intweight;};structData{intdis;intcamp;boolmark;};vector<E>edge[10001];Datainfo[601];intmain(){intn;while(cin>>n&&n!=0){inti,j,m;cin>>m;intd[10001][3];for(i=0;i<m;i++)cin?d[i][0]?d[i][l]?d[i][2];for(i=1;i<=n;i++){edge[i].clear();info[i].dis=-1;info[i].mark=false;cin>>info[i].camp;)for(i=0;i<m;i++){Etmp;tmp.weight=d[i][2];inta=d[i][0],b=d[i][l];if(info[a].camp==1&&info[b].camp==2){tmp.next=b;edge[a].push_back(tmp);}elseif(info[a].camp==2&&info[b].camp==1){tmp.next=a;edge[b].push_back(tmp);)else(tmp.next=b;edge[a].push_back(tmp);tmp.next=a;edge[b].push_back(tmp);}}info[l].dis=0;info[l].mark=true;intnewP=1;for(i=1;i<n;i++){for(j=0;j<edge[newP].size();j++){intt,w;t=edge[newP][j].next;w=edge[newP][j].weight;if(info[t].mark==true)continue;if(info[t].dis==-1||info[newP].dis+w<info[t].dis){info[t].dis=info[newP].dis+w;}}intmin=5000001;for(j=1；j<=n;j++){

if(info[j].mark)

continue;if(info[j].dis==-1)continue;if(info[j].dis<min){min=info[j].dis;newP=j;))info[newP].mark=true;)cout<<info[2].dis<<endl;)return0;}DDOD1449：#include<iostream>#include<queue>#include<vector>#include<algorithm>usingnamespacestd;#defineMAX501vector<int>edge[MAX];intmain(){intDegree[MAX];intn,m;while(cin>>n>>m){inti;vector<int>Q;Q.clear();for(i=1;i<=n;i++){Degree[i]=0;edge[i].clear();)for(i=0;i<m;i++){inta,b;cin>>a>>b;Degree[b]++;edge[a].push_back(b);)for(i=1;i<=n;i++){if(Degree[i]==0)Q.push_back(i);)intres[MAX],size=0;while(!Q.empty()){sort(Q.begin(),Q.end());intt=Q[0]；res[size++]=t;Q.erase(Q.begin());for(i=0;i<edge[t].size();i++){Degree[edge[t][i]]--；if(Degree[edge[t][i]]==0)Q.push_back(edge[t][i]);}}for(i=0;i<size;i++){if(i==size-1)cout<<res[i]<<endl]elsecout<<res[i]<<"))return0;)JDOJ1450：#include<iostream>#include<string>#include<map>usingnamespacestd;map<stringJint>name;intmain(){intn;while(cin>>n&&n!=0){inti,len=0,ent=0,Degree[2003];name.clear();for(i=0;i<n*2;i++)Degree[i]=0;while(n--){stringa,b;cin>>a>>b;if(name.find(a)==name.end())name[a]=len++;if(name.find(b)==name.end())name[b]=len++;Degree[name[b]]++;)for(i=0;i<len;i++){if(Degree[i]==0)cnt++;}if(ent==1)cout<<"Yes"<<endl;elsecout<<"No"<<endl;)return0;)JDOJ1457：#include<iostream>#include<queue>usingnamespacestd;boolmark[101][101][101]]〃是否搜索過structNode(inta,b,c,t;};queue<Node>Q;voidMove(int&a,intsa,int&b,intsb){if(sb-b>=a){b+=a;a=0;}else(a=a-(sb-b);b=sb;})intBFS(ints,intn,intm){while(!Q.empty()){Nodenow=Q.front。；Q?pop();for(inti=1;i<=6;i++){inta,b,c;a=now.a;b=now.b;c=now.c;if(i==1)Move(as,b,n);if(i==2)Move(b,n,a,s);if(i==3)Move(a,s,c,m);if(i==4)Move(c)m,日)s);if(i==5)Move(b,n,c,m);if(i==6)Move(c,b,n);if(!mark[a][b][c]){mark[a][b][c]=true;Nodet;t.a=a;t.b=b;t.c=c;t.t=now.t+1;if(a==s/2&&b==s/2)returnt.t;if(a==s/2&&c==s/2)returnt.t;if(b==s/2&&c==s/2)returnt.t;Q.push(t);)}return-1;)intmain(){ints,n,m;while(cin>>s>>n>>m){if(s==0)break;if(s%2==1){cout<<"NO"<<endl;continue;)inti,j,k;for(i=0;i<=s;i++){for(j=0；j<=n;j++){for(k=0;k<=m;k++)mark[i][j][k]=false;))while(!Q.empty())Q-pop();mark[s][0][0]=true;Nodestart;start.a=s;start.b=start.c=start.t=0;Q.push(start);intres=BFS(s,n,m);if(res!=-l)cout<<res<<endl;elsecout<<"NO"<<endl;)return0;}3DOJ1459:#include<iostream>#include<cstdio>#include<math.h>usingnamespacestd;intans[22];boolmark[22];intn;boolIsPrime(intx){inti,a=sqrt(x)+1;for(i=2;i<a;i++){if(x%i==0)returnfalse;)returntrue;)voidCheck(){if(!IsPrime(ans[n]+ans[l]))return;for(inti=1;i<n;i++)printf(*'%d二ans[i]);printf("%d\n",ans[n]);}voidDFS(intnum){if(num>1){if(!IsPrime(ans[num]+ans[num-1]))return;)if(num==n){Check();return;)for(inti=2;i<=n;i++){if(!mark[i]){mark[i]=true;ansfnum+1]=i;DFS(num+1);mark[i]=false;}})intmain(){intcas=0;while(cin>>n){cas++;for(inti=0;i<22;i++)mark[i]=false;ans[l]=1;printf("Case%d:\n",cas);mark[l]=true;DFS(l);printf(M\nM);)return0;)JDOJ1120:#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;intmain(){charn[7];while(scanf("%s",&n)!=EOF){inta=strlen(n);do{printf("%s\n",n);}while(next__permutation(n>n+a));printf("\n");)return0;}JDOJ1091：#include<iostream>usingnamespacestd;structCoordinate{intx,y;intcost,state;}；intmatric[7][7];boolmark[7][7];intres;Coordinatest,ed;voidDFS(Coordinatet){if(t.cost>res)〃剪枝return;if(t.x==ed.x&&t.y==ed.y){res=t.cost;return;)Coordinatetmp;for(inti=0;i<4;i++){tmp=t;if(i==0){tmp.x--;if(tmp.x<0||mark[tmp.x][tmp.y])continue;)elseif(i==1){tmp.x++;if(tmp.x>5||mark[tmp.x][tmp.y])continue;)elseif(i==2){tmp.y--;if(tmp.y<0||mark[tmp.x][tmp.y])continue;)elseif(i==3){tmp.y++;if(tmp.y>5||mark[tmp.x][tmp.y])continue;)mark[tmp.x][tmp.y]=true;intonecost=matric[tmp.x][tmp.y]*t.state;tmp.cost=t.cost+onecost;tmp.state=onecost%4+1;DFS(tmp);mark[tmp.x][tmp.y]=false;))intmain(){intn;cin>>n;while(n--){res=0x7fffffff;inti,j;for(i=0;i<6;i++){for(j=0;j<6;j++){cin>>matricfi][j];mark[i][j]=false;))cin>>st.x>>st.y>>ed.x>>ed.y;st.cost=0;st.state=1;//mark[st.x][st.y]=true;此題非常特殊，會繞回起點，所以不能標記起點DFS(st);cout<<res<<endl;)return0;)JDO31131:#include<iostream>#include<cstdio>usingnamespacestd;#defineMAX101intmax(inta,intb){returna>b?a:b;)intmain(){intn;while(cin>>n){inti.j,input[MAX],tmp,res=1;intIncrease[MAX],OpIncrease[MAX];for(i=1;i<=n;i++)scanf("%d"，&input[i]);for(i=1;i<=n;i++){tmp=1;for(j=1;j<i;j++){if(input[j]<input[i])tmp=max(tmp,Increase[j]+1);)Increase[i]=tmp;)for(i=n;i>=1;i--){tmp=1;for(j=n;j>i;j--){if(input[j]<input[i])tmp=max(tmp,Oplncrease[j]+1);)Oplncrease[i]=tmp;)for(i=1;i<=n;i++)res=max(res,Increase[i]+Oplncrease[i]-1);res=n-res;cout<<res<<endl;)return0;)3DOJ1111:#include<iostream>#include<string>#include<cstdio>usingnamespacestd;intmain(){charstr[101];while(gets(str)){strings,a,b,c="s=str;gets(str);a=str;gets(str);b=str;intt=s.find(a,0);boolflag=true;while(t!=string::npos){if(t==0){if(s.size()>a.size()&&s[t+a.size()]!='')flag=false;)else(if(s[t-1]!='')flag=false;else(if(t+a.size()<s.size()&&s[t+a.size()]!=*')flag=false;))c+=s.substr(0,t);if(flag)c+=b;elsec+=a;s=s.substr(t+a.size());t=s.find(a,0);flag=true;)c+=s;cout<<c<<endl;)return0;)DDOJ1186:#include<iostream>#include<stdio.h>usingnamespacestd;structDatelnfo(inty,m,d;};intdayofMonth[13][2]={0,0,31,31,28,29,31,31,30,30,31,31,30,30,31,31,31,31,30,30,31,31,30,30,31,31,}；Dateinfogetmd(inty3intn){Dateinfot;t.y=y;boolisleap=false;if((y%4==0&&y%100!=0)||(y%400==0))isleap=true;intm=1^d=n;while(d>dayofMonth[m][isleap]){d-=dayofMonth[m][isleap];m++;)t.m=m;t.d=d;returnt;)intmain(){intv>n;while(cin>>y>>n){Dateinfores=getmd(y)n);printf("%04d-%02d-%02d\n"res.y,res.m^res.d);}return0;JDOJ1081:#include<iostream>usingnamespacestd;#defineMOD10000intmain(){inta0,al,p,q,k,tempi,l,m;while(cin>>a0>>al>>p>>q>>k){a0=a0%MOD;al=al%MOD;if(k==0){cout<<a0<<endl;continue;)if(k==l){cout<<al<<endl;continue;)k--；1=1；m=0;while(k>l){if(k%2==0){k=k/2;inta=pJb=q>c=lJd=m;p=(a*a+b*c)%MOD;q=(a*b+b*d)%MOD;l=(c*a+d*c)%MOD;m=(c*b+d*d)%MOD;)else(k-Stempl=al;al=(p*al+q*a0)%MOD;a0=(l*temp：l+m*a0)%MOD;))templ=p*al+q*a0;cout<<templ%MOD<<endl;))JDOJ1072：#include<iostream>usingnamespacestd;intnum=0;intarray[15]={8,8,8,8,8,10,10,10,10,18,18,18,18,18,18};intqueue[15];intacc,res[1000];intlength=0;boolflag;voidcomb(ints,intn,intm){inti;if(s>n)return;if(num==m){acc=0;for(i=0;i<m;i++){acc=acc+queue[i];)flag=true;for(i=0;i<length;i++){if(acc==res[i]){flag=false;break;))if(flag==true){res[length++]=acc;)return;)queue[num++]=array[s];comb(s+1,n,m);num--;comb(s+1,n,m);)intmain(){inti;for(i=1;i<=15;i++){comb(0j15,i);)cout<<length<<endl;return0;)JDO：)1103(二次方程計算器)：#include<iostream>#include<string>#include<stdio.h>#include<math.h>usingnamespacestd;structData(inta,b,c;};intmain(){stringn;while(cin>>n){inti=0,a,len=n.length();Dataxs;boold=false,f=false;xs.a=0;xs.b=0;xs.c=0;while(i<len){if(n[i]>='0'&&n[i]<='9'){a=i;while(n[i]>=*0,&&n[i]<='91){i++；}charp[10]={0};intj,b=0;for(j=a;j<i;j++){P[b++]=n[j];)sscanf(p,"%d",&b);if(i==len){if(f)xs.c+=b;elsexs.c-=b;break;)if(n[i]=='x'){if(i+1<len&&n[i+1]==，A*){if(i+2<len&&n[i+2]=='2'){if((d&&f)||(!d&&!f))xs.a+=b;if((d&&!f)||(!d&&f))

xs.a-=b;f=false;)i+=3;)else{if((d&&f)||(!d&&!f))

xs.b+=b;if((d&&!f)||(!d&&f))

xs.b-=b;f=false;i++；))else{if((d&&f)||(!d&&!f))xs.c+=b;if((d&&!f)||(!d&&f))xs.c-=b;f=false;)}elseif(n[i]=='x'){if(i+1<len&&n[i+1]==，A，){if(i+2<len&&n[i+2]=='2'){if(f)xs.a--;elsexs.a++;f=false;}i+=3;)else(if(f)xs.b--;elsexs.b++;f=false;i++；})elseif(n[i]=='=1){d=true;i++;)elseif(n[i]==*-'){f=true;i++；}elseif(n[i]=='+'){i++；}}doubletemp=xs.b*xs.b-4*xs.a*xs.c;if(temp<0){cout<<"NoSolution"<<endl;)else{doubleal,a2;temp=sqrt(temp);al=0.5*(-temp-xs.b)/(double)xs.a;a2=0.5*(temp-xs.b)/(double)xs.a;printf("%.2f%.2f\n'\ a2);)n.clear();}return0;)QCOJA1117(解方程式)：#include<iostream>usingnamespacestd;structData{intmula;intmulsc2;}；structStation(Datasc;Datakc;};intmain(){intajn,m,z;while(cin>>a>>n>>m>>z){if(z==1||z==2){cout<<a<<endl;continue;)Stationst[21];inti,sc2;for(i=1;i<n;i++){if(i==1){st[i].sc.mula=1;st[i].sc.mulsc2=0;continue;)if(i==2){st[i].sc.mula=0;st[i].sc.mulsc2=1;st[i].kc.mula=1;st[i].kc.mulsc2=0;continue;)st[i].sc.mula=st[i-1].sc.mula+st[i-2].sc.mula;st[i].sc.mulsc2=st[i-1].sc.mulsc2+st[i-2].sc.mulsc2;st[i].kc.mula=st[i-1].kc.mula+st[i-2].sc.mula;st[i].kc.mulsc2=st[i-1].kc.mulsc2+st[i-2].sc.mulsc2;}sc2=(m-st[n-1].kc.mula*a)/st[n-1].kc.mulsc2;cout<<st[z].kc.mula*a+st[z].kc.mulsc2*sc2<<endl;)return0;)JDOJ1348：#include<iostream>usingnamespacestd;longlongres;#defineMAX100001voidMerge(intA[],intlow,intmid,inthigh){inttmp[MAX],i,j?k;i=k=low;j=mid+1;while(i<=mid&&j<=high){if(A[i]>A[j]){tmp[k++]=A[i++];res+=(high-j+1);)elsetmp[k++]=A[j++];)while(i<=mid)tmp[k++]=A[i++];while(j<=high)tmp[k++]=A[j++];while(low<=high)A[low]=tmp[low++];)voidMergeSort(intA[],intlow,inthigh){if(low<high){intmid=(low+high)/2;MergeSort(A^low,mid);MergeSort(A,mid+1,high);Merge(A,low,mid,high);))intmain(){intn;while(cin>>n){inti,input[MAX];for(i=0;i<n;i++)cin>>input[i];res=0;MergeSort(input,0,n-1);cout<<res<<endl;)return0;)JDOJ1113(完全二叉樹)：#include<iostream>#include<math.h>usingnamespacestd;intmain(){intm,n;while(cin>>m>>n){if(m==0)return0;inth=0,a=m,res=0;while(a<=n){res+=pow(2,h);a=a*2+1;h++;)a=a-pow(2,h)+1;if(n>=a)res=res+n-a+1;cout<<res<<endl;)return0;

14678910121416182123242526272829313335363738394041434547485052545657586061626365排列組合:#include<stdio.h>chararray[]="abed";#defineN4#defineM3intqueue[N]={0};inttop=0;intflag[N]={0};voidperm(ints,intn){inti;if(s>n)return;if(s==n){for(i=0;i<n;i++){printf("%c"^queue[i]);)printf("\t");return;}for(i=0;i<n;i++){if(flag[i]==0){flag[i]=1;queue[s]=array[i];permCs+l,n);flag[i]=)}}voidcomb(ints,intn,intm){inti;if(s>n)return;if(top==m){for(i=0;i<m;i++)printf("%c",queue[i]);printf("\t");return;)queue[top++]=array[s];comb(s+l,n,m);top--;comb(s+l,n