CF1479C Continuous City

題意：

給定 L, R. 構造一個有向帶權圖, 其中點數不大于 32, 且所有邊都是從較小的點指向較大的點. 假設這個有向圖有 n 個點, 你需要保證從 1到n 的所有路徑的權值都在 [L, R]內且不存在 x∈[L,R], 使得不存在或存在多于一條從 1 到 n 的路徑權值為 x, 或者斷言這是不可能的.

題解：

點數不超過32，其實就在往二進制的方向引，但是想了半天也沒頭緒
看了海量題解，終于悟出一些
參考文章
首先無論如何都有解，$lo{g}_2(1e6)=19.931569$,一共用22個點就夠了(20個中間點+出發點+結束點)
題目要求構造值域為[L，R]的路徑長度，我們先從1號點向所有點連一條長度為L的邊，現在的問題就是如何構造出值域[1,R-L]的路徑長度
對于所有中間點$i\in [2,21]$，我們可以認為第i個點代表二進制的第i-2位，從i號點向其他點(不含結束點)連一條長度為$2^{i?2}$的邊
如圖，(相同顏色權值一樣，綠色和黃色未畫完全)，點2到點21可以表示出路徑長度的值域為$[1,2^{i?2}?1]$,你可以這么理解，二進制下，走一條邊相當于對應的第i-2位是1，如果你從2走到3，在走到4，相當于權值為111(二進制)，如果一直走到點21，權值不就是$2^{i?2}?1$
再加上之前的L，此時1→i的路徑長度值域為$[L,L+2^{i?2}?1]$

現在問題在于$L+2^{i?2}?1$又不是R,現在我們開始考慮如何湊出R-L
(還是先忽略L)，我們用第22號點當作n號點
枚舉$i\in [2,21]$，如果R-L第i-2位是1，令t表示將R-L末i-2位都修改為0后的值，然后我們就從i向n號點連一條權值為t+1的邊。可以理解成我們將缺失那部分拆成兩部分，一部分可以用之前已經構造好的二進制來實現，另一部分作為權值再建新邊，這樣組合正好就是我們需要的值
一下01都是二進制下，
比如R-L值為101(二進制)，第0位是1，所以我們就從點2向點22建邊，邊權為101-1+1，第2位是1，所以我們從點4向點22建邊，邊權為101-101+1，這樣我們就可以構造出[L,R]。因為我之前構造邊權都是點2到點21之間的，現在R-L的第i位是1，就將第i-2個點連向n，因為第i+2個點最大值域到$2^{i?2}$，所以邊權為$(R?L)?2^{i?2}+1$
比如樣例[4,9]，根據我講的方法構造如圖：

感性再理解理解，確實不好想

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } int L,R,cnt,tot; const int maxn=2e6+9; struct node{int x,y,z; }; vector<node>vec; int main() {scanf("%d%d",&L,&R);puts("YES");vec.push_back({1,22,L});//從1號點向n號點連邊for(int i=1;i<=20;++i){for(int j=i+1;j<=21;++j){int t;if(i!=1)t=1<<i-2;else t=L;vec.push_back({i,j,t});//從1~20號點向之后除n號點以外的點連邊}}int t=R-L;for(int i=2;i<=21;++i){if(t>>(i-2)&1){t^=(1<<i-2);vec.push_back({i,22,t+1});}}printf("22 %d\n",vec.size());for(int i=0;i<vec.size();i++){printf("%d %d %d\n",vec[i].x,vec[i].y,vec[i].z);}return 0;//輸出構造方案 }

總結

以上是生活随笔為你收集整理的CF1479C Continuous City的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。