小晴天系列—暴力
A:题目大意：给出一个n，在1~n这n个数里面任选三个数，求它们的最小公倍数。找到这个最大的ans。
思路：如果n是奇数的话，那么n，n-1，n-2必然互质，所以ans=n*(n-1)*(n-2)
如果n是偶数的话，而且n也是3的倍数的话，那么最大的最小公倍数肯定是(n-1)*(n-2)*(n-3)
而且n不是3的倍数的话，那么最大的最小公倍数肯定是n*(n-1)*(n-3)。
代码如下：
1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 int main() 5 { 6 long long sum,n; 7 while (cin>>n){ 8 if(n==1) 9 { 10 printf("1 "); 11 continue; 12 }else if(n==2) 13 { 14 printf("2 "); 15 continue; 16 } 17 else if(n%2!=0) 18 { 19 sum=n*(n-1)*(n-2); 20 }else 21 { 22 if(n%3==0) 23 { 24 sum=(n-3)*(n-1)*(n-2); 25 }else 26 { 27 sum=n*(n-1)*(n-3); 28 } 29 } 30 printf("%lld ",sum);} 31 return 0; 32 }
B：题目大意：
第1行两个正整数n, m (1 ≤ n, m ≤ 1000)表示地图大小，接下来n行每行m个字符描述地图。
. 表示此处为空地
* 表示此处为障碍（激光不可穿过，激光路径打到障碍时就结束）
T 代表瑶瑶的坦克位置
E 代表敌人
/ 代表按 左下-右上 放置的镜子
代表按 左上-右下 放置的镜子
寻找最大的能攻击到的敌人数。
例如：
5 5 .*/E E*.*. E*TEE .../ .*EE 答案是4.
代码如下：
1 #include <cstdio> 2 #include <cstring> 3 #define max(a,b) a>b?a:b 4 using namespace std; 5 6 char s[1010][1010]; 7 int mapp[1010][1010]; 8 int n,m; 9 int x,y; 10 int go(int x,int y,int way) 11 { 12 memset(mapp,0,sizeof(mapp)); 13 int sum=0; 14 while (1) 15 { 16 if(s[x][y]=='*') return sum; 17 if(mapp[x][y]>=2) return sum; 18 if(s[x][y]=='E'&&mapp[x][y]==0) sum++; 19 mapp[x][y]++; 20 if(s[x][y]=='/') 21 { 22 switch(way) 23 { 24 case 0:x=x-1;y=y;way=1;break; 25 case 1:y=y+1;x=x;way=0;break; 26 case 2:x=x+1;y=y;way=3;break; 27 case 3:y=y-1;x=x;way=2;break; 28 } 29 } 30 else if(s[x][y]=='\') 31 { 32 switch (way) 33 { 34 case 0:way=3;x=x+1;y=y;break; 35 case 1:way=2;x=x;y=y-1;break; 36 case 2:way=1;x=x-1;y=y;break; 37 case 3:way=0;x=x;y=y+1;break; 38 } 39 } 40 else if(s[x][y]=='.'||s[x][y]=='E') 41 { 42 switch (way) 43 { 44 case 0:x=x;y=y+1;break; 45 case 1:x=x-1;y=y;break; 46 case 2:x=x;y=y-1;break; 47 case 3:x=x+1;y=y;break; 48 } 49 } 50 51 } 52 return sum; 53 } 54 int main() 55 { 56 scanf ("%d %d",&n,&m); 57 int i,j,k; 58 for(i=0;i<=n+1;i++) 59 { 60 for(j=0;j<=m+1;j++) 61 { 62 if(i==0||j==0||i==n+1||j==m+1) 63 { 64 s[i][j]='*'; 65 continue; 66 } 67 scanf (" %c",&s[i][j]); 68 if(s[i][j]=='T') 69 { 70 x=i,y=j; 71 s[i][j]='.'; 72 } 73 } 74 } 75 int ans=0; 76 for(i=0;i<4;i++) 77 { 78 ans=max(ans,go(x,y,i)); 79 } 80 printf("%d ",ans); 81 return 0; 82 }
C：题目大意：一个三位数乘以一个两位数，得到一个四位数+一个三位数，加完之后得到一个五位数。
输入五行，以字符串输入。例如：
*** ** 3384 846 *****
求打*的位置有几种填法。暴力枚举两个乘数。然后对每一个得到的结果进行判断是否符合题意。代码如下：
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 6 char s[5][5]; 7 8 int ok1(int i) 9 { 10 int a,b,c,d; 11 a=i/100;b=(i%100)/10;c=(i%10); 12 if(s[0][0]!='*'&&s[0][0]-'0'!=a) return 0; 13 if(s[0][1]!='*'&&s[0][1]-'0'!=b) return 0; 14 if(s[0][2]!='*'&&s[0][2]-'0'!=c) return 0; 15 return 1; 16 } 17 int ok2(int j) 18 { 19 int a,b; 20 a=j/10;b=j%10; 21 if(s[1][0]!='*'&&s[1][0]-'0'!=a) return 0; 22 if(s[1][1]!='*'&&s[1][1]-'0'!=b) return 0; 23 return 1; 24 } 25 int ok3(int m) 26 { 27 int a,b,c,d; 28 a=m/1000;b=(m%1000)/100;c=(m%100)/10;d=(m%10); 29 if(s[2][0]!='*'&&s[2][0]-'0'!=a) return 0; 30 if(s[2][1]!='*'&&s[2][1]-'0'!=b) return 0; 31 if(s[2][2]!='*'&&s[2][2]-'0'!=c) return 0; 32 if(s[2][3]!='*'&&s[2][3]-'0'!=d) return 0; 33 return 1; 34 } 35 int ok4(int n) 36 { 37 int a,b,c; 38 a=n/100;b=(n%100)/10;c=(n%10); 39 if(s[3][0]!='*'&&s[3][0]-'0'!=a) return 0; 40 if(s[3][1]!='*'&&s[3][1]-'0'!=b) return 0; 41 if(s[3][2]!='*'&&s[3][2]-'0'!=c) return 0; 42 return 1; 43 } 44 int ok5(int sum) 45 { 46 int a,b,c,d,e; 47 a=sum/10000;b=(sum%10000)/1000;c=(sum%1000)/100;d=(sum%100)/10;e=sum%10; 48 if(s[4][0]!='*'&&s[4][0]-'0'!=a) return 0; 49 if(s[4][1]!='*'&&s[4][1]-'0'!=b) return 0; 50 if(s[4][2]!='*'&&s[4][2]-'0'!=c) return 0; 51 if(s[4][3]!='*'&&s[4][3]-'0'!=d) return 0; 52 if(s[4][4]!='*'&&s[4][4]-'0'!=e) return 0; 53 return 1; 54 } 55 int main() 56 { 57 int t; 58 scanf ("%d",&t); 59 while (t--) 60 { 61 int i,j,k,sum=0; 62 for(i=0;i<5;i++) 63 scanf ("%s",s[i]); 64 for(i=100;i<=999;i++) 65 { 66 for(j=10;j<=99;j++) 67 { 68 int m=i*(j%10); 69 int n=i*(j/10); 70 if(ok1(i)&&ok2(j)&&m>=1000&&m<10000&&n>=100&&n<1000) 71 { 72 if(ok3(m)&&ok4(n)&&(m+n*10)>=10000&&ok5(m+n*10)) 73 sum++; 74 } 75 } 76 } 77 printf("%d ",sum); 78 } 79 return 0; 80 }
D题：还有木有解决的问题。以后更新。
E题：给一个数列，给一个k。最大元素大于K的连续子序列的个数。
虽然是暴力专题，可是还是用dp来解的。dp[i]表示，包含第i个数之前的所有数中的子序列的个数。
那么如果a[i]>k，dp[i]=i+1,否则dp[i]=dp[i-1]。
代码如下：
1 #include <cstdio> 2 #include <cstring> 3 #define max(a,b) a>b?a:b 4 int dp[200005],a[200005]; 5 int n,k; 6 int main() 7 { 8 int t; 9 scanf ("%d",&t); 10 while (t--) 11 { 12 scanf ("%d%d",&n,&k); 13 int i,j; 14 for(i=0;i<n;i++) 15 { 16 scanf ("%d",&a[i]); 17 if(a[i]>k) 18 dp[i]=1; 19 else 20 dp[i]=0; 21 } 22 for(i=1;i<n;i++) 23 { 24 if(a[i]>k) 25 dp[i]=i+1; 26 else 27 dp[i]=dp[i-1]; 28 } 29 int sum=0; 30 for(i=0;i<n;i++) 31 sum+=dp[i]; 32 printf("%d ",sum); 33 } 34 return 0; 35 }
F题：题目大意：这里有m个苹果，把他们分别放在n个篮子里。有多少种放法。篮子可以允许放0个。但是，1 2 1 和1 1 2是一种情况。
这个问题属于m的n划分问题。可以用dp来做。
dp[i][j]代表j的i划分的个数。 递推式：dp[i][i]=dp[i][j-i]+dp[i-1][j];
代码如下：
1 #include <cstdio> 2 int dp[100][100]; 3 int main() 4 { 5 int t; 6 scanf ("%d",&t); 7 while (t--) 8 { 9 int m,n,i,j,k; 10 scanf ("%d %d",&n,&m); 11 dp[0][0]=1; 12 for(i=1;i<=m;i++) 13 { 14 for(j=0;j<=n;j++) 15 { 16 if(j-i>=0) 17 dp[i][j]=dp[i-1][j]+dp[i][j-i]; 18 else 19 dp[i][j]=dp[i-1][j]; 20 } 21 } 22 printf("%d ",dp[m][n]); 23 } 24 return 0; 25 }
G：题目大意：搜索整个图，找到图中最大的连通的点数。
dfs搜索整个图。dfs入门题目。
代码如下：
1 #include <cstdio> 2 #include <cstring> 3 #define max(a,b) a>b?a:b 4 using namespace std; 5 6 int num[25][25]; 7 int n,m; 8 int dir[8][2]={1,0,0,1,-1,0,0,-1,1,1,-1,1,-1,-1,1,-1};//搜索八个方向。 9 int sum; 10 int ok(int x,int y) 11 { 12 if(x>=0&&x<n&&y<m&&y>=0) 13 return 1; 14 return 0; 15 } 16 void dfs(int x,int y) 17 { 18 if(num[x][y]) 19 sum++; 20 num[x][y]=0; 21 for(int i=0;i<8;i++) 22 { 23 int xx=x+dir[i][0]; 24 int yy=y+dir[i][1]; 25 if(ok(xx,yy)&&num[xx][yy]) 26 dfs(xx,yy); 27 } 28 } 29 int main() 30 { 31 int t; 32 scanf ("%d",&t); 33 while (t--) 34 { 35 scanf("%d %d",&n,&m); 36 int i,j,k; 37 for(i=0;i<n;i++) 38 for(j=0;j<m;j++) 39 scanf ("%d",&num[i][j]); 40 int maxx=0; 41 for(i=0;i<n;i++) 42 for(j=0;j<m;j++) 43 if(num[i][j]) 44 { 45 sum=0; 46 dfs(i,j); 47 maxx=max(maxx,sum); 48 } 49 printf("%d ",maxx); 50 } 51 return 0; 52 }
好了。。还有两题没有ac，等题解发了再更新。
其实还是有很多题目不会做。。还需要很努力很努力