关于程序员:浙江大学软件学院2020年保研上机试题题解

参考代码：

#include <bits/stdc++.h>
using namespace std;

int n;
int rot[15], ans[15] = {0};    // 别离存储不同次幂对应的系数

void dfs(int now, int exp, int an){if(now == n){ans[exp] += an;
        return;
    }
    dfs(now+1,exp+1, an);
    dfs(now+1, exp, an*rot[now]);
}

int main(){
    int root;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){scanf("%d", &rot[i]);
        rot[i] = -rot[i];
    }
    dfs(0,0,1); // 前面相乘的参量初始化为 1
    for(int i = n-1; i >= 0; i--)   printf("%d%s", ans[i], i == 0 ? "\n" : " ");
    return 0;
}

参考代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 10010;
const int INF = 0x3fffffff;

struct triple{int pos1, pos2, pos3;};

int seq1[maxn], seq2[maxn], seq3[maxn];

int dis(int p1, int p2, int p3){int maxNum = max(max(seq1[p1], seq2[p2]), seq3[p3]);
    int minNum = min(min(seq1[p1], seq2[p2]), seq3[p3]);
    return (maxNum-minNum)*2;
}

int main(){
    int n1, n2, n3;
    scanf("%d %d %d", &n1, &n2, &n3);
    for(int i = 0; i < n1; i++) scanf("%d", &seq1[i]);
    for(int i = 0; i < n2; i++) scanf("%d", &seq2[i]);
    for(int i = 0; i < n3; i++) scanf("%d", &seq3[i]);
    sort(seq1, seq1+n1);
    sort(seq2, seq2+n2);
    sort(seq3, seq3+n3);
    int p1 = 0, p2 = 0, p3 = 0;
    int minD = INF;
    triple ans;
    while(1){int maxNum = max(max(seq1[p1], seq2[p2]), seq3[p3]);
        int minNum = min(min(seq1[p1], seq2[p2]), seq3[p3]);
        if((maxNum-minNum)*2 <= minD){minD = (maxNum-minNum)*2;
            ans.pos1 = p1;
            ans.pos2 = p2;
            ans.pos3 = p3;
        }
        if(seq1[p1] == minNum){
            p1++;
            if(p1 == n1)    break;
        }
        else if(seq2[p2] == minNum){
            p2++;
            if(p2 == n2)    break;
        }
        else{
            p3++;
            if(p3 == n3)    break;
        }
    }
    // 最初这部分调节很重要，即调节两头的数字使其最大但不影响总的最小间隔
    while(ans.pos1+1 < n1 && minD == dis(ans.pos1+1, ans.pos2, ans.pos3))   ans.pos1++;
    while(ans.pos2+1 < n2 && minD == dis(ans.pos1, ans.pos2+1, ans.pos3))   ans.pos2++;
    while(ans.pos3+1 < n3 && minD == dis(ans.pos1, ans.pos2, ans.pos3+1))   ans.pos3++;
    printf("MinD(%d, %d, %d) = %d\n", seq1[ans.pos1], seq2[ans.pos2], seq3[ans.pos3], minD);
    return 0;
}

参考代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 10010;

struct student{int id, score;}stu[1010];

struct node{
    int id;
    int num = 0, totalS = 0;
}isRoot[maxn];

int n;
int father[maxn];
int exist[maxn] = {0};
vector<node> ans;

void init(){for(int i = 0; i < maxn; i++){father[i] = i;
    }
}

int findFather(int a){
    int x = a;
    while(a != father[a]){a = father[a];
    }
    while(x != a){int tmp = father[x];
        father[x] = a;
        x = tmp;
    }
    return a;
}

void Union(int a, int b){int fa = findFather(a);
    int fb = findFather(b);
    if(fa < fb) father[fb] = fa;
    else if(fb < fa)    father[fa] = fb;
}

bool cmp(node a, node b){if(a.totalS != b.totalS)    return a.totalS > b.totalS;
    else if(a.num != b.num) return a.num < b.num;
    else    return a.id < b.id;
}

int main(){init();
    int k, teammate, score;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){scanf("%d %d", &stu[i].id, &k);
        exist[stu[i].id] = 1;
        for(int j = 0; j < k; j++){scanf("%d", &teammate);
            exist[teammate] = 1;
            Union(stu[i].id, teammate);
        }
        scanf("%d", &stu[i].score);
    }
    for(int i = 0; i < n; i++){// 只能统计分数信息
        int f = findFather(stu[i].id);
        isRoot[f].id = f;
        isRoot[f].totalS += stu[i].score;
    }
    for(int i = 0; i < maxn; i++){// 统计人数信息
        if(exist[i]){int f = findFather(i);  // 此处 i 就是学生 id 不要再调用.id 了
            isRoot[f].num++;
        }
    }
    for(int i = 0; i < maxn; i++){if(isRoot[i].num)   ans.push_back(isRoot[i]);
    }
    sort(ans.begin(), ans.end(), cmp);
    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i++) printf("%04d %d %d\n", ans[i].id, ans[i].num, ans[i].totalS);
    return 0;
}

参考代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;

int n, money;
int item[maxn], coupon[maxn];

struct node{
    int id1, id2;   // 别离代表商品编号和代金券编号
    friend bool operator < (node a, node b){return item[a.id1] - coupon[a.id2] > item[b.id1] - coupon[b.id2];
    }
};

bool cmp(int a, int b){return a > n;}

int main(){scanf("%d %d", &n, &money);
    for(int i = 0; i < n; i++)  scanf("%d", &item[i]);
    for(int i = 0; i < n; i++)  scanf("%d", &coupon[i]);
    sort(item, item+n);
    sort(coupon, coupon+n, cmp);
    priority_queue<node> q;
    for(int i = 0; i < n; i++){q.push(node{i, 0});
    }
    int cnt = 0;
    while(!q.empty()){node first = q.top();
        q.pop();
        if(money >= item[first.id1] - coupon[first.id2]){money -= (item[first.id1]-coupon[first.id2]);
            cnt++;
            if(first.id2+1 < n) q.push(node{first.id1, first.id2+1});   // 最初的 id2 用 + 1 不要用 ++
        }else   break;
    }
    printf("%d %d\n", cnt, money);
    return 0;
}