CXJY-Day 5
FLAG: T3不是很熟练，虚树还待加深理解，建议以后重写一下
简单题(easy)
【题目描述】
给定一个长度为n序列$a_i$，定义其异或前缀和$b_i$为$b_1=a_1,b_i=b_{i-1} xor a_i (i≥2)$。
给定序列长度n，已知序列中的$m(0≤m≤n)$个的数，求所有满足要求的序列a_i所对应的b_i中$\sum_i b_i$的最大值。
【输入格式】
第一行两个正整数n,m。
接下来m行，每行两个正整数i,x，表示第i个数$a_i=x$。
【输出格式】
输出一行答案。
【输入样例1】
5 3
4 0
3 7
5 0【输出样例1】
7【数据范围与约定】
对于100%的数据$n≤10^9,m≤10^5,0≤a_i≤10^9$
题解
贪心对于一段可以自己填的值，第一个填的值应该是把前面一段的xor和为0，然后最后一个值的每一位由后面连续的一段中1和0的个数决定，如果1较多，则取1，否则取0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int x,v;
}a[100005];
struct path{
int l,r;
}b[100005];
bool cmp(node x,node y){return x.x<y.x;}
int n,m,cnt;
ll ans=0;
int calc(int id){
int t[33]; memset(t,0,sizeof t);
int la=0;
for (int i=b[id].l;i<=b[id].r;++i){
int tt=a[i].v^la; la=tt;
for (int j=0;j<=30;++j){
if ((tt>>j)&1) t[j]--;
else t[j]++;
}
}
int ret=0;
for (int i=0;i<=30;++i){
if (t[i]<0) ret|=(1<<i);
}
return ret;
}
int main(){
freopen("easy.in","r",stdin);
freopen("easy.out","w",stdout);
cin>>n>>m;
for (int i=1;i<=m;++i){
scanf("%d%d",&a[i].x,&a[i].v);
}
sort(a+1,a+m+1,cmp);
int now=1;
while (now<=m){
int nxt=now;
while (nxt<m && a[nxt+1].x==a[nxt].x+1) nxt++;
b[++cnt]=(path){now,nxt};
now=nxt+1;
}
int la=0;
if (a[1].x!=1) la=calc(1),ans+=la;
for (int id=1;id<=cnt;++id){
for (int i=b[id].l;i<=b[id].r;++i){
la^=a[i].v;
ans+=la;
}
if (id!=cnt){
int tk=calc(id+1);
ans+=tk; la=tk;
}
}
cout<<ans<<endl;
return 0;
}回文串计数(count)
【题目描述】
给定一个字符串S（S的长度$<=1000$，仅包含小写字母）。你需要找到S中的两个不相交的非空子串$s_1$,$s_2$，$s_1$在$s_2$左边，且满足$s_1+s_2$是回文串。问有多少种方案。我们认为两个方案不同，当且仅当$s_1$在原串中的位置不同，或者$s_2$在原串中的位置不同。
【输入格式】
输入一行，包含字符串S。
【输出格式】
输出一行答案。
【输入样例】
abba【输出样例】
7满足条件的方案如下：(“a”, “a”)、(“a”, “ba”)、(“a”, “bba”)、(“ab”, “a”)、(“ab”, “ba”)、 (“abb”, “a”)、(“b”, “b”)。
【数据范围与约定】
对于100%的数据，串长<=1000。
20% $n<=100$
题解
先考虑$|s2|<|s1|$情况，显然s1是由~s2（即s2的翻转）和一个回文串连接而成，可以先区间dp求出$[i,j]$是否为回文串，然后前缀和求出以i为起点，终点位于$[l,r]$的回文串总数
枚举l,r，l表示s1中~s2和回文串的分界处，r表示s2的开头，可以算出合法的以l为起点，终点小于r的回文串数$s$，然后二分+哈希求出l前与r后可以匹配的最长串长度为$t$，则对答案贡献$s*t$
同理处理$|s1|<|s2|$和$|s1|=|s2|$的情况
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
char s[1005];
int n,f[1005][1005],g[1005][1005];
ull p[1005],hs[2][1005],pr=131,ans;
ull getA(int l,int r){
return hs[0][r]-hs[0][l-1]*p[r-l+1];
}
ull getB(int l,int r){
return hs[1][l]-hs[1][r+1]*p[r-l+1];
}
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
scanf("%s",s+1);
n=strlen(s+1);
p[0]=1;
for (int i=1;i<=n;++i) p[i]=p[i-1]*pr;
for (int len=1;len<=n;++len){
for (int i=1;i<=n-len+1;++i){
int j=i+len-1;
if (i==j || len==2&&s[i]==s[j]) f[i][j]=1;
else if (len>2) f[i][j]=(s[i]==s[j])*f[i+1][j-1];
}
}
for (int i=1;i<=n;++i){
for (int j=i;j<=n;++j){
g[j][i]=f[i][j];
}
}
for (int i=1;i<=n;++i){
for (int j=i;j<=n;++j){
f[i][j]+=f[i][j-1];
}
}
for (int i=1;i<=n;++i){
for (int j=i;j>=1;--j){
g[i][j]+=g[i][j+1];
}
}
for (int i=1;i<=n;++i){
hs[0][i]=hs[0][i-1]*pr+s[i]-'a'+1;
}
for (int i=n;i>=1;--i){
hs[1][i]=hs[1][i+1]*pr+s[i]-'a'+1;
}
for (int l=1;l<=n;++l){
for (int r=l+1;r<=n;++r){
int s1=f[l][r-1];
int L=1,R=min(l-1,n-r+1),A=0;
while (L<=R){
int M=(L+R)>>1;
if (getB(l-M,l-1)==getA(r,r+M-1)){
A=M;
L=M+1;
}else R=M-1;
}
ans+=s1*(A);
}
}
for (int l=1;l<=n;++l){
for (int r=l+1;r<=n;++r){
int s1=g[r][l+1];
int L=1,R=min(l,n-r),A=0;
while (L<=R){
int M=(L+R)>>1;
if (getB(l-M+1,l)==getA(r+1,r+M)){
A=M;
L=M+1;
}else R=M-1;
}
ans+=s1*A;
}
}
for (int l=1;l<=n;++l){
for (int r=l+1;r<=n;++r){
int L=1,R=min(l,n-r+1),A=0;
while (L<=R){
int M=(L+R)>>1;
if (getB(l-M+1,l)==getA(r,r+M-1)){
A=M;
L=M+1;
}else R=M-1;
}
ans+=A;
}
}
cout<<ans<<endl;
return 0;
}七彩路径(colorful)
【题目描述】
给定一棵n个点的树，每个节点上有一种颜色，第i个节点上的颜色为c_i。
给定树上的一条路径，定义这条路径的美丽程度为这条路径包含的所有节点的不同的颜色数量。
这棵树上有n(n-1)/2条不同的路径，求这些路径的美丽程度的和。
【输入格式】
第一行一个正整数n。表示树上的节点数。
第二行n个正整数，第i个正整数表示第i个节点上的颜色c_i。
接下来n-1行，每行两个正整数u,v表示在u,v两个节点之间有一条边。
【输出格式】
输出一行答案。
【输入样例】
6
1 2 1 3 2 1
1 2
1 3
2 4
2 5
3 6【输出样例】
29【数据范围与约定】
对于100%的数据，$n≤500000,1≤c_i≤500000$
题解
首先分开考虑每种颜色，也就是拆成n棵只存在当前枚举的颜色，其他颜色视为无色的树。那么就变成了求所有路径中经过这种颜色的路径数，这样还是不好求，再转化一下，如果我们知道所有路径中没有经过这种颜色的路径数也可以算出答案。
对于求没有进过这个颜色的路径数，我们可以把这棵树上这种颜色的点删掉，就得到了一些联通块，每个联通块中的全部路径都是要求的。于是就可以对每棵树dfs一遍，得到结果，时间复杂度是O(N*N)，显然会TLE。
继续优化，可以发现，在dfs的过程中，我们只关心和当前节点颜色相同的节点，于是我们就可以考虑使用虚树，也就是不用真的把原树拆开，我们只需要同时维护所有颜色的信息，在dfs到一个节点是只使用和更新当前颜色的信息即可。这样就可一遍dfs解决所有问题，时间复杂度就减为O(N)，十分完美。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct path{
int Next,y;
}Pth[1000005];
ll ans;
int n,head[500005],Col[500005],cnt,NotIn[500005],NotInRoot[500005],top[500005],size[500005];
inline void add(int x,int y){
cnt++;
Pth[cnt].Next=head[x];
Pth[cnt].y=y;
head[x]=cnt;
}
inline ll calc(ll x){return x*(x-1)/2;}
void dfs(int u,int prv){
int NxtTop=top[Col[u]];
top[Col[u]]=u;
size[u]=1;
for (int i=head[u];i;i=Pth[i].Next){
int v=Pth[i].y;
if (v==prv) continue;
NotIn[u]=0;
dfs(v,u);
size[u]+=size[v];
ans-=calc(size[v]-NotIn[u]);
}
if (NxtTop){
NotIn[NxtTop]+=size[u];
}else NotInRoot[Col[u]]+=size[u];
top[Col[u]]=NxtTop;
}
int main(){
freopen("colorful.in","r",stdin);
freopen("colorful.out","w",stdout);
cin>>n; ans=calc(n)*n;
for (int i=1;i<=n;++i){
scanf("%d",&Col[i]);
}
for (int i=1;i<n;++i){
int x,y;
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(1,-1);
for (int i=1;i<=n;++i) ans-=calc(n-NotInRoot[i]);
cout<<ans<<endl;
return 0;
}树
-
树形dp
- 距离相关
- 路径相关
- 连通块相关
例题
保卫王国
没有上司的舞会
站岗
侦察守卫 给定一棵树，边权均为1，每个点上可以建立通讯站，在第i个点上建立通讯站的费用是wi，对于没有建立通讯站的点，它的通讯费用为sd，d为离他最近的通讯站的距离，求最小的通讯费用，其中s单调递增
$f[i][j][k=0/1]$表示第i个点离它的最近通讯站距离为j，且该通讯站在i的子树外/内
$f[i][j][1]=\sum \min(f[i][j-1][1],f[1][j+1][0],f[1][j+1][1],f[i][j][1])$,且至少有一个孩子为第一项
$f[i][j][0]$同理，但不用特殊指定一项 有一棵点数为 N 的树，树边有边权。给你一个在 0~ N 之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。链接
考虑每条边的贡献，$f[i][j]$表示第i个点，i的子树有j个黑点，那么转移到父亲时，它与父亲的连边的贡献就很好做了 CF1039D
CF1097G
赛道修建 给定一棵树，求有多少个连通块
$f[i]$表示以i为根的联通块的数量，$f[i]*=f[j]+1$，其中j为i的儿子节点，最后全部加和即可 给定一颗树，点带权，求出点权和最小的连通块
$f[i]$表示以i为根的连通块的答案，$f[i]=v[i]+\sum \min(0,f[son])$ 给定一棵树，每个点有一种颜色，求出取出颜色不超过两种的连通块的方案数，每条边连接的点颜色不同
$f[i][j]$表示以i为根的连通块，除了i节点的颜色外还有一个j的颜色$f[i][j]*=1+f[u][c[i]]，c[u]=j$
虚树
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/cxjy-day-5/
