题解：

作业：

L题：

简单搜索&&进阶搜索 - Virtual Judge (vjudge.net)

1.这道题目需要用到dfs算法。如果用的是广搜，去判断结果上面会很吃亏（TLE）.

2.我们定义一个pos  [ N ] 数组，来记录当前字符跟第 几个 数据 的 值 相等。

通俗来说，就是pos [ j ]代表的是这是第  j  个数据，然后pos [ j ]里面存储的值，就叫x吧，为当前遍历到第 j 个数据 的第x个。只有4个字母组成，所以dfs不会爆。

3.如果要求出序列最短值，我们可以用一个变量deep，来记录是多少，但是我们需要去遍历deep从1开始到多少，能够满足最短序列。也就是说我们预设给一个最小值，去看在dfs中这个最小值能否满足有解。如果有结束循坏即可。

#include<stdio.h>
#include<string.h>
#define N 10
char str[N][10];
int length[N],pos[N];
char next[4]={'A','C','G','T'};
int deep,flag=1,n;
int dfs(int step)
{
//	printf("--%d--\n",step);
	if(flag==0||step>deep) //如果已经找到
	{
		return 0;
	}
	int temp[N]={0},i,j,is;
	int mmax=0;
	for(i=0;i<4;i++)//遍历四个
	{
		is=0;
		for(j=0;j<n;j++)//预存
		{
			temp[j]=pos[j];
		//	printf("%d ",pos[j]);
		}
	//	puts("");
		mmax=0;
		for(j=0;j<n;j++)//找是否相等
		{
			if(pos[j]<length[j]&&str[j][pos[j]]==next[i])
			{
			//	printf("%s %d %d %d %c\n",str[j],step,j,pos[j],next[i]);
				pos[j]++;
				is=1;
			}
			if(mmax<length[j]-pos[j]) mmax=length[j]-pos[j];
		}
	//	printf("+++%d\n",mmax);
		if(mmax==0) 
		{
			flag=0;
			return 0;
		}
		if(mmax+step>deep+1) 
		{
			for(j=0;j<n;j++)//预存
			{
				temp[j]=pos[j];
			//	printf("%d ",pos[j]);
			}
			return 0;
		}

		if(is)//有价值去dfs它
		{
			dfs(step+1);
			for(j=0;j<n;j++)
				pos[j]=temp[j];
		}
	}
}
int main()
{
	int t,i,max;
	scanf("%d",&t);
	while(t--)
	{
		max=0;
		scanf("%d",&n);
		for(i=0;i<n;i++)
		{
			scanf("%s",str[i]);
			length[i]=strlen(str[i]);
			if(length[i]>max) max=length[i];
			pos[i]=0;
		}
	//	for(i=0;i<n;i++)
		{
	//		puts(str[i]);
		//	printf("%d\n",length[i]);
		}
		deep=max;
		while(1)
		{
		//	printf("--%d--",deep);
			flag=1;
			dfs(1);
			if(flag==0) break;
			deep++;
		}
		printf("%d\n",deep);
	}
//	puts(res);
//	printf("%d\n",pd());
}

N题

简单搜索&&进阶搜索 - Virtual Judge (vjudge.net)

1.这个题目与搜索无关（虽然只有10个城市，但是dfs也会爆TLE），需要使用到dp。

2.我们知道每一个城市都有三种状态，没去过，去过一次，去过俩次。因此我们可以用三进制来表示城市的状态 一共会有3^n次方种状态。

比如三进制 1011 表示，第一个城市访问1次，第二个城市访问0次，第三个城市访问1次，第四个城市访问1次，表示当前的状态，此时三进制的值为3^3+3^2*0+3^1+3^0=27+3+1=31

把10进制转化为三进制并且对应城市即可表示状态

3.我们开一个dp数组表示，dp[N][M]，其中N表示一共有几种状态，M表示在这个状态下，到  第x个  城市 的最小花费。

4.存储图我用的是邻接矩阵，因为这是一个无向图。

5.我们遍历所有的状态，如果这个城市在这个状态下，取到的值为0，说明这个城市没有访问，那么这样的值我们是不需要的。

6.在遍历状态下的同时，我们可以遍历最小花费，到 x 就是到 x的最小花费。需要注意的是，我们要设置一个起点，此时dp[i^3][i]=0;代表从i除非（此时，只有 i 城市被访问一次）。其他dp值都需要为INF。

从 j 出发到 k，去遍历。在 i 的状态下到 k ，如果访问了俩次，就是值为2的时候我们不去考虑它能不能通过其他点来刷新，如果值不为2，那么dp[i+k^3][k]，这个表示的是，在 i 的状态下再去访问一次k（所以值不能为2）的状态，到k的最小值。

p=i+k^3

因此递推公式为：dp[p][k]=MIN(dp[p][k],dp[i][j]+e[j][k]);

在dp[i][j]存储的就是  i  的状态下到 j 的最小值

代码如下：

#include<stdio.h>
#define N 11
#define Maxn 60010
#define INF 99999999
int dp[Maxn][N];//在三进制状态下对应的城市最短路径
int e[N][N],three[N];
int n,m,counts[Maxn][N];
int csh()
{
	three[0]=1;
	int i,j,t;
	for(i=1;i<N;i++)
	{
		three[i]=3*three[i-1];
	//	printf("%d\n",three[i]);
	}
	for(i=0;i<three[10];i++)
	{
		t=i;
		for(j=0;t;j++)
		{
		//	printf("%d ",t%3);
			counts[i][j]=t%3;
			t/=3;
		}
	//	puts("");
	}
}
int init()
{
	int i,j;
	for(i=0;i<N;i++)
	{
		for(j=0;j<N;j++)
		{
			e[i][j]=INF;
		}
	}
	for(i=0;i<Maxn;i++)
	{
		for(j=0;j<N;j++)
		{
			dp[i][j]=INF;
			dp[three[j]][j]=0;
		}
		
	}
}
int MIN(int a,int b)
{
	if(a>b) return b;
	return a;
}
int DP()
{
	int i,j,k,flag,p,min=INF;
	for(i=0;i<three[n];i++)
	{
		flag=1;
		for(j=0;j<n;j++) //从j开始
		{
			if(counts[i][j]==0) 
			{
				flag=0;//说明这种状态到达不了
				continue;
			}
		//	if(dp[i][j]==INF) continue;
			for(k=0;k<n;k++)//到达j点
			{
				if(e[j][k]==INF) continue;
				if(counts[i][k]==2) continue;
				p=i+three[k];
				dp[p][k]=MIN(dp[p][k],dp[i][j]+e[j][k]);
			}
		}
		if(flag)
		{
			for(j=0;j<n;j++)
			{
				min=MIN(min,dp[i][j]);
			}
		}
	}
	if(min==INF) puts("-1");
	else printf("%d\n",min);
}
int main()
{
	int i,j,u,v,w;
	csh();
	while(~scanf("%d%d",&n,&m))
	{
		init();
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			u-=1;
			v-=1;
			e[u][v]=e[v][u]=MIN(w,e[u][v]);
		}
		DP();
	}
}

P题

简单搜索&&进阶搜索 - Virtual Judge (vjudge.net)

1.这一题也是dfs题，但是不建议加步数去判断最大值（会出错），我们只记录做了最大的题数就可以了。

 2.我们dfs时需要知道前一个的列坐标作为当前行坐标，还需要知道前一个的时间和已经做的题数。

3.我们不能选择数组a[i][i]的位置，这个时没有意义的，如果已经要做的题的列坐标已经出现就不必考虑。

4.不能算步数去看最大值，因为如果你做的是最后一题，最后一题无论怎么样都是列坐标的book数组都为1的，会有错误答案（之前就是卡死在这里）.

代码如下：

#include<stdio.h>
#define N 16
int a[N][N];
int n,count,book[N];
int dfs(int x,int pre,int s)
//前一个的列坐标，前一个的时间，已经题数
{
	int i,flag=0;
	for(i=0;i<n;i++)//遍历
	{
		if(i==x||book[i])//如果是自己做自己是不需要的
		//或者下一个题不能做
		{
			continue;
		}
		if(a[x][i]>=pre)//如果大于前一个时间，则递归求解
		{
			book[i]=1;
			dfs(i,a[x][i],s+1);
			book[i]=0;
			flag=1;
		}
	}
	if(flag==0&&s>count)//如果没有大于的或者没有可以继续的，保留最大的值
		count=s;
	return 0;
}
int main()
{
	int i,j;
	while(~scanf("%d",&n))
	{
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				scanf("%d",&a[i][j]);
			}
		}
		book[0]=1;
		count=0;
		dfs(0,0,1);//默认最小一个
		printf("%d\n",count);
	}
	return 0;
}

Q题

简单搜索&&进阶搜索 - Virtual Judge (vjudge.net)

1.这是一个dfs题目，但是需要剪枝。

2.这个题目你必须要知道的是，除了最底层的表面积是 上面的圆加上侧面积，其他层都只是需要侧面积。

3.我们知道，需要满足m层，并且取的都是整数，那么最上面一层的最小半径必须为1，高也必须为1。因为每一层都需要比下一层多至少1个。我们可以算出m层至少需要多大的表面积和体积。如果我们在dfs的时候，还需要k层，我们就可以看当前体积加上k层最小体积是否超过，超过就放弃这条道路，表面积也是一样，如果当前表面积已经大于我们存储的最小值，便可以舍去这条道路。

代码如下：

#include<stdio.h>
#define M 25
#define INF 99999999
int minv[M],s[M],mins=INF;
int n,m;
int dfs(int step,int prev,int prer,int preh,int surfaces)
{
	int i,j,v,ts,k,nox;
	if(step<=0)
	{
		if(prev==0&&mins>surfaces)
		{
			mins=surfaces;
		}
		return 0;
	}
	if(prev<=0||surfaces+s[step]>=mins||minv[step]>prev) return 0;

	for(i=step;i<prer;i++)
	{
		for(j=step;j<preh;j++)
		{
			nox=0;
			v=i*i*j;//体积
			if(prev-v*step>0) continue;//太小了
			if(prev-v<0) break;//太大了
			if(step==m) ts=(i*i+i*j*2)+surfaces;
			else ts=(i*j*2)+surfaces;
			
			for(k=1;k<step;k++)
			{
				nox+=(i-k)*(i-k)*(j-k);
			}
			if(ts<mins&&prev-v<=nox) dfs(step-1,prev-v,i,j,ts);
		}
	}
}
int main()
{
	
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=i;j++)
		{
			minv[i]+=j*j*j;//最小体积
			s[i]+=2*j*j;//最小表面积
		}
	}
	if(m==0||n==0) 
	{
		printf("0\n");
		return 0;
	}
	dfs(m,n,100,1000,0);
	if(mins==INF) puts("0");
	else printf("%d\n",mins);
	return 0;
	
}

CF：

G1题

Problem - G1 - Codeforces

这个题目暴力+前缀和可以解决，因为一个数只能被前面比它小或者相等的数来构成。排序，加上暴力，前缀和就可以。

#include<stdio.h>
#define N 5010
int a[N],b[N];
int quicksort(int left,int right)
{
	if(left>=right) return 0;
	int i=left,j=right,t=a[left],temp;
	while(i<j)
	{
		while(i<j&&a[j]>=t) j--;
		while(i<j&&a[i]<=t) i++;
		if(i<j)
		{
			temp=a[i];a[i]=a[j];a[j]=temp;
		}
	}
	a[left]=a[i];
	a[i]=t;
	quicksort(left,i-1);
	quicksort(i+1,right);
	return 0;
}
int main()
{
	int t,n,i,j,p,q,flag=1,sum;
	scanf("%d",&t);
	while(t--)
	{
		b[0]=0;
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		quicksort(1,n);
		for(i=1;i<=n;i++)
		{
			b[i]=b[i-1]+a[i];
		}
		flag=1;
		b[0]=1;
	//	for(i=0;i<=n;i++)
		{
	//		printf("%d ",b[i]);
		}
	//	puts("");
		//第i个数字只能通过i-1的数字得到
		for(i=1;i<=n&&flag;i++)
		{
			if(a[i]>b[i-1])
			{
				flag=0;
				break;
			}
			else if(a[i]<b[i-1])
			{
				//前面有一个一样的，或者前面相加等于它
				for(p=1;p<i;p++)
				{
					for(q=p+1;q<i;q++)
					{
						if(b[q]-b[p]==a[i])
						{
							flag=1;
							break;
						}
					}
					if(q<i) break;
				}
			}
		}
		if(flag) puts("YES");
		else puts("NO");
	}
}

G2题

Problem - G2 - Codeforces

这个题目我卡在最后一个点，然后去看了别人的代码，他们只计算了一个前缀和就可以，我才意识到，这个很类似于二进制，先是1 再是 1 然后才能是2，就像8421可以组成1-15的任何数字，我明白，只要后面给的数字小于等于它前一个位置的前缀和，那么他就一定会被组成，否则是不能的。

快排会爆，用归并可以不爆。

代码：

#include<stdio.h>
#define N 200100
long long a[N],b[N],sum,n;
void merge(int left,int right)
{
	if(left>=right) return ;
	int i,j,mid=(left+right)/2,k;
	for(i=left,j=left;i<=right&&j<=right;i++,j++)
	{
		b[i]=a[j];
	}
	for(i=left,j=mid+1,k=left;i<=mid&&j<=right;)
	{
		if(b[i]>b[j])
		{
			a[k++]=b[j++];
		}
		else 
		{
			a[k++]=b[i++];
		}
	}
	while(i<=mid) a[k++]=b[i++];
	while(j<=right) a[k++]=b[j++];
}
int fun(int left,int right)
{
	int i,j,mid;
	i=left;j=right;
	mid=(left+right)/2;
	if(i<j)
	{
		fun(i,mid);
		fun(mid+1,j);
		merge(i,j);
	}
	else return 0;
}
int main()
{
	long long t,i,j,p,q,flag=1,sum;
	scanf("%lld",&t);
	while(t--)
	{
		sum=1;
	//	b[0]=0;
		flag=1;
		scanf("%lld",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
		}
		
		fun(1,n);
		
		if(n==1&&a[1]==1)
		{
			puts("YES");
			continue;
		}
		else if(n==1&&a[1]!=1)
		{
			puts("NO");
			continue;
		}
		for(i=2;i<=n;i++)
		{
			if(sum<a[i])
			{
				flag=0;
				break;
			}
			else sum+=a[i];
		}
		if(flag) puts("YES");
		else puts("NO");
	}
}

Java知识点：

LinkedList

这是java提供的一种线性表，是双向的一个链表。

方法：

add(type) 向链表末尾添加元素

addfirst(elem) 元素添加到头

addLast(elem)元素添加到尾部

offer(elem)链表末尾添加元素

offerFirst(elem)在链表头部插入元素

offerLast(elem)尾部插入元素

clear()清空链表

remove(index)删除指定位置元素

removeFirst()删除并且返回第一个元素

removeLast()删除并且返回最后一个元素

get(index)返回指定位置的元素

getFirst()返回第一个元素

getLast()返回最后一个元素

size()链表长度

HashSet

HashSet是基于HashMap来实现的，不允许有重复元素。它是无序的.

add()添加方法

contains()判断方法元素是否存在于集合当中

remove()删除集合元素

clear()清除所有元素。

size()计算大小

HashMap

HashMap是一个散列表，存储的内容是键值对映射，不支持线程同步。它也是无序的。

put()添加元素

get()访问key对应的value

remove()删除key对应的键值对

size()计算大小

Iteraor(迭代器)

是集合框架的一种机制，提供了一种不暴露集合内部实现的情况下遍历元素的方法。（类似于c语言指针）

next()返回下一个元素

hasNext()检测是否还有元素

remove()将迭代器所返回的元素删除

泛型：

泛型使一个参数可以接受多种类型，从而减少构造方法。泛型只能使引用数据类型

E在集合中使用

T type java类

K key键

V 值

N 数值类型

? 不确定的类型，是所有类型的父类

java日期时间

Date类封装了当前的日期和时间

after(date) 判断Date对象是否在指定日期之后

before(date)判断是否在指定日期之前

compare To(date)比较date对象大小

setTime(time)表示时间和日期

toString()将date对象转换为以下形式：String dow mon dd hh:mm ss zzz yyyy。dow是星期。

 正则表达式

用来搜索、编辑或者处理文本。

"."匹配任何一个字符

\s+表示可以匹配多个空格

^定义了以什么开始

\d+匹配一个或者多个数字

?设置括号内的选项是可选的

\.匹配"."

java语言俩个\\才能有转义的作用

java序列化

一个对象可以被表示为一个字节序列，该字节序列包括该对象的数据、有关对象的类型信息和存储在对象中数据的类型。

我们可以根据序列化写入文件的信息，在内存中新建对象。

如果一个对象想要序列化成功，该类必须实现java.io.Serializable接口，该类所有数学必须是可序列化的。

ObjectOuputStream类用来序列化一个对象

ObjectInputStream类反序列化。返回值为Object。