天天看點

NOIP模拟73

T1:

  20分:狀壓DP或Dfs O(2^n)暴力

  60分:發現答案為1e5級别,做0/1背包即可

  100分:分析過程,由于要求最小的非幸運數,那麼由于數的組成是連續的

  那麼模拟過程發現,能夠延伸所能組成的數的集合的機關數為:1,2,4,11,22,44

  進一步拓展發現第i個數為Pre[i - 1] + 1,是以若a[i] > Pre[i - 1] + 1,那麼答案則為

  Pre[i - 1] + 1,時間複雜度O(nlogn)(sort排序)

代碼如下:

NOIP模拟73
NOIP模拟73

View Code

T2:

  矩陣乘法,重新定義矩陣乘法為C[i][j] = $\prod$A[i][k]^B[k][j],于是直接調配矩陣系數即可

  需要注意的是,由于将幂乘轉化為指數相加,那麼在指數矩陣取模時需要根據費馬定理對(mod - 1)取模

NOIP模拟73
NOIP模拟73

T3:

  全源最短路,考慮在最短路過程中記錄每個白點連向最短路的連邊,最終在每個白點所有連邊集合中取最小值即可

NOIP模拟73
NOIP模拟73

T4:

  狀壓DP,是狀态劃分類型,考慮定義f[i]表示隻考慮i集合中所有元素的拓撲序方案數

  那麼對于(1 << j & i == 0)f[i | 1 << j] += f[i] * (1 << cnt),其中j為非i集合中的點,cnt為

  i集合中連向j點的邊數,其意義為考慮将j點作為新集合的拓撲序最後一個,那麼i集合對新集合

  的貢獻即為f[i] * (1 << cnt),即任意删邊

NOIP模拟73
NOIP模拟73
上一篇: NOIP模拟5
下一篇: NOIP模拟2