饭煲

叶粉叶吹叶本命

hdu1495 非常可乐

看题目时万万没想到是bfs……不过这种寻找最少次数的问题确实除了bfs也想不到其他办法了orz


Problem Description

大家一定觉的运动以后喝可乐是一件很惬意的事情,但是seeyou却不这么认为。因为每次当seeyou买了可乐以后,阿牛就要求和seeyou一起分享这一瓶可乐,而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子,它们的容量分别是N 毫升和M 毫升 可乐的体积为S (S<101)毫升 (正好装满一瓶) ,它们三个之间可以相互倒可乐 (都是没有刻度的,且 S==N+M,101>S>0,N>0,M>0) 。聪明的ACMER你们说他们能平分吗?如果能请输出倒可乐的最少的次数,如果不能输出"NO"。

 


Input

三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量,以"0 0 0"结束。

 


Output

如果能平分的话请输出最少要倒的次数,否则输出"NO"。

 


Sample Input

7 4 3

4 1 3

0 0 0

 


Sample Output

NO

3

 

题目看了半天没看懂(……),说几个比较容易误会的点

可乐必须平分且喝完,可以用可乐瓶也就是s喝……

所以一个水杯往另两个水杯倒水共六种操作,每种操作还有两种情况,以下代码_(:з」∠)_


```

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

bool flag[110][110][110]={0};

struct st{

int s,n,m;

int step;

st(int a,int b,int c,int d):s(a),n(b),m(c),step(d){}

}; 

int main()

{

int n,m,s;

while(cin>>s>>n>>m&&s||n||m){

if(s%2) cout<<"NO"<<endl;

else{

bool r=1;

if(n<m) swap(n,m);

queue <st> qe;

st t=st(s,0,0,0);

flag[s][0][0]=1;

qe.push(t);

while(!qe.empty()){

st k=qe.front();

qe.pop();

if(k.n==s/2&&k.s==s/2){

cout<<k.step<<endl;

r=0;

break;

}

if(k.s>0&&k.n<n){//s倒n

int t1=n-k.n;

if(t1>=k.s&&!flag[0][k.n+k.s][k.m]){

qe.push(st(0,k.n+k.s,k.m,k.step+1));

flag[0][k.n+k.s][k.m]=1;

}else if(t1<k.s&&!flag[k.s-t1][n][k.m]){

qe.push(st(k.s-t1,n,k.m,k.step+1));

flag[k.s-t1][n][k.m]=1;

}

}

if(k.s>0&&k.m<m){//s倒m

int t1=m-k.m;

if(t1>=k.s&&!flag[0][k.n][k.m+k.s]){

qe.push(st(0,k.n,k.m+k.s,k.step+1));

flag[0][k.n][k.m+k.s]=1;

}else if(t1<k.s&&!flag[k.s-t1][k.n][m]){

qe.push(st(k.s-t1,k.n,m,k.step+1));

flag[k.s-t1][k.n][m]=1;

}

}

if(k.m>0&&k.n<n){//m倒n

int t1=n-k.n;

if(t1>=k.m&&!flag[k.s][k.n+k.m][0]){

qe.push(st(k.s,k.n+k.m,0,k.step+1));

flag[k.s][k.n+k.m][0]=1;

}else if(t1<k.m&&!flag[k.s][n][k.m-t1]){

qe.push(st(k.s,n,k.m-t1,k.step+1));

flag[k.s][n][k.m-t1]=1;

}

}

if(k.n>0&&k.m<m){//n倒m

int t1=m-k.m;

if(t1>=k.n&&!flag[k.s][0][k.m+k.n]){

qe.push(st(k.s,0,k.m+k.n,k.step+1));

flag[k.s][0][k.m+k.n]=1;

}else if(t1<k.n&&!flag[k.s][k.n-t1][m]){

qe.push(st(k.s,k.n-t1,m,k.step+1));

flag[k.s][k.n-t1][m]=1;

}

}

if(k.n>0&&k.s<s){//n倒s

int t1=s-k.s;

if(t1>=k.n&&!flag[k.s+k.n][0][k.m]){

qe.push(st(k.s+k.n,0,k.m,k.step+1));

flag[k.s+k.n][0][k.m]=1;

}else if(t1<k.n&&!flag[s][k.n-t1][k.m]){

qe.push(st(s,k.n-t1,k.m,k.step+1));

flag[s][k.n-t1][k.m]=1;

}

}

if(k.m>0&&k.s<s){//m倒s

int t1=s-k.s;

if(t1>=k.m&&!flag[k.s+k.m][k.n][0]){

qe.push(st(k.s+k.m,k.n,0,k.step+1));

flag[k.s+k.m][k.n][0]=1;

}else if(t1<k.m&&!flag[s][k.n][k.m-t1]){

qe.push(st(s,k.n,k.m-t1,k.step+1));

flag[s][k.n][k.m-t1]=1;

}

}

}

if(r) cout<<"NO"<<endl;

}

memset(flag,0,sizeof(flag));

}

return 0;

}

```


P1019 单词接龙

一道题看错题目三次

一百多行代码找出16个错误(有的错误还看半天没找出来

是废物本人了

就是,很通俗的递归(。),直接套就阔以,除了处理重叠有点麻烦

P1019 单词接龙

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beastbeast 和 astonishastonish ,如果接成一条龙则变为 beastonishbeastonish ,另外相邻的两部分不能存在包含关系,例如 atat 和 atideatide 间不能相连。

输入输出格式

输入格式:

 

输入的第一行为一个单独的整数 nn ( n \le 20n≤20 )表示单词数,以下 n 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

 

输出格式:

 

只需输出以此字母开头的最长的“龙”的长度

 

输入输出样例

输入样例#1: 复制

5

at

touch

cheat

choose

tact

a

输出样例#1: 

23 

说明

(连成的“龙”为atoucheatactactouchoose)

NOIp2000提高组第三题

ac代码:

#include <iostream>

#include <cstring>

#include <string>

using namespace std;

string a[22];//储存数组 

int flag[22]={0};//标记是否用过2次以上 

int n,maxn=0;

string g;

void dfs(int x,string t){

int i=0,j,k;

int h=0,l1,l2;

int e=t.length();

if(e>maxn)maxn=e;

l1=t.length();

string t2=t;

for(i=1;i<=n;i++){

h=0;//重叠数量 

l2=a[i].length();

if(e==0){

if(a[i][0]==g[0]){


t=a[i],flag[i]++;


dfs(x+1,t);


t=t2,flag[i]--;

}else continue;

}else{

if(flag[i]<2){

if(l1>=l2) j=l1-l2;

else j=0;

int p=0;//最后重合位置 

for(;j<l1;j++){

if(a[i][0]==t[j]){

h=1;

p=0;

for(k=1;k<l2&&j+k<l1;k++){

if(a[i][k]==t[j+k]) h++,p=k;

else h=0;

}

}

}

 

if(a[i][p-h]!=t[l1]) h=0;

if(h==l2) continue;

else{

if(h==0) continue;

for(j=h;j<l2;j++){

t=t+a[i][j];

if(t2==a[3]){

}

}

flag[i]++;

dfs(x+1,t);

t=t2,flag[i]--;

}

}

}

}

}

using namespace std;

int main()

{

string t;

cin>>n;

int i;

for(i=1;i<=n;i++){

cin>>a[i];

}

cin>>g;

dfs(1,t);

cout<<maxn<<endl;

return 0;

}



P1149 火柴棒等式

补上之前落下的递归题orz

基本思路就是个二重循环,枚举a,再枚举b,直接a+b得出c

然后在枚举的范围懵了orz,其实最大是24根火柴,减去加号等于号是20根,再减去0后除以2剩余八根,就是最大值为1111

题目描述

给你n根火柴棍,你可以拼出多少个形如“ A+B=C ”的等式?等式中的 A 、 B 、 C 是用火柴棍拼出的整数(若该数非零,则最高位不能是 00 )。用火柴棍拼数字 0-90−9 的拼法如图所示:

注意:

  1. 加号与等号各自需要两根火柴棍

  2. 如果 A≠B ,则 A+B=C与 B+A=C 视为不同的等式( A,B,C>=0 )

  3. nn 根火柴棍必须全部用上

输入输出格式输入格式:

一个整数 n(n<=24)n(n<=24) 。

输出格式:

一个整数,能拼成的不同等式的数目。

输入输出样例

输入样例#1: 14

输出样例#1: 2

输入样例#2: 18

输出样例#2: 9

说明

【输入输出样例1解释】

2 个等式为

 0+1=1

0+1=1  。

【输入输出样例2解释】

99 个等式为:

0+4=4

0+11=11

1+10=11

2+2=4

2+7=9

4+0=4

7+2=9

10+1=11

11+0=11

ac代码:

#include <iostream>

#include <cmath>

#include <map>

#define ll long long

using namespace std;


int s=0;

int n;

void dfs(int x,int l,int t){

int i;

map <int,int> mp;

mp[0]=6,mp[1]=2,mp[3]=5,mp[4]=4,mp[5]=5,mp[6]=6,mp[7]=3,mp[8]=7,mp[9]=6,mp[2]=5;

int r=l;

for(i=0;i<=t;i++){

l=r;

int y=i;

do{

int k=y%10;

l+=mp[k];

y=y/10;

}while(y);


int h=i+x;

if(l>=n) continue;


int e=h;

do{

int k=h%10;

l+=mp[k];

h=h/10;


}while(h);


if(l==n){

s++;


}


}

}

int main()

{


cin>>n;

map <int,int> mp;

mp[0]=6,mp[1]=2,mp[2]=5,mp[3]=5,mp[4]=4,mp[5]=5,mp[6]=6,mp[7]=3,mp[8]=7,mp[9]=6;

n-=4;//等号和加号

int sum=0,i;//方法总数 

ll t=0;

int g=(n-6)/4;

while(g>0){

t=t*10+1;

g--;

}

t=1200;

for(i=0;i<=t;i++){

g=0;//已用火柴 

int h=i;

do{

int k=h%10;

g+=mp[k];

h=h/10;

}while(h);

    if(g>=n) continue;

dfs(i,g,t);


}

cout<<s<<endl;

return 0;

}


P1022 计算器的改良(模拟)

写的脑子发懵orz

就是模拟,思路是平时做一元一次方程的思路,常数归为一边变量再放到另一边,除了写起来麻烦好像也没什么难点,不多港了(

题目背景

NCLNCL 是一家专门从事计算器改良与升级的实验室,最近该实验室收到了某公司所委托的一个任务:需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交给了一个刚进入的新手ZL先生。

题目描述 

为了很好的完成这个任务, ZLZL 先生首先研究了一些一元一次方程的实例:

4+3x=8

6a-5+1=2-2a

-5+12y=0

ZLZL 先生被主管告之,在计算器上键入的一个一元一次方程中,只包含整数、小写字母及+、-、=这三个数学符号(当然,符号“-”既可作减号,也可作负号)。方程中并没有括号,也没有除号,方程中的字母表示未知数。

你可假设对键入的方程的正确性的判断是由另一个程序员在做,或者说可认为键入的一元一次方程均为合法的,且有唯一实数解。

输入输出格式输入格式: 

一个一元一次方程。

输出格式: 

解方程的结果(精确至小数点后三位)。

输入输出样例 

输入样例#1: 

6a-5+1=2-2a

输出样例#1: 

a=0.750

ac代码:

#include <iostream>

#include <cmath>

#include <stdio.h>

#include <cstring>

using namespace std;

int main()

{

char a[110]={0};

cin>>a;

double s=0,g=0;//结果,未知数前的常数


int i;

char y;


for(i=0;i<strlen(a);){

 

if(a[i]=='=') break;

 

if(a[i]=='+'||i==0&&a[0]!='-'){

 

if(i!=0) i++;

 

int t=0;

 

while(a[i]>='0'&&a[i]<='9'){

 

t=t*10+(a[i]-'0');

 

i++;

 }

 

if(a[i]>='a'&&a[i]<='z'){

y=a[i];

if(t==0) t=1;

g+=t;

i++;

 }else{

s-=t;

 }

 

 }

 

if(a[i]=='-'){

i++;

 

int t=0;

 

while(a[i]>='0'&&a[i]<='9'){

 

t=t*10+(a[i]-'0');

 

i++;

 }

 

if(a[i]>='a'&&a[i]<='z'){

y=a[i];

if(t==0) t=-1;

g-=t;

i++;

 }else{

s+=t;

 }

 }

 

 

 }

 

int h=++i;

 

for(;i<strlen(a);i++){

if(a[i]=='+'||i==h&&a[h]!='-'){

if(i!=h) i++;

 

int t=0;

 

while(a[i]>='0'&&a[i]<='9'){

 

t=t*10+(a[i]-'0');

 

i++;

 }

 

if(a[i]>='a'&&a[i]<='z'){

y=a[i];

if(t==0) t=1;

g-=t;

 }else{

s+=t;

 }

 

 }

 

if(a[i]=='-'){

i++;

 

int t=0;

 

while(a[i]>='0'&&a[i]<='9'){

 

t=t*10+(a[i]-'0');

 

i++;

 }

 

if(a[i]>='a'&&a[i]<='z'){

y=a[i];

if(t==0) t=-1;

g+=t;

 }else{

s-=t;

 }

 }

 }

 

double x=s/g;

 

 //cout<<s<<" "<<g<<endl;

 

printf("%c=%.3f\n",y,x);

 

 

return 0;

}


P1464 Function(记忆化搜索+打表)

水题,不多港了= =

题目描述

对于一个递归函数 w(a,b,c)w(a,b,c)

  • 如果 a \le 0a≤0 or b \le 0b≤0 or c \le 0c≤0 就返回值 11 .

  • 如果 a>20a>20 or b>20b>20 or c>20c>20 就返回 w(20,20,20)w(20,20,20)

  • 如果 a<ba<b 并且 b<cb<c 就返回 w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)w(a,b,c−1)+w(a,b−1,c−1)−w(a,b−1,c)

  • 其它的情况就返回 w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)

这是个简单的递归函数,但实现起来可能会有些问题。当 a,b,ca,b,c 均为15时,调用的次数将非常的多。你要想个办法才行.

/* absi2011 : 比如 w(30,-1,0)w(30,−1,0) 既满足条件1又满足条件2

这种时候我们就按最上面的条件来算

所以答案为1

*/

输入输出格式输入格式:

会有若干行。

并以 -1,-1,-1−1,−1,−1 结束。

保证输入的数在 [-9223372036854775808,9223372036854775807][−9223372036854775808,9223372036854775807] 之间,并且是整数。

输出格式:

输出若干行,每一行格式:

w(a, b, c) = ans

注意空格。

输入输出样例

输入样例#1: 

1 1 1

2 2 2

-1 -1 -1

输出样例#1: 

w(1, 1, 1) = 2

w(2, 2, 2) = 4

说明

记忆化搜索


ac代码:

#include <iostream>

#include <cmath>

#include <stdio.h>

using namespace std;

int w[50][50][50]={0};

void num(){

int i,j,k;

for(i=0;i<=20;i++){

for(j=0;j<=20;j++){

for(k=0;k<=20;k++){

if(i<=0||j<=0||k<=0) w[i][j][k]=1;

else if(i<j&&j<k) w[i][j][k]=w[i][j][k-1]+w[i][j-1][k-1]-w[i][j-1][k];

else w[i][j][k]=w[i-1][j][k]+w[i-1][j-1][k]+w[i-1][j][k-1]-w[i-1][j-1][k-1];

}

}

}

}

int main()

{

num();

int a,b,c;

while(cin>>a>>b>>c&&a!=-1||b!=-1||c!=-1){

int g;

if(a<=0||b<=0||c<=0) g=1;

else if(a>20||b>20||c>20) g=w[20][20][20];

else g=w[a][b][c];

 

printf("w(%d, %d, %d) = %d\n",a,b,c,g); 

}

return 0;

}


聚聚们都是不用睡觉的神仙咩(。

矩阵快速幂

在斐波那契数列之中

f[i] = 1*f[i-1]+1*f[i-2]  f[i-1] = 1*f[i-1] + 0*f[i-2];

所以

ac代码:

#include <iostream>

#include <cstring>

#include <cmath>

#define ll long long

using namespace std;

ll s=1000000009;

struct st{

ll a[2][2];

};

st num2(st r,st k){

ll i,j,h;

st g;

memset(g.a,0,sizeof(g.a));

for(i=0;i<2;i++){

for(j=0;j<2;j++){

for(h=0;h<2;h++){

g.a[i][j]=(g.a[i][j]+r.a[i][h]*k.a[j][h])%s;

}

}

}

return g;

}

void num1(ll n){

st k,r;

ll i,j;

memset(r.a,0,sizeof(r.a));

for(i=0;i<2;i++) r.a[i][i]=1;

k.a[0][0]=k.a[1][0]=k.a[0][1]=1;

k.a[1][1]=0;

while(n){

if(n&1){

r=num2(r,k);

}

k=num2(k,k);

n=n/2;

}

cout<<r.a[0][1]%s<<endl;

}

int main()

{

ll n;

cin>>n;

num1(n);

return 0;

}


1289 大鱼吃小鱼 (模拟+栈)

好久没用过栈了,果然忘得很快orz

题目描述:

有N条鱼每条鱼的位置及大小均不同,他们沿着X轴游动,有的向左,有的向右。游动的速度是一样的,两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向(0表示向左,1表示向右)。问足够长的时间之后,能剩下多少条鱼?

Input

第1行:1个数N,表示鱼的数量(1 <= N <= 100000)。 第2 - N + 1行:每行两个数A[i], B[i],中间用空格分隔,分别表示鱼的大小及游动的方向(1 <= A[i] <= 10^9,B[i] = 0 或 1,0表示向左,1表示向右)。

Output

输出1个数,表示最终剩下的鱼的数量。

Input示例

5

4 0

3 1

2 0

1 0

5 0

Output示例

2

栈的用法:

  1. push(): 向栈内压入一个成员;

  2. pop(): 从栈顶弹出一个成员;

  3. empty(): 如果栈为空返回true,否则返回false;

  4. top(): 返回栈顶,但不删除成员;

  5. size(): 返回栈内元素的大小;


ac代码:

#include <iostream>

#include <stack>

using namespace std;

int main()

{

ios::sync_with_stdio(false);

stack<int> sk;

int n,a,b,i;

cin>>n;

int g=n;

for(i=0;i<g;i++){

cin>>a>>b;

if(b){

sk.push(a);//将a压入栈 

}else{

while(!sk.empty()){//栈内为空返回true,否则返回false

if(a<sk.top())//返回栈顶元素但不删除 

{

n--;

break;

}

else{

sk.pop();//删除栈顶

n--; 

}

}

}

}

cout<<n<<endl;

return 0;

 

 }