来源

A - Alice and Bob （sg函数打表）

暴力打表，时间复杂度为O(n^3logN)。可以发现后手胜的状态数非常少：如果某堆石头数量是i，另一堆石头最多只有一种数量满足后手胜。

反证法：假设 (i, p) 和 (i, q) 都是后手必胜，且 q > p。那么在状态 (i, q) 时，先手可以在第二堆选 q-p 个，第一堆选 0 个，转移到后手胜的 (i, p)，说明 (i, q) 是先手胜，矛盾。

因此可以直接保存后手胜的状态到代码中提交。

#include <bits/stdc++.h>

#define endl '\n'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N) 
typedef long long ll;

using namespace std;
/*-----------------------------------------------------------------*/

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f

const int N = 3e5 + 10;
const double eps = 1e-5;

int ans[] = {3,2,7,5,12,9,15,11,20,14,22,17,32,24,33,19,35,26,38,31,40,29,52,42,53,37,58,28,60,45,62,50,65,47,68,55,70,49,75,44,79,57,86,67,87,64,92,72,99,74,101,77,110,83,113,85,116,90,118,82,123,89,126,97,127,95,129,94,136,103,145,108,146,106,156,139,160,122,161,120,164,125,166,112,174,81,177,133,180,138,182,132,186,143,190,142,195,149,197,152,198,135,199,105,203,148,215,168,218,158,224,172,228,171,229,163,232,154,236,185,239,141,241,192,246,115,253,184,256,194,259,189,264,208,266,201,268,188,271,210,274,207,278,214,280,221,281,205,286,170,289,217,298,179,301,226,305,252,306,248,307,234,309,131,313,245,315,223,317,213,321,250,322,212,325,244,327,220,332,231,339,255,340,151,346,261,350,176,358,276,359,263,362,285,367,293,370,283,372,238,375,270,379,288,386,296,390,295,391,243,408,319,411,312,415,303,432,300,435,329,445,345,446,343,449,338,454,334,456,291,461,352,464,311,467,349,470,384,474,395,478,361,479,357,483,400,485,388,487,399,489,337,494,364,496,342,501,324,505,377,509,374,511,397,518,393,520,369,521,273,525,423,527,366,529,421,530,407,531,405,532,356,537,413,541,420,545,336,549,434,553,382,556,443,557,419,558,348,560,427,565,258,568,410,570,431,574,437,577,355,580,425,586,417,588,402,590,354,596,460,600,440,601,404,603,439,610,469,614,448,620,453,624,430,632,473,635,492,639,381,646,499,648,508,649,504,651,452,653,503,658,516,660,481,661,463,664,515,666,466,671,459,673,498,683,442,691,477,693,564,697,551,702,331,711,555,716,514,719,429,722,595,723,543,726,491,735,540,737,567,740,523,744,572,748,585,752,539,760,476,761,472,766,576,768,583,771,563,772,458,776,513,778,634,780,579,785,628,787,619,788,507,799,626,800,548,805,594,810,607,811,593,818,622,822,617,825,547,827,644,828,599,831,616,836,630,842,612,845,606,849,609,855,535,857,676,866,605,869,685,870,663,871,451,876,657,877,592,879,637,883,695,886,641,892,710,893,534,896,680,899,643,904,679,910,706,912,678,917,730,918,656,920,689,924,732,929,669,935,714,937,700,944,751,946,699,948,704,956,794,957,708,964,687,969,718,976,721,982,750,985,675,986,582,989,668,991,763,995,757,996,713,1000,747,1007,743,1010,728,1013,756,1017,774,1020,754,1023,797,1029,796,1032,782,1036,742,1038,765,1040,816,1046,655,1053,833,1055,864,1061,791,1062,739,1065,746,1070,824,1072,803,1076,853,1079,808,1081,807,1082,790,1085,784,1090,793,1098,830,1102,875,1106,852,1107,682,1110,815,1117,814,1118,813,1120,848,1122,835,1130,863,1131,820,1145,859,1150,770,1156,868,1164,885,1165,839,1167,734,1175,882,1180,862,1186,890,1190,851,1192,888,1194,881,1201,838,1202,562,1206,861,1208,906,1211,902,1212,874,1214,915,1219,943,1225,847,1227,898,1231,909,1241,844,1243,927,1245,914,1248,973,1254,954,1261,908,1265,950,1268,940,1269,923,1274,931,1279,967,1284,978,1285,895,1292,1027,1295,963,1297,960,1302,972,1307,933,1311,959,1314,952,1317,984,1322,841,1329,994,1331,1051,1334,1043,1336,1002,1337,971,1346,1006,1348,981,1358,725,1361,1012,1363,926,1366,1009,1371,1035,1372,999,1376,1025,1378,993,1381,942,1384,873,1387,1045,1389,1034,1390,966,1394,922,1397,1089,1400,1005,1403,1144,1405,939,1408,1060,1413,1069,1414,1058,1419,1019,1420,962,1425,1100,1428,1078,1432,1016,1438,1140,1443,1096,1446,1064,1449,1125,1451,988,1455,1094,1457,1088,1458,1048,1461,1004,1464,1104,1465,1015,1468,1092,1470,1143,1477,1022,1481,1109,1484,1116,1491,1174,1492,1075,1499,1087,1502,1137,1509,1134,1510,1124,1514,1074,1516,1129,1521,1068,1525,1161,1527,1042,1529,1159,1532,1136,1534,1155,1536,1153,1537,1139,1539,1113,1541,1152,1543,1067,1547,980,1560,1183,1561,1169,1563,1142,1569,1158,1575,1133,1577,1178,1580,1239,1581,1149,1590,1197,1592,1163,1599,598,1605,1247,1606,1112,1611,1188,1612,1171,1617,1229,1619,1173,1622,1238,1625,1217,1626,1127,1633,1031,1636,1200,1640,1221,1643,1237,1651,1236,1653,1199,1661,1258,1664,1283,1665,1185,1674,1148,1678,1235,1679,1204,1682,1281,1684,1290,1687,1084,1692,1278,1694,1276,1695,1057,1702,1289,1707,1272,1708,1260,1710,1301,1713,1264,1717,1224,1721,1253,1729,1327,1730,1233,1736,1216,1746,1251,1754,1320,1756,1300,1758,1115,1762,1357,1765,1305,1767,1316,1769,1263,1772,1418,1774,1310,1777,802,1782,1344,1785,1340,1787,1325,1795,1267,1799,1257,1802,1343,1811,1319,1812,998,1820,1250,1822,1339,1824,1380,1825,1304,1831,1354,1832,1309,1837,1430,1838,1360,1842,1352,1845,1299,1847,1416,1850,1342,1854,759,1859,1370,1863,1392,1866,1294,1869,1442,1877,1410,1878,1369,1879,1365,1882,1287,1884,1368,1888,1356,1901,1396,1904,1386,1906,1196,1914,1407,1919,1383,1922,1475,1923,1437,1929,1223,1935,1422,1941,1480,1942,1472,1947,1460,1949,1448,1953,1436,1964,1495,1966,1402,1970,1505,1972,1520,1975,1434,1978,1399,1981,1508,1986,1504,1992,1494,1994,1441,1997,1497,2001,1571,2003,1507,2004,1271,2007,1453,2011,1463,2018,901,2026,1487,2029,1555,2030,1490,2031,1479,2033,1554,2036,1375,2040,1424,2042,1412,2050,1566,2051,1440,2056,1546,2059,1524,2067,1565,2070,1551,2076,1531,2077,1177,2080,1589,2085,1597,2088,1513,2094,1550,2096,1518,2098,1501,2100,1588,2103,1579,2105,1568,2107,1489,2116,1557,2129,1553,2132,1704,2134,1483,2137,1587,2140,1333,2142,1604,2145,1630,2148,1586,2152,1603,2161,1574,2163,1741,2168,1594,2174,1670,2176,1616,2180,1584,2182,1657,2184,1621,2191,1512,2193,1663,2194,1628,2195,1601,2198,1614,2202,1673,2203,1610,2205,1474,2209,1445,2215,1256,2217,1659,2222,1691,2224,1642,2229,1638,2230,1467,2234,1701,2237,1690,2239,1650,2246,1712,2254,1751,2255,1648,2256,1573,2261,1700,2268,1699,2271,1681,2276,1647,2281,1609,2283,1728,2287,1706,2288,1351,2293,1672,2297,1698,2298,1646,2302,1635,2310,1655,2317,1761,2318,1745,2322,1724,2329,1608,2332,1805,2335,1726,2338,1583,2341,1719,2345,1753,2347,1676,2350,1744,2356,1669,2358,1790,2362,1743,2365,1814,2366,1668,2368,1723,2369,1050,2375,1798,2376,1732,2381,1776,2385,1781,2388,1324,2390,1545,2393,1792,2395,1873,2398,1818,2400,1817,2402,1789,2404,1794,2406,1764,2411,1780,2415,1830,2420,1808,2421,1549,2426,1760,2427,1738,2435,1807,2437,1689,2439,1716,2444,1858,2449,1784,2453,1749,2455,1210,2459,1835,2462,1891,2469,1828,2473,1810,2485,1849,2490,1740,2492,1927,2493,1844,2495,1735,2502,1876,2505,1871,2509,1909,2511,1897,2513,1865,2515,1900,2516,1804,2523,1841,2525,1890,2530,1913,2538,1771,2546,1989,2548,1940,2549,1926,2550,1925,2551,1857,2556,2013,2557,1779,2564,1911,2567,1903,2570,1938,2572,1894,2575,1917,2576,1881,2592,1916,2597,1937,2600,1899,2604,1147,2607,1715,2611,1974,2613,1862,2616,1959,2623,1182,2627,2039,2632,1958,2634,1834,2640,1667,2642,1934,2645,1983,2647,1956,2657,1486,2661,1944,2665,1933,2668,2048,2669,1624,2671,2025,2673,1977,2675,1955,2682,2009,2684,2016,2687,1988,2689,1952,2691,1969,2700,1932,2702,2021,2704,1999,2707,1991,2708,1921,2709,1896,2720,1856,2729,2015,2733,2058,2738,1985,2743,1893,2746,2092,2747,2055,2749,2047,2751,1840,2754,2066,2758,2111,2759,2062,2761,1963,2768,2091,2773,1886,2778,2128,2779,2023,2780,1996,2785,2045,2788,2119,2789,1951,2792,2165,2798,2087,2804,2114,2806,2064,2809,2074,2810,1313,2814,2158,2816,2072,2826,2126,2830,1875,2832,2038,2834,2125,2836,1374,2840,1350,2843,2173,2846,2187,2850,2079,2856,2084,2862,2155,2864,2110,2869,2151,2873,2170,2879,1852,2881,2147,2882,2139,2883,2113,2891,2102,2899,2124,2902,2069,2905,2212,2910,1797,2915,2200,2917,2179,2919,2160,2921,2122,2925,2121,2927,2178,2931,1961,2938,2020,2943,2167,2946,2219,2953,1968,2954,1645,2956,2090,2957,1827,2960,2236,2970,2154,2972,2233,2974,2244,2979,2260,2981,1427,2985,2189,2986,1980,2993,2265,2997,2228,3001,2249,3004,2275,3006,2270,3007,2242,3012,2328,3015,2227,3020,2172,3024,2214,3026,2253,3031,2285,3032,2274,3036,2208,3037,2061,3039,2150,3046,2267,3048,2028,3057,2295,3061,2241,3064,2232,3067,2207,3078,2006,3082,2321,3084,2301,3089,2252,3097,2280,3099,2259,3101,2354,3103,2417,3106,2380,3110,2258,3113,2331,3116,2431,3117,2324,3118,2312,3119,2248,3121,2044,3125,2306,3128,2316,3130,2308,3138,2109,3145,2344,3148,2251,3156,1748,3159,1559,3163,2305,3169,2384,3172,2290,3177,2374,3179,2413,3182,2392,3190,2409,3193,2300,3197,2353,3201,2383,3202,2334,3206,2465,3207,2083,3213,2379,3217,2361,3218,2320,3225,2434,3229,2226,3232,2452,3235,1734,3241,2561,3244,2197,3246,2472,3247,2373,3250,2326,3252,1801,3254,2082,3258,2423,3261,2221,3269,2446,3273,1861,3281,2451,3286,2484,3287,2479,3289,2372,3294,2489,3297,2488,3299,2475,3302,2443,3303,1523,3312,2587,3314,2387,3317,2442,3323,2537,3325,2499,3327,2441,3333,2292,3334,2131,3335,1686,3338,2273,3341,2433,3343,2586,3345,2482,3350,2521,3351,2457,3355,2508,3358,2507,3359,2408,3367,2654,3368,2529,3372,2595,3374,2520,3377,2582,3379,2533,3381,2519,3384,2501,3385,1596,3391,2555,3393,2429,3395,2554,3396,2343,3405,2544,3409,2594,3412,2532,3413,2467,3418,2626,3422,2569,3423,2360,3425,2314,3433,2263,3441,2518,3449,2652,3454,2581,3459,2580,3460,2304,3463,2638,3464,2609,3466,2599,3467,2579,3471,2527,3475,2585,3478,2186,3480,2637,3488,2543,3495,2498,3498,2487,3500,2481,3502,2566,3506,2664,3508,2630,3510,2563,3512,2419,3518,2606,3519,2352,3525,2621,3529,2680,3534,2535,3536,2578,3538,2560,3544,2542,3547,2651,3549,2718,3552,2461,3558,2602,3560,1632,3565,2696,3569,2659,3570,2340,3578,2629,3584,2656,3585,2371,3589,2279,3592,2559,3598,2478,3600,2723,3601,2620,3605,2619,3614,2694,3619,2712,3621,2644,3628,2618,3635,2726,3638,2699,3640,2706,3643,2717,3647,2742,3651,2737,3656,2791,3658,2679,3665,2715,3667,2636,3671,2650,3673,2757,3676,2741,3681,2782,3684,2584,3689,2736,3693,2541,3698,2765,3699,2574,3704,2802,3705,2775,3709,2771,3712,1816,3714,2795,3719,2756,3720,2678,3722,2590,3724,2829,3727,2732,3731,2378,3733,2801,3737,2867,3739,2625,3743,2818,3748,2677,3756,2825,3759,2735,3762,2800,3763,2349,3767,2876,3769,2808,3771,2823,3772,2667,3776,2861,3777,2855,3781,2860,3787,2813,3793,2839,3795,2968,3798,2941,3801,2898,3809,2866,3810,2397,3811,2144,3814,2728,3821,3076,3822,2909,3824,2853,3825,2767,3832,2740,3835,2895,3838,2540,3841,2940,3844,2698,3848,2812,3852,2731,3854,2820,3859,975,3862,2794,3864,2477,3872,2930,3877,3066,3880,2889,3882,2859,3886,2849,3888,2845,3890,2784,3896,2967,3898,2745,3900,2886,3907,2875,3908,2211,3914,3030,3916,2912,3917,2753,3921,2964,3923,2936,3924,2553,3927,2929,3932,2848,3935,2907,3941,2504,3944,2950,3948,2948,3952,3011,3955,2858,3957,2797,3961,3055,3965,2996,3966,2978,3971,2914,3974,2770,3977,2711,3982,2977,3991,1868,3995,2901,3998,2983,3999,2838,4010,3017,4011,2893,4012,2777,4016,3051,4017,3010,4018,2693,4026,3150,4027,2952,4030,1931,4033,3081,4037,3019,4038,2364,4044,2878,4049,3060,4051,3043,4052,2763,4055,2157,4057,3074,4060,3000,4068,3187,4070,3035,4074,2995,4075,2828,4079,1908,4081,2991,4082,2966,4089,2649,4097,3053,4100,3087,4103,3023,4107,3034,4109,2924,4111,3041,4119,3123,4120,3094,4121,2990,4125,2615,4128,3045,4135,2934,4138,2959,4140,3086,4141,3029,4146,3137,4150,3072,4151,2976,4152,2945,4154,2497,4160,2963,4162,2714,4165,3280,4169,3153,4172,3212,4173,3127,4176,3028,4181,3542,4182,3165,4184,3133,4186,2872,4192,2933,4195,3136,4197,2923,4199,2962,4209,3147,4210,3143,4219,3093,4222,3115,4223,3096,4231,2989,4234,3092,4237,3009,4240,2448,4243,3158,4247,3195,4249,3050,4253,3152,4261,3211,4262,3140,4263,3080,4270,3278,4271,3175,4272,3162,4277,3216,4278,3069,4288,3320,4290,3265,4291,3189,4296,3192,4298,3331,4300,3181,4302,3003,4305,3239,4307,3204,4310,3272,4314,3215,4317,3337,4319,3221,4324,3105,4330,3063,4336,2904,4338,3209,4341,3285,4343,3220,4345,3257,4348,3199,4356,3275,4361,3168,4363,2999,4372,3400,4373,3234,4375,3237,4383,3361,4384,3310,4390,2871,4395,3184,4398,3432,4399,3387,4416,3329,4425,3231,4428,3607,4429,3132,4434,3404,4437,3453,4438,3383,4442,3309,4443,3014,4446,3228,4447,3091,4449,3108,4452,3308,4453,3306,4454,3249,4466,3316,4468,3399,4471,3256,4473,3293,4478,3430,4479,2725,4487,3438,4489,3407,4493,3291,4495,3227,4503,3112,4506,3224,4507,2425,4511,3322,4519,3357,4522,3364,4523,3349,4525,3366,4526,3283,4528,3243,4532,3398,4539,3277,4543,3171,4546,3296,4547,3268,4549,3271,4550,2852,4552,3371,4559,3402,4563,3167,4567,3452,4571,3443,4572,1697,4578,3469,4579,3411,4581,3264,4586,3596,4593,2035,4595,3458,4599,3448,4601,3436,4605,3429,4608,2787,4610,3260,4619,2663,4621,3486,4622,3390,4628,3483,4631,3421,4635,3348,4644,3568,4650,3370,4652,3613,4657,3521,4660,3482,4663,3347,4670,3447,4674,3492,4675,3446,4678,3301,4681,3497,4683,3174,4690,3435,4691,3428,4700,3059,4705,3562,4706,2118,4708,3477,4712,3440,4717,3491,4722,3532,4725,3417,4732,3750,4733,3485,4740,3577,4742,3515,4744,3354,4745,2842,4751,3517,4761,3528,4763,3524,4765,3625,4768,3580,4771,3663,4772,3595,4773,3551,4775,3686,4778,3583,4779,2988,4782,2897,4786,3574,4789,3540,4801,3609,4803,3457,4805,2053,4807,3634,4809,3494,4810,3415,4814,3645,4815,2722,4818,3594,4821,3623,4832,3557,4836,3514,4839,3603,4845,3637,4847,3505,4850,3555,4856,3474,4865,3669,4871,3617,4876,3527,4878,3662,4882,3490,4888,3675,4889,3612,4892,3473,4897,3427,4903,3717,4907,3655,4914,3389,4921,3576,4926,3633,4928,3591,4932,3726,4935,3631,4939,3616,4941,3567,4945,3462,4948,3692,4953,3753,4956,3680,4959,3654,4967,3588,4969,3531,4972,3661,4977,3642,4979,3582,4992,3223,5000,3742};

typedef pair<int, int> PII;

set<PII> ex;

int main() {
    IOS;
    int n = sizeof(ans) / sizeof(int);
    ex.insert({0, 0});
    for(int i = 0; i < n; i += 2) {
        ex.insert({ans[i], ans[i + 1]});
    }
    int t;
    cin >> t;
    while(t--) {
        int n, m;
        cin >> n >> m;
        if(n < m) swap(n, m);
        if(ex.count({n, m})) cout << "Bob" << endl;
        else cout << "Alice" << endl;
    }
}

K - Knowledge Test about Match （乱搞）

由sqrt(x)的性质，随着x的增加，sqrt(x)增长得越慢。因此a和b数组之间差值越小越好。

从0开始递增枚举差值d，每次暴力找到差值为d的数对填入答案即可。

#include <bits/stdc++.h>
 
#define endl '\n'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
 
using namespace std;
/*-----------------------------------------------------------------*/
 
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
 
const int N = 3e5 + 10;
const double eps = 1e-5;
int visp[N];
int arr[N];
int vis[N];
int ans[N];
 
int main() {
    IOS;
    int t;
    cin >> t;
    while(t--) {
        memset(vis, 0, sizeof vis);
        memset(visp, 0, sizeof visp);
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        sort(arr, arr + n);
        int cnt = 0;
        for(int d = 0; cnt < n ; d++) {
            for(int i = 0; i < n; i++) {
                if(visp[i]) continue;
                int v = arr[i];
                if(v - d >= 0 && !vis[v - d]) {
                    ans[v - d] = v;
                    vis[v - d] = 1;
                    visp[i] = 1;
                    cnt++;
                } else if(v + d < n && !vis[v + d]) {
                    ans[v + d] = v;
                    vis[v + d] = 1;
                    visp[i] = 1;
                    cnt++;
                }
            }
        }
        for(int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
    }
}