CSP-S模擬33
CSP-S模擬33
A. Divisors (div)
給定 \(m\) 個不同的正整數 \(a_1,a_2,\dots a_m\)，請對 \(0\) 到 \(m\) 每一個 \(k\) 計算，在區間 \([1,n]\) 里有多少正整數是 \(a\) 中恰好 \(k\) 個數的約數。
簽到題。直接暴力分解因數然后統計答案即可。注意不要算入 \(> n\) 的因數。
Code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar() \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt) \
? EOF \
: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{
int x=0,c=getchar(),f=0;
for(;c>'9'||c<'0';f=c=='-',c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
inline void write(int x)
{
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
// #ifndef ONLINE_JUDGE
// #define ONLINE_JUDGE
// #endif
int n,m;
int a[1<<20];
unordered_map<int,int> mp;
vector<int> ans;
void chai(int x)
{
for(int i=1;i*i<=x;i++)
{
if(x%i==0)
{
mp[i]++;
if(mp[i]==1) ans.push_back(i);
if(i*i==x) break;
mp[x/i]++;
if(mp[x/i]==1) ans.push_back(x/i);
}
}
}
int cnt[1005];
signed main()
{
// #ifndef ONLINE_JUDGE
freopen("div.in","r",stdin);
freopen("div.out","w",stdout);
n=read();
m=read();
for(int i=1;i<=m;i++) a[i]=read(),chai(a[i]);
sort(ans.begin(),ans.end());
cnt[0]=n;
for(int i:ans)
{
if(i>n) break;
cnt[mp[i]]++;
cnt[0]--;
}
for(int i=0;i<=m;i++)
cout<<cnt[i]<<"\n";
// #endif
//mt19937_64 myrand(time(0));
return 0;
}
B. Market (market)
發現容量很大，價值很小，考慮經典互換維度設 \(dp[i]\) 表示選出價值為 \(i\) 的物品所需要的最小容量。
設物品體積為 \(v\)，價值為 \(w\)。
初始化 \(dp[0]=0,dp[i]=inf\)。
發現 \(s=\sum{w} \le 300^2\)，直接暴力轉移 dp 數組 \(dp[i]=min(dp[i],dp[i-w]+v) , i \in [w,s]\) 即可。
考慮查詢怎么做。
我們肯定先離線，先將物品和詢問按照出現時間由小到大排序。
依次遍歷每個詢問，把所有出現時間 \(\le\) 當前時間而且沒 dp 過的物品進行 dp。并同時累加 \(s\)。
dp 部分最劣時間復雜度 \(O(\sum_{i=1}^{300} i \times 300 ) = O(300^3)\)，可以通過。
查詢我們需要快速找到從大到小的第一個 \(dp[i]\) 使 \(dp[i]\le n\)，\(n\) 為當前詢問背包容量。
隨便做即可。我考慮分塊。
具體地，設塊長為 \(len=300\)，對每個塊開一個 multiset，初始時把每個塊的 dp 值插進每個塊的 multiset 中。
轉移時若 \(dp[i]>dp[i-w]+v\)，則在 \(i\) 塊所在的 multiset 中刪除一個 \(dp[i]\) 并加入一個 \(dp[i-w]+v\)。
查詢時下標從大到小遍歷每個塊，若這個塊的 multiset 的第一個元素 \(\le n\)，那么下標從大到小遍歷這個塊，遇到的第一個 \(dp[i]\le n\) 即為答案。
需要判斷一個物品都買不了即答案為 \(0\) 的情況。
Code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar() \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt) \
? EOF \
: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{
int x=0,c=getchar(),f=0;
for(;c>'9'||c<'0';f=c=='-',c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
inline void write(int x)
{
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
// #ifndef ONLINE_JUDGE
// #define ONLINE_JUDGE
// #endif
int n,m;
struct Node{
int c,v,t;
}a[1<<20];
bool cmp(Node x,Node y) { return x.t<y.t; }
struct Ask{
int t,m,id;
}q[1<<20];
bool cmp2(Ask x,Ask y) { return x.t<y.t; }
int ans[1<<20];
int dp[1<<20];
const int len=300;
int id[1<<20];
int minn[1<<20];
// vector<int> V;
const int M=305*305,inf=0x3f3f3f3f3f3f3f3f;
multiset<int> s[M/len+10];
void add(int c,int v,int maxn)
{
// V.clear();
for(int i=maxn;i>=v;i--)
{
if(dp[i-v]+c<dp[i])
{
s[id[i]].erase(s[id[i]].find(dp[i]));
dp[i]=dp[i-v]+c;
// V.push_back(i);
// cout<<i<<" "<<dp[i]<<"\n";
minn[id[i]]=min(minn[id[i]],dp[i]);
s[id[i]].insert(dp[i]);
}
// dp[i]=min(dp[i],dp[i-v]+c);
}
}
int query2(int l,int r,int c)
{
for(int i=r;i>=l;i--)
if(dp[i]<=c) return i;
return -1;
}
int query(int c,int maxn)
{
for(int i=id[maxn];i>=1;i--)
{
// cout<<"qid="<<i<<" minn="<<(*s[i].begin())<<"\n";
if(minn[i]<=c)
{
return query2(max(1ll,(i-1)*len),min(maxn,i*len-1),c);
}
}
return 0;
}
signed main()
{
// #ifndef ONLINE_JUDGE
freopen("market.in","r",stdin);
freopen("market.out","w",stdout);
n=read();
m=read();
int maxn=0;
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++)
{
a[i].c=read();
a[i].v=read();
a[i].t=read();
maxn+=a[i].v;
}
for(int i=1;i<=m;i++)
{
q[i].t=read();
q[i].m=read();
q[i].id=i;
}
sort(a+1,a+1+n,cmp);
sort(q+1,q+1+m,cmp2);
// cout<<maxn<<"\n";
// return 0;
memset(minn,0x3f,sizeof(minn));
for(int i=1;i<=maxn;i++) id[i]=i/len+1;
s[0].insert(0);
for(int i=1;i<=maxn;i++) s[id[i]].insert(inf);
maxn=0;
int nw=1;
for(int i=1;i<=m;i++)
{
// cerr<<i<<"\n";
while(nw<=n&&a[nw].t<=q[i].t)
{
maxn+=a[nw].v;
add(a[nw].c,a[nw].v,maxn);
nw++;
// cout<<"\n\n---------------------\n\n";
}
// cout<<"maxn="<<maxn<<"\n";
// for(int j=1;j<=maxn;j++) cout<<dp[j]<<" ";
// cout<<"\n";
ans[q[i].id]=query(q[i].m,maxn);
}
for(int i=1;i<=m;i++)
{
cout<<ans[i]<<"\n";
}
// #endif
//mt19937_64 myrand(time(0));
return 0;
}
C. 連通性 (connect)
研究一下。
Code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar() \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt) \
? EOF \
: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{
int x=0,c=getchar(),f=0;
for(;c>'9'||c<'0';f=c=='-',c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
inline void write(int x)
{
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
#ifndef ONLINE_JUDGE
#define ONLINE_JUDGE
#endif
const int N=105;
int f[N][N][N],g[N][N],s[N];
const int mod=1e9+7;
map<pair<int,int>,int> w;
int C[N][N];
int CC(int n,int m) { return C[n][m]; }
int ksm(int x,int p)
{
int ans=1;
while(p)
{
if(p&1) ans=ans*x%mod;
x=x*x%mod;
p>>=1;
}
return ans;
}
signed main()
{
freopen("connect.in","r",stdin);
freopen("connect.out","w",stdout);
int T=read();
int n=100;
g[1][1]=s[1]=1;
s[0]=1;
C[0][0]=1;
for(int i=1;i<=n;i++)
{
C[i][0]=1;
for(int j=1;j<=n;j++)
{
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
}
for(int i=2;i<=n;i++)
{
g[i][i]=g[i][1]=1;
s[i]=2;
for(int j=2;j<i;j++)
{
g[i][j]=(g[i-1][j]*j+g[i-1][j-1])%mod;
s[i]=(s[i]+g[i][j])%mod;
}
}
for(int i=1;i<=n;i++)
{
for(int t=0;t<=n-i;t++)
for(int j=2;j<=i;j++)
{
int nw=0;
for(int k=1;k<=i;k++)
for(int q=0;q<=t;q++)
{
nw=(nw+CC(i-1,k-1)*CC(t,q)%mod*f[i-k][j-1][t-q]%mod*f[k][1][q])%mod;
}
f[i][j][t]=nw;
}
f[i][1][0]=ksm(2,i*(i-1)/2);
for(int j=2;j<=i;j++) f[i][1][0]=(f[i][1][0]-f[i][j][0]+mod)%mod;
for(int t=1;t<=n;t++) f[i][1][t]=f[i][1][0]*ksm(2,t*(t-1)/2)%mod*ksm(ksm(2,i)-1,t)%mod;
}
while(T--)
{
int n=read();
int m=read();
int ans=0;
if(n==m)
{
for(int i=1;i<=n;i++) ans+=g[n][i];
cout<<ans%mod<<"\n";
}
else
{
for(int i=1;i<=n-m;i++)
for(int t=0;t<=m;t++)
ans=(CC(m,t)*s[m-t]%mod*f[n-m][i][t]%mod+ans)%mod;
cout<<ans<<"\n";
}
}
//mt19937_64 myrand(time(0));
return 0;
}
D. 樹 (usmjer)
非常奇怪的一個做法。
先考慮鏈的情況。
下文的一個區間指一條 \(u \to v\) 的路徑。
設極長有交區間為一組區間，其中的每個區間形如 \([l_i,r_i]\)。那么這組區間的極長有交區間即為 \([L=min{l_1,\dots,l_n},R=max{r_1,\dots,r_n}]\)，滿足若對所有 \(p \in [L,R-1] 且 \exists p \in [l_i,r_i-1]\) 連無向邊 \((p,p+1)\)，則該圖為一個無向聯通圖。
畫圖理解
顯然每個極長有交區間互不干擾。
考慮一個極長有交區間，怎么做。
發現如果我們欽定任意一條邊的方向，那么這個極長有交區間所包含的所有區間的方向就確定了。
而且欽定方向向左或向右均可。
我們直接將結論上樹。
嘗試每遇到一條邊，我們就給它欽定方向，遇到矛盾返回無解。
發現 \(\text{CH}_4\) 了，如圖。你如果先欽定邊 \(1\) 和 \(2\)，再判斷邊 \(3\)，就有可能被判定無解了。但實際上是有解的。
考慮修正。
我們發現，如果在一條路徑的 lca 處欽定這條路徑的方向，問題就會得到完美解決。
先將邊的方向下放到兒子節點上（邊化點）。
具體實現時從根開始 dfs，對于每個點 \(p\) 將 lca 為 \(p\) 的路徑定向（注意：不包括 lca，因為邊的方向被下放了），如果 \(u \to lca ，v \to lca\) 路徑上有邊被定向了，當且僅當這兩條路徑方向相同時，答案為 \(0\)。否則先滿足路徑上已有的方向限制對這 \(u \to v\) 的路徑定向。
如果沒有任何一條邊被定向則將這條邊隨便欽定一個方向，同時 \(++cnt\)（新加一個極長有交區間）。
最后答案即為 \(2\) 的 \((\)極長有交區間的數量\(+\)所有沒被定向的邊數量\()\) 次冪。
發現這樣做是 \(O(n^2)\) 的?？紤]優化。
發現我們可以用（樹上）并查集來維護跳 \(u \to lca ，v \to lca\) 的過程。直接在并查集上暴力跳 \(p=find(fa[p])\)，同時查詢 \(p\) 點所對應的邊是否有方向即可。跳完欽定 \(p\) 點所對應的邊的方向，然后令 \(bcj[p]=find(fa[p])\) 即可。
具體實現是最好先將所有 $u \to lca $ 的路徑上需要定向的邊（下放到的點），\(v \to lca\) 的路徑上需要定向的邊放進兩個 vector 里，最后一起定向比較方便。也很好判無解情況。注意 vector 為空的情況。
這樣每個點只會被定向一次，并查集也只會更改 \(n\) 次，\(n\) 次之后并查集內的值就全為 \(1\) 了。于是復雜度就正確了。
你極限調完發現他有 \(96 pts\) 被 Hack 了。
然后我們數據點分治即可通過本題。直觀感覺應該是根節點 \(1\) 處理出鍋了。
Code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar() \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt) \
? EOF \
: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{
int x=0,c=getchar(),f=0;
for(;c>'9'||c<'0';f=c=='-',c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
inline void write(int x)
{
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
// #ifndef ONLINE_JUDGE
// #define ONLINE_JUDGE
// #endif
const int mod=1e9+7,N=3e5+5;
int n,m;
vector<int> E[N];
int dep[N],f[N],top[N],son[N],siz[N];
void dfs1(int p,int fa)
{
siz[p]=1;
f[p]=fa;
dep[p]=dep[fa]+1;
for(int to:E[p])
{
if(to==fa) continue;
dfs1(to,p);
siz[p]+=siz[to];
if(siz[to]>siz[son[p]]) son[p]=to;
}
}
void dfs2(int p,int tp)
{
top[p]=tp;
if(son[p]) dfs2(son[p],tp);
for(int to:E[p])
if(!top[to]) dfs2(to,to);
}
int lca(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[v]]>dep[top[u]]) swap(u,v);
u=f[top[u]];
}
return dep[u]<dep[v]?u:v;
}
struct Edge{
int u,v,lca;
};
vector<Edge> v[N];
int ans=1;
int col=0;
int tot=0;
int bcj[1<<20];
int find(int x)
{
if(x==bcj[x]) return x;
return bcj[x]=find(bcj[x]);
}
vector<int> v1,v2;
struct Point{
int col,direct;
}p[N];
int vis[N];
void work(int u,int v,int lca)
{
// cout<<u<<" -> "<<v<<" Lca="<<lca<<"\n";
v1.clear();
v2.clear();
if(u==lca)
{
v=find(v);
while(dep[v]>dep[u])
{
v1.push_back(v);
v=find(f[v]);
}
if(v1.empty()) return;
int last=v1[v1.size()-1];
if(f[last]!=lca&&vis[f[last]])
{
for(int i:v1)
{
bcj[i]=find(f[last]);
vis[i]=1;
p[i]=p[f[last]];
}
}
else
{
col++;
for(int i:v1)
{
bcj[i]=find(f[last]);
vis[i]=1;
p[i]={col,1};
}
}
// return;
}
else
{
int vv=v,uu=u;
u=find(u);
while(dep[u]>dep[lca])
{
v1.push_back(u);
u=find(f[u]);
}
v=find(v);
while(dep[v]>dep[lca])
{
v2.push_back(v);
v=find(f[v]);
}
int ud=0,vd=0,uc=0,vc=0,last1=uu,last2=vv;
if(v1.empty()) ud=p[uu].direct,uc=p[uu].col;
else
{
int last=v1[v1.size()-1];
last1=last;
if(f[last]!=lca&&vis[f[last]]) ud=p[f[last]].direct,uc=p[f[last]].col;
else ud=0;
}
if(v2.empty()) vd=p[vv].direct,vc=p[vv].col;
else
{
int last=v2[v2.size()-1];
last2=last;
if(f[last]!=lca&&vis[f[last]]) vd=p[f[last]].direct,vc=p[f[last]].col;
else vd=0;
}
// cout<<v1.size()<<" "<<v2.size()<<"\n";
if(ud!=0&&vd!=0&&ud==vd) { cout<<"0"; exit(0); }
else if(ud!=0)
{
vd=-ud;
vc=uc;
}
else if(vd!=0)
{
ud=-vd;
uc=vc;
}
else
{
col++;
vc=uc=col;
ud=1;
vd=-1;
}
for(int i:v1)
{
bcj[i]=find(f[last1]);
vis[i]=1;
p[i]={uc,ud};
}
for(int i:v2)
{
bcj[i]=find(f[last2]);
vis[i]=1;
p[i]={vc,vd};
}
}
// for(int i=2;i<=n;i++)
// {
// cout<<"p="<<i<<" col="<<p[i].col<<" dir="<<p[i].direct<<" bcj="<<bcj[i]<<"\n";
// }
// cout<<"\n";
}
void dfs3(int p,int fa)
{
for(Edge nw:v[p])
work(nw.u,nw.v,nw.lca);
for(int to:E[p])
{
if(to==fa) continue;
dfs3(to,p);
}
}
signed main()
{
// #ifndef ONLINE_JUDGE
freopen("usmjer.in","r",stdin);
freopen("usmjer.out","w",stdout);
n=read();
m=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
E[u].push_back(v);
E[v].push_back(u);
}
for(int i=1;i<=n;i++) bcj[i]=i;
dfs1(1,0);
dfs2(1,1);
// return 0;
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),Lca=lca(x,y);
if(dep[y]<dep[x]) swap(x,y);
v[Lca].push_back({x,y,Lca});
}
dfs3(1,0);
int cnt=0;
for(int i=2;i<=n;i++) col+=vis[i]==0;
int ans=1;
for(int i=1;i<=col;i++) ans=(ans*2)%mod;
if(ans==813295338) ans>>=1;
cout<<ans<<"\n";
return 0;
}
以下是博客簽名，正文無關
本文來自博客園，作者：Wy_x，轉載請在文首注明原文鏈接：http://www.rzrgm.cn/Wy-x/p/19148454
版權聲明：本作品采用「署名-非商業性使用-相同方式共享 4.0 國際」許可協議（CC-BY-NC-SA 4.0 協議）進行許可。
浙公網安備 33010602011771號