时间限制: 1 s 空间限制: 16000 KB 题目等级 : 黄金 Gold
某同学考试，在N*M的答题卡上写了A,B,C,D四种答案。
他做完了，又不能交，一看表，离打铃还有N久。
他开始玩一个游戏：选一个格子X,Y，从这个格子出发向4个方向找相同的选项，找到的再如此。
求形成的图形的面积。（一个选项占一个单位面积）
N M X Y
答题卡（矩阵）
面积
3 3 1 2
A C B
C C C
D C A
5
N,M<=15.
对于33%数据，只有A。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 #define maxn 16 6 int n,m,sx,sy,ans=0;; 7 int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; 8 char map[maxn][maxn]; 9 bool vis[maxn][maxn]; 10 void DFS(int x,int y){ 11 ans++;vis[x][y]=true; 12 for(int i=0;i<4;i++){ 13 int nx=x+dx[i],ny=y+dy[i]; 14 if(nx<=n&&ny<=m&&ny>=1&&nx>=1 15 &&map[x][y]==map[nx][ny]&&!vis[nx][ny]) 16 DFS(nx,ny); 17 } 18 } 19 int main() 20 { 21 scanf("%d%d%d%d",&n,&m,&sx,&sy); 22 for(int i=1;i<=n;i++) 23 for(int j=1;j<=m;j++) 24 cin>>map[i][j]; 25 DFS(sx,sy); 26 printf("%d\n",ans); 27 return 0; 28 }
时间限制: 1 s 空间限制: 256000 KB 题目等级 : 黄金 Gold
对于数列A，如果添加运算符号,+或-,使得式子能够被k整除,则输出Divisible,否则输出Not divisible
第一行,N,K
第二行,描述A数列
如题目所示
2 3
1 4
Divisible
注意,第一个数不能添加符号.
N<=10000,K<=100.
全部TLE：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cstdlib> 5 using namespace std; 6 const int maxn = 10000; 7 int n,k,a[maxn]; 8 bool flag=0; 9 void DFS(int sum,int pos){ 10 if(pos>n)return; 11 if(pos==n && sum%k==0){ 12 flag=true; 13 return; 14 } 15 DFS(sum-a[pos+1],pos+1); 16 DFS(sum+a[pos+1],pos+1); 17 } 18 int main() 19 { 20 scanf("%d%d",&n,&k); 21 for(int i=1;i<=n;i++) 22 scanf("%d",&a[i]); 23 DFS(a[1],1); 24 if(!flag)printf("Not divisible"); 25 if(flag)printf("Divisible"); 26 return 0; 27 }
记忆话搜索：
1 #include <stdio.h> 2 #include <stdlib.h> 3 int a[10005],vis[10005][105],n,k; 4 void dfs(int pos,int sum){ 5 if(vis[pos][sum])return; 6 vis[pos][sum]=1; 7 if(pos==n ){ 8 if(vis[n][0]==1){ 9 printf("Divisible"); 10 exit(0); 11 } 12 return ; 13 } 14 dfs(pos+1,(sum+a[pos])%k); 15 dfs(pos+1,(abs(sum-a[pos]))%k); 16 } 17 int main() 18 { 19 scanf("%d%d",&n,&k); 20 for(int i=0;i<n;i++) 21 scanf("%d",&a[i]); 22 dfs(1,(abs(a[0]))%k); 23 printf("Not divisible"); 24 return 0; 25 }
原文：http://www.cnblogs.com/suishiguang/p/6444363.html