目录
题解
CF
A题
B题
简单搜索
B题
M题
F题
Java知识点
多态
转换
初始化块
包装类
==与equals
final修饰符
抽象方法和抽象类
接口
Problem - A - Codeforces
1.这一题和之前那一道题目很类似,说的是求最短路径,没有必要使用BFS(肯定也能求出来,但是很麻烦)。
2.题目说在坐标里面,只能走x-1,y和x+1,y+1。

对于上面这个情况来说是一定有解决的。
没有解的情况是当终点在起点下面说明是无解的,也就是起点y坐标一定要小于终点y坐标。
然后就是在y轴坐标相等的情况下,我们也需要判断一下,因为如果起点在终点的左边也是不可能的,改变x的值只能是-1(此时)
最后就是我们去看终点倒起点坐标的x轴坐标位于什么位置

比如上面就是这个样子,会在-1,-1的位置,无论我们怎么走,都是不能走到的,因为那个位置不在起点左边,起点只能往左边走。它往左边走的那个位置必须是能够斜上往上走的。
如果满足条件我们计算出来即可。
sum+=d-b;//y轴相差距离x1=b;x2=c-sum;if(x2<=a) {sum+=a-x2;printf("%d\n",sum);}
其他情况是-1.
代码如下:
#include
#include
int main()
{int t,a,b,c,d,sum=0,x1,x2;scanf("%d",&t);while(t--){sum=0;scanf("%d%d%d%d",&a,&b,&c,&d);if(dc){printf("%d\n",a-c);}else {sum+=d-b;//y轴相差距离x1=b;x2=c-sum;if(x2<=a) {sum+=a-x2;printf("%d\n",sum);}else {puts("-1");}}}
}
Problem - B - Codeforces
1.该题目是需要特判的。
2.题目需要我们求出MEX数组,然后算出最小的不在MEX数组里面的值。这个值的取值其实很简单。
3.我们知道,如果全部为0,那么分数一定为1,因为0全部都在数组里面了。
4.如果不全为0,为了使这个构造的数组最小,我们可以知道如果是0的个数小于等于非0个数的时候,我们可以插空去排列它,这样任意的相邻数字构造出来,是都不会为0的,此时答案是0
5.如果0的个数够多,说明总有俩个0是需要在一起的,那么0,我们是不可能取到的 ,那么我们需要这么排列,为了使它们最小,我们需要将最小的俩个非0元素放在最前面,后面任意,反正0也是必须取到的,这俩个非0元素会出现俩种情况,如果后面的数字都是1包括这俩个数字,说明1是取不到的,我们只能取到2,因此最大值如果是1,说明答案是2,否则答案为1。因为最大值是1,这个数组是能取到1的,不能把这个当作答案,而其他情况一定是1的,非0的俩个元素相加是一定大于等于2.
代码如下:
#include
#define N 200010
int a[N];
int main()
{int t,n,i;scanf("%d",&t);while(t--){int zero=0,num=0,max=0;scanf("%d",&n);for(i=0;i1||max==0)puts("1");else puts("2");}}
}
简单搜索&&进阶搜索 - Virtual Judge (vjudge.net)
1.这道题我本来使用BFS做的,答案应该也是对的,但是,如果用BFS就不是按字典序的。也算是错的吧,然后去看了别人的代码思想
2.这道题如果要满足字典序,我们可以知道的是,如果我们翻转,翻转俩次就会使那个地方又回到之前的状况,所以最优的肯定是只翻转一次。
3.我们需要从第一行开始遍历穷举,然后根据第一行的情况在第二行判断它上方(第一行)是否有黑,去翻转第二行,这样我们就能得到翻好的第一行,然后依次类推。
4.最后一行是不需要再去翻转了,因为你再翻转也只会打乱到数第二行,因此我们去判断最后一行是不是都为白即可。
5.我们需要遍历第一行的所有情况就是2^n-1个情况。然后就是需要保存最优解。
代码如下:
#include
#define N 25
#define INF 99999999
int m,n,min=INF;
int map[N][N],res[N][N],now[N][N],t[N][N];
//now数组当前移动情况,t数组当前翻砖情况
void copy(int a[N][N],int b[N][N])
{int i,j;for(i=0;i{-1,0},{1,0},{0,0},{0,-1},{0,1}};int tx,ty,i;for(i=0;i<5;i++){tx=x+next[i][0];ty=y+next[i][1];if(tx<0||ty<0||tx>=m||ty>=n) continue;t[tx][ty]=1-t[tx][ty];}
}
int ares()//解决问题
{int i,j,sum=0;for(i=0;i>j)&1;}init();k=ares();if(min>k){min=k;copy(res,now);}}
}
int main()
{scanf("%d%d",&m,&n);int i,j;for(i=0;i
简单搜索&&进阶搜索 - Virtual Judge (vjudge.net)
1.这一题用的是BFS算法。
2.相对位置指的是,另外一层x,y坐标和当前传送门一样的位置(我还以为是到另外一个传送门).
3.需要注意的点是,如果你到了传送门的位置,它的相对位置,是不能为#,*的,只能为P和 ". "
4.然后就是注意时刻。
#include
#define N 15
char map[2][N][N];
int n,m,t;
struct node
{int z;int x;int y;int s;
}path[N*N*3];
int head,tail;
int bfs()
{head=tail=0;path[head].z=0;path[head].x=0;path[head].y=0;path[head].s=0;tail++;int tx,ty,book[2][N][N]={0},now;book[0][0][0]=1;int next[4][2]={{-1,0},{1,0},{0,1},{0,-1}},i,j;while(headt) return -1;if(tx<0||ty<0||tx>=n||ty>=m) continue;if(map[path[head].z][tx][ty]=='*'||book[path[head].z][tx][ty]) continue;if(map[path[head].z][tx][ty]=='.'){path[tail].z=path[head].z;path[tail].x=tx;path[tail].y=ty;path[tail].s=path[head].s+1;book[path[head].z][tx][ty]=1;tail++;}if(map[path[head].z][tx][ty]=='#'&&map[1-path[head].z][tx][ty]=='#'){book[path[head].z][tx][ty]=1;book[1-path[head].z][tx][ty]=1;continue;}if(map[path[head].z][tx][ty]=='#'){if(map[1-path[head].z][tx][ty]=='.'){path[tail].z=1-path[head].z;path[tail].x=tx;path[tail].y=ty;book[path[head].z][tx][ty]=1;path[tail].s=path[head].s+1;tail++;}if(map[1-path[head].z][tx][ty]=='P'){return path[head].s+1;}}if(map[path[head].z][tx][ty]=='P') return path[head].s+1;}head++;}return -1;
}
int main()
{int c,i,j,k,sum=0,l;scanf("%d",&c);l=c;while(c--){scanf("%d%d%d",&n,&m,&t);for(i=0;i<2;i++){for(j=0;j
简单搜索&&进阶搜索 - Virtual Judge (vjudge.net)
1.深搜即可,和之前的做的水坑的差不多。
代码如下:
#include
#define N 110
int map[N][N];
int n,m;
int dfs(int x,int y)
{int tx,ty,i;int next[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};for(i=0;i<8;i++){tx=x+next[i][0];ty=y+next[i][1];if(tx>=0&&ty>=0&&tx
创建任何对象总是从该类所在继承树最顶层类的构造器开始执行,然后依次向下执行,最后才执行本类的构造器。
java引用变量有俩种类型一个是编译时运行,一个时运行时类型,编译时类型由声明改变量时使用的类型决定,运行时类型由实际赋给改变量的对象决定的。
大致的意思是父类变量可以接受子类变量,从而会实现多种类。
转换,基本类型只能在数值类型之间进行。数值型不能和布尔型进行交换。
引用类型之间只能在具有继承关系的俩个类型之间进行,如果俩个没有任何继承关系的类型,是无法进行类型转换的,会编译出错。
强制类型转换可能会出现异常,因此我们需要instanceof运算符来判断是否可以成功转换。
instanceof 运算符的前一个操作数通常是一个引用类型变量,后一个操作数通常是一个类,也可以是一个接口,instanceof主要判断前面的对象是否为后面的类,或者子类,返回bool型数据
类型 instanceof 类型(可写变量)
初始化块的修饰符只能是static,使用static修饰的初始化块被称为静态初始化块。
初始化和构造器作用相似,但是初始化块是一段固定执行的代码,不接受任何参数。
因为8种基本数据类型的变量不能被当成Object类型变量使用,java提供了包装类。为8种基本数据类型定义了相应的引用类型,并且称为基本数据类型的包装类。
包装类可以实现基本类型变量和字符串之间的转换。
利用包装类提供的parseXxx(String s)静态方法,除去Character之外的所有包装类都提供了该方法。
利用包装类提供的valueOf(String s)静态方法
toString()方法是Object类里的一个实列方法,所有的java对象都有toString()方法。
所有的java对象都可以和字符串进行连接运算,当java对象和字符串进行连接运算时,系统自动调用java对象toString()方法的返回值和字符串进行连接运算。
java程序种判断俩个变量是否相等有俩种方式,一种时==运算符,另一种时equals()方法,若使用==来判断俩个变量的值是否相等时,只能判断数组类型的基本类型变量。但如果时引用类型变量,只有当他们指向同一个对象时,==判断才会返回真。
String已经重写了Object的equals方法,就是判断俩个字符串是否相等。
如果重写equals应该满足,自发性,对称性,一致性,传递性,一致性。
java类里面只能包含成员变量,方法,构造器,初始化块,内部类。static可以修饰成员变量,方法,初始化块,内部类,static修饰的成员就是类成员,类成员属于整个类,不属于单个对象。
静态初始化块时类成员的一种,静态初始化块用于执行类初始化动作,在类的初始化阶段,系统会调用该类的静态初始化块来对类进行初始化。
static关键字,类成员不能访问实例成员。
如果一个类只能创建一个实例,则这个类被称为单例类。如果是单例类,必须使用static修饰,保证知道只创建过一次。
final修饰符用于修饰类,变量和方法。final修饰符表示该变量一旦获得了初值,就不可以被改变,final也可以修饰局部变量和形参。
final修饰的成员变量必须由程序员显式的指定初始值。类似于c语言的define
对于final修饰的引用变量而言,不能改变的是引用变量的地址,而不是地址所保存的值。
final修饰的方法不可以被重写。修饰的类不可以有子类。
不可变类的意思是创建该类的的实例后,该实例的实例变量是不可以改变的,java提供的8个包装类和java.lang.String类都是不可变类。
例如:
Double d=new Double(6.5)
定义抽象类只需要在普通类上加上abstract修饰符即可。
抽象方法和抽象类必须使用abstract修饰符来修饰,抽象方法不能有方法体。
抽象类不能被实例化,无法使用new关键字来调用抽象类的构造器创建抽象类的实例。
抽象类可以包含成员变量、方法构造器初始化块、内部类5种,抽象类的构造器不能用于创建实例,主要是被子类调用。
含有抽象方法的类只能被定义成抽象类。
abstract不能用于修饰成员变量,不能修饰局部变量、不能修饰构造器。
abstract和static不能同时修饰某一个方法,但是可以同时修饰内部类。abstract方法不能被定义为private访问权限,private和abstract不能同时修饰方法。
抽象类是从多个具体类中抽象出来的父类,它具有更高层次的抽象。类似于我们日常生活中说的模板,子类总体上会大致保留抽象类的行为方式。
抽象父类可以只定义需要使用的某些方法,不能实现的部分抽象成抽象方法,留给子类去实现。
接口定义了一种规范,定义了某一批类所需要遵守的规范,而不关心这些类的内部状态数据,也不关系这些类方法的实现细节,它只规定这批类里面必须提供某些方法。
所以接口是从多个相似类抽象出来的规范,接口不提供任何实现。
接口的定义,不使用class关键字,而是使用interface关键字。基本语法如下:
[修饰符]interface 接口名字extends 父接口1,父接口2{……}
修饰符可以省略,省略就是default,即只有在相同包结构才能访问该接口。
一个接口可以有多个直接父接口,接口只能和接口继承。
接口里面不能包含构造器和初始化块定义,接口可以包含成员变量(只能是静态变量),方法(只能是抽象实例方法、类方法、默认方法或者私有方法)、内部类(包括内部接口、枚举)定义。
如果不是定义默认方法、内方法、私有方法,系统会自动增加abstract修饰符。接口定义的内部类、内部接口、内部枚举默认采用public static俩个修饰符,不管用户是否指定这俩个修饰符。
接口默认方法必须使用default修饰,不能使用static修饰。
接口和类继承不一样,接口支持多继承,一个接口可以有多个直接父接口。
接口不能用于创建实例,但是可以用于声明引用类型变量,接口的主要用途就是被实现类实现。
一个类可以实现一个或者多个接口,继承使用extends关键字,实现使用implements关键字。
[修饰符]class 类名extends 父类implements 接口1,接口2{类体部分}
实现接口方法时,必须使用public访问修饰符。
接口和抽象类都不能被实例化,都可以包含抽象方法。