ACM模板Word格式.docx
- 文档编号:8456427
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:23
- 大小:21.68KB
ACM模板Word格式.docx
《ACM模板Word格式.docx》由会员分享,可在线阅读,更多相关《ACM模板Word格式.docx(23页珍藏版)》请在冰点文库上搜索。
elsereturn;
//线段树
//用一维数组tree[]实现,由于树是不平衡的,所以大小一般开为总区间长度的3-4倍
//用途:
建立线段树
//调用方式:
build(1,1,n,)
//参数:
n为节点标号,l为左边界,r为右边界,val为要初始化的值
voidbuild(intn,intl,intr,intval){
tree[n]=val;
if(l==r)return;
intmid=(l+r)/2;
build(n<
1,l,mid);
build((n<
1)+1,mid+1,r);
//用途:
在线段树中查询
//调用方式:
query(1,1,n,,)
//参数:
n为节点标号,l为查询区间的左边界,r为查询区间的右边界,ll为目标区间的左边界,rr为目标区间的右边界
intquery(intn,intl,intr,intll,intrr){
intk;
if(l==ll&
&
r==rr)returntree[n];
intmid=(r+l)/2;
if(rr<
=mid)returnquery(n<
1,l,mid,ll,rr);
elseif(mid<
ll)returnquery((n<
1)+1,mid+1,r,ll,rr);
elsereturnmax(query(n<
1,l,mid,ll,mid),query((n<
1)+1,mid+1,r,mid+1,rr));
更新线段树(更新一个点)
update(1,1,n,,)
n为节点标号,l为查询区间的左边界,r为查询区间的右起界,v为待更新节点,val为要更新的值
voidupdata(intn,intl,intr,intv,intval){
if(l==v&
r==v){
tree[n]=val;
return;
intmid=(l+r)/2,k;
if(v<
=mid)k=updata(n<
1,v,l,mid);
elsek=updata((n<
1)+1,v,mid+1,r);
if(k>
tree[n])tree[n]=k;
//高精度
//在Linux中,gcc很统一的用%lld
//在Windows中,MinGW的gcc和VC6都需要使用%I64d
//但VS2008却是用%lld
//用一个int表示一位数字
constintmaxn=1000;
structbign{
intlen,s[maxn];
bign(){
memset(s,0,sizeof(s));
len=0;
bign(intnum){*this=num;
bign(constchar*num){*this=num;
bignoperator=(constchar*num){
len=strlen(num);
for(inti=0;
i<
len;
i++)
s[i]=num[len-i-1]-'
0'
;
return*this;
bignoperator=(intnum){
chars[maxn];
sprintf(s,"
%d"
num);
*this=s;
stringstr()const{
stringres="
"
i++)res=(char)(s[i]+'
)+res;
if(res=="
)res="
0"
returnres;
bignoperator+(constbign&
b)const{
bignc;
for(inti=0,g=0;
max(len,b.len)+1;
i++){
intx=s[i]+b.s[i]+g;
c.s[c.len++]=x%10;
g=x/10;
if(c.s[c.len-1]==0)c.len--;
returnc;
bignoperator*(constbign&
intres[maxn],g=0,i,j;
memset(res,0,sizeof(res));
for(i=0;
g=0;
for(j=0;
j<
b.len||g;
j++){
res[i+j]+=s[i]*b.s[j]+g;
g=res[i+j]/10;
res[i+j]%=10;
}
memcpy(c.s,res,sizeof(res));
c.len=i+j-1;
bignoperator+=(constbign&
b){
*this=*this+b;
bignoperator*=(constbign&
*this=*this*b;
};
istream&
operator>
(istream&
in,bign&
x){
strings;
in>
s;
x=s.c_str();
returnin;
ostream&
operator<
(ostream&
out,constbign&
cout<
x.str();
returnout;
-------------------------------------------------------------
constlonglongmaxn=1000000000;
longlongs[600];
intlen;
s[0]=1;
len=1;
voidoperator*=(constbign&
inti,j;
longlongres[600],g;
memset(res,0,sizeof(res));
g=res[i+j]/maxn;
res[i+j]%=maxn;
memcpy(s,res,sizeof(res));
len=i+j-1;
}
voidoperator+=(constbign&
intl;
longlongg=0;
l=max(len,b.len)+1;
l;
s[i]+=b.s[i]+g;
if(s[i]>
=maxn){
s[i]-=maxn;
g=1;
elseg=0;
if(s[l-1]==0)l--;
len=l;
voidoutput(){
inti=len-1;
printf("
%I64d"
s[i--]);
while(i>
=0)printf("
%09I64d"
s[i--]);
\n"
);
//字典树
//建树
TreeNode*r;
r=newTreeNode();
//树中节点的结构体
structTreeNode{
intcount;
//计数,当然可以按需要设定
TreeNode*next[26];
//可能作为其后继的26个字母
TreeNode(){
count=1;
for(inti=0;
26;
i++)
next[i]=NULL;
voidInsert(char*a,TreeNode*r){
inti=0,t;
TreeNode*tmp=r;
while(a[i]){
t=a[i]-'
a'
if(tmp->
next[t]!
=NULL){
tmp=tmp->
next[t];
//tmp->
count++;
截取自求一某字符串为前缀的字符串的数量(应按题目自拟)
else{
tmp->
next[t]=newTreeNode();
i++;
return;
intQuery(char*a,TreeNode*r){
inti=0,t,ans;
t=a[i]-'
next[t]!
=NULL){
tmp=tmp->
//ans=tmp->
count;
自拟
elsereturn0;
returnans;
//树状数组
//代替静态线段树求区间上的统计个数问题
//树状数组:
对于序列c,我们设一个数组a定义a[i]=c[i–2^k+1]+…+c[i],k为i在二进制下末尾0的个数。
//作用:
查询0-x范围内
intq(intx)
{
intr=0;
while(x)
{
r+=a[x];
x-=(x&
(-x));
//x&
(-x)求二进制表示中最右边的一位1
returnr;
在x处添加d
//其中n为边界
voidadd(intx,intd)
while(x<
=n)
a[x]+=d;
x+=(x&
//有限状态自动机
//可以搜索以正则式表达的模式串
//构造自动机的核心是构造其状态转移函数
#include<
stdio.h>
string.h>
chara[1001],b[1001];
ints[9][256],color[9];
voidinit(){//状态转移函数构造
inti;
charc;
s[1]['
+'
]=s[1]['
-'
]=2;
for(i=0;
i<
=9;
i++){
c=i+'
s[1][c]=3;
s[2][c]=3;
s[3][c]=3;
s[4][c]=5;
s[5][c]=5;
s[7][c]=8;
s[6][c]=8;
s[8][c]=8;
s[3]['
.'
]=4;
e'
]=s[3]['
E'
]=6;
s[5]['
]=s[5]['
s[6]['
]=s[6]['
]=7;
color[3]=color[8]=color[5]=1;
//接受状态
intmain(){
intcas,i,j,k,len,st;
scanf("
%d\n"
&
cas);
init();
while(cas--){
gets(a);
i=0;
j=strlen(a)-1;
while(a[i]=='
'
)i++;
while(a[j]=='
)j--;
if(a[0]=='
)b[0]='
elseb[0]='
len=1;
for(k=i;
k<
=j;
k++)
b[len++]=a[k];
st=1;
//初始状态
for(i=0;
len;
st=s[st][b[i]];
if(!
st)break;
//其他未定义状态
if(i!
=len)printf("
ILLEGAL\n"
else{
if(color[st])printf("
LEGAL\n"
elseprintf("
return0;
//高斯消元
//复杂度为n^3
//矩阵长==宽==l
//b[i]即对应着i个解
//寻找主元素(一列中最大值,这样有利于稳定)
for(j=1;
=l;
k=j;
for(i=j+1;
if(fabs(a[k][j])<
fabs(a[i][j])){
k=i;
if(j!
=k){
for(i=j;
t=a[k][i];
a[k][i]=a[j][i];
a[j][i]=t;
t=b[j];
b[j]=b[k];
b[k]=t;
//使主元素变1
a[j][i]=a[j][i]/a[j][j];
b[j]/=a[j][j];
//消元
for(k=j+1;
k<
k++){
a[i][k]=a[i][k]-a[i][j]*a[j][k];
b[i]=b[i]-a[i][j]*b[j];
//回代
for(i=l-1;
i>
=1;
i--){
for(j=l;
j>
i;
j--){
//ST算法
//即递推求出每个位置起(包括该点),长度为2^i(0<
=i<
log2n)区间内的最大值和最小值
//查询时把查询区间分成两个相交的区间,求得两个的最大最小值。
//代替静态的线段树求区间最大最小值问题
//数组开设
//a[n][lb(n)]如:
a[50000][16]
//输入数据
i<
n;
scanf("
a[i][0]);
b[i][0]=a[i][0];
//构造
for(s=1,i=1;
s<
for(j=0;
;
j++){
if((s<
1)+j>
n)break;
a[j][i]=max(a[j][i-1],a[j+s][i-1]);
b[j][i]=min(b[j][i-1],b[j+s][i-1]);
s<
=1;
//查询
q;
%d%d"
x,&
y);
x--;
//由于数据由0开始输的
t=y-x;
k=1;
c=0;
while(k<
k<
c++;
c--;
printf("
max(a[x][c],a[y-(1<
c)][c])-min(b[x][c],b[y-(1<
c)][c]));
//二分求幂
scanf("
%d%d"
&
m,&
n);
------------
//递推版本
//可用于矩阵求幂
ans=1;
while(n>
0){
if(n&
1)ans*=m;
m=m*m;
n/=2;
//递归函数
intcal(intn){
intt;
if(n==1)returnm;
t=cal(n/2);
1)returnt*t*m;
elsereturnt*t;
//表达式树
//str为输入的字符串,tree为表达式树,lch为左孩子,rch为右孩子
charstr[50],tree[50],lch[50],rch[50];
//nc:
以个数作为节点的索引
intlen,nc;
intbuild_tree(char*s,intx,inty){
inti,c1=-1,c2=-1,c3=-1,p=0;
intu;
if(y-x==1){
u=++nc;
lch[u]=rch[u]=0;
tree[u]=s[x];
returnu;
//找最后一个计算的运算符
for(i=x;
y;
switch(s[i]){
case'
('
:
p++;
break;
)'
p--;
if(!
p)c1=i;
*'
/'
p)c2=i;
^'
p)c3=i;
//这里可以扩张
if(c1<
0)c1=c2;
0)c1=c3;
0)returnbuild_tree(s,x+1,y-1);
//找两边
lch[u]=build_tree(s,x,c1);
rch[u]=build_tree(s,c1+1,y);
tree[u]=s[c1];
//此为后序遍历,可自拟
voidprin_tree(intu){
if(lch[u]!
=0)prin_tree(lch[u]);
if(rch[u]!
=0)prin_tree(rch[u]);
%c"
tree[u]);
inti,j,g;
%s"
str);
len=strlen(str);
g=build_tree(str,0,len);
prin_tree(g);
//表达式转换用栈实现,更容易推广为求值
//f1为最终结果
charstr[50];
charf1[50],f2[50];
//f1数据栈,f2运算符栈
ints1,s2;
//分别表示两栈顶
//如果是运算符,则先将栈中比它优先级高的运算符出栈,然后自己再入栈
voidxx(charc){
inti,j;
if(c=='
||c=='
){
while(s2&
f2[s2-1]!
='
)
f1[s1++]=f2[--s2];
f2[s2++]=c;
elseif(c=='
s2--;
(f2[s2-1]=='
||f2[s2-1]=='
))
intcal(inta,intb,charc){
switch(c){
returna+b;
returna-b;
returna*b;
returna/b;
while(b--)a*=a;
returna;
default:
inti,j,l,len,p,k;
s1=0,s2=0;
len;
if(isdigit(str[i]))f1[s1++]=str[i];
elsexx(str[i])
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ACM 模板