constructive algorithms-526互联

E. Misha and Paintings

https://codeforces.com/problemset/problem/1720/E

题意：给到一个n*n矩阵，问至少需要几次操作才能使得矩阵中有exactly k个点。

每次操作定义为选定一个方阵，将其所有元素变为x,x自定义。

n<=500,k<=n2，aij<=n2

题解：对于这类构造题，我们往往希望粗调逼近所需值，然后细调至达到k。

首先我们特判当前总数<k的情况，选择k-x个位置变成没出现过的颜色即可。

当k=1时，至多1次操作即可。

否则至多两次操作。

我们从(1,1)为左上角，不断扩大方阵大小直到再扩大会小于k（如果恰好等于或k-1则找到构造），假定此时长度为l，则选则(l+1,l+1)作为右下角扩展方阵每次会使得方阵内不同数至多变化2，故总可以到达k或k-1,得解。

最后再判能否一次操作，枚举边长和左上角坐标看是否可行即可。

复杂度O(n3)

2022ICPC南京 F,三角形（捧杯题？）

https://sua.ac/wiki/2022-icpc-nanjing/f/

Problem - F - Codeforces

题意：给一个巨大的正方形网格（边长1e9)，给定k，问能否用恰k个锐角三角形对其进行分割，若不能输出NO，否则给出构造方案，点为整数（可证明不影响构造）。

题解：这类问题我们往往需要通过其不等关系或相等关系通过代数关系估计其上下界从而找到合理的构造。

我们可以发现对于四个角上的顶点，至少有2个三角形分割它，对于某条边上的至少要3个三角形分割它，对于悬空的点至少要5个三角形分割它。那么我们设有x个点在边上，y个浮空点。

根据上述分析的不等关系，得到4 * 2+3 * x+5 * y<=3 * k

根据内角关系得：4 * 90+180 x +360 * y=k180

得到y>=2.

而对于两个浮空点，至多有两个三角形同时使用其二者，故此时至少存在8个三角形才有解。

对于k>=8我们发现可以通过在某一个锐角三角形中三边取中点可以构造出+3个三角形，故我们只需找到k=8,9,10即可。

我们根据上述代数分析当y取2（事实上y越少越好构造故我们都取y=2)，x依次取2,3,4。

有如下构造：

E. Serega the Pirate

Problem - 1700E - Codeforces

题意：给定一个n*m矩阵，问是否存在一种行走方案，使得在每个点都可以走无数次的前提下，每个点第一次被遍历的时刻是按照序号递增的，t(1)<t(2)<t(3)...且每个点都能被访问到。如果做不到，问最少需要交换几次点才能做到，若不需要交换则输出0，若1次则输出1，若>=2次则输出2。

n*m<=400000

题解：我们可以发现若一个点四周的点值均大于其值，则这个点是不能被到达的。若图上没有这样的点，则不需要交换即可做到。否则，将一个不可到达点变成可到达点需要交换不可达点或者其四周的点，而某一次交换至多影响10个点，故我们可以找到一个不可达点后枚举其与其相邻点与图上所有点交换后是否可能形成通路，若可以则为1，否则则为2。

F. Tenzing and Tree

Problem - F - Codeforces

题意：给定一棵树的结构，定义边的权重为其两边黑点数量之差，树的权重为其每条边权重之和。问k从0->n，染k个点为黑色时树的最大权重时多少。

n<=5000

题解：这类问题应当从其代数式上考虑如何达到最值。

可以得到边权相当于|k-2 * siz[v]|，而总和即为Σ|k-2 * siz[v]|。绝对值不好求，我们考虑如何破开绝对值，我们发现可以取得一个黑点使得这个点两边数量差最小（重心），取这个点作为根时可以去除绝对值。

问题转化为求(n-1)*k -2∑siz[v],而对于一个黑点，它将会使得其所有祖先节点产生-2的贡献，故我们可以按照到root的距离对点排序后染色即可得到最大权重。

C. XOR Triangle

https://codeforces.com/problemset/problem/1710/C

题意：给你一个巨大的n,问你有多少三元组{a,b,c},使得(a^b,bc,c^a)组成一个三角形的三边，答案取模。

n<=pow(2,200000)

题解：对于这种题，我们可以枚举一位时观察性质。

枚举abc在000->111中的所有情况，发现a^b+bc总是>=a^{c，当且仅有两种情况使得其可以取>号，故一个三元组合理当且仅当其三个数都出现过上述情况使得x}y+y^z>xz,这是什么？数位dp！按照数位dp求解即可，复杂度为O(64n)。

贴个代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
string s;
int dp[200010][2][2][2][2][2][2];
int dfs(int p,int lx,int ly,int lz,int x,int y,int z){
	if(p>s.length()-1){
		return x&&y&&z;
	}
	int res=dp[p][lx][ly][lz][x][y][z];
	if(res!=-1) return res;
	res=0;
	int w=s[p]-'0';
	for(int i=0;i<=(lx?w:1);i++)
	for(int j=0;j<=(ly?w:1);j++)
	for(int k=0;k<=(lz?w:1);k++){
		int w=s[p]-'0';
		res=(res+dfs(p+1,lx&(i==w),ly&(j==w),lz&(k==w),
		x|((i==1&&j==0&&k==0)|(i==0&&j==1&&k==1)),
		y|((j==1&&i==0&&k==0)|(j==0&&i==1&&k==1)),
		z|((k==1&&i==0&&j==0)|(k==0&&i==1&&j==1))))%mod;
	}
	return dp[p][lx][ly][lz][x][y][z]=res;
}

signed main(){
	cin>>s;
	memset(dp,-1,sizeof dp);
	int ans=dfs(0,1,1,1,0,0,0);
	cout<<ans;
}