给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(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.数据操作
Q&A:
什么是二分法呢?
其实一直以来,在我的印象当中就是高中时候求解二元一次方程组解的时候所使用的算法。
也是现代计算器进行计算的原理。(即一直>>1[除以2]直到答案符合精度)
现在,我将通过系统的学习来为大家讲述二分法的更深入的地方。
Time limit : 1 s | Memory limit : 32 mb |
---|---|
Submitted : 6 | Accepted : 2 |
64bit Integer Format : %lld |
---|
#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; }
输入一行数字,如果我们把这行数字中的‘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.
对于一个存在着标准输入输出的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 *
std::cout |
#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; }
#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; }
吃糖果问题
复杂方法:
#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"); } }
#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问题。。。
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:
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.
4 -935 2475 -11 -15 1 0 -3 -2 93 16 3 2 191 -192 11 -12
8,11,18 1 The code cannot be decrypted. 16,15
八月 | ||||||
---|---|---|---|---|---|---|
日 | 一 | 二 | 三 | 四 | 五 | 六 |
28 | 29 | 30 | 31 | 1 | 2 | 3 |
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |