加塞
rnk7,\(100+30+10+15=155\)。
题目来源:2022 牛客 OI 赛前集训营-提高组(第三场)
T1 一般图最小匹配
说的很复杂,实际水题。就是从 \(n\) 个数中选 \(2m\) 个数,两个两个求差后,求这个差的和的最小值。
显然排序之后求差是最小的,但显然不能直接贪心,考虑 DP。
先排序,然后设 \(\mathit{dp}_{i,j}\) 表示前 \(i\) 个数选 \(j\) 组的方案数,在以下两种情况中取 \(\min\):
- 不选当前数,即 \(\mathit{dp}_{i-1,j}\);
- 选当前数,即 \(\mathit{dp}_{i-2,j-1}+a_i-a_{i-1}\)。
初始化 \(\forall\mathit{dp}_{i,j}=\infty\) 且 \(\forall\mathit{dp}_{i,0}=0\),答案即为 \(\mathit{dp}_{n,m}\)。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
putchar(sf);
}
constexpr int MAXN=5005;
int n,m,a[MAXN];
long long dp[MAXN][MAXN];
int main(){
freopen("match.in","r",stdin);
freopen("match.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;++i)a[i]=read();
sort(a+1,a+n+1);
memset(dp,0x3f,sizeof(dp));
for(int i=0;i<=n;++i)dp[i][0]=0;
for(int i=2;i<=n;++i)
for(int j=1;j<=m;++j)
dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+a[i]-a[i-1]);
write(dp[n][m]);
return fw,0;
}
T2 重定向
不难,没搞出来可惜了。
首先,50pts 的 \(O(Tn^2\log n)\) 暴力是好想的,暴力枚举要删除的位置,用 set 维护当前最小能填的数,在最终的序列中取字典序最小的即可。可以用 vector 自带重载小于运算符,直接比较字典序。实际上这个复杂度过不了,不知是否是出题人有意放过,但让我丢了 20pts。
考虑正解。发现复杂度瓶颈主要在求出最优的删除位置,那么我们就调用我们智慧的人类大脑得:
- 若 \(a_i\ne0\land a_{i+1}\ne0\),那么将 \(i\) 删除最优当且仅当 \(a_i>a_{i+1}\);
- 若 \(a_i\ne0\land a_{i+1}=0\),那么将 \(i\) 删除最优当且仅当 \(a_i>w\),其中 \(w\) 是当前序列能填的最小数;
- 若 \(a_i=0\),则只有位置 \(i\) 的后缀最小值小于当前序列能填的最小数时,删除这个后缀最小值第一次出现的位置最优。换句话说,如果后面出现了一个更小的,把这个更小的数放到前面是更优的。
如果没找到,默认删除 \(n\) 即可。注意删除的这个点的值在最后是可以回填进序列中的。找到了最优删除位置,填数就很简单。复杂度 \(O(Tn\log n)\),2s 时限加上出题人的有意防水,能过。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define INF 0x3f3f3f3f
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
putchar(sf);
}
constexpr int MAXN=2e5+5;
int T,n,a[MAXN],tmp[MAXN];
int minn[MAXN],pos[MAXN];
int main(){
freopen("repeat.in","r",stdin);
freopen("repeat.out","w",stdout);
T=read();
while(T--){
set<int>st;
n=read();
for(int i=1;i<=n;++i)pos[i]=0;
for(int i=1;i<=n;++i)pos[a[i]=read()]=i;
for(int i=1;i<=n;++i)if(!pos[i])st.emplace(i);
minn[n+1]=INF;
for(int i=n;i;--i)minn[i]=min(minn[i+1],a[i]?a[i]:INF);
int del=n;
for(int i=1;i<n;++i)
if(a[i]&&a[i+1]&&a[i]>a[i+1]){
del=i;st.emplace(a[i]);break;
}else if(a[i]&&!a[i+1]&&a[i]>*st.begin()){
del=i;st.emplace(a[i]);break;
}else if(!a[i]){
if(minn[i]<*st.begin()){
a[i]=minn[i],del=pos[a[i]];break;
}
a[i]=*st.begin(),st.erase(a[i]);
}
for(int i=1;i<=n;++i){
if(a[i]||del==i)continue;
a[i]=*st.begin(),st.erase(a[i]);
}
for(int i=1;i<=n;++i)if(del^i)write(a[i],' ');
putchar('\n');
}
return fw,0;
}
T3 斯坦纳树
需要用到虚树的思想,不过输出全 1 就有 10pts。
我们首先考虑什么情况下牛的做法会假,实际上就是这种情况:
正确的斯坦纳树边权和是 \(3\),但牛的做法边权和是 \(4\)。
进而我们想到,用询问的点集作为关键点构造虚树,那么一旦虚点(图中是 \(\boldsymbol2\))的度数 \(\boldsymbol{\ge3}\) 时,牛的做法一定会假。
否则,当虚点度数 \(<3\) 时,只有两种情况:
- 若度数为 \(1\),直接删除虚点,此时必不会影响答案;
- 若度数为 \(2\),将虚点的两端连起来即可。
但是,这样我们少考虑了一种情况:如果边权是 \(0\),那么即使边被多跑了,答案不会受到影响。
所以我们需要用并查集维护连通块,把边权为 \(0\) 的两端合并,连通块被删除当且仅当它里面的所有点被删除。至于维护,我们从后往前删点(注意这个 trick 已经很老了),按上述策略维护虚点,如果操作后无虚点,则牛的做法为真,否则为假。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
constexpr int MAXN=3e5+5;
int n,p[MAXN],cnt[MAXN],ans[MAXN],sum;
struct Edge{
int u,v,w;
bool operator<(const Edge&x)const{
return w<x.w;
}
}e[MAXN];
int f[MAXN],siz[MAXN];
int find(int x){
if(f[x]^x)f[x]=find(f[x]);
return f[x];
}
unordered_set<int>st[MAXN];
void del(int x){
if(st[x].size()<=2&&!cnt[x]){
--sum;
int tmp[3],len=0;
for(auto v:st[x]){
tmp[++len]=v;
st[v].erase(x);
}
st[x].clear();
if(len==2){
st[tmp[1]].emplace(tmp[2]);
st[tmp[2]].emplace(tmp[1]);
}
for(int i=1;i<=len;++i)del(tmp[i]);
}
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n=read();
iota(f+1,f+n+1,1);
for(int i=1,u,v,w;i<n;++i){
u=read(),v=read(),w=read();
e[i]={u,v,w};
if(!w)f[find(u)]=find(v);
}
for(int i=1;i<n;++i){
if(!e[i].w)continue;
st[find(e[i].u)].emplace(find(e[i].v));
st[find(e[i].v)].emplace(find(e[i].u));
}
for(int i=1;i<=n;++i)++cnt[find(p[i]=read())];
for(int i=n;~i;--i){
ans[i]=!sum;
if(!--cnt[find(p[i])])++sum,del(find(p[i]));
}
for(int i=1;i<=n;++i)write(ans[i],'#');
return putchar('\n'),fw,0;
}
标签:删除,mathit,buf,obuf,虚点,加塞,dp
From: https://www.cnblogs.com/laoshan-plus/p/18438201