CF1328D Carousel
注意，题目并没有要求同一种动物必须染相同的颜色。虽然样例的确满足这一点。
我们断言，需要的颜色数不会超过(3)。我们从(1)到(3)依次尝试，当构造成功了就直接输出答案。
要使答案为(1)，显然只有一种情况，就是整个序列只有一种动物。
要使答案为(2)。先把序列里每一段极长的、相同动物的连续段用同一种颜色表示，把相邻的段涂上不同的颜色（例如：上一段是(1)，这一段就是(2)；上一段是(2)，这一段就是(1)）。
此时，还需要考虑的只有(1)和(n)的关系。若(1)和(n)是同一种动物，或者它们现在已经是不同的颜色了，则说明当前的涂色方法就是一个合法解。
否则，我们要做一些调整，使(1)和(n)颜色不同。我们检查序列里是否存在一个同色段的长度大于(1)。如果存在，则我们可以把这一段劈成两半，前一半还是原来的颜色，后一半和原来颜色相反，且从它往后的每一段颜色都和原来反转。这样，(1)和(n)就一定不同色了。
如果找不到长度大于(1)的同色段。说明我们无法用(2)种颜色构造出合法解。即答案为(3)。我们直接在原来构造的基础上令(n)的颜色为(3)即可。
时间复杂度(O(n))。
参考代码：
//problem:CF1328D
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace Fread{
const int MAXN=1<<20;
char buf[MAXN],*S,*T;
inline char getchar(){
if(S==T){
T=(S=buf)+fread(buf,1,MAXN,stdin);
if(S==T)return EOF;
}
return *S++;
}
}//namespace Fread
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#endif
inline int read(){
int f=1,x=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll readll(){
ll f=1,x=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
/* ------ by:duyi ------ */ // myt天下第一
const int MAXN=2e5;
int n,a[MAXN+5],col[MAXN+5];
bool check1(){
for(int i=1;i<=n;++i){
int j=i%n+1;
if(a[i]!=a[j])return 0;
}
puts("1");
for(int i=1;i<=n;++i)printf("%d ",1);puts("");
return 1;
}
bool check2(){
col[1]=1;
for(int i=2;i<=n;++i){
if(a[i]!=a[i-1]){
col[i]=3-col[i-1];
}
else{
col[i]=col[i-1];
}
}
if((a[n]==a[1])||(a[n]!=a[1]&&col[n]!=col[1])){
puts("2");
for(int i=1;i<=n;++i)printf("%d ",col[i]);puts("");
return 1;
}
for(int i=1;i<n;++i)if(a[i]==a[i+1]){
col[i+1]=3-col[i];
for(int j=i+2;j<=n;++j){
if(a[j]!=a[j-1]){
col[j]=3-col[j-1];
}
else{
col[j]=col[j-1];
}
}
puts("2");
for(int i=1;i<=n;++i)printf("%d ",col[i]);puts("");
return 1;
}
return 0;
}
void check3(){
col[1]=1;
for(int i=2;i<=n;++i){
if(a[i]!=a[i-1]){
col[i]=3-col[i-1];
}
else{
col[i]=col[i-1];
}
}
col[n]=3;
puts("3");
for(int i=1;i<=n;++i)printf("%d ",col[i]);puts("");
}
int main() {
int T=read();while(T--){
n=read();
for(int i=1;i<=n;++i)a[i]=read();
if(check1())continue;
if(check2())continue;
check3();
}
return 0;
}
CF1328E Tree Queries
我们要找到一个合法的(u)，使得所有(v_1dots v_k)都在(u)到根的路径上，或者距离路径上某个点距离为(1)。
这里的距离为(1)，肯定不会说(v_i)是某个路径上点的父亲，因为这种情况下它自己本身也必在路径上。所以这里的距离为(1)，可以转化为，要么(v_i)在路径上，要么它是路径上某个点的儿子。也就是说，(v_i)和(v_i)的父亲，至少要有一个点是路径上的点。
判断一个点(v)在不在(u)到根的路径上，其实就是判断(u)是否在(v)的子树内。这个可以用dfs序(O(1))判断。
至此，我们可以(O(k))地check某一个(u)是否满足条件。但显然不能暴力枚举所有(u)，否则单次询问复杂度退化为(O(nk))。
我们发现，如果有解，则(v_1dots v_k)里深度最深的点的父亲，一定是一个合法的(u)。所以只要找到这个深度最深的点，再check它的父亲即可。
单次询问时间复杂度(O(k))。
参考代码：
//problem:CF1328E
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace Fread{
const int MAXN=1<<20;
char buf[MAXN],*S,*T;
inline char getchar(){
if(S==T){
T=(S=buf)+fread(buf,1,MAXN,stdin);
if(S==T)return EOF;
}
return *S++;
}
}//namespace Fread
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#endif
inline int read(){
int f=1,x=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll readll(){
ll f=1,x=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
/* ------ by:duyi ------ */ // myt天下第一
const int MAXN=2e5;
int n,m,dfn[MAXN+5],ofn[MAXN+5],cnt,dep[MAXN+5],fa[MAXN+5];
vector<int>G[MAXN+5];
void dfs(int u){
dfn[u]=++cnt;
dep[u]=dep[fa[u]]+1;
for(int i=0;i<SZ(G[u]);++i){
int v=G[u][i];
if(v==fa[u])continue;
fa[v]=u;
dfs(v);
}
ofn[u]=cnt;
}
bool isanc(int ann,int u){
return dfn[u]>=dfn[ann] && dfn[u]<=ofn[ann];
}
int K,a[MAXN+5];
bool check(int u){
for(int i=1;i<=K;++i){
if(isanc(a[i],u)||isanc(fa[a[i]],u))continue;
return 0;
}
return 1;
}
int main() {
n=read();m=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
G[u].pb(v);G[v].pb(u);
}
dfs(1);
while(m--){
K=read();
int u=0;
for(int i=1;i<=K;++i){
a[i]=read();
if(!u||dep[a[i]]>dep[u])u=a[i];
}
if(u==1){
puts("YES");continue;
}
if(check(fa[u]))puts("YES");
else puts("NO");
}
return 0;
}
CF1328F Make k Equal
先把(a_1dots a_n)按从小到大排序。
显然，最终的(k)个相等的数一定等于(a_1dots a_n)里的某个值，不可能凭空冒出一个新的值（因为这样代价一定更大）。
我们枚举最终的(k)个相等的数等于几。也就是枚举(a_1dots a_n)里的某个值(x)。因为是排好序后，所以(x)在序列里一定是连续的一段。我们要在这一段左边补几个数，右边补几个数，使得段的长度达到(k)。在左边补几个数，根据题目规则，显然必须要把左边所有的数先补成(x-1)。同理，如果要在右边补几个等于(x)的数，必须先把右边所有数变成(x+1)。
如果原序列等于(x)的连续段为(a_ldots a_r)，即(forall iin[l,r] a_i=x)，则我们的总操作次数为：
[left((x-1)(l-1)-sum_{i=1}^{l-1}a_i
ight)+left(sum_{i=r+1}^{n}a_i-(x+1)(n-r)
ight)+k-(r-l+1)
]
做前缀和、后缀和，即可(O(1))计算上式。
当然，如果(rgeq k)或者(n-l+1geq k)，我们可以只补左边，或者只补右边。这两种情况也要考虑到。
时间复杂度(O(n))。
参考代码：
//problem:CF1328F
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace Fread{
const int MAXN=1<<20;
char buf[MAXN],*S,*T;
inline char getchar(){
if(S==T){
T=(S=buf)+fread(buf,1,MAXN,stdin);
if(S==T)return EOF;
}
return *S++;
}
}//namespace Fread
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#endif
inline int read(){
int f=1,x=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll readll(){
ll f=1,x=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
/* ------ by:duyi ------ */ // myt天下第一
const int MAXN=2e5;
const ll INF=1e18;
int n,K,a[MAXN+5];
ll pre[MAXN+5],suf[MAXN+5];
int main() {
n=read();K=read();
for(int i=1;i<=n;++i)a[i]=read();
sort(a+1,a+n+1);
for(int i=1;i<=n;++i)pre[i]=pre[i-1]+a[i];
for(int i=n;i>=1;--i)suf[i]=suf[i+1]+a[i];
ll ans=INF;
for(int i=1;i<=n;++i){
int j=i;
while(j+1<=n&&a[j+1]==a[i])++j;
if(j-i+1>=K){ans=0;break;}
ans=min(ans,(ll)(a[i]-1)*(i-1)-pre[i-1]+suf[j+1]-(ll)(a[i]+1)*(n-j)+K-(j-i+1));
if(j>=K){
ans=min(ans,(ll)(a[i]-1)*(i-1)-pre[i-1]+K-(j-i+1));
}
if(n-i+1>=K){
ans=min(ans,suf[j+1]-(ll)(a[i]+1)*(n-j)+K-(j-i+1));
}
i=j;
}
cout<<ans<<endl;
return 0;
}