【LGR-156-Div.3】洛谷网校 8 月普及组月赛 I & MXOI Round 1 & 飞熊杯 #2（同步赛）

\(T1\) luogu P9581 宝箱 \(100pts\)

• 水题，模拟即可。

  int main()
  {
  	int a,b,ans=0;
  	cin>>a>>b;
  	if((a<0&&b<0)||(a>0&&b>0))
  	{
  		cout<<max(abs(a),abs(b))<<endl;;
  	}
  	else
  	{
  		if(a==0||b==0)
  		{
  			cout<<abs(a)+abs(b)<<endl;
  		}
  		else
  		{
  			cout<<abs(a)+abs(b)+min(abs(a),abs(b))<<endl;
  		}
  	}
  	return 0;
  }
  

\(T2\) luogu P9582 方格 \(100pts\)

• 水题。
• 令 \(sum_{i,j}\) 表示 \((1,1) \sim (i,j)\) 中与 \((i,j)\) 颜色相同的数量，则所求即为 \(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} sum_{i,j} - 不合法答案\) 。

  ll a[2001][2001],sum[2001];//不开long long见祖宗
  int main()
  {
  	ll n,m,i,j,pd,ans=0;
  	cin>>n>>m;
  	for(i=1;i<=n;i++)
  	{
  		for(j=1;j<=m;j++)
  		{
  			cin>>a[i][j];
  			ans+=sum[a[i][j]]*2;
  			sum[a[i][j]]++;
  			if(a[i-1][j]==a[i][j])
  			{
  				ans-=2;
  			}
  			if(a[i][j-1]==a[i][j])
  			{
  				ans-=2;
  			}
  		}
  	}
  	cout<<ans<<endl;
  	return 0;
  }
  

\(T3\) luogu P9583 涂色 \(0pts\)

• 感觉类似luogu P9117 [春季测试 2023] 涂色游戏。
• 对于 \((i,j)\) 的方格，若有 \((h_i+l_j) \bmod k=0\) ，则 \((i,j)\) 无颜色；否则有颜色。
• 考虑对原题面进行转换，有颜色的方格数量等于总方格数量减无颜色的方格数量，而无颜色的方格数量可以理解为染色次数为 \(k\) 的倍数的方格数量。开个桶维护一下即可。

  ll h[500001],l[500001],sum[500001];
  int main()
  {
  	ll n,m,q,k,i,pd,x,ans=0;
  	cin>>n>>m>>q>>k;
  	for(i=1;i<=q;i++)
  	{
  		cin>>pd>>x;
  		if(pd==1)
  		{
  			h[x]++;
  		}
  		if(pd==2)
  		{
  			l[x]++;
  		}
  	}
  	for(i=1;i<=n;i++)
  	{
  		sum[h[i]%k]++;
  	}
  	sum[k]=sum[0];
  	for(i=1;i<=m;i++)
  	{
  		l[i]%=k;
  		ans+=n-sum[k-l[i]];//也可以写成ans+=sum[k-l[i]]; 输出时输出n*m-ans即可
  	}
  	cout<<ans<<endl;
  	return 0;
  }
  

\(T4\) luogu P9584 城市 \(0pts\)

• 有时间再写，暂时咕了。

总结

• 自己的模拟能力和题目转化能力太差，往后要多练习这种能力。