2020浙江大学计算机与软件学院保研上机题（代码简明）
小结
7-1
Standard Form of Polynomial
(20分)
The canonical representation of an algebraic polynomial of degree n is expressed as P(x)=a_n x^n + a_{n-1}x^{n-1} + ⋯ + a_1x + a_0. Given that the leading coefficient satisfies a_n=1 and all integer roots { r_1, ..., r_n } are present for the polynomial P(x), it can be expressed as the product (x−r_1)(x−r_2)⋯(x−r_n). Your task is to express the polynomial in its canonical form, factoring out all integer roots.
Input Specification:
Each input file includes exactly one test case. In each scenario, the first line provides a positive integer n (≤10), representing the degree of P(x). Following that, on the next line, there are n integer roots listed, separated by spaces.
Output Specification:
对于每一种情况，在一行中输出系数a_i（其中i从n−1到0）。确保所有数字之间仅用一个空格分隔，并且行末无多余的空格。我将确信所有计算结果都在整数范围之内。
Sample Input:
3
-1 4 -1Sample Output:
-2 -7 -4提示：深度优先搜索。
#include<cstdio>
#include<vector>
using namespace std;
const int maxn = 20;
int A[maxn],n;
bool vis[maxn]={false};
vector<int> v;
int cnt=0;
void dfs(int s,int limit)
{
v.push_back(s);
vis[s]=true;
if(v.size()==limit){
int tmp=1;
for(int i=0; i<v.size(); i++){
tmp*=A[v[i]];
}
cnt+=tmp;
v.pop_back();
vis[s]=false;
return;
}
for(int i=s+1; i<n; i++){
if(vis[i]==false){
dfs(i,limit);
}
}
vis[s]=false;
v.pop_back();
}
int main()
{
scanf("%d",&n);
for(int i=0; i<n; i++){
scanf("%d",&A[i]);
A[i]=-A[i];
}
for(int limit=1; limit<=n; limit++){
cnt=0;
for(int i=0; i<n; i++){
if(vis[i]==false){
dfs(i,limit);
}
}
printf("%d",cnt);
if(limit!=n) printf(" ");
else printf("\n");
}
return 0;
}7-2
Distance of Triples
(25分)
该三元组的距离定义为D(a, b, c) = |a - b| + |b - c| + |c - a|。考虑三个非空整数集合S₁、S₂和S₃，请确定所有可能组合中的最小距离。
Input Specification:
Each input file holds one test case. For every instance, the initial line provides three positive integers N₁、N₂ and N₃（each not exceeding 1e4）that denote the sizes of sets S₁、S₂ and S₃ correspondingly. Subsequently、the elements of these sets are listed in the following three lines separately. All figures mentioned here fall within integer values ranging from -1e4 to +1e4、and within each set they remain unique. The figures on a single line are separated by spaces.
Output Specification:
对于每一个情况，在一行中输出MinD(a, b, c) = d的结果，请注意其中(a, b, c)是拥有最小距离的triples，并将d作为对应的数值记录下来。如果存在多个解，则输出最大的triples。
Sample Input:
4 4 6
0 9 -1 11
10 -25 11 -10
9 2 41 17 12 30Sample Output:
MinD(11, 11, 12) = 2Hint:
Another solution exists in addition to the primary one. Furthermore, the value of MinD(9, 10, 9) equals exactly 2. Considering that (11, 11, 12) is larger in magnitude compared to it's the larger one and therefore needs to be displayed.
提示：三指针，每次移动指向最小值的指针，直到三个指针都到终点。
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int inf = 1000000000;
vector<int> v1,v2,v3;
int n1,n2,n3;
int getMin(int p1, int p2, int p3)
{
int Min=inf,index=-1;
if(p1!=n1-1){
if(v1[p1]<Min){
Min = v1[p1];
index = 1;
}
}
if(p2!=n2-1){
if(v2[p2]<Min){
Min = v2[p2];
index = 2;
}
}
if(p3!=n3-1){
if(v3[p3]<Min){
Min = v3[p3];
index = 3;
}
}
return index;
}
int main()
{
scanf("%d%d%d",&n1,&n2,&n3);
v1.resize(n1);
v2.resize(n2);
v3.resize(n3);
for(int i=0; i<n1; i++){
scanf("%d",&v1[i]);
}
for(int i=0; i<n2; i++){
scanf("%d",&v2[i]);
}
for(int i=0; i<n3; i++){
scanf("%d",&v3[i]);
}
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
sort(v3.begin(),v3.end());
int p1,p2,p3;
p1=p2=p3=0;
int index;
int MinD=inf,mini,minj,mink,nowD;
while(true){
nowD=abs(v1[p1]-v2[p2])+abs(v2[p2]-v3[p3])+abs(v1[p1]-v3[p3]);
if(nowD<=MinD){
MinD = nowD;
mini = p1;
minj = p2;
mink = p3;
}
index = getMin(p1,p2,p3);
if(index==1) p1++;
else if(index==2) p2++;
else if(index==3)p3++;
else break;
}
printf("MinD(%d, %d, %d) = %d\n",v1[mini],v2[minj],v3[mink],MinD);
return 0;
}7-3
Partial School Ranking
(25分)
In a team-based programming competition, each institution is required to send n participants who will compete individually. The participating teams will be sorted based on their cumulative scores, and your task is to compile a ranking list.
It sounds like an easy challenge, but complicating things is that we are missing critical data on all competing teams! This provides limited data on individual student scores, and these images include groups of students wearing university badges from the same institution. This means we must reconstruct an approximate ranking based on whatever data is available.
Input Specification:
Every input file includes a single test case. For each test case, the first line provides a positive integer N (≤1000). Subsequently, N lines follow one after another in the format:
ID k teammate1⋯teammatek Score
where ID represents a unique 4-digit identification number assigned to each student; k, where k ranges from 0 to 5, indicates the number of teammates this student has in a photo; and the Score represents the percentage achieved by this student in that particular photo, ranging from 0% to 400%.
It is guaranteed that each ID with a Score is given only once.
Output Specification:
For each case, first print in a single line the total number of universities (all students who are directly or indirectly teammates with others are considered part of one university). Subsequently, publish this information in a structured manner.
ID S Scoretotal
where ID represents the lowest student ID among universities; and S denotes the overall count of students. Additionally, Scoretotal refers to the maximum recoverable score for each university. Universities should be ranked starting with those having highest Scoretotal, or ordered by increasing S when there's a tie among Scoretotals, and, if needed, sorted by ascending ID within ties for Scoretotals.
Sample Input:
11
7456 3 7457 7458 7459 157
6666 3 5551 5552 7777 100
1234 3 5678 9012 0002 80
8888 0 340
2468 3 0001 0004 2222 110
7777 1 6666 57
3721 1 2333 30
9012 3 1236 1235 1234 10
1235 2 5678 9012 50
2222 4 1236 2468 6661 6662 16
2333 4 3721 6661 6662 6663 44Sample Output:
4
8888 1 340
0001 15 340
5551 4 157
7456 4 157提示：并查集。
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 10000;
struct node{
int score;
int father;
int total;
node(){
score=0;
father=-1;
total=1;
}
}S[maxn];
struct university{
int head;
int id;
int num;
int score;
university(){
id=100000;
num=0;
score=0;
}
};
void Union(int root1, int root2)
{
if(S[root1].total>S[root2].total){
S[root2].father = root1;
S[root1].total+=S[root2].total;
}
else{
S[root1].father = root2;
S[root2].total+=S[root1].total;
}
}
int myFind(int x)
{
if(S[x].father==-1) return x;
else return S[x].father = myFind(S[x].father);
}
bool cmp(university a,university b)
{
if(a.score!=b.score) return a.score>b.score;
else if(a.num!=b.num) return a.num<b.num;
else return a.id<b.id;
}
int main()
{
set<int> st;
int n,id,k,score,tmate,root1,root2;
scanf("%d",&n);
for(int i=0; i<n; i++){
scanf("%d%d",&id,&k);
st.insert(id);
for(int j=0; j<k; j++){
scanf("%d",&tmate);
st.insert(tmate);
root1 = myFind(id);
root2 = myFind(tmate);
if(root1!=root2){
Union(root1,root2);
}
}
scanf("%d",&score);
S[id].score = score;
}
map<int,university> mp;
int root;
for(auto it=st.begin(); it!=st.end(); it++){
root = myFind(*it);
if(mp.count(root)==0){
mp[root].head=root;
}
if(mp[root].id>*it) mp[root].id=*it;
mp[root].num++;
mp[root].score+=S[*it].score;
}
printf("%d\n",mp.size());
vector<university> ans;
for(auto it=mp.begin();it!=mp.end(); it++){
ans.push_back(it->second);
}
sort(ans.begin(),ans.end(),cmp);
for(int i=0; i<ans.size(); i++){
printf("%04d %d %d\n",ans[i].id,ans[i].num,ans[i].score);
}
return 0;
}7-4
Shopping With Coupons
(30分)
There are N items on your shopping list, and you have N kinds of coupon that can save you some money on buying any of these items. At the mean time, you have D dollars in your pocket. How can you buy as many items as you can? Here you may use any coupon many times and buy any item many times, but only one coupon may be used to get a reduction of payment for one item once -- that is, for example, you may use coupon A1 to buy item B1, and then use coupon A2 to buy item B1. At the mean time, coupon A1 can be used to buy item B2. But you may not use coupon A1 to buy item B1 AGAIN.
Let's imagine a situation involving four items priced at $10,$12,$15,and$20respectively;alongwithfourdiscountcouponsvaluedat$6,$7,$8,and$9.Ifyouhavea totalof$30inyourpossession,theoptimalpurchasingstrategywouldbe...
- Purchase a ten-dollar item four times; each purchase utilizing one coupon exclusively. Thus totaling: (4 × $10) - ($6 + $7 + $8 + $9) = $40 - $30 = $10.
- Purchase a twelve-dollar item three times; each time using specific coupons valued at seven, eight, and nine dollars respectively. Thus totaling: (3 × $12) - (7 + 8 + 9) = $36 - $24 = $12.
- Purchase a fifteen-dollar item using a nine-dollar coupon; thereby reducing the total cost to: ($15 - $9) = $6.
Only $2 remain, which is insufficient to purchase any additional items. I regret to inform you that the maximum number of items you can buy is 8.
Input Specification:
Each input file includes one test case. For each test case, the first line provides two positive integers: N (≤10⁵), representing the number of items and coupons, and D (≤10⁶), denoting the amount of money available to you.
In the second line, N positive prices are provided, alongside N positive coupon values in the third line. It is ensured that the maximum coupon value does not exceed the minimum item price, with all figures capped at 10^9. The numerical values within each line are separated by spaces.
Output Specification:
Output or display on a single line the highest quantity of items attainable and the largest remaining balance, using a single space as the separator.
Sample Input:
4 30
12 20 15 10
9 6 8 7Sample Output:
8 2提示：利用优先级队列。
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 100000;
int A[maxn],B[maxn],record[maxn];
bool cmp(int a, int b)
{
return a>b;
}
struct node{
int product;
int coupon;
friend bool operator < (node a, node b){
return A[a.product]-B[a.coupon]>A[b.product]-B[b.coupon];
}
};
int main()
{
int n,d;
scanf("%d%d",&n,&d);
for(int i=0; i<n; i++){
scanf("%d",&A[i]);
}
for(int i=0; i<n; i++){
scanf("%d",&B[i]);
}
sort(A,A+n);
sort(B,B+n,cmp);
priority_queue<node> q;
node tmp;
for(int i=0; i<n; i++){
tmp.product = i;
tmp.coupon = 0;
q.push(tmp);
}
int total=0,cnt=0;
while(!q.empty()){
tmp=q.top(); q.pop();
cnt++;
total+=(A[tmp.product]-B[tmp.coupon]);
//printf("%d\n",(A[tmp.product]-B[tmp.coupon]));
if(total>d){
total-=(A[tmp.product]-B[tmp.coupon]);
cnt--;
break;
}
if(tmp.coupon<n-1){
tmp.coupon++;
q.push(tmp);
}
}
printf("%d %d\n",cnt,d-total);
return 0;
}