int myatoi(char *str)
{
int ret=0;
int sign=1;
if(*str=='-')
sign=-1;
else
ret=ret*10+(*str-'0');
str++;
while(*str!= '\0')
{
ret=ret*10+(*str-'0');
str++;
}
return sign*ret;
}
高精度計算是NOIP中常考常用的算法之一，某天我閑的DT，寫了個代碼極其冗長的高精度加法函數，方便大家直接調用。
#include <iostream>
#include <string>
using namespace std;
char result[100];
void Highj(char a[],char b[])
{
int x[100],y[100];
int i,l,la,lb;
char temp[100];
for (i=0;i<99;i++){x[i]=0;y[i]=0;} //初始化
la=strlen(a);
lb=strlen(b);
//把char型數組 按正倒序 變成整型數組
if (la<=lb)
{
for (i=la-1;i>=0;i--)
y[i]=a[la-1-i]-'0';
for (i=lb-1;i>=0;i--)
x[i]=b[lb-1-i]-'0';
l=la;
}
else
{
for (i=la-1;i>=0;i--)
x[i]=a[la-1-i]-'0';
for (i=lb-1;i>=0;i--)
y[i]=b[lb-1-i]-'0';
l=lb;
}
//執行加法運算
for (i=0;i<l;i++)
{
x[i]=x[i]+y[i];
if (x[i]>=10)
{
x[i]-=10;
x[i+1]+=1;
}
}
//再把整型數組按照倒序轉換成char型數組
for (i=99;i>=0;i--)
temp[99-i]=x[i]+'0';
//從不是0的一位開始輸出結果
for (i=0;i<=99;i++)
{
if (temp[i]>'0')
{
for(int j=i;j<=99;j++)
result[j-i]=temp[j];
return;
}
}
//如果沒有一位大於0
result[0]='0';
return;
}
int main()
{
char a[100],b[100];
cin>>a>>b;
Highj(a,b);
cout<<result<<endl;
return 0;
}
Trie，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
它有3个基本性质：
这是一个Trie结构的例子： 
在这个Trie结构中，保存了A、to、tea、ted、ten、i、in、inn这8个字符串，仅占用8个字节（不包括指针占用的空间）。
以下是我自己寫的Trie的代碼：
#include <fstream>
/*
NOIP必备资料： Retrieval Tree 字典树
本程序为字典树的基本操作，包含字典树的建立、插入、删除的操作
本程序在GCC下编译通过并能正确工作
欢迎交流：zyfworks@gmail.com
*/
using namespace std;
const int sonnum=26; //子节点个数
const char base='a';
struct Trie
{
bool isStr; //该处是否插入过一个字符串
struct Trie *son[sonnum];//子节点
};
Trie *NewTrie() //Create a new node 建立一个新的字典树
{
Trie *temp=new Trie;
temp->isStr=false;
for (int i=0;i<sonnum;i++)
temp->son[i]=NULL; //初始化子节点
return temp;
}
void Insert(Trie *pnt,char *s,int len) //Insert a new word to Trie Tree
{ //向字典树插入一个新的字符串
Trie *temp=pnt;
for (int i=0;i<len;i++)
{
if (temp->son[s[i]-base]==NULL)
temp->son[s[i]-base]=NewTrie();
temp=temp->son[s[i]-base];
}
temp->isStr=true;
}
bool check(Trie *pnt,char *s,int len) //测试字典树中是否存在某个字符串
{
Trie *temp=pnt;
for (int i=0;i<len;i++)
if (temp->son[s[i]-base]!=NULL)
temp=temp->son[s[i]-base];
else return false;
return temp->isStr;
}
void DeleteWord(Trie *pnt,char *s,int len)//从字典树中删除某个字符串
{
Trie *temp=pnt;
for (int i=0;i<len;i++)
if (temp->son[s[i]-base]!=NULL)
temp=temp->son[s[i]-base];
else return;
temp->isStr=false;
}
int main()
{
Trie *Tree;
Tree=NewTrie();
ifstream fin("trie.in");
ofstream fout("trie.out");
char s[100];
int m;
fin>>m;
for (int i=0;i<m;i++)
{
fin>>s;
Insert(Tree,s,strlen(s)); //插入字符串
}
fin>>m;
for (int i=0;i<m;i++)
{
fin>>s;
DeleteWord(Tree,s,strlen(s)); //删除字符串
}
fin>>m;
for (int i=0;i<m;i++)
{
fin>>s;
fout<<check(Tree,s,strlen(s))<<endl;//测试字符串是否存在
}
return 0;
}
高精度計算是NOIP中常考常用的算法之一，剛才把我們班康運澤同學寫的高精度乘法要了過來，改成了完全的封裝函數，貼了出來。
代碼如下：
#include<fstream>
using namespace std;
ifstream fin("mul.in");
ofstream fout("mul.out");
int e[220]={5};
int gjdcf(char *mul,char *mul2)
{
int i,j,lq,lw,q[110],w[110],temp;
lq=strlen(mul);
for (i=0;i<lq;i++)
{
q[lq-1-i]=mul[i]-'0';
}
lw=strlen(mul2);
for (i=0;i<lw;i++)
{
w[lw-1-i]=mul2[i]-'0';
}
if (lq<lw)
{
for (i=0;i<lw;i++)
{
temp=q[i];
q[i]=w[i];
w[i]=temp;
}
temp=lq;
lq=lw;
lw=temp;
}
for (i=0;i<(lq+lw+1);i++)
{
e[i]=0;
}
for (i=0;i<lw;i++)
{
for (j=0;j<lq;j++)
{
if ((e[j+i-1]>=10)&&((j+i-1)>=0))
{
e[j+i]=e[j+i]+e[j+i-1]/10;
e[j+i-1]=e[j+i-1]%10;
}
if ((w[i]*q[j])<10)
{
e[j+i]=(w[i]*q[j])+e[j+i];
}
if ((w[i]*q[j])>=10)
{
e[j+i+1]=(w[i]*q[j])/10+e[j+i+1];
e[j+i]=(w[i]*q[j])%10+e[j+i];
}
if ((e[j+i])>=10)
{
e[j+i+1]=e[j+i]/10+e[j+i+1];
e[j+i]=e[j+i]%10;
}
}
}
return lq+lw;
}
void print(int p)
{
int i;
if (e[p-2]==0)
{
fout<<0;
}
else
{
if ((e[p-1]==0)&&(e[p-2]!=0))
{
for (i=p-2;i>=0;i--)
{
fout<<e[i];
}
}
else
{
for (i=p-1;i>=0;i--)
{
fout<<e[i];
}
}
}
}
int main()
{
char aa[101],bb[101];
fin>>aa>>bb;
print(gjdcf(aa,bb));
return 0;
}
问题描述
设有N堆沙子排成一排，其编号为1,2,3,…,N(N<=100)。每堆沙子有一定的数量。现要将N堆沙子并成为一堆。归并的过程只能每次将相邻的两堆沙子堆成一堆，这样经过N-1次归并后成为一堆。找出一种合理的归并方法，使总的代价最小。
【输入格式】
输入由若干行组成，第一行有一个整数，n（1≤n≤100）；表示沙子堆数。第2至m+1行是每堆沙子的数量。
【输出格式】
一个整数，归并的最小代价。
【输入样例】
输入文件名：shizi.in
7
13
7
8
16
21
4
18
【输出样例】
输出文件名：shizi.out
239
令f[i,j]表示归并第i个数到第j数的最小代价,sum[i,j]表示第i个数到第j个数的和，这个可以事先计算出来。sum[i,j]可以在O(1)的时间内算出.
/*
*f[i,j]表示從第i個到第j個歸併的最小代價
*sum[i,j]表示第i個數到第j個數的總和
*邊界條件：f[i][i]=0
sum[i][i]=stone[i][i]
*總和遞推公式：sum[i][j]=sum[i][j-1]+stone[j]
*狀態轉移方程：f[i,j]=min{f[i,k]+f[k+1][j]+sum[i][j]}(i<=k<=j-1)
*目標結果：f[1,n]
*/
#include <iostream>
using namespace std;
#define M 101
#define INF 1000000000
int n; //石子的堆數
int f[M][M]; //f[i,j]表示從第i個到第j個歸併的最小代價
int sum[M][M]; //sum[i,j]表示第i個數到第j個數的總和
int stone[M]; //每堆石子合併的代價
int main()
{
freopen("shizi.in","r",stdin);
freopen("shizi.out","w",stdout);
int i,j,k;
cin>>n;
for(i=1;i<=n;i++)
scanf("%d",&stone[i]);
for(i=1;i<=n;i++)
{
f[i][i]=0;
sum[i][i]=stone[i];
for(j=i+1;j<=n;j++)
sum[i][j]=sum[i][j-1]+stone[j];
}
for(int len=2;len<=n;len++)//归并的石子长度
{
for(i=1;i<=n-len+1;i++)//i為起點，j為終點
{
j=i+len-1;
f[i][j]=INF; //合併代價初始為最大值
for(k=i;k<=j-1;k++)
{
if(f[i][j]>f[i][k]+f[k+1][j]+sum[i][j])
f[i][j]=f[i][k]+f[k+1][j]+sum[i][j];
}
}
}
printf("%d\n",f[1][n]);
return 0;
}
