摘要: WA了N多次,猛然發(fā)現(xiàn)一處少寫一符號,總算A掉了.這種題目就是要細心細心再細心.
#include <iostream>#include<cstring>#include<cmath>using namespace std;int main(){ char str[...
閱讀全文
摘要: 兩個都是麻煩的計數(shù)問題,只不過一個是二進制,另一個似乎更貼近十進制的現(xiàn)實世界.不過計算機里,還是二進制感覺能跑得更快一些,移位總比乘十來得更快一些.計數(shù)從0-n的每一位的數(shù)字個數(shù),先計數(shù)位數(shù)小于n的位數(shù)的數(shù)字個數(shù),再從高位到低位依次循環(huán)累加計數(shù)和n位數(shù)相同且小于n的數(shù)的各位數(shù)字.考慮的情形很多,有一點考慮不到就很難得到正確答案.
/**//*Source CodeProblem:&nb...
閱讀全文
摘要: 給定有理數(shù)P/Q，求它的二進制小數(shù)的循環(huán)節(jié)長度。先把這個分數(shù)化為既約分數(shù)，則循環(huán)節(jié)開始的位置M是使?jié)M足2^M | Q的最大M。令Q1=Q/2^M,則循環(huán)節(jié)的長度就是求最小的N使2^N模Q1為1。這個問題好像沒有有效的解法（關于Q1的位數(shù)為多項式級別）。由于2和Q1互素，可以用歐拉定理來解。即2^phi（Q1）對Q1同余1。所求的N一定是phi（Q1）的一個因子，先分解Q1，再分解phi（Q1），遞...
閱讀全文
http://acm.pku.edu.cn/JudgeOnline/problem?id=2085 給定整數(shù)N，和一個序列的逆序數(shù)M，求以1，2...N為元素，逆序為M，且按字典序最小的那個序列。
只要知道這樣一個事實：一個序列的逆序唯一決定了這個序列。
例如：序列1，4，3，2的逆序為1--0，2--2，3--1，4--0，可以用一個四維坐標來表示（0，2，1，0），第i維的數(shù)是 i 在原序列中的逆序數(shù)，取值范圍是0，1...4-i。
為解決這個問題，以N=4,逆序數(shù)M=5為例。
對這個問題可以采取貪心策略。
首先，如果所求序列以1為首，則1的逆序為0，可以從上表看出此時序列的逆序數(shù)最多為2+1=3<5，不滿足。考慮以2為首，序列的逆序最多為3+1<5，不滿足。
考慮以3為首，可見當1的逆序為3，2的逆序為2，4的逆序為0時滿足要求，這時1，2，4均為最大逆序，因而只能排列為4，2，1，加上首數(shù)，所求序列為3，4，2，1。
若M=3，采取同樣的貪心策略，可求得結果為1，4，3，2。
依此思路，可以得到所求序列關于N，M的關系式，具體如下：
1，2，3，...N-P, N-((p-1)*p/2-M), N , N-1...N-P+1.(P是滿足（P-1）*P/2>=M的最小值)。
代碼就容易多了。
關于更多排列的內(nèi)容可參考：
/Files/sdz/s.doc
#include <stdio.h>
int main(int argc, char *argv[])
{
int n,m;
int p,temp,i;
while(scanf("%d%d",&n,&m) && n>0)
{
p=1;
while((p*(p-1))/2<m)p++;
temp=(p*(p-1))/2;
for(i=1;i<=n-p;i++)
printf("%d ",i);
printf("%d ",n-temp+m);
for(i=n;i>=n-p+1;i--)
{
if(i!=n-temp+m)
printf("%d ",i);
}
printf("\n");
}
return 0;
}
//Bridging signals 1631 最長上升子序列 dp問題 2010.8.13
#include <iostream>
using namespace std;
const int MAXP=40005;
int L[MAXP];
int bSearch(int left,int right,int num)
{
if(right==left)
return left;
int mid=(left+right)/2;
if(num==L[mid])
return mid;
else if(num>L[mid])
{
if(right<mid+1)
return mid;
else
return bSearch(mid+1,right,num);
}
else if(num<L[mid])
{
if(left>mid-1)
return mid;
else
return bSearch(left,mid,num);
}
else return mid;
}
int solve(int n)
{
int ans=0;
int temp=0;
int count=0;
scanf("%d",&temp);
L[ans++]=temp;
n--;
while(n--)
{
scanf("%d",&temp);
if(temp>L[ans-1])
L[ans++]=temp;
else
L[bSearch(0,ans-1,temp)]=temp;
}
return ans;
}
int main(int argc, char *argv[])
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
cout<<solve(n)<<endl;
}
return 0;
}
以前從沒有對O（log N）和O（N）的區(qū)別有所正確認識，今日總算知道了。它們的唯一區(qū)別就是，N是一億的時候，log(N)就是不到26，N還是一億。
http://acm.pku.edu.cn/JudgeOnline/problem?id=3070
PKU的這道題雖然容易，但的確很有意思。我也是第一次用快速冪取模，一用，果然不同凡響。
快速冪取模，其實就是秦九韶算法 取指數(shù)。
把n化成二進制形式后，得到一個多項式,寫成秦九韶形式，多項式的加就是乘，乘則為指數(shù)運算（指數(shù)為2）。由于N的二進制位個數(shù)為log(n),這樣把O（N）的問題化為O（log N）。
.
//PKU 3070 ,calculate Fibonacci
#include <iostream>
#include<stack>
int FPM(int);//fast-power-modulus function declare
using namespace std;
const int Mod=10000;
int main(int argc, char *argv[])
{
int n=0;
while(scanf("%d",&n))
{
if(n==-1)
break;
printf("%d\n",FPM(n));
}
return 0;
}
int FPM(int n)//fast-power-modulus function
{
int matr[4]={1,0,0,1};//initialize matrix
stack<bool>dec;//stack to store binary digit
while(n)//resolve n to binary digit
{
dec.push(1&n);//get the last binary digit
n>>=1;
}
while(!dec.empty())
{
//matrix square
matr[1]=((matr[0]+matr[3])*matr[1])%Mod;
matr[0]=(matr[0]*matr[0]+matr[2]*matr[2])%Mod;
matr[3]=(matr[3]*matr[3]+matr[2]*matr[2])%Mod;
matr[2]=matr[1];
//matrix multiply,
if(dec.top())
{
matr[0]=(matr[0]+matr[1])%Mod;
matr[1]=(matr[1]+matr[3])%Mod;
matr[3]=matr[2];
matr[2]=matr[1];
}
dec.pop();
}
return matr[1];//matr[1] is the result F[N]
}