2024牛客寒假算法基础集训营2

A.Tokitsukaze and Bracelet

B.Tokitsukaze and Cats

C.Tokitsukaze and Min-Max XOR

D.Tokitsukaze and Slash Draw

E and F.Tokitsukaze and Eliminate (easy)(hard)

G.Tokitsukaze and Power Battle (easy)

暂无

I.Tokitsukaze and Short Path (plus)

J.Tokitsukaze and Short Path (minus)

K.Tokitsukaze and Password (easy)

A.Tokitsukaze and Bracelet

阅读理解题，读懂题目按照要求模拟即可,重复的计算使用函数来解决

void solve(){int a,b,c; cin>>a>>b>>c;int ans=0;if(a==150) ans=1;if(a==200) ans=2;auto get = [&](int x){if(x>=29 && x<=32) return 0;if(x==45) return 2;return 1;};ans+=get(b)+get(c);cout<<ans<<endl;return ;
}

B.Tokitsukaze and Cats

我们要计算的是贡献，一个猫带来的贡献是看周围有没有其他的猫导致重复的所以我们就直接用

st[M][M]表示找个位置有没有猫然后看周围位置是不是有猫即可

bool st[M][M];
void solve(){cin>>n>>m>>k;int ans=0;while(k--){int a,b; cin>>a>>b;ans+=!st[a-1][b];ans+=!st[a+1][b];ans+=!st[a][b-1];ans+=!st[a][b+1];st[a][b]=true;}cout<<ans<<endl;return ;
}

C.Tokitsukaze and Min-Max XOR

1.记录方案数从数组中选一堆数出来的

2.与两个数异或<=k

接着分析我们可以发现选出这一堆数其实和整个数中有用的其实只有最大值和最小值，其他的都是看贡献即可

由此假设不考虑其他数的选择题目变成了选两个数异或小于等于k这也就是经典的trie树求解，但是考虑到树上的话，我们也是可以按照从小到大来排序不影响选择吗，同时保证到i的时候是最大值，那么贡献是什么呢贡献就是找到前面的一个满足的数后中间的数可选可不选 $2^{r-l-1}$ 也就是 $\frac{2^{r-1}}{2^l}$

也就是前面的数的贡献是后面的除以他那么我怎么记录前面的数的贡献呢？我们发现本题要的是逆元所以除以一个数可以变成乘以一个数的逆元由此前缀可以用trie数+逆元的贡献来记录即可

然后就是普通的操作了

LL tr[N*32][2],cnt[N*32],idx;LL qmi(LL a,LL b){LL res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
LL inv(LL x){return qmi(x,mod-2);
}
void insert(int x,LL val){int p=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(!tr[p][u]) tr[p][u]=++idx;p=tr[p][u];(cnt[p]+=val)%mod;}
}
LL query(int x,int y){int p=0;LL res=0;for(int i=30;i>=0;i--){int ux=x>>i&1,uy=y>>i&1;if(uy){res=(res+cnt[tr[p][ux]])%mod;if(!tr[p][!ux]) return res;p=tr[p][!ux];}else{if(!tr[p][ux]) return res;p=tr[p][ux];}}res=(res+cnt[p])%mod;return res;
}void intn(){for(int i=0;i<=idx;i++)for(int j=0;j<=1;j++)tr[i][j]=0,cnt[i]=0;idx=0;
}
void solve(){intn();cin>>n>>k;vector<int> a(n+1);for(int i=1;i<=n;i++) cin>>a[i];sort(a.begin()+1,a.end());LL ans=0;for(int i=1;i<=n;i++){(ans+=query(a[i],k)*qmi(2,i-1)%mod+1)%=mod;insert(a[i],inv(qmi(2,i)));}cout<<ans<<endl;return ;
}

D.Tokitsukaze and Slash Draw

典型的轮换变化我们可以直接抽象为图论，由于是最优解也就是最快抵达这个点的解把数和数之间的转化直接看成边即可，然后用dijkstra,由于要他排在第k张牌也就是抽走上面的n-k张牌符合边的要求接着就是初始的时候是0用map存边的最小值减少方案注意LL

void solve(){cin>>n>>m>>k;unordered_map<int,int> mp;for(int i=1;i<=m;i++){int x,y; cin>>x>>y;x%=n;if(!mp.count(x)) mp[x]=y;else mp[x]=min(mp[x],y);}int need=n-k;auto dijkstra = [&](){vector<bool> st(n+5);for(int i=1;i<=n;i++) d[i]=2e18;priority_queue<PII,vector<PII>,greater<PII>> q;q.emplace(0,0);while(!q.empty()){auto [cost,u]=q.top(); q.pop();if(st[u]) continue;st[u]=true;if(u==need) return cost;for(auto&[v,w]:mp){int ne=(u+v)%n;if(d[ne]>cost+w){d[ne]=cost+w;q.emplace(d[ne],ne);}}}return (LL)-1;};cout<<dijkstra()<<endl;return ;
}

E and F.Tokitsukaze and Eliminate (easy)(hard)

做题的时候特别是计算贡献的时候一定要找到贡献的来源，我们可以发现消除一个数(如果找个数在右边第一次出现)之后其最右边的数都会消失，那么怎么做的贡献最少呢，当然十当前数组的每一个数都出现的时候最优的这样的删除一次删除的数最多可以（j结论明显所以直接用map存书的数量即可然后删除）这种最优性贡献都是如此思考

1.贡献来源

2.如何减少贡献

3.贡献是否最优

int a[N];
void solve(){map<int,int> mp,cnt;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];cnt[a[i]]++;}int ans=0;for(int i=n;i>=1;i--){mp[a[i]]++;cnt[a[i]]--;if(mp.size()==cnt.size()){ans++;for(auto&[v,w]:mp){if(cnt[v]==0) cnt.erase(v);}mp.clear();}}cout<<ans<<endl;return ;
}

G.Tokitsukaze and Power Battle (easy)

本质上是一个线段树维护一个区间值

暂无

I.Tokitsukaze and Short Path (plus)

这是明显的计算贡献的题目我们看边的贡献是啥 $|a_v+a_u|+|a_v-a_u| = 2*max(a_u,a_v)$

也就是说两个点之间的边贡献就是两个中的最大值的两倍，我们要计算的是 $\sum_i^n\sum_j^ndist_{i,j}$

所以我们来看每一个点之间带来的贡献如果直接抵达的话i和其他所有点的贡献是两者中的最大值

也就是一个点a和比他小的点的贡献就是 $dist_{a,i}=dist_{i,a}=a_i$ ，同时简单思考两个点直接的最短路会不会中间有过度点，可以发现明显没有假设有的话可以简单论证一定比我现在找个要大，所以找个是最优的贡献，照权重由小到大排序之后 $sum=\sum_i^n2*a_i*(i-1)*2$ ,注意开long long

void solve(){LL sum=0;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);for(int i=1;i<=n;i++){sum+=4*(LL)(i-1)*a[i];}cout<<sum<<endl;return ;
}

J.Tokitsukaze and Short Path (minus)

同上我们分析贡献 $dist_{u,v}=|a_u+a_v|-|a_u-a_v|=min(a_u,a_v)$ 所以这次变成两个点中最小的了，但是如果直接同上一题是不是最优的呢？我们要考虑是否有中间点过度我们可以发现如果过度的是最小值 $a_1$ 我们无法确定最优所以最优就是两者取最小值(也就是考虑齐全看我们的贡献是否是最优的) $disti,j=min(2*a_1,min(a_i,a_j))$

接着同上计算即可注意long long

int a[N];
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);LL sum=0;for(int i=1;i<=n;i++){sum+=4ll*(n-i)*min(2*a[1],a[i]);}cout<<sum<<endl;return ;
}

K.Tokitsukaze and Password (easy)

首先我们读懂题目意思也就是我们需要的是

1.没有前导0

2.是8的倍数

3.<=y

4.其中的abcd字母是同字母数字相同不同字母数字不同(1-9),'-'只有一个也是1-9

数据范围1<=n<=9

首先我们可以发现整个数字的变化其实只有 $5^9$ 所以我们可以考虑dfs直接暴力枚举所有情况即可

然后按照条件一个一个来

1. 特殊如果只有一个数可以为0，其他的如果有变化的话就是从1开始，否则就是不满足要求

2&&3.由于数目较少到最后直接判断即可

4.(1)dfs枚举情况用map存储，同时st记录这个数是不是重复出现，同时记得还原现场

(2)'-'直接枚举

(3)枚举的同时需要满足没有前导0的要求

然后我们按照这个思考大纲书写代码即可

map<char,int> mp;
bool st[10];
void dfs(int u,LL res){if(u==n){if(res<=y && res%8==0) cnt++;return ;}if(s[u]>='0' && s[u]<='9'){if(s[u]=='0' && (!u && n!=1)) return ;dfs(u+1,res*10+(s[u]-'0'));}else if(s[u]=='_'){for(int i=(u==0 ? (n==1 ? 0 : 1) : 0);i<=9;i++){dfs(u+1,res*10+i);}}else{if(mp.count(s[u])) dfs(u+1,res*10+mp[s[u]]);else{for(int i=(u==0 ? (n==1 ? 0 : 1) : 0);i<=9;i++){if(st[i]) continue;mp[s[u]]=i;st[i]=true;dfs(u+1,res*10+i);st[i]=false;mp.erase(s[u]);}}}
}
void solve(){memset(st,0,sizeof st);mp.clear(); cnt=0;cin>>n>>s>>y;dfs(0,0);             cout<<cnt<<endl;return ;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/264650.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！