QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#716392#9585. 划分数字qzez#AC ✓380ms53352kbC++141.1kb2024-11-06 15:07:072024-11-06 15:07:08

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 15:07:08]
  • 评测
  • 测评结果:AC
  • 用时:380ms
  • 内存:53352kb
  • [2024-11-06 15:07:07]
  • 提交

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