2024初三年前集训测试3

\(T1\) 夕景昨日 \(90pts\)

• 部分分

  • \(10pts\) ：输出 No 。
  • \(20pts\) ：\(2^{n}\) 的 \(DFS\) 暴力枚举能得到的所有数，用 map 里进行判断。
  • \(90pts\) ：输出 Yes 。

• 正解

  • 观察到 \(1 \le n \le 100000,0 \le a_{i} \le 500000\) 。
  • 猜测 \(n\) 到达一定数量级时，一定有解。 \(n\) 个数最多产生 \(2^{n}\) 个数，但由 \(a_{i}\) 最多配对出 \(nV\) 个数。经打表，枚举 \(V=1 \sim 500000\) 解关于 \(n\) 的不等式 \(2nV \le 2^{n}\) ，解得当 \(V=500000\) 时，\(n\) 的最小整数解为 \(25\) 。
    • 严格意义上来说，极限数据应该造成 \(1,2,4,8,16,32, \dots\) 。
  • 故当 \(n \le 25\) 时，仍选择用 \(DFS\) 暴力枚举；否则，一定有解。
  点击查看代码

  ll a[100001],flag=0;
  map<ll,ll>vis;
  void dfs(ll x,ll now,ll n)
  {
      if(x==n)
      {
          vis[now]++;
          if(vis[now]==2)
          {
              flag=1;
          }
      }
      else
      {
          dfs(x+1,now+a[x+1],n);
          dfs(x+1,now-a[x+1],n);
      }
  }
  int main()
  {
      ll n,i;
      cin>>n;
      for(i=1;i<=n;i++)
      {
          cin>>a[i];
      }
      if(n<=25)
      {
          dfs(0,0,n);
          if(flag==0)
          {
              cout<<"No"<<endl;
          }
          else
          {
              cout<<"Yes"<<endl;
          }
      }
      else
      {
          cout<<"Yes"<<endl;
      }
      return 0;
  }
  

\(T2\) 透明答案 \(70pts\)

• 部分分
  • \(30pts\) ：输出 Bob 。
  • \(70pts\) ：输出 Ayano 。

\(T3\) 界外科学 \(50pts\)

• 部分分

  • \(50pts\) ：超大背包 \(2^{n}\) 枚举。

    点击查看代码

    ll a[50],b[50],ans=0;
    void dfs(ll x,ll worth,ll now,ll n,ll m)
    {
        if(x==n)
        {
            ans=(worth<=m)?max(ans,now):ans;           
        }
        else
        {
            dfs(x+1,worth^a[x+1],now+b[x+1],n,m);
            dfs(x+1,worth,now,n,m);
        }
    }
    int main()
    {
        ll n,m,i;
        cin>>n>>m;
        for(i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        for(i=1;i<=n;i++)
        {
            cin>>b[i];
        }
        dfs(0,0,0,n,m);
        cout<<ans<<endl;
        return 0;
    }
    

  • \(100pts\) ：输出 \(\sum\limits_{i=1}^{n}b_{i}\) 。

\(T4\) 回忆补时 \(30pts\)

• 部分分

  • \(30pts\) ：\(n^{2}q\) 暴力枚举。

    点击查看代码

    ll k[100001],b[100001];
    int main()
    {
        ll n,q,x,ans,i,j,h;
        scanf("%lld",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%lld%lld",&k[i],&b[i]);
        }
        scanf("%lld",&q);
        for(i=1;i<=q;i++)
        {
            scanf("%lld",&x);
            ans=0;
            for(j=1;j<=n;j++)
            {
                for(h=j+1;h<=n;h++)
                {
                    ans=max(ans,max(k[h]*(k[j]*x+b[j])+b[h],k[j]*(k[h]*x+b[h])+b[j]));
                }
            }
            printf("%lld\n",ans);
        }
        return 0;
    }
    

• 正解

  点击查看官方题解

  

  

总结

• 打到 \(8:40\) 就去打矩阵快速幂了。
• 要学会通过值域猜测时间复杂度和判断答案范围。

后记

• 没有大样例，差评。
• 建议本场比赛改名为暴力骗分/良心送分模拟赛。