2024初三集训模拟测试4

\(T1\) 打赌 \(0pts\)

\(T2\) 舞会 \(0pts\)

\(T3\) 最小生成树 \(0pts\)

• 经打表，有最小生成树的边权和为 \(n-1\) ，构造每条边上的两端点互质即可。

• 故 \(\prod\limits_{i=1}^{n}\varphi(i)\) 即为所求。

  点击查看代码

  const ll p=100000007;
  ll phi[40000],prime[40000],vis[40000],len=0;
  void euler(ll n)
  {
  	memset(vis,0,sizeof(vis));
  	phi[1]=1;
  	for(ll i=2;i<=n;i++)
  	{
  		if(vis[i]==false)
  		{
  			len++;
  			prime[len]=i;
  			phi[i]=i-1;
  		}
  		for(ll j=1;j<=len&&i*prime[j]<=n;j++)
  		{
  			vis[i*prime[j]]=1;
  			if(i%prime[j]==0)
  			{
  				phi[i*prime[j]]=phi[i]*prime[j];
  				break;
  			}
  			else
  			{
  				phi[i*prime[j]]=phi[i]*(prime[j]-1);
  			}
  		}
  	}
  }
  int main()
  {
  	freopen("mst.in","r",stdin);
  	freopen("mst.out","w",stdout);
  	ll n,ans=1,i;
  	cin>>n;
  	euler(n);
  	for(i=1;i<=n;i++)
  	{
  		ans=ans*phi[i]%p;
  	}
  	cout<<ans<<endl;
  	fclose(stdin);
  	fclose(stdout);
  	return 0;
  }
  

\(T4\) 买汽水 \(0pts\)

• 部分分

  • \(50pts\)

    • 超大背包，暴力 \(DFS\) 枚举每天买或不买饮料。

    • 时间复杂度为 \(O(2^{n})\) 。

      点击查看代码

      ll p[50],ans=0;
      void dfs(ll x,ll n,ll m,ll worth,ll weight)
      {
      	if(x==n+1)
      	{
      		if(weight<=m)
      		{
      			ans=max(ans,worth);
      		}
      	}
      	else
      	{
      		if(weight+p[x]<=m)
      		{
      			dfs(x+1,n,m,worth+p[x],weight+p[x]);
      		}
      		dfs(x+1,n,m,worth,weight);
      	}
      }
      int main()
      {
      	freopen("drink.in","r",stdin);
      	freopen("drink.out","w",stdout);
      	ll n,m,i;
      	cin>>n>>m;
      	for(i=1;i<=n;i++)
      	{
      		cin>>p[i];
      	}
      	dfs(1,n,m,0,0);
      	cout<<ans<<endl;
      	fclose(stdin);
      	fclose(stdout);
      	return 0;
      }
      

• 正解

  • 考虑优化搜索过程，使用双向搜索。具体地，对于 \([1,\left\lfloor \frac{n}{2}\right\rfloor]\) 进行第一遍搜索，对于得到的价值存到一个 set 里面。对于 \([\left\lfloor \frac{n}{2}\right\rfloor+1,n]\) 进行第二遍搜索，对于得到的价值在 set 里面找到满足 \(\le m-\) 当前重量的最大价值，进行转移即可。
  • 时间复杂度为 \(O(2^{\frac{n}{2}}\log n)\) 。
  点击查看代码

  set<ll>vis;
  ll p[50],ans=0;
  void dfsl(ll x,ll n,ll m,ll worth,ll weight)
  {
      if(x==n+1)
      {
          if(weight<=m)
          {
              vis.insert(worth);
          }
      }
      else
      {
          if(weight+p[x]<=m)
          {
              dfsl(x+1,n,m,worth+p[x],weight+p[x]);
          }
          dfsl(x+1,n,m,worth,weight);
      }
  }
  void dfsr(ll x,ll n,ll m,ll worth,ll weight)
  {
      if(x==n+1)
      {
          if(weight<=m)
          {
              ans=max(ans,worth+(*(--vis.upper_bound(m-weight))));
          }
      }
      else
      {
          if(weight+p[x]<=m)
          {
              dfsr(x+1,n,m,worth+p[x],weight+p[x]);
          }
          dfsr(x+1,n,m,worth,weight);
      }
  }
  int main()
  {
      freopen("drink.in","r",stdin);
      freopen("drink.out","w",stdout);
      ll n,m,i;
      cin>>n>>m;
      for(i=1;i<=n;i++)
      {
          cin>>p[i];
      }
      dfsl(1,n/2,m,0,0);
      dfsr(n/2+1,n,m,0,0);
      cout<<ans<<endl;
      fclose(stdin);
      fclose(stdout);
      return 0;
  }
  

总结

• 开题顺序 \(T4,T2,T1\) 。
• 要善于从题目背景中获得信息。