2022牛客寒假算法基础集训营1

B题 炸鸡块君与FIFA22
题目大意：
给出胜负序列，每次询问区间 (l,r,s) ，回答在经历 (l-r) 之后积分是多少，初始积分为 (s)

胜 (+1) 积分，平 (+0) 积分，败的时候如果此时积分为 (3) 的倍数则 (-0) ，否则 (-1)

思路解析：
(ST) 表，预处理出 (st[k][i][j]) 表示表示在初始分数为k的情况下经历了 ([i,i+2^j-1]) 一段后分数的变化量

查询倍增查询即可

AC代码：
#include<bits/stdc++.h>
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,“Ofast”,“inline”)

#define endl ‘\n’

#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;

int n,q;
char a[maxn];
int st[3][maxn][20],lg[maxn];

void init(){

lg[1]=0;lg[2]=1;
for(int i=3;i<=n;i++)lg[i]=lg[i/2]+1;for(int j=0;j<20;j++){for(int i=1;i+(1<<j)-1<=n;i++){if(!j){if(a[i]=='W')st[0][i][j]=st[1][i][j]=st[2][i][j]=1;if(a[i]=='L')st[0][i][j]=0,st[1][i][j]=st[2][i][j]=-1;if(a[i]=='D')st[0][i][j]=st[1][i][j]=st[2][i][j]=0;}else {int p=i+(1<<(j-1));st[0][i][j]=st[0][i][j-1]+st[(0+st[0][i][j-1]+3)%3][p][j-1];st[1][i][j]=st[1][i][j-1]+st[(1+st[1][i][j-1]+3)%3][p][j-1];st[2][i][j]=st[2][i][j-1]+st[(2+st[2][i][j-1]+3)%3][p][j-1];}}
}

}

int query(int s,int l,int r){

int pos=l;
while(pos<=r){int j=0;while(pos+(1<<j)-1<=r)j++;j--;s+=st[s%3][pos][j];pos+=(1<<j);
}
return s;

}

int main(){

IOScin>>n>>q;cin>>a+1;init();while(q--){int l,r,s;cin>>l>>r>>s;cout<<query(s,l,r)<<endl;
}

}
C题 Baby’s first attempt on CPU
题目大意：
给出 (n) 个句子和每个句子与前三句的关系，如果两句之间有关系的话，那么你必须在他们添加空语句使得有关系的两句话中间至少隔了三句话，问最少需要插入多少空语句使得所有语句合法

思路解析：
模拟，在另一个数组中插入，如果有关系的语句就从后往前看隔了几个，需要插入几个，计算即可

AC代码：
#include<bits/stdc++.h>
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,“Ofast”,“inline”)

#define endl ‘\n’

#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=505;

int n;
int a[maxn][maxn];
int b[maxn*10],top;

int main(){

IOScin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=3;j++){cin>>a[i][j];if(a[i][j]){int now=i-j,sum=0;for(int k=top;k>0;k--){if(b[k]==now)break;sum++;}if(sum<3){for(int k=1;k<=3-sum;k++)b[++top]=0;}}}b[++top]=i;
}
cout<<top-n<<endl;

}
D题 牛牛做数论
题目大意&思路解析：
首先我们要知道取得最大值和最小值实质是让我们求什么：

第一个是让我们计算素数序列的前缀积不超过 (n) 的最大值

第二个是让我们求 ([2,n]) 中最大的质数

前缀积不需要很多素数，因为一小部分的前缀积就已经很大了，超过了 (1e9)

试除法判断素数即可求最大

AC代码：
#include<bits/stdc++.h>
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,“Ofast”,“inline”)

#define endl ‘\n’

#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;

bool pd(int x){
for(int i=2;i<=x/i;i++){
if(x%i==0)return false;
}
return true;
}

ll prime[maxn],st[maxn],tot;
ll sum[maxn];

void get_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i])prime[++tot]=i;
for(int j=1;prime[j]<=n/i;j++){
st[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
}
}

int main(){

IOSint t;
cin>>t;get_primes(100);sum[0]=1;
for(int i=1;i<=100;i++)sum[i]=sum[i-1]*prime[i];while(t--){int n;cin>>n;if(n==1){cout<<-1<<endl;continue;}for(int i=1;i<=n;i++){if(sum[i+1]>n){cout<<sum[i]<<" ";break;}}while(!pd(n))n--;cout<<n<<endl;
}

}
E题 炸鸡块君的高中回忆
题目大意：
有 (n) 个人 (m) 张卡，每一次进去 (m) 个然后回来一个带回 (m) 张卡，重复操作，进来和出去都需要一个单位时间，问最短时间，若无解，输出 (-1)

思路解析：
无解情况：只有一张卡并且总人数大于 (1)

特殊情况：卡的数量大于等于人数，答案为 (1)

一般情况：模拟即可（相当于除了第一次每一次可以带走 (m-1) 个人）

AC代码：
#include<bits/stdc++.h>
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,“Ofast”,“inline”)

#define endl ‘\n’

#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;

int main(){

IOSint t;
cin>>t;while(t--){ll n,m,ans=0;cin>>n>>m;if(m>=n)cout<<1<<endl;else if(m==1)cout<<-1<<endl;else {n-=m;ans++;ans+=n/(m-1)*2;if(n%(m-1))ans+=2;cout<<ans<<endl;}
}

}
F题 中位数切分
题目大意：
给出序列 (a[]) ,和一个正整数 (m) ，问最多可以把序列分成几段，使得每一段的中位数都大于等于 (m) ，（偶数个数的中位数是中间较小的那一个），若无解，输出 (-1)

思路解析：
我们考虑一个合法序列的中位数满足什么条件：序列中大于等于 (m) 的数量大于小于 (m) 的数量。

所以我们可以贪心的去选择：

从前往后枚举，如果当前位置的左边合法并且右边的序列是可分割的，那么就把这一段分割出去

用后缀维护区间大于等于 (m) 的数量即可

AC代码：
#include<bits/stdc++.h>
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,“Ofast”,“inline”)

#define endl ‘\n’

#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;

int n,m;
int a[maxn];
int up[maxn],dn[maxn];

int main(){

IOSint t;
cin>>t;while(t--){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];up[i]=0;dn[i]=0;}for(int i=1;i<=n+50;i++){up[i]=0;dn[i]=0;}for(int i=n;i>=1;i--){up[i]=up[i+1];dn[i]=dn[i+1];if(a[i]>=m)up[i]++;else dn[i]++;}ll ans=0;int l=1;for(int i=1;i<=n;i++){if(i==n){if(up[l]>dn[l])ans++;break;}if((up[l]-up[i+1]>dn[l]-dn[i+1])&&up[i+1]>dn[i+1]){ans++;l=i+1;}}if(ans==0)cout<<"-1"<<endl;else cout<<ans<<endl;
}

}

G题 ACM is all you need
题目大意：
给出序列 (f[]) ,你可以选择一个数 (b) ，使每个 (f_i=|f_i-b|+b) ,问有多少个 (local minimum)

(local minimum) 定义：(f_i<min(f_i-1,f_i+1))

思路解析：
首先 (+b) 是没有用的，可以直接去掉

然后，对与绝对值，我们可以看作是 (f_i) 与 (b) 的距离，对于 (2<=i<=n-1) 的 (f) 来说，我们可以计算出当前数变化后不满足条件是 (b) 的取值范围，可以得到一个 (b) 的区间，那么我们就会得到若干 (b) 的区间,每一个区间代表着使得某一个 (f) 不成立

这样问题就转化为了在数轴上区间覆盖问题，(map) 维护差分即可

AC代码：
#include<bits/stdc++.h>
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,“Ofast”,“inline”)

#define endl ‘\n’

#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;
const int inf=1e9+7;

int n;
int a[maxn];
map<int,int>q;

int main(){

IOSint t;
cin>>t;while(t--){q.clear();cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int tot=0;for(int i=2;i<n;i++){if(a[i]==a[i-1]||a[i]==a[i+1])continue;tot++;if(a[i]<a[i-1]&&a[i]<a[i+1]){int x=min(a[i-1],a[i+1]);q[-1]++;q[(x+a[i]-1)/2+1]--;}else if(a[i]>a[i+1]&&a[i]>a[i-1]){int x=max(a[i-1],a[i+1]);q[(x+a[i])/2+1]++;}else{int x=max(a[i-1],a[i+1]);q[(x+a[i]-1)/2+1]--;int r=(x+a[i]-1)/2;x=min(a[i-1],a[i+1]);q[(x+a[i])/2+1]++;}}ll now=0,ans=q[-1];for(auto &i:q){now+=i.second;ans=min(ans,now);}cout<<ans<<endl;
}

}
H题 牛牛看云
题目大意：
给出序列 (a[]) ，求(\sum_{i=1}^n\sum_{j=i}n|a_i+a_j-1000|)

思路解析：
我们可以在值域上枚举，我们会发现每一个数都会和其他任何一个数计算一次（包括自己），所以我们只需要在值域上枚举计算即可，注意我们枚举计算的时候会多计算一次自己与自己的计算结果，单独计算即可

AC代码：
#include<bits/stdc++.h>
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,“Ofast”,“inline”)

#define endl ‘\n’

#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;

int n;
ll a[maxn];
ll sum[maxn];

int main(){

IOScin>>n;for(int i=1;i<=n;i++){cin>>a[i];sum[a[i]]++;
}
ll ans=0;
for(int i=0;i<=1000;i++){if(sum[i]==0)continue;ll tot=0;for(int j=0;j<=1000;j++){ans+=sum[i]*sum[j]*abs(i+j-1000);}ans+=sum[i]*abs(i+i-1000);
}
cout<<ans/2<<endl;

}
I题 B站与各唱各的
题目大意：
(n) 个人 (m) 句歌词，每个人每一句都可以选择唱或者不唱，如果有一句歌词数所有人都唱了或者都没唱，那么就失败了，否则成功，问期望成功句子的数量

思路解析：
我们可以发现 (m) 句歌词是独立的，所以可以计算每一句成功的期望然后乘以 (m)

可得出结论：(ans=m*\frac{2^n-2}{2n})

AC代码：
#include<bits/stdc++.h>
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,“Ofast”,“inline”)

#define endl ‘\n’

#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;
const int mod=1e9+7;

ll ksm(ll a, ll b)
{
ll ans=1,base=a%mod;
while(b)
{
if(b&1)
ans=ansbase%mod;
base=basebase%mod;
b>>=1;
}
return ans;
}

ll inv(ll x){
return ksm(x,mod-2)%mod;
}

int main(){

IOSint t;
cin>>t;while(t--){ll n,m;cin>>n>>m;if(n==1){cout<<0<<endl;continue;}ll p=ksm(2,n)%mod;cout<<m*(p+mod-2)%mod*inv(p)%mod<<endl;
}

}

J题 小朋友做游戏
题目大意：
给出 (A) 个安静小朋友， (B) 个调皮小朋友，每个人有一个权值，选出 (n) 个人围成一个圈并且满足没有两个调皮小朋友是挨着的，问最大权值和。如果没有任何方案可行，输出 (-1)

思路解析：
首先我们判断无解情况：

在 (n) 个人中，必须选出 ((n+1)/2) 个小朋友来把调皮隔开，所以安静小朋友必须大于等于 ((n+1)/2)

然后我们先从安静小朋友里选择最大的 ((n+1)/2) 个，剩下的和调皮小朋友一起排序，从大到小贪心去选，直到凑成 (n) 个人

AC代码：
#include<bits/stdc++.h>
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,“Ofast”,“inline”)

#define endl ‘\n’

#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;

vectora;
ll b[maxn],q[maxn];

int main(){

IOSint t;
cin>>t;while(t--){int x,y,n;cin>>x>>y>>n;a.clear();for(int i=1;i<=x;i++)cin>>b[i];for(int i=1;i<=y;i++)cin>>q[i];if(x<(n+1)/2){cout<<-1<<endl;continue;}sort(b+1,b+x+1);ll ans=0;for(int i=x-(n+1)/2+1;i<=x;i++){ans+=b[i];}for(int i=1;i<=x-(n+1)/2;i++){a.push_back({b[i],1});}for(int i=1;i<=y;i++){a.push_back({q[i],0});}sort(a.begin(),a.end());int tot=n-(n+1)/2;int sum=(n+1)/2;for(int i=a.size()-1;i>=0;i--){if(sum==n)break;if(tot&&a[i].second==0){ans+=a[i].first;tot--;}else {ans+=a[i].first;}sum++;}cout<<ans<<endl;
}

}