3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

yes
no
yes

《搜索是怎样剪枝的-1》

1.只要找到3条边。

2.从大到小顺序找。

3.每次搜边时要确定边的相对顺序唯一（直接从TLE→秒）

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXM (20+10)
int tt,n,a[MAXM],cnt,len;
bool b[MAXM],flag;
bool dfs(int l,int x,int pre)
{
//	cout<<l<<' '<<x<<' '<<kth<<endl;
	if (x==len) {l++;x=0;pre=n-1;}
	if (l==4)
	{
		return 1;
	}
	for(int i=pre-1;i;i--)
		if (!b[i]&&x+a[i]<=len)
		{
			b[i]=1;
			if (dfs(l,x+a[i],i)) return 1;
			b[i]=0;
		//	if (!x) return 0;
		}
	return 0;
}
int main()
{
	scanf("%d",&tt);
	while (tt--)
	{
		cnt=0;
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			cnt+=a[i];b[i]=0;
		}
		sort(a+1,a+1+n);
		if (n<4||cnt%4||a[n]>cnt/4)
		{
			printf("non");continue;
		}
		b[n]=1;len=cnt/4;
		if (dfs(1,a[n],n))
		{
			printf("yesn");
		}
		else printf("non");
	}
	return 0;
}

水灾（sliker）

大雨应经下了几天雨，却还是没有停的样子。ksy刚从外地回来，知道不久除了自己家，其他的地方都将会被洪水淹没。

ksy的老家可以用一个N*M的地图表示，地图上有五种符号：“. * X D S”。其中“X”表示石头，水和人都不能从上面经过。“.”表示平原，ksy和洪水都可以经过。“*”表示洪水开始地方（可能有多个地方开始发生洪水）。“D”表示ksy的家。“S”表示ksy现在的位置。

ksy每分钟可以向相邻位置移动，而洪水将会在ksy移动之后把相邻的没有的土地淹没（从已淹没的土地）。

求ksy回答家最少时间。如他回不了家，被淹死输出KAKTUS。

Input

3 3

D.*

...

.S.

Output

3

Input

3 3

D.*
...

..S

Output

KAKTUS

Input

3 6

D...*.

.X.X..

....S.

Output

6

因为第i秒走后，所到达的点不能有Flood

所以必须在之前Flood，然后再往下找

显然柯黑再同一个地方停留不优

故只要存储到达一个点的最短时间

注意C++中构造函数的写法

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<functional>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN (50+10)

struct node
{
	int x,y,t;
	node():x(0),y(0),t(0){}
	node(int _x,int _y,int _t):x(_x),y(_y),t(_t){/*cout<<x<<' '<<y<<' '<<t<<endl;*/}
}start,end;
/*
node made_node(int i,int j,int t)
{
	node now;
	now.x=i;
	now.y=j;
	now.t=t;
	return now;
}
*/

int n,m;
bool map[MAXN][MAXN],b[MAXN][MAXN];
char s[MAXN];
queue<node> flood,q;
bool inside(int x,int y)
{
	if (x>=1&&x<=n&&y>=1&&y<=m) return true;
	return false;
}
bool bfs()
{
	int l=-1;
	while (!q.empty())
	{
		node now=q.front();
//		cout<<now.x<<' '<<now.y<<endl;
		q.pop();
		if (now.t>l)
		{
			int size=flood.size();
			while (size)
			{
				node nowf=flood.front();
				flood.pop();
				int x=nowf.x,y=nowf.y;
				if (x>1&&b[x-1][y])
				{
					flood.push(node(x-1,y,now.t));
					map[x-1][y]=b[x-1][y]=0;
				}
				if (x<n&&b[x+1][y])
				{
					flood.push(node(x+1,y,now.t));
					map[x+1][y]=b[x+1][y]=0;
				}
				if (y>1&&b[x][y-1])
				{
					flood.push(node(x,y-1,now.t));
					map[x][y-1]=b[x][y-1]=0;
				}
				if (y<m&&b[x][y+1])
				{
					flood.push(node(x,y+1,now.t));
					map[x][y+1]=b[x][y+1]=0;
				}

				size--;
			}
			l++;
		}
		int x=now.x,y=now.y;
//		if (!map[x][y]) continue;
		if (x>1&&map[x-1][y])
		{
			if (x-1==end.x&&y==end.y){end.t=now.t+1; return true;}
			q.push(node(x-1,y,now.t+1));
			map[x-1][y]=0;
		}
		if (x<n&&map[x+1][y])
		{
			if (x+1==end.x&&y==end.y){end.t=now.t+1; return true;}
		 	q.push(node(x+1,y,now.t+1));
			map[x+1][y]=0;
		}
		if (y>1&&map[x][y-1])
		{
			if (x==end.x&&y-1==end.y){end.t=now.t+1; return true;}
			q.push(node(x,y-1,now.t+1));
			map[x][y-1]=0;
		}
		if (y<m&&map[x][y+1])
		{
			if (x==end.x&&y+1==end.y){end.t=now.t+1; return true;}
			q.push(node(x,y+1,now.t+1));
			map[x][y+1]=0;
		}





	}
	return false;
}

int main()
{
	freopen("sliker.in","r",stdin);
	freopen("sliker.out","w",stdout);
	scanf("%d%d",&n,&m);
	memset(map,1,sizeof(map));
	memset(b,1,sizeof(b));

	for (int i=1;i<=n;i++)
	{
		scanf("%s",s);
		for (int j=0;j<m;j++)
		{
			if (s[j]=='S')
			{
				start=node(i,j+1,0);
				q.push(start);
			}
			if (s[j]=='D')
			{
				end=node(i,j+1,0);
				b[i][j+1]=0;
			}
			if (s[j]=='X')
			{
				map[i][j+1]=0;
				b[i][j+1]=0;
			}
			if (s[j]=='*')
			{
				map[i][j+1]=0;
				b[i][j+1]=0;
				flood.push(node(i,j+1,0));
			}

		}
	}
/*	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (map[i][j]) cout<<"map "<<i<<' '<<j<<endl;
	cout<<"end"<<end.x<<' '<<end.y;
*/

	if (bfs()) printf("%dn",end.t);
	else printf("KAKTUSn");


//	while (1);
	return 0;
}

在一堆字母中找一段字母，使其中至少含有1个原音，2个辅音字母，且按字典序从小到大排列

果断搜

Program P3049;
var
   n,i,j,m:longint;
   a:array[1..26] of char;
   b:array['a'..'z'] of boolean;
   c:char;
procedure swap(var a,b:char);
var
   t:char;
begin
   t:=a;a:=b;b:=t;
end;
procedure dfs(father:longint;s:string;flag:boolean;l:longint);
var
   i:longint;
begin
   if l=n then
   begin
      if flag then writeln(s);
      exit;
   end;
   for i:=father+1 to m-(n-l)+1 do
      dfs(i,s+a[i],flag or b[a[i]],l+1);


end;
begin
   fillchar(b,sizeof(b),false);
   b['a']:=true;b['e']:=true;b['i']:=true;b['o']:=true;b['u']:=true;
   readln(n,m);
   for i:=1 to m do
   begin
      read(a[i]);
      read(c);
   end;
   for i:=1 to m-1 do
      for j:=i+1 to m do
         if ord(a[i])>ord(a[j]) then swap(a[i],a[j]);
   if n<3 then halt;
   dfs(0,'',false,0);


end.

这题就是搜……

注意设定maxn 要不然肯定爆 maxn=1*10^最大位数/2 1234..89-11121314这样的

Program aa;
const
   maxn=1000000000000000;
var
   n,t:longint;
   a:array[1..15] of char;
procedure dfs(l,sum,res,bl:int64);
var
   i,j:longint;
begin
   if l=n then
   begin
      res:=res+bl*sum;
      if res=0 then
      begin
         inc(t);
         if t<=20 then
         begin
            for i:=1 to n-1 do write(i,' ',a[i],' ');
            writeln(n);


         end;
      end;


      exit;
   end;

   a[l]:='+';
   dfs(l+1,l+1,res+bl*sum,1);
   a[l]:='-';
   dfs(l+1,l+1,res+bl*sum,-1);
   a[l]:='.';
   if sum<=maxn then
   if l+1<=9 then
      dfs(l+1,sum*10+(l+1),res,bl)
   else
      dfs(l+1,sum*100+(l+1),res,bl);


end;
begin
 {  assign(output,'a.pas');
   rewrite(output);
  }
   read(n);
   t:=0;
   dfs(1,1,0,1);
   writeln(t);

 //  close(output);
end.

这题是BFS水的

主要是范围

0<=n,k<=100000  但是有可能搜到200000……

半天功夫才A.

program P3278;
const
   maxn=200000;
var
   n,k,i,j:longint;
   q,deep:array[1..maxn] of longint;
   b:array[0..maxn] of boolean;
procedure add(x:longint);
begin
   if not(b[x]) then
   begin
      b[x]:=true;
      inc(j);
      q[j]:=x;
      deep[j]:=deep[i]+1;
   end;
end;
begin
   read(n,k);
   i:=1;
   j:=1;
   fillchar(b,sizeof(b),false);
   b[n]:=true;
   q[1]:=n;deep[1]:=0;
   if n=k then
   begin
      writeln('0');
      halt;
   end;


   while i<=j do
   begin
      if (q[i]>0) then add(q[i]-1);
      if b[k] then break;
      if (q[i]<maxn) then add(q[i]+1);
      if b[k] then break;
      if (q[i]*2<maxn) then add(q[i]*2);
      if b[k] then break;
      inc(i);
   end;
   writeln(deep[j]);

end.

题目大意：一张图G，有一些障碍物，求路径长度一定（可环）时的路径总数

果断广搜

Program ttd;
var
   n,m,t,i,j,k,x1,x2,y1,y2:longint;
   s:string;
   b:array[0..101,0..101] of boolean;

   f:array[0..15,0..101,0..101] of longint;
begin
   readln(n,m,t);
   fillchar(b,sizeof(b),true);
   for i:=1 to n do
   begin
      readln(s);
      for j:=1 to m do if s[j]='*' then b[i,j]:=false;
   end;
   readln(x1,y1,x2,y2);
   fillchar(f,sizeof(f),0);
   f[0,x1,y1]:=1;

   for k:=1 to t do
   begin
      for i:=1 to n do
         for j:=1 to m do
            if f[k-1,i,j]>0 then
            begin
               if b[i+1,j] then inc(f[k,i+1,j],f[k-1,i,j]);
               if b[i-1,j] then inc(f[k,i-1,j],f[k-1,i,j]);
               if b[i,j+1] then inc(f[k,i,j+1],f[k-1,i,j]);
               if b[i,j-1] then inc(f[k,i,j-1],f[k-1,i,j]);



            end;


   end;
             {
   for k:=0 to t do
   begin
   for i:=1 to n do
   begin
      for j:=1 to m do
      begin
         write(f[k,i,j],' ');
      end;
      writeln;
      end;
      writeln;
   end;
            }
   writeln(f[t,x2,y2]);


end.

标准记忆化搜索 模板题

Program P1088;
var
   ans,n,m,i,j:longint;
   a,f:array[0..101,0..101] of longint;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
function dfs(x,y:longint):longint;
var
   i,j:longint;
begin
   if f[x,y]>0 then exit(f[x,y]);
   dfs:=0;
   if a[x-1,y]<a[x,y] then dfs:=max(dfs,dfs(x-1,y)+1);
   if a[x+1,y]<a[x,y] then dfs:=max(dfs,dfs(x+1,y)+1);
   if a[x,y-1]<a[x,y] then dfs:=max(dfs,dfs(x,y-1)+1);
   if a[x,y+1]<a[x,y] then dfs:=max(dfs,dfs(x,y+1)+1);
   f[x,y]:=dfs;
end;
begin
   read(n,m);
   fillchar(a,sizeof(a),127);
   for i:=1 to n do
      for j:=1 to m do
         read(a[i,j]);
   fillchar(f,sizeof(f),0);
   ans:=0;

   for i:=1 to n do
      for j:=1 to m do
      begin
         if f[i,j]=0 then ans:=max(ans,dfs(i,j));
      end;
   writeln(ans+1);
end.

此题也可用GE做，可是我不会矩阵乘法……

Program P1830;
const
   maxn=28;
   maxf=100007;
   none=-2139062144;
var
   ans,tt,n,i,j,s,t,mid:longint;
   b:array[1..29] of longint;
   h,num:array[0..maxf] of longint;

function hash(x:longint):longint;
var
   i,j:longint;
begin
   hash:=x mod maxf;
   while (num[hash]<>x) and (num[hash]<>none) do
   begin
      hash:=(hash+1) mod maxf;
   end;
   num[hash]:=x;
   exit(hash);
end;
procedure dfs(x,l:longint);
var
   i,j:longint;
begin
   if l=mid+1 then
   begin
      inc(h[hash(x)]);
      exit;
   end;
   for i:=l to mid do
      dfs(x xor b[i],i+1);
   dfs(x,mid+1);

end;
procedure find(x,l:longint);
var
   i,j:longint;
begin
   if l=n+1 then
   begin
      inc(ans,h[hash(x)]);
      exit;
   end;
   for i:=l to n do
      find(x xor b[i],i+1);
   find(x,n+1);

end;

begin
   read(tt);
   while (tt>0) do
   begin
      ans:=0;
      fillchar(b,sizeof(b),0);
      fillchar(num,sizeof(num),128);
      fillchar(h,sizeof(h),0);

      read(n);
      s:=0;
      for i:=1 to n do
      begin
         read(j);
         if j=1 then inc(s,1 shl (i-1));
      end;
      t:=0;
      for i:=1 to n do
      begin
         read(j);
         if j=1 then inc(t,1 shl (i-1));
      end;
      while (true) do
      begin
         read(i,j);
         if (i=0) and (j=0) then break;
         inc(b[i],1 shl (j-1));
      end;
      for i:=1 to n do inc(b[i],1 shl (i-1));
      mid:=n shr 1;
      dfs(s,1);
      find(t,mid+1);
      if ans=0 then writeln('Oh,it''s impossible~!!') else
      writeln(ans);
      dec(tt);
   end;
end.

把一个大矩阵分割成n个矩阵，使它们的方差最小。

g[i,j,k,l,path]表示（i,j） 到 （k,l) 的矩阵分割成path个的最小方差，然后暴力搜索+记忆化

O（n^5) (n<=10) ,无压力水过。

Program b;
const
   maxn=10;
var
   n,m,i,j,k,l,deltax,r:longint;
   delta:double;
   f:array[1..maxn,1..maxn] of longint;
   sum:array[1..maxn,1..maxn,1..maxn,1..maxn] of double;
   g:array[1..maxn,1..maxn,1..maxn,1..maxn,1..maxn] of double;
function min(a,b:double):double;
begin
   if a<b then exit(a) else exit(b);
end;
function dfs(x,y,k,l,path:longint):double;
var
   i,j:longint;
   ans:double;
begin
   if g[x,y,k,l,path]<>0 then exit(g[x,y,k,l,path]);

   if path=1 then
   begin
      g[x,y,k,l,1]:=sum[x,y,k,l]-delta;
      g[x,y,k,l,1]:=g[x,y,k,l,1]*g[x,y,k,l,1];

      exit(g[x,y,k,l,1]);
   end;
   ans:=maxlongint;




   for i:=x to k-1 do
      for j:=1 to path-1 do
         ans:=min(ans,dfs(x,y,i,l,j)+dfs(i+1,y,k,l,path-j));
   for j:=y to l-1 do
      for i:=1 to path-1 do
         ans:=min(ans,dfs(x,y,k,j,i)+dfs(x,j+1,k,l,path-i));


   g[x,y,k,l,path]:=ans;
   exit(ans);

end;
begin
   read(n,m,r);
   deltax:=0;
   for i:=1 to n do
      for j:=1 to m do
      begin
         read(f[i,j]);
         sum[i,j,i,j]:=f[i,j];
         inc(deltax,f[i,j]);

      end;



   delta:=deltax/r;
   for i:=1 to n do
      for j:=1 to m do
      begin
         for k:=i+1 to n do
         begin
            sum[i,j,k,j]:=sum[i,j,k-1,j]+f[k,j];
         end;
         for l:=j+1 to m do
         begin
            sum[i,j,i,l]:=sum[i,j,i,l-1]+f[i,l];
         end;

         for k:=i+1 to n do
            for l:=j+1 to n do
            begin
               sum[i,j,k,l]:=sum[i,j,k-1,l]+sum[i,j,k,l-1]-sum[i,j,k-1,l-1]+f[k,l];
           end;
      end;
   fillchar(g,sizeof(g),0);





   writeln(sqrt(dfs(1,1,n,m,r)/r):2:2);


end.

·