【cf623X】AIM Tech Round (Div. 1)

2016年3月6日1,3570

A. Graph and String

题意

n个点,每个点有a,b,c其中一种颜色,若两个点颜色的字母相邻则它们之间连边。

给出图的连边情况,求一种可行的染色方案。

题解

如果有一个点和其它点都有连边,将其标号b。

然后选择一个未被标号的点,标号为a,二分图染色。

最后验证一下即可。

B. Array GCD

题意

给定长为n的数列和两个操作,每个操作用一次

1.移除数列的一个子串,代价是长度*a

2.对于一些数字+1或者-1,每个数字代价为b

求使得数列的gcd大于1的最小代价

题解

由于不能删掉所有的数,那么至少会剩下第一个或最后一个

这两个可能会被修改,枚举2 * 3 = 6种情况,分解质因数后扫一遍数列,取最优值