10.5组队训练赛-2024CCPC山东省赛

成绩 4
排名 8（差3题）

写在前面

I k a 是简单题，但是因为 a 爆 long long 一直没有看出来，导致交了很都发。
出现的问题就是代码能力太弱，不能保证一遍过。改错的能力也很弱，没有及时发现出错的地方，一直在题意理解和算法方面打转。浪费时间。

J 题想了一个贪心感觉是正确的，事实证明就是正确的，但是不知道vector啥原因最后没过，赛后看了两个小时的题解，依然觉着没有问题，最后才发现就是vector的问题，十分生气，但也没有办法，就是菜

说说这次：大家人居7题，我也是无语了，我们直接被拉了3到，我也没有想到成这样，真的都这么厉害吗，还是自己不够努力呀，哎，菜

J. Colorful Spanning Tree

题目大意：每个颜色有 \(a_i\) 个点，颜色与颜色之间有边权，求所有点的最小生成树。

思路：

当时一个很明显贪心思路就是，先形成数，然后贪心直接找最小的边连。然后我就直接上去莽了，实时证明她是正确的，因为最小生成树的性质，

最小生成树里面一定包含每个点的所有边的最小边，因为，如果不包含，添加最小边一定形成一个环，这个时候用最小边替换那条边，仍然可以使图联通，并且总价值最小，因此结论成立。

问题就出现在维护最小值上面，一开始我很麻烦的用了vector 排序去做，结果发现过了一半的数据，当时就觉得我的贪心出现了问题，就卡住了。

其实问题也在我，如果知道这个生成树的性质，就不会质疑我的算法的问题，进而发现vector 出错的概率就更大，需要长脑子了。

/*
	
	考点：贪心，最小生成树板子 
	看了题解，看了题解代码，想了很久，结果本来就是对的
	因为vector的问题！！！
	
	不过通过这个题目也学到一些东西。
	
	最小生成树里面一定包含一个点的所有边的最小边
	因为，如果不包含，添加最小边一定形成一个环
	这个时候用最小边替换那条边，仍然可以使图联通，并且总价值最小。
	因此结论成立。 
*/ 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){int x;scanf("%lld",&x);return x;}
const int B=1e6+10;
const int inf=0x3f3f3f3f;
int T;
int n;
int a[B];
vector<int>v[1000009];
int fa[B];
int find(int x)
{
	if (fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
struct node
{
	int u,v,x;
}e[B];
int cmp(node a,node b)
{
	return a.x<b.x;
}
int minxx[B]; 
void work()
{
	n=read();
	int tot=0;
	for (int i=1;i<=n;i++) a[i]=read(),fa[i]=i,minxx[i]=0x3f3f3f3f;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++) 
		{
			int x=read();
			if (!a[i] || !a[j]) continue;
			e[++tot]={i,j,x};
			minxx[i]=min(minxx[i],x);
		}
	}
	int sum=0;
	sort(e+1,e+1+tot,cmp);
	for (int i=1;i<=tot;i++)
	{
//		if (e[i].u==e[i].v) continue; 
		int u=find(e[i].u);
		int v=find(e[i].v);
		if (fa[u]==fa[v]) continue;
		fa[v]=u;
		sum+=e[i].x;
	}
	for (int i=1;i<=n;i++)
	{
		int res=a[i]-1;
		if (res<=0) continue;
		sum+=minxx[i]*res;
	}
	cout<<sum<<endl;
}
signed main()
{
	cin.tie(0); 
	T=read();
	while (T--) work();
	return 0;
}

K - Matrix

题目大意：

给一个 \(n\times n\) 的矩阵填数字，要求 \(1-2n\) 至少都存在一次，并且任意矩形的四个顶点，两两不同的情况只有一种

思路：

思维题，反正我是想不出来，但是感觉非常巧妙。

其实看做法发现还是挺有道理的。

首先确定那个不同的四个角，也就是第一行和最后一行的两个数，然后，因为问我不想在其他行存在答案，所以我就直接把其他行的数字，每一行都相同，这样就可以保证所有的行都不能在被用，然后再来看剩下的列，为了保证当取第一行和最后一行的数的时候相同，所以我们直接让两行剩下的数，每一列都是相同的数，然后这样算下来刚好2n个，好神奇!!!!!

#include<bits/stdc++.h>
using namespace std;
int read(){int x;scanf("%d",&x);return x;}
const int B=1e6+10;
const int inf=0x3f3f3f3f;
int T;
int n;
int a[109][109];
void work()
{
	cin>>n;
	a[1][1]=1;
	a[1][2]=2;
	a[n][1]=3;
	a[n][2]=4;
	int now=2;
	for (int i=5;;i++)
	{
		a[1][++now]=i;
		a[n][now]=i;
		if (now>=n) 
		{
			now=i;
			break;
		}
	}
	puts("Yes");
	for (int i=1;i<=n;i++) cout<<a[1][i]<<" ";
	puts(""); 
	for (int i=2;i<n;i++)
	{
		now++; 
		for (int j=1;j<=n;j++)
		{
			cout<<now<<" ";
		} 
		cout<<"\n"; 
	}
	for (int i=1;i<=n;i++)
	{
		cout<<a[n][i]<<" ";
	}
}
int main()
{
	T=1;
	while (T--) work();
	return 0;
}

C. Colorful Segments 2

题目大意：

现在给一些线段染色，每个线段相互独立，有 k 中颜色，要求相交的线段不能染相同的颜色，求方案数。

思路：

显然，我感觉我不会做，做不了一点，一开始以为是DP，结果发现时间复杂度不对，然后就做不出来了，我还以为是DP优化，然而推了半个小时的式子但是发现不对，草了

然后开始想组合数，然后发现，我依旧不会做，因为，组合数一点思路都没有，我一直在想一个区间被多次相交，前后都相交，怎么算。

然后我忘记了染色计数的一个高中感觉，没错，我只能称为感觉，然后对于这种当前位置操作会对两侧都产生影响的问题，可以选择从左边依次来做，这样也可以实现两两限制

就是高中相邻格子不能染相同的颜色，或者物品填格子问题，做法就是从左到右计算出每个位置可以做出的贡献，然后做乘法。

对于这道题目，当前面有 \(t\) 个与当前线段交叉，那么线段的贡献值为 \(k-t\)

然后直接做乘法就可以了。

解决交叉问题其实就是维护当前有多少个 \(r\) 在当前 \(l\) 的后面，可以用树状数组，线段树计数，也可以用队列，维护出已经不满足的 \(r\),每少一个 \(r\) 就意味着当前位置可以多天一种颜色，而每次计算完一个线段的时候，假设一个颜色不能用 k--，

假设的原因是保证 k 一直都是当前位置可以用的颜色个数，即使-1，如果然不会和下一个区间有交叉，同样也会被加回来。

树状数组代码
用到了离散化，
这里强调一句：unique 的意思表示删除相邻相同的元素，不具备排序的能力

所以离散化需要先排序然后去重

/*
	先写一个树状数组的
	用树状数组维护前面右端点在当前左端点之前的数量，求一个后缀和
	结果发现坐标大小1e9
	
	直接离散化 
*/ 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){int x;scanf("%lld",&x);return x;}
const int B=1e6+10;
const int mod=998244353; 
const int inf=0x3f3f3f3f;
int T;
int n,k;
struct node
{
	int l,r;
}a[B];
int b[B];
int tot;
int cmp(node a,node b)
{
	if (a.l==b.l) return b.r<b.r;
	return a.l<b.l;
}
int t[B];
int lowbit(int x){return x&-x;}
void modify(int x,int y){for (int i=x;i<=tot;i+=lowbit(i)) t[i]+=y;}
int query(int x){int res=0;for (int i=x;i;i-=lowbit(i)) res+=t[i];return res;}
int find(int l,int r)
{
	return query(r)-query(l-1);
} 
void work()
{
	tot=0;
	cin>>n>>k;
	for (int i=1;i<=n;i++)
	{
		a[i].l=read();
		a[i].r=read();
		b[++tot]=a[i].l;
		b[++tot]=a[i].r;
	}
	sort(a+1,a+1+n,cmp);
	//离散化忘记排序，先排序，然后在去重，
	//unique 的作用：去掉相邻相同的元素。 
	sort(b+1,b+1+tot);
	tot=unique(b+1,b+1+tot)-b-1;
	int ans=1;
	for (int i=1;i<=n;i++)
	{
		a[i].l=lower_bound(b+1,b+1+tot,a[i].l)-b;
		a[i].r=lower_bound(b+1,b+1+tot,a[i].r)-b;
		int t=find(a[i].l,tot);
		ans=(ans%mod*(k-t)%mod)%mod;
		modify(a[i].r,1);
	}
	cout<<ans%mod<<"\n";
	for (int i=1;i<=n;i++)//还原 
	{
		modify(a[i].r,-1);
	}
}
signed main()
{
	cin.tie(0);
	T=read();
	while (T--) work();
	return 0;
}

法二

优先队列做法

/*
	先写一个树状数组的
	用树状数组维护前面右端点在当前左端点之前的数量，求一个后缀和
	结果发现坐标大小1e9
	
	直接离散化 
*/ 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){int x;scanf("%lld",&x);return x;}
const int B=1e6+10;
const int mod=998244353; 
const int inf=0x3f3f3f3f;
int T;
int n,k;
struct node
{
	int l,r;
}a[B];
int b[B];
int tot;
int cmp(node a,node b)
{
	if (a.l==b.l) return b.r<b.r;
	return a.l<b.l;
}
int t[B];
int lowbit(int x){return x&-x;}
void modify(int x,int y){for (int i=x;i<=tot;i+=lowbit(i)) t[i]+=y;}
int query(int x){int res=0;for (int i=x;i;i-=lowbit(i)) res+=t[i];return res;}
int find(int l,int r)
{
	return query(r)-query(l-1);
} 
void work()
{
	tot=0;
	cin>>n>>k;
	for (int i=1;i<=n;i++)
	{
		a[i].l=read();
		a[i].r=read();
	}
	sort(a+1,a+1+n,cmp);
	int ans=1;
	priority_queue<int>q;
	for (int i=1;i<=n;i++)
	{
		while (!q.empty() && -q.top()<a[i].l) k++,q.pop();
		ans=(ans%mod*k%mod)%mod;
		k--;
		q.push(-a[i].r);
	} 
	cout<<ans%mod<<endl;
}
signed main()
{
	cin.tie(0);
	T=read();
	while (T--) work();
	return 0;
}