2021牛客暑期多校训练营1
比赛地址
A题 Alice and Bob 题目地址
题目大意：两人博弈，每次一个人从一堆中拿 
个，同时从另一堆拿 &preview=true)
个，问谁先不能拿。
打表：
很简单可以想明白，如果（2,3）后手赢了，那么（2,3）可以直接转移到的状态都是先手赢。
另一个人的策略可以是：第一堆拿 第二堆拿
、第一堆拿
，第二堆拿
。
代码：
#include <bits/stdc++.h>
using namespace std;
int a[10001][10001];
int main()
{
freopen("ex.out","w",stdout);
for(int i=1;i<=5000;i++)
{
a[i][1]=1;
a[1][i]=1;
a[i][i]=1;
}
for(int i=2;i<=5000;i++)
{
for(int j=2;j<=5000;j++)
{
if(a[i][j]==0)
{
cout<<"{"<<i<<","<<j<<"}"<<",";
for(int ii=1;ii<=5000;ii++)
{
for(int jj=0;jj<=5000;jj++)
{
if(i+ii<=5000&&j+ii*jj<=5000)
a[i+ii][j+ii*jj]=1;
if(i+ii*jj<=5000&&j+ii<=5000)
a[i+ii*jj][j+ii]=1;
if(j+ii<=5000&&i+ii*jj<=5000)
a[j+ii][i+ii*jj]=1;
if(j+ii*jj<=5000&&i+ii<=5000)
a[j+ii*jj][i+ii]=1;
}
}
a[i][j]=0;
}
}
}
fclose(stdin);
fclose(stdout);
}打表结果：
{2,3},{5,7},{9,12},{11,15},{14,20},{17,22},{19,33},{24,32},{26,35},{28,58},{29,40},{31,38},{37,53},{42,52},{44,75},{45,60},{47,65},{49,70},{50,62},{55,68},{57,79},{64,87},{67,86},{72,92},{74,99},{77,101},{81,174},{82,118},{83,110},{85,113},{89,123},{90,116},{94,129},{95,127},{97,126},{103,136},{105,199},{106,146},{108,145},{112,166},{115,246},{120,161},{122,160},{125,164},{131,309},{132,182},{133,177},{135,198},{138,180},{139,156},{141,239},{142,190},{143,186},{148,203},{149,195},{151,340},{152,197},{154,232},{158,218},{163,229},{168,215},{170,286},{171,228},{172,224},{176,350},{179,298},{184,253},{185,236},{188,268},{189,259},{192,241},{194,256},{201,266},{205,281},{207,274},{208,264},{210,271},{212,322},{213,317},{214,278},{217,289},{220,327},{221,280},{223,315},{226,301},{231,332},{234,307},{238,372},{243,391},{244,325},{245,313},{248,306},{250,321},{252,305},{255,339},{258,565},{261,346},{263,359},{270,375},{273,521},{276,358},{283,370},{285,362},{288,379},{291,456},{293,367},{295,390},{296,386},{300,432},{303,415},{311,464},{312,411},{319,408},{324,501},{329,435},{331,702},{334,454},{336,545},{337,489},{338,449},{342,496},{343,446},{345,445},{348,558},{349,467},{352,461},{354,590},{355,577},{356,532},{357,479},{361,478},{364,494},{366,527},{369,520},{374,509},{377,505},{381,639},{382,553},{384,470},{388,485},{393,518},{395,474},{397,511},{399,487},{400,483},{402,588},{404,601},{405,531},{407,530},{410,568},{413,537},{417,586},{419,557},{420,541},{421,529},{423,525},{425,580},{427,560},{429,719},{430,624},{431,570},{434,549},{437,574},{439,603},{440,600},{442,683},{443,556},{448,614},{451,871},{452,651},{453,620},{458,772},{459,671},{460,596},{463,661},{466,666},{469,610},{472,761},{473,632},{476,760},{477,691},{481,660},{491,726},{492,635},{498,673},{499,646},{503,653},{504,649},{507,788},{508,648},{513,776},{514,716},{515,664},{516,658},{523,740},{534,893},{535,855},{539,752},{540,735},{543,723},{547,825},{548,800},{551,697},{555,711},{562,1202},{563,771},{564,693},{567,737},{572,744},{576,766},{579,780},{582,986},{583,768},{585,748},{592,877},{593,811},{594,805},{595,722},{598,1599},{599,828},{605,866},{606,845},{607,810},{609,849},{612,842},{616,831},{617,822},{619,787},{622,818},{626,799},{628,785},{630,836},{634,778},{637,879},{641,886},{643,899},{644,827},{655,1046},{656,918},{657,876},{663,870},{668,989},{669,929},{675,985},{676,857},{678,912},{679,904},{680,896},{682,1107},{685,869},{687,964},{689,920},{695,883},{699,946},{700,937},{704,948},{706,910},{708,957},{710,892},{713,996},{714,935},{718,969},{721,976},{725,1358},{728,1010},{730,917},{732,924},{734,1167},{739,1062},{742,1036},{743,1007},{746,1065},{747,1000},{750,982},{751,944},{754,1020},{756,1013},{757,995},{759,1854},{763,991},{765,1038},{770,1150},{774,1017},{782,1032},{784,1085},{790,1082},{791,1061},{793,1090},{794,956},{796,1029},{797,1023},{802,1777},{803,1072},{807,1081},{808,1079},{813,1118},{814,1117},{815,1110},{816,1040},{820,1131},{824,1070},{830,1098},{833,1053},{835,1122},{838,1201},{839,1165},{841,1322},{844,1241},{847,1225},{848,1120},{851,1190},{852,1106},{853,1076},{859,1145},{861,1206},{862,1180},{863,1130},{864,1055},{868,1156},{873,1384},{874,1212},{875,1102},{881,1194},{882,1175},{885,1164},{888,1192},{890,1186},{895,1285},{898,1227},{901,2018},{902,1211},{906,1208},{908,1261},{909,1231},{914,1245},{915,1214},{922,1394},{923,1269},{926,1363},{927,1243},{931,1274},{933,1307},{939,1405},{940,1268},{942,1381},{943,1219},{950,1265},{952,1314},{954,1254},{959,1311},{960,1297},{962,1420},{963,1295},{966,1390},{967,1279},{971,1337},{972,1302},{973,1248},{975,3859},{978,1284},{980,1547},{981,1348},{984,1317},{988,1451},{993,1378},{994,1329},{998,1812},{999,1372},{1002,1336},{1004,1461},{1005,1400},{1006,1346},{1009,1366},{1012,1361},{1015,1465},{1016,1432},{1019,1419},{1022,1477},{1025,1376},{1027,1292},{1031,1633},{1034,1389},{1035,1371},{1042,1527},{1043,1334},{1045,1387},{1048,1458},{1050,2369},{1051,1331},{1057,1695},{1058,1414},{1060,1408},{1064,1446},{1067,1543},{1068,1521},{1069,1413},{1074,1514},{1075,1492},{1078,1428},{1084,1687},{1087,1499},{1088,1457},{1089,1397},{1092,1468},{1094,1455},{1096,1443},{1100,1425},{1104,1464},{1109,1481},{1112,1606},{1113,1539},{1115,1758},{1116,1484},{1124,1510},{1125,1449},{1127,1626},{1129,1516},{1133,1575},{1134,1509},{1136,1532},{1137,1502},{1139,1537},{1140,1438},{1142,1563},{1143,1470},{1144,1403},{1147,2604},{1148,1674},{1149,1581},{1152,1541},{1153,1536},{1155,1534},{1158,1569},{1159,1529},{1161,1525},{1163,1592},{1169,1561},{1171,1612},{1173,1619},{1174,1491},{1177,2077},{1178,1577},{1182,2623},{1183,1560},{1185,1665},{1188,1611},{1196,1906},{1197,1590},{1199,1653},{1200,1636},{1204,1679},{1210,2455},{1216,1736},{1217,1625},{1221,1640},{1223,1929},{1224,1717},{1229,1617},{1233,1730},{1235,1678},{1236,1651},{1237,1643},{1238,1622},{1239,1580},{1247,1605},{1250,1820},{1251,1746},{1253,1721},{1256,2215},{1257,1799},{1258,1661},{1260,1708},{1263,1769},{1264,1713},{1267,1795},{1271,2004},{1272,1707},{1276,1694},{1278,1692},{1281,1682},{1283,1664},{1287,1882},{1289,1702},{1290,1684},{1294,1866},{1299,1845},{1300,1756},{1301,1710},{1304,1825},{1305,1765},{1309,1832},{1310,1774},{1313,2810},{1316,1767},{1319,1811},{1320,1754},{1324,2388},{1325,1787},{1327,1729},{1333,2140},{1339,1822},{1340,1785},{1342,1850},{1343,1802},{1344,1782},{1350,2840},{1351,2288},{1352,1842},{1354,1831},{1356,1888},{1357,1762},{1360,1838},{1365,1879},{1368,1884},{1369,1878},{1370,1859},{1374,2836},{1375,2036},{1380,1824},{1383,1919},{1386,1904},{1392,1863},{1396,1901},{1399,1978},{1402,1966},{1407,1914},{1410,1877},{1412,2042},{1416,1847},{1418,1772},{1422,1935},{1424,2040},{1427,2981},{1430,1837},{1434,1975},{1436,1953},{1437,1923},{1440,2051},{1441,1994},{1442,1869},{1445,2209},{1448,1949},{1453,2007},{1460,1947},{1463,2011},{1467,2230},{1472,1942},{1474,2205},{1475,1922},{1479,2031},{1480,1941},{1483,2134},{1486,2657},{1487,2026},{1489,2107},{1490,2030},{1494,1992},{1495,1964},{1497,1997},{1501,2098},{1504,1986},{1505,1970},{1507,2003},{1508,1981},{1512,2191},{1513,2088},{1518,2096},{1520,1972},{1523,3303},{1524,2059},{1531,2076},{1545,2390},{1546,2056},{1549,2421},{1550,2094},{1551,2070},{1553,2129},{1554,2033},{1555,2029},{1557,2116},{1559,3159},{1565,2067},{1566,2050},{1568,2105},{1571,2001},{1573,2256},{1574,2161},{1579,2103},{1583,2338},{1584,2180},{1586,2148},{1587,2137},{1588,2100},{1589,2080},{1594,2168},{1596,3385},{1597,2085},{1601,2195},{1603,2152},{1604,2142},{1608,2329},{1609,2281},{1610,2203},{1614,2198},{1616,2176},{1621,2184},{1624,2669},{1628,2194},{1630,2145},{1632,3560},{1635,2302},{1638,2229},{1642,2224},{1645,2954},{1646,2298},{1647,2276},{1648,2255},{1650,2239},{1655,2310},{1657,2182},{1659,2217},{1663,2193},{1667,2640},{1668,2366},{1669,2356},{1670,2174},{1672,2293},{1673,2202},{1676,2347},{1681,2271},{1686,3335},{1689,2437},{1690,2237},{1691,2222},{1697,4572},{1698,2297},{1699,2268},{1700,2261},{1701,2234},{1704,2132},{1706,2287},{1712,2246},{1715,2607},{1716,2439},{1719,2341},{1723,2368},{1724,2322},{1726,2335},{1728,2283},{1732,2376},{1734,3235},{1735,2495},{1738,2427},{1740,2490},{1741,2163},{1743,2362},{1744,2350},{1745,2318},{1748,3156},{1749,2453},{1751,2254},{1753,2345},{1760,2426},{1761,2317},{1764,2406},{1771,2538},{1776,2381},{1779,2557},{1780,2411},{1781,2385},{1784,2449},{1789,2402},{1790,2358},{1792,2393},{1794,2404},{1797,2910},{1798,2375},{1801,3252},{1804,2516},{1805,2332},{1807,2435},{1808,2420},{1810,2473},{1814,2365},{1816,3712},{1817,2400},{1818,2398},{1827,2957},{1828,2469},{1830,2415},{1834,2634},{1835,2459},{1840,2751},{1841,2523},{1844,2493},{1849,2485},{1852,2879},{1856,2720},{1857,2551},{1858,2444},{1861,3273},{1862,2613},{1865,2513},{1868,3991},{1871,2505},{1873,2395},{1875,2830},{1876,2502},{1881,2576},{1886,2773},{1890,2525},{1891,2462},{1893,2743},{1894,2572},{1896,2709},{1897,2511},{1899,2600},{1900,2515},{1903,2567},{1908,4079},{1909,2509},{1911,2564},{1913,2530},{1916,2592},{1917,2575},{1921,2708},{1925,2550},{1926,2549},{1927,2492},{1931,4030},{1932,2700},{1933,2665},{1934,2642},{1937,2597},{1938,2570},{1940,2548},{1944,2661},{1946,8478},{1951,2789},{1952,2689},{1955,2675},{1956,2647},{1958,2632},{1959,2616},{1961,2931},{1963,2761},{1968,2953},{1969,2691},{1974,2611},{1977,2673},{1980,2986},{1983,2645},{1985,2738},{1988,2687},{1989,2546},{1991,2707},{1996,2780},{1999,2704},{2006,3078},{2009,2682},{2013,2556},{2015,2729},{2016,2684},{2020,2938},{2021,2702},{2023,2779},{2025,2671},{2028,3048},{2035,4593},{2038,2832},{2039,2627},{2044,3121},{2045,2785},{2047,2749},{2048,2668},{2053,4805},{2055,2747},{2058,2733},{2061,3037},{2062,2759},{2064,2806},{2066,2754},{2069,2902},{2072,2816},{2074,2809},{2079,2850},{2082,3254},{2083,3207},{2084,2856},{2087,2798},{2090,2956},{2091,2768},{2092,2746},{2102,2891},{2109,3138},{2110,2864},{2111,2758},{2113,2883},{2114,2804},{2118,4706},{2119,2788},{2121,2925},{2122,2921},{2124,2899},{2125,2834},{2126,2826},{2128,2778},{2131,3334},{2136,7030},{2139,2882},{2144,3811},{2147,2881},{2150,3039},{2151,2869},{2154,2970},{2155,2862},{2157,4055},{2158,2814},{2160,2919},{2165,2792},{2167,2943},{2170,2873},{2172,3020},{2173,2843},{2178,2927},{2179,2917},{2186,3478},{2187,2846},{2189,2985},{2197,3244},{2200,2915},{2207,3067},{2208,3036},{2211,3908},{2212,2905},{2214,3024},{2219,2946},{2221,3261},{2226,3229},{2227,3015},{2228,2997},{2232,3064},{2233,2972},{2236,2960},{2241,3061},{2242,3007},{2244,2974},{2248,3119},{2249,3001},{2251,3148},{2252,3089},{2253,3026},{2258,3110},{2259,3099},{2260,2979},{2263,3433},{2265,2993},{2267,3046},{2270,3006},{2273,3338},{2274,3032},{2275,3004},{2278,5154},{2279,3589},{2280,3097},{2285,3031},{2290,3172},{2292,3333},{2295,3057},{2300,3193},{2301,3084},{2304,3460},{2305,3163},{2306,3125},{2308,3130},{2312,3118},{2314,3425},{2316,3128},{2320,3218},{2321,3082},{2324,3117},{2326,3250},{2328,3012},{2331,3113},{2334,3202},{2337,5391},{2340,3570},{2343,3396},{2344,3145},{2349,3763},{2352,3519},{2353,3197},{2354,3101},{2360,3423},{2361,3217},{2364,4038},{2371,3585},{2372,3289},{2373,3247},{2374,3177},{2378,3731},{2379,3213},{2380,3106},{2383,3201},{2384,3169},{2387,3314},{2392,3182},{2397,3810},{2408,3359},{2409,3190},{2413,3179},{2417,3103},{2419,3512},{2423,3258},{2425,4507},{2429,3393},{2431,3116},{2433,3341},{2434,3225},{2441,3327},{2442,3317},{2443,3302},{2446,3269},{2448,4240},{2451,3281},{2452,3232},{2457,3351},{2461,3552},{2464,5074},{2465,3206},{2467,3413},{2471,5415},{2472,3246},{2475,3299},{2477,3864},{2478,3598},{2479,3287},{2481,3500},{2482,3345},{2484,3286},{2487,3498},{2488,3297},{2489,3294},{2497,4154},{2498,3495},{2499,3325},{2501,3384},{2504,3941},{2507,3358},{2508,3355},{2518,3441},{2519,3381},{2520,3374},{2521,3350},{2527,3471},{2529,3368},{2532,3412},{2533,3379},{2535,3534},{2537,3323},{2540,3838},{2541,3693},{2542,3544},{2543,3488},{2544,3405},{2553,3924},{2554,3395},{2555,3391},{2559,3592},{2560,3538},{2561,3241},{2563,3510},{2566,3502},{2569,3422},{2574,3699},{2578,3536},{2579,3467},{2580,3459},{2581,3454},{2582,3377},{2584,3684},{2585,3475},{2586,3343},{2587,3312},{2589,7373},{2590,3722},{2594,3409},{2595,3372},{2599,3466},{2602,3558},{2606,3518},{2609,3464},{2615,4125},{2618,3628},{2619,3605},{2620,3601},{2621,3525},{2625,3739},{2626,3418},{2629,3578},{2630,3508},{2636,3667},{2637,3480},{2638,3463},{2644,3621},{2649,4089},{2650,3671},{2651,3547},{2652,3449},{2654,3367},{2656,3584},{2659,3569},{2663,4619},{2664,3506},{2667,3772},{2677,3748},{2678,3720},{2679,3658},{2680,3529},{2686,5423},{2693,4018},{2694,3614},{2696,3565},{2698,3844},{2699,3638},{2706,3640},{2711,3977},{2712,3619},{2714,4162},{2715,3665},{2717,3643},{2718,3549},{2722,4815},{2723,3600},{2725,4479},{2726,3635},{2728,3814},{2731,3852},{2732,3727},{2735,3759},{2736,3689},{2737,3651},{2740,3832},{2741,3676},{2742,3647},{2745,3898},{2753,3917},{2756,3719},{2757,3673},{2763,4052},{2765,3698},{2767,3825},{2770,3974},{2771,3709},{2775,3705},{2777,4012},{2782,3681},{2784,3890},{2787,4608},{2791,3656},{2794,3862},{2795,3714},{2797,3957},{2800,3762},{2801,3733},{2802,3704},{2808,3769},{2812,3848},{2813,3787},{2818,3743},{2820,3854},{2822,5661},{2823,3771},{2825,3756},{2828,4075},{2829,3724},{2838,3999},{2839,3793},{2842,4745},{2845,3888},{2848,3932},{2849,3886},{2852,4550},{2853,3824},{2855,3777},{2858,3955},{2859,3882},{2860,3781},{2861,3776},{2866,3809},{2867,3737},{2871,4390},{2872,4186},{2875,3907},{2876,3767},{2878,4044},{2885,5060},{2886,3900},{2888,6547},{2889,3880},{2893,4011},{2895,3835},{2897,4782},{2898,3801},{2901,3995},{2904,4336},{2907,3935},{2909,3822},{2912,3916},{2914,3971},{2923,4197},{2924,4109},{2929,3927},{2930,3872},{2933,4192},{2934,4135},{2936,3923},{2940,3841},{2941,3798},{2945,4152},{2948,3948},{2950,3944},{2952,4027},{2959,4138},{2962,4199},{2963,4160},{2964,3921},{2966,4082},{2967,3896},{2968,3795},{2976,4151},{2977,3982},{2978,3966},{2983,3998},{2988,4779},{2989,4231},{2990,4121},{2991,4081},{2995,4074},{2996,3965},{2999,4363},{3000,4060},{3003,4302},{3009,4237},{3010,4017},{3011,3952},{3014,4443},{3017,4010},{3019,4037},{3022,5143},{3023,4103},{3028,4176},{3029,4141},{3030,3914},{3034,4107},{3035,4070},{3041,4111},{3043,4051},{3045,4128},{3050,4249},{3051,4016},{3053,4097},{3055,3961},{3059,4700},{3060,4049},{3063,4330},{3066,3877},{3069,4278},{3071,6465},{3072,4150},{3074,4057},{3076,3821},{3080,4263},{3081,4033},{3086,4140},{3087,4100},{3091,4447},{3092,4234},{3093,4219},{3094,4120},{3096,4223},{3105,4324},{3108,4449},{3112,4503},{3115,4222},{3123,4119},{3127,4173},{3132,4429},{3133,4184},{3135,6081},{3136,4195},{3137,4146},{3140,4262},{3142,7295},{3143,4210},{3147,4209},{3150,4026},{3152,4253},{3153,4169},{3155,5788},{3158,4243},{3161,5094},{3162,4272},{3165,4182},{3167,4563},{3168,4361},{3171,4543},{3174,4683},{3175,4271},{3181,4300},{3184,4395},{3186,6414},{3187,4068},{3189,4291},{3192,4296},{3195,4247},{3199,4348},{3204,4307},{3209,4338},{3211,4261},{3212,4172},{3215,4314},{3216,4277},{3220,4343},{3221,4319},{3223,4992},{3224,4506},{3227,4495},{3228,4446},{3231,4425},{3234,4373},{3237,4375},{3239,4305},{3243,4528},{3249,4454},{3256,4471},{3257,4345},{3260,4610},{3263,5326},{3264,4581},{3265,4290},{3267,6971},{3268,4547},{3271,4549},{3272,4310},{3275,4356},{3277,4539},{3278,4270},{3280,4165},{3283,4526},{3285,4341},{3291,4493},{3293,4473},{3296,4546},{3301,4678},{3305,6684},{3306,4453},{3308,4452},{3309,4442},{3310,4384},{3316,4466},{3319,5271},{3320,4288},{3322,4511},{3329,4416},{3331,4298},{3337,4317},{3340,5962},{3347,4663},{3348,4635},{3349,4523},{3353,6224},{3354,4744},{3357,4519},{3361,4383},{3363,5818},{3364,4522},{3366,4525},{3370,4650},{3371,4552},{3376,7861},{3383,4438},{3387,4399},{3389,4914},{3390,4622},{3398,4532},{3399,4468},{3400,4372},{3402,4559},{3404,4434},{3407,4489},{3411,4579},{3415,4810},{3417,4725},{3420,6349},{3421,4631},{3427,4897},{3428,4691},{3429,4605},{3430,4478},{3432,4398},{3435,4690},{3436,4601},{3438,4487},{3440,4712},{3443,4571},{3445,5188},{3446,4675},{3447,4670},{3448,4599},{3451,5029},{3452,4567},{3453,4437},{3456,5108},{3457,4803},{3458,4595},{3462,4945},{3469,4578},{3473,4892},{3474,4856},{3477,4708},{3482,4660},{3483,4628},{3485,4733},{3486,4621},{3490,4882},{3491,4717},{3492,4674},{3494,4809},{3497,4681},{3504,5435},{3505,4847},{3514,4836},{3515,4742},{3517,4751},{3521,4657},{3523,5434},{3524,4763},{3527,4876},{3528,4761},{3531,4969},{3532,4722},{3540,4789},{3542,4181},{3546,5531},{3551,4773},{3554,5006},{3555,4850},{3557,4832},{3562,4705},{3564,7970},{3567,4941},{3568,4644},{3572,5163},{3574,4786},{3576,4921},{3577,4740},{3580,4768},{3582,4979},{3583,4778},{3587,5172},{3588,4967},{3591,4928},{3594,4818},{3595,4772},{3596,4586},{3603,4839},{3607,4428},{3609,4801},{3611,5014},{3612,4889},{3613,4652},{3616,4939},{3617,4871},{3623,4821},{3625,4765},{3627,5070},{3630,5039},{3631,4935},{3633,4926},{3634,4807},{3637,4845},{3642,4977},{3645,4814},{3649,5353},{3650,5002},{3653,5276},{3654,4959},{3655,4907},{3660,5118},{3661,4972},{3662,4878},{3663,4771},{3669,4865},{3675,4888},{3678,5300},{3679,5047},{3680,4956},{3683,5161},{3686,4775},{3688,5474},{3691,5183},{3692,4948},{3695,5024},{3697,5107},{3701,5625},{3702,5090},{3703,5027},{3707,5092},{3711,5146},{3716,5054},{3717,4903},{3726,4932},{3729,5113},{3735,5200},{3736,5199},{3741,5106},{3742,5000},{3745,5233},{3746,5127},{3747,5008},{3750,4732},{3752,5399},{3753,4953},{3755,8730},{3758,5042},{3761,5508},{3765,5022},{3774,5230},{3775,5078},{3779,6364},{3780,5616},{3783,6241},{3784,5097},{3786,5432},{3789,5258},{3790,5148},{3792,5065},{3797,7201},{3800,5206},{3803,5157},{3804,5087},{3806,6104},{3807,5103},{3813,5255},{3816,5455},{3817,5004},{3819,8109},{3820,5111},{3827,5210},{3829,5130},{3831,5459},{3834,5059},{3837,5552},{3840,6201},{3843,5453},{3846,5279},{3847,5181},{3850,5209},{3851,5139},{3856,5177},{3858,5530},{3861,5052},{3866,5408},{3867,5193},{3869,5586},{3870,5190},{3871,5124},{3874,5365},{3876,5176},{3879,5511},{3884,5286},{3892,5247},{3893,5179},{3894,5134},{3902,5303},{3904,5252},{3905,5122},{3910,6090},{3911,5396},{3913,5068},{3919,5802},{3920,5325},{3926,5266},{3929,8064},{3930,5237},{3934,5891},{3937,5360},{3938,5219},{3940,5580},{3943,5663},{3946,5823},{3947,5298},{3950,5215},{3954,5866},{3959,5488},{3960,5321},{3963,6358},{3964,5340},{3968,5499},{3969,5302},{3973,5291},{3976,5307},{3979,5744},{3981,5222},{3984,6828},{3985,5229},{3987,5334},{3989,5383},{3990,5356},{3993,5609},{3997,5886},{4001,6389},{4002,5338},{4003,5315},{4005,5492},{4006,5373},{4008,5314},{4014,5376},{4020,5504},{4022,5443},{4024,5244},{4029,5407},{4032,5570},{4035,5590},{4036,5282},{4040,5555},{4042,5431},{4046,6037},{4047,5697},{4048,5269},{4054,6486},{4059,5487},{4062,5635},{4063,5332},{4065,5579},{4067,5430},{4072,5546},{4073,5518},{4077,5481},{4078,5464},{4084,6029},{4085,5644},{4087,5358},{4091,9632},{4092,5420},{4094,5607},{4095,5521},{4096,5471},{4099,5640},{4102,5602},{4105,5478},{4113,5634},{4114,5458},{4116,5589},{4117,5541},{4118,5382},{4124,5619},{4127,6130},{4130,5692},{4132,5462},{4133,5403},{4137,6073},{4143,5536},{4145,5783},{4148,6280},{4149,5569},{4156,5600},{4158,5452},{4164,5841},{4167,6277},{4168,5406},{4171,5678},{4175,5796},{4178,5653},{4180,6598},{4188,5711},{4190,5650},{4194,5972},{4201,5765},{4202,5669},{4204,5564},{4205,5544},{4207,5781},{4208,5362},{4212,5792},{4213,5730},{4215,5466},{4217,5735},{4221,5758},{4225,6521},{4226,5734},{4227,5681},{4228,5675},{4229,5659},{4233,5560},{4236,5667},{4239,6590},{4242,5701},{4245,5535},{4251,7273},{4252,5707},{4255,6233},{4256,5806},{4258,5751},{4259,5723},{4260,5706},{4265,5925},{4266,5715},{4268,5638},{4274,5937},{4275,5674},{4280,5816},{4281,5717},{4283,8572},{4284,5760},{4286,7025},{4287,5773},{4293,5918},{4295,6111},{4304,5772},{4309,5825},{4312,5791},{4316,5950},{4321,5832},{4323,5666},{4326,6004},{4328,5947},{4329,5747},{4332,5732},{4334,5594},{4340,5994},{4347,5894},{4350,5874},{4351,5762},{4353,6493},{4354,5884},{4358,6134},{4359,5862},{4360,5813},{4365,6010},{4366,5929},{4368,5890},{4370,5768},{4377,5956},{4379,5859},{4381,6198},{4382,5523},{4386,6113},{4387,6060},{4388,5945},{4389,5928},{4392,6194},{4393,6023},{4394,5828},{4397,5983},{4402,6346},{4403,6018},{4404,5906},{4406,6245},{4407,5940},{4408,5904},{4409,5880},{4411,5893},{4412,5878},{4414,5821},{4418,5978},{4420,5870},{4421,5753},{4423,5840},{4427,6638},{4431,6335},{4432,5936},{4436,5985},{4440,6172},{4441,6007},{4445,6529},{4451,6445},{4456,6002},{4458,6255},{4459,5931},{4461,8008},{4462,6485},{4463,5924},{4465,6107},{4470,6054},{4475,5914},{4477,6139},{4481,5838},{4483,6031},{4485,6208},{4486,6051},{4491,6324},{4492,6100},{4497,6072},{4499,5801},{4501,6506},{4502,6042},{4505,6169},{4509,6036},{4513,6065},{4515,6764},{4516,6289},{4517,6110},{4521,7660},{4530,6304},{4531,6167},{4534,6391},{4535,6069},{4536,6064},{4538,6197},{4541,6520},{4542,6093},{4545,6122},{4554,6098},{4556,6117},{4558,6400},{4561,6253},{4562,6149},{4565,5980},{4569,6859},{4570,6588},{4574,6156},{4575,6145},{4577,6166},{4583,9101},{4584,6268},{4585,6161},{4588,6627},{4589,6247},{4590,6079},{4592,8850},{4597,9769},{4598,6316},{4603,6437},{4604,6020},{4607,6174},{4612,6265},{4613,6214},{4615,9687},{4616,6342},{4618,6232},{4624,6427},{4625,6332},{4627,6196},{4630,7290},{4633,6744},{4634,6239},{4637,6729},{4638,6388},{4639,6307},{4641,6184},{4643,6155},{4646,6501},{4647,6462},{4648,6017},{4655,6257},{4659,6136},{4662,6699},{4665,6164},{4667,6285},{4669,6250},{4672,6354},{4677,9407},{4680,6920},{4685,6455},{4686,6431},{4687,6283},{4689,6298},{4693,7043},{4694,6910},{4695,6221},{4697,6622},{4699,6219},{4702,6322},{4704,6321},{4710,6888},{4711,6314},{4714,6619},{4715,6271},{4719,6440},{4720,6327},{4724,6857},{4727,7350},{4728,6404},{4730,6423},{4731,6386},{4735,6716},{4736,6595},{4737,6363},{4739,6292},{4747,6781},{4748,6435},{4750,6345},{4753,6422},{4755,6451},{4757,6476},{4758,6362},{4760,7453},{4767,6694},{4770,6341},{4777,6629},{4781,6339},{4784,6374},{4788,7671},{4791,6555},{4792,6419},{4793,6385},{4795,9814},{4796,6498},{4797,6303},{4799,7576},{4800,7013},{4812,7182},{4813,6579},{4817,6527},{4820,6511},{4823,6576},{4825,6785},{4826,6331},{4827,6207},{4829,6776},{4831,6492},{4834,6568},{4835,6418},{4838,6753},{4841,9986},{4842,6541},{4844,6524},{4849,6612},{4852,6958},{4853,6566},{4854,6478},{4855,6454},{4859,6545},{4860,6473},{4861,6433},{4862,6394},{4864,6647},{4867,6412},{4869,6771},{4870,6368},{4873,6678},{4874,6409},{4875,6302},{4881,6666},{4884,6925},{4885,6564},{4887,7029},{4891,6751},{4894,6698},{4895,6652},{4896,6464},{4900,6611},{4902,6535},{4905,6600},{4909,8030},{4910,6662},{4911,6540},{4913,6681},{4916,6656},{4918,7327},{4919,6513},{4923,7267},{4924,7226},{4925,6637},{4930,6518},{4931,6425},{4934,8215},{4937,6802},{4938,6644},{4943,7742},{4944,6614},{4947,8317},{4950,6981},{4951,6835},{4952,6763},{4955,6626},{4958,6837},{4961,6719},{4962,6559},{4964,6906},{4966,6609},{4971,8846},{4974,6814},{4975,6641},{4981,8293},{4982,6743},{4984,6768},{4986,6748},{4987,6715},{4988,6673},{4989,6664},{4991,8501},{4994,6742},{4995,6728},{4997,6897},{4998,6804},{4999,6759},{5010,6724},{5012,7189},{5013,6903},{5016,6746},{5017,6661},{5019,7978},{5020,6714},{5021,6702},{5026,6848},{5031,6844},{5032,6732},{5034,6953},{5035,6812},{5036,6795},{5037,6726},{5041,7057},{5044,6793},{5046,6884},{5049,6876},{5051,6741},{5056,6687},{5058,7426},{5062,7600},{5064,7220},{5067,6881},{5072,6670},{5076,6557},{5080,6824},{5082,7045},{5083,6976},{5084,6800},{5086,6905},{5089,7137},{5096,7168},{5099,6917},{5101,6809},{5105,6966},{5110,7143},{5115,6870},{5117,6842},{5120,8089},{5121,6826},{5126,6952},{5129,6983},{5132,6780},{5136,7233},{5137,6868},{5141,9182},{5142,7012},{5145,6933},{5150,7105},{5151,6788},{5152,6787},{5156,7069},{5159,7040},{5165,7417},{5166,6901},{5167,6855},{5169,7272},{5170,6899},{5174,7088},{5175,6970},{5185,6956},{5187,6924},{5192,7035},{5195,7178},{5196,7082},{5197,6993},{5202,7140},{5204,6942},{5208,6989},{5212,7122},{5214,7933},{5217,7063},{5218,6969},{5221,7097},{5224,7054},{5226,6950},{5228,7387},{5232,7079},{5235,7566},{5236,7118},{5239,9171},{5240,7261},{5241,6944},{5243,7249},{5246,6947},{5249,7107},{5251,7306},{5254,8823},{5257,7740},{5260,7042},{5262,7008},{5264,7187},{5265,7007},{5268,7353},{5273,6938},{5274,6696},{5278,7110},{5281,6887},{5284,7135},{5288,7117},{5289,7090},{5290,7077},{5293,7032},{5295,7103},{5297,7053},{5306,7480},{5309,7331},{5310,7166},{5312,6995},{5317,7148},{5318,7059},{5320,6932},{5323,7561},{5324,7165},{5328,7534},{5329,7329},{5330,7298},{5331,7197},{5336,7160},{5342,7557},{5343,7205},{5345,7112},{5346,7068},{5349,7237},{5351,7476},{5355,7154},{5364,9707},{5367,7245},{5369,7340},{5371,7235},{5375,7175},{5378,7157},{5380,7208},{5385,7396},{5386,7257},{5387,7224},{5388,7211},{5390,9340},{5393,7294},{5395,7170},{5398,7450},{5401,9933},{5402,8125},{5405,7452},{5410,7399},{5411,7260},{5413,8525},{5414,7750},{5418,7287},{5422,7131},{5425,7415},{5427,7348},{5428,7325},{5437,7403},{5439,7259},{5441,7648},{5442,7422},{5445,7255},{5447,9500},{5448,7478},{5450,7493},{5451,7401},{5457,7305},{5461,7598},{5468,7632},{5469,7549},{5470,7337},{5473,7587},{5476,7879},{5477,7412},{5480,7746},{5483,7798},{5484,7319},{5486,7279},{5490,7370},{5494,9464},{5495,7394},{5497,7617},{5501,7449},{5503,7297},{5506,7313},{5510,7520},{5513,7490},{5514,7436},{5516,7366},{5520,7310},{5525,7529},{5527,7372},{5529,7475},{5533,7573},{5538,7406},{5539,7195},{5543,7504},{5548,7991},{5549,7616},{5551,8691},{5554,7398},{5557,7543},{5558,7464},{5562,7626},{5563,7547},{5566,7525},{5568,7219},{5572,8669},{5573,8368},{5574,7546},{5575,7514},{5578,7487},{5582,8113},{5583,7670},{5584,7393},{5588,7590},{5592,7390},{5596,8431},{5597,7657},{5598,7596},{5599,7542},{5604,7681},{5605,7613},{5606,7217},{5611,7484},{5613,8019},{5614,7506},{5618,7513},{5621,7691},{5623,7766},{5624,7637},{5627,8280},{5628,7900},{5629,7688},{5630,7442},{5632,7953},{5633,7608},{5637,7571},{5642,9850},{5643,7890},{5646,7678},{5647,7383},{5649,7644},{5652,8039},{5655,7709},{5656,7621},{5658,7584},{5665,9156},{5671,7787},{5673,9472},{5677,7763},{5680,7852},{5683,7792},{5684,7696},{5686,7615},{5687,7559},{5690,7654},{5691,7582},{5694,7821},{5695,7665},{5699,7752},{5703,7699},{5704,7579},{5709,9983},{5710,7647},{5713,8197},{5714,7733},{5719,9704},{5720,7808},{5721,7730},{5722,7575},{5725,7904},{5726,7725},{5728,7153},{5737,8184},{5738,7888},{5739,7810},{5740,7786},{5743,7651},{5746,8148},{5749,7806},{5750,7624},{5755,8128},{5756,7851},{5764,7998},{5767,7708},{5770,7757},{5775,7776},{5776,7694},{5778,8273},{5779,7873},{5780,7674},{5785,7932},{5786,7921},{5787,7838},{5790,7828},{5794,8451},{5795,7919},{5798,7906},{5800,7773},{5804,7846},{5808,8367},{5809,8194},{5810,7875},{5812,7800},{5815,7843},{5820,8306},{5827,7856},{5830,7945},{5831,7893},{5834,7860},{5837,7915},{5843,7835},{5845,8314},{5846,7882},{5848,7765},{5850,8096},{5851,7827},{5852,7782},{5854,8333},{5855,7913},{5857,7974},{5861,7966},{5864,7796},{5868,7837},{5872,9131},{5873,7995},{5876,7903},{5882,8522},{5883,8269},{5888,8048},{5896,8612},{5897,8461},{5898,8417},{5899,7960},{5901,9015},{5902,8210},{5903,8142},{5908,8073},{5909,7825},{5911,8530},{5912,7937},{5913,7867},{5916,7940},{5920,8038},{5922,8023},{5927,8152},{5933,9540},{5934,8237},{5935,8102},{5939,8559},{5942,8010},{5944,7958},{5949,8481},{5952,8027},{5954,9142},{5955,8005},{5958,8162},{5959,8059},{5960,8004},{5964,8227},{5965,7737},{5967,8036},{5968,7831},{5970,8046},{5971,8045},{5974,9873},{5975,8512},{5976,7896},{5987,8179},{5988,8145},{5989,7947},{5991,8224},{5993,8222},{5996,8079},{5998,8486},{5999,7886},{6001,8363},{6006,8167},{6009,8058},{6012,9482},{6013,8248},{6014,8244},{6015,8191},{6016,8186},{6022,8057},{6025,8018},{6027,9603},{6028,8101},{6033,9174},{6034,8382},{6035,8042},{6039,8095},{6041,8232},{6044,7951},{6046,9820},{6047,8000},{6049,8207},{6050,8157},{6053,8357},{6056,8219},{6058,8800},{6059,8413},{6062,8320},{6063,8012},{6067,8386},{6068,8354},{6075,8164},{6077,8094},{6083,8896},{6084,8278},{6086,8106},{6088,8365},{6089,8299},{6092,8313},{6095,8221},{6096,8141},{6102,8425},{6106,8395},{6109,8352},{6115,8493},{6116,8264},{6119,8763},{6120,8218},{6124,8724},{6125,8261},{6126,8088},{6128,8347},{6129,8257},{6132,8402},{6141,8410},{6143,8083},{6147,8688},{6148,8345},{6152,8490},{6153,8292},{6158,8343},{6160,8309},{6163,9214},{6171,8290},{6176,8762},{6177,8439},{6178,8329},{6180,8325},{6182,8406},{6186,8252},{6188,8139},{6190,8374},{6191,8188},{6193,9557},{6200,8362},{6203,8727},{6204,8350},{6205,8339},{6210,9200},{6211,8324},{6213,8633},{6216,8360},{6218,8503},{6223,8586},{6226,8316},{6228,8815},{6229,8714},{6230,8204},{6235,8552},{6236,8448},{6237,8390},{6244,8821},{6249,8436},{6252,8786},{6259,9492},{6260,8455},{6262,8506},{6264,8469},{6267,9523},{6270,8563},{6274,8985},{6275,8405},{6279,8580},{6282,9431},{6287,8592},{6288,8400},{6291,9565},{6294,8554},{6296,9053},{6297,8378},{6300,8550},{6306,8677},{6309,8464},{6311,9153},{6313,8541},{6318,8597},{6319,8473},{6320,8472},{6329,8649},{6330,8591},{6334,8622},{6337,8518},{6338,8476},{6351,8605},{6353,8722},{6356,8497},{6360,9014},{6361,8639},{6367,8626},{6370,8661},{6372,8700},{6373,8569},{6377,8566},{6380,8549},{6382,8754},{6384,8515},{6393,9031},{6396,8735},{6397,8595},{6402,8657},{6406,8373},{6411,8601},{6416,9965},{6417,8521},{6429,8877},{6439,8978},{6442,9426},{6443,8666},{6447,9088},{6448,8665},{6450,8734},{6453,8652},{6457,8702},{6459,8642},{6461,9109},{6467,8660},{6469,8933},{6470,8812},{6471,8674},{6472,8574},{6475,8457},{6480,8775},{6481,8761},{6483,8685},{6488,8771},{6489,8720},{6490,8716},{6491,8673},{6495,8510},{6497,9475},{6500,8629},{6503,8599},{6508,9020},{6509,8903},{6510,8747},{6515,9194},{6516,8803},{6517,8749},{6523,8868},{6526,9589},{6531,8758},{6533,9703},{6534,8913},{6537,8819},{6539,8792},{6544,8753},{6550,8916},{6551,8773},{6552,8377},{6554,9266},{6561,8941},{6563,8781},{6570,9123},{6571,9087},{6572,8848},{6575,8826},{6578,8960},{6582,9042},{6584,8840},{6586,8857},{6592,8884},{6594,8780},{6597,8955},{6602,8870},{6603,8839},{6605,8958},{6606,8794},{6608,8687},{6616,9347},{6617,8947},{6621,9257},{6624,8838},{6631,8906},{6633,9147},{6634,8943},{6636,8909},{6640,9036},{6643,8968},{6646,9057},{6649,9301},{6650,8741},{6654,8976},{6655,8863},{6659,9289},{6660,9009},{6668,8932},{6672,9079},{6676,8983},{6677,8919},{6680,9278},{6683,9030},{6686,9212},{6689,9403},{6690,9090},{6691,8859},{6693,8990},{6701,9435},{6704,9128},{6705,9061},{6707,9013},{6708,8989},{6710,8967},{6711,8952},{6713,9953},{6721,9048},{6723,9447},{6734,9151},{6736,9050},{6738,9067},{6739,9006},{6750,9221},{6755,9073},{6757,9100},{6761,9026},{6767,9226},{6770,9203},{6773,9140},{6775,9108},{6778,9548},{6779,9363},{6783,9166},{6790,9188},{6792,9138},{6798,9208},{6806,9259},{6808,9008},{6811,9460},{6816,9653},{6817,9127},{6819,9160},{6821,9134},{6823,8996},{6830,9219},{6831,9130},{6833,9165},{6839,9005},{6846,9338},{6847,9296},{6850,9275},{6852,9176},{6854,9745},{6861,9218},{6864,9292},{6865,9269},{6867,9280},{6872,9120},{6874,9641},{6875,9326},{6878,9328},{6880,9310},{6883,9810},{6886,9283},{6890,9497},{6891,9299},{6893,9334},{6894,9249},{6896,9668},{6908,9455},{6912,9113},{6915,9580},{6916,9256},{6919,9318},{6922,9385},{6927,9463},{6928,9380},{6930,9265},{6931,9242},{6935,9468},{6940,9396},{6949,9973},{6955,9459},{6960,9763},{6962,9383},{6964,9438},{6968,9560},{6973,9332},{6974,9274},{6978,9198},{6980,9713},{6985,9892},{6986,9487},{6987,9424},{6988,9393},{6991,9485},{6992,9430},{6997,9891},{6998,9379},{6999,9359},{7001,9618},{7002,9314},{7004,9477},{7010,9533},{7015,9389},{7018,9514},{7020,9645},{7021,9452},{7023,9491},{7028,9667},{7034,9710},{7037,9579},{7039,9355},{7047,9951},{7048,9914},{7049,9519},{7051,9377},{7056,9513},{7061,9451},{7065,9552},{7067,9419},{7071,9853},{7072,9793},{7073,9495},{7075,9778},{7081,9659},{7084,9545},{7087,9627},{7092,9504},{7094,9771},{7095,9518},{7100,9437},{7101,9375},{7115,9682},{7116,9531},{7120,9861},{7121,9650},{7124,9639},{7126,9555},{7128,9542},{7133,9573},{7142,9607},{7145,9623},{7150,9584},{7152,9571},{7159,9601},{7163,9726},{7164,9694},{7173,9680},{7174,9538},{7181,9616},{7184,9783},{7185,9782},{7186,9743},{7191,9781},{7192,9583},{7194,9610},{7199,9698},{7203,9848},{7210,9677},{7213,9757},{7215,9591},{7223,9598},{7228,9889},{7230,9657},{7232,9788},{7240,9935},{7241,9834},{7243,9797},{7247,9648},{7252,9697},{7264,9741},{7266,9631},{7269,9762},{7276,9730},{7278,9722},{7281,9913},{7282,9825},{7285,9857},{7286,9766},{7289,9809},{7293,9908},{7300,9693},{7302,9800},{7309,9822},{7315,9609},{7321,9829},{7324,9995},{7334,9796},{7336,9728},{7339,9907},{7344,9847},{7346,9906},{7347,9813},{7356,9832},{7358,9939},{7360,9931},{7361,9807},{7363,9924},{7376,9878},{7378,9905},{7382,9872},{7385,9958},{7392,9897},{7410,9985},{7411,9962},{7414,9886},{7421,9755},{7431,9949},{7435,9941},{7440,9876},{7458,9842},{7461,9982},{7466,9977},{7468,9968},{7500,9975},{7555,9994}B题 Ball Dropping 题目地址
题目大意：一个球卡在一个直角等腰梯形内部，求卡着的高度。
根据相似三角形，很容易能求出结果。
代码
#include<bits/stdc++.h>
using namespace std;
double r, a, b, h;
int main()
{
scanf("%lf%lf%lf%lf",&r,&a,&b,&h);
if(a<b)
{
int c=a;
a=b;
b=c;
}
if(r*2.0<=b)cout<<"Drop"<<endl;
else
{
cout<<"Stuck"<<endl;
double x=b*h/(a-b);
double l=2*r/a*sqrt((a/2)*(a/2)+(h+x)*(h+x));
double ll=l-x;
printf("%.10lf\n",ll);
}
}D题 Determine the Photo Position 题目地址
题目大意：给出一个 
的 
矩阵，要用一个 
的矩阵去覆盖一段 
，问方案数。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,a[5001][5001];
int ans;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
int num=0;
for (int j=1;j<=n;j++)
{
scanf("%1d",&a[i][j]);
if (a[i][j]==0) num++;
else num=0;
if (num>=m) ans++;
}
}
printf("%d\n",ans);
return 0;
}F题 Find 3-friendly Integers 题目地址
题目大意：定义一个自然数是 
的，如果它存在一个子串(允许前导 )是 
的倍数。多组数据，求 
- 
中的 的数的个数。
思路：
如果是三位数及以上，一定是 的。求一下一百以内的数。
代码：
#include<bits/stdc++.h>
using namespace std;
long long t,l,r;
int a[101];
long long _if(long long x)
{
if(x<=99)return a[x];
return x-99+a[99];
}
int main()
{
cin>>t;
a[0]=1;
for(int i=1;i<=9;i++)
{
a[i]=a[i-1];
if(i%3==0)
{
a[i]++;
}
}
for(int i=10;i<=99;i++)
{
a[i]=a[i-1];
if(i%3==0||i/10%3==0||i%10%3==0)
{
a[i]++;
}
}
while(t--)
{
cin>>l>>r;
cout<<_if(r)-_if(l-1)<<endl;
}
} G题 Game of Swapping Numbers 题目地址
题目大意：给定序列 
，需要交换恰好 次 
中两个不同的数，使得 每个位置的绝对差值和最大。
思路：
A B两个差的绝对值，相当于赋予两个数符号，我们可以先选出，相应位置的大数和小数，然后排序贪心，比较他们的交换贡献值。
代码：
#include<bits/stdc++.h>
using namespace std;
int a[500010],b[500010];
long long ans;
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
if(n==2)
{
while(k--)
{
int c=a[1];
a[1]=a[2];
a[2]=c;
}
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
if(a[i]>b[i])
{
int c=a[i];
a[i]=b[i];
b[i]=c;
}
ans+=b[i]-a[i];
}
sort(a+1,a+1+n);
sort(b+1,b+1+n);
for(int i=1;i<=k;i++)
{
if(i>n)break;
int t;
t=2*(a[n+1-i]-b[i]);
if(t>0)
ans+=t;
else break;
}
cout<<ans<<endl;
}I题 Increasing Subsequence 题目地址
题目大意：给出排列P，两个人轮流取数，每次取的数需要在之前该人取数的右边，且比当前取出来的所有的数都要大。所有当前可选的数都将等概率随机的被当前决策人选中。问两个人期望去数的轮数。
思路：
从后往前取（待补充）
代码：
#include<bits/stdc++.h>
using namespace std;
long long mod=998244353;
double eps=1e-7;
long long a[5010],inv[5010];
long long n;
long long qsm(long long a,long long n)
{
long long res=1;
while(n)
{
if(n&1)
res=res*a%mod;
a=a*a%mod;
n/=2;
}
return res;
}
long long f[5010][5010];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;i++)
inv[i]=qsm(i,mod-2);
for(int j=n;j>=0;j--)
{
long long cnt=0,sum=0;
for(int i=n;i>=0;i--)
{
if(a[i]>j)
{
cnt++;
sum+=f[j][a[i]];
sum%=mod;
}
else if(a[i]<j)
{
f[a[i]][j]=1;
if(!cnt)continue;
f[a[i]][j]+=sum*inv[cnt]%mod;
f[a[i]][j]%=mod;
}
}
}
long long res=0;
for(int i=1;i<=n;i++)
res=(res+f[0][i])%mod;
res=res*inv[n]%mod;
cout<<res<<endl;
return 0;
}
京公网安备 11010502036488号