本文主要是介绍CUGBACM_Summer_Tranning3 2013长沙现场赛（二分+bfs模拟+DP+几何），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A题：二分
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4791
用lower_bound可以轻松解决，不过比赛的时候逗逼了。
刚开始没有预处理，所以队友给出一组数据的时候没通过，然后一时紧张又想不出什么好的解决办法，所以就没再继续敲代码。实在有点可惜了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define INF 1000000009
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll p[100003],s[100003],pp[100010];
int main()
{int t;cin>>t;while(t--){int n,m,i;ll mm;scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%I64d%I64d",s+i,p+i);pp[n]=s[n]*p[n];for(i=n-1;i>0;i--)pp[i]=min(pp[i+1],p[i]*s[i]);while(m--){scanf("%I64d",&mm);int k=lower_bound(s+1,s+n+1,mm)-s;if(k>=n) printf("%I64d\n",pp[n]);else printf("%I64d\n",min(mm*p[k],pp[k+1]));}}return 0;}
J题：简单DP
dp[i][j]表示打败前i个队伍后且当前挑战者是j的概率。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define INF 1000000009
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
double Map[205][205],dp[10010][205];
int a[10005];
int main()
{int m,n,i,j;while(~scanf("%d",&m)){m=m*(m-1)*(m-2)/6;for(i=0;i<m;i++)for(j=0;j<m;j++)scanf("%lf",&Map[i][j]);scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",a+i);for(i=0;i<m;i++){dp[0][i]=1;for(j=1;j<=n;j++)dp[j][i]=0;}for(i=1;i<=n;i++)for(j=0;j<m;j++){dp[i][j]=max(dp[i][j],dp[i-1][j]*Map[j][a[i]]);dp[i][a[i]]=max(dp[i][a[i]],dp[i-1][j]*Map[j][a[i]]);//cout<<i<<' '<<j<<' '<<dp[i][j]<<' '<<dp[i][a[i]]<<endl;}double ans=0;for(i=0;i<m;i++)ans=max(dp[n][i],ans);printf("%.8f\n",ans);}return 0;}
K题：BFS或者DFS模拟旋转过程
给出10s，而旋转只有6种情况，所以时间是绰绰有余的，所以这道题目就是你能写出来肯定不会TLE，会一A或者2A啥的。
刚开始是我先看的题，自己想的是用DFS，然后大帝看后用BFS的，不过都一样了。都是每一种情况都得遍历一遍。然后孟神他们还真的是用DFS的，时间5s多，我们BFS是1s9，比较快。不过能写出来的都能A了这题。
所以只要有耐心就可以A的题。所以和队友一起搞了一个小时，然后试样例的时候差一点崩溃，这么多代码，第二组样例错了，然后debug原来是判断的时候写错数组名称了。然后交了一WA，然后更加崩溃！！这么多代码哪里知道哪错了呀。后面看旋转类型的时候，发现第一种旋转写错下标了，然后改了两个下标，后面的旋转类型实在代码太多不想debug了就交了，没想到直接A了，哈哈，队友给力！
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
#define INF 1000000009
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct Matrix
{int step;int a[26];
}st,s1,s;
int n;
int BFS()
{int ans=0;queue <Matrix> q;while(!q.empty())q.pop();q.push(st);while(!q.empty()){s1=q.front();int res=(s1.a[7]==s1.a[6]&&s1.a[7]==s1.a[13]&&s1.a[7]==s1.a[12])+(s1.a[0]==s1.a[1]&&s1.a[0]==s1.a[2]&&s1.a[0]==s1.a[3])+(s1.a[16]==s1.a[17]&&s1.a[16]==s1.a[18]&&s1.a[16]==s1.a[19])+(s1.a[20]==s1.a[21]&&s1.a[20]==s1.a[22]&&s1.a[20]==s1.a[23])+(s1.a[4]==s1.a[5]&&s1.a[4]==s1.a[10]&&s1.a[4]==s1.a[11])+(s1.a[8]==s1.a[9]&&s1.a[8]==s1.a[14]&&s1.a[8]==s1.a[15]);if(res>ans){ans=res;if(ans==6)return ans;}q.pop();if(s1.step<n){int a,b;s=s1;a=s.a[1];b=s.a[3];s.a[1]=s.a[7];s.a[3]=s.a[13];s.a[7]=s.a[17];s.a[13]=s.a[19];s.a[17]=s.a[21];s.a[19]=s.a[23];s.a[21]=a;s.a[23]=b;a=s.a[9];s.a[9]=s.a[8];s.a[8]=s.a[14];s.a[14]=s.a[15];s.a[15]=a;s.step=s1.step+1;q.push(s);s=s1;a=s.a[1];b=s.a[3];s.a[1]=s.a[21];s.a[3]=s.a[23];s.a[21]=s.a[17];s.a[23]=s.a[19];s.a[17]=s.a[7];s.a[19]=s.a[13];s.a[7]=a;s.a[13]=b;a=s.a[8];s.a[8]=s.a[9];s.a[9]=s.a[15];s.a[15]=s.a[14];s.a[14]=a;s.step=s1.step+1;q.push(s);s=s1;a=s.a[6];b=s.a[7];s.a[6]=s.a[8];s.a[7]=s.a[9];s.a[8]=s.a[23];s.a[9]=s.a[22];s.a[23]=s.a[4];s.a[22]=s.a[5];s.a[4]=a;s.a[5]=b;a=s.a[0];s.a[0]=s.a[2];s.a[2]=s.a[3];s.a[3]=s.a[1];s.a[1]=a;s.step=s1.step+1;q.push(s);s=s1;a=s.a[6];b=s.a[7];s.a[6]=s.a[4];s.a[7]=s.a[5];s.a[4]=s.a[23];s.a[5]=s.a[22];s.a[23]=s.a[8];s.a[22]=s.a[9];s.a[8]=a;s.a[9]=b;a=s.a[0];s.a[0]=s.a[1];s.a[1]=s.a[3];s.a[3]=s.a[2];s.a[2]=a;s.step=s1.step+1;q.push(s);s=s1;a=s.a[3];b=s.a[2];s.a[3]=s.a[5];s.a[2]=s.a[11];s.a[5]=s.a[16];s.a[11]=s.a[17];s.a[16]=s.a[14];s.a[17]=s.a[8];s.a[14]=a;s.a[8]=b;a=s.a[6];s.a[6]=s.a[12];s.a[12]=s.a[13];s.a[13]=s.a[7];s.a[7]=a;s.step=s1.step+1;q.push(s);s=s1;a=s.a[3];b=s.a[2];s.a[3]=s.a[14];s.a[2]=s.a[8];s.a[14]=s.a[16];s.a[8]=s.a[17];s.a[16]=s.a[5];s.a[17]=s.a[11];s.a[5]=a;s.a[11]=b;a=s.a[6];s.a[6]=s.a[7];s.a[7]=s.a[13];s.a[13]=s.a[12];s.a[12]=a;s.step=s1.step+1;q.push(s);}}return ans;
}
int main()
{while(~scanf("%d",&n)){for(int i=0;i<24;i++)scanf("%d",&st.a[i]);st.step=0;int a=BFS();printf("%d\n",a);}return 0;
}
这篇关于CUGBACM_Summer_Tranning3 2013长沙现场赛（二分+bfs模拟+DP+几何）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
