可解的算法太多了，采用的算法是试x的值。注意题目的输入x^3-2x^2不会写成x^3+-2x^2。一直RE在这儿。
1 /* 4516 */ 2 #include <iostream> 3 #include <string> 4 #include <map> 5 #include <queue> 6 #include <set> 7 #include <stack> 8 #include <vector> 9 #include <deque> 10 #include <algorithm> 11 #include <cstdio> 12 #include <cmath> 13 #include <ctime> 14 #include <cstring> 15 #include <climits> 16 #include <cctype> 17 #include <cassert> 18 #include <functional> 19 #include <iterator> 20 #include <iomanip> 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set<int> 25 #define stpii set<pair<int, int> > 26 #define mpii map<int,int> 27 #define vi vector<int> 28 #define pii pair<int,int> 29 #define vpii vector<pair<int,int> > 30 #define rep(i, a, n) for (int i=a;i<n;++i) 31 #define per(i, a, n) for (int i=n-1;i>=a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 #define LL long long 42 43 const int maxl = 505; 44 const int maxn = 10; 45 char s[maxl], ss[maxl]; 46 int A[40][maxn], B[maxn], B_[maxn]; 47 int c[maxn], cn; 48 49 bool check() { 50 memset(B, 0, sizeof(B)); 51 B[1] = 1; 52 B[0] = c[0]; 53 54 rep(i, 1, cn) { 55 memset(B_, 0, sizeof(B_)); 56 rep(j, 1, maxn) 57 B_[j] += B[j-1]; 58 rep(j, 0, maxn) 59 B_[j] += B[j] * c[i]; 60 memcpy(B, B_, sizeof(B)); 61 } 62 63 rep(i, 0, maxn) { 64 if (A[0][i] != B[i]) 65 return false; 66 } 67 68 return true; 69 } 70 71 bool judge(int p, int i, int x) { 72 LL ret = 0, base = 1; 73 74 for (int j=0; j<=i; ++j) { 75 ret += A[p][j] * base; 76 base *= x; 77 } 78 79 return ret == 0; 80 } 81 82 void reduce(int p, int i, int x) { 83 int q = p + 1; 84 85 memcpy(B, A[p], sizeof(B)); 86 for (int j=i; j>0; --j) { 87 A[q][j-1] = B[j]; 88 B[j-1] -= B[j] * x; 89 } 90 } 91 92 bool solve() { 93 // init parameter 94 int i = 0, a = 0, p = 0, q; 95 int cnt = 0; 96 bool neg = false, flag = false; 97 98 memset(A, 0, sizeof(A)); 99 cn = 0; 100 101 while (1) { 102 if (s[i]=='+' || s[i]==' ') { 103 if (neg) 104 a = -a; 105 if (flag && p==0) 106 p = 1; 107 A[0][p] += a; 108 neg = false; 109 flag = false; 110 p = 0; 111 a = 0; 112 cnt = 0; 113 } else if (s[i] == '-') { 114 neg = true; 115 } else if (s[i] == 'x') { 116 if (cnt == 0) 117 a = 1; 118 flag = true; 119 } else if (s[i] == '^') { 120 ; 121 } else { 122 if (flag) 123 p = p*10+s[i]-'0'; 124 else 125 a = a*10+s[i]-'0'; 126 ++cnt; 127 } 128 if (s[i] == ' ') 129 break; 130 ++i; 131 } 132 133 p = 0, q = 1; 134 int x, xx; 135 136 while (1) { 137 for (i=5; i>=0; --i) { 138 if (A[p][i] != 0) 139 break; 140 } 141 if (i < 0) 142 break; 143 if (A[p][i] != 1) 144 return false; 145 if (i == 0) 146 break; 147 148 a = A[p][0]; 149 if (a == 0) { 150 c[cn] = 0; 151 while (i > 0) { 152 A[q][i-1] = A[p][i]; 153 --i; 154 } 155 flag = true; 156 } else if (a > 0) { 157 flag = false; 158 for (x=1; x*x<=a; ++x) { 159 if (a%x == 0) { 160 if (judge(p, i, -x)) { 161 reduce(p, i, x); 162 flag = true; 163 c[cn] = x; 164 break; 165 } else if (judge(p, i, x)) { 166 reduce(p, i, -x); 167 flag = true; 168 c[cn] = -x; 169 break; 170 } 171 xx = a/x; 172 if (xx != x) { 173 if (judge(p, i, -xx)) { 174 reduce(p, i, xx); 175 flag = true; 176 c[cn] = xx; 177 break; 178 } else if (judge(p, i, xx)) { 179 reduce(p, i, -xx); 180 flag = true; 181 c[cn] = -xx; 182 break; 183 } 184 } 185 } 186 } 187 } else { 188 flag = false; 189 a = -a; 190 for (x=1; x*x<=a; ++x) { 191 if (a%x == 0) { 192 if (judge(p, i, x)) { 193 reduce(p, i, -x); 194 c[cn] = -x; 195 flag = true; 196 break; 197 } else if (judge(p, i, -x)) { 198 reduce(p, i, x); 199 c[cn] = x; 200 flag = true; 201 break; 202 } 203 xx = a/x; 204 if (xx != x) { 205 if (judge(p, i, xx)) { 206 reduce(p, i, -xx); 207 flag = true; 208 c[cn] = -xx; 209 break; 210 } else if (judge(p, i, -xx)) { 211 reduce(p, i, xx); 212 flag = true; 213 c[cn] = xx; 214 break; 215 } 216 } 217 } 218 } 219 } 220 221 if (!flag) 222 return false; 223 224 ++cn; 225 ++p; 226 ++q; 227 } 228 229 return cn>0; 230 } 231 232 void change() { 233 int l = 0; 234 int i = 0; 235 int len = strlen(s); 236 237 while (i < len) { 238 if (s[i] == '-') { 239 if (i && s[i-1]!='+') 240 ss[l++] = '+'; 241 } 242 ss[l++] = s[i++]; 243 } 244 245 ss[l] = ' '; 246 strcpy(s, ss); 247 } 248 249 int main() { 250 ios::sync_with_stdio(false); 251 #ifndef ONLINE_JUDGE 252 freopen("data.in", "r", stdin); 253 freopen("data.out", "w", stdout); 254 #endif 255 256 int t; 257 bool flag; 258 259 scanf("%d", &t); 260 rep(tt, 1, t+1) { 261 scanf("%s", s); 262 change(); 263 flag = solve(); 264 printf("Case #%d: ", tt); 265 if (flag) { 266 sort(c, c+cn); 267 rep(i, 0, cn) { 268 if (c[i] == 0) 269 printf("x"); 270 else if (c[i] > 0) 271 printf("(x+%d)", c[i]); 272 else 273 printf("(x-%d)", -c[i]); 274 } 275 putchar(' '); 276 #ifndef ONLINE_JUDGE 277 if (!check()) 278 puts("wrong"); 279 #endif 280 } else { 281 puts("-1"); 282 } 283 } 284 285 #ifndef ONLINE_JUDGE 286 printf("time = %d. ", (int)clock()); 287 #endif 288 289 return 0; 290 }
测试数据和答案。
1 from random import randint 2 import shutil 3 4 def GenEle(k): 5 if k == 0: 6 return "x" 7 elif k>0: 8 return "(x+%d)" % (k) 9 else: 10 return "(x-%d)" % (-k) 11 12 13 def GenLine(): 14 src, ans = "", "" 15 k = randint(1, 5) 16 L = [] 17 for i in xrange(k): 18 x = randint(-10, 10) 19 L.append(x) 20 L = sorted(L) 21 ans = "".join(map(GenEle, L)) 22 a = [0 for i in xrange(6)] 23 a[1] = 1 24 a[0] = L[0] 25 for i in xrange(1, k): 26 b = [0 for j in xrange(6)] 27 for j in xrange(1, 6): 28 b[j] += a[j-1] 29 for j in xrange(0, 6): 30 b[j] += a[j] * L[i] 31 a = b 32 i = 5 33 while i>=0: 34 if a[i]>0: 35 break 36 i -= 1 37 srcList = [] 38 while i>=0: 39 line = "" 40 if a[i] < 0: 41 line += "-" 42 a[i] = -a[i] 43 if i==0 or a[i]!=1: 44 line += str(a[i]) 45 if i==1: 46 line += "x" 47 elif i>1: 48 line += "x^%d" % i 49 i -= 1 50 srcList.append(line) 51 src = "+".join(srcList) 52 return src, ans 53 54 55 def GenDataIn(): 56 bound = 10**2 57 ansList = [] 58 with open("data.in", "w") as fout: 59 t = 50 60 fout.write("%d " % (t)) 61 for tt in xrange(t): 62 line, ans = GenLine() 63 fout.write(line + " ") 64 ansList.append(ans) 65 with open("F:code_todaydata.in", "w") as fout: 66 for i,ans in enumerate(ansList): 67 line = "Case #%d: %s " % (i+1, ans) 68 fout.write(line) 69 70 71 def MovDataIn(): 72 desFileName = "F:workspacecpp_hdojdata.in" 73 shutil.copyfile("data.in", desFileName) 74 75 if __name__ == "__main__": 76 GenDataIn() 77 MovDataIn() 78 79