7-1 Standard Form of Polynomial (20 分)
The standard form of a polynomial of degree n is P(x)=anxn+an−1xn−1+⋯+a1x+a0. Given that an=1 and all the n roots { r1, …, rn } of P(x) are integers. Then P(x) can be written as (x−r1)(x−r2)⋯(x−rn). Your job is to write P(x) in its standard form with all roots given.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive n (≤10) which is the degree of P(x). Then n integer roots are given in the next line, separated by spaces.
Output Specification:
For each case, output the coefficients ai (i=n−1,⋯,0) in a line. All the numbers must be separated by one space, and there must be no extra space at the beginning or the end of the line. It is guaranteed that all the calculation will be within the range of int.
Sample Input:
3
-1 4 -1
Sample Output:
-2 -7 -4
代码如下：
#include <iostream>
using namespace std;
int main()
{
int n;
int root[15], temp[15], result[15];
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> root[i];
root[i] = -root[i];
}
result[1] = 1; // 第一个因式存入
result[0] = root[0];
for (int i = 1; i < n; i++) // n个多项式需要乘n-1次，i指明了当前最高次数
{
for (int j = 0; j <= i; j++) // 将前面i个多项式乘积结果保存
temp[j] = result[j];
for (int j = i + 1; j > 0; j--) // 先乘x项
result[j] = result[j - 1];
result[0] = 0;
for (int j = 0; j <= i; j++) // 再乘常数项
result[j] += root[i] * temp[j];
}
for (int i = n - 1; i >= 0; i--)
{
cout << result[i];
if (i != 0)
cout << " ";
}
return 0;
}
别人的DFS实现：
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> root(15), result(15, 0);
void dfs(int pol, int val, int coe) // pol代表多项式个数，val代表值，coe代表次数，
{
if (pol == n) // n个多项式相乘完毕
result[coe] += val;
else
{
dfs(pol + 1, val * root[pol], coe); // 乘以常数项
dfs(pol + 1, val, coe + 1); // 乘以x
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> root[i];
root[i] = -root[i];
}
dfs(0, 1, 0);
for (int i = n - 1; i >= 0; i--)
{
cout << result[i];
if (i != 0)
cout << " ";
}
return 0;
}
7-2 Distance of Triples (25 分)
The distance of triples (三元组) (a,b,c) is defined as D(a,b,c)=∣a−b∣+∣b−c∣+∣c−a∣. Now given three non-empty integer sets S1, S2 and S3, you are supposed to find the minimum distance of all the possible triples (a,b,c) where a∈S1, b∈S2 and c∈S3 .
Input Specification:
Each input file contains one test case. For each case, the first line gives three positive integers N1, N2 and N3 (all no more than 104), which are the sizes of S1, S2 and S3, respectively. Then the members of the three sets are given in the following three lines, respectively. All the numbers are integers in the range [−104,104], and they are distinct within each set. The numbers in a line are separated by spaces.
Output Specification:
For each case, print in a line MinD(a, b, c) = d, where (a, b, c) are the triples that has the minimum distance, and d is the corresponding distance. If the solution is not unique, output the largest triples.
Sample Input:
4 4 6
0 9 -1 11
10 -25 11 -10
9 2 41 17 12 30
Sample Output:
MinD(11, 11, 12) = 2
Hint:
Notice that there are two solutions. The other one is MinD(9, 10, 9) = 2. Since (11, 11, 12) is larger, this one must be printed out.
代码如下（408代码19分）：
这题用408写只能拿19分，因为408那个是一个序列遍历完就结束了，但是这个要求最大三元组，所以必须把所有序列遍历完，时间复杂度应该为O(S1+S2+S3)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int i = 0, j = 0, k = 0, n1, n2, n3, dist = 0x3f3f3f3f;
int main()
{
int A, B, C;
cin >> n1 >> n2 >> n3;
vector<int> s1(n1), s2(n2), s3(n3);
for (int s = 0; s < n1; s++)
cin >> s1[s];
for (int s = 0; s < n2; s++)
cin >> s2[s];
for (int s = 0; s < n3; s++)
cin >> s3[s];
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
sort(s3.begin(), s3.end());
while (i < n1 && j < n2 && k < n3)
{
int a = s1[i], b = s2[j], c = s3[k];
int temp = abs(a - b) + abs(a - c) + abs(b - c);
if (temp <= dist) // 要求输出最大的三元组，因此这里需要加上等号，因为越往后遍历肯定是越大的
{
dist = temp;
A = a, B = b, C = c;
}
if (a <= b && a <= c && i != n1)
i++;
else if (b <= a && b <= c && j != n2)
j++;
else if (c <= a && c <= b && k != n3)
k++;
}
printf("MinD(%d, %d, %d) = %d\n", A, B, C, dist);
return 0;
}
AC代码25分：
这个代码能AC不过感觉有些冗余了，这里提供另外一个思路：可以从大往小遍历，也就是从后往前，这样应该60行之内就能解决了
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int i = 0, j = 0, k = 0, n1, n2, n3, dist = 0x3f3f3f3f;
int main()
{
int A, B, C;
cin >> n1 >> n2 >> n3;
vector<int> s1(n1), s2(n2), s3(n3);
for (int s = 0; s < n1; s++)
cin >> s1[s];
for (int s = 0; s < n2; s++)
cin >> s2[s];
for (int s = 0; s < n3; s++)
cin >> s3[s];
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
sort(s3.begin(), s3.end());
while (i < n1 && j < n2 && k < n3)
{
int a = s1[i], b = s2[j], c = s3[k];
int temp = abs(a - b) + abs(a - c) + abs(b - c);
if (temp <= dist) // 要求输出最大的三元组，因此这里需要加上等号，因为越往后遍历肯定是越大的
{
dist = temp;
A = a, B = b, C = c;
}
if (a <= b && a <= c) // 没办法，它要最大三元组，所以应当所有序列全部遍历完，而不是一个遍历完就算了
{
if (i != n1 - 1)
i++;
else
{
if (b <= c)
{
if (j != n2 - 1)
j++;
else
k++;
}
else if (c <= b)
{
if (k != n3 - 1)
k++;
else
j++;
}
}
}
else if (b <= a && b <= c)
{
if (j != n2 - 1)
j++;
else
{
if (a <= c)
{
if (i != n1 - 1)
i++;
else
k++;
}
else if (c <= a)
{
if (k != n3 - 1)
k++;
else
i++;
}
}
}
else if (c <= a && c <= b)
{
if (k != n3 - 1)
k++;
else
{
if (a <= b)
{
if (i != n1 - 1)
i++;
else
j++;
}
else if (b <= a)
{
if (j != n2 - 1)
j++;
else
i++;
}
}
}
}
printf("MinD(%d, %d, %d) = %d\n", A, B, C, dist);
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.
For example, suppose there are 4 items with prices of 10,12, 15 and 20; and 4 kinds of coupons with values of 6,7, 8 and 9. If you have $30 in your pocket, the best way to buy is the following:
buy 10 item for 4 times, with each coupon once, and hence pay 10 x 4 − 6 − 7 − 8 − 9 = $10 in total;
buy 12 item for 3 times, with coupons of 7, 8 and 9, and hence pay 12 x 3 − 7 − 8 − 9 = $12 in total;
buy 15 item with 9 coupon, and hence pay $6;
Now you have $2 left, not enough to buy any more items. Therefore the maximum number of items you can buy is 8.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers: N (≤105), the number of items (and the coupons), and D (≤106), the amount of money you have.
Then N positive prices are given in the second line, and N positive coupon values are given in the third line. It is guaranteed that the highest value of coupons is less than the lowest price of items, and all the numbers are bounded above by 109. The numbers in a line are separated by spaces.
Output Specification:
Print in a line the maximum number of items you can buy, and the maximum amount of money left, separated by 1 space.
Sample Input:
4 30
12 20 15 10
9 6 8 7
Sample Output:
8 2
其实就是贪心策略，每次都买可以花最少钱的物品，不过这题贪心的实现并不那么简单，需要采用优先队列来实现，不用优先队列也行，不过会麻烦不少
代码如下：
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 100005;
int n, d, cnt = 0;
int prices[MAXN], coupons[MAXN];
struct node
{
int i, j;
friend bool operator<(node n1, node n2)
{
return prices[n1.i] - coupons[n1.j] > prices[n2.i] - coupons[n2.j]; // 队头最小
}
};
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
cin >> n >> d;
for (int i = 0; i < n; i++)
cin >> prices[i];
for (int i = 0; i < n; i++)
cin >> coupons[i];
sort(prices, prices + n); // 价格从小到大排序
sort(coupons, coupons + n, cmp); // 优惠券从大到小排序
priority_queue<node> q;
for (int i = 0; i < n; i++)
q.push({i, 0});
while (d > 0 && !q.empty())
{
node temp = q.top();
q.pop();
int cost = prices[temp.i] - coupons[temp.j];
if (d >= cost) // 少写了个等号调试了好久
{
d -= cost;
cnt++;
if (temp.j != n - 1) // 对于该商品已经没有优惠券可以用了
{
temp.j++;
q.push(temp);
}
}
else
break; // 已经买不起了，后面的优惠券面值更小更买不起
}
cout << cnt << " " << d << endl;
return 0;
}
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
