校内模拟-2024-3-28
A
原题链接
【题意】
求树上距离（无边权）为 $k$ 的无序点对数。
$1\le n\le 5\times 10^4,1\le k\le 500$。
【解析】
这题我做过（惊恐）于是场上秒了。
可以左转我的题解。
我的做法是 DP，复杂度 $O(nk)$。
B
原题链接
【题意】
给定一棵无边权的树，树上有 $m$ 个关键点，你要选择其中一个出发，到达其余所有关键点，路径（显然）可重复。费用定义为经过边的总数，求最小费用和对应的出发点（多个费用相同的点取最小）。
【解析】
容易发现，答案一定是一些走两遍的路径和一些走一遍的路径组成的，所以为了最小化答案，走一遍的路径就是直径。答案就是 （要经过的点数 $-1$）$\times 2$ $-$ 直径。
猜到这个结论就好想了，考虑如果要经过一个点，当且仅当其子树内有关键点，所以从直径开始 dfs 即可。
别忘了特判只有一个点的情况。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define F(i,x,y) for(int i=x;i<=y;++i)
#define fo(i,x,y) for(int i=x;i>=y;--i)
#define mem(x,y) memset(x,y,sizeof(x))
#define eb emplace_back
#define pii pair<int,int>
#define endl '\n'
constexpr int N=2e5+10;
constexpr int inf=0x3f3f3f3f;
constexpr ll INF=0x3f3f3f3f3f3f3f3f;
constexpr db eps=1e-8;
int n,m;
vector<int> e[N];
int st[N],f[N],cnt;
int dfs(int u,int fa,int dis){
f[u]=dis;
for(int v:e[u]){
if(v==fa) continue;
st[u]|=dfs(v,u,dis+1);
}
return st[u];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
int x,y;
F(i,1,n-1){
cin>>x>>y;
e[x].eb(y);
e[y].eb(x);
}
F(i,1,m){
cin>>x;
st[x]=1;
}
if(m==1){
cout<<x<<endl<<0<<endl;
return 0;
}
int c1=0,c2=0;
dfs(x,0,0);
F(i,1,n) if(st[i]&&f[i]>f[c1]) c1=i;
dfs(c1,0,0);
F(i,1,n){
if(st[i]){
cnt++;
if(f[i]>f[c2]) c2=i;
}
}
cout<<min(c1,c2)<<endl;
cout<<(cnt-1)*2-f[c2]<<endl;
return 0;
}
|
C
原题链接
【题意】
给定 $3$ 个长为 $n$ 的字符串，串中的字符表示一个数（如 ‘A’ 表示相同的一个数）。在 $n$ 进制下，前两个字符串代表的数的和等于第三个串代表的数。求每个字符 $c$ 代表的唯一数 $x$（’A’ $\le c\le$ ‘Z’,$0\le x\le 9$）
【解析】
先考虑爆搜。其实真的就是爆搜，从低位到高位枚举，最后再判断是否可行。可以获得 $40$ 分的好成绩（我考场就是这样的）。
我们想想能不能优化一下爆搜，剪一下枝。容易想到第一个显然的剪枝，最高位不能有进位，不然会超出 $n$ 位。这样是不够的，再考虑如果已经枚举出来一些数了，我们无法判断只是因为不知道是否有进位。
那么根据题目，进位最多为 $1$。所以判断一下，如果进不进位都不成立的话显然不行。
这样就可以通过本题，复杂度十分玄学，我不会算。听说正解是高斯消元，我也不会，先咕着。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define F(i,x,y) for(int i=(x);i<=(y);++i)
#define Fo(i,x,y) for(int i=(x);i>=(y);--i)
int n;
string a,b,c;
int x[30],y[30],z[30];
int num[30],nex[30],st[30],cnt,flag;
bool chk(){
if(num[x[0]]+num[y[0]]>=n) return true;
Fo(i,n-1,0){
int t1=num[x[i]],t2=num[y[i]],t3=num[z[i]];
if(t1==-1||t2==-1||t3==-1) continue;
if((t1+t2)%n!=t3&&(t1+t2+1)%n!=t3) return true;
}
return false;
}
bool chk2(){
int tmp=0,i=n-1;
while(i>=0){
if((num[x[i]]+num[y[i]]+tmp)%n!=num[z[i]]) break;
tmp=(num[x[i]]+num[y[i]]+tmp)/n;
i--;
}
return (i<0);
}
void dfs(int s){
if(chk()||flag) return ;
if(s==n){
if(chk2()){
F(i,0,n-1) cout<<num[i]<<" ";
flag=1;
}
return ;
}
Fo(i,n-1,0){
if(!st[i]){
st[i]=1;
num[nex[s]]=i;
dfs(s+1);
st[i]=0;
num[nex[s]]=-1;
}
}
}
void init(int x){
if(!st[x]){
st[x]=1;
nex[cnt++]=x;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>a>>b>>c;
memset(num,-1,sizeof(num));
F(i,0,n-1){
x[i]=(int)a[i]-'A';
y[i]=(int)b[i]-'A';
z[i]=(int)c[i]-'A';
}
Fo(i,n-1,0){
init(x[i]);
init(y[i]);
init(z[i]);
}
F(i,0,n-1) st[i]=0;
dfs(0);
return 0;
}
|
D
原题链接
【题意】
给定一棵 $n$ 个节点的树，每条边有边权，求出树上两点距离小于等于 $k$ 的点对数量。
【解析】
跟第一题和板子题很像对吧（其实就是点分治板子）。记录所有出现过的距离，双指针尝试更新，容斥减掉子树内的答案并分治。复杂度 $O(n\ log^2n)$。
没啥好说的，很板。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define eb emplace_back
const int N=1e5+10;
const int inf=0x3f3f3f3f;
int n,k;
struct edge{
int v,next,w;
}e[N];
int tot,rt,sum,cnt,ans;
int head[N],vis[N],mx[N],siz[N],dis[N],rem[N];
void add(int u,int v,int w){
e[++tot].v=v;
e[tot].w=w;
e[tot].next=head[u];
head[u]=tot;
}
void getroot(int u,int fa){
siz[u]=1;
mx[u]=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
if(v==fa||vis[v]) continue;
getroot(v,u);
siz[u]+=siz[v];
mx[u]=max(mx[u],siz[v]);
}
mx[u]=max(mx[u],sum-siz[u]);
if(mx[u]<mx[rt]) rt=u;
}
void getdis(int u,int fa){
rem[++cnt]=dis[u];
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
if(vis[v]||v==fa) continue;
dis[v]=dis[u]+e[i].w;
getdis(v,u);
}
}
int calc(int u,int s){
cnt=0;
dis[u]=s;
getdis(u,0);
sort(rem+1,rem+cnt+1);
int l=1,r=cnt,res=0;
while(l<=r){
if(rem[l]+rem[r]<=k){
res+=(r-l);
l++;
}
else r--;
}
return res;
}
void solve(int u){
vis[u]=1;
ans+=calc(u,0);
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
if(vis[v]) continue;
ans-=calc(v,e[i].w);
mx[rt=0]=inf;
sum=siz[v];
getroot(v,u);
solve(rt);
}
}
signed main(){
cin>>n;
for(int i=1,x,y,z;i<n;++i){
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
cin>>k;
mx[rt]=sum=n;
getroot(1,0);
solve(rt);
cout<<ans<<endl;
return 0;
}
|
总而言之，这场模拟赛还是不错的，锻炼了我的点分（就是 B 题想到正解了没对很可惜，以后加强训练代码能力）。希望能越来越好，撒花！
