2024牛客寒假算法基础集训营2 补题
A.Tokitsukaze and Bracelet 签到 模拟
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define eb emplace_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;
void Showball(){
int a,b,c;
cin>>a>>b>>c;
cout<<(a/50)-2+(b>=34)+(c>=34)+(b==45)+(c==45)<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T=1;
if(cases) cin>>T;
while(T--)
Showball();
return 0;
}
B.Tokitsukaze and Cats 签到
思路：
两个相邻格子，能够省下一个减速带，所以统计一下相邻格子数量即可。
参考代码：
void Showball(){
int n,m,k;
cin>>n>>m>>k;
vector a(n+1,vector<int>(m+1));
for(int i=0;i<k;i++){
int x,y;
cin>>x>>y;
x--,y--;
a[x][y]++;
}
int cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a[i][j]&&a[i][j+1]) cnt++;
if(a[i][j]&&a[i+1][j]) cnt++;
}
}
cout<<4*k-cnt<<endl;
}
C.Tokitsukaze and Min-Max XOR 01字典树
题意：
给你一个序列 \(a\) , 求升序子序列个数，其中最大值和最小值的异或小于等于 \(k\)。
思路：
假定我们确定了最小值和最大值分别是 \(a_i\) 和 \(a_j\) , 并且 \(a_i\) ^ \(a_j \le k\) 。那么两者之间的数可选可不选，于是有
\(2^{j-i-1}\) 种方案。我们考虑枚举最大值，去找所有满足条件的最小值。然后计算贡献即可。这里可以用字典树去查找最小值的贡献。因为我们需要异或和小于等于 \(k\)。那么当 \(k\) 的该位是 \(1\) 的时候，那么最大值和最小值该位有两种情况：
\(1\) 相同 , 异或和为 \(0\)，所以后面的位可以随便选了，直接加上子树的贡献。
\(2\) 不相同 ，接着往下走。
对于贡献我们拆开表达 \(2^{j-1}/2^i\) , 那么也就是说每个合法的最小值的贡献就是 \(\frac{1}{2^i}\) 。
具体细节参考代码
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define eb emplace_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10, M = 32*N+10;
const int mod = 1e9 + 7;
const int cases = 1;
LL a[N],f[M],son[M][2],idx;
int n,k;
void init(){//初始化字典树
idx=1;
for(int i=0;i<=32*n;i++){
f[i]=son[i][0]=son[i][1]=0;
}
}
void insert(int x,LL val){
int p=1;
for(int i=30;~i;i--){
auto &s=son[p][x>>i&1];
if(!s) s=++idx;
p=s;
f[p]=(f[p]+val)%mod;//维护贡献
}
}
LL search(int x){
LL res=0;
int p=1;
for(int i=30;~i;i--){
int s=x>>i&1;
int t=k>>i&1;
if(t){//k该位为1
if(son[p][s]) res=(res+f[son[p][s]])%mod;//同号直接算上子树贡献
p=son[p][!s];//不同号接着走
}else p=son[p][s];//k该位为0，只能走同号
}
res=(res+f[p])%mod;//更新答案
return res;
}
//快速幂 a^b mod p
LL qmi(int a, int b, int p)
{
LL res = 1 % p;
while (b)
{
if (b & 1) res = res * a % p;
a = a * (LL)a % p;
b >>= 1;
}
return res;
}
LL inv(LL x){//逆元
return qmi(x,mod-2,mod);
}
void Showball(){
cin>>n>>k;
init();
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
LL res=n;
for(int i=2;i<=n;i++){//枚举最大值
insert(a[i-1],inv(qmi(2,i-1,mod)));//插入值，并且插入贡献
res=(res+search(a[i])*qmi(2,i-1,mod)%mod)%mod;//计算贡献
}
cout<<res<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T=1;
if(cases) cin>>T;
while(T--)
Showball();
return 0;
}
D.Tokitsukaze and Slash Draw 最短路
题意：
一共有 \(n\) 张卡牌，有一张关键卡牌在从下往上数第 \(k\) 张的位置，你现在有 \(m\) 种操作，第 \(i\) 种操作你可以
以 \(b_i\) 的代价把顶端的 \(a_i\) 张牌放到牌堆底部，求使得关键牌移动到牌堆顶部时的最小代价。
思路：
此题可以DP或者最短路解决。考虑最短路，对于每种操作，我们可以遍历 \(i\) ，然后从 \(i\) 向 \((i+a_i)\%n\)
连一条权值为 \(b_i\)的边。那么问题就变成了以 \(k-1\) 为起点，终点为 \(n-1\) 的最短路。最短路可以用Dijkstra解决。注意开long long。
参考代码：
void Showball(){
int n,m,k;
cin>>n>>m>>k;
vector<LL> a(m),b(m),dis(n,1e18),st(n);
vector<pair<LL,LL>> e[n];
for(int i=0;i<m;i++) cin>>a[i]>>b[i];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
e[i].eb((i+a[j])%n,b[j]);//建边
}
}
auto dijkstra=[&](int s){//dijkstra
dis[s]=0;
priority_queue<PLL,vector<PLL>,greater<PLL>> q;
q.push({0,s});
while(!q.empty()){
auto [dist,u]=q.top();
q.pop();
if(st[u]) continue;
st[u]=true;
for(auto [v,w]:e[u]){
if(dis[v]>dist+w){
dis[v]=dist+w;
q.push({dis[v],v});
}
}
}
};
dijkstra(k-1);
LL ans=dis[n-1];
if(ans==1e18) ans=-1;
cout<<ans<<endl;
}
E|F.Tokitsukaze and Eliminate 贪心
题意：
有一排的宝石，每个宝石都有颜色，可以进行若干次下列操作：
选择一种颜色，将最右边该颜色的宝石及其右边的所有宝石删除。求出将宝石全部删除的最小操作次数。
思路：
根据贪心策略，我们从后往前考虑，如果在第 \(i\) 个宝石时，发现 \(i\) 之前的宝石所拥有的颜色，已经被全部包含。那么我们就需要用 \(i\) 的颜色进行一次操作，这样可以保证局部最优。容易证明可以推出全局最优(因为前面的所有颜色已经被包含，用其他颜色操作，操作的宝石数只会更少)。
我们可以用 \(b_i\)来维护前 \(i\) 个元素有多少种颜色。接下来计数即可。
参考代码:
void Showball(){
int n;
cin>>n;
vector<int> a(n+1),b(n+1);
set<int> s;
for(int i=1;i<=n;i++) {
cin>>a[i];
s.insert(a[i]);
b[i]=s.size();
}
int ans=0;
set<int> ss;
int st=n;
for(int i=n;i>=1;i--){
ss.insert(a[i]);
if(ss.size()==b[st]){
ans++;
ss.clear();
st=i-1;
}
}
cout<<ans<<endl;
}
G.Tokitsukaze and Power Battle (easy) 树状数组 贪心 线段树
题意：
有一个长度为 \(n\) 的非负整数数组，有 \(q\) 次操作：
1 i x：将第 \(i\) 个数改为 \(x\)2 l r：查询区间 \([l,r]\) 内，每个长度不小于2的子区间，任意分成连续两段后，左段之和减去右段之和的最大值。
思路1： 树状数组+贪心
首先，我们发现题目是要求实现单点修改，区间查询的操作，可以选择树状数组或者线段树。
树状数组比较好写，这里先讲树状数组。首先看操作 \(1\)，将第 \(i\) 个数修改为 \(x\)，转化为将第 \(i\) 增加
\(x-a_i\) 即可。接着看操作 \(2\) ，我们要在\([l,r]\) 中选一个子区间，根据贪心策略，我们的子区间左端点选 \(l\) 是最优的。并且为了让结果更大，显然分成的右段只有一个元素的情况是最优的。那么我们枚举右端点即可。此时时间复杂度是 \(O(q*n*logn)\) ，我们需要将枚举右端点这个进行优化。当然这个优化也是本题的核心。
我们定义目前最优解是 \(res\) ，我们从大到小枚举右端点，设当前枚举的右端点是 \(i\)，如果 \(res \geq getsum(1,i)\) 时，那么我们就不用再继续进行枚举了。因为你选择右端点是 \(i\) 的答案是 \(getsum(l,i-1)-a[i] = getsum(l,i)-2*a[i]\), 以后的右端点自然不会再更新 \(res\) 的值。
接下来我们来分析最多会枚举几次。我们要满足在 \(i\) 之前的 \(res \geq getsum(l,i)\) 。我们令此时选择的右端点是 \(R(R>i)\) ,那么此时的答案应该是 \(getsum(l,R-1)-a[R]=getsum(l,i)+getsum(i+1,R-1)-a[R]\) 。
即：\(getsum(i+1,R-1) \ge a[R]\)。最极端的情况则形如 \(1,2,4,8,16...a[R]\)。
那么最多只需要 \(log(1e9)\)次即可找到最优解。
最终时间复杂度优化为 \(O(q*logn*logn)\)
参考代码：
void Showball(){
int n,q;
cin>>n>>q;
vector<int> a(n+1);
vector<LL> c(n+1);
auto lowbit=[&](int x){return x&-x;};
auto add=[&](int x,int k){while(x<=n){c[x]+=k;x+=lowbit(x);}};
auto sum=[&](int x){LL res=0;while(x>0){res+=c[x];x-=lowbit(x);}return res;};
auto getsum=[&](int l,int r){return sum(r)-sum(l-1);};
for(int i=1;i<=n;i++){
cin>>a[i];
add(i,a[i]);
}
while(q--){
int op,x,y;
cin>>op>>x>>y;
if(op==1) {add(x,y-a[x]);a[x]=y;}
else{
LL res=-1e18;
for(int i=y;i>=x+1;i--){
if(res>=getsum(x,i)) break;
res=max(res,getsum(x,i-1)-a[i]);
}
cout<<res<<endl;
}
}
}
思路2： 树状数组+线段树
根据思路1的分析， 我们只需要用线段树维护区间 \(getsum(l-1)-a[l]\) 的最大值即可。单点修改，维护前缀和我们继续用树状数组解决。因为单点修改完数组 \(a_x\) 的值之后，\([x+1,n]\) 的前缀和也会发生改变，所以就需要线段树区间修改，这个思路思维量小，代码量稍大。具体细节参考代码注释
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define eb emplace_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 5e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;
LL a[N],c[N];
int n,q;
int lowbit(int x){
return x&-x;
}
void add(int x,int k){
while(x<=n){
c[x]+=k;
x+=lowbit(x);
}
}
LL getsum(int x){
LL res=0;
while(x>0){
res+=c[x];
x-=lowbit(x);
}
return res;
}
//线段树
struct node{
int l,r;
LL maxn,tag;
}tr[N*4];
#define ls u<<1
#define rs u<<1|1
void pushup(node &u,node &l,node &r){
u.maxn=max(l.maxn,r.maxn);
}
void pushup(int u){
pushup(tr[u],tr[ls],tr[rs]);
}
void addtag(node &u,LL tag){//更新懒标记
u.maxn+=tag;
u.tag+=tag;
}
void pushdown(int u){
addtag(tr[ls],tr[u].tag);
addtag(tr[rs],tr[u].tag);
tr[u].tag=0;
}
void build(int u,int l,int r){
tr[u].l=l,tr[u].r=r;
tr[u].tag=0;
if(l==r){
tr[u].maxn=getsum(l-1)-a[l];//维护该值
return;
}
int mid=l+r>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,LL tag){//区间修改
if(l<=tr[u].l&&tr[u].r<=r) {
addtag(tr[u],tag);
return;
}
int mid=tr[u].l+tr[u].r>>1;
pushdown(u);
if(l<=mid) modify(ls,l,r,tag);
if(r>mid) modify(rs,l,r,tag);
pushup(u);
}
LL query(int u,int l,int r){//区间查询
if(tr[u].l>r||tr[u].r<l) return -1e18;//不要忘记边界情况
if(l<=tr[u].l&&tr[u].r<=r){
return tr[u].maxn;
}
pushdown(u);
return max(query(ls,l,r),query(rs,l,r));
}
void Showball(){
cin>>n>>q;
for(int i=1;i<=n;i++) c[i]=0;//树状数组清零
for(int i=1;i<=n;i++){
cin>>a[i];
add(i,a[i]);//树状数组初始化
}
build(1,1,n);
while(q--){
int op,x,y;
cin>>op>>x>>y;
if(op==1){
/*注意这里是将a[x]-> y。所以单点修改应该增加y-a[x]。
又因为我们维护的是getsum(x-1)-a[x]。
所以要转换成y-a[x];
*/
modify(1,x,x,a[x]-y);
/*
单点修改后会对后面的区间前缀和影响
*/
if(x<n) modify(1,x+1,n,y-a[x]);
//树状数组更新
add(x,y-a[x]);
a[x]=y;
}else{
//记得减去前面的前缀和
cout<<query(1,x+1,y)-getsum(x-1)<<endl;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T=1;
if(cases) cin>>T;
while(T--)
Showball();
return 0;
}
I.Tokitsukaze and Short Path(plus) 思维
题意：
给你一个 \(n\) 个点的完全图，定义边权 \(w_{i,j}=|a_i+a_j|+|a_i-a_j|\)。
求 \(\sum_{i=1}^n\sum_{j=1}^ndist(i,j)\) 的值， \(dist(i,j)\) 表示从 \(i\) 到 \(j\) 的最短路
思路：
绝对值化简一下，我们发现\(w_{i,j}=2*max(a_i,a_j)\)。
所以 \(dist(i,j)=w_{i,j}\)。
直接算肯定超时，所以我们可以算贡献，每个数的贡献是\(4*a_i*k\)，其中 \(k\) 是比 $a_i $小的数的个数。
排序，统计所有数的贡献即可。
参考代码：
void Showball(){
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
sort(all(a),greater<int>());
LL ans=0;
for(int i=0;i<n;i++){
ans+=4LL*a[i]*(n-i-1);
}
cout<<ans<<endl;
}
J.Tokitsukaze and Short Path (minus) 思维
题意：
此题和 I题一样，不同的是\(w_{i,j}=|a_i+a_j|-|a_i-a_j|\)
思路：
绝对值化简一下，我们发现\(w_{i,j}=2*min(a_i,a_j)\)。
此时 \(dist(i,j)\)不再简单的是 \(w_{i,j}\)。因为取的是最小值，所以从 \(i\) 到 \(j\) 还存在一种路线:
从\(i\) 到 \(k\) ,再从 \(k\) 到 \(j\) ，其中 \(k\) 为数组 \(a\) 最小值对应的下标。算法依旧是先排序，然后
算每个数的贡献，只是比 I题多了一种情况。
参考代码：
void Showball(){
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
sort(all(a));
LL ans=0;
for(int i=0;i<n;i++){
ans+=4LL*min(a[i],2*a[0])*(n-i-1);
}
cout<<ans<<endl;
}
K.Tokitsukaze and Password (easy)
题意：
给你一个含有数字，字符 \(a,b,c,d,\_\) 的字符串。问你这个字符串能够构成多少种符合以下条件的字符串。
1.不含前导0。
2.是8的倍数
3.小于等于给出的数字 \(y\)
4.标记着相同字母的数位上的数字一定相同，标记着不同字母的数位上的数字一定互不相同。标记 \(\_\) 表示任意数字都可以。
思路：
easy版本数据范围小，直接枚举出所有的情况，判断即可。
参考代码：
void Showball(){
int n,y;
string s,t;
cin>>n>>s>>y;
set<int> st;
for(int a='0';a<='9';a++)
for(int b='0';b<='9';b++)
for(int c='0';c<='9';c++)
for(int d='0';d<='9';d++)
for(int _='0';_<='9';_++){
if(a==b||a==c||a==d||b==c||b==d||c==d) continue;
t=s;
for(auto &x:t){
if(x=='a') x=a;
else if(x=='b') x=b;
else if(x=='c') x=c;
else if(x=='d') x=d;
else if(x=='_') x=_;
}
if(n>1&&t[0]=='0') continue;
int k=stoi(t);
if(k<=y&&k%8==0) st.insert(k);
}
cout<<st.size()<<endl;
}