蓝桥杯备战刷题five（自用）

1.数字三角形（方向次数限制，动态规划）

  //如果n为奇数时，最后必然走到最后行最中间的数，如果为偶数，则取中间两个数的最大值，
  //因为向左下走的次数与向右下走的次数相差不能超过 1

#include <iostream>
using namespace std;
const int N=110;
int g[N][N];
int f[N][N];
int n;
int ans;
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=i;j++)
    {
      cin>>g[i][j];
    }
  }
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=i;j++)
    {
      f[i][j]=max(f[i-1][j],f[i-1][j-1])+g[i][j];
    }
  }
  //如果n为奇数时，最后必然走到最后行最中间的数，如果为偶数，则取中间两个数的最大值，
  //因为向左下走的次数与向右下走的次数相差不能超过 1
  if(n%2)cout<<f[n][n/2+1];
  else cout<<max(f[n][n/2],f[n][n/2+1]);
  return 0;
}

2.作物杂交（DFS，递归）

#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int N=2000+100;
int n,m,k,t;
vector<pair<int,int>> fa[N];
int tim[N];
int f[N];//f[i]表示得到i需要花费的时间
map<int,int>mp;
int ans;
int dfs(int t)//倒着推
{
  for(int i=0;i<fa[t].size();i++)
  {
    int a=fa[t][i].first;
    int b=fa[t][i].second;
    if(!mp[a])dfs(a);
    if(!mp[b])dfs(b);
    if(mp[a]&&mp[b])
    {
      mp[t]=1;
      f[t]=min(f[t],max(tim[a],tim[b])+max(f[a],f[b]));
    }
  }
  return f[t];
}
int main()
{
  cin>>n>>m>>k>>t;
  for(int i=1;i<=n;i++)
  {
    cin>>tim[i];
    f[i]=1e9;//初始都是得不到的
  }
  for(int i=1;i<=m;i++)
  {
    int x;
    cin>>x;
    mp[x]=1;
    f[x]=0;//已经有了，得到的时间为0
  }
  for(int i=1;i<=k;i++)
  {
    int a,b,c;
    cin>>a>>b>>c;
    fa[c].push_back({a,b});
  }
  cout<<dfs(t);
  return 0;
}

3.Excel地址（思维）

#include <iostream>
#include <vector>
using namespace std;
int main()
{
  long long n;
  cin>>n;
  vector<char>v;
  while(n)
  {
    n--;//0-25表示A-Z，所以先减一
    v.push_back(n%26+'A');//贡献当前位的表示
    n/=26;//贡献当前位的权
  }
  for(int i=v.size()-1;i>=0;i--)
  cout<<v[i];
  return 0;
}

4.k倍区间（思维）

组合求法，假设%k值相等的区间有n个，根据得出的结论发现任何两个前缀区间的和对k取模的值相等，则由大的前缀区间减掉小的前缀区间所形成的区间的必定是K倍区间。那n个中取任何两个区间都可以组成k倍区间，问有多少k倍区间，就转换成n个区间取两个的情况有多少个，就是Cn2=n*(n-1)/2，所以对于每个%k值相等的区间都添加一次组合就可以算出总共有多少k倍区间了

#include <iostream>
using namespace std;
const int N=1e5+10;
#define ll long long
ll sum;
ll cnt[N];//cnt[i]表示与k取模后余i的个数
int a[N];
int n,k;
ll ans;
int main()
{
  cin>>n>>k;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
    sum=sum+a[i];//计算前缀和
    cnt[sum%k]++;//统计所有前缀和%k后的余数相同个数
  }
  //余数为0直接就是k的倍数l
  ans+=cnt[0];
  //剩下的余数相同的前缀和选2个相同的进行相减
  //即可得到一个子区间且和是k的倍数
  for(int i=0;i<k;i++)
  {
    //组合数cnt[i]个数选两个：C(n,2)=n*(n-1)/2
    //求得的组合数即所有组合即可贡献答案
    ans+=cnt[i]*(cnt[i]-1)/2;
  }
  cout<<ans<<endl;
  return 0;
}

（思路来自Moon） 

 5.包子凑数（动态规划）

#include <iostream>
using namespace std;
const int N=110;
const int M=1e4;
int n;
int a[N];
int f[M];//f[i]=0表示i个包子凑不出来，f[i]=1表示i个包子凑得出来
int gcd(int a,int b)//用来判断是否互质，若全不互质那肯定凑不出来无限个
{
  return b?gcd(b,a%b):a;
}
int main()
{
  cin>>n;
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
  } 
  //求出数组a的最大公因数
  int g=gcd(a[0],a[1]);
  for(int i=2;i<n;i++)
  {
    g=gcd(g,a[i]);
  }
  //如果最大公因数大于1，肯定无法表示的有无限
  if(g>1)
  {
    cout<<"INF"<<endl;
  }
  else
  {
    int ans=0;
   f[0]=1;//0个包子肯定可以
   for(int i=0;i<n;i++)
   {
     for(int j=0;j+a[i]<M;j++)
     {
       if(f[j])
       {
         f[j+a[i]]=1;
       }
     }
   }
   for(int i=0;i<M;i++)
   {
     if(!f[i])
     {
       ans++;
     }
   }
   cout<<ans<<endl;
  }
  return 0;
}

7.分巧克力（二分）

以下是错误代码！！（注意切巧克力是有边的限制的，不能使用面积，面积满足但是形状不满足的巧克力是不合法的！！） 

#include <iostream>
#include <cmath>
using namespace std;
const int N=1e5+10;
#define ll long long
int n,k;
int b=1e9;
int cnt=0;
ll sum[N]; 
int main()
{
  cin>>n>>k;
  for(int i=1;i<=n;i++)
  {
    int h,w;
    cin>>h>>w;
    int kk=(int)sqrt(h*w);
    b=min(b,kk);
    sum[i]=(ll)h*w;
  }
  for(int i=1;i<=n;i++)
  {
    cnt+=(sum[i]/(b*b));
  }
  if(cnt>=k)
  cout<<b<<endl;
  else
  {
    while(cnt<k)
    {
      b--;
      cnt=0;
      for(int i=1;i<=n;i++)
      {
        cnt+=(sum[i]/(b*b));
      }
    }
    cout<<b<<endl;
  }
  return 0;
}

#include <iostream>
#include <cmath>
using namespace std;
const int N=1e5+10;
#define ll long long
int n,k;
int ans;
int h[N],w[N];
bool check(int x)
{
  int cnt=0;
  for(int i=1;i<=n;i++)
  {
    cnt+=(h[i]/x)*(w[i]/x);//有多少个x的高，多少个x的宽，这样才能切出巧克力
  }
  return cnt>=k;
}
int main()
{
  cin>>n>>k;
  for(int i=1;i<=n;i++)
  {
    cin>>h[i]>>w[i];
  }
  int l=1;
  int r=N;
  while(l<=r)
  {
    int mid=(l+r)/2;
    if(check(mid))
    {
      ans=mid;//ans是符合要求的，不断取大的
      l=mid+1;
    }
    else
    {
      r=mid-1;
    }
  }
  cout<<ans<<endl;
  return 0;
}

8.九宫幻方（DFS）

#include <iostream>
#include <map>
using namespace std;
int a[4][4];
int ans[4][4];
int n,cnt;
pair<int,int>p[10];
map<int,int>mp;
bool check()
{
  int sum=a[1][1]+a[2][2]+a[3][3];
  if(sum!=a[1][3]+a[2][2]+a[3][1])return 0;
  for(int i=1;i<=3;i++)
  {
    int temp1=0,temp2=0;
    for(int j=1;j<=3;j++)
    {
      temp1+=a[i][j];
      temp2+=a[j][i];
    }
    if(temp1!=sum||temp2!=sum)return 0;
  }
  return 1;
}
void dfs(int now)
{
  if(now>n)//也就是所有为0的点都已经遍历完了
  {
    if(check())
    {
      cnt++;
      for(int i=1;i<=3;i++)
      {
        for(int j=1;j<=3;j++)
        {
          ans[i][j]=a[i][j];
        }
      }
    }
    return;
  } 
  //x和y表示可以填数的点
  int x=p[now].first,y=p[now].second;
  for(int i=1;i<=9;i++)
  {
    if(mp[i])continue;//填过的不可以再填
    a[x][y]=i;
    mp[i]=1;
    dfs(now+1);
    a[x][y]=0;
    mp[i]=0;
  }
}
int main()
{
  for(int i=1;i<=3;i++)
  {
    for(int j=1;j<=3;j++)
    {
      cin>>a[i][j];
      if(!a[i][j])p[++n]=make_pair(i,j);
      mp[a[i][j]]=1;
    }
  }
  dfs(1);
  if(cnt==1)
  {
    for(int i=1;i<=3;i++)
    {
      for(int j=1;j<=3;j++)
      {
        cout<<ans[i][j]<<" \n"[j==3];
      }
    }
  }
  else cout<<"Too Many\n";
  return 0;
}