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);
}
标签:好点,int,res,872,Codeforces,ans,Div,include,节点
From: https://www.cnblogs.com/hyk-blessingsoftware/p/17396378.html