>天梯赛重复提交不会有任何惩罚！想怎么提交就怎么提交 > >能骗分的题务必去骗骗分，哪怕是猜答案，猜中一个也是分 > >没完整想法的题目，如果会暴力就先写暴力 本次模拟赛的难度可能会比正式赛偏高，大家不要太急慢慢练就行 从本场题目安排能够看出，是会存在有些简单题放在难题后面的情况的，如果前面的题被卡了的话务必去看看后边的题意先，或是跟跟榜，不要在一道题上死冲，如果被前面分值低的题目卡太久就太不划算了，可能后面的分值高的题几分钟就能写掉的 --- ## C语言：从入门到入土 判断 $n\times d$ 与 $x-y$ 的大小关系即可： - $n\times d\lt x-y$，能学完； - $n\times d = x-y$，刚好学完； - $n\times d\gt x-y$，不能学完。 --- ## 智能外卖柜 模拟即可。 --- ## 游戏收藏家 答案为 $\max(0.01,\min(20,w\times4.875\%))$. 注意题目要求在满足赚的钱在 $[0.01,20]$ 区间内的前提下，至少赚到 $w\times 4.875\%$ 元，且货币最小单位为 $0.01$ 元，因此需在小数点后两位向上取整。 这种题推荐转整数写法，只要有浮点数的存在就意味着会有误差。 *注意 `ceil` 函数可能存在误差，在某些情况下需要搭配 $eps$ 调试精度* ```cpp void solve1() { double x; scanf("%lf",&x); double d=max(0.01,min(20.0,x*0.04875)); if(d*100==(int)(d*100)) printf("%.2lf\n",x+d); else printf("%.2lf\n",x+((int)(d*100))/100.0+0.01); } void solve2() { double x; scanf("%lf",&x); double d=max(0.01,min(20.0,x*0.04875)); printf("%.2lf\n",x+ceil(d*100.0)/100.0); } void solve3() { char s[10]; scanf("%s",s); long long d=0; for(int i=0;s[i];i++) if(s[i]!='.') d=d*10+s[i]-'0'; ll mn=d+1,mx=d+2000; d*=104875; d=d/100000+(d%100000?1:0); d=max(mn,min(mx,d)); printf("%d.%02d\n",d/100,d%100); } ``` --- ## 热闹的朋友圈 将日期读作字符串，去除后三位字符后使用 $map$ 统计即可 ```cpp void solve() { int n; cin>>n; map<string,int> mp; rep(i,1,n) { string s; cin>>s; mp[s.substr(0,7)]++; } int mn=1e9,mx=0; for(auto it:mp) { mn=min(mn,it.second); mx=max(mx,it.second); } int cntmn=0,cntmx=0; for(auto it:mp) { if(it.second==mn) cntmn++; else if(it.second==mx) cntmx++; } cout<<mn<<' '<<cntmn; for(auto it:mp) if(it.second==mn) cout<<' '<<it.first; cout<<'\n'; cout<<mx<<' '<<cntmx; for(auto it:mp) if(it.second==mx) cout<<' '<<it.first; cout<<'\n'; } ``` --- ## 妙妙子日 较为经典的日期题型，预处理+二分/前缀和即可 ```cpp // 这份是二分，也可以使用前缀和进一步优化 #define rep(i,a,b) for(auto i=(a);i<=(b);i++) #define pb push_back vector<int> vec; void init() { rep(y,1000,2999) { int dm[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; if(y%4==0&&y%100!=0||y%400==0) dm[2]++; rep(m,1,12) { rep(d,1,dm[m]) { int t=y*10000+m*100+d,u=t,s=0; while(t>0) { s^=t%10; t/=10; } if(s==0) vec.pb(u); } } } } void solve() { init(); int T; cin>>T; while(T--) { string s1,s2; cin>>s1>>s2; int t1=stoi(s1.substr(0,4))*10000+stoi(s1.substr(5,2))*100+stoi(s1.substr(8,2)); int t2=stoi(s2.substr(0,4))*10000+stoi(s2.substr(5,2))*100+stoi(s2.substr(8,2)); cout<<upper_bound(all(vec),t2)-lower_bound(all(vec),t1)<<'\n'; } } ``` --- ## 载货汽车 分开考虑收入与支出 收入： - 路线补贴 $\frac{L_i}{100}\times V_i$ - 提早到达奖金 $\max(H_i-\frac{L_i}{S_i},0)\times U_i$ - 工资 $Z_i$ 支出： - 油价 $\frac{L_i}{100}\times W_i\times P_i$ - 车险 $\frac{L_i}{100}\times B_i$ - 交通费 $L_i\times G_i$ - 车辆维护 $F_i$ 相加后获得总收入 $X$ 与总支出 $Y$，算得净利率后取最高项即可。 ```cpp #define rep(i,a,b) for(auto i=(a);i<=(b);i++) #define repp(i,a,b) for(auto i=(a);i<(b);i++) #define pb push_back void solve() { int n; cin>>n; rep(i,1,n) { double L,P,W,V,B,G,F,S,H,U,Z; cin>>L>>P>>W>>V>>B>>G>>F>>S>>H>>U>>Z; double in=0,out=0; in+=(L/100.0)*V; in+=max(0.0,H-L/S)*U; in+=Z; out+=(L/100.0)*W*P; out+=(L/100.0)*B; out+=L*G; out+=F; va.pb(in-out); vb.pb((in-out)/in*100.0); } int p=0; repp(i,1,n) if(vb[p]<vb[i]) p=i; cout<<p+1<<' '<<va[p]<<' '<<vb[p]<<'\n'; } ``` --- ## 欢乐拍卖会 本质上就是重载排序方法，但可以借助 STL 默认的排序方法稍微投机取巧。 ```cpp #define rep(i,a,b) for(auto i=(a);i<=(b);i++) #define repp(i,a,b) for(auto i=(a);i<(b);i++) #define pb push_back struct node { string name; vector<int> vec; bool operator < (const node& a) const { int siz=min(vec.size(),a.vec.size()); repp(i,0,siz) if(vec[i]!=a.vec[i]) return vec[i]>a.vec[i]; if(vec.size()!=a.vec.size()) return vec.size()>a.vec.size(); /* 以上语句可直接简写为 if(vec!=a.vec) return vec>a.vec; */ return name<a.name; } }ar[10050]; void solve() { int n; cin>>n; rep(i,1,n) { cin>>ar[i].name; int m; cin>>m; while(m--) { int d; cin>>d; ar[i].vec.pb(d); } sort(all(ar[i].vec),greater<int>()); // 降序 } sort(ar+1,ar+n+1); rep(i,1,n) cout<<i<<' '<<ar[i].name<<'\n'; } ``` --- ## 还原FFT 由于原多项式每项的系数一定为 $0$ 或 $1$，不妨采用二进制枚举的方式枚举出两个序列。 但直接枚举+检查的时间复杂度在无解的情况下能达到 $O(2^n\cdot 2^n\cdot n^2)$，不足以完全通过本题。 考虑到题目给定的 $n$ 即结果序列的最高位，换言之我们输出的多项式的最高位次数之和应当等于 $n$. 因此在枚举完第一个序列后，根据最高位来求出第二个序列的最高位**必须**是哪一位，以缩小第二个序列的枚举范围。 时间复杂度在无解的情况下约 $O(\sum\limits_{i+j=n,i\ge 1,j\ge 1}2^i\cdot 2^j\cdot n^2)$，即 $O(2^n\cdot n^3)$. 但题目保证一定有解，因此第一个序列的最高位实际上枚举到 $\lfloor\frac n 2\rfloor$ 就够了，时间复杂度还能缩小一半。 ```cpp #define rep(i,a,b) for(auto i=(a);i<=(b);i++) #define per(i,a,b) for(auto i=(a);i>=(b);i--) int n,a[25],b[25],c[25],d[25]; void solve() { cin>>n; rep(i,0,n) cin>>c[i]; repp(sta1,2,1<<n) { rep(i,0,n) a[i]=sta1>>i&1; int highBit=0; per(i,n+1,0) if(sta1>>i&1) { highBit=i; break; } highBit=n-highBit; int minRange=1<<highBit; int maxRange=(1<<highBit+1)-1; rep(sta2,minRange,maxRange) { rep(i,0,n) { b[i]=sta2>>i&1; d[i]=0; } rep(i,0,n) rep(j,0,n) d[i+j]+=a[i]*b[j]; bool flag=true; rep(i,0,n) if(c[i]!=d[i]) { flag=false; break; } if(flag) { rep(i,0,n) cout<<a[i]<<(i==n?'\n':' '); rep(i,0,n) cout<<b[i]<<(i==n?'\n':' '); return; } } } } ``` --- ## 社交团体 对于每个身份码分解一遍质因数，将每个质数作为图中的一点，借助并查集将每个人拥有的不同质因数进行合并。 最后统计在所有出现过的质因数中，总共存在多少个集合即可。 时间复杂度 $O(v\log\log v + n\sqrt v)$ 或 $O(v+n\sqrt v)$ ？ 注意：身份码为 $1$ 时答案一定 $+1$. ```cpp #define rep(i,a,b) for(auto i=(a);i<=(b);i++) #define pb push_back bool prim[1000050]; // prim[x]：x是否是质数，仅>1有效 int pr[1050],pcnt=0; // pr[i]: 第i个质数，仅1000以内 int pos[1000050],tot=0; // pos[x]: x是第几个质数 bool vis[100050]; // vis[x]: 第x个质数是否出现过 int gp[100050]; void init() { rep(i,2,1000) if(!prim[i]) { pr[++pcnt]=i; pos[i]=++tot; for(int j=i*i;j<=1000000;j+=i) prim[j]=true; } rep(i,1001,1000000) if(!prim[i]) pos[i]=++tot; } int fnd(int p) { return p==gp[p]?p:(gp[p]=fnd(gp[p])); } void merge(int a,int b) { a=fnd(a),b=fnd(b); if(a^b) gp[b]=a; } void solve() { init(); rep(i,1,100000) gp[i]=i; int n; cin>>n; int ans=0; rep(i,1,n) { int d; cin>>d; if(d==1) { ans++; continue; } vector<int> vec; rep(j,1,pcnt) { if(d==1) break; if(d%pr[j]==0) { d/=pr[j]; vec.pb(pr[j]); while(d%pr[j]==0) d/=pr[j]; } } if(d>1) vec.pb(d); for(int &j:vec) vis[pos[j]]=true; repp(j,1,vec.size()) merge(pos[vec[0]],pos[vec[j]]); } rep(i,1,100000) if(vis[i]&&fnd(i)==i) ans++; cout<<ans<<'\n'; } ``` 以下这份是以前的标程，但性能上可能并不是特别优秀 ```cpp int pr[100050],pcnt=0; int pos[1000050]; bool prim[1000050]; void init() { for(int i=2;i<=1000;i++) if(!prim[i]) { pr[++pcnt]=i; pos[i]=pcnt; for(int j=i*i;j<=1000000;j+=i) prim[j]=true; } for(int i=1001;i<=1000000;i++) if(!prim[i]) pr[++pcnt]=i,pos[i]=pcnt; } int gp[100050]; bool vis[100050]; int fnd(int p) { return p==gp[p]?p:(gp[p]=fnd(gp[p])); } void merge(int a,int b) { a=fnd(a),b=fnd(b); if(a!=b) gp[b]=a; } int main() { init(); for(int i=1;i<=pcnt;i++) gp[i]=i; int n,ans=0; scanf("%d",&n); for(int i=1;i<=n;i++) { int d; scanf("%d",&d); if(d==1) { ans++; continue; } vector<int> vec; for(int j=1;j<=pcnt;j++) { if(d==1) break; if(!prim[d]) { vec.push_back(d); break; } if(d%pr[j]==0) { vec.push_back(pr[j]); while(d%pr[j]==0) d/=pr[j]; } } for(int j=1;j<vec.size();j++) merge(pos[vec[0]],pos[vec[j]]); for(int j:vec) vis[pos[j]]=true; } for(int i=1;i<=pcnt;i++) if(vis[i]&&i==fnd(i)) ans++; printf("%d\n",ans); return 0; } ``` --- ## 连续表示法 预处理出每个字符对应的编号，可以用 $map$ 也可以直接用数组，然后使用双指针处理即可。 时间复杂度 $O(n)$. ```cpp unordered_map<char,int> id; void init() { int d=0; for(char c='A';c<='Z';c++)id[c]=++d; for(char c='a';c<='z';c++)id[c]=++d; for(char c='0';c<='9';c++)id[c]=++d; } char s[205]; void solve() { scanf("%s",s); int n=strlen(s),i=0; while(i<n) { if(i==n-1) { putchar(s[i]); break; } if(id[s[i+1]]-id[s[i]]==1) { int j=i+1; while(j<n&&id[s[j]]-id[s[j-1]]==1) j++; printf("[%c%c]",s[i],s[j-1]); i=j; } else if(id[s[i+1]]-id[s[i]]==-1) { int j=i+1; while(j<n&&id[s[j]]-id[s[j-1]]==-1) j++; printf("(%c%c)",s[i],s[j-1]); i=j; } else { putchar(s[i]); i++; } } putchar('\n'); } ``` --- ## 相似折线图 根据题意，我们需要在原折线图中找出变化趋势与询问的折线相同的一段子折线图，高度不要求相同。 因此，可以做一遍前缀差，将折线图描述为相邻两点的差值序列，题目就变成了在序列中查找一段连续子序列。 使用 KMP 或哈希均可，数据范围较小，并没有什么哈希冲突。 时间复杂度 $O(nq+mq)$. ```cpp // KMP #define rep(i,a,b) for(auto i=(a);i<=(b);i++) #define repp(i,a,b) for(auto i=(a);i<(b);i++) #define pb push_back int n,m,H[10050],h[1050]; int S[10050],T[1050],Next[1050]; void getNext() { int j=0; Next[1]=0; rep(i,2,m) { while(j>0&&T[i]!=T[j+1]) j=Next[j]; if(T[i]==T[j+1]) j++; Next[i]=j; } } bool KMP() { int j=0; rep(i,1,n) { while(j>0&&S[i]!=T[j+1]) j=Next[j]; if(S[i]==T[j+1]) j++; if(j==m) return true; } return false; } void solve() { cin>>n; rep(i,0,n) cin>>H[i]; rep(i,1,n) S[i]=H[i]-H[i-1]; int q; cin>>q; vector<int> ans; rep(i,1,q) { cin>>m; rep(j,0,m) cin>>h[j]; rep(j,1,m) T[j]=h[j]-h[j-1]; getNext(); if(KMP()) ans.pb(i); } cout<<ans.size()<<'\n'; repp(i,0,ans.size()) cout<<ans[i]<<(i+1==ans.size()?'\n':' '); } ``` ```cpp // 哈希 #define rep(i,a,b) for(auto i=(a);i<=(b);i++) #define repp(i,a,b) for(auto i=(a);i<(b);i++) #define pb push_back int n,m,H[10050],h[1050]; int S[10050],T[1050]; const ll chsh=13331; ll hsh[10050],bs[10050]; void solve() { cin>>n; rep(i,0,n) cin>>H[i]; bs[0]=1; rep(i,1,n) { S[i]=H[i]-H[i-1]; hsh[i]=(hsh[i-1]*chsh+S[i]+100)%mod; bs[i]=bs[i-1]*chsh%mod; } int q; cin>>q; vector<int> ans; rep(i,1,q) { cin>>m; rep(j,0,m) cin>>h[j]; ll hs=0; rep(j,1,m) { T[j]=h[j]-h[j-1]; hs=(hs*chsh+T[j]+100)%mod; } rep(j,m,n) { if(hs==(hsh[j]-hsh[j-m]*bs[m]%mod+mod)%mod) { ans.pb(i); break; } } } cout<<ans.size()<<'\n'; repp(i,0,ans.size()) cout<<ans[i]<<(i+1==ans.size()?'\n':' '); } ``` --- ## 关于我转生成为位运算大师但做的却是一道关于前缀和的题目这件事 观察三个函数： - 当符号为按位与 `&` 时，$x\&(x-1)$ 的含义也就是消除 $x$ 二进制位上最低位的 $1$。因此总操作次数为 $x$ 二进制上 $1$ 的个数； - 当符号为按位或 `|` 时，如果 $x$ 初始时最低位为 $1$，那么 $x|(x-1)=x$ 恒成立；如果 $x$ 初始时最低位为 $0$，那么 $x-1$ 的最低位为 $1$，在执行一次后将来到循环状态。因此总操作次数为 $[x\text{是偶数}]$； - 当符号为按位异或 `^` 时，如果当前 $x=1$，那么 $1\oplus 0=1$ 恒成立；否则，记当前最低位 $1$ 的位置为 $p$，所有比 $p$ 更高的位在进行一次异或操作后都将变为 $0$，而所有比 $p$ 更低的位本应都是 $0$，但在 $x-1$ 后都将变为 $1$，因此在一次操作后 $x$ 将会变为 $2^{p+1}-1$，操作两次后将变为 $1$，此后将来到循环状态。综上，总操作次数为 $[x\text{是偶数}]+1$，特殊的，当 $x=1$ 时总操作次数为 $0$. 对于这三个函数的前缀和函数： - 当符号为按位与 `&` 时，考虑统计 $1\sim n$ 内每个数的二进制上 $1$ 的个数之和。按每一位出现的次数来计算，例如在 $2^i$ 位上的数是以 $2^{i+1}$ 作为周期循环出现的，且每个周期内的前 $2^i$ 个数为 $0$，后 $2^i$ 个数为 $1$，因此直接整除后计算周期数统计个数，最后一个周期根据模数计算个数即可。 - 当符号为按位或 `|` 时，因为只有在 $x$ 是偶数时次数为 $1$，因此 $\lfloor\frac n 2\rfloor$ 即为答案； - 当符号为按位异或 `^` 时，除 $x=1$ 时答案为 $0$ 外，其余情况下在 $x$ 为偶数时次数为 $2$，为奇数时次数为 $1$，也就是在 $x\ge 2$ 时次数均为“按位或 `|` ”时 $+1$，因此答案即 $\lfloor\frac n 2\rfloor+n-1$. 时间复杂度 $O(T\log n)$. ```cpp #define rep(i,a,b) for(auto i=(a);i<=(b);i++) void solve() { ll n,ans=0; cin>>n; rep(i,0,56) { ans+=(n+1)/(1LL<<(i+1))*(1LL<<i); ans+=max(0LL,(n+1)%(1LL<<(i+1))-(1LL<<i)); } cout<<ans<<' '; cout<<n/2<<' '; cout<<n/2+n-1<<'\n'; } ``` 下面这份代码是以前写的标程，已经忘了当时是怎么想的了…… ```cpp ll a[60]; int main() { a[0]=1; for(int i=1;i<=56;i++) a[i]=(a[i-1]<<1)+(1LL<<(i-1))-1; int T; scanf("%d",&T); while(T--) { ll n; scanf("%lld",&n); ll ans1=0,ans2=n/2,ans3=n/2*3-(n%2==0?1:0),t=0; while(n) { for(int i=56;i>=0;i--) { if(n>>i&1) { ans1+=a[i]+t*(1LL<<i); t++; n^=(1LL<<i); break; } } } printf("%lld %lld %lld\n",ans1,ans2,ans3); } return 0; } ``` --- ## 换根树 先假定树的根结点为 $1$，处理出树上每个结点的深度与父子关系 假如现在询问的是当 $u$ 结点为根时，$v$ 结点的父亲结点的编号，那么讨论 $u$ 和 $v$ 在以 $1$ 为根的树上的关系： - 如果 $LCA(u,v)=u$，即 $u$ 是 $v$ 的祖先，那么 $v$ 的父结点也就是在以 $1$ 为根的树上的父结点； - 如果 $LCA(u,v)\ne u\text{ or }v$，即 $u$ 和 $v$ 的最近公共祖先是其它结点，相同的，$v$ 如果要向 $u$ 走，一定是需要在以 $1$ 为根的树上向深度浅的结点走的，也就是说 $v$ 的父结点也就是在以 $1$ 为根的树上的父结点； - 如果 $LCA(u,v)=v$，即 $v$ 是 $u$ 的祖先，那么此时就需要找出 $u$ 在 $v$ 的哪个子结点的子树上，那个子结点就是答案。考虑记录 dfs 序，对于每个结点在每次回溯时都记录一遍，以形成一个长度不超过 $2n$ 的序列，并对于每个结点使用 $vector$ 记录分别有哪些时刻访问了该结点。在这样的约束下，$u$ 结点的整个 DFS 序列一定被包含于 $v$ 结点的 DFS 序列当中，取出最后一次访问 $u$ 结点的时刻 $t$，在整个 $v$ 结点的 DFS 序列中二分查找比 $t$ 大的最小时刻 $tim$，那么对于整个 DFS 序列而言，第 $tim-1$ 时刻所访问的结点正是答案。 时间复杂度 $O(n\log n)$. 当然也可以离线处理询问，时间复杂度应该能优化到 $O(n)$ 吧（但怎么看大家的 $O(n)$ 写法比 $O(n\log n)$ 用的时间还要多哇）。 ```cpp #include<bits/stdc++.h> using namespace std; const int MAXN=100050,MAXF=18; int n,q; vector<int> G[MAXN]; vector<int> vertex_clock[MAXN]; int dfs_clock[MAXN<<1],clk=0; int depth[MAXN]; int father[MAXN][MAXF]; void dfs(int u,int fa) { dfs_clock[++clk]=u; vertex_clock[u].push_back(clk); depth[u]=depth[fa]+1; father[u][0]=fa; for(int i=1;i<MAXF;i++) father[u][i]=father[father[u][i-1]][i-1]; for(int &v:G[u]) { if(v==fa) continue; dfs(v,u); dfs_clock[++clk]=u; vertex_clock[u].push_back(clk); } } int lca(int a,int b) { if(depth[a]>depth[b]) swap(a,b); while(depth[a]<depth[b]) for(int i=MAXF-1;i>=0;i--) if(depth[b]-(1<<i)>=depth[a]) b=father[b][i]; if(a==b) return a; while(father[a][0]!=father[b][0]) for(int i=MAXF-1;i>=0;i--) if(father[a][i]!=father[b][i]) { a=father[a][i]; b=father[b][i]; } return father[a][0]; } int main() { scanf("%d",&n); for(int i=2;i<=n;i++) { int d; scanf("%d",&d); G[i].push_back(d); G[d].push_back(i); } dfs(1,0); scanf("%d",&q); while(q--) { int root,node; scanf("%d%d",&root,&node); if(root==node) puts("-1"); else { if(node==lca(root,node)) { int tim=*upper_bound( vertex_clock[node].begin(), vertex_clock[node].end(), vertex_clock[root][vertex_clock[root].size()-1] ); printf("%d\n",dfs_clock[tim-1]); } else printf("%d\n",dfs_clock[vertex_clock[node][0]-1]); } } return 0; } ``` --- ## 跑业务 由于每次被管制后通过那些道路的时间一定是缩小的，因此可以先借助 Floyd 或 Dijkstra 预处理出整张图任意两点间的最短路 $dis[i][j]$。 对于每次询问，假设现在每次只管制一条路 $(u,v)$，其通行时间变成了 $w$，那么便是一道经典题（应该吧）。我们在跑单子的过程中，从 $a$ 点前往 $b$ 点共有以下三种方式： - 不主动选择经过 $(u,v)$，即通行时间为管制前的最短时间 $dis[a][b]$； - 主动选择经过 $(u,v)$，并先到达 $u$ 再到达 $v$，则目前的最短时间为 $dis[a][u]+w+dis[v][b]$； - 主动选择经过 $(u,v)$，并先到达 $v$ 再到达 $u$，则目前的最短时间为 $dis[a][v]+w+dis[u][b]$。 而当管制的道路数量多起来之后，不仅是要枚举每条路**是否主动选择经过**，每条路**经过的方向**如何，还要枚举**经过选中的这些路的顺序**。对于 $i\in[2,K]$ 的每个 $i$，从 $A_{i-1}$ 前往 $A_i$ 都需要这样枚举一次。 总时间复杂度为 $O(N^3+Q\cdot K\cdot 2^H\cdot H!\cdot 2^H\cdot H)$. > 纯暴力的Dijkstra如果写得好的话应该能冲过去吧？就算冲不过去也有很多分能拿。 ```cpp #define rep(i,a,b) for(auto i=(a);i<=(b);i++) #define repp(i,a,b) for(auto i=(a);i<(b);i++) #define REPP(i,a,b,s) for(auto i=(a);i<(b);i+=(s)) #define pb push_back const int MAXN=405; const int MAXM=10005; const int MAXK=35; const int MAXH=5; int n,m,k; int dis[MAXN][MAXN]; int a[MAXK]; int u[MAXM],v[MAXM],w[MAXM]; int b[MAXH],d[MAXH]; void solve() { cin>>n>>m; mst(dis,INF); rep(i,1,m) { cin>>u[i]>>v[i]>>w[i]; dis[u[i]][v[i]]=dis[v[i]][u[i]]=min(dis[u[i]][v[i]],w[i]); } rep(i,1,n) dis[i][i]=0; rep(i,1,n) rep(j,1,n) rep(k,1,n) dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]); cin>>k; rep(i,1,k) cin>>a[i]; int q; cin>>q; while(q--) { int h; cin>>h; repp(i,0,h) cin>>b[i]>>d[i]; int ans=0; rep(i,2,k) // 每条大边 { int len=dis[a[i-1]][a[i]]; repp(sta,1,1<<h) // 状态：是否一定要走过管制的边 { vector<int> vec; repp(j,0,h) if(sta>>j&1) vec.pb(j); // 必须走过的边的编号 int sum=0,tmp=INF,siz=vec.size(); for(int &g:vec) sum+=d[g]; // 取这些边的时间总和 do { repp(rev,0,1<<siz) // 是否翻转某些边的两点 { vector<int> dot; dot.pb(a[i-1]); repp(j,0,siz) if(rev>>j&1) { dot.pb(u[b[vec[j]]]); dot.pb(v[b[vec[j]]]); } else { dot.pb(v[b[vec[j]]]); dot.pb(u[b[vec[j]]]); } dot.pb(a[i]); int s=sum; REPP(j,0,dot.size(),2) s+=dis[dot[j]][dot[j+1]]; tmp=min(tmp,s); } }while(next_permutation(all(vec))); len=min(len,tmp); } ans+=len; } cout<<ans<<'\n'; } } ```