10.24模擬賽
チーム分け
題意
每個點有限制形如這個點分的組人數 \(\le a_i\)，問合法方案數。\(n\le 1000\)
題解
一個組內的限制只與 \(a_i\) 最小的元素相關，不妨將 \(a_i\) 從大到小排序延后計算貢獻。
設 \(dp_{i,j}\) 表示考慮完前 \(i\) 個人，有 \(j\) 個人沒有參與匹配的方案數，答案為 \(dp_{n,0}\)。轉移的話：
- 第 \(i\) 個人不匹配。\(dp_{i,j}\gets dp_{i-1,j-1}\)。
- 第 \(i\) 個人新開一組。枚舉前面有多少人和我放在一組，乘上一個組合數轉移。即對 \(k\in [0,a_i-1]\)，有 \(dp_{i,j}\gets dp_{i-1,j+k}\times \binom{j+k}{k}\)。
還有 \(O(n^2\log n)\) 的做法。考慮直接枚舉大小恰為 \(i\) 的集合有多少個。設 \(dp_{i,j}\) 表示考慮完大小 \(\ge i\) 的集合，剩余 \(j\) 個數沒有匹配的方案數，每次枚舉選出多少個大小為 \(i\) 的集合進行轉移。
code：
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=2010,mod=1e9+7;
int n,m,k,T,a[N],w[N],f[N][N],jie[N],ni[N],s[N];
int inv[N][N];
vector<int> g[N];
int ksm(int x,int k){
int ans=1;
while(k){
if(k&1) ans=ans*x%mod;
x=x*x%mod;k>>=1;
}return ans;
}
bool cmp(int a,int b){
return a>b;
}
int c(int n,int m){
return jie[m]*ni[n]%mod*ni[m-n]%mod;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
rep(i,1,n) cin>>a[i],w[a[i]]++;
jie[0]=1;
rep(i,1,n) jie[i]=jie[i-1]*i%mod;
ni[n]=ksm(jie[n],mod-2);
per(i,n-1,0) ni[i]=ni[i+1]*(i+1)%mod;
per(i,n,1) s[i]=s[i+1]+w[i];
f[n+1][0]=1;
rep(i,1,n){
rep(k,0,n/i){
inv[i][k]=ksm(ksm(jie[i],k)%mod,mod-2)%mod;
}
}
per(i,n,1){
rep(j,0,s[i]){
rep(k,0,n/i){
if(f[i+1][j+k*i-w[i]]&&j+k*i<=n&&j+k*i-w[i]>=0){
int x=c(k*i,j+k*i)*ni[k]%mod*jie[i*k]%mod*inv[i][k]%mod;
f[i][j]=(f[i][j]+f[i+1][j+k*i-w[i]]*x)%mod;
}
}
}
}cout<<f[1][0];
return 0;
}
Card Collector
題意
有一些物品，其有坐標和權值，現在有如下選擇：
- 第一輪：在每一行中至多選擇一個。
- 第二輪：在每一列中至多選擇一個。
問可獲得的最大值。
題解
賽時做法：
我們有一個思路，就是從大到小，判斷每個點能不能放在其中一輪中。
發現判斷這玩意的過程就是二分圖匹配，卡卡常就過 \(10^6\) 了。
code：
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int N=2e6+10;
int n,r,c,x,y,a[N],idx[N],fr[N];
int g[N][2],ma[N],tim,vis[N];
long long ans;
bool bfs(int u){
if(fr[u]) return 0;
int v=g[u][0];
if(vis[v]^tim){
vis[v]=tim;
if(!ma[v]||bfs(ma[v])){
ma[v]=u;fr[u]=0;
return 1;
}else fr[u]=1;
}v=g[u][1];
if(vis[v]^tim){
vis[v]=tim;
if(!ma[v]||bfs(ma[v])){
ma[v]=u;fr[u]=0;
return 1;
}else fr[u]=1;
}return 0;
}
bool cmp(int x,int y){return a[x]>a[y];}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>r>>c;
rep(i,1,n){
cin>>x>>y>>a[i];
g[i][0]=x;g[i][1]=y+r;idx[i]=i;
}sort(idx+1,idx+n+1,cmp);
rep(i,1,n){
int u=idx[i];tim++;
if(bfs(u)) ans+=a[u];
}cout<<ans;
return 0;
}
正經做法
還是先連邊，考慮把二分圖左右合并，那么我們可以發現任意合法情況每個圖都是基環樹森林，或者是一些森林混合基環樹。考慮最大生成樹和最大生成基環樹，這兩做法幾乎一樣，區別就是加了一個最大未選邊。
code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int N = 2e6+5;
int f[N],n,r,c;
bool tp[N];ll ans;
struct node{int u,v,w;}a[N];
int fd(int x){return x == f[x]?x:f[x] = fd(f[x]);}
char buf[1<<21],*p1,*p2;
inline int rd()
{
char c;int f = 1;
while(!isdigit(c = getchar()))if(c=='-')f = -1;
int x = c-'0';
while(isdigit(c = getchar()))x = x*10+(c^48);
return x*f;
}
int main()
{
freopen("oblivious.in","r",stdin);
freopen("oblivious.out","w",stdout);
n = rd();r = rd();c = rd();
for(int i = 1;i <= r+c;i++)f[i] = i;
for(int i = 1;i <= n;i++)a[i] = {rd(),rd()+r,rd()};
sort(a+1,a+n+1,[](node x,node y){return x.w > y.w;});
for(int i = 1;i <= n;i++)
{
int u = fd(a[i].u),v = fd(a[i].v),w = a[i].w;
if(u != v){if(!tp[u]||!tp[v])ans += w,tp[u] |= tp[v],f[v] = u;}
else if(!tp[u])tp[u] = 1,ans += w;
}
cout << ans << endl;
return 0;
}
Bitaro's Travel 2
題意
給一個矩形，每個坐標有點權，代表高度。
現在有一種操作叫跳高，具體為：
- 上升到 \(x+L+0.5\) 的位置。
- 保持當前高度不變，重復向四個相鄰方向（上下左右）移動。途經的所有單元格的山峰高度必須低于當前海拔。
- 降落到某一點。
現在有詢問形如 \((a,b)\to(c,d)\) 的最小跳高次數，若不可到達輸出 \(-1\)。
\(n\le 3\times 10^5\)
題解
有結論：一次跳高只可能使得可以到達的點增加，不會使原來可以到達的點無法到達。
于是考慮在查詢時如何快速得知從起點到終點需要經過的最高的山的最低高度 \(h\)（也就是說，只要在跳躍過程中跳到了這個高度即可）。這是一個經典問題，可以使用 Kruskal 重構樹簡單地求解。
接下來處理每次最多跳 \(L\) 的限制。根據上面的結論，除了最后一次跳躍，每次貪心地跳到當前能跳到的最高的山是正確的。對于每個坐標 \((x,y)\) 處理出 \(\mathrm{nx}_{x,y}\) 表示 \((x,y)\) 跳一次可以到達的最高的山的坐標，發現這個東西可以倍增；于是對于每個詢問就能求出最少跳幾次可以到達高度 \(h\)。將這個答案 \(+1\) 即為最終答案。
\(\mathrm{nx}_{x,y}\) 可以用掃描線的技巧處理。把所有山按照高度排序，從低到高掃描所有的高度 \(h'\)：對于高度 \(<h'-L\) 的山找出當前加入過的山中與它連通的高度最大的山（可以使用并查集維護），作為其 \(\mathrm{nx}\) 的值；接著把 \(\le h'\) 且未加入的山加入，并與四聯通且已加入的其他山合并。
\(nx_{x,y}\) 還可以在遍歷重構樹的時候用一個 \(set\) 維護，因為某個點的 \(nx\) 一定在其重構樹的祖先上。這樣很好寫，考場上沒調出來，反思一下。
code：
#include<bits/stdc++.h>
#define pb push_back
#define tpi tuple<int,int,int>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=6e5+10;
int n,w[N],W,H,L,fa[N],dep[N],f[N][21],vis[N];
int mx[N][21],tot,ce[N],nw[N],q,ff[N][21];
vector<int> g[N];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int idx(int i,int j){
return (i-1)*W+j;
}
inline int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;f[u][0]=fa;
for(int i=1;(1<<i)<=dep[u];i++){
f[u][i]=f[f[u][i-1]][i-1];
}for(int v:g[u]){
if(v==fa) continue;
dfs(v,u);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
per(i,20,0){
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
}if(x==y) return x;
per(i,20,0){
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
}return f[x][0];
}
void getst(){
rep(i,1,20){
rep(j,1,n){
ff[j][i]=ff[ff[j][i-1]][i-1];
}
}
rep(i,1,20){
rep(j,1,n){
mx[j][i]=max(mx[j][i-1],mx[ff[j][i-1]][i-1]);
}
}
}
int solve(int x,int w){
int ans=0;
per(i,20,0){
if(mx[x][i]<w){
ans+=(1<<i);x=ff[x][i];
}
}if(mx[x][0]>=w) return ans+1;
return -1;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
vector<tpi> w,e;
cin>>H>>W>>L;tot=H*W;n=H*W;
rep(i,1,H){
rep(j,1,W){
int x;cin>>x;
ce[idx(i,j)]=x;
w.emplace_back(x,i,j);
rep(k,0,1){
int fx=i-dx[k],fy=j-dy[k];
if(fx<=0||fy<=0||fx>H||fy>W) continue;
int ww=max(ce[idx(i,j)],ce[idx(fx,fy)]);
e.emplace_back(ww,idx(i,j),idx(fx,fy));
}
}
}
sort(e.begin(),e.end());
sort(w.begin(),w.end());
rep(i,1,N-1) fa[i]=i;
for(auto t:e){
int w=get<0>(t),u=get<1>(t),v=get<2>(t);
if(find(u)!=find(v)){
u=find(u);v=find(v);
fa[u]=fa[v]=++tot;nw[tot]=w;
g[u].pb(tot);g[v].pb(tot);
g[tot].pb(u);g[tot].pb(v);
}
}int sum=0;
dfs(tot,0);
int l=0;rep(i,1,N-1) fa[i]=i;
for(auto t:w){
int ww=get<0>(t),x=get<1>(t),y=get<2>(t);
vis[idx(x,y)]=1;
while(get<0>(w[l])+L<ww){
int i=get<1>(w[l]),j=get<2>(w[l]);
mx[idx(i,j)][0]=ce[find(idx(i,j))];
ff[idx(i,j)][0]=find(idx(i,j));
l++;
}rep(k,0,3){
int fx=x+dx[k],fy=y+dy[k];
if(fx<=0||fy<=0||fx>H||fy>W) continue;
if(!vis[idx(fx,fy)]) continue;
fa[find(idx(fx,fy))]=idx(x,y);
}
}while(l<n){
int i=get<1>(w[l]),j=get<2>(w[l]);
ff[idx(i,j)][0]=find(idx(i,j));
mx[idx(i,j)][0]=ce[find(idx(i,j))];l++;
}getst();
cin>>q;
while(q--){
int a,b,c,d;
cin>>a>>b>>c>>d;
int res=nw[lca(idx(a,b),idx(c,d))];
cout<<solve(idx(a,b),res)<<'\n';
}
return 0;
}
Equalization
P7718 「EZEC-10」Equalization
題意
給你一個長為 \(n\) 的數組 \(a_1,a_2,\ldots,a_n\)。
你可以任選三個整數 \(l,r,x\ (1\le l\le r\le n\)，\(x\in \mathbb Z)\)，并將 \(a_l,a_{l+1},\ldots,a_r\) 均加上 \(x\)，稱為一次操作。
問最少進行幾次操作，才能使 \(a\) 中所有元素均相等？并求出能使操作次數最少的不同方案數。
由于方案數可能很大，請對 \(10^9+7\) 取模。
兩種方案相同，當且僅當兩方案每次操作選擇的 \((l,r,x)\) 均相同。
特別地，不進行任何操作也算一種方案。
對于 \(100\%\) 的數據，\(1\le n\le 18\)，\(-10^9\le a\le 10^9\)。
題解
首先看到區間操作我們可以想到差分轉換，將區間操作轉化為差分序列上的一個或兩個單點操作，具體來說我們設 \(b_i=a_{i+1}-a_i\)，那么對于一次形如 \(\forall i\in[l,r],a_i\leftarrow a_i+x\) 的操作三元組 \((l,r,x)\)，我們有：
- \(l=1,r=n\)，等于啥也沒干，那么我們顯然不會選擇這樣的區間進行操作，否則就會浪費一次操作次數，所以我們 duck 不必考慮這種情況。
- \(l=1,r\ne n\)：相當于令 \(b_{r}\leftarrow b_r-x\)
- \(l\ne 1,r=n\)：相當于令 \(b_{l-1}\leftarrow b_{l-1}+x\)
- \(l\ne 1,r\ne n\)：相當于令 \(b_{l-1}\leftarrow b_{l-1}+x,b_r\leftarrow b_r-x\)
于是問題轉化為：給定長度為 \(n-1\) 的差分序列，每次可以進行以下兩種操作之一：修改一個單點的值，或者指定三個整數 \(x,y,z\)，將 \(b_x\) 改為 \(b_x+z\)，\(b_y\) 改為 \(b_y-z\)，最少需要多少次操作才能將所有數變為 \(0\)。
直接處理不太容易，因此考慮挖掘一些性質。做過這道題的同學應該不難想到，我們可以在每次操作的兩個點之間連一條邊，如果咱們操作的是一個單點那么就連一條自環，這樣顯然會得到一張點數為 \(n-1\)，邊數等于操作次數的圖。那么有一個性質：在最優策略連出的圖中，對于每個連通塊 \((V',E')\)，記 \(S=\sum\limits_{x\in V'}b_x\)，有
- 如果 \(S=0\)，那么該連通塊必然是一棵樹，耗費 \(|V'|-1\) 次操作。
- 如果 \(S\ne 0\)，那么該連通塊必然是一棵樹加一個自環，耗費 \(|V'|\) 次操作。
證明不會，感性理解一下即可
觀察到這個性質之后，求解第一問就易如反掌了，注意到 \(n\) 很小，因此考慮狀壓，記 \(dp_S\) 表示將 \(S\) 中的元素變為 \(0\) 的最少操作次數，枚舉子集轉移即可，復雜度 \(3^{n-1}\)。
接下來考慮第二問，顯然每次操作都是不同的，因此我們可以只用考慮操作方案的集合有哪些，最后乘個操作次數的階乘即可。其次，如果我們能夠知道對于一個連通塊而言，將它按照最優策略變為 \(0\) 的方案數，我們就能用乘法原理一邊 DP 一遍記錄將每個集合變為 \(0\) 的最優策略的方案數了。因此考慮將每個集合變為 \(0\) 的方案數，還是分 \(S=0\) 和 \(S\ne 0\) 兩種情況處理：
- \(S=0\)，那么該連通塊是一棵無根樹，那么可以很自然地猜到應該跟什么有標號樹計數有關，Prufer 序列算一算結果是 \(|V'|^{|V'|-2}\)，事實上結論也的確如此，這里稍微口胡一下證明：顯然一個操作集合唯一對應一棵樹，而對于一棵無根樹而言，能夠得到它的操作集合也是唯一的，證明可以通過構造方案說明：我們假設這棵樹中編號最大（其實大不大無所謂，只要形成一個嚴格的偏序關系即可）的葉子節點為 \(u\)，與其相連的點為 \(v\)，那么我們必須讓 \(u\) 的權值變為 \(0\)，因為否則進行完此次操作之后，點 \(u\) 就孤立了，無法再次通過兩點的操作變回 \(0\) 了，因此這次操作 \(u\) 的權值必須減去 \(a_u\)，\(v\) 的權值也就必然加上 \(a_u\)，如此進行下去直到還剩一個點為止，而由于該連通塊中權值之和為 \(0\)，因此最終剩下的那個點權值也是 \(0\)，故我們構造出的方案合法。又因為我們每一次操作唯一，因此操作集合唯一；如果我們改變下操作的邊集的順序那么顯然操作集合不會變，因此操作集合與無根樹形成雙射關系，證畢。
- \(S\ne 0\)，其實不過是在無根樹的基礎上加了一個自環，加這個自環的侯選位置總共有 \(|V'|\) 個，再加上對于這個自環而言有兩個區間能夠改變差分序列上這個點的值（假設我們要改變 \(b_x\)，那么我們可以操作 \([1,x]\)，也可以操作 \([x+1,n]\)），因此還需乘個 \(2\)，總方案數 \(2|V'|^{|V'|-1}\)，如果你
力求極致、追求嚴謹，那么也可以仿照 \(S=0\) 的證明方式。
時間復雜度 \(\mathcal O(3^{n-1})\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,cnt,ans1,ans2,a[18],d[18],c[18],fact[18],power[18],f[1 << 17],g[1 << 17],v[1 << 17],val[1 << 17],bit[1 << 17],mod = 1e9 + 7;
inline ll read(){
ll s = 0,w = 1;
char ch = getchar();
while (ch < '0'|| ch > '9'){ if (ch == '-') w = -1; ch = getchar();}
while (ch >= '0'&& ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
return s * w;
}
ll qp(ll x,ll y){
ll a = 1,b = x;
while (y){
if (y & 1) a = a * b % mod;
b = b * b % mod,y >>= 1;
}
return a;
}
int main(){
n = read();
for (ll i = 0;i < n;i += 1) a[i] = read();
n -= 1;
for (ll i = 0;i < n;i += 1) d[i] = a[i + 1] - a[i];
c[0] = fact[0] = power[1] = 1;
for (ll i = 1;i <= n;i += 1) fact[i] = fact[i - 1] * i % mod;
for (ll i = 2;i <= n;i += 1) power[i] = qp(i,i - 2);
for (ll i = 1;i <= n + 1;i += 1) c[i] = 2 * qp(i + 2,i - 1) % mod;
for (ll i = 1;i < (1 << n);i += 1){
ll sum = 0;
for (ll j = 0;j < n;j += 1) if (i & (1 << j)) sum += d[j],bit[i] += 1;
if (!sum) f[i] = 1,g[i] = power[bit[i]];
}
for (ll i = 1;i < (1 << n);i += 1) if (f[i]){
bool fl = 1;
for (ll j = (i - 1) & i;j;j = (j - 1) & i) if (f[j]){fl = 0; break;}
val[i] = fl;
}
for (ll i = 1;i < (1 << n);i += 1) if (f[i]){
for (ll j = i;j;j = (j - 1) & i) v[j] = 0;
for (ll j = (i - 1) & i;j;j = (j - 1) & i) if (val[j] && !v[j]){
if (f[j] + f[i ^ j] > f[i]) f[i] = f[j] + f[i ^ j],g[i] = g[j] * g[i ^ j] % mod;
else if (f[j] + f[i ^ j] == f[i]) g[i] = (g[i] + g[j] * g[i ^ j] % mod) % mod;
for (ll k = (i ^ j);k;k = (k - 1) & (i ^ j)) v[k] = 1;
}
}
ans1 = n - *max_element(f,f + (1 << n));
if (ans1 == n){cout<<n<<endl<<c[n] * fact[ans1] % mod; return 0;}
for (ll i = 0;i < (1 << n);i += 1) if (f[i] == n - ans1) ans2 = (ans2 + g[i] * c[n - bit[i]] % mod) % mod;
cout<<ans1<<endl<<ans2 * fact[ans1] % mod;
return 0;
}
浙公網安備 33010602011771號