C

思维

每个人都给出除了自己以外，人数最多的颜色有多少人。问能否判断有人说谎

如果只有一组人数最多的颜色，有人，没人撒谎的情况肯定是，这组内人报告，这组外其他人报告

如果有多组人数最多的颜色，都有人，那么所有人都报告。因为至少有两组，所以总人数不少于。

还一种可能是个人颜色都一样，所有人都报告，也是可以的

其它都不合法

void solve(){
	int n;
	cin>>n;
	vi a(n+1);
	rep(i,1,n)cin>>a[i];
	
	set<int>s;
	map<int,int>mp;
	rep(i,1,n){
		s.insert(a[i]);
		mp[a[i]]++;
	}
	if(s.size()==1){
		if(a[1]==n-1){
			cout<<"Other\n";
		}
		else if(2*a[1]>n){
			cout<<"Lie\n";
		}
		else{
			cout<<"Other\n";
		}
	}
	else if(s.size()==2){
		int x=*s.begin();
		int y=*s.rbegin();
		if(y==x+1&&y==mp[x]){
			cout<<"Other\n";
		}
		else{
			cout<<"Lie\n";
		}
	}
	else{
		cout<<"Lie\n";
	}
}

D

多源BFS

找到所有到叶子的最短距离最大的非叶点

从所有叶子开始多源BFS，记录每个非叶点到最近的叶子1的距离

void solve(){
    int n;
    cin>>n;
    vvi g(n+1);
    vi in(n+1);
    rep(i,1,n-1){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        in[u]++;
        in[v]++;
    }
     
    queue<int>q;
    vi d(n+1,1e9);
    rep(i,1,n){
        if(in[i]==1){
            q.push(i);
            d[i]=0;
        }
    }
     
    while(q.size()){
        int u=q.front();
        q.pop();
         
        for(int v:g[u]){
            if(d[v]>d[u]+1){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
     
    int mx=0;
    vi ans;
    rep(i,1,n){
        if(d[i]>mx){
            mx=d[i];
            ans.clear();
            ans.push_back(i);
        }
        else if(d[i]==mx){
            ans.push_back(i);
        }
    }
    cout<<ans.size()<<'\n';
    for(int x:ans){
        cout<<x<<' ';
    }
    cout<<'\n';
}

E

数论

找一个子序列，满足相邻元素要么要么，问最长序列

显然子序列，转移时可以从所有的因子，或者的倍数转移过来，因子可以直接枚举，倍数，由于不保证元素不重，枚举复杂度可能炸了。

但是每个往前且是倍数的转移，实际上从转移前驱来看，等价于往后的因子转移，所以可以记录每个因子的前驱倍数的最优解。每个的结束后，分解，更新所有因子的

void solve(){
    int n;
    cin>>n;
    vi a(n+1);
    rep(i,1,n){
        cin>>a[i];
    }
     
    vi dp(n+1),mx(n+1);
    int ans=0;
    rep(i,1,n){
        int res=dp[a[i]];
        rep(j,1,sqrt(a[i])){
            if(a[i]%j==0){
                res=max(res,dp[j]+1);
                if(a[i]/j!=j){
                    res=max(res,dp[a[i]/j]+1);
                }
            }
        }
        res=max(res,mx[a[i]]+1);
        dp[a[i]]=res;
        rep(j,1,sqrt(a[i])){
            if(a[i]%j==0){
                mx[j]=max(mx[j],dp[a[i]]);
                if(a[i]/j!=j){
                    mx[a[i]/j]=max(mx[a[i]/j],dp[a[i]]);
                }
            }
        }
        ans=max(ans,res);
    }
    cout<<ans<<'\n';
}

F

贪心 增量 堆

每个长度为的区间贡献是，可以把一些点的颜色反转，让区间断开。问最多操作次后的最小答案？

一个错误的贪心是，每次取出最长的区间，从中间断开。这虽然在只有一次操作的情况下是最优的，但不是全局最优的。考虑一个长度8的，按我们这个策略操作两次后是，但实际最优的是，也就是尽可能均匀的切分成三段

所以，我们实际上是要对于每个区间，决定操作几次，如果决定操作一个区间次，就要尽可能均分地把他分成份

这里有一个重要性质，对于一个区间，我们给他增加操作次数，边际效益是递减的，也就是增加一次操作，这个区间贡献地减小量，是递减的

那么问题也就转化成，有个区间的话，我们有个序列，其中表示，第个区间操作次数从增加到次，这个区间的贡献的减小量，每个都是递减的，每一个我们都要取一个前缀，总的选取的前缀长度加起来为，使得选中的元素和最大（我们这里是减小量最大，也就使得原问题中的剩余贡献最小）。

这是个经典问题，每个序列都是单调的，那么我们一个堆维护所有序列的开头的最值，那么堆顶就是个序列里所有剩余元素的最大值，这样每次取出的都是全局最大值，取次取走了最大的个。这贪心是对的

注意这个策略的正确性依赖于每个序列都是单调的，如果不单调就不对了

然后一个子问题是，长度的区间，操作次的最小贡献，如何计算。

显然均分的话，较小段长度为，然后有段长度为，剩余段长度为，这是经典贪心不谈

int s(int x){
    return x*(x+1)/2;
}
int f(int x,int y){
    int tot=x-y;
    if(tot<0)return 0;
    int mn=tot/(y+1);
    int mx=mn+1;
    int cntmx=tot%(y+1);
    int cntmn=y+1-cntmx;
     
    return cntmx*s(mx)+cntmn*s(mn);
}
void solve(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
     
    s=' '+s;
    s+='x';
     
    int len=0;
    multiset<array<int,3>>q;
     
    int ans=0;
    rep(i,1,n+1){
        if(s[i]=='o'){
            len++;
        }
        else{
            q.insert({f(len,0)-f(len,1),len,0});
            ans+=len*(len+1)/2;
            len=0;
        }
    }   
     
 
    while(k--&&q.size()){
        auto u=*q.rbegin();
        q.erase(--q.end());
         
        int delta=u[0],len=u[1],del=u[2];
        del++;
        ans-=delta;
        if(del<=len){
            q.insert({f(len,del)-f(len,del+1),len,del});
        }
 
    }
     
     
    cout<<ans<<'\n';
}