Codeforces Round 872 (Div. 2)
感谢灵茶山艾府
A（脑筋急转弯）
给一个回文字符串，找出最长的不回文子串。
子串可以是不连续的。没有则输出-1；
如果全都是一个字母，那就是-1
否则是n-1。因为在原来回文的基础上总可以去掉一个使得不回文（前提是不是全部都是一个字母）
B（贪心）
给出n*m个数，找出这个式子的最大值。
不同的摆放方式会导致不同的值。有点像哈夫曼树。尽量让最大的数出现最多次，同时最小的数出现最多次。
因此只需要考虑（1,1），（1,2）,(2,1)三个地方放什么数即可。
注意这里容易遗漏：有两种情况：左上角摆最大值，和最小值。
要分类讨论。
开始计算出现次数：第一步容易发现n和m的取值影响结果，于是让n小于m。
1.最大值摆左上角，最小值摆右侧，次小值摆下侧
2.最小值摆左上角，最大值摆右侧，次大值摆下侧。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=1e5+10;
void solve()
{
int n,m;
cin>>n>>m;
int cnt1=0,cnt2=0;
vector<int> a;
int x;
for(int i=0;i<n;i++)
{
cin>>x;
if(x==-1) cnt1++;
else if(x==-2) cnt2++;
else a.push_back(x);
}
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());
int res=0;
//������������
int len=int(a.size());
res=max(res,cnt1+len);
res=max(res,cnt2+len);
res=min(res,n);
for(int i=0;i<a.size();i++)
{
int l=min(a[i]-1,i+cnt1);
int r=min(n-a[i],int(a.size())-1-i+cnt2);
res=max(res,l+1+r);
}
cout<<res<<endl;
}
int main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
C（贪心）
n个人，m个座位。怎么摆放使得最多人有座位
有三种人：
1.如果没有人，就坐在第m个位置。否则坐在最左边的人的左侧
2.如果没有人，就坐在第1个位置，否则坐在最右边的人的右侧
3.坐在给定的第x[i]个位置。
不同的进场顺序导致不同的选座位方式。
抽象出来前两种人的选座方式:
第一种人实际上就是直接在当前选座的左边补一个。第二种人在右边补一个。
因此我们先安排好全部第3种人，然后从某个座位开始往左往右遍历，如果当前位置没人，就安排一个第1/2种人坐下，如果有人就跳过，如果超过m或小于1就不安排。
因此对每个x[i]枚举一下从哪里开始往左往右安排最长即可。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=1e5+10;
void solve()
{
int n,m;
cin>>n>>m;
int cnt1=0,cnt2=0;
vector<int> a;
int x;
for(int i=0;i<n;i++)
{
cin>>x;
if(x==-1) cnt1++;
else if(x==-2) cnt2++;
else a.push_back(x);
}
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());
int res=0;
//向左向右延伸
int len=int(a.size());
res=max(res,cnt1+len);
res=max(res,cnt2+len);
res=min(res,m);
for(int i=0;i<a.size();i++)
{
int l=min(a[i]-1,i+cnt1);
int r=min(m-a[i],int(a.size())-1-i+cnt2);
res=max(res,l+1+r);
}
cout<<res<<endl;
}
int main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
C,D（树上期望、点期望转换成边期望）
在一棵给定的树上选择k个点。到k个点距离之和最近的点被称为好点。求好点个数的期望。（树边距离为1）
首先看最简单的情况。k=1，则只有被选择的点
k=2：因为是一棵树，两点之间只会有一条路径。因此两个点之间路径上所有点都是好点
k=3：一条线上三个点，显然为中位数。不在一条线上的话，容易证明：设某个点到选定的3个点距离一致。此时往一个点更近，就会往另外两个点更远，因此符合要求的点只有1个。
进而知道k=奇数时，好点只有1个。期望为1。
如果为偶数时，情况比较复杂。
首先把期望公式为：1个好点乘以对应概率+2个好点乘以对应概率·······=枚举每个点，$\sum 该点是好点*该点是好点的概率$
但是情况仍然不好计算。
不如计算有多少好边，好点概率等于好边+1。
树上一条边连接两个连通块因此，某条边时好边的情况是：一个连通块已经选了k/2个点，另一个连通块选k/2个点。
还要记录一下两边的size，实际上一个size2=n-size1。因此记录子树的size即可。
这里只给出简单版的代码：即k=1,2,3。除以的操作用快速幂求逆元。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,p=1e9+7;
int n,k,siz[N],ans;
vector<int>G[N];
void dfs(int x,int fa){
siz[x]=1;
for(int to:G[x]) if(to!=fa)
dfs(to,x),siz[x]+=siz[to];
ans+=siz[x]*(n-siz[x]);
}
int qpow(int x,int y){
int ans=1;
while(y){
if(y&1) ans=ans*x%p;
x=x*x%p,y>>=1;
}
return ans;
}
signed main(){
cin>>n>>k;
if(k==1||k==3) cout<<1<<'\n';
else{
for(int i=1,x,y;i<n;i++)
cin>>x>>y,
G[x].push_back(y),
G[y].push_back(x);
dfs(1,0);
ans+=n*(n-1)/2,ans%=p;
cout<<ans*qpow((n*(n-1)/2)%p,p-2)%p<<'\n';
}
}
E（树上启发式合并）
给定一棵树，树上有n个点。求最少修改多少次点的权值能够使得树上所有路径的异或和为1。
从简单情况考虑，即从下往上考虑，预先对每个点向根节点求一次异或。
要使得路径异或和为0，至少要使得叶节点上每个点权值相同。那么修改次数最少就是把出现次数最多的数，保持，其他的修改成出现次数最多的数。然后父节点修改为子树中出现最多的数。
但是可能有多个出现最多的数，这里就需要都存储下来，因此根节点需要合并不同子树的信息，这里就用到启发式合并。简单来说就是用一个map，把小的map合并到大的map上。
合并之后，对根节点操作，只保留出现次数最多的数。
最后回溯到根节点时，如果子树中出现最多的数可以是0，那么异或和就是0，不需要修改根节点，否则需要修改一次根节点。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
const int N =1e5+10;
vector<int> g[N];
int n,a[N];
map<int,int> f[N];
int ans;
void dfs(int u,int fa)
{
int mx=1,c=0;
for(auto to:g[u])
{
if(to==fa) continue;
a[to]^=a[u];
dfs(to,u);
c++;
if(f[u].size()<f[to].size()) swap(f[u],f[to]);
for(auto &o:f[to]) mx=max(mx,f[u][o.first]+=o.second);
}
if(!c) f[u][a[u]] =1;
else ans+=c-mx;
if(mx!=1)
{
for(auto it=begin(f[u]);it!=end(f[u]);)
{
if((it->second!=mx)) it=f[u].erase(it);
else it->second=1,it=next(it);
}
}
if(u==1)
cout<<ans+(!f[u].count(0));
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1,a,b;i<n;i++)
{
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1,0);
}