【题解】牛客小白月赛34
A dd爱科学1.0
两种解法
1、
最长上升子序列
对应
，
表示改至第
位为止，最后一位
的最小代价，
对应转移方程:))
就是答案，复杂度)
两种解法
1、
二分+单调队列维护，复杂度)
#include<bits/stdc++.h>
using namespace std;
char a[1000005],q[1000005];
int n,tail;
int find(char x){
int l,r,mid;
l=1;r=tail;int s=-1;
while (l<=r){
mid=(l+r)/2;
if (x>=q[mid-1]&&x<=q[mid])s=max(s,mid);
if (x>=q[mid])l=mid+1;
else r=mid-1;
}
return s;
}
int main(){
scanf("%d",&n);
scanf("%s",a+1);
q[0]='A'-1;tail=0;
for (int i=1;i<=n;i++)
if (a[i]>=q[tail])q[++tail]=a[i];
else{
int x=find(a[i]);
if (x!=-1)q[x]=a[i];
}
printf("%d\n",n-tail);
} 2、dp 对应转移方程:
#include<bits/stdc++.h>
using namespace std;
int n,ans;
char a[1000005];
int f[1000005][30];
int main(){
scanf("%d",&n);
scanf("%s",a+1);
memset(f,0x3f,sizeof(f));
for (int i=1;i<=26;i++)f[0][i]=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=26;j++)f[i][j]=min(f[i][j-1],f[i-1][j]+(a[i]!=j+'A'-1));
printf("%d",f[n][26]);
} B dd爱探险 状压dp
首先
个点
次跳完，明白这个跳跃过程其实是一条链，每个点只有被经过和没被经过两个状态，所以典型状压dp
对于状态，转成二进制数形式，第
位对应
或
，对应为时表示这个点已经被经过，对应则表示没有
定义dp数组
,状态表示如上，
表示当前停在这个点上，有
这四个状态，
表示没经过加速，
表示经过一次重力加速，
表示经过一次反重力加速，
表示两次加速都已经结束，注意状态转移
最后枚举最后停留的位置，-1%5D%5Bj%5D%5B3%5D))
就是答案，复杂度)
#include<bits/stdc++.h>
using namespace std;
int n,p[20][20],f[65540][20][5];
int c[20],a[20],b[20];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for (int j=1;j<=n;j++)scanf("%d",&p[i][j]);
memset(f,0x3f,sizeof(f));
for (int i=0;i<n;i++)f[1<<i][i+1][0]=0;
for (int t=1;t<(1<<n);t++){
int y=t;
for (int i=1;i<=n;i++)c[i]=y%2,y/=2;
int m1,m2;
m1=m2=0;
for (int i=1;i<=n;i++)
if (c[i])a[++m1]=i;
else b[++m2]=i;
for (int i=1;i<=m1;i++)
for (int j=1;j<=m2;j++){
f[t+(1<<(b[j]-1))][b[j]][0]=min(f[t+(1<<(b[j]-1))][b[j]][0],f[t][a[i]][0]+p[a[i]][b[j]]);
f[t+(1<<(b[j]-1))][b[j]][1]=min(f[t+(1<<(b[j]-1))][b[j]][1],min(f[t][a[i]][0],f[t][a[i]][1]+p[a[i]][b[j]]));
f[t+(1<<(b[j]-1))][b[j]][2]=min(f[t+(1<<(b[j]-1))][b[j]][2],min(f[t][a[i]][0]+2*p[a[i]][b[j]],f[t][a[i]][2]+p[a[i]][b[j]]));
f[t+(1<<(b[j]-1))][b[j]][3]=min(f[t+(1<<(b[j]-1))][b[j]][3],min(f[t][a[i]][1]+2*p[a[i]][b[j]],f[t][a[i]][2]));
f[t+(1<<(b[j]-1))][b[j]][3]=min(f[t+(1<<(b[j]-1))][b[j]][3],f[t][a[i]][3]+p[a[i]][b[j]]);
}
}
int ans=1000000000;
for (int i=1;i<=n;i++)ans=min(ans,f[(1<<n)-1][i][3]);
printf("%d\n",ans);
} C dd爱科学2.0 dp
与A题dp解法一样，只要转移条件改成)))
即可
#include<bits/stdc++.h>
using namespace std;
int n,ans;
char a[1000005];
int f[1000005][30];
int main(){
scanf("%d",&n);
scanf("%s",a+1);
memset(f,0x3f,sizeof(f));
for (int i=1;i<=26;++i)f[0][i]=0;
for (int i=1;i<=n;++i)
for (int j=1;j<=26;++j)f[i][j]=min(f[i][j-1],f[i-1][j]+abs(a[i]-(j-1+'A')));
printf("%d",f[n][26]);
} D dd爱矩阵 贪心+优先队列
先把问题简化一下，如果两行，每行个数，怎么选
把两行分别降序
，如果令第一行为数组
，第二行为数组
则可得到最大值为
，并且得到
且
所以可以把
全部推入优先队列当中，并且标记对应的,每次取出
，再把
推入优先队列当中，次操作即可得到前大
复杂度
回到这个题目，由于是行，可以每次处理两行，并成一行新的，次操作把行并成一行，复杂度)
#include<bits/stdc++.h>
using namespace std;
int n,a[1005],b[1005],c[1005];
struct t{
int x,z;
friend bool operator<(t x,t y){
return x.z<y.z;
}
};
bool cmp(int x,int y){
return x>y;
}
int main(){
priority_queue<t>q;
scanf("%d",&n);
for (int i=1;i<=n;i++)scanf("%d",&b[i]);
sort(b+1,b+1+n,cmp);
for (int i=2;i<=n;i++){
for (int j=1;j<=n;j++)scanf("%d",&a[j]);
sort(a+1,a+1+n,cmp);
for (int j=1;j<=n;j++){
t p;
p.x=1;p.z=a[1]+b[j];q.push(p);
}
for (int j=1;j<=n;j++){
t pp=q.top();t p;
q.pop();
c[j]=pp.z;
p.x=pp.x+1;
p.z=pp.z-a[pp.x]+a[p.x];
q.push(p);
}
for (int j=1;j<=n;j++)b[j]=c[j];
while (!q.empty())q.pop();
}
for (int j=1;j<=n;j++)printf(j==n?"%d\n":"%d ",b[j]);
} E dd爱旋转 模拟，算复杂度肯定不能每次操作完整个矩阵动一次
发现每次操作都会上下翻转，所以上下可以通过操作次数的奇偶直接控制
操作
相当于在上下翻转的情况下左右再翻转一次，所以再左右可以通过操作次数奇偶直接控制
所以直接一遍枚举判断情况解决，复杂度)
#include<bits/stdc++.h>
using namespace std;
int n,Q;
int a[2005][2005];
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)scanf("%d",&a[i][j]);
scanf("%d",&Q);
int s1,s2;
s1=s2=1;
while (Q--){
int x;
scanf("%d",&x);
s1=1-s1;
if (x==2)s2=1-s2;
}
if (s1==1)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)printf(j==n?"%d\n":"%d ",s2?a[i][j]:a[i][n-j+1]);
else
for (int i=n;i>=1;i--)
for (int j=n;j>=1;j--)printf(j==1?"%d\n":"%d ",s2?a[i][j]:a[i][n-j+1]);
} F dd爱框框 单调队列维护窗口移动，复杂度)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,a[10000005],w;
int n;
int main(){
scanf("%d%lld",&n,&x);
for (int i=1;i<=n;i++)scanf("%lld",&a[i]);
int l,r;
l=0;r=n+1;
int s,t;
s=1;t=0;
w=0;
for (int i=1;i<=n;i++){
w+=a[i];t++;
while (w-a[s]>=x)w-=a[s++];
if (w>=x){
if (t-s+1<r-l+1)r=t,l=s;
}
}
printf("%d %d\n",l,r);
} G dd爱捣乱 G题数据出了点问题，影响了部分同学，出题人在这里再次表示抱歉
首先讨论完美串满足条件，如果是奇串，则每一位前后两位不同，即
如果是偶串，则相邻两位不同
综上，只要任意连续三位都满足两两不同，就是一个完美串
那么一个很显然的想法，枚举每一位的情况，保证再枚举前两位情况，保证不同的情况下更新答案
复杂度)
复杂度显然有点偏大，常数没控制好极有可能
所以进一步想，每一位最多只会受前两位和后两位的影响，根据鸽巢原理，实际上最多只有五种情况:
，必有一种情况满足完美串
所以对于每一位只要枚举改变量就行了，表示把第
位的改变量是，第位的改变量是的最小代价
最后枚举最后两位改变量)
就是答案
复杂度)
#include<bits/stdc++.h>
using namespace std;
int n,ans;
char b[1000005];
int a[1000005];
int f[1000005][6][6];
int main(){ scanf("%d",&n); scanf("%s",b+1); for (int i=1;i<=n;i++)a[i]=b[i]-'a'; memset(f,-1,sizeof(f)); for (int i=-2;i<=2;i++) for (int j=-2;j<=2;j++) if ((a[1]+i+26)%26!=(a[2]+j+26)%26)f[2][i+2][j+2]=abs(i)+abs(j); for (int i=3;i<=n;i++) for (int j=-2;j<=2;j++) for (int k=-2;k<=2;k++) if (f[i-1][j+2][k+2]!=-1) for (int t=-2;t<=2;t++) if ((a[i]+t+26)%26!=(a[i-2]+j+26)%26&&(a[i]+t+26)%26!=(a[i-1]+k+26)%26){ if (f[i][k+2][t+2]==-1)f[i][k+2][t+2]=f[i-1][j+2][k+2]+abs(t); else f[i][k+2][t+2]=min(f[i][k+2][t+2],f[i-1][j+2][k+2]+abs(t)); } ans=1e9; for (int i=0;i<=4;i++) for (int j=0;j<=4;j++) if (f[n][i][j]!=-1)ans=min(ans,f[n][i][j]); printf("%d\n",ans); }
H dd爱捣乱 不管是多少，把位置对
取余，余数相等的位置的值必然相等，通过简单贪心可知，肯定是把这些位置的数都改成余数相等的位置中值最小的那个数
因为给定了限制条件
，所以只要枚举所在的位置，可以直接利用前缀和计算出最小改变量，复杂度
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
ll a[1000005],g[1000005],f[1000005],b[1000005];
int main(){
scanf("%d%d",&n,&k);
k++;
for (int i=1;i<=n;i++)scanf("%lld",&a[i]);
for (int i=0;i<k;i++)g[i]=1000000001;
memset(f,0,sizeof(f));
memset(b,0,sizeof(b));
for (int i=1;i<=n;i++)f[i%k]+=a[i];
for (int i=1;i<=n;i++)g[i%k]=min(g[i%k],a[i]);
for (int i=1;i<=n;i++)b[i%k]++;
ll ss=a[1];
for (int i=2;i<=n;i++)ss=min(ss,a[i]);
ll ans=100000000000000000ll;
ll pp=0;
for (int i=1;i<=n;i++)pp+=a[i];
for (int i=0;i<k;i++)
ans=min(ans,f[i]-g[i]*b[i]+pp-f[i]-(1ll*n-b[i])*ss);
printf("%lld\n",ans);
} 
查看1道真题和解析