題干：

蒜頭國有?nn?座城市，編號分別為?0,1,2,3,\ldots,n-10,1,2,3,…,n?1。編號為?xx?和?yy?的兩座城市之間如果要修高速公路，必須花費?x|yx∣y?個金幣，其中|表示二進制按位或。

吝嗇的國王想要花最少的價格修建高速公路，使得所有城市可以通過若干條高速公路互相達到。現(xiàn)在請你求出?n=2019n=2019?時，一共有多少不同的方案，能讓所有城市連通并且造價最低。方案數(shù)可能很大，你只需輸出對?10^9+7109+7?取模的結(jié)果。

樣例輸入復制

無

樣例輸出復制

無

解題報告：

? 這題首先看最終答案是多少，顯然不難發(fā)現(xiàn)，因為每個結(jié)點都至少連一條邊，所以結(jié)果不可能低于0+1+2+3+..n-1。又因為可以每條邊都和0連，所以可以做到0+1+2+3+..n-1。接下來就是構(gòu)造答案的方案數(shù)了。

這個最終答案的構(gòu)造也可以直接n^2建圖然后跑MST就完事了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; const ll mod = 1e9+7; int main() {int n = 2019;ll ans = 1;for (int i = 1; i < n; i++) {ll tmp = 0;for(int j = 0; j<i; j++) {if((i|j) == i) {tmp++;}}ans = (ans * tmp)%mod;}printf("%lld\n", ans);return 0 ;}

還有一種nlogn的做法：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; const ll mod = 1e9+7; int main() {int n = 2019;ll ans = 1;for (int i = 1; i < n; i++) {int t = 0;//代表i這個數(shù)有幾個1.for (int j = 0; i >> j > 0; j++) {if (i >> j & 1) t++;}ans = ans * ((1 << t) - 1) % mod;}printf("%lld\n", ans);return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【计蒜客 - 蓝桥训练】修建公路（贪心，或运算，dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。