2020 Multi-University Training Contest 2(补题)

Lead of Wisdom
思路：暴力搜索。

#include<iostream>
typedef long long ll;
const int maxn=60;
int n,m,i,j,x,cnt[maxn],z[maxn],e[maxn][maxn][4];//z用于存储cnt不等于0的部分，e用于存储a，b，c，d; 
ll ans;
void dfs(int x,int a,int b,int c,int d){
  if(x>m){//x>m，搜索分支结束 
    ll tmp=1LL*a*b*c*d;
    if(tmp>ans)ans=tmp;
    return;
  }
  int num=cnt[x];
  if(!num){//当cnt等于0跳过 
    dfs(z[x],a,b,c,d);
    return;
  }
  for(int i=1;i<=num;i++)dfs(x+1,a+e[x][i][0],b+e[x][i][1],c+e[x][i][2],d+e[x][i][3]);
}
int main(){
    int t; 
  scanf("%d",&t);
  while(t--){
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)cnt[i]=0;
    for(int i=0;i<n;i++)
    {
      scanf("%d",&x);
      cnt[x]++;
      for(j=0;j<4;j++)scanf("%d",&e[x][cnt[x]][j]);
    }
    x=m+1;
    for(i=m;i;i--){
      z[i]=x;
      if(cnt[i])x=i;//当cnt不为零，则后一位记录 
    }
    ans=0;
    dfs(1,100,100,100,100);
    printf("%lld\n",ans);
  }
}

The Oculus
直接根据A*B与C的差找到斐波那契数列中缺少的那一个。A与B与C取unsigned long long。

#include<iostream>
typedef unsigned long long ull;
const int maxn=3000005;
int i;
ull A,B,C,f[maxn];
ull read(){
  int n,i,x;
  ull ans=0;
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&x);
    if(x)ans+=f[i];
  }
  return ans;
}
int main(){
  for(f[1]=1,f[2]=2,i=3;i<3e6+5;i++)f[i]=f[i-1]+f[i-2];
  int t;
  scanf("%d",&t);
  while(t--){
    A=read();
    B=read();
    C=read();
    A*=B;
    for(i=1;C+f[i]!=A;i++);
    printf("%d\n",i);
  }
}