{"id":428,"date":"2013-07-25T13:17:07","date_gmt":"2013-07-25T05:17:07","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=428"},"modified":"2013-07-25T13:17:07","modified_gmt":"2013-07-25T05:17:07","slug":"1009-product-of-polynomials-25","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=428","title":{"rendered":"1009. Product of Polynomials (25)"},"content":{"rendered":"<p>\u65f6\u95f4\u9650\u5236<br \/>\n400 ms<br \/>\n\u5185\u5b58\u9650\u5236<br \/>\n32000 kB<br \/>\n\u4ee3\u7801\u957f\u5ea6\u9650\u5236<br \/>\n16000 B<br \/>\nThis time, you are supposed to find A*B where A and B are two polynomials.<br \/>\n<b>Input Specification:<\/b><br \/>\nEach input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 a<sub>N1<\/sub>\u00a0N2 a<sub>N2<\/sub>\u00a0&#8230; NK a<sub>NK<\/sub>, where K is the number of nonzero terms in the polynomial, Ni and a<sub>Ni<\/sub>\u00a0(i=1, 2, &#8230;, K) are the exponents and coefficients, respectively. It is given that 1 &lt;= K &lt;= 10, 0 &lt;= NK &lt; &#8230; &lt; N2 &lt; N1 &lt;=1000.<br \/>\n&nbsp;<br \/>\n<b>Output Specification:<\/b><br \/>\nFor each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.<br \/>\n<b>Sample Input<\/b><\/p>\n<pre>2 1 2.4 0 3.2\n2 2 1.5 1 0.5<\/pre>\n<p><b>Sample Output<\/b><\/p>\n<pre>3 3 3.6 2 6.0 1 1.6<\/pre>\n<p>=====================================<br \/>\n\u8fd9\u9898\u76ee\u6ca1\u4ec0\u4e48\u96be\u5ea6\u7684\u8bf4\uff0c\u5c31\u662f\u591a\u9879\u5f0f\u4e58\u79ef\u561b~<br \/>\n\u552f\u4e00\u8981\u6ce8\u610f\u7684\u4e8b\u60c5\u662f\uff0c\u7ed3\u679c\u7684\u8f93\u51fa\u65f6\u6309\u7167\u6307\u6570\u9012\u51cf\u7684&#8230;\u8fd9\u91cc\u7528\u4e86map\u91cc\u9762\u7684reverse_iterator\uff0c\u771f\u5fc3\u662f\u597d\u7528\uff01<br \/>\n\u53e6\u5916\uff0c\u4e5f\u4e0d\u77e5\u9053\u7cfb\u6570\u6709\u6ca1\u6709\u8d1f\u6570\uff0c\u6240\u4ee5\u5904\u7406\u7684\u65f6\u5019\u8003\u8651\u4e86\u4e00\u4e0b\u76f8\u52a0\u4e3a0\u7684\u60c5\u51b5&#8230;\u8c8c\u4f3c\u6ca1\u5565\u5fc5\u8981\u54e6&#8230;<br \/>\n\u603b\u4e4b\u662f\u5f88\u7b80\u5355\u7684\u4e1c\u897f~\u524d\u63d0\u662f\u6709STL\u8fd9\u8d27&#8230;<br \/>\n=====================================<\/p>\n<pre>\n#include <stdio.h>\n#include <map>\nusing namespace std;\n#define MapIterator map<int,float>::iterator\n#define MapIteratorReverse map<int,float>::reverse_iterator\nint main()\n{\n    int K;\n    scanf(\"%d\", &K);\n    map<int,float> polyA; \/\/\u7b2c\u4e00\u884c\n    for(int i=0; i<k; i++)\n    {\n        int Ni; float Ki;\n        scanf(\"%d %f\", &#038;Ni, &#038;Ki);\n        pair<int, float> p(Ni, Ki);\n        polyA.insert(p);\n    }\n    scanf(\"%d\", &K);\n    map<int,float> result; \/\/\u7ed3\u679c\n    for(int i=0; i<k; i++)\n    {\n        \/\/\u8bfb\u53d6\u7b2c\u4e8c\u884c\u7684\u6570\u636e\n        int Ni; float Ki;\n        scanf(\"%d %f\", &#038;Ni, &#038;Ki);\n        MapIterator it;\n        for(it = polyA.begin(); it != polyA.end(); it++)\n        {\n            int Nj = it->first + Ni;  \/\/\u4e58\u65b9\n            float Kj = it->second * Ki;\/\/\u7cfb\u6570\n            if(result.count(Nj) > 0)\n            {\n                \/\/\u539f\u6765\u6709\u7ed3\u679c\n                float sum = Kj + result[Nj];\n                if(sum == 0)\n                    \/\/\u8fd9\u9879\u6ca1\u4e86...\n                    result.erase(Nj);\n                else\n                    result[Nj] = sum;\n            }\n            else\n            {\n                result.insert(pair<int,float>(Nj, Kj));\n            }\n        }\n    }\n    printf(\"%d\", result.size());\n    MapIteratorReverse it;\n    for(it = result.rbegin(); it != result.rend(); it++)\n    {\n        printf(\" %d %.1f\", it->first, it->second);\n    }\n    return 0;\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u65f6\u95f4\u9650\u5236 400 ms \u5185\u5b58\u9650\u5236 32000 kB \u4ee3\u7801\u957f\u5ea6\u9650\u5236 16000 B This time, you are supposed to find A*B where A and B are two polynomials. Input Specification: Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1\u00a0N2 aN2\u00a0&#8230; NK aNK, where K [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[84],"class_list":["post-428","post","type-post","status-publish","format-standard","hentry","category-study","tag-pat"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/428","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=428"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/428\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=428"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=428"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=428"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}