今天2021.10.6。

---

中午组队赛，遇到一个分层图最短路的模板题，但是不会做。。没学过，所以现学了一下：https://blog.csdn.net/Mr_dimple/article/details/120629967；

---

把昨天最后的那道题补了：

1475.C Ball in Berland（思维，容斥）

题意：

一共n对关系 (xi,yi)，从中挑出两对，确保两队中人不冲突（同一个人不在两个队中），一共可以挑选出多少组两对？

思路：

只能在O(N)或者O(logN)的时间内过。

依次遍历n对关系，统计当前关系可以和多少对关系组成一组？
对于该对关系中的 x，统计出和其一对的y的个数 sum1；
对于该对关系中的 y，统计出和其一对的x的个数 sum2；
那么，和当前关系(x,y)配对的关系一共有n - (sum1 + sum2 - 1)个。(和当前关系有牵连的都不能要，其他的都可以。此外，多加了一个这对关系本身，要去掉）

除此之外，前面的 x 位置可能与后面的 y 位置组合，但是后面枚举到 y 位置时，又把 x 位置算一遍，每个位置都多算了，总结果要除2。

Code：

const int N = 200010, mod = 1e9+7;
int T, n, m;
PII a[N];

int main(){
	Ios;
	cin>>T;
	while(T--)
	{
		int k;
		cin>>n>>m>>k;
		mp1.clear();
		mp2.clear();
		for(int i=1;i<=k;i++){
			cin>>a[i].first;mp1[a[i].first]++;
		}
		for(int i=1;i<=k;i++){
			cin>>a[i].second;mp2[a[i].second]++;
		}
		
		ll ans=0;
		for(int i=1;i<=k;i++)
		{
			int x=a[i].first,y=a[i].second;

			ans+=k-(mp1[x]+mp2[y]-1);
		}
		cout<<ans/2<<"\n";
	}
	
	return 0;
}

---

1332.B. Composite Coloring（思维）

题意：

给出长度为 n 的数列，其中每个数大小[4,1000]。现将其染色，确保：互质的两个数不能染成同一颜色。
输出所需要的颜色个数，并依次输出每个位置的颜色。

思路：

数4~1000中，正好能由前面11个"奇数"(2,3,5,7,11,13,17,19,23,29,31)的倍数组成。
所以，一种数的所有倍数一种颜色。

Code：

const int N = 200010, mod = 1e9+7;
int T, n, m, a[N];
int f[12]={0,2,3,5,7,11,13,17,19,23,29,31};
int flag[12];
int ans[N];

int main(){
	Ios;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		
		mem(flag,0);
		
		int cnt=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=11;j++)
			{
				if(a[i]%f[j]==0){
					if(!flag[j]) flag[j]=++cnt;
					ans[i]=flag[j];
					break;
				}
			}
		}
		cout<<cnt<<"\n";
		for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
		cout<<'\n';
	}
	
	return 0;
}

---

明天加油！