本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-01 16:21:44
得分
得分太少，不想说了……
T1
歪解
本来想要贪心，但是自己随便写了一组数就挂了，所以了一点点 rand，自己的数据对了不少，但是好像没有得分。
正解
DP！！！
首先应该将数组排序，当只有一个或者零个数时，无法组成一组数，所以把 $dp[0][1~n]$ 和$dp[1][1~n]$ 赋成最大值。 对于 $dp[i][j]$ 有两种情况
1： 本身不被选，那么 $dp[i][j]$ 就等于 $dp[i-1][j]$。
2： 本身被选，那么 $dp[i][j]$ 就等于 $dp[i-2][j-1]$,因为与这个数最近的数一定是它的前一个，并且之前有 $j-1$ 组时才能变成 $j$ 组。
代码（正确的）：
#include<bits\/stdc++.h>
#define int long long
using namespace std;
inline long long read() {
long long s = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') {
s = (s << 3) + (s << 1) + (ch ^ 48);
ch = getchar();
}
return s;
}
inline void write(long long x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x \/ 10);
putchar(x % 10 + '0');
}
int a[1000005];
int n,m;
int dp[5005][5005];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) dp[0][i]=0x3f3f3f3f3f3f3f3f,dp[1][i]=0x3f3f3f3f3f3f3f3f;
for(int i=2;i<=n;i++){
dp[i][0]=0;
for(int j=1;j<=m;j++){
dp[i][j]=dp[i-1][j];
dp[i][j]=min(dp[i][j],min(dp[i-2][j-1]+a[i]-a[i-1],dp[i-1][j]));
}
}
cout<<dp[n][m];
return 0;
}
T2
错误的做法：贪心
也不知道哪里贪的不对，但是就是不对。
正确的做法：贪心
也不知道哪里贪对了，但是就是贪对了。
思路（我自己的）
大体分为两种情况。
第一种是在原先的数列中已经有了 1。这时考虑是否要把 1 提前，如果把 1 提前，那么就把 1 提前，不然就删去上升序列中的最后一个数。
第二种是在原先的队列中没有 1，那么就加上 1，然后删去上升序列中的最后一个数（如果 $n>2$，那么一定不能是 1）。
最后一步就是 WA 了。
错误的代码：
#include<bits\/stdc++.h>
#define int long long
using namespace std;
int t,n,a[2000005];
set<int> s;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--){
cin>>n;
int uu=0,flag=n+1;
a[n+1]=0;
for(int i=1;i<=n;i++) s.insert(i);
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==1) flag=i;
if(a[i]==0&&uu==0) uu=i;
s.erase(a[i]);
}
if(s.count(1)){
s.erase(1);
a[uu]=1;
for(int i=1;i<=n;i++){
if(i==uu) continue;
if(a[i]>a[i+1]){
s.insert(a[i]);
a[i]=-1;
break;
}
}
}
else if(uu<flag&&uu!=0){
if(a[uu-1]>*s.begin()){
s.insert(a[uu-1]);a[uu-1]=-1;
}
else {
a[flag]=-1;
s.insert(1);
}
}
else {
for(int i=1;i<=n;i++){
if(a[i+1]==0){
if(a[i]>*s.begin()){
s.insert(a[i]);
a[i]=-1;
break;
}
}
else if(a[i]>a[i+1]){
s.insert(a[i]);
a[i]=-1;
break;
}
}
}
int flagg=0;
for(int i=1;i<=n;i++){
if(flagg==0&&i==n) continue;
if(a[i]>0) cout<<a[i]<<" ";
else if(a[i]==0){
cout<<*(s.begin())<<" ";
s.erase(*(s.begin())) ;
}
else flagg=1;
}
cout<<"\n";
}
return 0;
}
T3
上来写了一大堆，然后样例都没有过，调了半个小时，然后还是没有过样例。
正解
好像是找到虚点所连接在集合中的点的个数，如果大于 3，就说明会出错。（还要把边权为 0 的点合并）
自己写的
先求集合中的最小生成树，再把原图中的点删除一部分，把剩下的再求一下最小生成树，比较是否相同（就是纯模拟了一遍题意）。然后就错了。
错误的代码
#include<bits\/stdc++.h>
#define int long long
using namespace std;
struct nd{
int y,z;
};
int cnt;
struct nt{
int x,y,z;
}s[1000005],c[1000005];
int fa[1000005],minn=0x3f3f3f3f;
vector<nd> v[105];
int a[105],n,m;
set<int> ss;
int mp[105][105];
queue<int> q;
bool cmp(nt x,nt y){
return x.z<y.z;
}
void bfs(int r){
q.push(r);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<v[x].size();i++){
int xx=v[x][i].y;
if(xx==r||mp[r][xx]) continue;
mp[r][xx]=mp[r][x]+v[x][i].z;
q.push(xx);
}
}
}
int find(int x) {
while (x != fa[x]) x = fa[x];
return x;
}
int kruskal(){
int sum=0,t=0;
for(int i=1;i<m;i++){
s[++cnt]={mp[a[m]][a[i]],a[m],a[i]};
}
sort(s+1,s+1+cnt,cmp);
for(int i=1;i<=n;i++) {
fa[i]=i;
}
for(int i=1;i<=cnt;i++){
int fx=find(s[i].x),fy=find(s[i].y);
if(fx!=fy){
fa[fy]=fx;
sum+=s[i].z;
++t;
if(t==m-1) break;
}
}
return sum;
}
int kruskals(){
int cntt=0;
for(auto i:ss){
for(int j:ss){
c[++cntt]={mp[i][j],i,j};
}
}
int sum=0,t=0;
sort(s+1,s+1+cnt,cmp);
for(int i=1;i<=n;i++) {
fa[i]=i;
}
for(int i=1;i<=cntt;i++){
int fx=find(c[i].x),fy=find(c[i].y);
if(fx!=fy){
fa[fy]=fx;
sum+=c[i].z;
++cnt;
if(t==m-1) break;
}
}
return sum;
}
void match(int x){
if(x==n+1) return ;
minn=min(minn,kruskals());
for(int i=x+1;i<=n;i++){
if(ss.count(i)) continue;
ss.insert(i);
match(i);
ss.erase(i);
}
match(x+1);
}
signed main() {
\/\/ freopen("steiner.in","r",stdin);
\/\/ freopen("steiner.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int x,y,z;
cin>>x>>y>>z;
v[x].push_back({y,z});
v[y].push_back({x,z});
}
for(int i=1;i<=n;i++){
bfs(i);
}
for(int i=1;i<=n;i++){
cin>>a[i];
m=n;
for(int j=1;j<=m;j++) ss.insert(a[j]);
minn=0x3f3f3f3f;
match(1);
if(kruskal()!=minn){
cout<<0;
}
else {
cout<<1;
}
}
\/\/ fclose(stdin);
\/\/ fclose(stdout);
return 0;
}
T4
死于苹果（ios）……
高效的思路
输出 $1$，即可得 15 分，但是因为关了同步，所以 0。
鲁ICP备2025150228号