打表求调
查看原帖
打表求调
666114
BWsha2k楼主2024/10/24 10:17

#2 #8 WA

#include<iostream>
#include<cmath>
#define int long long
using namespace std;

const int MAXN = 2e5+66;
int ans[MAXN];
int a, b, cnt = 0;

void init()
{
ans[0] = 202173;
ans[1] = 136131,ans[2] = 138503,ans[3] = 138214,ans[4] = 138252,ans[5] = 138252;
ans[6] = 138214,ans[7] = 138503,ans[8] = 136131,ans[9] = 155315,ans[13] = 138214,ans[14] = 138252,ans[15] = 138252;
ans[16] = 138214,ans[17] = 138503,ans[18] = 136131,ans[19] = 155315,ans[20] = 155315;
ans[24] = 138252,ans[25] = 138252;
ans[26] = 138214,ans[27] = 138503,ans[28] = 136131,ans[29] = 155315,ans[30] = 155315;
ans[31] = 136131,ans[35] = 138252;
ans[36] = 138214,ans[37] = 138503,ans[38] = 136131,ans[39] = 155315,ans[40] = 155315;
ans[41] = 136131,ans[42] = 138503,ans[46] = 138214,ans[47] = 138503,ans[48] = 136131,ans[49] = 155315,ans[50] = 155315;
ans[51] = 136131,ans[52] = 138503,ans[53] = 138214,ans[57] = 138503,ans[58] = 136131,ans[59] = 155315,ans[60] = 155315;
ans[61] = 136131,ans[62] = 138503,ans[63] = 138214,ans[64] = 138252,ans[68] = 136131,ans[69] = 155315,ans[70] = 155315;
ans[71] = 136131,ans[72] = 138503,ans[73] = 138214,ans[74] = 138252,ans[75] = 138252;
ans[79] = 155315,ans[80] = 155315;
ans[81] = 136131,ans[82] = 138503,ans[83] = 138214,ans[84] = 138252,ans[85] = 138252;
ans[86] = 138214,ans[90] = 155315;
ans[91] = 136131,ans[92] = 138503,ans[93] = 138214,ans[94] = 138252,ans[95] = 138252;
ans[96] = 138214,ans[97] = 138503,ans[130] = 155315;
ans[131] = 136131,ans[135] = 138252;
ans[136] = 138214,ans[137] = 138503,ans[138] = 136131,ans[139] = 155315,ans[140] = 155315;
ans[141] = 136131,ans[142] = 138503,ans[146] = 138214,ans[147] = 138503,ans[148] = 136131,ans[149] = 155315,ans[150] = 155315;
ans[151] = 136131,ans[152] = 138503,ans[153] = 138214,ans[157] = 138503,ans[158] = 136131,ans[159] = 155315,ans[160] = 155315;
ans[161] = 136131,ans[162] = 138503,ans[163] = 138214,ans[164] = 138252,ans[168] = 136131,ans[169] = 155315,ans[170] = 155315;
ans[171] = 136131,ans[172] = 138503,ans[173] = 138214,ans[174] = 138252,ans[175] = 138252;
ans[179] = 155315,ans[180] = 155315;
ans[181] = 136131,ans[182] = 138503,ans[183] = 138214,ans[184] = 138252,ans[185] = 138252;
ans[186] = 138214,ans[190] = 155315;
ans[191] = 136131,ans[192] = 138503,ans[193] = 138214,ans[194] = 138252,ans[195] = 138252;
ans[196] = 138214,ans[197] = 138503,ans[202] = 138503,ans[203] = 138214,ans[204] = 138252,ans[205] = 138252;
ans[206] = 138214,ans[207] = 138503,ans[208] = 136131,ans[209] = 155315,ans[240] = 155315;
ans[241] = 136131,ans[242] = 138503,ans[246] = 138214,ans[247] = 138503,ans[248] = 136131,ans[249] = 155315,ans[250] = 155315;
ans[251] = 136131,ans[252] = 138503,ans[253] = 138214,ans[257] = 138503,ans[258] = 136131,ans[259] = 155315,ans[260] = 155315;
ans[261] = 136131,ans[262] = 138503,ans[263] = 138214,ans[264] = 138252,ans[268] = 136131,ans[269] = 155315,ans[270] = 155315;
ans[271] = 136131,ans[272] = 138503,ans[273] = 138214,ans[274] = 138252,ans[275] = 138252;
ans[279] = 155315,ans[280] = 155315;
ans[281] = 136131,ans[282] = 138503,ans[283] = 138214,ans[284] = 138252,ans[285] = 138252;
ans[286] = 138214,ans[290] = 155315;
ans[291] = 136131,ans[292] = 138503,ans[293] = 138214,ans[294] = 138252,ans[295] = 138252;
ans[296] = 138214,ans[297] = 138503,ans[302] = 138503,ans[303] = 138214,ans[304] = 138252,ans[305] = 138252;
ans[306] = 138214,ans[307] = 138503,ans[308] = 136131,ans[309] = 155315,ans[313] = 138214,ans[314] = 138252,ans[315] = 138252;
ans[316] = 138214,ans[317] = 138503,ans[318] = 136131,ans[319] = 155315,ans[350] = 155315;
ans[351] = 136131,ans[352] = 138503,ans[353] = 138214,ans[357] = 138503,ans[358] = 136131,ans[359] = 155315,ans[360] = 155315;
ans[361] = 136131,ans[362] = 138503,ans[363] = 138214,ans[364] = 138252,ans[368] = 136131,ans[369] = 155315,ans[370] = 155315;
ans[371] = 136131,ans[372] = 138503,ans[373] = 138214,ans[374] = 138252,ans[375] = 138252;
ans[379] = 155315,ans[380] = 155315;
ans[381] = 136131,ans[382] = 138503,ans[383] = 138214,ans[384] = 138252,ans[385] = 138252;
ans[386] = 138214,ans[390] = 155315;
ans[391] = 136131,ans[392] = 138503,ans[393] = 138214,ans[394] = 138252,ans[395] = 138252;
ans[396] = 138214,ans[397] = 138503,ans[402] = 138503,ans[403] = 138214,ans[404] = 138252,ans[405] = 138252;
ans[406] = 138214,ans[407] = 138503,ans[408] = 136131,ans[409] = 155315,ans[413] = 138214,ans[414] = 138252,ans[415] = 138252;
ans[416] = 138214,ans[417] = 138503,ans[418] = 136131,ans[419] = 155315,ans[420] = 155315;
ans[424] = 138252,ans[425] = 138252;
ans[426] = 138214,ans[427] = 138503,ans[428] = 136131,ans[429] = 155315,ans[460] = 155315;
ans[461] = 136131,ans[462] = 138503,ans[463] = 138214,ans[464] = 138252,ans[468] = 136131,ans[469] = 155315,ans[470] = 155315;
ans[471] = 136131,ans[472] = 138503,ans[473] = 138214,ans[474] = 138252,ans[475] = 138252;
ans[479] = 155315,ans[480] = 155315;
ans[481] = 136131,ans[482] = 138503,ans[483] = 138214,ans[484] = 138252,ans[485] = 138252;
ans[486] = 138214,ans[490] = 155315;
ans[491] = 136131,ans[492] = 138503,ans[493] = 138214,ans[494] = 138252,ans[495] = 138252;
ans[496] = 138214,ans[497] = 138503,ans[502] = 138503,ans[503] = 138214,ans[504] = 138252,ans[505] = 138252;
ans[506] = 138214,ans[507] = 138503,ans[508] = 136131,ans[509] = 155315,ans[513] = 138214,ans[514] = 138252,ans[515] = 138252;
ans[516] = 138214,ans[517] = 138503,ans[518] = 136131,ans[519] = 155315,ans[520] = 155315;
ans[524] = 138252,ans[525] = 138252;
ans[526] = 138214,ans[527] = 138503,ans[528] = 136131,ans[529] = 155315,ans[530] = 155315;
ans[531] = 136131,ans[535] = 138252;
ans[536] = 138214,ans[537] = 138503,ans[538] = 136131,ans[539] = 155315,ans[570] = 155315;
ans[571] = 136131,ans[572] = 138503,ans[573] = 138214,ans[574] = 138252,ans[575] = 138252;
ans[579] = 155315,ans[580] = 155315;
ans[581] = 136131,ans[582] = 138503,ans[583] = 138214,ans[584] = 138252,ans[585] = 138252;
ans[586] = 138214,ans[590] = 155315;
ans[591] = 136131,ans[592] = 138503,ans[593] = 138214,ans[594] = 138252,ans[595] = 138252;
ans[596] = 138214,ans[597] = 138503,ans[602] = 138503,ans[603] = 138214,ans[604] = 138252,ans[605] = 138252;
ans[606] = 138214,ans[607] = 138503,ans[608] = 136131,ans[609] = 155315,ans[613] = 138214,ans[614] = 138252,ans[615] = 138252;
ans[616] = 138214,ans[617] = 138503,ans[618] = 136131,ans[619] = 155315,ans[620] = 155315;
ans[624] = 138252,ans[625] = 138252;
ans[626] = 138214,ans[627] = 138503,ans[628] = 136131,ans[629] = 155315,ans[630] = 155315;
ans[631] = 136131,ans[635] = 138252;
ans[636] = 138214,ans[637] = 138503,ans[638] = 136131,ans[639] = 155315,ans[640] = 155315;
ans[641] = 136131,ans[642] = 138503,ans[646] = 138214,ans[647] = 138503,ans[648] = 136131,ans[649] = 155315,ans[680] = 155315;
ans[681] = 136131,ans[682] = 138503,ans[683] = 138214,ans[684] = 138252,ans[685] = 138252;
ans[686] = 138214,ans[690] = 155315;
ans[691] = 136131,ans[692] = 138503,ans[693] = 138214,ans[694] = 138252,ans[695] = 138252;
ans[696] = 138214,ans[697] = 138503,ans[702] = 138503,ans[703] = 138214,ans[704] = 138252,ans[705] = 138252;
ans[706] = 138214,ans[707] = 138503,ans[708] = 136131,ans[709] = 155315,ans[713] = 138214,ans[714] = 138252,ans[715] = 138252;
ans[716] = 138214,ans[717] = 138503,ans[718] = 136131,ans[719] = 155315,ans[720] = 155315;
ans[724] = 138252,ans[725] = 138252;
ans[726] = 138214,ans[727] = 138503,ans[728] = 136131,ans[729] = 155315,ans[730] = 155315;
ans[731] = 136131,ans[735] = 138252;
ans[736] = 138214,ans[737] = 138503,ans[738] = 136131,ans[739] = 155315,ans[740] = 155315;
ans[741] = 136131,ans[742] = 138503,ans[746] = 138214,ans[747] = 138503,ans[748] = 136131,ans[749] = 155315,ans[750] = 155315;
ans[751] = 136131,ans[752] = 138503,ans[753] = 138214,ans[757] = 138503,ans[758] = 136131,ans[759] = 155315,ans[790] = 155315;
ans[791] = 136131,ans[792] = 138503,ans[793] = 138214,ans[794] = 138252,ans[795] = 138252;
ans[796] = 138214,ans[797] = 138503,ans[802] = 138503,ans[803] = 138214,ans[804] = 138252,ans[805] = 138252;
ans[806] = 138214,ans[807] = 138503,ans[808] = 136131,ans[809] = 155315,ans[813] = 138214,ans[814] = 138252,ans[815] = 138252;
ans[816] = 138214,ans[817] = 138503,ans[818] = 136131,ans[819] = 155315,ans[820] = 155315;
ans[824] = 138252,ans[825] = 138252;
ans[826] = 138214,ans[827] = 138503,ans[828] = 136131,ans[829] = 155315,ans[830] = 155315;
ans[831] = 136131,ans[835] = 138252;
ans[836] = 138214,ans[837] = 138503,ans[838] = 136131,ans[839] = 155315,ans[840] = 155315;
ans[841] = 136131,ans[842] = 138503,ans[846] = 138214,ans[847] = 138503,ans[848] = 136131,ans[849] = 155315,ans[850] = 155315;
ans[851] = 136131,ans[852] = 138503,ans[853] = 138214,ans[857] = 138503,ans[858] = 136131,ans[859] = 155315,ans[860] = 155315;
ans[861] = 136131,ans[862] = 138503,ans[863] = 138214,ans[864] = 138252,ans[868] = 136131,ans[869] = 155315,ans[902] = 138503,ans[903] = 138214,ans[904] = 138252,ans[905] = 138252;
ans[906] = 138214,ans[907] = 138503,ans[908] = 136131,ans[909] = 155315,ans[913] = 138214,ans[914] = 138252,ans[915] = 138252;
ans[916] = 138214,ans[917] = 138503,ans[918] = 136131,ans[919] = 155315,ans[920] = 155315;
ans[924] = 138252,ans[925] = 138252;
ans[926] = 138214,ans[927] = 138503,ans[928] = 136131,ans[929] = 155315,ans[930] = 155315;
ans[931] = 136131,ans[935] = 138252;
ans[936] = 138214,ans[937] = 138503,ans[938] = 136131,ans[939] = 155315,ans[940] = 155315;
ans[941] = 136131,ans[942] = 138503,ans[946] = 138214,ans[947] = 138503,ans[948] = 136131,ans[949] = 155315,ans[950] = 155315;
ans[951] = 136131,ans[952] = 138503,ans[953] = 138214,ans[957] = 138503,ans[958] = 136131,ans[959] = 155315,ans[960] = 155315;
ans[961] = 136131,ans[962] = 138503,ans[963] = 138214,ans[964] = 138252,ans[968] = 136131,ans[969] = 155315,ans[970] = 155315;
ans[971] = 136131,ans[972] = 138503,ans[973] = 138214,ans[974] = 138252,ans[975] = 138252;
ans[979] = 155315,ans[1302] = 138503,ans[1303] = 138214,ans[1304] = 138252,ans[1305] = 138252;
ans[1306] = 138214,ans[1307] = 138503,ans[1308] = 136131,ans[1309] = 155315,ans[1313] = 138214,ans[1314] = 138252,ans[1315] = 138252;
ans[1316] = 138214,ans[1317] = 138503,ans[1318] = 136131,ans[1319] = 155315,ans[1350] = 155315;
ans[1351] = 136131,ans[1352] = 138503,ans[1353] = 138214,ans[1357] = 138503,ans[1358] = 136131,ans[1359] = 155315,ans[1360] = 155315;
ans[1361] = 136131,ans[1362] = 138503,ans[1363] = 138214,ans[1364] = 138252,ans[1368] = 136131,ans[1369] = 155315,ans[1370] = 155315;
ans[1371] = 136131,ans[1372] = 138503,ans[1373] = 138214,ans[1374] = 138252,ans[1375] = 138252;
ans[1379] = 155315,ans[1380] = 155315;
ans[1381] = 136131,ans[1382] = 138503,ans[1383] = 138214,ans[1384] = 138252,ans[1385] = 138252;
ans[1386] = 138214,ans[1390] = 155315;
ans[1391] = 136131,ans[1392] = 138503,ans[1393] = 138214,ans[1394] = 138252,ans[1395] = 138252;
ans[1396] = 138214,ans[1397] = 138503,ans[1402] = 138503,ans[1403] = 138214,ans[1404] = 138252,ans[1405] = 138252;
ans[1406] = 138214,ans[1407] = 138503,ans[1408] = 136131,ans[1409] = 155315,ans[1413] = 138214,ans[1414] = 138252,ans[1415] = 138252;
ans[1416] = 138214,ans[1417] = 138503,ans[1418] = 136131,ans[1419] = 155315,ans[1420] = 155315;
ans[1424] = 138252,ans[1425] = 138252;
ans[1426] = 138214,ans[1427] = 138503,ans[1428] = 136131,ans[1429] = 155315,ans[1460] = 155315;
ans[1461] = 136131,ans[1462] = 138503,ans[1463] = 138214,ans[1464] = 138252,ans[1468] = 136131,ans[1469] = 155315,ans[1470] = 155315;
ans[1471] = 136131,ans[1472] = 138503,ans[1473] = 138214,ans[1474] = 138252,ans[1475] = 138252;
ans[1479] = 155315,ans[1480] = 155315;
ans[1481] = 136131,ans[1482] = 138503,ans[1483] = 138214,ans[1484] = 138252,ans[1485] = 138252;
ans[1486] = 138214,ans[1490] = 155315;
ans[1491] = 136131,ans[1492] = 138503,ans[1493] = 138214,ans[1494] = 138252,ans[1495] = 138252;
ans[1496] = 138214,ans[1497] = 138503,ans[1502] = 138503,ans[1503] = 138214,ans[1504] = 138252,ans[1505] = 138252;
ans[1506] = 138214,ans[1507] = 138503,ans[1508] = 136131,ans[1509] = 155315,ans[1513] = 138214,ans[1514] = 138252,ans[1515] = 138252;
ans[1516] = 138214,ans[1517] = 138503,ans[1518] = 136131,ans[1519] = 155315,ans[1520] = 155315;
ans[1524] = 138252,ans[1525] = 138252;
ans[1526] = 138214,ans[1527] = 138503,ans[1528] = 136131,ans[1529] = 155315,ans[1530] = 155315;
ans[1531] = 136131,ans[1535] = 138252;
ans[1536] = 138214,ans[1537] = 138503,ans[1538] = 136131,ans[1539] = 155315,ans[1570] = 155315;
ans[1571] = 136131,ans[1572] = 138503,ans[1573] = 138214,ans[1574] = 138252,ans[1575] = 138252;
ans[1579] = 155315,ans[1580] = 155315;
ans[1581] = 136131,ans[1582] = 138503,ans[1583] = 138214,ans[1584] = 138252,ans[1585] = 138252;
ans[1586] = 138214,ans[1590] = 155315;
ans[1591] = 136131,ans[1592] = 138503,ans[1593] = 138214,ans[1594] = 138252,ans[1595] = 138252;
ans[1596] = 138214,ans[1597] = 138503,ans[1602] = 138503,ans[1603] = 138214,ans[1604] = 138252,ans[1605] = 138252;
ans[1606] = 138214,ans[1607] = 138503,ans[1608] = 136131,ans[1609] = 155315,ans[1613] = 138214,ans[1614] = 138252,ans[1615] = 138252;
ans[1616] = 138214,ans[1617] = 138503,ans[1618] = 136131,ans[1619] = 155315,ans[1620] = 155315;
ans[1624] = 138252,ans[1625] = 138252;
ans[1626] = 138214,ans[1627] = 138503,ans[1628] = 136131,ans[1629] = 155315,ans[1630] = 155315;
ans[1631] = 136131,ans[1635] = 138252;
ans[1636] = 138214,ans[1637] = 138503,ans[1638] = 136131,ans[1639] = 155315,ans[1640] = 155315;
ans[1641] = 136131,ans[1642] = 138503,ans[1646] = 138214,ans[1647] = 138503,ans[1648] = 136131,ans[1649] = 155315,ans[1680] = 155315;
ans[1681] = 136131,ans[1682] = 138503,ans[1683] = 138214,ans[1684] = 138252,ans[1685] = 138252;
ans[1686] = 138214,ans[1690] = 155315;
ans[1691] = 136131,ans[1692] = 138503,ans[1693] = 138214,ans[1694] = 138252,ans[1695] = 138252;
ans[1696] = 138214,ans[1697] = 138503,ans[1702] = 138503,ans[1703] = 138214,ans[1704] = 138252,ans[1705] = 138252;
ans[1706] = 138214,ans[1707] = 138503,ans[1708] = 136131,ans[1709] = 155315,ans[1713] = 138214,ans[1714] = 138252,ans[1715] = 138252;
ans[1716] = 138214,ans[1717] = 138503,ans[1718] = 136131,ans[1719] = 155315,ans[1720] = 155315;
ans[1724] = 138252,ans[1725] = 138252;
ans[1726] = 138214,ans[1727] = 138503,ans[1728] = 136131,ans[1729] = 155315,ans[1730] = 155315;
ans[1731] = 136131,ans[1735] = 138252;
ans[1736] = 138214,ans[1737] = 138503,ans[1738] = 136131,ans[1739] = 155315,ans[1740] = 155315;
ans[1741] = 136131,ans[1742] = 138503,ans[1746] = 138214,ans[1747] = 138503,ans[1748] = 136131,ans[1749] = 155315,ans[1750] = 155315;
ans[1751] = 136131,ans[1752] = 138503,ans[1753] = 138214,ans[1757] = 138503,ans[1758] = 136131,ans[1759] = 155315,ans[1790] = 155315;
ans[1791] = 136131,ans[1792] = 138503,ans[1793] = 138214,ans[1794] = 138252,ans[1795] = 138252;
ans[1796] = 138214,ans[1797] = 138503,ans[1802] = 138503,ans[1803] = 138214,ans[1804] = 138252,ans[1805] = 138252;
ans[1806] = 138214,ans[1807] = 138503,ans[1808] = 136131,ans[1809] = 155315,ans[1813] = 138214,ans[1814] = 138252,ans[1815] = 138252;
ans[1816] = 138214,ans[1817] = 138503,ans[1818] = 136131,ans[1819] = 155315,ans[1820] = 155315;
ans[1824] = 138252,ans[1825] = 138252;
ans[1826] = 138214,ans[1827] = 138503,ans[1828] = 136131,ans[1829] = 155315,ans[1830] = 155315;
ans[1831] = 136131,ans[1835] = 138252;
ans[1836] = 138214,ans[1837] = 138503,ans[1838] = 136131,ans[1839] = 155315,ans[1840] = 155315;
ans[1841] = 136131,ans[1842] = 138503,ans[1846] = 138214,ans[1847] = 138503,ans[1848] = 136131,ans[1849] = 155315,ans[1850] = 155315;
ans[1851] = 136131,ans[1852] = 138503,ans[1853] = 138214,ans[1857] = 138503,ans[1858] = 136131,ans[1859] = 155315,ans[1860] = 155315;
ans[1861] = 136131,ans[1862] = 138503,ans[1863] = 138214,ans[1864] = 138252,ans[1868] = 136131,ans[1869] = 155315,ans[1902] = 138503,ans[1903] = 138214,ans[1904] = 138252,ans[1905] = 138252;
ans[1906] = 138214,ans[1907] = 138503,ans[1908] = 136131,ans[1909] = 155315,ans[1913] = 138214,ans[1914] = 138252,ans[1915] = 138252;
ans[1916] = 138214,ans[1917] = 138503,ans[1918] = 136131,ans[1919] = 155315,ans[1920] = 155315;
ans[1924] = 138252,ans[1925] = 138252;
ans[1926] = 138214,ans[1927] = 138503,ans[1928] = 136131,ans[1929] = 155315,ans[1930] = 155315;
ans[1931] = 136131,ans[1935] = 138252;
ans[1936] = 138214,ans[1937] = 138503,ans[1938] = 136131,ans[1939] = 155315,ans[1940] = 155315;
ans[1941] = 136131,ans[1942] = 138503,ans[1946] = 138214,ans[1947] = 138503,ans[1948] = 136131,ans[1949] = 155315,ans[1950] = 155315;
ans[1951] = 136131,ans[1952] = 138503,ans[1953] = 138214,ans[1957] = 138503,ans[1958] = 136131,ans[1959] = 155315,ans[1960] = 155315;
ans[1961] = 136131,ans[1962] = 138503,ans[1963] = 138214,ans[1964] = 138252,ans[1968] = 136131,ans[1969] = 155315,ans[1970] = 155315;
ans[1971] = 136131,ans[1972] = 138503,ans[1973] = 138214,ans[1974] = 138252,ans[1975] = 138252;
ans[1979] = 155315;
}

bool check(int v)
{
	bool res = true;
	int last = -9;
	while(v > 0)
	{
		if(last == -9) last = v % 10;
		else
		{
			if(abs((v % 10) - last) < 2)
			{
				res = false;
				break;
			}
			last = v % 10;
		}
		v /= 10;
	}
	return res;
}

void solve()
{
	int id = a;
	while(id % 1000000 != 1) // pre
	{
		if(check(id)) cnt++;
		if(id == b) return;
		id++;
	}
	for(int i = id;i+1000000 <= b;i += 1000000) // dabiao
	{
		cnt += ans[i/1000000];
		id = i;
	}
	for(int i = id;i <= b;i++) // last
	{
		if(check(i)) cnt++;
	}
}

signed main()
{
	cin >> a >> b;
	init();
	solve();
	cout << cnt << endl;
	return 0;
}
2024/10/24 10:17
加载中...