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.数据操作

#include <iostream>

using namespace std;
struct A{
    int a;
    int b;
}A1={0};
struct A my_swap(int a1,int b1)
{
    A1.a=b1;
    A1.b=a1;
    return A1;
}

int main()
{
    int a=1,b=2;
    A A2= my_swap(a,b);
    my_swap(a,b);
    printf("%d %d",a,b);
    return 0;
}

用结构体实现了swap

其实最简单的还是用指针来写swap

my_swap(int &a,int &b)
my_swap(int *a,int *b)
/×
两种写法等价

然而直接用

my_swap(int a,int b);
是不能交换函数值的

因为虽然在这个函数虽然在这个函数内部互换了函数值,但是这仅仅局限与函数内部,对于整个main函数的调用并没有使用返回值。

我在想如果用内联函数进行展开是不是可以交换呢。读者们可以亲自试试。
inline int swap(int a,int b);

 

二分法学习--acm第三讲

Q&A:

什么是二分法呢?

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

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

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


 

立flag!

我可能真的要脱单了。


华丽分割线

好吧,反正写了也没有人看。说正事了:

要是我成功的脱单了的话,

1.我就每天早上7:00起床背单词

2.晚上10:30上床睡觉

3.学习高级流型微积分,量子力学

4.每天做一道acm题。

----来自一个单身了好几年的工科男的哀叹


更新:脱单失败。。。

1.虽然失败了,但是我依旧会将上述flag实施下来。

2.其实当初内心是不希望脱单成功的,这样的话哪有时间实施我的flag。。。

3.我要减肥,游泳,从下周起不断的完善自己。虽然就像那句老话说的:做最好的自己。不用和谁比,做最好的自己就好!

2017-10-15

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问题。。。