NOIP 2015 提高組 初賽
疑難點 學習 感悟。
一、
3.
示例如下（來自自個的了解）：
101.101 十進制 轉十進制1*10^2+0*10^1+1*10^0+1*10^-1+0*10^-2+1*10^-3
101.101 二進制 轉十進制1*2^2+0*2^1+1*2^0+1*2^-1+0*2^-2+1*2^-3
101.101 八進制 轉十進制1*8^2+0*8^1+1*8^0+1*8^-1+0*8^-2+1*8^-3
101.101 十六進制 轉十進制1*16^2+0*16^1+1*16^0+1*16^-1+0*16^-2+1*16^-3
題解如下：
0.1 二進制轉十進制0*2^0+1*2^-1=0.5
A選項
0.8十六進制轉十進制0*16^0+8*16^-1=0.5
4.
示例如下（來自自個的了解）：
101.101 十進制 轉十進制1*10^2+0*10^1+1*10^0+1*10^-1+0*10^-2+1*10^-3
101.101 二進制 轉十進制1*2^2+0*2^1+1*2^0+1*2^-1+0*2^-2+1*2^-3
101.101 八進制 轉十進制1*8^2+0*8^1+1*8^0+1*8^-1+0*8^-2+1*8^-3
101.101 十六進制 轉十進制1*16^2+0*16^1+1*16^0+1*16^-1+0*16^-2+1*16^-3
題解如下：
D選項
1762 八進制轉十進制1*8^3+7*8^2+6*8^1+2*8^0=1010
3F2十六進制轉十進制3*16^2+15*16^1+2*16^0=1010
7.
(來自《算法競賽入門經典》P155)
用遞歸定義 二叉樹T 的先序周遊、中序周遊、後序周遊：
先序周遊 PreOrder(T)=T的根節點+PreOrder(T的左子樹)+PreOrder(T的右子樹)
中序周遊 InOrder(T)=InOrder(T的左子樹)+T的根節點+InOrder(T的右子樹)
後序周遊 PostOrder(T)=PostOrder(T的左子樹)+PostOrder(T的右子樹)+T的根節點
8.
(來自《啊哈！算法》P184)
滿二叉樹的嚴格定義是一棵深度為h且有2^h-1個結點的二叉樹。如下圖所示：
完全二叉樹嚴格定義：若設二叉樹的高度為h，除第h層外，其他各層(1-h-1)的結點數都達到最大個數，
第h層從右向左連續缺若幹節點，則這個二叉樹就是完全二叉樹。
如下圖所示：
9.
(來自《算法競賽入門經典》P355-P356)
最小生成樹：
在無向圖中，連通且不含圈的圖稱為樹(Tree)。給定無向圖G=(V,E),連接配接G中所有點，且邊集是E的子集的書稱為G的生成樹(Spanning Tree)，而權值最小的生成樹稱為最小生成樹(Minimal Spanning Tree,MST)。
10.
T(n)=T(n-1)+n
推導：
T(n)=T(n-2)+n-1+n
T(n)=T(n-3)+n-2+n-1+n
T(n)=T(n-4)+n-3+n-2+n-1+n
......
T(n)=T(1)+2+......+n-3+n-2+n-1+n
T(n)=T(0)+1+2+......+n-3+n-2+n-1+n
T(n)=1+1+2+......+n-3+n-2+n-1+n
T(n)=1+(1+n)*n/2
T(n)=(n^2+n+2)/2
故T(n)=O(n^2)
類似的一題，(來自《大話資料結構》P422)
T(n)<=2T(n/2)+n,T(1)=0
推導：
T(n)<=2*(2T(n/2/2)+n/2)+n=2*2T(n/2/2)+2n
T(n)<=2*2*(2T(n/2/2/2)+n/2/2)+2n=2*2*2T(n/2/2/2)+3n
T(n)<=2*2*2*(2T(n/2/2/2/2)+n/2/2/2)+3n=2*2*2*2T(n/2/2/2/2)+4n
......
T(n)<=2^tT(n/2^t)+tn
n/2^t=1
n=2^t
logn=tlog2
t=logn/log2
帶入t值
T(n)<=2^tT(n/2^t)+tn=n*T(1)+nlogn/log2=nlogn/log2
T(n)<=O(nlogn)
二、
5.
(來自《啊哈！算法》P238)
二分圖的定義是：如果一個圖的所有頂點可以被分為X和Y兩個集合，
并且所有邊的兩個頂點恰好一個屬于集合X，另一個屬于集合Y，
即每個集合内的頂點沒有邊相連，那麼此圖就是二分圖。例子如下圖所示：
(來自《資料結構(C語言版)》嚴蔚敏 吳偉民 P158)
n表示圖中頂點數目，有n(n-1)/2條邊的無向圖稱為完全圖。
(來自《資料結構(C語言版)》嚴蔚敏 吳偉民 P159)
在無向圖G中，如果從頂點v到頂點u有路徑，則稱v和u是連通的。如果對于圖中任意兩個頂點u、v，u和v都是連通的，則稱G是連通圖。示例如下：
(來自《啊哈！算法》P180)
樹其實就是不包含回路的連通無向圖。
示例如下：
左為樹，右為圖
三、
1.答案1075
容斥原理
2015-2015/4-2015/5-2015/6+2015/20+2015/12+2015/30-2015/60=1075
容斥原理不懂的，建議學習此文https://blog.csdn.net/mrcrack/article/details/80562324第16講内容：第6章 容斥原理及應用
2019-2-15 23:00
1.基本思路，2015扣除能被4、5、6整除的數。
能被4整除的數有2015/4=503個；
能被5整除的數有2015/5=403個；
能被6整除的數有2015/6=335個；
能同時被4、5整除的數有2015/20=100個;
能同時被4、6整除的數有2015/12=167個;
能同時被5、6整除的數有2015/30=67個;
能同時被4、5、6整除的數有2015/60=33個;
能被4、5、6整除的數503+403+335-（100+167+67）+33=940個；
不能被4、5、6整除的數2015-940=1075個；
該題就算思路知曉，運算也容易出錯。
能被4整除的數有2015/4=503個；
4 8 12 16 20 24 28 32 36 40
44 48 52 56 60 64 68 72 76 80
84 88 92 96 100 104 108 112 116 120
124 128 132 136 140 144 148 152 156 160
164 168 172 176 180 184 188 192 196 200
204 208 212 216 220 224 228 232 236 240
244 248 252 256 260 264 268 272 276 280
284 288 292 296 300 304 308 312 316 320
324 328 332 336 340 344 348 352 356 360
364 368 372 376 380 384 388 392 396 400
404 408 412 416 420 424 428 432 436 440
444 448 452 456 460 464 468 472 476 480
484 488 492 496 500 504 508 512 516 520
524 528 532 536 540 544 548 552 556 560
564 568 572 576 580 584 588 592 596 600
604 608 612 616 620 624 628 632 636 640
644 648 652 656 660 664 668 672 676 680
684 688 692 696 700 704 708 712 716 720
724 728 732 736 740 744 748 752 756 760
764 768 772 776 780 784 788 792 796 800
804 808 812 816 820 824 828 832 836 840
844 848 852 856 860 864 868 872 876 880
884 888 892 896 900 904 908 912 916 920
924 928 932 936 940 944 948 952 956 960
964 968 972 976 980 984 988 992 996 1000
1004 1008 1012 1016 1020 1024 1028 1032 1036 1040
1044 1048 1052 1056 1060 1064 1068 1072 1076 1080
1084 1088 1092 1096 1100 1104 1108 1112 1116 1120
1124 1128 1132 1136 1140 1144 1148 1152 1156 1160
1164 1168 1172 1176 1180 1184 1188 1192 1196 1200
1204 1208 1212 1216 1220 1224 1228 1232 1236 1240
1244 1248 1252 1256 1260 1264 1268 1272 1276 1280
1284 1288 1292 1296 1300 1304 1308 1312 1316 1320
1324 1328 1332 1336 1340 1344 1348 1352 1356 1360
1364 1368 1372 1376 1380 1384 1388 1392 1396 1400
1404 1408 1412 1416 1420 1424 1428 1432 1436 1440
1444 1448 1452 1456 1460 1464 1468 1472 1476 1480
1484 1488 1492 1496 1500 1504 1508 1512 1516 1520
1524 1528 1532 1536 1540 1544 1548 1552 1556 1560
1564 1568 1572 1576 1580 1584 1588 1592 1596 1600
1604 1608 1612 1616 1620 1624 1628 1632 1636 1640
1644 1648 1652 1656 1660 1664 1668 1672 1676 1680
1684 1688 1692 1696 1700 1704 1708 1712 1716 1720
1724 1728 1732 1736 1740 1744 1748 1752 1756 1760
1764 1768 1772 1776 1780 1784 1788 1792 1796 1800
1804 1808 1812 1816 1820 1824 1828 1832 1836 1840
1844 1848 1852 1856 1860 1864 1868 1872 1876 1880
1884 1888 1892 1896 1900 1904 1908 1912 1916 1920
1924 1928 1932 1936 1940 1944 1948 1952 1956 1960
1964 1968 1972 1976 1980 1984 1988 1992 1996 2000
2004 2008 2012
能被5整除的數有2015/5=403個；
5 10 15 20 25 30 35 40 45 50
55 60 65 70 75 80 85 90 95 100
105 110 115 120 125 130 135 140 145 150
155 160 165 170 175 180 185 190 195 200
205 210 215 220 225 230 235 240 245 250
255 260 265 270 275 280 285 290 295 300
305 310 315 320 325 330 335 340 345 350
355 360 365 370 375 380 385 390 395 400
405 410 415 420 425 430 435 440 445 450
455 460 465 470 475 480 485 490 495 500
505 510 515 520 525 530 535 540 545 550
555 560 565 570 575 580 585 590 595 600
605 610 615 620 625 630 635 640 645 650
655 660 665 670 675 680 685 690 695 700
705 710 715 720 725 730 735 740 745 750
755 760 765 770 775 780 785 790 795 800
805 810 815 820 825 830 835 840 845 850
855 860 865 870 875 880 885 890 895 900
905 910 915 920 925 930 935 940 945 950
955 960 965 970 975 980 985 990 995 1000
1005 1010 1015 1020 1025 1030 1035 1040 1045 1050
1055 1060 1065 1070 1075 1080 1085 1090 1095 1100
1105 1110 1115 1120 1125 1130 1135 1140 1145 1150
1155 1160 1165 1170 1175 1180 1185 1190 1195 1200
1205 1210 1215 1220 1225 1230 1235 1240 1245 1250
1255 1260 1265 1270 1275 1280 1285 1290 1295 1300
1305 1310 1315 1320 1325 1330 1335 1340 1345 1350
1355 1360 1365 1370 1375 1380 1385 1390 1395 1400
1405 1410 1415 1420 1425 1430 1435 1440 1445 1450
1455 1460 1465 1470 1475 1480 1485 1490 1495 1500
1505 1510 1515 1520 1525 1530 1535 1540 1545 1550
1555 1560 1565 1570 1575 1580 1585 1590 1595 1600
1605 1610 1615 1620 1625 1630 1635 1640 1645 1650
1655 1660 1665 1670 1675 1680 1685 1690 1695 1700
1705 1710 1715 1720 1725 1730 1735 1740 1745 1750
1755 1760 1765 1770 1775 1780 1785 1790 1795 1800
1805 1810 1815 1820 1825 1830 1835 1840 1845 1850
1855 1860 1865 1870 1875 1880 1885 1890 1895 1900
1905 1910 1915 1920 1925 1930 1935 1940 1945 1950
1955 1960 1965 1970 1975 1980 1985 1990 1995 2000
2005 2010 2015
能被6整除的數有2015/6=335個；
6 12 18 24 30 36 42 48 54 60
66 72 78 84 90 96 102 108 114 120
126 132 138 144 150 156 162 168 174 180
186 192 198 204 210 216 222 228 234 240
246 252 258 264 270 276 282 288 294 300
306 312 318 324 330 336 342 348 354 360
366 372 378 384 390 396 402 408 414 420
426 432 438 444 450 456 462 468 474 480
486 492 498 504 510 516 522 528 534 540
546 552 558 564 570 576 582 588 594 600
606 612 618 624 630 636 642 648 654 660
666 672 678 684 690 696 702 708 714 720
726 732 738 744 750 756 762 768 774 780
786 792 798 804 810 816 822 828 834 840
846 852 858 864 870 876 882 888 894 900
906 912 918 924 930 936 942 948 954 960
966 972 978 984 990 996 1002 1008 1014 1020
1026 1032 1038 1044 1050 1056 1062 1068 1074 1080
1086 1092 1098 1104 1110 1116 1122 1128 1134 1140
1146 1152 1158 1164 1170 1176 1182 1188 1194 1200
1206 1212 1218 1224 1230 1236 1242 1248 1254 1260
1266 1272 1278 1284 1290 1296 1302 1308 1314 1320
1326 1332 1338 1344 1350 1356 1362 1368 1374 1380
1386 1392 1398 1404 1410 1416 1422 1428 1434 1440
1446 1452 1458 1464 1470 1476 1482 1488 1494 1500
1506 1512 1518 1524 1530 1536 1542 1548 1554 1560
1566 1572 1578 1584 1590 1596 1602 1608 1614 1620
1626 1632 1638 1644 1650 1656 1662 1668 1674 1680
1686 1692 1698 1704 1710 1716 1722 1728 1734 1740
1746 1752 1758 1764 1770 1776 1782 1788 1794 1800
1806 1812 1818 1824 1830 1836 1842 1848 1854 1860
1866 1872 1878 1884 1890 1896 1902 1908 1914 1920
1926 1932 1938 1944 1950 1956 1962 1968 1974 1980
1986 1992 1998 2004 2010
能同時被4、5整除的數有2015/20=100個;
20 40 60 80 100 120 140 160 180 200
220 240 260 280 300 320 340 360 380 400
420 440 460 480 500 520 540 560 580 600
620 640 660 680 700 720 740 760 780 800
820 840 860 880 900 920 940 960 980 1000
1020 1040 1060 1080 1100 1120 1140 1160 1180 1200
1220 1240 1260 1280 1300 1320 1340 1360 1380 1400
1420 1440 1460 1480 1500 1520 1540 1560 1580 1600
1620 1640 1660 1680 1700 1720 1740 1760 1780 1800
1820 1840 1860 1880 1900 1920 1940 1960 1980 2000
能同時被4、6整除的數有2015/12=167個;
12 24 36 48 60 72 84 96 108 120
132 144 156 168 180 192 204 216 228 240
252 264 276 288 300 312 324 336 348 360
372 384 396 408 420 432 444 456 468 480
492 504 516 528 540 552 564 576 588 600
612 624 636 648 660 672 684 696 708 720
732 744 756 768 780 792 804 816 828 840
852 864 876 888 900 912 924 936 948 960
972 984 996 1008 1020 1032 1044 1056 1068 1080
1092 1104 1116 1128 1140 1152 1164 1176 1188 1200
1212 1224 1236 1248 1260 1272 1284 1296 1308 1320
1332 1344 1356 1368 1380 1392 1404 1416 1428 1440
1452 1464 1476 1488 1500 1512 1524 1536 1548 1560
1572 1584 1596 1608 1620 1632 1644 1656 1668 1680
1692 1704 1716 1728 1740 1752 1764 1776 1788 1800
1812 1824 1836 1848 1860 1872 1884 1896 1908 1920
1932 1944 1956 1968 1980 1992 2004
能同時被5、6整除的數有2015/30=67個;
30 60 90 120 150 180 210 240 270 300
330 360 390 420 450 480 510 540 570 600
630 660 690 720 750 780 810 840 870 900
930 960 990 1020 1050 1080 1110 1140 1170 1200
1230 1260 1290 1320 1350 1380 1410 1440 1470 1500
1530 1560 1590 1620 1650 1680 1710 1740 1770 1800
1830 1860 1890 1920 1950 1980 2010
能同時被4、5、6整除的數有2015/60=33個;
60 120 180 240 300 360 420 480 540 600
660 720 780 840 900 960 1020 1080 1140 1200
1260 1320 1380 1440 1500 1560 1620 1680 1740 1800
1860 1920 1980
2.
（思路來自《資料結構(C語言版)》嚴蔚敏 吳偉民)
遞推公式得出如下
(1)0個結點f(0)=1
(2)1個結點f(1)=1
(3)2個結點，固定一個為根節點，兩種情形,一個左子樹，一個右子樹。f(2)=f(1)*f(0)+f(0)*f(1)=2
(4)3個結點，f(3)=f(2)*f(0)+f(0)*f(2)+f(1)*f(1)=2*1+1*2+1*1=5
(5)4個結點，f(4)=f(3)*f(0)+f(0)*f(3)+f(2)*f(1)+f(1)*f(2)=5*1+1*5+2*1+1*2=14
(6)5個結點，f(5)=f(4)*f(0)+f(0)*f(4)+f(3)*f(1)+f(1)*f(3)+f(2)*f(2)=14*1+1*14+5*1+1*5+2*2=42
四、
2.
(來自《算法競賽入門經典》P66)
函數的形參和在函數内聲明的變量都是該函數的局部變量。無法通路其他函數的局部變量。
局部變量的存儲空間是臨時配置設定的，函數執行完畢時，局部變量的空間将被釋放，其中的值無法保留到下次使用。
題中a的變化沒有影響到p1，原因如上所示，故c1值不變。
題中*a影響的是p2指向的記憶體塊，即c2裡的值，故(*a)++對應的c2值要改變。
4.今日（2016.10.27）有重大突破，困擾已久的遞歸問題找到一種速度極快的解法。
以往的做法是自頂向下逐層遞歸，對于手算而言，運算量是天文級别的，第一次做就算能對，也不能保證第二次能對。
今日是自底向上，找規律，發現很快就能找到規律，在短時間内，隻要運算不出現低級錯誤，很快就能解決問題。此法是偶然想到，但卻解決了困擾已久的遞歸程式寫結果問題。
此題做法如下，n=0,n=1,n=2,n=3,n=4,n=5求出相應結果。在求解的過程中能發現規律。
(1)n=0
fun(0,1,3)=0
(2)n=1
fun(1,1,3)=1 附帶産物 fun(0,1,2)=0 fun(0,2,3)=0
(3)n=2
fun(2,1,3)=3 附帶産物 fun(2,1,3)=3 fun(1,1,2)=1 fun(0,1,3)=0 fun(0,3,3)=0 fun(1,2,3)=1 fun(0,2,1)=0 fun(0,1,3)=0
(3)n=3
fun(3,1,3)=7 附帶産物 fun(2,1,2)=3 fun(1,1,3)=1 fun(1,3,3)=1 fun(0,3,1)=0 fun(0,1,3)=0
fun(2,2,2)=3 fun(1,2,1)=1 fun(0,2,3)=0 fun(0,3,3)=0 fun(1,1,2)=1
(4)n=4
大膽猜想
fun(3,fromPos,toPos)=7
fun(2,fromPos,toPos)=3
fun(1,fromPos,toPos)=1
fun(0,fromPos,toPos)=0
很快寫出
fun(4,1,3)=15
(5)n=5
繼續猜
fun(4,fromPos,toPos)=15
fun(3,fromPos,toPos)=7
fun(2,fromPos,toPos)=3
fun(1,fromPos,toPos)=1
fun(0,fromPos,toPos)=0
很快寫出
fun(5,1,3)=31
很高興想到上述辦法，困擾了有半年了，此類題目是最耗時，且準确率不高。
五、
1.讀完題目，沒明白題意，硬讀程式，沒讀懂，但發現程式先處理lmax，再處理rmax，對兩種處理可以看見的代碼進行對比，發現具有對稱性，先解決第二空rmax[i]=x[i]，再解決第三空rmax[i]=rmax[i+1]+x[i]，之後解決第四空rmax[i]=rmax[i+1]，最後解決第一空rmax[n-1]=x[n-1]，根據對稱性，解決四空，還是很輕松，再讀一遍程式，看懂不少，但細節上還有問題。
第五空4分，重讀題目，發現輸出是最大和，馬上想到第五空應填lmax[i]+rmax[i]，但對至少間隔1個數，有疑問，
将程式從ans=x[0]+x[2];開始重讀一遍，啟發很大，ans=x[0]+x[2];等價于ans=lmax[0]+rmax[2];馬上将第五空進行修改lmax[i-1]+rmax[i+1]，代入i=1進行檢驗lmax[0]+rmax[2]，代入i=n-2進行檢驗lmax[n-3]+rmax[n-1]，發現兩個邊界都挺合理，至此該題程式填空完畢。
但程式還有些細節問題，從解題角度而言，該題結束。
2.有迪傑斯特拉算法（參見《啊哈！算法》P155）基礎，就算學習日期離考試比較久遠，此題還是會比較簡單。
第五空2分，其餘3分，故第五空最簡單，直接抄下行代碼，改個不等号即可。dist[i]>dist[v]+w[i][j];
第一空，處指派位置，掃描程式，多處出現v==-1，但沒有v=-1的指派，故該空v=-1;
第四空，程式中提到int used[MAXV]；//記錄結點是否已擴充（0:未擴充；1：已擴充）。
結點v進行擴充。
程式中始終找不到used[v]=1;故該空used[v]=1;
第二空，第三空，依據：每次從未擴充的結點中選取dist值最小的結點v進行擴充。
在所有沒用過的結點中，選中最小距離的結點，
第二空dist[i]<dist[v]
第三空v=i;