原文链接： https://zhuanlan.zhihu.com/p/683282513
2024牛客寒假算法基础集训营5-个人题解
（开幕雷击，wcgo）
A：mutsumi的质数合数
签到题，只需要注意1既不是质数也不是合数即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
int n;cin>>n;
int num=0,val;
for(int i=1;i<=n;i++){
cin>>val;
if(val<2)num++;
}
cout<<n-num<<'\n';
return 0;
}
B：tomorin的字符串迷茫值
做法其实相当的简单粗暴，赛时没想出来，忏悔...
既然不能删除连续的字符，那么就只有"mygo"，"m_ygo"，"my_go"，"myg_o"，"m_y_go"，"m_yg_o"，"my_g_o"，"m_y_g_o"这8种子串能够通过删除得到"mygo"；
那么我们就只需要寻找这八种子串的数量。对于匹配的子串，子串内的删除方式是唯一确定的，因此现在需要考虑子串外删除的方式有多少种：只需要分别求左边删的方式数和右边删的方式数，再相乘即可得。
至于怎么求删除方式的种数，我们考虑对于任意一个长度为n字符串，由于不能连续删除，我们这里使用dp，简单思考易知转移方程为dp[i]=dp[i-1]+dp[i-2]，其中dp[i]表示长度为i的字符串有多少种删除方式（发现这就是个斐波那契数列）
那么愉快解决问题：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e9+7;
ll f[200005];
bool check(string s1,string s2){
for(int i=0;i<s1.size();i++){
if(s1[i]=='x')continue;
else{
if(s1[i]!=s2[i]) return 0;
}
}
return 1;
}
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
string s;
cin>>s;
int n=s.size();
f[0]=1;f[1]=2;
for(int i=2;i<=n;i++){
f[i]=(f[i-1]+f[i-2])%M;//f[i]表示长度为i的字符串有多少删除方式
}
s=" "+s+"诶...一辈子？（笑）";
ll sum=0;
vector<string>str={"mygo","mxygo","myxgo","mygxo","mxyxgo","myxgxo","mxygxo","mxyxgxo"};
for(int i=0;i<n;i++){
for(auto &j:str){
auto x=s.substr(i,j.size());
if(check(j,x)){
//cout<<j<<" "<<x<<'\n';
sum=(sum+f[i-1]*f[n-(i+j.size())+1])%M;
}
}
}
cout<<sum<<"\n";
return 0;
}
C：anon的私货
比较典的贪心题，思路是：在两个数字之间插入x个0，可以等效为这两个数字同时减去x；
了解思路之后代码就很好写了：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200010];
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
int n;cin>>n;
for(int i=2;i<=2*n;i+=2){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>a[i];
}
a[0]=1e9;a[2*n+2]=1e9;
ll num=0;
for(int i=1;i<=2*n+1;i+=2){
ll s=min(a[i+1]-1,a[i-1]-1);
a[i+1]-=s;a[i-1]-=s;
num+=s;
}
cout<<num<<"\n";
return 0;
}
D：soyorin的树上剪切
仍是赛时没做出来（唉，剪切线）
//后补
E：soyorin的数组操作（easy）
显然n%2==0时，若干次操作总能使得原数组变为非降序；
那么我们其实只需要探讨n%2==1的情况：
由于k是偶数，此时我们最多只能操控到倒数第二个数。
通过最后一个数与倒数第二个数的差值，我们可以知道倒数第二个数最多能被操作多少次，如此操作；然后，倒数第四个数最多能被操作多少次也可以算出来...依次类推，这样，我们可以知道所有偶数位上的数字最多能被操作多少次。
所有操作完成后，判断数组是否有序即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100010];
//ll prex[10010];
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
int t;cin>>t;
while(t--){
bool flg=0;
int n;cin>>n;
//ll maxn=0;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(n%2==0)flg=1;
else{
ll sum=0;
for(int i=n-1;i>=2;i-=2){
a[i]+=sum*i;
a[i-1]+=sum*(i-1);
if(a[i]>a[i+1]){
break;
}
ll t=(a[i+1]-a[i])/i;
sum+=t;
a[i]+=t*i;
a[i-1]+=t*(i-1);
// if(a[i-1]>a[i]){
// break;
// }
}
if(is_sorted(a+1,a+1+n)){
flg=1;
}
}
if(flg)cout<<"YES"<<"\n";
else cout<<"NO"<<"\n";
}
return 0;
}
F：soyorin的数组操作（hard）
与上题唯一的不同是偶数的计算，这里使用二分强行糊过去的（数据似乎不是很强...）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100010];
int n;
bool check(ll x){
ll b[100010]={};
for(int i=1;i<=n;i++){
b[i]=a[i];
}
for(int i=1;i<=n;i++){
b[i]+=x*i;
}
if(is_sorted(b+1,b+1+n)){
return 1;
}
else{
return 0;
}
}
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
int t;cin>>t;
while(t--){
bool flg=0;
cin>>n;
//ll maxn=0;
for(int i=1;i<=n;i++){
cin>>a[i];
}
ll sum=0;
if(n%2==0){
flg=1;
ll l=0,r=1e9,mid=0,ans=0;
while(l<r){
mid=l+(r-l)/2;
if(!check(mid)){
l=mid+1;
}
else{
ans=mid;
r=mid;
}
}
sum=ans;
}
else{
for(int i=n-1;i>=2;i-=2){
a[i]+=sum*i;
a[i-1]+=sum*(i-1);
if(a[i]>a[i+1]){
break;
}
ll t=(a[i+1]-a[i])/i;
sum+=t;
a[i]+=t*i;
a[i-1]+=t*(i-1);
}
if(is_sorted(a+1,a+1+n)){
flg=1;
}
}
if(flg)cout<<sum<<"\n";
else cout<<-1<<"\n";
}
return 0;
}
G：sakiko的排列构造（easy）
构造题，经典数字找规律。
一开始没思路，搓了两个样例之后豁然开朗了。
比如：1 2 3 4 5 6
我们发现，如果将其倒序，即6 5 4 3 2 1，此时 均为7，都是质数，符合题意；
那如果是：1 2 3 4 5 6 7 呢？
我们发现，大于7的最小质数是11，这意味着我们需要往11上凑，但显然不是所有的数都能凑出11。
这时候，我们发现只需用1 2 3这前三个凑不出11的数字垫一下，后面接上的7 6 5 4就都能凑出11。
那么前三个怎么凑呢？事实上样例中就有：1 3 2即可。
那么1 3 2 7 6 5 4就是该样例的一个解。
那么此时我们基本也明白这个题的做法了：
首先用埃氏筛求出1~2n的所有质数；
接下来是dfs(n)的操作：
然后在1~n中遍历i，当n+i为质数时停止遍历，这样是为了找到大于n的最小质数；
那么此时我们就可以找到一个“断点”了：范围内数字需要全部倒序输出；
然后我们继续dfs(i-1)，直到1~n的所有数字都被输出。
在1e3范围内是一定有解的，所以不需要输出-1（开始的时候写一半忘了加-1的输出条件发现还过了.jpg）
丑陋的dfs如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vis[2000];
int prime[2000];
void sieve(int n){//埃氏筛
int i,j,k;
k=0;
vis[0]=vis[1]=1;
for(i=2;i<=n;i++)
{
if(vis[i]==0)
prime[k++]=i;
for(j=i+i;j<=n;j+=i)
vis[j]=1;
}
}
void dfs(int n){
if(n==0) return;
else if(n==1){cout<<1<<" ";return;}
else if(n==2){cout<<2<<" "<<1<<" ";return;}
for(int i=1;i<=n;i++){
if(!vis[n+i]){
dfs(i-1);
for(int j=n;j>=i;j--){
cout<<j<<" ";
}
break;
}
}
}
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
int n;cin>>n;
sieve(2*n);
//cout<<vis[n+1]<<'\n';
dfs(n);
//cout<<-1<<'\n';
return 0;
}
H：sakiko的排列构造（hard）
与上题的唯一区别是数组大小和-1的输出。
（赛时忘改数组大小就交了，喜提一发罚时）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vis[1000006];
int prime[1000006];
void sieve(int n)
{
int i,j,k;
k=0;
vis[0]=vis[1]=1;
for(i=2;i<=n;i++)
{
if(vis[i]==0)
prime[k++]=i;
for(j=i+i;j<=n;j+=i)
vis[j]=1;
}
}
bool flg=0;
void dfs(int n){
if(n==0) return;
else if(n==1){cout<<1<<" ";return;}
else if(n==2){cout<<2<<" "<<1<<" ";return;}
for(int i=1;i<=n;i++){
if(!vis[n+i]){
flg=1;
dfs(i-1);
for(int j=n;j>=i;j--){
cout<<j<<" ";
}
break;
}
}
}
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
int n;cin>>n;
sieve(2*n);
//cout<<vis[n+1]<<'\n';
dfs(n);
//cout<<-1<<'\n';
if(!flg)cout<<-1<<'\n';
return 0;
}
I：rikki的最短路
简单模拟，签到题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
ll t,a,k,sum=0;
cin>>t>>a>>k;
if(t>0){
if(-k<=a&&a<=t+k){
sum+=abs(a);
sum+=abs(a-t);
}
else{
sum+=abs(t);
sum+=2*abs(t-a);
}
}
else{
if(-k+t<=a&&a<=k){
sum+=abs(a);
sum+=abs(a-t);
}
else{
sum+=abs(t);
sum+=2*abs(t-a);
}
}
cout<<sum<<"\n";
return 0;
}
J：rikki的数组陡峭值
很妙的贪心：遍历，当发现相邻区间有交集时，将其合并，此时合并的区间变成原来两个区间的交集，就这样将所有能合并的都合并起来，再DP就好了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l[100005],r[100005];
ll dp[100005][2];
vector<pair<ll,ll>> vec;
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>l[i]>>r[i];
}
ll L=l[1],R=r[1];
for(int i=2;i<=n;i++){
if(L<=r[i]&&R>=l[i]){
L=max(L,l[i]);
R=min(R,r[i]);
}
else{
//cout<<"l r"<<L<<" "<<R<<'\n';
vec.push_back({L,R});
L=l[i];R=r[i];
}
}
//cout<<"l r"<<L<<" "<<R<<'\n';
vec.push_back({L,R});
ll ans=0;
for(int i = 1; i < vec.size(); i++){
dp[i][0] = min(dp[i - 1][0] + abs(vec[i].first - vec[i - 1].first), dp[i - 1][1] + abs(vec[i].first - vec[i - 1].second));
dp[i][1] = min(dp[i - 1][0] + abs(vec[i].second - vec[i - 1].first), dp[i - 1][1] + abs(vec[i].second - vec[i - 1].second));
}
cout << min(dp[vec.size()-1][0], dp[vec.size()-1][1]) << endl;
return 0;
}
K：soyorin的通知
DP，其实是个完全背包，但赛时大脑短路没看出来，令人感慨
//后补
L：anon的星星
暴力枚举，签到题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
int n,x;
cin>>n>>x;
int a,b;
bool flg=0;
for(a=0;a<=n;a++){
b=n-a;
if(a-b==x){
cout<<a<<" "<<b<<'\n';
flg=1;
break;
}
}
if(!flg)cout<<-1<<'\n';
return 0;
}
M：mutsumi的排列连通
贪心+讨论。
一个很重要的思路：当可以通过删除操作得到两个以上连通块时，最多只需要两次删除操作；
比如：
a：1 2 3 4 5 6
b：4 5 6 1 3 2
随意找两个处于相同位置的数字，比如数组a中，3在第三列，数组b中，6也在第三列，那么只需要删去3和6就能得到两个以上连通块；
另外，若使用a[x]表示数字x在数组a上的位置，用b[x]表示数字x在数组b上的位置，那么我们知道：当时，似乎只需要一次操作就能将原来的排列分成两个连通块；
但是需要注意一点：当时，可能会是这种情况：
1 2 3 4
1 3 2 4
故此时需要进行特判（判断是否在头部或者尾部）；
至于什么情况下输出-1，简单思考后，我们可以知道只有两种情况：
（1）时
（2）且数组a和b相同时
愉快解决：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100010],b[100010],c[100010];
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
int t;cin>>t;
while(t--){
int n;cin>>n;
int x;
for(int i=1;i<=n;i++){
cin>>x;
a[x]=i;
}
for(int i=1;i<=n;i++){
cin>>x;
b[x]=i;
}
if(n<=1)cout<<-1<<'\n';
else if(n==2){
if(a[1]==b[1]&&a[2]==b[2]){
cout<<-1<<'\n';
}
else{
cout<<1<<'\n';
}
}
else if(n>2){
for(int i=1;i<=n;i++){
c[i]=abs(a[i]-b[i]);
}
//sort(c+1,c+1+n);
bool flg=0;
for(int i=1;i<=n;i++){
if(c[i]<=1){
if(c[i]==0&&(i==1||i==n)){
continue;
}
else{
cout<<1<<'\n';
flg=1;
break;
}
}
}
if(!flg)cout<<2<<'\n';
//if(c[1]<=1)cout<<1<<'\n';
}
for(int i=1;i<=n;i++){
a[i]=0;b[i]=0;c[i]=0;
}
}
return 0;
}
京公网安备 11010502036488号