『模拟赛』csp-s模拟赛6
挂分日寄：0+20+0+0
喵喵赛时对拍拍了10000个点都没拍出来，赛后一下就拍出错来了，我谔谔。
T1
DP喵~
首先 sort 一遍方便处理 其实转移时加一个 abs 取绝对值就可，纯纯多此一举
设 \(f[i,j,1/0]\) 为前 \(i\) 个数中选 \(j\) 个的最小值
若选当前这个数，则 \(f[i,j,1]=f[i-1,j-1,0]+a[i]-a[i-1]\)
若不选当前这个数，则 \(f[i,j,0]=min(f[i-1,j,0],f[i-1,j,1]\)
考虑到可以用滚动数组滚调一维。
优化一下即可。
没了。
int n,m;
int f[2][N][2],a[N];signed main(){freopen("match.in","r",stdin);freopen("match.out","w",stdout);n=rd,m=rd;for(int i=1;i<=n;i++) a[i]=rd;sort(a+1,a+1+n);mst(f,0x3f);for(int i=2;i<=n;i++){int g=i&1;for(int j=0;j<=m;j++)f[g][j][0]=f[g][j][1]=inf;f[g^1][0][0]=0;for(int j=1;j<=m;j++){f[g][j][0]=min(f[g^1][j][0],f[g^1][j][1]);f[g][j][1]=f[g^1][j-1][0]+a[i]-a[i-1];}}printf("%lld",min(f[n&1][m][1],f[n&1][m][0]));return Elaina;
}
赛后听GGrun可反悔贪心的思路也不错。懒得打。遂咕咕。
T2
赛时近300行巨大贪心分讨。
总的来说就是手模几组数据发现最优解也就只有那几种操作。
比如说：把第一个数删掉；如果数组中有 \(1\) 那么删去 \(1\)...等等。
接下来码就完事了。
复杂度是 \(O(nq \times 常数)\)
Code（不建议点开）
int n,m,len; int a[N]; int now[N],ans[N]; mapbool cmp(int *x,int *y){//x<y?
// for(int i=1;i<=n;i++){
// cout<<x[i]<<' ';
// }
// cout<<endl;
for(int i=1;i<=n;i++){
if(x[i]<y[i]) return 1;
else if(x[i]>y[i]) return 0;
else continue;
}
return 1;
}
void work(){
// n=rd;
cin>>n;
vis.clear();
fill(ans,ans+1+n,inf);bool _0=1;int fst=0;
for(int i=1;i<=n;i++){cin>>a[i];
// a[i]=rd,
_0=_0&&(a[i]!=0),vis[a[i]]=i;
if(!fst && a[i]==0) fst=i;
}
if(!fst){for(int i=1;i<n;i++){cout<<i<<' ';}cout<<'\n';return ;
}int pre;
/---------------------------------------------/
len=0;
pre=vis[a[1]];
vis[a[1]]=0;
for(int i=2,cnt=0;i<=n;i++){
if(a[i]!=0){
now[++len]=a[i];
}else{
++cnt;
while(vis[cnt]) ++cnt;
now[++len]=cnt;
}
}
if(cmp(now,ans)){memcpy(ans,now,sizeof(int) *(n+1));
}vis[a[1]]=pre;
/---------------------------------------------/
len=0;
int mx=0,pos;
for(int i=1;i<=n;i++){if(a[i]>mx) mx=a[i],pos=i;else if(a[i]==mx) continue;else break;
}pre=vis[a[pos]];
vis[a[pos]]=0;for(int i=1,cnt=0;i<=n;i++){if(i==pos) continue;if(a[i]!=0){now[++len]=a[i];}else{++cnt;while(vis[cnt]) ++cnt;now[++len]=cnt;}
}
// for(int i=1;i<n;i++){
// cout<<now[i]<<' ';
// }
// cout<<endl;
if(cmp(now,ans)){memcpy(ans,now,sizeof(int) *(n+1));
}vis[a[pos]]=pre;
/---------------------------------------------/
len=0,mx=0;
pos=1;
for(int i=1;i<=n;i++){
if(a[i]i||a[i]0){
if(vis[i]&&vis[i]!=i){
pos=vis[i];
break;
}
}else break;
}
pre=vis[a[pos]];
vis[a[pos]]=0;for(int i=1,cnt=0;i<=n;i++){if(i==pos) continue;if(a[i]!=0){now[++len]=a[i];}else{++cnt;while(vis[cnt]) ++cnt;now[++len]=cnt;}
}if(cmp(now,ans)){memcpy(ans,now,sizeof(int) *(n+1));
}vis[a[pos]]=pre;
/---------------------------------------------/
len=0,mx=0,pos=0;
for(int i=1;i<=n;i++){
if(a[i]i||a[i]0) continue;
else if(a[i]>mx) mx=a[i],pos=i;
else break;
}
if(!pos){for(int i=1;i<n;i++) now[i]=i;if(cmp(now,ans)){memcpy(ans,now,sizeof(int) *(n+1));}
}pre=vis[a[pos]];
vis[a[pos]]=0;for(int i=1,cnt=0;i<=n;i++){if(i==pos) continue;if(a[i]!=0){now[++len]=a[i];}else{++cnt;while(vis[cnt]) ++cnt;now[++len]=cnt;}
}if(cmp(now,ans)){memcpy(ans,now,sizeof(int) *(n+1));
}vis[a[pos]]=pre;
/---------------------------------------------/
len=0;
if(vis[1]){
int mn=1,fnd=0;
while(a[1]>mn){if(!vis[mn]){fnd=1;break;}++mn;}if(fnd){int mx=0;for(int i=1;i<=n;i++){if(!a[i]){break;}if(a[i]>mx){mx=a[i];pos=i;}}vis[a[pos]]=0;for(int i=1,cnt=0;i<=n;i++){if(i==pos) continue;if(a[i]!=0){now[++len]=a[i];}else{++cnt;while(vis[cnt]) ++cnt;now[++len]=cnt;}}}else{pos=vis[1];vis[1]=0;for(int i=1,cnt=0;i<=n;i++){if(i==pos) continue;if(a[i]!=0){now[++len]=a[i];}else{++cnt;while(vis[cnt]) ++cnt;now[++len]=cnt;}}}
}else{if(fst)vis[a[1]]=0;a[fst]=1;vis[1]=fst;for(int i=1,cnt=0;i<=n;i++){if(i==fst) continue;if(a[i]!=0){now[++len]=a[i];}else{++cnt;while(vis[cnt]) ++cnt;now[++len]=cnt;}}
}if(cmp(now,ans)){memcpy(ans,now,sizeof(int) *(n+1));
}for(int i=1;i<n;i++){cout<<ans[i]<<' ';
// printf("%lld ",ans[i]);
}
cout<<'\n';
// putchar('\n');
}
signed main(){
// freopen("repeat.in","r",stdin);
// freopen("repeat.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
// int T=rd;
int T;
cin>>T;
while(T--)work();return Elaina;
}
T3
考虑到样例有个都是 \(1\)，所以我们直接 cout<<1 喜提 15pts
贴个官方题解吧，感觉挺详细的。
int n,m,sum,idx,a[N],ans[N];
int fa[N],cnt[N],son[N];
set<int> st[N];
struct EDGE{int frm,to;
}e[N];int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}void del(int x){if(st[x].size()<=2 && !cnt[x]){--sum;int num=0;for(auto to:st[x])son[++num]=to;st[x].clear();for(int i=1;i<=num;i++){for(int j=1;j<=num;j++){if(i==j) continue;st[son[i]].insert(son[j]);}st[son[i]].erase(x);}for(int i=1;i<=num;i++)del(son[i]);}
}signed main(){
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) fa[i]=i;for(int i=1,x,y,z;i<n;i++){cin>>x>>y>>z;if(!z){int a=find(x),b=find(y);if(a>b) swap(a,b);fa[b]=a;}elsee[++idx].frm=x,e[idx].to=y;}for(int i=1;i<n;i++)st[find(e[i].frm)].insert(find(e[i].to)),st[fa[e[i].to]].insert(fa[e[i].frm]);for(int i=1;i<=n;i++){cin>>a[i];a[i]=find(a[i]);++cnt[a[i]];}for(int i=n;i>=1;i--){ans[i]=(sum==0),--cnt[a[i]];if(!cnt[a[i]]) ++sum,del(a[i]);}for(int i=1;i<=n;i++)cout<<ans[i];return Elaina;
}
T4
考虑到样例有几个都是 \(1\)，所以我们直接 cout<<1 喜提 10pts
诶 这句话怎么感觉在哪见过
正解奇妙 \(O(n^6log(n))\) DP。
