Jack's Blog

流淌的心,怎能阻拦,吹来的风,又怎能阻挡。

迷宫问题广度搜索--ACM第五讲

给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(maze problem)

 

迷宫可以以二维数组来存储表示。0表示通路,1表示障碍。注意这里规定移动可以从上、下、左、右四方方向移动。坐标以行和列表示,均从0开始,给定起点(0,0)和终点(4,4),迷宫表示如下:

左图每个方块表示一个状态,浅蓝色的表示遍历了该状态。

广度优先搜索即是按层数一层一层来遍历,先将一层全部扩展,然后再进行下一层。

利用队列先进先出(FIFO)的性质恰好可以来完成这个任务

 

对应的队列的情况:

具体过程:

1 每次取出队列首元素(初始状态),进行拓展

2 然后把拓展所得到的可行状态都放到队列里面

3 将初始状态删除

4 循环执行以上三步直到找到目标状态或者队列为空。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
int mp[10][10];
bool inq[10][10];//passed set true

struct node{
    int x,y;
    node(int x=0,int y=0):x(x),y(y) {}
};
queue<node> q;
node frm[10][10];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
bool bfs(){
    q.push(node(1,1));
    inq[1][1]=true;
    frm[1][1]=node(0,0);
    while (!q.empty()){
        node now = q.front();
        q.pop();
        if (now.x==5 && now.y==5){
            return true;
        }
        for(int i=0;i<4;i++){
            int tx=now.x+dx[i],ty=now.y+dy[i];
            if (!inq[tx][ty] && mp[tx][ty]==0){
                inq[tx][ty]=true;
                q.push(node(tx,ty));
                frm[tx][ty]=now;
            }
        }
    }
    return false;
}
void printans(int x,int y){
    if (x==0 && y==0)   return;
    printans(frm[x][y].x,frm[x][y].y);
    printf("(%d, %d)\n",x-1,y-1);
}
int main(){
    for (int i=0;i<=6;i++){
        for (int j=0;j<=6;j++){
            mp[i][j]=-1;
        }
    }
    for (int i=1;i<=5;i++){
        for (int j=1;j<=5;j++){
            scanf("%d",&mp[i][j]);
        }
    }
    bfs();
    printans(5,5);
    return 0;
}

函数的参数是什么样的?
结构体
struct A指针或引用
链表 数组
线性表
链表——无顺序数组
为什么是零散的状态?
1.可以动态申请内存
链表不需要任何静态的申请
eg.1
1 2 3 4 6 8 10
1 2 3 6 8 10
删除第四位
for(int i=3;i<=n;i++){
    a[i]=a[i+1]
}
链表插入一次就好
数组得挪很多次
链表访问比数组麻烦
链表结构体

声明一个指针函数
Struct link{
    int data;
    link* next;(内置类型的一个东西)
}
link *l;
l=new link();
(*l).data=15(l->data=15);
l->next =NULL;
link *head=new link();
link *push_back(link *p,int x)
{
    link *q= new link();
    q->data = x;
    q->next = NULL;
    p->next = q;
    return p->next;

}
Link *tmp = head;

链表访问复杂度较高(频繁插入删除,不频繁查找)
for(int i=1;i<10;i++)
{
    tmp = push_back(tmp,i);
}
栈 stack(抽象数据结构)
只能在顶端进行插入和删除
先进后出
队列(抽象数据结构)
可以用数组,也可用链表
数据结构
1.数据形态
2.数据操作

二分法学习--acm第三讲

Q&A:

什么是二分法呢?

其实一直以来,在我的印象当中就是高中时候求解二元一次方程组解的时候所使用的算法。

也是现代计算器进行计算的原理。(即一直>>1[除以2]直到答案符合精度)

现在,我将通过系统的学习来为大家讲述二分法的更深入的地方。


 

acm--4

A - A

Time limit : 1 s Memory limit : 32 mb
Submitted : 6 Accepted : 2
64bit Integer Format : %lld

 

Problem Description

FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.
 

Input

The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.

Output

For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.

Sample Input

5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1

Sample Output

13.333 31.500
#include <stdio.h>
#include <stdlib.h>
#include <cstdio>

struct info{
    double val;
    int pos;
};
int amount(info a[],int n)
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
           if(a[j].val>a[i].val)
           {
               double t;
               t = a[i].val;
               a[i].val=a[j].val;
               a[j].val=t;
               int tt;
               tt=a[i].pos;
               a[i].pos=a[j].pos;
               a[j].pos=tt;
           }
        }
    }
    return 0;
}
int main()
{

    int M,N;
    int i;
    while(1)
    {
        scanf("%d %d",&M,&N);
        if(M==-1&&N==-1)
            break;
        info price[N]={0};
        int F[N]={0},J[N]={0};
        for(i=0;i<N;i++)
        {
            scanf("%d %d",&J[i],&F[i]);
            price[i].val=(double)J[i]/F[i];
            price[i].pos=i;
        }
        amount(price,N);
        double output=0;
        for(i=0;i<N;i++)
        {
            if(M>=F[price[i].pos])
            {
                output+=price[i].val*F[price[i].pos];
                M-=F[price[i].pos];
            }
            else if(M>0&&M<F[price[i].pos])
            {
                output+=price[i].val*M;
                M=0;
                break;
            }
        }
        printf("%.3lf\n",output);
    }
    return 0;
}

然而在oj里面。。。Runtime Error

没办法啊,只好看看哪里可以改进

2.sort

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int MAXN = 1010;
struct node
{
    double j,f;
    double r;
}a[MAXN];
/*
int cmp(const void *a,const void *b)//从大到小排序 
{
    struct node *c=(node *)a;
    struct node *d=(node *)b;
    if(c->r > d->r) return -1;
    else return 1;
}    */
bool cmp(node a,node b)
{
    return a.r  >  b.r;
}    
int main()
{
    int N;
    double M;
    double ans;
    while(scanf("%lf%d",&M,&N))
    {
        if(M==-1&&N==-1) break;
        for(int i=0;i<N;i++)
        {
           scanf("%lf%lf",&a[i].j,&a[i].f);
           a[i].r=(double)a[i].j/a[i].f;
        }    
        //qsort(a,N,sizeof(a[0]),cmp);
        sort(a,a+N,cmp);
        ans=0;
        for(int i=0;i<N;i++)
        {
            if(M>=a[i].f)
            {
                ans+=a[i].j;
                M-=a[i].f;
            }    
            else 
            {
                ans+=(a[i].j/a[i].f)*M;
                break;
            }    
        }   
        printf("%.3lf\n",ans); 
    }    
    return 0;
}

key3:without sort:

#include<stdio.h>
#include<stdlib.h>

const int MAXN = 1010;
struct node
{
    double j,f;
    double r;
}a[MAXN];
int cmp(const void *a,const void *b)//从大到小排序 
{
    struct node *c=(node *)a;
    struct node *d=(node *)b;
    if(c->r > d->r) return -1;
    else return 1;
}    
int main()
{
    int N;
    double M;
    double ans;
    while(scanf("%lf%d",&M,&N))
    {
        if(M==-1&&N==-1) break;
        for(int i=0;i<N;i++)
        {
           scanf("%lf%lf",&a[i].j,&a[i].f);
           a[i].r=(double)a[i].j/a[i].f;
        }    
        qsort(a,N,sizeof(a[0]),cmp);
        ans=0;
        for(int i=0;i<N;i++)
        {
            if(M>=a[i].f)
            {
                ans+=a[i].j;
                M-=a[i].f;
            }    
            else 
            {
                ans+=(a[i].j/a[i].f)*M;
                break;
            }    
        }   
        printf("%.3lf\n",ans); 
    }    
    return 0;
}

acm--3

输入一行数字,如果我们把这行数字中的‘5’都看成空格,那么就得到一行用空格分割的若干非负整数(可能有些整数以‘0’开头,这些头部的‘0’应该被忽略掉,除非这个整数就是由若干个‘0’组成的,这时这个整数就是0)。

你的任务是:对这些分割得到的整数,依从小到大的顺序排序输出。        

初玩can,接触第三天的一道水题

第一程序为最初所写,第二个为参考优化后,

#include"stdio.h"
main()
{
    char c;
    while((scanf("%c",&c))!=EOF)
    {
         char a[1300];
         long long int b[1300],sum=0;
         int state=0,temp,k=0,i,j,l;
        for(i=0;c!='\t'&&c!='\n'&&c!=' ';i++)
        {
            a[i]=c;
            scanf("%c",&c);
        }
        a[i]='\0';
        for(j=0;j<i;j++)
        {
            if(a[j]=='5')
            {
                  if(state==1)
                    b[k++]=sum;
                  state=0;
                  sum=0;
            }
            else if(a[j]=='0')
              {
                   state=1;
                sum=sum*10+a[j]-'0';
              }
            else
                {
                   sum=sum*10+a[j]-'0';
                   state=1;
                }
        }
        if(state==1)
            b[k++]=sum;
            k--;
        for(j=0;j<k;j++)
            for(l=0;l<k-j;l++)
        {
            if(b[l]>b[l+1])
            {
                temp=b[l];
                b[l]=b[l+1];
                b[l+1]=temp;
            }
        }
        for(i=0;i<=k-1;i++)
        {
            printf("%lld ",b[i]);
        }
        printf("%lld\n",b[i]);
    }
}

2.

#include"stdio.h"
#include"string.h"
main()
{
 
    int i,len,k,n,temp,j,l;
     char s[5005];
     while(scanf("%s",s)!=EOF)
    {
        int a[5005];
        n=0;
        k=0;
        len=strlen(s);
         s[len]='5';
         i=0;
         while(s[i++]=='5');  //跳过前缀5,防止多输出0
        for(i--;i<=len;++i)
        {
             if(i>0&&s[i]=='5'&&s[i-1]=='5') //忽略连续的5,防止多输出0
                 continue;
            if(s[i]!='5')
                 k=k*10+s[i]-'0';
            else            //遇到5就增加一个数
            {
                 a[n++]=k;
               k=0;
            }
        }
        for(j=0;j<n-1;j++)
            for(l=0;l<n-j-1;l++)
        {
            if(a[l]>a[l+1])
            {
                temp=a[l];
                a[l]=a[l+1];
                a[l+1]=temp;
            }
        }
        for(i=0;i<n-1;i++)
        {
            printf("%d ",a[i]);
        }
        printf("%d\n",a[i]);
    }
}

ACM--C++初学

       对于一个存在着标准输入输出的C++控制台程序,一般会在#include <iostream>的下一行发现一句话,using namespace std

       这句话其实就表示了所有的标准库函数都在标准命名空间std中进行了定义。其作用就在于避免发生重命名的问题。

#include <iostream>
using namespace std;
 
namespace ZhangSan
{
    int a=10; //张三把10赋值给了变量a
}
namespace LiSi
{
    int a=5; //李四把10赋值给了变量a
}
 
void main()
{
    int a=1;
    cout<<"张三定义的a="<<ZhangSan::a<<endl;
    cout<<"李四定义的a="<<LiSi::a<<endl;
    cout<<"主函数定义的a="<<a<<endl;   
}

上例中的“ZhangSan::a”和“LiSi::a”分别表示了调用张三命名空间中的a变量和李四命名空间中的a变量。这样的好处显而易见,那就是虽然张三和李四这两个程序员都定义了一个变量a,但是并不会出现重名的危险。

 2. 关于using namespace *

  顾名思义,using namespace * 就表示释放命名空间* 中间的东西。好处在于我们在程序里面就不用在每个函数的头上都加上*::来调用。比如说如果上面那个程序,如果我们不在using namespace std,那么我们就需要在主函数中的标准输出流cout函数前面加上std,写成
 
std::cout
表示调用std空间里面的标准输出流cout。但是有些时候我们也不能图这个方便,比如说如果在主函数中将命名空间ZhangSan和LiSi的中所定义的变量释放出来,如下例1:
#include <iostream>
using namespace std;
 
namespace ZhangSan
{
    int a=10; //张三把10赋值给了变量a
}
namespace LiSi
{
    int a=5; //李四把10赋值给了变量a
}
 
void main()
{
    int a=1;
    using namespace ZhangSan;
    using namespace LiSi;
    cout<<a<<endl;
}
如果我们在主函数中把 int a=1给删除,如下例2:
#include <iostream>
using namespace std;
 
namespace ZhangSan
{
    int a=10; //张三把10赋值给了变量a
}
namespace LiSi
{
    int a=5; //李四把10赋值给了变量a
}
 
void main()
{
    using namespace ZhangSan;
    using namespace LiSi;
    cout<<a<<endl;
}
会发现根本就不会通过编译,输出的错误信息为:
error C2872: “a”: 不明确的符号
  分析可以看出,上面这个例2会引起歧义。因为ZhangSan中间的a被释放出来,同理LiSi中间的a也被释放出来了。那么编译器就不知道到底哪个才是需要输出的a,自然就会引起歧义了。同理,在例1中,编译器同样不知道到底哪个才是需要输出的a,于是它只采用了主函数中自己定义的a,这样程序也不会报错,但是只会输出1,自然结果就如上面的图所示了。
摘自:http://www.cnblogs.com/uniqueliu/archive/2011/07/10/2102238.html

 

acm-2

吃糖果问题

复杂方法:

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
main()
{
    int i,t,j,N,f[50]={0};
    scanf("%d",&t);
    for(i=0;i<t;i++)
    {
        scanf(" %d",&N);
        for(j=0;j<N;j++)
        {
            scanf(" %d",&f[j]);
        }
        int k;
        for(j=0;j<N;j++)
        {
            for(k=0;k<N;k++)
            {
                if(f[i]<f[i+1])
                {
                    int middle = f[i];
                    f[i]=f[i+1];
                    f[i+1]=middle;
                }
            }
        }
        int flag=f[0];
        for(k=0;k<N;k++)
        {
            flag=flag-f[k+1];
        }
        if(flag>=2)
            printf("No\n");
        else
            printf("Yes\n");
    }

}

简便算法:

# include<stdio.h>
int main()
{
    long T, N;
    double candy, max,sum;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d", &N);
        max = sum = 0;
        while(N--)
        {
            scanf("%lf", &candy);
            max = max > candy ? max : candy;
            sum += candy;
        }
    sum -= max;
    if(max <= sum + 1)
        printf("Yes\n");
    else
        printf("No\n");
 }
}

acm-第一题

Problem Description

对于表达式n^2+n+41,当n在(x,y)范围内取整数值时(包括x,y)(-39<=x<y<=50),判定该表达式的值是否都为素数。

Input

输入数据有多组,每组占一行,由两个整数x,y组成,当x=0,y=0时,表示输入结束,该行不做处理。

Output

对于每个给定范围内的取值,如果表达式的值都为素数,则输出"OK",否则请输出“Sorry”,每组输出占一行。

Sample Input

0 1 0 0

Sample Output

OK
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int is_prime(int a)
{
    int j;
    for(j=2;j<=sqrt(a);j++)
    {
        if(a % j ==0)
        {
            return 1;
        }
    }
    return 0;
}

int main()
{

    int x,y;
    while(1)
    {
        int flag=0;
        scanf("%d%d",&x,&y);
        int i;
        if(x==0&&y==0)
            return 0;
        if(x>y)
        {
            int t=y;
            y=x;
            x=t;
        }

        for(i=x;i<=y;i++)
        {
            int s;
            s = i*i+i+41;
            if(is_prime(s))
            {
                flag++;
                break;
            }
        }
        if(flag == 0)
            printf("OK\n");
        else
            printf("Sorry\n");
        }
    return 0;
}



很简单的一道题,发出来纯粹是因为无聊。这个题一直不能Accept,本来以为是我写错了,最后老师查出来是hoj问题。。。

ACM practice 1

1.

The Sarcophagus itself is locked by a secret numerical code. When somebody wants to open it, he must know the code and set it exactly on the top of the Sarcophagus. A very intricate mechanism then opens the cover. If an incorrect code is entered, the tickets inside would catch fire immediately and they would have been lost forever. The code (consisting of up to 100 integers) was hidden in the Alexandrian Library but unfortunately, as you probably know, the library burned down completely.

But an almost unknown archaeologist has obtained a copy of the code something during the 18th century. He was afraid that the code could get to the ``wrong people'' so he has encoded the numbers in a very special way. He took a random complex number B that was greater (in absolute value) than any of the encoded numbers. Then he counted the numbers as the digits of the system with basis B. That means the sequence of numbers an, an-1, ..., a1, a0 was encoded as the number X = a0 + a1B + a2B2 + ...+ anBn.

Your goal is to decrypt the secret code, i.e. to express a given number X in the number system to the base B. In other words, given the numbers X and Byou are to determine the ``digit'' a0 through an.

Input

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case consists of one single line containing four integer numbers Xr, Xi, Br, Bi (|Xr|,|Xi| <= 1000000, |Br|,|Bi| <= 16). These numbers indicate the real and complex components of numbers X and B, i.e. X = Xr + i.Xi, B = Br + i.Bi. B is the basis of the system (|B| > 1), X is the number you have to express.

Output

Your program must output a single line for each test case. The line should contain the ``digits'' an, an-1, ..., a1, a0, separated by commas. The following conditions must be satisfied:

  • for all i in {0, 1, 2, ...n}: 0 <= ai < |B|
  • X = a0 + a1B + a2B2 + ...+ anBn
  • if n > 0 then an <> 0
  • n <= 100

If there are no numbers meeting these criteria, output the sentence "The code cannot be decrypted.. If there are more possibilities, print any of them.

Sample Input

4

-935 2475 -11 -15

1 0 -3 -2

93 16 3 2

191 -192 11 -12

Sample Output

8,11,18

1

The code cannot be decrypted.

16,15