题目来源：牛客网

这次是我们队一起打的，题目不难，但是我还是写的比较慢，还是有点菜，赛后一周才补的差不多，DP，搜索，简单的规律和博弈都涉及到了，可以说是练手的题把。

A-小乐乐的组合数+（规律）

题目链接：https://ac.nowcoder.com/acm/contest/301/A

题目大意：中文题，好理解

思路：首先处理出来前七位能组合成多少个（七个数一循环）然后看有多少组循环，再加上多出来的个数即可

AC：

//#pragma comment(linker, "/STACK:1024000000,1024000000")#include<stdio.h>
#include<string.h> 
#include<math.h> //#include<map>  
//#include<set>
#include<deque> 
#include<queue> 
#include<stack> 
#include<bitset>
#include<string> 
#include<fstream>
#include<iostream> 
#include<algorithm> 
using namespace std; #define ll long long 
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
//  register
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;int arr[10];int main()
{int n,m,k;while(~scanf("%d%d",&n,&m)){clean(arr,0);ll ans=0,res=0;for(int i=1;i<7;++i){for(int j=1;j*7-i<=m;++j)res++;arr[i]=res;}res+=(m/7);
//      for(int i=1;i<7;++i)
//          cout<<arr[i]<<" ";
//      cout<<endl;
//      cout<<res<<endl;if(n<7)printf("%d\n",arr[n]);else{printf("%lld\n",res*(n/7)+arr[n%7]);}}}

B-小乐乐搭积木（状压DP）

题目链接：https://ac.nowcoder.com/acm/contest/301/B

题目大意：中文题，铺砖问题，状压DP入门

思路：状压DP板子

AC：

C-小乐乐玩木桶（巨水）

题目链接：https://ac.nowcoder.com/acm/contest/301/C

题目大意：给出底面积和木板长度，求容积

思路：找到最短的模板，然后代公式

AC：

int main()
{int n,s;while(~scanf("%d%d",&n,&s)){int minl=INF,l;for(int i=1;i<=n;++i){scanf("%d",&l);minl=min(minl,l);}printf("%d\n",s*minl);}}

D-小乐乐玩木桶+（巨水排序）

题目链接：https://ac.nowcoder.com/acm/contest/301/D

题目大意：还是上一题的意思，只不过能那三个木板

思路：排序，然后选出第三短的木板，套公式

AC：

int arr[3];bool cmp(int a,int b)
{return a>b;
}int main()
{int n,s;while(~scanf("%d%d",&n,&s)){int minl=INF,l;for(int i=1;i<=n;++i){sort(arr,arr+3,cmp);scanf("%d",&l);arr[2]=max(arr[2],l);}sort(arr,arr+3,cmp);printf("%d\n",s*arr[2]);}}

E-小乐乐匹配字符串（简单DP）

题目链接：https://ac.nowcoder.com/acm/contest/301/E

题目大意：中文题，

思路：最长公共子序列，DP入门

AC：

char s1[1010],s2[1010];
int dp[1010][1010];int main()
{while(cin>>s1>>s2){clean(dp,0);int l1=strlen(s1),l2=strlen(s2);for(int i=1;i<=l1;++i){for(int j=1;j<=l2;++j){if(s1[i-1]==s2[j-1])dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j]);elsedp[i][j]=max(dp[i][j-1],dp[i-1][j]);}}cout<<dp[l1][l2]<<endl;clean(s1,'\0');clean(s2,'\0');}
}

F-小乐乐下象棋（简单DP）

题目链接：https://ac.nowcoder.com/acm/contest/301/F

题目大意：中文题，如题

思路：对于每走一步，都加上它上一步的结果，dp[i][j]=(dp[nx][ny]+dp[i][j])%mod

AC：

//#pragma comment(linker, "/STACK:1024000000,1024000000")#include<stdio.h>
#include<string.h> 
#include<math.h> //#include<map>  
//#include<set>
#include<deque> 
#include<queue> 
#include<stack> 
#include<bitset>
#include<string> 
#include<fstream>
#include<iostream> 
#include<algorithm> 
using namespace std; #define ll long long 
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
const int MAXN=1e6+10;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;int fx[8]={2,2,-2,-2,1,1,-1,-1},fy[8]={1,-1,1,-1,2,-2,2,-2};
ll dp[2][210][210];int main()
{std::ios::sync_with_stdio(false);int n,m,k;while(cin>>n>>m>>k){int crt=0,next=1;clean(dp[crt],0);clean(dp[next],0);dp[crt][0][0]=1;for(int i=1;i<=k;++i)//走k次{clean(dp[next],0);for(int j=0;j<n;++j)//遍历地图{for(int z=0;z<m;++z){//对于每个点，如果能够走过，则+;if(dp[crt][j][z]!=0){for(int go=0;go<8;++go)//遍历四个方向{int nx=j+fx[go];int ny=z+fy[go];if(nx>=0&&ny>=0&&nx<n&&ny<m)dp[next][nx][ny]=(dp[next][nx][ny]+dp[crt][j][z])%mod;}//cout<<dp[crt][j][z]<<" "<<dp[next][j][z]<<endl;}}}swap(crt,next);}cout<<dp[crt][n-1][m-1]%mod<<endl;}
}

G-小乐乐打游戏（简单搜索）

题目链接：https://ac.nowcoder.com/acm/contest/301/G

题目大意：中文题，如题

思路：类似之前做的鬼抓人的那个题hdu-3085-Nightmare Ⅱ，还更简单，随便什么搜索，然后判断一下曼哈顿距离

AC：

//#pragma comment(linker, "/STACK:1024000000,1024000000")#include<stdio.h>
#include<string.h>
#include<math.h>//#include<map> 
//#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;#define ll long long
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
//  register
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;struct node{int x,y,tim;
};char mp[1010][1010];
int vis[1010][1010];
int fx[4]={0,0,1,-1},fy[4]={1,-1,0,0};
queue<node> que;
node F,E,S;
int n,m,tim;int judge(node e)
{if(e.x>=1&&e.y>=1&&e.x<=n&&e.y<=m)//在地图{if(mp[e.x][e.y]!='#'&&vis[e.x][e.y]==0)//不是墙&&没走过{if(abs(e.x-F.x)+abs(e.y-F.y)>e.tim)return 1;
//            if(F.x+e.tim<e.x||F.y+e.tim<e.y)//不会被烧死
//                return 1;}}return 0;
}void bfs()
{que.push(S);vis[S.x][S.y]=1;while(que.size()){node a=que.front();que.pop();if(mp[a.x][a.y]=='E')//出来了{cout<<"PIG PIG PIG!"<<endl;return ;}for(int i=0;i<4;++i){node e;e.x=a.x+fx[i],e.y=a.y+fy[i],e.tim=a.tim;if(judge(e))//不能走{e.tim++;que.push(e);vis[e.x][e.y]=1;   }//cout<<e.x<<" "<<e.y<<endl;}}cout<<"A! WO SI LA!"<<endl;
}int main()
{std::ios::sync_with_stdio(false);while(cin>>n>>m){clean(vis,0);while(que.size())que.pop();for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cin>>mp[i][j];if(mp[i][j]=='F')F.x=i,F.y=j;if(mp[i][j]=='S')S.x=i,S.y=j,S.tim=0;if(mp[i][j]=='E')E.x=i,E.y=j;}}bfs();}
}

H-小乐乐学数学

题目链接：https://ac.nowcoder.com/acm/contest/301/H

题目大意：

思路：现在还不会emmmmm......

I-小乐乐学博弈（简单博弈，巴士+尼姆）

题目链接：https://ac.nowcoder.com/acm/contest/301/I

题目大意：中文题

思路：多考虑两个就知道了，简单博弈

AC：

int main()
{int n,m,k;while(~scanf("%d%d%d",&n,&m,&k)){int maxnum=max(n,m),minnum=min(n,m);if(minnum==0&&maxnum==0){printf("LAOZI CHUI SI NI!\n");continue;}if(minnum==0){if(maxnum%k==0)printf("LAOZI CHUI SI NI!\n");elseprintf("HAI YOU SEI!\n");continue;}if(maxnum%minnum<=k)printf("HAI YOU SEI!\n");elseprintf("LAOZI CHUI SI NI!\n");}}

J-小乐乐和25（暴力）

题目链接：https://ac.nowcoder.com/acm/contest/301/J

题目大意：中文题

思路：对于每种情况都暴力转移最少的次数，然后比较，25，50，75，00

AC：

//#pragma comment(linker, "/STACK:1024000000,1024000000")#include<stdio.h>
#include<string.h>
#include<math.h>//#include<map> 
//#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;#define ll long long
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
//  register
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;int cnt(string s,char a,char b)
{int ans=0;int len=s.size();int p=len-1;for(;p>=0;--p)//找最后面的数{if(s[p]==b)break;}if(p==-1)//没有找到return INF;for(int i=p;i<len-1;++i)//统计次数{swap(s[i],s[i+1]);ans++;}p=len-2;for(;p>=0;--p)//找前面的数{if(s[p]==a)break;}if(p==-1)return INF;for(int i=p;i<len-2;++i)//统计次数{swap(s[i],s[i+1]);ans++;}for(p=0;p<len;++p)//将这个数前面的0消掉{if(s[p]!='0')break;}for(;p>=1;--p)//把这个数的0放到后面{swap(s[p],s[p-1]);ans++;}if(s[len-1]==b&&s[len-2]==a)return ans;return INF;
}int main()
{std::ios::sync_with_stdio(false);string s;while(cin>>s){if(s=="0")cout<<0<<endl;else{int res=INF;res=min(res,cnt(s,'0','0'));res=min(res,cnt(s,'2','5'));res=min(res,cnt(s,'5','0'));res=min(res,cnt(s,'7','5'));if(res==INF)cout<<-1<<endl;elsecout<<res<<endl;}}
}