給出一棵二分搜索樹(shù)，再給一個(gè)節(jié)點(diǎn)編號(hào)n，求以這個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹(shù)葉子節(jié)點(diǎn)的最大值與最小值。若n是奇數(shù)，那么他必然是個(gè)葉子節(jié)點(diǎn)，最大最小都是他自己。否則求n所在的層數(shù)，他的層數(shù)就是他的因子中2的個(gè)數(shù)（規(guī)律），轉(zhuǎn)化為求n的因子中2的個(gè)數(shù)。而2的個(gè)數(shù)取決于n的二進(jìn)制表示中最后一個(gè)1所處的位置i，因?yàn)橹暗哪硯讉€(gè)1，假設(shè)處于j（j>i）,那么n可以表示為2^j+2^i+2^x(x>i且個(gè)數(shù)未定)=2^i*(1+2^(j-i)+2^(x-i)),看見(jiàn)米有，n必須有i個(gè)因子2.求出i的值后，即層數(shù)，可得n的左右各有num=2^i-1個(gè)兒孫（女），不信請(qǐng)看圖，概不解釋。那么最小值就是n-num,最大值就是n+num.那馬怎么求num呢，這時(shí)就可以請(qǐng)出神奇的位運(yùn)算了（以速度"嗖嗖嗖"的快而揚(yáng)名ACM界），首先是確定二進(jìn)制n后綴連續(xù)0的個(gè)數(shù)，這樣想：怎么取出這i個(gè)0呢？其實(shí)不必考慮這個(gè)掣肘的問(wèn)題，咱們直接跑到結(jié)果上考慮，就是求2^i-1,你花仙米有，這是個(gè)等差數(shù)列的前n項(xiàng)和：2^0+2^1+2^2+……+2^(i-1).那么這又是個(gè)什么形式呢，這就是二進(jìn)制只有連續(xù)i個(gè)1的（其余都是前導(dǎo)0）數(shù)的十進(jìn)制表示形式，OK，好辦了，利用系統(tǒng)自動(dòng)轉(zhuǎn)換功能，咱們只需把這i個(gè)1羅列出來(lái)即可：把n的后i個(gè)0變成1，可采取如下形式n^(n|n-1),稍微解釋下，n|n-1是將后i個(gè)0變成1，把第i+1個(gè)1變成0，然后和n抑或一下，得到什么？哈，就是2^i-1,即i個(gè)1的十進(jìn)制形式,代碼就不放了，上面明白了實(shí)現(xiàn)很簡(jiǎn)單的！
那啥，轉(zhuǎn)載務(wù)必注明：Pzjay原創(chuàng)呃！
本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/shifuwawa/archive/2010/01/07/5153446.aspx
以下是我根據(jù)上面的描述寫(xiě)出來(lái)的代碼，一次AC，0MS
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
int k;
cin>>k;
if(k%2!=0)
{
cout<<k<<" "<<k<<endl;
continue;
}
int num=k^(k|k-1);
cout<<k-num<<" "<<k+num<<endl;
}
return 0;
}
不得不說(shuō)poj 2305是一道進(jìn)制轉(zhuǎn)換的經(jīng)典題目。一開(kāi)始我沒(méi)有考慮到整除的情況。所以總是WA。后來(lái)加了一個(gè)判斷就AC了。
#include<iostream>
#include<cstring>
using namespace std;
char s1[1005],s2[15];
int main()
{
int n;
while(cin>>n&&n)
{
cin>>s1>>s2;
__int64 a=0,b=0;int len1,len2;
len1=strlen(s1);len2=strlen(s2);
for(int i=0;i<len2;i++)
{
a*=n;
a+=s2[i]-'0';
}
for(int j=0;j<len1;j++)
{
b*=n;
b+=s1[j]-'0';
if(b>=a)
b%=a;
}
int k=0;
if(b==0)
{
cout<<"0"<<endl;
continue;
}
while(b!=0)
{
s2[k++]=b%n+'0';
b/=n;
}
s2[k]='\0';
int len=strlen(s2);
for(k=len-1;k>=0;k--)
cout<<s2[k];
cout<<endl;
}
return 0;
}
這應(yīng)該是一道DP題。下面的代碼是我見(jiàn)過(guò)的最短的代碼。拿出來(lái)跟大家分享。
#include<iostream>
#include<stdio.h>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
int arrival[1450];
int trip[1450];
int time[1450];
int n,t,m;
int main()
{
int test;
cin>>test;
while(test--)
{
cin>>n>>t>>m;
for(int i=1;i<=m;i++)
scanf("%d",arrival+i);
trip[0]=time[0]=0;
for(int j=1;j<=m;j++)
{
time[j]=max(time[max(j-n,0)],arrival[j])+2*t;
trip[j]=trip[max(j-n,0)]+1;
}
printf("%d %d\n",time[m]-t,trip[m]);
}
return 0;
}
然后是該作者的介紹
題目大意：有一些汽車(chē)在左岸，你要用一條小破船把它們拉到右岸去。每個(gè)測(cè)試點(diǎn)包含多個(gè)測(cè)試數(shù)據(jù)。第一行的整數(shù)C表示測(cè)試數(shù)據(jù)的數(shù)目。接下來(lái)每個(gè)測(cè)試數(shù)據(jù)的第一行為三個(gè)整數(shù)N, T, M表示一次可以運(yùn)送N輛汽車(chē)，到達(dá)對(duì)岸的時(shí)間為T(mén)，汽車(chē)的總數(shù)是M。接下來(lái)的M行每行有一個(gè)整數(shù)，表示這輛汽車(chē)什么時(shí)候會(huì)來(lái)到左岸。對(duì)于每個(gè)測(cè)試數(shù)據(jù)，輸出兩個(gè)整數(shù)，分別是最少要耗用多少時(shí)間（包括你等車(chē)的時(shí)間，就是從0開(kāi)始直到最后一輛車(chē)到達(dá)右岸），以及在這個(gè)前提下你最少要運(yùn)送多少次。只要到右岸去就算作一次。
這個(gè)題出在DP專(zhuān)場(chǎng)不太合適……事實(shí)上本人用貪心的手段就解決了這個(gè)問(wèn)題。
貪心策略：先運(yùn)送M % N輛汽車(chē)到對(duì)岸（就是M除上N的余數(shù)），之后每次運(yùn)N輛汽車(chē)，直到運(yùn)完為止。這里的意思是，只有船上確實(shí)有了這么多車(chē)才出發(fā)，在此之前等著那些車(chē)來(lái)。對(duì)于這個(gè)策略的證明各位可以使用數(shù)學(xué)歸納法，比較簡(jiǎn)單，這里就不耗費(fèi)篇幅了。
DFS題目啊?？赐ㄟ^(guò)率就知道非常簡(jiǎn)單的。一下付代碼，大家自己看下。
#include<iostream>
using namespace std;
char array[100][100];
int n,m;int count=0;
void dfs(int i,int j)
{
if(i<0||i>n||j<0||j>m)
return ;
if(array[i][j]!='W')
return ;
array[i][j]='.';
dfs(i-1,j);dfs(i+1,j);dfs(i,j-1);dfs(i,j+1);dfs(i-1,j-1);dfs(i-1,j+1);dfs(i+1,j-1);dfs(i+1,j+1);
}
void check()
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(array[i][j]=='W')
{
dfs(i,j);
count++;
}
}
}
}
int main()
{
cin>>n>>m;
for( int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>array[i][j];
}
}
check();
cout<<count<<endl;
return 0;
}
這道題目視枚舉題。直接枚舉各個(gè)長(zhǎng)度，然后求最小面積即可。
#include<iostream>
using namespace std;
int main()
{
int test;
cin>>test;
while(test--)
{
int n;
cin>>n;
int min=100000000;
int area;
int k;
for(int i=1;i<=n;i++)
{
for(int j=1;i*j<=n;j++)
{
if(n%(i*j)==0)
{
k=n/(i*j);
area=i*j+i*k+j*k;
if(area<min)
min=area;
}
}
}
cout<<min*2<<endl;
}
return 0;
}
這是一道模擬題。說(shuō)白了就是石頭剪子布的問(wèn)題。此題的關(guān)鍵點(diǎn)是要開(kāi)兩個(gè)數(shù)組。一個(gè)是原來(lái)的。一個(gè)是改動(dòng)后的，每次改動(dòng)完之后都要用改動(dòng)之后的初始化原來(lái)的一次。下面請(qǐng)看代碼。我把函數(shù)分的比較詳細(xì)。便于大家閱讀。
#include<iostream>
using namespace std;
char array[102][102];
char temp[102][102];
int r,c,n;
void init()
{
int i,j;
for( i=1;i<=r;i++)
{
for( j=1;j<=c;j++)
{
array[i][j]=temp[i][j];
}
}
}
void change(int i,int j)
{
if(array[i][j]=='R')
{
if(i>1&&array[i-1][j]=='S')
temp[i-1][j]='R';
if(i+1<=r&&array[i+1][j]=='S')
temp[i+1][j]='R';
if(j>1&&array[i][j-1]=='S')
temp[i][j-1]='R';
if(j+1<=c&&array[i][j+1]=='S')
temp[i][j+1]='R';
}
else
if(array[i][j]=='P')
{
if(i>1&&array[i-1][j]=='R')
temp[i-1][j]='P';
if(i+1<=r&&array[i+1][j]=='R')
temp[i+1][j]='P';
if(j>1&&array[i][j-1]=='R')
temp[i][j-1]='P';
if(j+1<=c&&array[i][j+1]=='R')
temp[i][j+1]='P';
}
else
if(array[i][j]=='S')
{
if(i>1&&array[i-1][j]=='P')
temp[i-1][j]='S';
if(i+1<=r&&array[i+1][j]=='P')
temp[i+1][j]='S';
if(j>1&&array[i][j-1]=='P')
temp[i][j-1]='S';
if(j+1<=c&&array[i][j+1]=='P')
temp[i][j+1]='S';
}
}
void occupy()
{
int i,j;
while(n--)
{
for(i=1;i<=r;i++)
{
for(j=1;j<=c;j++)
{
change(i,j);
}
}
init();
}
}
int main()
{
int test;
cin>>test;
int i,j;
while(test--)
{
cin>>r>>c>>n;
for( i=1;i<=r;i++)
{
for( j=1;j<=c;j++)
{
cin>>array[i][j];
temp[i][j]=array[i][j];
}
}
/////////////OK 輸入字符完畢。
occupy();
for( i=1;i<=r;i++)
{
for( j=1;j<=c;j++)
{
cout<<array[i][j];
}
cout<<endl;
}
if(test!=0)
cout<<endl;
}
return 0;
}
這個(gè)題首先要把輸入的坐標(biāo)轉(zhuǎn)化成鄰接矩陣的形式。之后再利用鄰接矩陣使用普里姆算法計(jì)算最小生成樹(shù)。并對(duì)其中的邊進(jìn)行排序。找出減去S個(gè)較大的后最大的那一個(gè)。因?yàn)檩^大的那幾個(gè)可以用衛(wèi)星傳輸
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stdio.h>
using namespace std;
typedef struct
{
double x;
double y;
}point;
point array[505];
double len[505][505];
double kk[505],next[505];
double re[505];
int sa,num;
double dis(point first,point second)
{
return sqrt((first.x-second.x)*(first.x-second.x)+(first.y-second.y)*(first.y-second.y));
}
void prim(int n)
{
int i,j;
//////////讀入數(shù)據(jù)完畢。開(kāi)始構(gòu)建鄰接矩陣
for(i=0;i<num;i++)
{
for(j=0;j<num;j++)
{
len[i][j]=15000000;
}
}
for(i=0;i<num;i++)
{
for(j=0;j<num;j++)
{
if(i!=j)
len[i][j]=dis(array[i],array[j]);
}
}
for(i=0;i<num;i++)
{
kk[i]=len[0][i];
next[i]=0;
}
/////////鄰接矩陣構(gòu)建完畢
int count=0;i=0;
while(count<num-1)
{
if(next[i]!=-1)
{
for(j=0;j<num;j++)
{
if(i!=j&&next[j]!=-1)
{
if(len[i][j]<kk[j])
{
kk[j]=len[i][j];
next[j]=i;
}
}
}
next[i]=-1;
double max=999999999;int k;
for(j=0;j<num;j++)
{
if(kk[j]<max&&next[j]!=-1)
{
k=j;
max=kk[j];
}
}
re[count]=max;
i=k;
count++;
}
}
}
int main()
{
int n;
cin>>n;
int i;
while(n--)
{
cin>>sa>>num;
for( i=0;i<num;i++)
{
scanf("%lf%lf",&array[i].x,&array[i].y);
}
prim(0);
sort(re,re+num-1);
printf("%.2f\n",re[num-1-sa]);
}
return 0;
}
pku2126 poj2126
題目大意：
給定多項(xiàng)式的系數(shù)，問(wèn)這個(gè)多項(xiàng)式能不能分解!
如果能輸出NO 否則輸出YES
實(shí)系數(shù)多項(xiàng)式分解定理：
當(dāng)n<2的時(shí)候不能分解輸出YES
當(dāng)n==2的時(shí)候如果有實(shí)數(shù)根就能分解輸出NO 否則不能分解輸出YES
當(dāng)n>2的時(shí)候一定能分解，那么輸出NO
#include<iostream>
using namespace std;
int array[25];
bool root(int a,int b,int c)
{
if(b*b>=4*a*c)
return true;
else
return false;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<=n;i++)
{
cin>>array[i];
}
if(n<=1)
cout<<"YES"<<endl;
else
if(n==2)
{
if(root(array[0],array[1],array[2]))
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
else
cout<<"NO"<<endl;
return 0;
}
3096暴力求解，0M通過(guò)
#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
char str[85];
char first[3],second[3];
int main()
{
first[2]='\0',second[2]='\0';
while(gets(str))
{
bool flag=true;
if(str[0]=='*')
break;
int len=strlen(str);
for(int i=0;i<len;i++)
{//從第幾個(gè)開(kāi)始找起
for(int j=1;j<(len-1)&&i+j<len;j++)
{////////這個(gè)是間隔
first[0]=str[i];first[1]=str[j+i];
for(int k=i+1;k<len&&k+j<len;k++)
{
second[0]=str[k];second[1]=str[k+j];
if(strcmp(first,second)==0)
flag=false;
}
}
}
if(flag)
cout<<str<<" is surprising."<<endl;
else
cout<<str<<" is NOT surprising."<<endl;
}
return 0;
}
這個(gè)題就是用一個(gè)遞歸轉(zhuǎn)化數(shù)字。10以下的不用轉(zhuǎn)換。
#include<iostream>
using namespace std;
int k;
int ff(int a)
{
int sum=1;
for(int i=0;i<a;i++)
sum*=10;
return sum;
}
void convert(int a)
{
if(k/ff(a)==0)
return ;
else
{
if(k%ff(a)>=ff(a)/2)
k=k/ff(a)+1;
else
k=k/ff(a);
k*=ff(a);
convert(a+1);
}
}
int main()
{
int n;
cin>>n;
while(n--)
{
cin>>k;
if(k<10)
{
cout<<k<<endl;
continue;
}
convert(1);
cout<<k<<endl;
}
return 0;
}