zjutoj部分成功代码一.docx

zjutoj部分成功代码一.docx

《zjutoj部分成功代码一.docx》由会员分享，可在线阅读，更多相关《zjutoj部分成功代码一.docx（57页珍藏版）》请在冰点文库上搜索。

zjutoj部分成功代码一

Zjutoj部分成功代码

注：

因为当初刷oj上的题目很辛苦，然后网上又没有相关的代码...就想着把自己的整理放出来可供acm新手做参考。

请原谅当时的整理较为随意，所以没有记录下题号，可能给使用者带来不便...所以花了很长的时间给文档加上了文档结构图，也算是一种补偿吧。

因为时间跨度较大，代码的风格啊整齐程度优化程度有些参差不齐，望见谅。

因为文档中的代码量较大，这里就不付上原题了，原题大家可以去上找到。

当然还有很多题目这里，没有提供方法，我会在后续继续增加。

最后还是希望这份文档能对acm的新手有所帮助。

队列（有向量的插入和删除）

#include

#include

#include

usingnamespacestd;

intmain（）

{

intcas,n,m,i,t,q;

intsum;

strings;

cin>>cas;

while（cas--）

{

vectorv;

cin>>n>>m;

for（i=1;i<=n;i++）

v.push_back（i）;

while（m--）

{

cin>>s;

if（s[0]=='T'）

{

cin>>t;

for（i=0;i

if（v[i]==t）

{

v.insert（v.begin（）,t）;

v.erase（v.begin（）+i+1）;

}

}

elseif（s=="Next"）

{

q=v[0];

v.push_back（q）;

cout<

v.erase（v.begin（））;

}

}

}

return0;

}

圣诞快乐

#include

#include

#include

usingnamespacestd;

intmain（）

{

chars[55];

intk,count,i;

stringstr="MerryChristmas";

while（gets（s））

{

vectorv;

k=strlen（s）;

for（i=0;i

if（s[i]!

=''）v.push_back（s[i]）;

count=14-v.size（）;

for（i=0;i

{

if（v[i]!

=str[i]）

{

if（v[i]==str[i]+32）continue;

else

{

if（v[i]==str[i]-32）continue;

elsecount++;

}

}

}

cout<

}

return0;

}

旅行问题（并查集）

#include

usingnamespacestd;

intbin[105];

intfindx（intx）

{

intr=x;

while（bin[r]!

=r）

r=bin[r];

returnr;

}

voidmerge（intx,inty）

{

intfx,fy;

fx=findx（x）;

fy=findx（y）;

if（fx!

=fy）

bin[fx]=fy;

}

intmain（）

{

intn,m,i,x,y,count;

while（cin>>n>>m）

{

for（i=1;i<=n;i++）

bin[i]=i;

for（;m>0;m--）

{

cin>>x>>y;

merge（x,y）;

}

for（count=-1,i=1;i<=n;i++）

if（bin[i]==i）

count++;

printf（"%d\n",count）;

}

}

最大特征值（动态规划）

#include

#include

usingnamespacestd;

intmax（inta,intb）

{

return（a<=b?

b:

a）;

}

intmain（）

{

intn;cin>>n;

while（n--）

{

strings;cin>>s;

intdp[1000];

inttemp;

dp[0]=temp=int（s[0]-78）;

for（inti=1;i

{

dp[i]=int（s[i]-78）;

dp[i]=max（dp[i],dp[i-1]+dp[i]）;

if（dp[i]>temp）temp=dp[i];

}

cout<

}

return0;

}

互质的个数

#include

#include

#include

usingnamespacestd;

inthuzhi（unsignedinta,unsignedintb）

{

if（a%b==0）returnb;

returnhuzhi（b,a%b）;

}//判断两数互质的递归

intmain（）

{

for（strings;getline（cin,s）;）

{

unsignedinta;

vectorv;

for（istringstreamsin（s）;sin>>a;v.push_back（a））;//istringstream对象可以绑定一行字符串，然后以空格为分隔符把该行分隔开来。

intsum=0;

for（inti=0;i

for（intj=i+1;j

{

if（huzhi（v[i],v[j]）==1）

sum++;

}

cout<

}

}

大菲波加（很重要的大数加）

#include

#include

#include

usingnamespacestd;

constintbitNum=500;

stringadd（conststring&a,conststring&b）

{

stringc（bitNum,'0'）;

inttemp=0;

for（intai=a.length（）-1,bi=b.length（）-1,ci=0;ai>=0||bi>=0||temp;ai--,bi--,ci++）

{

temp+=（ai>=0?

a[ai]-'0':

0）+（bi>=0?

b[bi]-'0':

0）;

c[ci]=temp%10+'0';

temp/=10;

}

reverse（c.begin（）,c.end（））;

c=c.substr（c.find_first_not_of（'0'））;

returnc;

}

voidmain（）

{

strings[1005]={"1","1"};

for（inti=2;i<1005;i++）

s[i]=add（s[i-1],s[i-2]）;

intm;

for（intn;cin>>n;）

{

while（n--）

{

cin>>m;

cout<

}

}

}

菲波数（也很重要，有大数的比较）

#include

#include

#include

usingnamespacestd;

constintbitNum=205;

inti;

stringq[1000]={"1","2"};

stringadd（conststring&a,conststring&b）

{

stringc（bitNum,'0'）;

inttemp=0;

for（intai=a.length（）-1,bi=b.length（）-1,ci=0;ai>=0||bi>=0||temp;ai--,bi--,ci++）

{

temp+=（ai>=0?

a[ai]-'0':

0）+（bi>=0?

b[bi]-'0':

0）;

c[ci]=temp%10+'0';

temp/=10;

}

reverse（c.begin（）,c.end（））;

c=c.substr（c.find_first_not_of（'0'））;

returnc;

}

boolfuck（stringa,stringb）

{

returna.length（）!

=b.length（）?

a.length（）

a<=b;

}

intmain（）

{

for（i=2;i<1000;i++）

{

q[i]=add（q[i-2],q[i-1]）;

}

for（stringa,b;cin>>a>>b&&a!

="0"||b!

="0";）

{

ints=0;

for（i=0;i<1000;i++）

if（fuck（a,q[i]）&&fuck（q[i],b））s++;

cout<

}

return0;

}

最多的商品（因为里面有map的多种用法所以重要）

#include

#include

#include

#include

#include

usingnamespacestd;

voidmain（）

{

for（intn;cin>>n&&n!

=0;）

{

mapma;

map:

:

iteratorit;

map:

:

iteratorpos;

while（n--）

{

strings;intm;

cin>>s>>m;

it=ma.find（s）;

if（it==ma.end（））ma[s]=m;

elseit->second=it->second+m;

}

intmax=0;

for（it=ma.begin（）;it!

=ma.end（）;it++）

{

if（it->second>max）{max=it->second;}

}

vectorv;

for（pos=ma.begin（）;pos!

=ma.end（）;pos++）

{

if（pos->second==max）v.push_back（pos->first）;

}

for（inti=0;i

cout<

cout<

}

}

删最多元素（上一题的强化版）

#include

#include

#include

#include

usingnamespacestd;

intmain（）

{

inti,j;

for（strings;cin>>s;）

{

mapma;

map:

:

iteratorit;

for（i=0;i

{

it=ma.find（s[i]）;

if（it==ma.end（））ma[s[i]]=1;

elsema[s[i]]++;

}

intmax=0;

vectorv1;vectorv2;vectorv3;

for（it=ma.begin（）;it!

=ma.end（）;it++）

{

if（it->second>max）max=it->second;

}

for（i=0;i

v1.push_back（s[i]）;

for（it=ma.begin（）;it!

=ma.end（）;it++）

{

if（it->second==max）v2.push_back（it->first）;

}

for（i=0;i

{

boolflag=1;

for（j=0;j

{

if（v1[i]==v2[j]）

{

flag=0;break;

}

}

if（flag）v3.push_back（v1[i]）;

}

if（v3.size（）==0）cout<<"NULL"<

else

{

for（i=0;i

cout<

cout<

}

}

return0;

}

背单词

#include

#include

#include

#include

usingnamespacestd;

voidmain（）

{

vectorv;vectorv1;

intcount;

for（intn;cin>>n;）

{

while（n--）

{

strings;cin>>s;

v.push_back（s）;

}

intm;cin>>m;

while（m--）

{

stringss;cin>>ss;

v1.push_back（ss）;

}

for（intp=0;p

{

count=0;

for（intq=0;q

{

if（v[q].substr（0,v1[p].length（））==v1[p]）count++;

}

cout<

}

}

}

素数的各位数字和

#include

#include

usingnamespacestd;

vectorv;

boolisPrime（intn）

{

if（n!

=2&&n%2==0）returnfalse;

for（inti=3;i*i<=n;i+=2）

if（n%i==0）returnfalse;

returntrue;

}

voidlist（）

{

for（inti=2;i<300000;i++）

{

if（isPrime（i））v.push_back（i）;

}

}

voidmain（）

{

list（）;

intsum;

for（intn;cin>>n;）

{

boolflag=0;

for（inti=0;i

{

if（v[i]==n）

{

sum=0;

while（n!

=0）

{

sum+=n%10;

n/=10;

}

flag=1;break;

}

}

if（flag）{cout<

elsecout<<"0"<

}

}

数字游戏

#include

#include

usingnamespacestd;

intmpow（inta,intb）

{

intresult=1;

for（inti=1;i<=b;i++）

result*=a;

returnresult;

}

intf（intn,inti）

{

for（intj=2;;j++）

{

if（mpow（i,j）==n）returnj;

if（mpow（i,j）>n）return0;

}

}

voidmain（）

{

doublen;

while（cin>>n&&n）

{

inti,k;

for（i=sqrt（n）+1;i>=2;i--）

{

k=f（n,i）;

if（k>0）{cout<

}

if（i==1）cout<<0<<""<<0<

}

}

剪花布条

#include

#include

usingnamespacestd;

voidmain（）

{

for（strings,s1;cin>>s>>s1;）

{

if（s=="#"）break;

intsum=0;

while（s.find（s1）

{

s=s.substr（s.find（s1）+s1.length（）,s.length（）-（s.find（s1）+s1.length（）））;

sum++;

}

cout<

}

}

趣味求和

#include

usingnamespacestd;

voidmain（）

{

inta,b,m,sum,t;

for（;cin>>a>>b;）

{

sum=a;t=a;

for（inti=1;i

{

a=a*10+t;

sum+=a;

}

cout<

}

}

Reversetest

#include

#include

usingnamespacestd;

voidmain（）

{

charc[100];

intn;cin>>n;

while（n--）

{

gets（c）;

intm=strlen（c）;

for（inti=m-1;i>=0;i--）

cout<

cout<

}

}

列出完数

#include

#include

usingnamespacestd;

voidmain（）

{

vectorv;inti;

for（i=2;i<10000;i+=2）

{

intsum=1;

for（intj=2;j<=i/2;j++）

{if（i%j==0）sum+=j;}

if（sum==i）{v.push_back（i）;}||先打表。

}

intn;

for（;cin>>n;）

{

cout<

";

for（intm=0;m<=v.size（）-1;m++）

if（v[m]<=n）cout<<''<

cout<

}

}

空心三角形

#include

usingnamespacestd;

voidmain（）

{

charch;intn;

for（;cin>>ch>>n;）

{

if（ch=='@'）break;

for（intp=1;p<=n-1;p++）

{cout<<'';}cout<

for（inti=1;i

{

for（intj=1;j

{cout<<'';}cout<

for（intk=1;k<=2*i-1;k++）

{cout<<'';}cout<

cout<

}

for（intt=1;t<=2*n-1;t++）

{cout<

}

}

数数字

#include

#include

usingnamespacestd;

voidmain（）

{

stringstr;charch;intm;

for（;cin>>str>>ch;）

{

m=0;

for（inti=0;i

{if（str[i]==ch）m++;}

cout<

}

}

比大小

#include

#include

usingnamespacestd;

voidmain（）

{

stringstr1,str2;

intsum1,sum2;

for（;cin>>str1>>str2;）

{

if（str1.length（）!

=str2.length（））

cout<<（str1.length（）>str2.length（）?

str2:

str1）<

elseif（str1.length（）==str2.length（））

{

sum1=0;sum2=0;

for（inti=0;i

{sum1+=str1[i]-'0';}

for（intj=0;j

{sum2+=str2[j]-'0';}

if（sum1==sum2）cout<<"thesame";

else

cout<<（sum1>sum2?

str2:

str1）;

cout<

}

}

}

无秤售油（可根据输入输出知道一斤为20两）

#include

#include

#include

usingnamespacestd;

voidmain（）

{

for（intn;cin>>n;）

{

vectorv;

cout<

"<

inti=0;

for（;n;）

{

if（n%2==1）

{v.push_back（pow（（double）2.0,i））;

n=n-1;

}

n=n/2;i=i+1;

}

for（intj=0;j

cout<<""<

}

}

矩阵