15211088-王意如-算法第一次上机解题报告.docxVIP

A?多项式计算器解题思路：本题考查秦九韶算法，由于x的次数是递增的，因此只要将x的值每次乘一次，累乘即可，千万不要每次都直接算x的n次方，会超时的。另外就是要每乘一次x取一次模以防答案溢出导致WA。代码：#include iostreamusingnamespacestd;int main(int argc, constchar * argv[]) {longlong n;int count=1; //计数器，输出使用while (cinn) {coutCase #count++:\n;longlong a[n+1];longlong x,t;cinxt;for (int i=0; it; i++) { //x的次数循环递增longlong sum=0;longlong w=1;cina[0]; sum+=a[0];for (int j=1; jn+1; j++) {cina[j]; //输入系数 w=w*x%1000007; //秦九韶算法 sum += a[j]*w; sum%=1000007; }coutsumendl; } }return0;}B 怠惰的园丁王木木解题思路：由题目可知，对于同一种高度的不同的草，可以看作是同一根。因此减少长度唯一的草的数量即可。先将后根草除去的长度，完成后它们的长度分别与前根草的长度相等。通过一个步骤将n根草变成了根草。不断重复直到只剩一根草即可。为了防治超时，先将所有情况（给定数据范围内）算出来，存到一个数组中，查询输出即可。代码：#include iostreamusingnamespacestd;int a[1000005]; //查询数组int main(){memset(a,0,sizeof(a));a[1]=1;for(int i=2;i1000005;i++) //循环算出所有情况 {a[i]=1+a[i/2]; }int n;while(scanf(%d,n)==1) //输入查询printf(%d\n,a[n]);}C jhljx学位运算解题思路：根据题目提示中异或的性质，代码：#include iostreamusing namespace std;const int MaxN = 1000000 + 7;int n, k, l, r;int nums[MaxN], prefix[MaxN];int main() {while (cin n) { prefix[0] = 0;for (int i = 1; i = n; i++) { cin nums[i]; prefix[i] = prefix[i - 1] ^ nums[i]; //前缀和数组 } cin k;while (k--) { cin l r;if (l r) swap(l, r);//需要特别注意 cout (prefix[r] ^ prefix[l - 1]) \n; } }}D 股票交易解题思路：题意即为求出满足的的最大值。先读入所有元素，然后进行线性遍历。遍历到第i个元素时，记录下之前所有元素的最小值，与当前元素作对比，一方面维护最小值，另一方面更新差值即可。代码：#include iostreamusing namespace std;const int MaxN = 1000000 + 7;int n, det, num, Min;int main() {while (cin n) { det = -1; Min = MaxN;//最小值while (n--) { cin num;if (num = Min) Min = num;//维护最小值elsedet = max(det, num - Min);//更新差值 }if (det 0) cout No solution\n;else cout det \n; }}E?模式寻对解题思路：求逆序对个数，按理说复杂度为O(tnlogn)的代码很可能会超时，但是似乎没有复杂度更低的办法了，于是就这么做了，居然没有超时。做法类似归并排序，求区间[l,r]中的逆序对个数，可以利用辅助空间先递归求出[l,mid)和[mid,r