掉大分

zibenlun · 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;
}

掉大分

得分

T1

歪解

正解