【做題記錄】2025刷題計劃-數學2
A. 「NOI2015」壽司晚宴
考慮一個 \(500\) 以內的數，頂多有一個大于 \(19\) 的質因子。那么對于所有數按照這個大質因子分類，同一個大質因子只能分給同一個人。對于剩下 \(8\) 個質因子狀壓 DP 即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define gcd __gcd
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=505,uS=(1<<8)-1;
const int prm[]={2,3,5,7,11,13,17,19};
int n,mod,dp[maxn][maxn];
int f1[maxn][maxn],f2[maxn][maxn];
vector<int> sta[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>mod;
for(int i=2,x,S;i<=n;i++){
x=i,S=0;
for(int j=0;j<=7;j++){
if(x%prm[j]==0){
S|=1<<j;
while(x%prm[j]==0){
x/=prm[j];
}
}
}
sta[x].pb(S);
}
// for(int i=1;i<=n;i++){
// cout<<i<<": ";
// for(int j:sta[i]){
// cout<<bitset<10>(j)<<" ";
// }
// puts("");
// }
dp[0][0]=1;
for(int S:sta[1]){
for(int S1=uS;~S1;S1--){
for(int S2=uS;~S2;S2--){
if((S&S2)==0){
(dp[S1|S][S2]+=dp[S1][S2])%=mod;
}
if((S&S1)==0){
(dp[S1][S2|S]+=dp[S1][S2])%=mod;
}
}
}
}
for(int i=2;i<=n;i++){
if(sta[i].empty()){
continue;
}
for(int j=0;j<=uS;j++){
for(int k=0;k<=uS;k++){
f1[j][k]=f2[j][k]=dp[j][k];
}
}
for(int S:sta[i]){
for(int S1=uS;~S1;S1--){
for(int S2=uS;~S2;S2--){
if((S&S2)==0){
(f1[S1|S][S2]+=f1[S1][S2])%=mod;
}
if((S&S1)==0){
(f2[S1][S2|S]+=f2[S1][S2])%=mod;
}
}
}
}
for(int j=0;j<=uS;j++){
for(int k=0;k<=uS;k++){
dp[j][k]=(f1[j][k]+f2[j][k]-dp[j][k])%mod;
dp[j][k]=(dp[j][k]+mod)%mod;
}
}
}
int ans=0;
for(int i=0;i<=uS;i++){
for(int j=0;j<=uS;j++){
// cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
(ans+=dp[i][j])%=mod;
}
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
C. 隨機漫游
看到 \(n\le 18\)，基本上是要做狀壓的。考慮進行預處理，然后在較小的復雜度內回答詢問。設 \(f_{S,u}\) 表示當前走完了 \(S\) 中的點，現在在 \(u\) 點（\(u\in S\)），走完剩下的點的期望步數。于是有方程：
\[f_{S,u}=1+\frac{1}{d_u}\sum f_{S\cup\{v\},v}
\]
其中 \((u,v)\) 是一條邊，\(d_u\) 表示 \(u\) 的度數。
考慮 \(S\) 與 \(S\cup\{v\}\) 的關系，顯然只有兩種情況，分別是 \(S=S\cup\{v\}\) 和 \(S\subsetneqq S\cup\{v\}\)。于是就可以倒著掃 \(S\)，對于每個 \(S\) 做高斯消元了。
考慮輸出答案，題目的要求其實就是要將 \(c\) 中的點全部走完。設 \(c\) 中的點構成的集合為 \(S\)，起點為 \(u\)，那么答案即為 \(f_{(\complement S)\cup\{u\},u}\)。總時間復雜度為 \(O(2^nn^3+m)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int mod=998244353;
int n,m,q,a[25][25];
int f[(1<<18)+5][25];
vector<int> e[25];
il int qpow(int x,int y){
// cout<<x<<" "<<y<<"\n";
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
y>>=1,x=x*1ll*x%mod;
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
// ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
e[u].pb(v),e[v].pb(u);
}
int uS=(1<<n)-1;
for(int S=uS-1;S;S--){
for(int i=1;i<=n;i++){
for(int j=1;j<=n+1;j++){
a[i][j]=0;
}
}
for(int u=1,tmp;u<=n;u++){
if(S>>(u-1)&1){
a[u][u]=mod-1;
tmp=qpow(e[u].size(),mod-2);
for(int v:e[u]){
if(S>>(v-1)&1){
a[u][v]=tmp;
}
else{
a[u][n+1]=(a[u][n+1]-f[S|1<<(v-1)][v]+mod)%mod;
}
}
a[u][n+1]=(a[u][n+1]*1ll*tmp+mod-1)%mod;
}
}
for(int i=1,cur,tmp;i<=n;i++){
if(S>>(i-1)&1){
tmp=0;
for(int j=i;j<=n;j++){
if(S>>(j-1)&1){
if(tmp<a[j][i]){
tmp=a[j][i],cur=j;
}
}
}
swap(a[i],a[cur]);
tmp=qpow(a[i][i],mod-2);
for(int j=1;j<=n;j++){
if(i!=j&&(S>>(j-1)&1)){
for(int k=i+1;k<=n+1;k++){
if((S>>(k-1)&1)||k==n+1){
a[j][k]=(a[j][k]-a[j][i]*1ll*a[i][k]%mod*tmp%mod+mod)%mod;
}
}
}
}
}
}
for(int i=1;i<=n;i++){
if(S>>(i-1)&1){
f[S][i]=a[i][n+1]*1ll*qpow(a[i][i],mod-2)%mod;
}
}
}
cin>>q;
while(q--){
int num,S=0,u;
cin>>num;
while(num--){
cin>>u;
S|=1<<(u-1);
}
cin>>u;
cout<<f[(uS^S)|1<<(u-1)][u]<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
D. [JLOI2014] 路徑規劃
首先計算在紅綠燈 \((a,b)\) 處期望的等待時間。記 \(a+b\) 為一個周期（即先有時長為 \(a\) 的紅燈，再有時長為 \(b\) 的綠燈），設我們在 \(x\) 時刻到達了這個紅綠燈，那么我們需要等待的時間顯然為 \(\max(a-x,0)\)。
要求出期望，就要用上面那個函數的和再除以總時長，也就是 \(\frac{a^2}{2(a+b)}\)。于是這道題就變成了一道普通的圖論問題。
考慮分層圖，一共建 \(k+1\) 層圖，在每個紅綠燈處向上一層連邊。考慮答案路徑，一定是從起點開始再若干個加油站加油再走到終點的過程，而加油站與加油站之間怎么走我們是不用管它的。那么我們就以每個加油站為起點跑最短路，將所有加油站抽出來，在限制內能走到另一個加油站就在新圖上連邊。最后再在新圖上跑一次最短路即可。
時間復雜度 \(O(50kn\log kn)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define id(x,y) ((x)+n*((y)-1))
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
int n,m,_k,lim,cst;
double dis[maxn],out[maxn];
bool gas[maxn],vis[maxn];
map<string,int> hao;
vector<pair<int,double> > e1[maxn],e2[maxn];
priority_queue<pair<double,int> > q;
il void dijkstra(int s,auto &e){
for(int i=1;i<=n*(_k+1);i++){
dis[i]=1e18,vis[i]=0;
}
dis[s]=0,q.push(mp(0,s));
while(q.size()){
int u=q.top().sec;
q.pop();
if(vis[u]){
continue;
}
vis[u]=1;
for(auto i:e[u]){
int v=i.fir;
double w=i.sec;
if(!vis[v]&&dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(mp(-dis[v],v));
}
}
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>_k>>lim>>cst;
for(int i=1,a,b;i<=n;i++){
string s;
cin>>s>>a>>b;
hao[s]=i;
gas[i]=~s.find("gas");
if(a){
// cout<<i<<"\n";
out[i]=a*1.0*a/2/(a+b);
}
}
int st=hao["start"],ed=hao["end"];
for(int i=1,u,v,w;i<=m;i++){
string a,b,c;
cin>>a>>b>>c>>w;
u=hao[a],v=hao[b];
for(int j=1;j<=_k+1;j++){
if(out[u]){
if(j<=_k){
e1[id(u,j)].pb(mp(id(v,j+1),w+out[u]));
}
}
else{
e1[id(u,j)].pb(mp(id(v,j),w));
}
if(out[v]){
if(j<=_k){
e1[id(v,j)].pb(mp(id(u,j+1),w+out[v]));
}
}
else{
e1[id(v,j)].pb(mp(id(u,j),w));
}
}
}
for(int i=1;i<=n;i++){
if(i==st||gas[i]){
// cout<<i<<"---";
dijkstra(i,e1);
for(int j=1;j<=n;j++){
if(gas[j]){
for(int k=1;k<=_k+1;k++){
if(dis[id(j,k)]<=lim){
for(int x=1,y=k;y<=_k+1;x++,y++){
e2[id(i,x)].pb(mp(id(j,y),dis[id(j,k)]+cst));
// cout<<id(i,x)<<" "<<id(j,y)<<" "<<dis[id(j,k)]+cst<<"\n";
}
}
}
}
else if(j==ed){
for(int k=1;k<=_k+1;k++){
if(dis[id(j,k)]<=lim){
for(int x=1,y=k;y<=_k+1;x++,y++){
e2[id(i,x)].pb(mp(id(j,y),dis[id(j,k)]));
// cout<<id(i,x)<<" "<<id(j,y)<<" "<<dis[id(j,k)]<<"\n";
}
}
}
}
}
}
}
dijkstra(st,e2);
double ans=1e18;
for(int i=1;i<=_k+1;i++){
// cout<<dis[id(ed,i)]<<"\n";
ans=min(ans,dis[id(ed,i)]);
}
printf("%.3f",ans);
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號