Problem A 矩陣第K小數

給定一個$n \times m$的矩陣，位置$A_{i,j}? = i\times j$，

給出$Q$個詢問，每一次查詢矩陣中第$Q_i$小的數是多少。

對于100%的數據 ， $1 \leq n,m \leq 10^9 , Q \leq 100 , 1 \leq Q_i \leq n\times m$

Sol : 本題采用暴力模擬的復雜度是不能通過的，并且其矩陣的排布都是有規律的。

　　 第$i$行構成的數列是公差為$i$的等差數列。 可以考慮枚舉每一行，然后就可以O(1) 計算這一行有多少比某一數$x$小了。

　　同時，對于每一個詢問二分答案，然后可以掃一遍$n$然后二分計算每一行的貢獻。這樣的復雜度就是$O(Qnlog_{2} (nm) )$

　　同時考慮，每一行貢獻是類似于$\lfloor \frac{x}{i} \rfloor$的東西，我們會發現這個東西對于$i$遞增，它可能的取值只會有$\sqrt{x}$種。

　　并且其值是單調下降的。 所以我們可以$O(\sqrt{n})$每次遍歷每一個"平臺"。但是由于需要二分答案，這樣的復雜度會變成$log_2 n \sqrt{n}$

　　總時間復雜度會變成$O(Q\sqrt{n} log_{2} (nm) log_2 n)$無法通過。

　　如何在$O(\sqrt{n})$的復雜度遍歷每一個塊，然后統一計算是本題的瓶頸。

　　問題等價于求$\sum\limits_{i=1}^n \lfloor \frac{x}{i} \rfloor $，我們可以考慮一個$i$滿足$a = \lfloor \frac{x}{i} \rfloor $?

　　在某一個區間內，有$a \leq \lfloor \frac{x}{i} \rfloor < a+1 $ ，所以可以解得此時的$i \in? [\left \lfloor \frac{x}{\left \lfloor \frac{x}{i}? \right \rfloor+1} \right \rfloor + 1, \left \lfloor \frac{x}{\left \lfloor \frac{x}{i} \right \rfloor} \right \rfloor]$

　　所以最后的復雜度就可以做到$O(Qlog_2 (nm) \sqrt{n} )$ 了。

# pragma GCC optimize(3) # include <bits/stdc++.h> # define int long long using namespace std; int n,m,q; inline int read() {int X=0,w=0; char c=0;while(c<'0'||c>'9') {w|=c=='-';c=getchar();}while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();return w?-X:X; } int calc(int i,int x){if (x%i==0) return min(x/i-1,m);else return min(x/i,m); } bool check(int x,int k) {int ret=0;for (int l=1,r;l<=min(x,m);l=r+1) {r=x/(x/l);ret+=min((x/l),n)*(r-l+1);} return (ret>=k); } signed main() {n=read();m=read();q=read();while (q--) {int x=read(); int l=1,r=n,ans;while (l<=r) {int mid=(l+r)>>1;if (check(mid,x)) ans=mid,r=mid-1;else l=mid+1;}printf("%lld\n",ans);}return 0; } mat.cpp

Problem B 最小極差生成樹

給出$n$個點$m$條邊的連通圖$G=(V,E)$，求出一棵生成樹使得其最大邊權和最小邊權的差最小。

對于100%的數據$1 \leq m\leq 4000 ,? 1 \leq n \leq 1000$

Sol : 枚舉每一條邊，以這條邊權$s$為下界跑最小生成樹，找出最小生成樹的最大邊權為$d$.

　　用$d-s$更新答案。注意可能會有不合法情況，輸出-1即可。

# pragma GCC optimize(3) # include <bits/stdc++.h> using namespace std; const int N=4e3+10; int n,m,f[N]; struct node{ int u,v,w;}E[N]; bool cmp(node a,node b) {return a.w<b.w;} inline int read() {int X=0,w=0; char c=0;while(c<'0'||c>'9') {w|=c=='-';c=getchar();}while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();return w?-X:X; } int father(int x) {if (f[x]==x) return x;return f[x]=father(f[x]); } int MST(int W) {for (int i=1;i<=n;i++) f[i]=i;int tmp=0,o=0;for (int i=1;i<=m;i++) {if (E[i].w<W) continue;int fx=father(E[i].u),fy=father(E[i].v);if (fx==fy) continue;tmp++; f[fx]=fy; o=max(o,E[i].w);if (tmp==n-1) break;}if (tmp!=n-1) return -1;else return o; } int main() {int T=read();while (T--) {n=read();m=read();for (int i=1;i<=m;i++) {int u=read(),v=read(),w=read(); E[i]=(node){u,v,w};}sort(E+1,E+1+m,cmp);int ans=-1;for (int i=1;i<=m;i++) {int t=MST(E[i].w);if (t==-1) continue;if (ans==-1) ans=t-E[i].w;else ans=min(ans,t-E[i].w);}printf("%d\n",ans);}return 0; } min.cpp

Problem C 數字分組

個體互異而值可能相同$n$個數$a_i$劃分為若干組。?對于某一組記下這組元素的極差(最大數-最小數)

一種合法的劃分要求每一組元素極差的和有$\leq M$的限制。求出所有合法劃分的總數$mod \ 10^9 + 7$的值。

對于20%的數據 ，$1 \leq n \leq 10$ ;?對于另外20%的數據，$M=0$

對于100%的數據，$1 \leq n \leq 200,0 \leq M \leq 1000,1 \leq a_i \leq 500 $

Sol : 對于20%數據直接第二類斯特林數求和然后乘起來即可。

　　對于100%的數據考慮DP。

　　先對數據排序，記$f_{i,j,k}$表示前$i$個數，還有$j$個劃分集可以添加元素，當前差值和為$k$方案總數。

　　首先，顯然即將添加的數$a_i$一定比之前添加的所有數要大，所以對于每一個沒有完全劃分好的集合都有貢獻。首先計算當前差值的和是多少，我們會向每一個沒有劃分好的集合中添加一個差值$a_i - a_{i-1}$ ， 所以當前差值的和就是$k + (a_i - a_{i-1})\times j$.

　　這是因為每一組的最值差就是這一組當中最大值和最小值之間所有數的差的和 。

　　所以這$j$組由于沒有被劃分好，就需要向里面添加這個差值$a_i - a_{i-1}$?

　　考慮新添加這個元素作為一個新的分組的開始：$f_{i,j+1,v} += f_{i-1,j,k}$

　　考慮新添加的這個元素作為一個新的分組的開始和結束：$f_{i,j,v} += f_{i-1,j,k}$

　　考慮新添加的元素作為之前一個舊的還沒劃分好的組的非結束的元素:$f_{i,j,v} += f_{i-1,j,k}\times j$ ($j \neq??0 $)

　　考慮新添加的元素作為之前一個舊的還沒劃分好的組的結束元素$f_{i,j-1,v} += f_{i-1,j,k}\times j$?($j \neq??0 $)

　　注意到這里枚舉的狀態$k$表示的是由那一維狀態轉移過來的狀態$k$

　　用滾動數組實現就可以排除空間限制。

　　復雜度$O(n^2k)$

# pragma GCC optimize(3) # include <bits/stdc++.h> # define int long long using namespace std; const int mo=1e9+7; int f[2][205][1005]; int a[205]; int n,w; signed main() {scanf("%lld%lld",&n,&w);for (int i=1;i<=n;i++) scanf("%lld",&a[i]);sort(a+1,a+1+n);int p=0; f[p][0][0]=1; for (int i=1;i<=n;i++) {p^=1; memset(f[p],0,sizeof(f[p]));for (int j=0;j<=i;j++)for (int k=0;k<=w;k++) {int v=(a[i]-a[i-1])*j+k;if (v>w) continue;f[p][j+1][v]+=f[p^1][j][k]; f[p][j+1][v]%=mo;f[p][j][v]+=f[p^1][j][k];f[p][j][v]%=mo;if (j) {f[p][j][v]+=f[p^1][j][k]*j; f[p][j][v]%=mo;f[p][j-1][v]+=f[p^1][j][k]*j;f[p][j-1][v]%=mo;} } }int ret=0;for (int k=0;k<=w;k++)ret+=f[p][0][k],ret%=mo;printf("%lld\n",ret); return 0; } grp.cpp

?

轉載于:https://www.cnblogs.com/ljc20020730/p/11170096.html

總結

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

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