【做题记录】构造题
CF468C Hack it!
題意：
令 \(F(x)\) 表示 \(x\) 的各個位上的數(shù)字之和，如 \(F(1234)=1+2+3+4=10\) 。
給定 \(a(a\le 10^{18})\) ，請求出任意一組 \(l,r(l,r\le 10^{200})\) ，要求滿足：
\[\sum_{i=l}^{r}F(i)\pmod{a}=0 \]輸出 \(l,r\) 。
$\texttt{solution}$注意到，若 \(F(x)=p\) ，那么 \(F(x+10^{18})=F(x)+1=p+1\) 。
那么可以發(fā)現(xiàn)，若 \(\sum_{i=0}^{10^{18}-1}F(i)=p\) ，那么有：
\[\sum_{i=1}^{10^{18}}F(i)=sum_{i=1}^{10^{18}-1}+F(10^{18})-F(0)=p+1 \]因此發(fā)現(xiàn) \(l=a-p,r=a-p+10^{18}-1\) 時恰好能夠成立。
因此考慮求出 \(p\) 。
\[\begin{aligned}\sum_{i=0}^{10^{18}-1}&=45\times 10^{17}+10\times \sum_{i=0}^{10^{17}-1}f(i)\\&=45\times 10^{17}+10\times (45\times 10^{16})+100\times \sum_{i=0}^{10^{16}-1}f(i)\\&=\dots\\&=18\times 45\times 10^{17}\\&=81\times 10^{18}\end{aligned} \]之后帶入式子就可以啦！
typedef unsigned long long ll; ll a,l,r,p,inf=1e18; int main() {a=rd(),p=inf%a*9llu%a*9llu%a;printf("%llu %llu\n",a-p,a-p+inf-1llu);return 0; }CF1491F Magnets
交互、二分。
早苗有 \(n\) 塊磁石，編號為 \(1,2,\cdots,n\)。每塊磁石的磁極可能是正極，負極，也可能沒有磁性。她希望你能幫她找出所有沒有磁性的磁石。
萬幸的是，你有一臺磁力檢測儀。你每次可以將每個磁石放在這臺機器的左托盤，右托盤或者不放。
機器將會返回此時的磁力強度。設(shè)托盤左邊有 \(n_1\) 個磁石為正極，\(s_1\) 個磁石為負極，托盤右邊中有 \(n_2\) 磁石為正極，\(s_2\) 個磁石為負極，則返回的磁力強度為 \(n_1n_2+s_1s_2-n_1s_2-n_2s_1\)。
如果一次測試中磁力強度的絕對值大于 \(n\)，這臺機器就會壞掉。
你需要在 \(n+\lfloor\log_2n\rfloor\) 次測試內(nèi)找到所有沒有磁性的磁石的編號，同時不能弄壞機器。
保證存在至少 \(2\) 塊磁石有磁性且至少 \(1\) 塊磁石沒有磁性。
$\texttt{solution}$先化簡式子發(fā)現(xiàn)交互的返回值就是 \((n_1-s_1)(n_2-s_2)\)。
由于正負極石頭放在一起會導(dǎo)致 \(n,s\) 會都大于 \(0\) ，使問題變得更為困難。
那么考慮每次查詢只對一塊石頭與其他一堆石頭之間進行詢問。
那么如果我們已經(jīng)知道了一塊有磁性的此時，就可以非常容易的知道其他所有的此時是否有磁性。
之后考慮如何才能找出有磁性的石頭，直接枚舉肯定是不行的，最壞都會到 \(O(n^2)\) 。
我們可以從 \(1\) 向 \(n\) 開始枚舉 \(i\)，詢問 \([1,i-1]\) 與 \(i\)。若詢問結(jié)果不為 \(0\)，則 \([1,i-1]\) 中必然有一塊有磁性的石頭，而 \(i\) 也一定是有磁性的。因此可以找出一塊有磁性的石頭。
之后我們是否可以 \(O(n)\) 檢查所有石頭了呢？還是不行。。。
考慮到答案不能超過 \(n+\log n\)，所以我們只能將上面第二塊石頭之后，也就是 \([i+1,n]\) 中的石頭判斷一遍。這樣到現(xiàn)在為止總共用了 \(n-1\) 次操作。
而 \([1,i-1]\) 中只有 \(1\) 快有磁性的石頭，所以我們可以二分出這塊石頭的位置，找出這最后一塊有磁性的石頭。那么我們就做完啦。
int T,n,Last,pos,cnt; int ans[Maxn]; inline int query(int nl,int nr,int k) {printf("? %d %d\n",nr-nl+1,1);for(int i=nl;i<=nr;i++) printf("%d%c",i,(i==nr)?'\n':' ');printf("%d\n",k);fflush(stdout);return rd(); } inline void print() {printf("! %d ",cnt);for(int i=1;i<=cnt;i++) printf("%d%c",ans[i],(i==cnt)?'\n':' ');fflush(stdout); } int main() {T=rd();while(T--){n=rd(),pos=-1,cnt=0;for(int i=2;i<=n && pos==-1;i++)if(query(1,i-1,i)) pos=i;for(int i=pos+1;i<=n;i++) if(!query(i,i,pos)) ans[++cnt]=i;int nl=1,nr=pos-1;while(nl<=nr){int mid=(nl+nr)>>1;if(query(1,mid,pos)) Last=mid,nr=mid-1;else nl=mid+1;}for(int i=1;i<pos;i++) if(i!=Last) ans[++cnt]=i;print();}return 0; }CF1586F Defender of Childhood Dreams
給定一張競賽圖(點數(shù) \(\le 1000\))，對于所有 \(a<b\)，都有一條由 \(a\) 到 \(b\) 的有向邊，并且每一條邊都有一個顏色?，F(xiàn)在要求所有長度大于等于 \(k\) 的路徑上都有 \(\ge 2\) 中顏色。求出整張圖中出現(xiàn)最少出現(xiàn)顏色的數(shù)量與邊的染色方案。
$\texttt{solution}$考慮將序列分為許多長度不超過 \(k\) 個塊，在塊與塊間連接相同顏色的邊。這樣可以保證在塊與塊間轉(zhuǎn)移的邊不會形成 \(\ge k\) 長度的路徑。
在每一個塊內(nèi)部再進行同樣的拆分(但在塊內(nèi)的顏色要與塊外的顏色不同)，遞歸進行即可。
#define Maxn 1005 int n,k,ans; int col[Maxn][Maxn]; void solve(int l,int r,int c) {if(l==r) return;int len=(r-l+k)/k,tot=(r-l+len)/len;for(int i=1,x,y;i<tot;i++)for(int j=i+1;j<=tot;j++)for(int p=1;p<=len;p++)for(int q=1;q<=len;q++){x=l+(i-1)*len+p-1,y=l+(j-1)*len+q-1;if(y>r) break;col[x][y]=c;}for(int i=1;i<=tot;i++) solve(l+(i-1)*len,min(l+i*len-1,r),c+1); } int main() {n=rd(),k=rd();solve(1,n,1);for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) ans=max(ans,col[i][j]);printf("%d\n",ans);for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) printf("%d ",col[i][j]);printf("\n");return 0; }CF715D Create a Maze
有一個 \(n\times m\) 的迷宮，每一格都是一個房間，每兩個相鄰的房間之間有一扇門。
在所有門中，有 \(k\) 扇是鎖著的，不能通行，其余沒有限制。
現(xiàn)在你在 \((1,1)\)，需要走到 \((n,m)\)，只能向下或向右走。
設(shè)總共的行走方案有 \(T\) 種。
現(xiàn)在給出 \(T\)，要求設(shè)計出一個迷宮滿足行走方案為 \(T\)。
要求：\(n,m\le 50,k\le 500,T\le 10^{18}\)。
$\texttt{solution}$這一題需要按照 \(T\) 的進制來解決問題。
首先考慮用二進制，那么我們可以這樣設(shè)計方案：
這樣我們就可以用二進制來表示出任何 \(\le 2^{49}\) 的 \(T\) 啦！
然而我們發(fā)現(xiàn)如果我們將我們的以 \(2\times 2\) 改為 \(3\times 3\)，可以將前面的二進制變?yōu)榱M制！！
之后構(gòu)造就比較類似，我們只要改為兩路 \(1\) 和中間的 \(3\times 3\) 即可。
這樣最大可以表示 \(6^{24}>10^{18}\)，可以解決這道題啦！
總結(jié)
- 上一篇： 期望 概率DP
- 下一篇： 努比亚 Z50S Pro 手机星光摄影套