2021 暑期牛客高校训练赛一

本文最后更新于：2021年8月19日 晚上 

第一场多校，感觉打的海星，不过赛后出题人说这场比赛是区域赛难度减的，所以实际上做的还是布行QAQ

比赛过程

比赛开始前提醒我的队友要去比赛，我们队原本是三个人的，但是由于林荫同学要去复读，所以现在只有两个人了。
比赛刚好赶上中午. . . 开赛半小时外卖来了就只能边吃饭边打. . .
不过队友签到十分快，所以实际上也没怎么耽误。
我便吃饭边看F，感觉这种数位方面的东西可能会有规律于是试了试打表，然后发现100以上的n全都是n-24的答案，便交了下，但是挂了. . .然后就发现自己又犯傻逼错误，用前缀求区间$[l,r]$的和是$a[r]-a[l-1]$但我却写的是$a[r]-a[l]$。改了错误后就A了。队友此时推了B但是他没推出来，所以我让他先看其他题我来推。其实也不算难推但是对精度处理好像有丶要求，不能做过多的浮点运算否则会有比较大的精度误差（我又因为这种sb错误wa了），最后改了下公式换成了long double过了。队友此时觉得A和H都可做，不过他交了发H结果T了，然后我去看了下H，队友去看J。H是一道很妙的题，队友交的是纯暴力，由于n和a的范围都是50W，所以我觉得剪枝暴力没准可以过，由于每两个数的差必成为公共模因，所以我们把每两个数之间的差枚举出来就能得到正确答案，由于n和a的范围相同，所以在大数据的情况下相邻两数的差必然十分小并且大多相同，因此我用最大的数减去最小的数，第二大的数减去第二小的数. .. 这样能保证每次得到的差大概率是不同的，并且由于跨度大可以直接减少一般复杂度并且十分平均（差的范围分布比较平均，假如数据随机（实际上大数据必然会导致这个现象，大数据的数分布是必然随机的）），然后以此为优化交上去A了。
看了眼提交，队友还在鏖战J，于是转向A，A的博弈用sg推了一遍后开始打表，先打了个100以内的表发现必败点十分稀疏，由此改变了算法打5k以内的表（不过好像还是哪里写挂了跑了一个半小时才出来），表打出来后就剩下10min了，我马不停蹄打了个程序交了上去，万幸，一遍过了。

总结

这场比赛感觉实际上正解都是些没学过的高级思路，但是由于一些性质导致我可以用奇怪的方式水过去（骗分奇迹）。五道题其中一道签到是队友打的不计，剩下四道一道是计算题（签到），一道我用暴力+优化的方式过了（不过我觉得我的优化由于数据范围的性质可以优化很多，不过不会证明），一道打表找规律（正解是数学证明鸽巢原理），一道还是打表（正解也是用函数的性质+sg推）。还是和鲸头鹳说的一样，老乱搞选手了（技能点的十分奇怪）

题目详情

(补题啊，记得啊！！)

A

Alice and Bob like playing games. There are two piles of stones with numbers n and m. Alice and Bob take turns to operate, each operation can take away k(k>0) stones from one pile and take away s×k(s≥0) stones from another pile. Alice plays first. The person who cannot perform the operation loses the game.

Please determine who will win the game if both Alice and Bob play the game optimally.
输入描述:
The first line contains an integer T denotes the total number of test cases.
Each test case contains two integers n,min a line, indicating the number of two piles of stones.
输出描述:
For each test case, print “Alice” if Alice will win the game, otherwise print “Bob”.

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

B

A standard sphere ball is falling in the air, and the center of the sphere is exactly on the centerline of an empty isosceles trapezoidal. The trapezoid is hanging horizontally under the sphere.
Please determine whether the ball will get stuck in the trapezoid or drop past the trapezoid.

输入描述:
The input contains four integers r, a, b, h, indicating the radius of the ball, the top base, the bottom base, and the height of the isosceles trapezoid.
It is guaranteed that
输出描述:
Output ‘Drop’ if the sphere ball will drop past the empty trapezoid, otherwise output ‘Stuck’.
If the answer is ‘Stuck’, please also calculate the stuck position(the height between the center of the sphere and the midpoint of the bottom base). Your answer is considered correct if its absolute or relative error does not exceed 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int n,maxx=-1,minn=500010;
double r,a,b,h;
double ans=0.0;
int main()
{
    cin>>r>>a>>b>>h;
    if(r*2<=b&&r*2<=a)
    {
        cout<<"Drop"<<endl;
        return 0;
    }
    a/=2;
    b/=2;
    long double x=(double)(h*b)/((double)a-b);
    long double kl=sqrt(b*b+x*x);
    ans= r*kl/(double)b-x;
    cout<<"Stuck"<<endl;
    printf("%0.12lf\n",ans);
    return 0;
}

D

You have taken the graduation picture of graduates. The picture could be regarded as a matrix A of , each element in A is 0 or 1, representing a blank background or a student, respectively.
However, teachers are too busy to take photos with students and only took a group photo themselves. The photo could be regarded as a matrix B of where each element is 2 representing a teacher.

As a master of photoshop, your job is to put photo B into photo A with the following constraints:
you are not allowed to split, rotate or scale the picture, but only translation.
each element in matrix B should overlap with an element in A completely, and each teacher should overlap with a blank background, not shelter from a student.

Please calculate the possible ways that you can put photo B into photo A.

输入描述:
The first line contains two integers n,m indicating the size of photos A and B.
In the next $n$ lines,each line contains {n}n characters of ‘0’ or ‘1’,representing the matrix A.
The last line contains {m}m characters of ‘2’, representing matrix B.
输出描述:
Output one integer in a line, indicating the answer.

签到题，没啥可说的

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
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
string s[2010],b;
int n,m;
int ans=0;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) cin>>s[i];
    cin>>b;
    int lastplace;
    for(int i=1;i<=n;i++){
        lastplace=n+1;
        for(int j=0;j<n;j++){
            if(s[i][j]=='0'&&(s[i][j-1]=='1'||j==0)){
                lastplace=j-1;
            }
            if(s[i][j]=='0'){
                if(j-lastplace>=m) ans++;
            }
            else lastplace=n+1;
        }
    }
    cout<<ans;
    return 0;
}

F

A positive integer is 3-friendly if and only if we can find a continuous substring in its decimal representation, and the decimal integer represented by the substring is a multiple of 3.

For instance:
1. is 3-friendly because “0” is a substring of “104” and .
2. is 3-friendly because “12” is a substring of “124” and . “24” is also a valid substring.
3. is not 3-friendly because
Note that the substring with leading zeros is also considered legal.

Given two integers and , you are asked to tell the number of positive integers such that and is 3-friendly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int n,a[500010]={0,0,0,1,1,1,2,2,2,3,4,4,5,6,6,7,8,8,9,10,11,12,12,13,14,14,15,16,16,17,18,19,20,21,22,23,24,25,26,27,28,28,29,30,30,31,32,32,33,34,35,36,36,37,38,38,39,40,40,41,42,43,44,45,46,47,48,49,50,51,52,52,53,54,54,55,56,56,57,58,59,60,60,61,62,62,63,64,64,65,66,67,68,69,70,71,72,73,74,75,76},b[500010],maxx=-1,minn=500010;
int main()
{
    long long T,ll,rr;
    cin>>T;
    while(T--)
    {
        scanf("%lld%lld",&ll,&rr);
        if(ll<=100)ll=a[ll-1];
        else ll-=25;
        if(rr<=100)rr=a[rr];
        else rr-=24;
        printf("%lld\n",rr-ll);
    }
    return 0;
}

H

For a given set , we called a hash function perfect hash function of S, if it satisfies
Given a set S with non-negative integers, please find the minimum positive integer seed that function is a perfect hash function of S.

Note: Six more test cases are added after contest.
输入描述:
The first line of input contains one integer $n$, describing the size of set S.
The second line contains integers , describing the elements in S.
It is guaranteed that
输出描述:
Output one integer in a line, indicating the answer.

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
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
int a[500010],b[500010],c[500010]={};
int cont[500010];
int n;
int maxi,mini;
int main()
{
    cin>>n;
    mini=n;
    for(int i=0;i<n;++i)scanf("%d",&a[i]);
    sort(a,a+n);
	int kl=n/2;
	for(int i=n,jk;i>=kl+1;i--)
	{
		jk=max(0,n-i-100);
		for(int j=n-i;j>=jk;j--)
			c[a[i]-a[j]]=1;
	}
    maxi=a[n-1]-a[0]+1;
    bool bl=0;
    for(int j=mini;j<maxi;++j)
	{
		if(c[j]==1)continue;
        memset(cont,0,sizeof(cont));
        bl=0;
        for(int i=0;i<n;++i)
		{
            cont[a[i]%j]++;
            if(cont[a[i]%j]>1){
                bl=1;
                break;
            }
        }
        if(bl==0){
            cout<<j;
            return 0;
        }
    }
    cout<<maxi;
    return 0;
}
2021 比赛 暑期牛客高校训练赛
大学 牛客 icpc

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！