20231030 B 组模拟赛 题解
前言
从这场开始模拟赛质量开始断崖式下跌，天天一堆锅。所以后面到 NOIP 前很多我都不打算改了。
T1
首先显而易见的是，对于任意一个 $k$，$[n+1,2n]$ 中在二进制下有 $k$ 个 $1$ 的数的数量是单调不减的。
证明很简单，考虑 $n\to n+1$，会去掉 $n+1$，新增 $2n+2,2n+1$。容易发现 $2n+2$ 和 $n+1$ 中 $1$ 的个数是相等的，只会新增一个 $2n+1$。即不会减少，只会增加。
那么可以二分答案。然后对于区间内“二进制下有 $k$ 个 $1$ 的数的数量”可以拆成两个前缀，还是比较好求的，大概思路类似于数位 DP，就不展开讲了。
另外题目有锅，答案在 long long 范围内，不知道文件是改前还是改后的。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=__int128;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
void print(i64 x,i64 p=0){
if(x==0){
if(p==0){
putchar('0');
}
return;
}
print(x/10,p+1);
putchar(x%10+'0');
}
#undef gc
const i64 inf=2e18;
i64 t,m,k;
i64 C[75][75],p2[75];
i64 f(i64 x,i64 k,i64 st=70){
if(st<k) return 0;
if(x==0&&k==0) return 1;
if(x==0||k==0) return 0;
i64 h=st;
while(p2[h]>x){
--h;
}
i64 res=C[h][k];
res+=f(x-p2[h],k-1,h);
return min(res,inf);
}
signed main(){
t=read();
forup(i,0,70){
C[i][0]=1;
forup(j,1,i){
C[i][j]=C[i-1][j-1]+C[i-1][j];
if(C[i][j]>inf) C[i][j]=inf;
}
}
p2[0]=1;
forup(i,1,70){
p2[i]=p2[i-1]*2;
}
while(t--){
m=read();k=read();
i64 ll=1,rr=1e18,mm;
while(ll<rr){
mm=(ll+rr)>>1;
if(f(mm<<1,k)-f(mm,k)<m) ll=mm+1;
else rr=mm;
}
i64 ans1=ll;
ll=ans1,rr=2e18;
while(ll<rr){
mm=(ll+rr)>>1;
if(f(mm<<1,k)-f(mm,k)==m) ll=mm+1;
else rr=mm;
}
i64 ans2=ll-ans1;
print(ans1);putchar(' ');print(ans2);puts("");
}
}
T2
首先容易发现我们可以对每个数找到“能删掉它的最小数”。具体而言，能删掉 $x$ 的最小数 $y=(\left\lfloor\sqrt{2x}\right\rfloor+1)^2-x$。容易发现它大概是分成一段一段递减的（就是对于前半段相等的，后半段显然是个一次函数）。观察小数据发现上段 $y$ 的最大值小于下一段的最小值，接下来考虑证明。
首先分段的依据是 $(\left\lfloor\sqrt{2x}\right\rfloor+1)^2$ 不相等，即 $\left\lfloor\sqrt{2x}\right\rfloor$ 不相等。设 $k=\left\lfloor\sqrt{2x}\right\rfloor$。
容易发现，对于一个 $k$，该段最大的 $x$ 为 $\left\lfloor\frac{(k+1)^2-1}{2}\right\rfloor$，最小的 $x$ 为上一段的最大值 $+1$，即 $\left\lfloor\frac{k^2-1}{2}\right\rfloor+1$。那么对应的 $y$ 就分别是 $(k+1)^2-\left\lfloor\frac{(k+1)^2-1}{2}\right\rfloor$ 和 $(k+1)^2-\left\lfloor\frac{k^2-1}{2}\right\rfloor-1$。故 $k+1$ 段 $y$ 的最小值就是 $(k+2)^2-\left\lfloor\frac{(k+2)^2-1}{2}\right\rfloor$。我们要证明的就是 $(k+1)^2-\left\lfloor\frac{k^2-1}{2}\right\rfloor-1<(k+2)^2-\left\lfloor\frac{(k+2)^2-1}{2}\right\rfloor$。
右边减左边，得：
$$ \begin{aligned} &(k+2)^2-\left\lfloor\frac{(k+2)^2-1}{2}\right\rfloor-\left((k+1)^2-\left\lfloor\frac{k^2-1}{2}\right\rfloor-1\right)\\ =&k^2+4k+4-k^2-2k-1+1+\left\lfloor\frac{k^2-1}{2}\right\rfloor-\left\lfloor\frac{(k+2)^2-1}{2}\right\rfloor\\ =&2k+4+\left\lfloor\frac{k^2-1}{2}\right\rfloor-\left\lfloor\frac{k^2+4k+3}{2}\right\rfloor \end{aligned} $$
然后分奇偶性讨论（因为下取整里面的分母是 $2$）。
若 $k$ 是奇数，那么 $k^2-1,k^2+4k+3$ 均是偶数，则有：
$$ \begin{aligned} &2k+4+\left\lfloor\frac{k^2-1}{2}\right\rfloor-\left\lfloor\frac{k^2+4k+3}{2}\right\rfloor\\ =&2k+4+\frac{(k^2-1)-(k^2+4k+3)}{2}\\ =&2k+4+\frac{-4k-4}{2}\\ =&2>0 \end{aligned} $$
若 $k$ 是偶数，那么那俩东西均是奇数，则有：
$$ \begin{aligned} &2k+4+\left\lfloor\frac{k^2-1}{2}\right\rfloor-\left\lfloor\frac{k^2+4k+3}{2}\right\rfloor\\ =&2k+4+\left\lfloor\frac{k^2-2}{2}\right\rfloor-\left\lfloor\frac{k^2+4k+2}{2}\right\rfloor\\ =&2k+4+\frac{(k^2-2)-(k^2+4k+2)}{2}\\ =&2k+4+\frac{-4k-4}{2}\\ =&2>0 \end{aligned} $$
其实几乎是一样的
那么也就是说，我们找到 $n$ 对应的 $k$ 后，$1\sim k-1$ 段全部都能被删掉，第 $k$ 段有一个后缀可以被删掉。
实现很简单，就不细说了。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=__int128;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
void print(i64 x,i64 p=0){
if(x==0){
if(p==0){
putchar('0');
}
return;
}
print(x/10,p+1);
putchar(x%10+'0');
}
#undef gc
const i64 N=1e18,inf=0x3f3f3f3f;
i64 t,n,ans;
signed main(){
t=read();
while(t--){
n=read();
ans=(1+n)*n/2;
i64 nw=sqrtl((n-1)*2+1);
i64 pp=((nw-1)*(nw-1)+1)/2-1,ed=(nw*nw-1)/2,len=n-(nw*nw)/2,st=ed-len+1;
ans-=(1+pp)*pp/2;ans-=(st+ed)*(ed-st+1)/2;
print(ans);puts("");
}
}
T3
首先容易发现，我们构造出的操作序列必然是先通过一系列操作得到一个 $a=b$ 的状态，然后执行多次 $a\gets a+b$，然后再进行若干次减一。容易发现对于一个固定的 $a=b$，后面两步要执行多少次是可以 $O(1)$ 计算的。也就是说，我们把问题转化成了“对于所有 $i=[1,n]$，求出到达 $a=b=i$ 的状态至少需要多少次操作”。
首先一个比较简单的想法是，将一个数 $i$ 向它的所有倍数 $ki$ 和 $i-1$ 连边，边权是转化到对应状态需要的代价（分别是 $k$（因为还要执行一次 $b\gets a$）和 $1$）。然后跑一边迪杰求最短路。这样边数是 $O(n\log n)$（$\frac{n}{1}+\frac{n}{2}+\frac{n}{3}\dots$）的，$O(n\log^2n)$ 不太能过，考虑优化。
那么很显然，一个点只需要向它的质数倍连边，复杂度就变成了 $O(n\log n\log\log n)$，就能过了。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e6+5,inf=0x3f3f3f3f;
int n,dis[N<<1],vis[N<<1],ans;
struct Node{
int a,dis;
bool operator <(const Node &r)const{return dis>r.dis;}
};
priority_queue<Node> q;
vector<int> pri;
int vv[N<<1];
void init(){
forup(i,2,n*2){
if(!vv[i]){
pri.push_back(i);
}
for(auto j:pri){
if(i*j>n*2) break;
vv[i*j]=1;
if(!(i%j)) break;
}
}
}
signed main(){
n=read();
if(n==0){
puts("1");
return 0;
}
init();
mem(dis,0x3f);
dis[1]=0;
q.push(Node{1,0});
while(q.size()){
int a=q.top().a;q.pop();
if(vis[a]) continue;
vis[a]=1;
for(auto i:pri){
if(a*i>n*2) break;
if(dis[a*i]>dis[a]+i){
dis[a*i]=dis[a]+i;
q.push(Node{a*i,dis[a*i]});
}
}
if(a>0&&dis[a-1]>dis[a]+1){
dis[a-1]=dis[a]+1;
q.push(Node{a-1,dis[a-1]});
}
}
printf("%d\n",dis[n]);
}
T4
很聪明的一道题，但是我很蠢。
题目的意思就是让你复制一些边（复制两端点和边权），把原图变成欧拉回路，问加的这些边边权和最小是多少。
首先考虑经典结论：欧拉回路存在的充要条件为每个点度数都为偶数，证明略。由于每条边会给整张图贡献 $2$ 的度数，那么总度数就是偶数。可以简单推出有偶数个点度数为奇数。我们的目标就是把它们的度数变为偶数。
容易发现若复制了一条链，那么只有链两端的点度数奇偶性会改变。也就是说如果我们想同时改变 $A,B$ 度数的奇偶性，只需要复制他们俩之间的最短路即可，可以先跑一遍 floyd 预处理。
那么相当于最初有一个大小为偶数的点集 $S$，表示 $S$ 内的点度数全为奇数。然后每次操作可以花费 $dis_{x,y}$ 的代价把 $x,y$ 两个点都删掉，问删掉整个点集需要的最小代价，容易想到 dp。设 $f_{msk}$ 为删成 $msk$ 需要的最小代价，转移就是枚举删那两个，记搜即可。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=20,inf=1e18;
i64 n,m,mp[N+5][N+5],ans,dp[1<<N|5],deg[N+5];
i64 solve(i64 msk){
if(dp[msk]!=inf) return dp[msk];
i64 res=inf;
forup(i,1,n-1){
if(!(msk&(1<<(i-1)))||!(deg[i]&1)) continue;
forup(j,i+1,n){
if(!(msk&(1<<(j-1)))||!(deg[j]&1)) continue;
res=min(res,solve(msk^(1<<(i-1))^(1<<(j-1)))+mp[i][j]);
}
}
dp[msk]=res;
return res;
}
signed main(){
n=read();m=read();
forup(i,1,n){
forup(j,1,n){
mp[i][j]=inf;
}
mp[i][i]=0;
}
forup(i,1,m){
i64 u=read(),v=read(),w=read();
mp[u][v]=mp[v][u]=min(mp[u][v],w);
ans+=w;
deg[u]++;deg[v]++;
}
forup(k,1,n){
forup(i,1,n){
if(i==k) continue;
forup(j,1,n){
mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
}
}
}
i64 msk=0;
forup(i,1,n){
forup(j,1,n){
if(mp[i][j]==inf){
puts("-1");
return 0;
}
}
if(!(deg[i]&1)) msk|=(1<<(i-1));
}
mem(dp,0x3f);
forup(i,0,(1<<n)-1){
dp[i]=inf;
}
dp[msk]=0;
printf("%lld\n",solve((1<<n)-1)+ans);
}