Codeforces Round #543 Div1题解
A. Diana and Liana
给定一个长度为\(m\)的序列，你可以从中删去不超过\(m-n*k\)个元素，剩下的元素从左往右每\(k\)个一组，最后一组可以不满。给定你一个大小为\(|S|\)的可重集，要求你分出的组中至少有一组构成的可重集包含了给定的可重集。
构造一种符合条件的删数方案。
\(n,m,k,|S|\le 5*10^5\)
写了\(1h\)才过，感觉身败名裂。
考虑枚举一个右端点\(r\)，显然可以确定一个最大的\(l\)恰好包含了这个可重集，那么\(check\)一下这段\([l,r]\)是否满足条件就好了。显然这个\(l\)随着\(r\)向右移动也是单调的。
然后\(WA\)了半天，最后为了方便，强制\(r-l+1\ge k\)，这样子只需要在\(l\)之前删掉\((l-1)\%k\)个，在\([l,r]\)之间删去\(r-l+1-k\)个，就很好写了。。。
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 500500
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int m,K,n,S,tot,Del,a[MAX],b[MAX],c[MAX],d[MAX];
int main()
{
m=read();K=read();n=read();S=read();Del=m-K*n;
for(int i=1;i<=m;++i)a[i]=read();
for(int i=1;i<=S;++i)if(!b[read()]++)++tot;
for(int l=1,r=1;r<=m;++r)
{
++c[a[r]];tot-=c[a[r]]==b[a[r]];
while(!tot&&r-l+1>K&&l<=m&&c[a[l]]>b[a[l]])--c[a[l]],++l;
if(!tot&&r-l+1>=K)
{
int v=(l-1)%K+r-l+1-K;
if(v>Del)continue;
printf("%d\n",v);if(!v)return 0;
for(int i=1;i<=(l-1)%K&&v;++i)printf("%d ",i),--v;
for(int i=l;i<=r&&v;++i)
if(d[a[i]]+1>b[a[i]])
printf("%d ",i),--v;
else d[a[i]]+=1;
return 0;
}
}
puts("-1");
return 0;
}
B. Once in a casino
你有一个长度为\(n\)的，值域为\(0-9\)的元素序列，每次可以给相邻两个元素同时加一或者减一，但是仍然要在\(0-9\)的范围之内。回答能否把当前这些元素变成给定的某个元素序列，如果可以输出方案的前\(10^5\)步，否则输出\(-1\)。
\(n\le 10^5\)。
首先不需要考虑在值域范围内的问题，从头到尾依次算一下，看看能否变过去就行了。
现在构造方案，比如说你现在要给\(x,x+1\)位置加一，但是\(x+1\)位置是\(9\)，那么你就递归处理，先让\(x+1\)位置减去一个\(1\)，递归回来之后再给\(x,x+1\)位置\(+1\)。
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 100100
int n,a[MAX],b[MAX],c[MAX];long long ans;char ch[MAX];
void init(int *a){scanf("%s",ch+1);for(int i=1;i<=n;++i)a[i]=ch[i]-48;}
void dfs(int x,int w)
{
if(!ans)return;
if(0<=a[x+1]+w&&a[x+1]+w<=9){printf("%d %d\n",x,w);a[x]+=w,a[x+1]+=w;--ans;return;}
dfs(x+1,-w);if(!ans)return;printf("%d %d\n",x,w);a[x]+=w;a[x+1]+=w;--ans;
}
int main()
{
scanf("%d",&n);init(a);init(b);
for(int i=1;i<=n;++i)c[i]=a[i];
for(int i=1;i<n;++i){int d=b[i]-c[i];c[i]+=d;c[i+1]+=d;ans+=abs(d);}
if(c[n]!=b[n]){puts("-1");return 0;}
cout<<ans<<endl;ans=min(ans,100000ll);
for(int i=1;i<n&&ans>0;++i)
while(a[i]!=b[i]&&ans>0)dfs(i,(b[i]-a[i])/abs(b[i]-a[i]));
return 0;
}
C. Compress String
给定一个串，你可以把它进行划分，有两种划分方式：要么是一个字符成一组，代价是\(a\)；要么是\([l,r]\)划分一组，要求\([l,r]\)是\([1,l-1]\)的一个子串，代价是\(b\)。求最小代价。
\(|S|\le 5000\)。
一边构建\(SAM\)一边\(dp\)，就很简单。。。
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 5050
int n,a,b,f[MAX];char s[MAX];
struct Node{int son[26],ff,len;}t[MAX<<1];
int tot=1,last=1;
void extend(int c)
{
int p=last,np=++tot;last=np;t[np].len=t[p].len+1;
while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].ff;
if(!p)t[np].ff=1;
else
{
int q=t[p].son[c];
if(t[q].len==t[p].len+1)t[np].ff=q;
else
{
int nq=++tot;
t[nq]=t[q];t[nq].len=t[p].len+1;
t[np].ff=t[q].ff=nq;
while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].ff;
}
}
}
int main()
{
scanf("%d%d%d%s",&n,&a,&b,s+1);
for(int i=1;i<=n;++i)f[i]=1e9;
for(int i=1;i<=n;++i)
{
extend(s[i]-97);f[i]=min(f[i],f[i-1]+a);
for(int j=i+1,u=1;j<=n;++j)
{
int c=s[j]-97;
if(!t[u].son[c])break;
f[j]=min(f[j],f[i]+b);
u=t[u].son[c];
}
}
printf("%d\n",f[n]);
return 0;
}
D. Power Tree
给定一棵树，每个点你可以选或者不选，如果选就有一个代价，现在对于每个叶子节点，要求其到根节点的路径上选择的点的集合必须非空且两两不同，求最小代价。
\(n\le 200000\)。
如果有\(k\)个叶子节点，那么一定会被选择\(k\)个点。
如果一个节点的儿子有多个叶子节点，那么至多只会有一个叶子节点不被选择。因此每个点的子树内要么选择了叶子节点个数个节点，要么是叶子个数减一。那么设\(f[u][j=0/1]\)表示这个子树内选择了叶子节点个数\(-j\)个节点的最小代价。
考虑如何转移：
\(f[u][1]=\min_v\{f[v][1]+\sum_{w\neq v}f[w][0]\}\)
\(f[u][0]=\min\{\sum f[v][1],f[u][0]+c[u]\}\)
对于求解每个点是否可能在最优方案中，则倒着\(dp\)再处理一遍就行了。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 200200
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
struct Line{int v,next;}e[MAX<<1];
int h[MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
int n,c[MAX],S[MAX],top;ll f[MAX][2];
bool leaf(int u){return !e[h[u]].next;}
void dfs(int u,int ff)
{
ll s=0;if(ff&&leaf(u)){f[u][1]=c[u];f[u][0]=0;return;}
f[u][0]=f[u][1]=1e18;
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff)dfs(e[i].v,u),s+=f[e[i].v][1];
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff)f[u][0]=min(f[u][0],s-f[e[i].v][1]+f[e[i].v][0]);
f[u][1]=min(s,f[u][0]+c[u]);
}
bool visf[MAX][2];
void find(int u,int ff)
{
if(visf[u][1])
{
if(f[u][1]==f[u][0]+c[u])S[++top]=u,visf[u][0]=true;
ll s=0;
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff)s+=f[e[i].v][1];
if(f[u][1]==s)
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff)visf[e[i].v][1]=true;
}
if(visf[u][0])
{
ll tmp=1e18;int tot=0;
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff)tmp=min(tmp,f[e[i].v][0]-f[e[i].v][1]);
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff)tot+=(tmp==f[e[i].v][0]-f[e[i].v][1]);
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff)
{
if(tot>1||tmp<f[e[i].v][0]-f[e[i].v][1])visf[e[i].v][1]=true;
if(tmp==f[e[i].v][0]-f[e[i].v][1])visf[e[i].v][0]=true;
}
}
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=ff)find(e[i].v,u);
}
int main()
{
n=read();
for(int i=1;i<=n;++i)c[i]=read();
for(int i=1,u,v;i<n;++i)u=read(),v=read(),Add(u,v),Add(v,u);
dfs(1,0);
printf("%I64d ",f[1][1]);visf[1][1]=true;
find(1,0);sort(&S[1],&S[top+1]);
printf("%d\n",top);for(int i=1;i<=top;++i)printf("%d ",S[i]);puts("");
return 0;
}
QwQ
剩下的题它们都鸽了。
主要是前面把我写自闭了