QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#716392 | #9585. 划分数字 | qzez# | AC ✓ | 380ms | 53352kb | C++14 | 1.1kb | 2024-11-06 15:07:07 | 2024-11-06 15:07:08 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define LB lower_bound
using namespace std;using ll=long long;using pii=pair<int,int>;
const int N=1e6+5;
int n,m;
ll dp[180][19][180][11];
ll pw[20];
void init(){
for(int i=pw[0]=1;i<=18;i++) pw[i]=pw[i-1]*10;
for(int x=0;x<=18*9;x++){
dp[x][0][0][min(10,x)]=1;
for(int i=1;i<=18;i++){
for(int y=0;y<=x&&y<=i*9;y++){
for(int z=0;z<=10;z++)if(dp[x][i-1][y][z]){
for(int o=0;o<10;o++) if(o+y<=x){
dp[x][i][y+o][min(z,abs(x-2*(y+o)))]+=dp[x][i-1][y][z];
}
}
}
}
}
}
ll calc(ll x){
x++;
ll ans=0;
for(int i=0;i<=18*9;i++){
int sum=0,mi=min(i,10);
for(int j=18;~j;j--){
int y=x/pw[j]%10;
for(int o=0;o<y;o++){
int sumt=sum+o,mit=min(mi,abs(i-2*sumt));
if(sumt>i) continue;
for(int z=0;z<=10;z++) ans+=dp[i][j][i-sumt][z]*min(mit,z);
}
sum+=y;mi=min(mi,abs(i-2*sum));
}
}
return ans;
}
void Solve(){
ll l,r;scanf("%lld%lld",&l,&r);
printf("%lld\n",calc(r)-calc(l-1));
}
int main(){
init();
int t=1;
scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 11ms
memory: 53352kb
input:
5 108 112 10 1000 10 10000 10 100000 114514 1919810
output:
16 3136 31636 316636 5715693
result:
ok 5 number(s): "16 3136 31636 316636 5715693"
Test #2:
score: 0
Accepted
time: 62ms
memory: 53308kb
input:
1000 66 87 51 78 63 98 25 50 33 71 76 79 25 44 20 65 52 56 34 82 38 75 75 82 36 99 48 85 11 43 32 65 57 90 34 42 22 53 15 60 53 63 48 50 23 84 42 50 76 80 43 91 10 33 27 65 70 88 89 93 37 78 23 27 27 57 44 58 83 84 76 90 46 97 21 35 59 88 22 98 62 84 65 83 45 67 42 89 72 78 45 57 61 76 15 34 18 39 4...
output:
73 76 125 82 111 4 62 129 7 150 115 27 208 125 104 93 113 30 94 144 31 14 193 23 12 153 74 116 67 31 121 15 88 36 9 50 178 38 98 245 77 64 62 138 16 33 49 68 73 180 116 125 180 269 16 98 14 225 150 245 189 18 160 57 36 126 81 184 61 99 20 256 70 275 160 117 62 149 215 105 68 214 211 163 27 32 66 64 ...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 69ms
memory: 51340kb
input:
1000 784 967 376 651 296 477 139 299 581 816 734 888 331 522 739 929 242 524 342 978 151 632 713 991 426 851 120 967 346 995 392 395 186 457 11 358 233 410 244 334 116 372 355 391 100 392 431 619 773 887 201 310 811 887 586 691 198 646 138 333 30 909 183 349 576 930 557 672 56 197 252 794 93 109 611...
output:
626 842 511 529 810 495 609 660 890 2044 1496 878 1341 2660 2091 32 796 1041 577 281 762 149 908 610 398 343 210 343 1340 600 2782 485 1207 365 469 1717 58 631 1604 2669 617 1598 396 1176 634 1872 1437 1034 615 769 1914 1749 226 86 1139 243 462 961 470 2027 1089 3067 2420 2604 1708 560 2070 925 2632...
result:
ok 1000 numbers
Test #4:
score: 0
Accepted
time: 84ms
memory: 53188kb
input:
1000 3598 9083 470 9161 1710 4348 61 8659 6105 6644 6667 7289 3549 7478 620 6212 1613 4450 4877 9942 2748 7481 3611 6284 4466 4769 5966 9717 1026 4042 5044 7571 5464 5842 199 2514 5779 7877 2291 2937 9295 9463 691 3944 36 5075 2260 2794 5489 7016 1189 7183 3746 8262 7828 9580 1139 6043 8714 9763 193...
output:
17459 27550 8232 26780 1401 2146 12223 17661 8842 15996 14701 8403 986 11390 9498 7680 1278 7274 6655 2135 351 10386 15890 1715 5047 18898 14222 5410 15492 3381 13478 759 24841 4063 30685 3940 6709 14709 4794 22019 6924 1045 7324 1599 14470 7398 19462 11867 2171 1207 6234 397 7958 28789 23917 21359 ...
result:
ok 1000 numbers
Test #5:
score: 0
Accepted
time: 98ms
memory: 51468kb
input:
1000 60939 89474 20234 42449 47719 73300 1054 92903 23163 81963 63919 75600 33034 48111 55227 87518 41440 99367 36751 49952 10301 33926 440 95202 26209 98365 63134 65743 63242 99621 17604 81880 47283 69026 26037 48301 36777 48230 30988 33761 83960 93881 31857 48266 18908 39131 4517 99682 35389 88405...
output:
90288 70042 80921 289837 186035 36068 47597 101115 183272 42263 74626 298075 227113 7371 115710 203527 68786 70232 36573 8409 31007 51770 64320 301441 167102 126745 246184 130530 31369 99424 178429 46205 231840 10094 127676 157101 47942 83420 75159 135254 9137 93259 120533 141010 53805 8190 163519 4...
result:
ok 1000 numbers
Test #6:
score: 0
Accepted
time: 126ms
memory: 53212kb
input:
1000 316086 814053 74312 221944 160779 568241 35235 171075 334579 336613 673352 678332 7821 352456 67132 111645 6660 821642 110585 318314 55193 795901 67500 944447 6031 194292 574966 592049 368848 585855 117125 119266 376237 870267 216131 781602 233462 788156 231375 337770 132153 981227 73320 362278...
output:
1575218 468602 1286991 430304 6284 14463 1090560 141755 2579014 657544 2343123 2769656 594201 57622 684436 6768 1562021 1787877 1751842 335937 2682834 914973 337681 408488 144338 434839 988926 304516 1465327 743502 863132 560480 2467232 1520803 828052 660838 1836357 504669 441652 1161341 534209 1148...
result:
ok 1000 numbers
Test #7:
score: 0
Accepted
time: 133ms
memory: 53264kb
input:
1000 6493884 9647345 5477548 8738766 1792193 3768876 3327948 8934835 461499 9933332 1420085 4601879 3209130 8488144 1392449 6282860 344825 5781991 6497488 9400631 7006065 9817198 1427816 8482960 601108 3766473 1514857 5368532 3174162 4279908 3767491 9589741 1843100 6197847 2447370 9956799 4554837 92...
output:
9947205 10309060 6248084 17741590 29980577 10074471 16696042 15481159 17203699 9186182 8881715 22320529 10009545 12195788 3501726 18417712 13793646 23754929 14808142 14681234 14111076 19377057 11283699 34342 2195713 7029682 21736469 18037073 16966457 221190 17124528 1297957 20610988 4992918 23053420...
result:
ok 1000 numbers
Test #8:
score: 0
Accepted
time: 155ms
memory: 51572kb
input:
1000 34263116 42164841 12039845 63031838 33358095 42325900 71211065 91520511 11565294 83926793 37964895 65262290 81649380 92260801 44971564 49670034 19618065 94435208 58500850 88873898 21470181 42890190 38515402 74285478 4629363 54570258 22755723 40326245 37342574 82404653 4106391 60051452 13752585 ...
output:
25026209 161467546 28402843 64281020 229119604 86430844 33601961 14795662 236844920 96117601 67816943 113277147 158105676 55653014 142697840 177157905 89688110 127920165 60583651 95574909 115748421 48531893 70938302 169985206 100318092 43374382 22621611 186926573 20198840 241756669 70234499 11893160...
result:
ok 1000 numbers
Test #9:
score: 0
Accepted
time: 166ms
memory: 51528kb
input:
1000 232413596 984261298 301717871 395259963 163088238 607809098 538546598 573275540 30213181 379497588 570643528 733010682 477208093 931324009 54536987 434301098 332193621 587496115 138868198 859547538 408018041 964285826 211372702 696851564 741991627 946334414 276269131 964102888 460310993 7106643...
output:
2380111958 295969647 1408219701 109992437 1105871800 514208009 1438076728 1202596504 807995257 2281911872 1760959576 1536654753 646671611 2177836171 792761261 2630829418 311755330 2566119385 717377505 635123195 1141951566 622677527 966264699 1611137948 662813279 950466471 898958475 871362864 7943151...
result:
ok 1000 numbers
Test #10:
score: 0
Accepted
time: 308ms
memory: 51600kb
input:
1000 415942217158650532 760462065274856764 828452448592632834 873676283980192138 161363433102126383 399957182134299403 47039450701819202 914942083903052826 736904239156221039 816632444368340363 108367437642189242 584470917963738350 303585775377649539 976626955671018129 372820133648158075 94876283651...
output:
1090979520222318395 143208686513759387 755546344393844130 2748358318811708847 252472651767173800 1507661011090217139 2131296897644860583 1823818278096044136 491572320488671209 1444310074482571618 1027758211932928050 2381767287736403562 1055817317828170236 787532605174509760 1318949145143266962 14896...
result:
ok 1000 numbers
Test #11:
score: 0
Accepted
time: 295ms
memory: 51476kb
input:
1000 926860653820043969 952477738312793266 990082961650358209 999641451881715134 940208206337467632 980041552684851709 919636885275103396 939674408101485386 931007217432895938 943890115141023426 962012924116943033 971937131141583219 906942192779639931 979508540602245242 903655902493135950 9634990264...
output:
81120763240587395 30267741630669530 126138925812538357 63451955852412389 40795820820197643 31426555508323072 229793225757846953 189503178950302133 37015099395725914 253737885374045663 297147361484746146 194353250845739806 103146576816178049 48202954481967224 34625286456154800 20161984368028696 23789...
result:
ok 1000 numbers
Test #12:
score: 0
Accepted
time: 380ms
memory: 51404kb
input:
1000 999999999999999929 999999999999999999 999999999999999930 999999999999999985 999999999999999945 999999999999999953 999999999999999979 999999999999999983 999999999999999937 999999999999999973 999999999999999918 999999999999999925 999999999999999906 999999999999999998 999999999999999928 9999999999...
output:
420 358 61 34 246 44 555 382 422 221 208 30 332 78 292 284 245 21 521 308 21 339 224 12 346 47 421 179 356 449 283 267 85 112 106 194 442 104 10 31 79 325 249 126 350 539 175 28 307 446 448 131 164 290 374 9 298 174 555 525 57 350 34 117 421 155 128 371 442 136 482 189 308 310 106 462 546 334 371 40...
result:
ok 1000 numbers
Test #13:
score: 0
Accepted
time: 9ms
memory: 51600kb
input:
1 1000000000000000000 1000000000000000000
output:
1
result:
ok 1 number(s): "1"
Extra Test:
score: 0
Extra Test Passed