9.10 CSP 模拟 34
T1 斐波那契数
由于边权只有 \(\{0,1\}\)，因此生成树的边权和取值连续，求出最小和最大判断即可。
点击查看代码
int t;
int n,m;
struct edge{
int u,v,w;
edge()=default;
edge(int u_,int v_,int w_):u(u_),v(v_),w(w_){}
}e[maxn];
int bel[maxn];
int find(int x){
if(x==bel[x]) return x;
else return bel[x]=find(bel[x]);
}
inline int Kruskal1(){
for(int i=1;i<=n;++i) bel[i]=i;
sort(e+1,e+m+1,[&](edge A,edge B){
return A.w<B.w;
});
int cnt=0,sum=0;
for(int i=1;i<=m;++i){
int u=e[i].u,v=e[i].v,w=e[i].w;
int fu=find(u),fv=find(v);
if(fu==fv) continue;
bel[fv]=fu;
++cnt,sum+=w;
}
if(cnt!=n-1) return n+1;
return sum;
}
inline int Kruskal2(){
for(int i=1;i<=n;++i) bel[i]=i;
sort(e+1,e+m+1,[&](edge A,edge B){
return A.w>B.w;
});
int cnt=0,sum=0;
for(int i=1;i<=m;++i){
int u=e[i].u,v=e[i].v,w=e[i].w;
int fu=find(u),fv=find(v);
if(fu==fv) continue;
bel[fv]=fu;
++cnt,sum+=w;
}
return sum;
}
int f[30];
int main(){
t=read();
while(t--){
n=read(),m=read();
for(int i=1,u,v,w;i<=m;++i){
u=read(),v=read(),w=read();
e[i]=edge(u,v,w);
}
int l=Kruskal1(),r=Kruskal2();
printf("%d %d\n",l,r);
bool chk=false;
f[1]=1,f[2]=1;
for(int i=1;i<=26;++i){
if(i>=3) f[i]=f[i-1]+f[i-2];
if(l<=f[i]&&f[i]<=r) chk=true;
}
if(chk) printf("YES\n");
else printf("NO\n");
}
return 0;
}
T2 期末考试
判断 \(S\) 是否合法，即判断是否对于所有 \(i\)，有 \(|S\cap T_i|=a_i\)。
发现 \(O(4^10n)\) 不能接受，但 \(O(4^5n)\) 是可以的。分成前后两半形如 \(f(S_1,i)+g(S_2,i)=a_i\)，可以把 \(f(S_1)\) 哈希存入 map，对于每个 \(g(S_2)\) 可以求出希望得到的 \(f\)，查询个数即可。
点击查看代码
struct Data{
int k;
Data()=default;
Data(int k_):k(k_){}
int operator&(const Data &rhs)const{
int res=0;
for(int i=1;i<=5;++i){
int now=3<<2*(i-1);
if((k&now)==(rhs.k&now)) ++res;
}
return res;
}
};
int t;
int n;
Data T[maxn][2];
int a[maxn];
char ch[12];
int g[maxs][maxn];
map<int,int> mp;
int ans;
int main(){
t=read();
while(t--){
n=read();
for(int i=1;i<=n;++i){
scanf("%s",ch+1);
a[i]=read()/10;
T[i][0].k=T[i][1].k=0;
for(int j=1;j<=5;++j){
T[i][0].k|=(ch[j]-'A')<<2*(j-1);
T[i][1].k|=(ch[j+5]-'A')<<2*(j-1);
}
}
mp.clear();
for(int s=0;s<(1<<10);++s){
int h=0;
for(int i=1;i<=n;++i){
int now=Data(s)&T[i][0].k;
h=(1ll*h*base%mod+now)%mod;
}
++mp[h];
}
ans=0;
for(int s=0;s<(1<<10);++s){
int h=0;
for(int i=1;i<=n;++i){
int now=a[i]-(Data(s)&T[i][1].k);
h=(1ll*h*base%mod+now)%mod;
}
ans+=mp[h];
}
printf("%d\n",ans);
}
return 0;
}
T3 麻烦的工作
贪心，任务按所需人数降序排序，优先安排人数较多的。证明似乎可以考虑拟阵（以后应该会学）。
那么就是对于每个 \(i\)，判断是否：
\[\sum_{j=1}^m \min(i,b_j)\ge \sum_{i=1^n} a_i \]左侧可以套路转化成设 \(c_i\) 表示不小于 \(i\) 的 \(b_j\) 个数，变成：
\[\sum_{i=1}^n c_i-\sum_{i=1}^n a_i\ge 0 \]线段树维护。
修改 \(b\) 是平凡的后缀加减，修改 \(a\) 时要求降序，因此如果增加则修改第一个，如果减少则修改最后一个。
点击查看代码
int n,m,q;
int a[maxn],b[maxn],c[maxn];
int id[maxn],sum[maxn];
int L[maxn],R[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int mn[maxn<<2];
int tag[maxn<<2];
inline void push_up(int rt){
mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
inline void push_down(int rt){
if(tag[rt]){
mn[rt<<1]+=tag[rt],tag[rt<<1]+=tag[rt];
mn[rt<<1|1]+=tag[rt],tag[rt<<1|1]+=tag[rt];
tag[rt]=0;
}
}
void build(int rt,int l,int r){
tag[rt]=0;
if(l==r) return mn[rt]=c[l]-sum[l],void();
build(lson),build(rson);
push_up(rt);
}
void update_range_add(int rt,int l,int r,int pl,int pr,int k){
if(pl<=l&&r<=pr){
mn[rt]+=k,tag[rt]+=k;
return;
}
push_down(rt);
if(pl<=mid) update_range_add(lson,pl,pr,k);
if(pr>mid) update_range_add(rson,pl,pr,k);
push_up(rt);
}
#undef mid
#undef lson
#undef rson
}S;
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i) a[i]=read(),id[i]=i;
sort(id+1,id+n+1,[&](int A,int B){
return a[A]>a[B];
});
for(int i=1;i<=m;++i){
b[i]=read();
++c[1],--c[b[i]+1];
}
for(int i=1;i<=n;++i) c[i]+=c[i-1];
for(int i=1;i<=n;++i){
++R[a[i]];
sum[i]=sum[i-1]+a[id[i]],c[i]+=c[i-1];
}
int now=0;
for(int i=lim;i>=0;--i){
if(R[i]) L[i]=now+1,R[i]+=now,now=R[i];
else L[i]=R[i]=0;
}
S.build(1,1,n);
q=read();
while(q--){
int opt=read(),x=read();
if(opt==1){
int p=L[a[x]];
S.update_range_add(1,1,n,p,n,-1);
if(L[a[x]]==R[a[x]]) L[a[x]]=R[a[x]]=0;
else ++L[a[x]];
++a[x];
if(!L[a[x]]&&!R[a[x]]) L[a[x]]=R[a[x]]=p;
else ++R[a[x]];
}
else if(opt==2){
int p=R[a[x]];
S.update_range_add(1,1,n,p,n,1);
if(L[a[x]]==R[a[x]]) L[a[x]]=R[a[x]]=0;
else --R[a[x]];
--a[x];
if(!L[a[x]]&&!R[a[x]]) L[a[x]]=R[a[x]]=p;
else --L[a[x]];
}
else if(opt==3){
++b[x];
if(b[x]<=n) S.update_range_add(1,1,n,b[x],n,1);
}
else{
if(b[x]<=n) S.update_range_add(1,1,n,b[x],n,-1);
--b[x];
}
printf("%d\n",(S.mn[1]>=0));
}
return 0;
}
T4 小 X 的 Galgame
策略应当为将 \(u\) 存档时，一次性去到所有应当去到的叶子，再去被 \(u\) 子树内其他节点存档时覆盖的叶子，反过来考虑就是每个叶子是在到根路径上第一个节点 \(u\) 存档时被去到的。
可以将 \(1\) 看作被存档，而如果一个节点没有存档，但子树内和祖先都存在存档点，那么这个节点是否存档没有影响，不妨看作存档。
这样存档的节点实际是原树删去一些叶子部分的子树剩余的全部子树，根据这个性质，DP 变得容易。
设 \(f_u\) 表示 \(u\) 子树没有存档的最小代价，实际就是 \(u\) 到所有叶子距离之和，\(g_u\) 表示 \(u\) 子树被存档的最小代价。
设 \(cnt_u\) 为 \(u\) 子树内的叶子个数，那么 \(f_u\) 转移是容易的。
\(g_u\) 转移是讨论儿子 \(v\) 有没有存档，没有存档即 \(cnt_u\times w(u,v)+g_v\)，有存档即 \(\mathrm{dist}(1,v)+f_v\)。
注意到在实际过程中，存在一个有存档的 \(v\)，是直接从 \(u\) 而不是 \(1\) 出发的，相当于如果存在有存档的 \(v\)，那么最终 \(g_u\) 应当减去 \(\mathrm{dist}(1,u)\)。这部分可以特殊处理，具体只需要维护差值的最小值，判断是否存在有存档的 \(v\) 或者将一个不存档的替换成有存档的来减去 \(\mathrm{dist}(1,u)\) 会不会更优。
点击查看代码
int n;
struct edge{
int v,w;
edge()=default;
edge(int v_,int w_):v(v_),w(w_){}
};
vector<edge> E[maxn];
ll dis[maxn];
ll f[maxn],g[maxn];
int cnt[maxn];
void dfs(int u,int fa){
if(u!=1&&(int)E[u].size()==1) return cnt[u]=1,void();
for(edge e:E[u]){
int v=e.v,w=e.w;
if(v==fa) continue;
dis[v]=dis[u]+w;
dfs(v,u);
cnt[u]+=cnt[v];
}
ll mn=llinf;
for(edge e:E[u]){
int v=e.v,w=e.w;
if(v==fa) continue;
f[u]+=f[v]+1ll*w*cnt[v];
g[u]+=min(f[v]+1ll*w*cnt[v],g[v]+dis[v]);
mn=min(mn,(g[v]+dis[v])-(f[v]+1ll*w*cnt[v]));
}
if(mn<0) g[u]-=dis[u];
else if(mn<dis[u]) g[u]+=mn-dis[u];
}
int main(){
n=read();
for(int i=1,u,v,w;i<n;++i){
u=read(),v=read(),w=read();
E[u].push_back(edge(v,w)),E[v].push_back(edge(u,w));
}
dfs(1,0);
printf("%lld\n",g[1]);
return 0;
}