多校联合训练 – hahaschool

HDU5396 / 15多校9-1 Expression

August 20, 20152015-08-20hahaschoolLeave a comment

题意

给出了一个算术表达式，表达式里面只会含有加减乘三种运算。我们每一次从中选取两个数字并执行这两个数字对应的运算，运算结果放回式子中继续进行运算，直到最后只剩下了一个数。让我们求的是每一种不同的选取方式所得到的结果的和。

注意

这个题没有做好的主要原因是没有领会到题目中关于不同的选取方式的定义，注意到题目中讲到只要有一轮选取的数字不一样，就视为不同。这句话的含义中有两个信息：一是允许重复，二是要分先后。

思路

最开始确实是没什么思路的，后来看了看board发现并不是特别难的题。于是尝试拆解问题，我们可以从算数式的一小段入手，以sample的1 + 4 * 6 – 8 * 3为例。

只考虑1 + 4部分，只有一种配置方法，就是(1 + 4);
考虑1 + 4 * 6部分，我们发现这一部分可以看成两种情况：1 + (4 * 6)和(1 + 4) * 6，在这里面我们已经考虑了1 + 4区段，而4 * 6区段只有一种配置。这样1 + 4 * 6这个区段就有两种配置了。
接下来考虑1 + 4 * 6 – 8区段，要想得到这个区段的全部情况，我们应该考虑：
1 + (4 * 6 – 8),1 + 4 * (6 – 8),(1 + 4) * 6 – 8,(1 + 4 * 6) – 8这些情况，其中(4 * 6 – 8)又可以看成考虑(4 * 6) – 8,4 * (6 – 8)这两种情况，而(1 + 4 * 6)的对应情况我们先前已经算好了。
最后，考虑1 + 4 * 6 – 8 * 3，顺着上面的思路来，就可以拆分成：
1 + (4 * 6 – 8 * 3),1 + 4 * (6 – 8 * 3),(1 + 4) * 6 – (8 * 3),(1 + 4 * 6) – 8 * 3,(1 + 4 * 6 – 8) * 3，接下来再去拆分这五种情况中的子情况。。。

如果比较敏感的话应该已经发现这就是典型的区间dp了，在推方程的时候，我们是将所有子情况的答案累加，得到当前情况的答案，但这还不够，还要注意每种情况，因为选择顺序的关系，会有多重副本，而这个副本的数量其实蛮好求，就是阶乘，而还要注意，我们在讨论当前情况的时候，是将整个等待处理的算式区段分成了（左区段）算子（分界点）算子（右区段）这样看待的，那么先后的问题又来了，我们不光左右区段的答案自身要乘上阶乘，最后整个结果还要乘上一个组合数，因为左右区段的操作又是分先后的。

以下引自官方题解，注意第2段第2行的dp[l][r]实际上是dp[l][k]。

代码

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <cmath>

using namespace std;

#define MODER 1000000007
#define MAXN 105
long long seq[MAXN];
long long fac[MAXN];
long long C[MAXN][MAXN];
string op;
int n = 0;

long long dp[MAXN][MAXN];

long long calc(char _op,long long a,long long b){
    if (_op == '+') {
        return a+b;
    }
    if (_op == '-') {
        return a-b;
    }
    if (_op == '*') {
        return a*b;
    }
    return 0;
}

void solve(){
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        dp[i][i] = seq[i];
    }
    for (int j = 1; j <= n; j++) {
        for (int i = j - 1; i >= 1; i--) {
            for (int k = i; k < j; k++) {
                if (op[k-1] == '*') {
                    dp[i][j] += calc(op[k-1], dp[i][k], dp[k+1][j])*(C[j-i-1][k-i]%MODER);
                    dp[i][j] %= MODER;
                }else{
                    dp[i][j] += calc(op[k-1], dp[i][k]*fac[j-k-1], dp[k+1][j]*fac[k-i])*(C[j-i-1][k-i]%MODER);
                    dp[i][j] %= MODER;
                }
                dp[i][j] %= MODER;
            }
        }
    }
    cout << (dp[1][n]+MODER)%MODER << endl;
}

int main(){
    fac[0] = 1;
    fac[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        fac[i] = fac[i-1] * i;
        fac[i] %= MODER;
    }
    for (int i = 0; i < MAXN; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j])%MODER;
        }
    }
    while (scanf(" %d",&n) != EOF) {
        for (int i = 1; i <= n; i++) {
            scanf(" %lld",&seq[i]);
        }
        cin >> op;
        solve();
    }
    return 0;
}

#include <iostream>

#include <iomanip>

#include <algorithm>

#include <queue>

#include <vector>

#include <set>

#include <stack>

#include <map>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <cmath>

using namespace std;

#define MODER 1000000007

#define MAXN 105

long long seq[MAXN];

long long fac[MAXN];

long long C[MAXN][MAXN];

string op;

int n = 0;

long long dp[MAXN][MAXN];

long long calc(char _op,long long a,long long b){

if (_op == '+') {

return a+b;

}

if (_op == '-') {

return a-b;

}

if (_op == '*') {

return a*b;

}

return 0;

}

void solve(){

memset(dp, 0, sizeof(dp));

for (int i = 1; i <= n; i++) {

dp[i][i] = seq[i];

}

for (int j = 1; j <= n; j++) {

for (int i = j - 1; i >= 1; i--) {

for (int k = i; k < j; k++) {

if (op[k-1] == '*') {

dp[i][j] += calc(op[k-1], dp[i][k], dp[k+1][j])*(C[j-i-1][k-i]%MODER);

dp[i][j] %= MODER;

}else{

dp[i][j] += calc(op[k-1], dp[i][k]*fac[j-k-1], dp[k+1][j]*fac[k-i])*(C[j-i-1][k-i]%MODER);

dp[i][j] %= MODER;

}

dp[i][j] %= MODER;

}

cout << (dp[1][n]+MODER)%MODER << endl;

}

int main(){

fac[0] = 1;

fac[1] = 1;

for (int i = 2; i < MAXN; i++) {

fac[i] = fac[i-1] * i;

fac[i] %= MODER;

}

for (int i = 0; i < MAXN; i++) {

C[i][0] = C[i][i] = 1;

for (int j = 1; j < i; j++) {

C[i][j] = (C[i-1][j-1] + C[i-1][j])%MODER;

}

while (scanf(" %d",&n) != EOF) {

for (int i = 1; i <= n; i++) {

scanf(" %lld",&seq[i]);

}

cin >> op;

solve();

}

return 0;

}

测试数据

97
42002488 796642576 700424534 492928793 184907764 938887713 107181410 792482963 116518857 549637047 48511747 856433446 590402464 673573447 69495247 203714018 787925377 850112031 375048938 271938638 802494129 158813597 264970784 798528530 490197704 767196026 415353101 689929144 369487202 500663908 925646045 947272745 114170350 422275395 246584468 426418550 579611856 152254016 594726322 728563727 288775478 565138043 680902891 876305510 191112081 452293970 492433812 225768745 679619541 994547367 982603691 15296092 603978680 788518145 465189078 210083862 284880628 329589000 399155372 591915435 797863137 618608585 376324991 227860486 120496725 572177678 329264566 227752653 18519150 658879074 140948055 480823355 695634904 724306259 441449688 256897368 85177480 128320040 41023787 381309904 286849451 367291277 211136278 290206582 349174511 816810643 807052002 541046992 896355733 423997911 637059027 125956299 890644270 192297197 195369584 799285045 466378517
*-+*-**-**+++*-+***+-+*---*--*-**--+*+-+-+*--*+-+*--*-+-+++-+--*-+-*-*++-*-**--+++*--*---++-*++*
100
325956497 703488203 24659275 111168319 30696633 867177774 567622896 185486419 730598881 883230119 563712961 180803964 584941667 42152595 815189025 948445222 884302629 466122431 388540473 372338423 752635513 450641548 639363964 357672619 825047257 242786661 924828610 870704848 270082303 123836441 184865109 256936904 141852852 53253274 127451487 980520417 371387947 159139226 594030471 989127423 368227302 520002431 426259211 996010421 453683913 296897751 30787432 117956896 228079495 691620926 472262826 67500912 817492577 585593640 200764240 553661751 385019596 415018760 607221075 359597740 879829661 611875418 72124927 645005443 360828306 807614336 631355051 144405553 577602237 307688494 780098694 145617805 554856951 119871777 577700931 735031691 442941868 914165376 161547196 986694552 589094296 393092926 299298515 27791972 528267970 281143872 40947478 656044098 203648506 270007357 395952343 102357150 867735114 759911266 233005045 225629783 216508671 965812522 867627947 54865288
+*+--*-*--+-+-+-**++**-*-*-+++*----*+-+-*-+--*-*++***--+--+--++*-*-+--+++--*--+**+**+-++++-++-+-+-*
90
956166081 237081354 516719910 457360421 651030602 297934201 515637975 519190273 54461470 788822420 279420737 34945495 176179851 783472901 692713303 659271374 203828810 406894617 768216502 461887911 221519925 409786328 934329140 306306033 329222655 272749566 919794473 709469627 302842176 528461835 946937241 537809932 810411833 899731345 234778231 117393561 254762040 126366265 546045205 14512569 569130426 607567456 203472523 734412701 828351711 918290891 334578733 149890177 382043196 169168053 245184636 511942620 100149911 315905467 115836107 692482046 906064513 661013850 824221946 293670720 80472372 90846392 220956727 408720330 754118436 945210308 859229672 853979780 968731675 852433305 908692551 199233651 11771210 317467451 856084951 49265992 825336724 452902485 164913224 679351928 304042220 847674906 821118447 182594926 694723853 291245530 803251413 540653332 592046149 142109566
++*---+*+**-++++***+*+-+*---+-+***--+-*-+++*+--*-*--**+***+--**-+-+-++*****------*+-++**-
98
465893828 289478394 637733884 308885867 438351788 735511445 307686150 260496183 824225502 905288458 256046492 786615060 148277488 673436291 27093667 401773414 1160361 980127483 369236180 639808765 442848666 282140241 285019731 91637988 737317728 162662493 733270777 918021327 953687807 211142407 579529297 24704404 541921193 680289260 117728749 103507124 79572674 561536575 15361202 98943187 967924857 691391009 194221889 323326354 951458576 315726744 858945948 955751157 648400730 61497384 961311423 784338729 294243201 890869562 522348152 691037449 323402334 682597630 973909177 717395005 95548247 21273692 917317409 131467669 249482841 728306708 443179802 60669811 107016161 656988680 561007944 172140657 89706235 52256148 475262929 286585935 470901312 299761485 692845276 902285286 173616886 630407007 687350996 982195399 356786913 761716439 746065586 615855955 988179377 213166205 714725937 33387759 271839281 110967052 14364116 148251161 502652519 90843729
-+-++-*+-+-++*---*+*+-**+**--*-+-*-*-+**+****+-+--*-*---++-*-**+-*+*+*****+--*-*-*++++**-*+*----+
90
350460548 683529871 618335624 301938708 443122496 740210529 608748989 773860075 674745679 22051422 3363717 987211125 7455042 150942802 582997451 291451956 853047743 431725539 36063965 916459186 38819334 344832685 905333497 1107506 975568033 430522271 161030190 197567954 895976561 296526280 570825600 567895344 214279060 533392121 265331207 871875814 43745873 576354855 463692349 974512750 403562709 549167732 828509064 696570071 722237507 802639046 991590202 959577397 340576026 62211977 989146740 14037103 635490010 76262658 676592780 771209273 144694401 589889441 374019705 794324052 631865159 951489016 543939718 848804382 598908343 454624051 191117102 551826494 15211257 347769268 242088328 821837708 735776787 734680412 604336524 27170997 995319171 131982742 84150036 813106575 43808331 416344584 422178259 871443637 216387827 398825027 345823744 111101361 155871499 780534153
**-*-++-*-**-*-+**++*-*-+--++-*-+*+-**+*+*-+--+-****++++--+--***-***+--*-*-**-+*+**+--*++
91
369083073 419494718 203958830 132372075 390802926 108536958 359364853 19500017 269482466 116851881 344733006 179976765 665095536 360566894 927223606 19745537 491617131 255871431 124073757 831691852 936168299 628337639 858503621 108450073 907654947 372031410 911623368 876473964 201368080 876278835 741544686 308383962 105473714 378332068 996785400 271362759 704071329 849695712 653933557 203390911 361151674 38280361 955354553 522170431 280173923 910896686 363582043 455411786 666760984 961246757 160430953 687453873 722283066 498568491 361164110 310314399 980345471 155440227 622193202 125958147 10507896 741345861 389880790 480072833 776884410 323432536 97991633 567659920 127960073 533577083 783345366 151218843 982868351 60821489 482093522 436596314 984998445 444073626 446463882 520127981 851250321 237935771 36254845 181834749 1892735 590141893 44183356 907397065 651309846 304020843 692801648
+--++--+-***+-*****-*+**-*-+-+-*-+---+-++**---*+*+++--*--+****-++-+*++*-+**--**---+*+++*-+
95
485961444 707318302 57064654 176495871 981660811 806591453 749245216 252359665 640407166 201588566 229199175 22221498 253223551 89060045 36553720 599810065 690462711 312436980 238112789 353747414 1235787 421192028 507582469 881355702 715088908 889803479 427807294 715763499 180319586 856082545 252088586 371033343 805019366 508584217 969333119 98454585 271605226 361453207 64747991 650332198 547814821 873131112 984499986 580710491 344613939 615329421 404282591 777196302 118410946 11963934 659717948 507303795 747209595 950367516 753045801 176048491 706920969 173638533 316930518 527337716 578840389 846842421 243743892 197032755 731614680 851429944 626387157 782585390 891983285 190702081 843662892 380320957 46341925 767604463 954225554 298117931 559555112 239118791 302671351 708956286 752167883 1322449 902538348 425160852 358281322 987326867 999028966 751278854 149097087 738185510 584755024 344857640 348462276 159402382 992435733
++*+*--+---*--+*+-+-+--*--+*-+*-***-++++-*++--**-*-++**+*--+---++-+*-+-*****--+*++-++---*+-*-*
90
708511031 580454884 227136142 315621694 816437399 199767158 386431313 686370110 238353452 139416588 779802144 608654642 467489163 831726446 177582404 378458251 337656406 254807945 342315402 863727928 286103825 511591671 575369197 838832647 507977204 814685639 337057684 773267625 341189200 866190414 207863050 394278149 453465048 441178914 35690319 69224577 296167130 849182168 708756333 283539732 546794320 603792560 38629336 734370168 392790933 10814704 666659334 849235982 691489146 328094362 607198396 698640135 10716951 828126963 375568154 828692719 823702322 575575625 918563014 375356521 475300605 659723582 175829677 963552591 888605399 232840649 634512826 82307505 912075233 92779504 653744096 592088094 742745064 820901033 815390368 483300366 543784186 724589233 156227853 913512225 19661415 753126660 567955191 261150273 594085718 547745500 853111654 352199308 705804090 799372957
+--*-*-----*-+---**+*-+*--++*--*+--+--**+***-*--*++-*+-+-***-+*+**+*-*-*-*-+--*---*+*+-++
96
745131348 132164682 53201627 902282100 874213989 356071088 989681045 309159690 969998164 250807468 224153864 637733574 414025807 534447052 239938263 651633817 668396919 458283193 843872939 159037502 11057109 236593972 429549911 851112401 704402304 78699305 238509846 404970270 39586946 9081814 306277267 3711244 564099019 968721766 710261919 586758441 982680786 401446643 500175322 213135781 877490352 453437567 329475656 806918548 853703984 114299540 88539338 160468731 669040349 957021960 49639602 535019049 141455628 719430169 270319732 619425002 947845400 586735438 752287536 216082851 802549300 311244799 445723663 870569122 283877780 655342789 300264268 954376549 311654858 144010011 396563887 901014044 266438208 32948491 722645416 381920087 782995709 50813474 604350127 112815107 314336714 409810162 881358330 733090236 875766857 841898841 821955077 972889196 454176407 564218854 438155439 767047250 355712741 832941005 456329031 419935147
**+++-*+---*-++*+++**++*-*+-*++*-**++*+*++-**+****-+++-+*-+--**-++++***+****+-**-*++--**+++*---
94
879208146 720194280 688588236 132151311 571754818 516340692 372196947 679358302 58621157 310946581 801039916 514131463 921434971 429834826 912359712 414935618 613718553 74440483 16817102 233159445 36718893 621052009 507311235 415092243 764745446 891797180 958065907 610573861 5726480 875130917 57458402 30582627 405021797 687280414 778490387 220908214 154543311 509544961 371751221 979852052 447958755 139043990 514555945 716641402 561306439 453747387 499366646 482768254 787975719 127490978 758930338 383071499 687188345 424770454 344217611 538347542 492161286 496179179 912925428 903636458 25400076 207749328 793144023 909837457 737624442 247805916 983546684 847258002 338263826 680076652 837407636 596231254 321433816 415494165 868192278 2043786 797470453 521067839 969135743 198743740 376254888 359629600 614277288 946583788 732320246 959854749 206526850 756861967 653066081 493501859 24106177 39504781 934132764 132575038
*---+--*-*+--+***+*-+*-+*-+--*****-----++*-+****-*-*--*+*++*+---**+*+*+*-+**+*+-*+*+-**--*+++

42002488 796642576 700424534 492928793 184907764 938887713 107181410 792482963 116518857 549637047 48511747 856433446 590402464 673573447 69495247 203714018 787925377 850112031 375048938 271938638 802494129 158813597 264970784 798528530 490197704 767196026 415353101 689929144 369487202 500663908 925646045 947272745 114170350 422275395 246584468 426418550 579611856 152254016 594726322 728563727 288775478 565138043 680902891 876305510 191112081 452293970 492433812 225768745 679619541 994547367 982603691 15296092 603978680 788518145 465189078 210083862 284880628 329589000 399155372 591915435 797863137 618608585 376324991 227860486 120496725 572177678 329264566 227752653 18519150 658879074 140948055 480823355 695634904 724306259 441449688 256897368 85177480 128320040 41023787 381309904 286849451 367291277 211136278 290206582 349174511 816810643 807052002 541046992 896355733 423997911 637059027 125956299 890644270 192297197 195369584 799285045 466378517

*-+*-**-**+++*-+***+-+*---*--*-**--+*+-+-+*--*+-+*--*-+-+++-+--*-+-*-*++-*-**--+++*--*---++-*++*

100

325956497 703488203 24659275 111168319 30696633 867177774 567622896 185486419 730598881 883230119 563712961 180803964 584941667 42152595 815189025 948445222 884302629 466122431 388540473 372338423 752635513 450641548 639363964 357672619 825047257 242786661 924828610 870704848 270082303 123836441 184865109 256936904 141852852 53253274 127451487 980520417 371387947 159139226 594030471 989127423 368227302 520002431 426259211 996010421 453683913 296897751 30787432 117956896 228079495 691620926 472262826 67500912 817492577 585593640 200764240 553661751 385019596 415018760 607221075 359597740 879829661 611875418 72124927 645005443 360828306 807614336 631355051 144405553 577602237 307688494 780098694 145617805 554856951 119871777 577700931 735031691 442941868 914165376 161547196 986694552 589094296 393092926 299298515 27791972 528267970 281143872 40947478 656044098 203648506 270007357 395952343 102357150 867735114 759911266 233005045 225629783 216508671 965812522 867627947 54865288

+*+--*-*--+-+-+-**++**-*-*-+++*----*+-+-*-+--*-*++***--+--+--++*-*-+--+++--*--+**+**+-++++-++-+-+-*

956166081 237081354 516719910 457360421 651030602 297934201 515637975 519190273 54461470 788822420 279420737 34945495 176179851 783472901 692713303 659271374 203828810 406894617 768216502 461887911 221519925 409786328 934329140 306306033 329222655 272749566 919794473 709469627 302842176 528461835 946937241 537809932 810411833 899731345 234778231 117393561 254762040 126366265 546045205 14512569 569130426 607567456 203472523 734412701 828351711 918290891 334578733 149890177 382043196 169168053 245184636 511942620 100149911 315905467 115836107 692482046 906064513 661013850 824221946 293670720 80472372 90846392 220956727 408720330 754118436 945210308 859229672 853979780 968731675 852433305 908692551 199233651 11771210 317467451 856084951 49265992 825336724 452902485 164913224 679351928 304042220 847674906 821118447 182594926 694723853 291245530 803251413 540653332 592046149 142109566

++*---+*+**-++++***+*+-+*---+-+***--+-*-+++*+--*-*--**+***+--**-+-+-++*****------*+-++**-

465893828 289478394 637733884 308885867 438351788 735511445 307686150 260496183 824225502 905288458 256046492 786615060 148277488 673436291 27093667 401773414 1160361 980127483 369236180 639808765 442848666 282140241 285019731 91637988 737317728 162662493 733270777 918021327 953687807 211142407 579529297 24704404 541921193 680289260 117728749 103507124 79572674 561536575 15361202 98943187 967924857 691391009 194221889 323326354 951458576 315726744 858945948 955751157 648400730 61497384 961311423 784338729 294243201 890869562 522348152 691037449 323402334 682597630 973909177 717395005 95548247 21273692 917317409 131467669 249482841 728306708 443179802 60669811 107016161 656988680 561007944 172140657 89706235 52256148 475262929 286585935 470901312 299761485 692845276 902285286 173616886 630407007 687350996 982195399 356786913 761716439 746065586 615855955 988179377 213166205 714725937 33387759 271839281 110967052 14364116 148251161 502652519 90843729

-+-++-*+-+-++*---*+*+-**+**--*-+-*-*-+**+****+-+--*-*---++-*-**+-*+*+*****+--*-*-*++++**-*+*----+

350460548 683529871 618335624 301938708 443122496 740210529 608748989 773860075 674745679 22051422 3363717 987211125 7455042 150942802 582997451 291451956 853047743 431725539 36063965 916459186 38819334 344832685 905333497 1107506 975568033 430522271 161030190 197567954 895976561 296526280 570825600 567895344 214279060 533392121 265331207 871875814 43745873 576354855 463692349 974512750 403562709 549167732 828509064 696570071 722237507 802639046 991590202 959577397 340576026 62211977 989146740 14037103 635490010 76262658 676592780 771209273 144694401 589889441 374019705 794324052 631865159 951489016 543939718 848804382 598908343 454624051 191117102 551826494 15211257 347769268 242088328 821837708 735776787 734680412 604336524 27170997 995319171 131982742 84150036 813106575 43808331 416344584 422178259 871443637 216387827 398825027 345823744 111101361 155871499 780534153

**-*-++-*-**-*-+**++*-*-+--++-*-+*+-**+*+*-+--+-****++++--+--***-***+--*-*-**-+*+**+--*++

369083073 419494718 203958830 132372075 390802926 108536958 359364853 19500017 269482466 116851881 344733006 179976765 665095536 360566894 927223606 19745537 491617131 255871431 124073757 831691852 936168299 628337639 858503621 108450073 907654947 372031410 911623368 876473964 201368080 876278835 741544686 308383962 105473714 378332068 996785400 271362759 704071329 849695712 653933557 203390911 361151674 38280361 955354553 522170431 280173923 910896686 363582043 455411786 666760984 961246757 160430953 687453873 722283066 498568491 361164110 310314399 980345471 155440227 622193202 125958147 10507896 741345861 389880790 480072833 776884410 323432536 97991633 567659920 127960073 533577083 783345366 151218843 982868351 60821489 482093522 436596314 984998445 444073626 446463882 520127981 851250321 237935771 36254845 181834749 1892735 590141893 44183356 907397065 651309846 304020843 692801648

+--++--+-***+-*****-*+**-*-+-+-*-+---+-++**---*+*+++--*--+****-++-+*++*-+**--**---+*+++*-+

485961444 707318302 57064654 176495871 981660811 806591453 749245216 252359665 640407166 201588566 229199175 22221498 253223551 89060045 36553720 599810065 690462711 312436980 238112789 353747414 1235787 421192028 507582469 881355702 715088908 889803479 427807294 715763499 180319586 856082545 252088586 371033343 805019366 508584217 969333119 98454585 271605226 361453207 64747991 650332198 547814821 873131112 984499986 580710491 344613939 615329421 404282591 777196302 118410946 11963934 659717948 507303795 747209595 950367516 753045801 176048491 706920969 173638533 316930518 527337716 578840389 846842421 243743892 197032755 731614680 851429944 626387157 782585390 891983285 190702081 843662892 380320957 46341925 767604463 954225554 298117931 559555112 239118791 302671351 708956286 752167883 1322449 902538348 425160852 358281322 987326867 999028966 751278854 149097087 738185510 584755024 344857640 348462276 159402382 992435733

++*+*--+---*--+*+-+-+--*--+*-+*-***-++++-*++--**-*-++**+*--+---++-+*-+-*****--+*++-++---*+-*-*

708511031 580454884 227136142 315621694 816437399 199767158 386431313 686370110 238353452 139416588 779802144 608654642 467489163 831726446 177582404 378458251 337656406 254807945 342315402 863727928 286103825 511591671 575369197 838832647 507977204 814685639 337057684 773267625 341189200 866190414 207863050 394278149 453465048 441178914 35690319 69224577 296167130 849182168 708756333 283539732 546794320 603792560 38629336 734370168 392790933 10814704 666659334 849235982 691489146 328094362 607198396 698640135 10716951 828126963 375568154 828692719 823702322 575575625 918563014 375356521 475300605 659723582 175829677 963552591 888605399 232840649 634512826 82307505 912075233 92779504 653744096 592088094 742745064 820901033 815390368 483300366 543784186 724589233 156227853 913512225 19661415 753126660 567955191 261150273 594085718 547745500 853111654 352199308 705804090 799372957

+--*-*-----*-+---**+*-+*--++*--*+--+--**+***-*--*++-*+-+-***-+*+**+*-*-*-*-+--*---*+*+-++

745131348 132164682 53201627 902282100 874213989 356071088 989681045 309159690 969998164 250807468 224153864 637733574 414025807 534447052 239938263 651633817 668396919 458283193 843872939 159037502 11057109 236593972 429549911 851112401 704402304 78699305 238509846 404970270 39586946 9081814 306277267 3711244 564099019 968721766 710261919 586758441 982680786 401446643 500175322 213135781 877490352 453437567 329475656 806918548 853703984 114299540 88539338 160468731 669040349 957021960 49639602 535019049 141455628 719430169 270319732 619425002 947845400 586735438 752287536 216082851 802549300 311244799 445723663 870569122 283877780 655342789 300264268 954376549 311654858 144010011 396563887 901014044 266438208 32948491 722645416 381920087 782995709 50813474 604350127 112815107 314336714 409810162 881358330 733090236 875766857 841898841 821955077 972889196 454176407 564218854 438155439 767047250 355712741 832941005 456329031 419935147

**+++-*+---*-++*+++**++*-*+-*++*-**++*+*++-**+****-+++-+*-+--**-++++***+****+-**-*++--**+++*---

879208146 720194280 688588236 132151311 571754818 516340692 372196947 679358302 58621157 310946581 801039916 514131463 921434971 429834826 912359712 414935618 613718553 74440483 16817102 233159445 36718893 621052009 507311235 415092243 764745446 891797180 958065907 610573861 5726480 875130917 57458402 30582627 405021797 687280414 778490387 220908214 154543311 509544961 371751221 979852052 447958755 139043990 514555945 716641402 561306439 453747387 499366646 482768254 787975719 127490978 758930338 383071499 687188345 424770454 344217611 538347542 492161286 496179179 912925428 903636458 25400076 207749328 793144023 909837457 737624442 247805916 983546684 847258002 338263826 680076652 837407636 596231254 321433816 415494165 868192278 2043786 797470453 521067839 969135743 198743740 376254888 359629600 614277288 946583788 732320246 959854749 206526850 756861967 653066081 493501859 24106177 39504781 934132764 132575038

*---+--*-*+--+***+*-+*-+*-+--*****-----++*-+****-*-*--*+*++*+---**+*+*+*-+**+*+-*+*+-**--*+++

302477149

455689444

197787710

802805207

652251842

492754358

934589866

940842836

821057755

931125012

15多校2-9/HDU 5308 I Wanna Become A 24-Point Master

July 23, 20152015-07-23hahaschool2 Comments

更新

根据出题人的回复，问题应该已经修复了，本文代码中的PATCH部分可以忽略。关于原来出现的问题的证明也已经失效，敬请留意。

题意

给出一个数字n，问你如果给你n个n，你要怎么样才能利用加减乘除运算给算成24呢？注意，没个数字只能使用一次，所有的数字必须都要用到。你要按照题里面介绍的特别的表示方法把你的解法表示出来。除法是可以出分数的，因为是SPJ，应该可以过。

思路

我个人不太认同出题人题解里面给出的手算4～15的所有情况，对于较大的数再机智得直接消除凑24，因为手算的太多了。

我的思路是对于比较小的情况，即n <= 27的时候，可以直接利用dfs找出答案。因为题目给出的表示方法其实意外地适合dfs的搜索过程，我们不断的枚举下一个操作，即从当前没用过的数里面选出两个，然后尝试加减乘除，每一次尝试就是改变当前数组尾部的值，同时做好标记进入下一层。只要搜索成功，我们就可以在dfs的退出过程中将路径保存下来，开一个stack，把这些个结果压进去，输出的时候弹出来，顺序就正好是正序了。

对于比较大的情况，事情就变得非常简单，假如说现在的n = k，那么只要找出24个相同的数k，加到一起，就是24 * k了，然后再额外拿一个k，做一下商，就得到了24，对于多出来的数，我们可以找两个k做一下差得0，然后用得到的0去乘上下一个多余的数，最后剩下一个0，和刚才的24加一下，多余的数也消耗掉了。

注意点

做这个题的时候发生了两处失误，首先是dfs的时候，范围设置的不正确，两层的循环都应该是从1开始的，原来外层从1开始而内层却是从i+1开始(i是外层的循环变量)，这样显然丢解了，而且搜索速度也拖慢了。

其次是题目中要求每个数只可以用一次，结果我偷懒把一个0跟好多哥数字去乘了，这样肯定就错了。

然后dfs应该采取一些必要的优化，比如说跳过重复的区段（剪枝），如果不做的话可能超时。如果实在没办法，打表也可以，反正才24种情况，并不会被拒绝提交。

然而还是没过

折腾了一下午后发现很有可能这个题的评测器在实现上有漏洞，通过排(feng)除(kuang)法(jiao)，发现有3组数据没有通过评测器，但是确实是正确的。

n = 13

1 + 2

3 + 4

5 + 6

7 + 8

9 + 10

11 + 12

13 + 14

15 + 16

17 + 20

21 - 22

18 / 23

19 + 24

n = 14

1 + 2

3 + 4

5 + 6

7 + 8

9 + 10

11 + 12

13 + 14

15 + 16

17 + 18

19 * 20

22 + 23

24 - 25

26 / 21

n = 22

1 + 2

3 + 4

5 + 6

7 + 8

9 + 10

11 + 12

13 + 14

15 + 16

17 + 18

19 + 20

21 + 22

23 + 24

25 + 26

27 + 28

29 + 30

31 * 32

33 + 34

35 - 39

36 / 40

38 / 37

42 - 41

如果数据确实不符合题意，请与我跟进，谢谢。

代码

为了过，最后没有办法特殊对待给上面三组数据打了补丁。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

int seq[100];
bool vis[100];
int n = 0;
struct expr{
    int a,b;
    char op;
    expr(int _a, char _op,int _b){
        a = _a;
        b = _b;
        op = _op;
    }
};
stack<expr> resstk;

bool dfs(int dep){
    if (dep == 2*n) {
        if (seq[dep-1] == 24) {
            return true;
        }else{
            return false;
        }
    }
    int prev = -909303;
    for (int i = 1; i < dep; i++) {
        if (!vis[i]) {
            if (seq[i] == prev) {
                continue;
            }else{
                prev = seq[i];
            }
            vis[i] = true;
            int inner_prev = -909303;
            for (int j = 1; j < dep; j++) {
                if (!vis[j]) {
                    if (seq[j] == inner_prev) {
                        continue;
                    }else{
                        inner_prev = seq[j];
                    }
                    vis[j] = true;
                    seq[dep] = seq[i] + seq[j];
                    if (dfs(dep+1)) {
                        resstk.push(expr(i,'+',j));
                        return true;
                    }else{
                        seq[dep] = seq[i] - seq[j];
                        if (dfs(dep+1)) {
                            resstk.push(expr(i,'-',j));
                            return true;
                        }else{
                            seq[dep] = seq[i] * seq[j];
                            if (dfs(dep+1)) {
                                resstk.push(expr(i,'*',j));
                                return true;
                            }else{
                                if (seq[j] != 0 && seq[i] % seq[j] == 0) {
                                    seq[dep] = seq[i] / seq[j];
                                    if (dfs(dep+1)) {
                                        resstk.push(expr(i,'/',j));
                                        return true;
                                    }else{
                                        vis[j] = false;
                                        seq[dep] = 0;
                                    }
                                }else{
                                    vis[j] = false;
                                    seq[dep] = 0;
                                }
                            }
                        }
                    }
                }

            }
            vis[i] = false;
        }
    }
    return false;
}
void init(){
    memset(seq, 0, sizeof(seq));
    memset(vis, 0, sizeof(vis));
    while (!resstk.empty()) {
        resstk.pop();
    }
}


void print(){
    while (!resstk.empty()) {
        expr &nowExpr = resstk.top();
        printf("%d %c %d\n",nowExpr.a,nowExpr.op,nowExpr.b);
        resstk.pop();
    }

}
void printSpec(){
    printf("1 - 2\n");
    int cur = n+2,pos = 3,zero = n+1;
    for (int i = 1; i <= n - 27; i++,pos++,cur++,zero++) {
        printf("%d * %d\n",zero,pos);
    }
    for (int i = 1; i <= 12; i++,pos+=2) {
        printf("%d + %d\n",pos,pos+1);
    }
    for (; cur <= 2*n-4;cur += 2) {
        printf("%d + %d\n",cur,cur+1);
    }
    printf("%d / %d\n",2*n-3,n);
    printf("%d + %d\n",2*n-2,zero);

}

int main(){
    while (scanf("%d",&n)!=EOF){
        if (n > 27) {
            printSpec();
            continue;
        }
        /*
         PATCH FOR THE DEFECTIVE SPJ
         */
        if (n == 22){
            printf("1 + 2\n"); printf("3 + 4\n"); printf("5 + 6\n"); printf("7 + 8\n"); printf("%d + 9\n",n+1);
            printf("%d / 10\n",n+2); printf("%d / 11\n",n+3); printf("%d / 12\n",n+4); printf("%d / 13\n",n+5);
            printf("%d * %d\n",n+6,n+7); printf("%d * %d\n",n+8,n+9); printf("%d * %d\n",n+10,n+11); printf("14 - 15\n");
            int now=n+13; for (int i=16;i<=n;i++){printf("%d * %d\n",i,now); now++;} printf("%d + %d\n",n+12,now); continue;
        }
        if (n == 13 || n == 14){
            printf("1 + 2\n");
            for (int i=1;i<=n*2-24;i++) printf("%d / %d\n",i*2+1,i*2+2); int num=n*4-46;
            int now=n+1+n*2-24;
            if (n!=12){
                printf("%d - %d\n",n+1,n+2); now++;
                for (int i=2;i<=n*2-24;i++){printf("%d - %d\n",now,n+1+i); now++;}
            }
            int k1=now;
            printf("%d - %d\n",num+1,num+2); num+=3; now++;
            for (int i=num;i<=n;i++){printf("%d * %d\n",i,now); now++;}
            printf("%d + %d\n",k1,now); continue;
        }
        /*
         END OF PATCH
         */
        if (n >= 1) {
            init();
            for (int i = 1; i <= n; i++) {
                seq[i] = n;
            }
            dfs(n+1);
            if (!resstk.empty()) {
                print();
            }else{
                puts("-1");
            }
            continue;
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

int seq[100];

bool vis[100];

int n = 0;

struct expr{

int a,b;

char op;

expr(int _a, char _op,int _b){

a = _a;

b = _b;

op = _op;

}

};

stack<expr> resstk;

bool dfs(int dep){

if (dep == 2*n) {

if (seq[dep-1] == 24) {

return true;

}else{

return false;

}

int prev = -909303;

for (int i = 1; i < dep; i++) {

if (!vis[i]) {

if (seq[i] == prev) {

continue;

}else{

prev = seq[i];

}

vis[i] = true;

int inner_prev = -909303;

for (int j = 1; j < dep; j++) {

if (!vis[j]) {

if (seq[j] == inner_prev) {

continue;

}else{

inner_prev = seq[j];

}

vis[j] = true;

seq[dep] = seq[i] + seq[j];

if (dfs(dep+1)) {

resstk.push(expr(i,'+',j));

return true;

}else{

seq[dep] = seq[i] - seq[j];

if (dfs(dep+1)) {

resstk.push(expr(i,'-',j));

return true;

}else{

seq[dep] = seq[i] * seq[j];

if (dfs(dep+1)) {

resstk.push(expr(i,'*',j));

return true;

}else{

if (seq[j] != 0 && seq[i] % seq[j] == 0) {

seq[dep] = seq[i] / seq[j];

if (dfs(dep+1)) {

resstk.push(expr(i,'/',j));

return true;

}else{

vis[j] = false;

seq[dep] = 0;

}

}else{

vis[j] = false;

seq[dep] = 0;

}

vis[i] = false;

}

return false;

}

void init(){

memset(seq, 0, sizeof(seq));

memset(vis, 0, sizeof(vis));

while (!resstk.empty()) {

resstk.pop();

}

void print(){

while (!resstk.empty()) {

expr &nowExpr = resstk.top();

printf("%d %c %d\n",nowExpr.a,nowExpr.op,nowExpr.b);

resstk.pop();

}

void printSpec(){

printf("1 - 2\n");

int cur = n+2,pos = 3,zero = n+1;

for (int i = 1; i <= n - 27; i++,pos++,cur++,zero++) {

printf("%d * %d\n",zero,pos);

}

for (int i = 1; i <= 12; i++,pos+=2) {

printf("%d + %d\n",pos,pos+1);

}

for (; cur <= 2*n-4;cur += 2) {

printf("%d + %d\n",cur,cur+1);

}

printf("%d / %d\n",2*n-3,n);

printf("%d + %d\n",2*n-2,zero);

}

int main(){

while (scanf("%d",&n)!=EOF){

if (n > 27) {

printSpec();

continue;

}

PATCH FOR THE DEFECTIVE SPJ

if (n == 22){

printf("1 + 2\n"); printf("3 + 4\n"); printf("5 + 6\n"); printf("7 + 8\n"); printf("%d + 9\n",n+1);

printf("%d / 10\n",n+2); printf("%d / 11\n",n+3); printf("%d / 12\n",n+4); printf("%d / 13\n",n+5);

printf("%d * %d\n",n+6,n+7); printf("%d * %d\n",n+8,n+9); printf("%d * %d\n",n+10,n+11); printf("14 - 15\n");

int now=n+13; for (int i=16;i<=n;i++){printf("%d * %d\n",i,now); now++;} printf("%d + %d\n",n+12,now); continue;

}

if (n == 13 || n == 14){

printf("1 + 2\n");

for (int i=1;i<=n*2-24;i++) printf("%d / %d\n",i*2+1,i*2+2); int num=n*4-46;

int now=n+1+n*2-24;

if (n!=12){

printf("%d - %d\n",n+1,n+2); now++;

for (int i=2;i<=n*2-24;i++){printf("%d - %d\n",now,n+1+i); now++;}

}

int k1=now;

printf("%d - %d\n",num+1,num+2); num+=3; now++;

for (int i=num;i<=n;i++){printf("%d * %d\n",i,now); now++;}

printf("%d + %d\n",k1,now); continue;

}

END OF PATCH

if (n >= 1) {

init();

for (int i = 1; i <= n; i++) {

seq[i] = n;

}

dfs(n+1);

if (!resstk.empty()) {

print();

}else{

puts("-1");

}

continue;

}

return 0;

}

标准答案里边很豪放地用了分数，正常来讲评测器应该是接受分数的，但不知道为什么不接受我这个调换位置保证不出现分数的答案了，真的很怪。我自己写了一个检查我自己答案的评测器，没有提供对分数的支持，但是评测器会在发现出现分数的时候报错，因为我的答案是已经调换顺序保证不出分数的了，此外也检查了每个数字的使用情况，保证和题意一致。

#include <iostream>
#include <cstring>

using namespace std;
int seq[200000];
int cnt[200000];

int main(int argc, const char * argv[]) {
    freopen("testdata.1009", "r", stdin);
    memset(seq, 0, sizeof(seq));
    int n = 0;
    while (cin >> n) {
        if (n <= 3) {
            int tmp;
            cin >> tmp;
            continue;
        }
        for (int i = 1; i <= n; i++) {
            seq[i] = n;
        }
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n-1; i++) {
            int a,b;
            char op;
            cin >> a >> op >> b;
            cnt[a]++,cnt[b]++;
            switch (op) {
                case '+':
                    seq[i+n] = seq[a] + seq[b];
                    break;
                case '-':
                    seq[i+n] = seq[a] - seq[b];
                    break;
                case '*':
                    seq[i+n] = seq[a] * seq[b];
                    break;
                case '/':
                    if (seq[a] % seq[b]) {
                        cout << "WRONG ANSWER AT " << n << endl;
                        return 998;
                    }
                    seq[i+n] = seq[a] / seq[b];
                    break;
                default:
                    break;
            }
        }if (seq[2*n-1] == 24) {
            for (int i = 1; i <= 2*n-2; i++) {
                if (cnt[i] != 1) {
                    cout << "WRONG ANSWER AT " << n << endl;
                    return 998;
                }
            }
        }else{
            cout << "WRONG ANSWER AT " << n << endl;
            return 998;
        }
        cout << "CORRECT AT " << n << endl;
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int seq[200000];

int cnt[200000];

int main(int argc, const char * argv[]) {

freopen("testdata.1009", "r", stdin);

memset(seq, 0, sizeof(seq));

int n = 0;

while (cin >> n) {

if (n <= 3) {

int tmp;

cin >> tmp;

continue;

}

for (int i = 1; i <= n; i++) {

seq[i] = n;

}

memset(cnt, 0, sizeof(cnt));

for (int i = 1; i <= n-1; i++) {

int a,b;

char op;

cin >> a >> op >> b;

cnt[a]++,cnt[b]++;

switch (op) {

case '+':

seq[i+n] = seq[a] + seq[b];

break;

case '-':

seq[i+n] = seq[a] - seq[b];

break;

case '*':

seq[i+n] = seq[a] * seq[b];

break;

case '/':

if (seq[a] % seq[b]) {

cout << "WRONG ANSWER AT " << n << endl;

return 998;

}

seq[i+n] = seq[a] / seq[b];

break;

default:

break;

}

}if (seq[2*n-1] == 24) {

for (int i = 1; i <= 2*n-2; i++) {

if (cnt[i] != 1) {

cout << "WRONG ANSWER AT " << n << endl;

return 998;

}

}else{

cout << "WRONG ANSWER AT " << n << endl;

return 998;

}

cout << "CORRECT AT " << n << endl;

}

return 0;

}

从1开始测了1个GB的数据，没发现问题，如果评测器有问题，请跟进，谢谢。

如果你还是不相信我

下面是官方题解：

虽然很蛋疼，写这么多其实就是为了让这么个玩意别再坑更多的人了。